Search code examples
bithuffman-codedeflate

how to correctly decode data when bits are read from right to left?


I have had my fair share of understanding compression so with major discoveries that i will later post on github but i am still unable to manually decode few byte sequence accordingly.

here is the output of a debugging program called infgen:

dynamic                 ! 10 0
count 259 27 14         ! 1010 11010 00010
code 16 2               ! 010
code 17 3               ! 011
code 18 5               ! 101
code 0 5                ! 101
code 8 6                ! 110
code 7 4                ! 100
code 9 4                ! 100
code 6 3                ! 011
code 10 5               ! 101
code 5 4                ! 100
code 11 3               ! 011
code 4 4                ! 100
code 3 6                ! 110 000

and bits were read from right to left why am i not getting:

14 5A B5 D6 E4 CA 11 CE F7

This is what i get for the first byte 14:

00010100

first bit is 0

second 2 bits 10

third 5 bits 00010

what am i missing, because the first 17 bits of deflate are

  • block type 3 bits
  • hdist 5 bits
  • hlit 5 bits
  • hclen 4 bits

Please correct me and my goal is to be able decode these back and forth, so i can change code 16 from 2 to 3 and see how the byte sequence changes.

Thank you


Solution

  • I can read your "why am I not getting" bytes directly from the bits in your infgen output. Take the first three bits 10 0 and put that after the end of the bits on the next line 1010 11010 00010 to get 10101101000010100, taking out the breaks for the symbols. Putting breaks in for the bytes: 1 01011010 00010100. The last eight bits are 0x14, and the next eight bits are 0x5a.