count[len]
is the number of codes of each bit length. For the canonical code defined by the deflate format, the codes simply count up from zero. So the first code for the first non-zero count[len]
is len
zero bits. If count[len]
is more than one, then the next code is one more than that, or just len-1
zero bits and a one bit.
When the codes of that length are used, add a zero bit at the end to go to the next length.
Therefore to make the step from the first code of length i
to the first code of length i+1
, you add count[i]
and then shift left by one bit.
Example code:
length code
2 00
2 01
3 100
3 101
3 110
4 1110
4 1111
We start with 00 for the first code, which is of length 2. There are two codes of length 2, so we add two and shift left by one bit, i.e. multiply by two, and get the first code of length 3 which is (0 + 2) * 2 = 4 = 100. To get to the first code of length 4, its (4 + 3) * 2 = 14 = 1110.