Lines Matching full:bits
67 inflate() sets up a first level table that covers some number of bits of
68 input less than the length of longest code. It gets that many bits from the
70 code is that many bits or less and how many, and if it is, it will tell
72 grabs more bits and tries to decode a longer code.
74 How many bits to make the first lookup is a tradeoff between the time it
78 building the table ends up taking a lot longer for more bits since short
80 simply to make the number of bits in the first table a variable, and then
84 of the first table is nine bits. Also the distance trees have 30 possible
85 values, and the size of the first table is six bits. Note that for each of
88 little more than eight bits for 286 symbols and a little less than five bits
96 lookup table for the first, let's say, nine bits of a Huffman symbol. The
97 symbol could be as short as one bit or as long as 15 bits. If a particular
98 symbol is shorter than nine bits, then that symbol's translation is duplicated
99 in all those entries that start with that symbol's bits. For example, if the
100 symbol is four bits, then it's duplicated 32 times in a nine-bit table. If a
101 symbol is nine bits long, it appears in the table once.
103 If the symbol is longer than nine bits, then that entry in the table points
104 to another similar table for the remaining bits. Again, there are duplicated
112 So a table entry either points to another table (in which case nine bits in
114 and the number of bits to gobble. Then you start again with the next
117 You may wonder: why not just have one lookup table for how ever many bits the
127 So the number of bits for the first lookup table is a trade of the time to
133 The code being decoded, with 10 symbols, from 1 to 6 bits long:
146 Let's make the first table three bits long (eight entries):
154 110: -> table X (gobble 3 bits)
155 111: -> table Y (gobble 3 bits)
157 Each entry is what the bits decode as and how many bits that is, i.e. how
158 many bits to gobble. Or the entry points to another table, with the number of
159 bits to gobble implicit in the size of the table.
161 Table X is two bits long since the longest code starting with 110 is five bits
169 Table Y is three bits long since the longest code starting with 111 is six
170 bits long:
192 indicates a base value and a number of bits to fetch after the code that is
