DokuWiki

This is an old revision of the document!

Level difference encoding Huffman trees

There are two sets of trees. The 6-bit-trees and the 4-bit-trees. The four-bit trees encode values betwenn -7 and 7 in 4-bit-twos-complement representation (so 0..7 and 9..15), while the 6 bit trees store values between 0 and 63 and are used modulo 64 in most contexts anyway, so signed/unsigned doesn't matter. These trees are built as canonical huffman trees from the given length tables.

6-bit trees

Tree 0

0: 2 Bit
1: 3 Bit
2: 4 Bit
3-6: 8 Bit
7-56: 9 Bit
57-59: 8 Bit
60: 4 Bit
61-63: 3 Bit

Tree 1

0: 2 Bit
1-2: 3 Bit
3: 4 Bit
4-6: 8 Bit
7-56: 9 Bit
57-60: 8 Bit
61: 4 Bit
62-63: 3 Bit

Tree 2

0: 1 Bit
1: 3 Bit
2-3: 5 Bit
4: 7 Bit
5-58: 9 Bit
59: 8 Bit
60: 7 Bit
61-62: 5 Bit
63: 3 Bit

Tree 3

0: 2 Bit
1-2: 3 Bit
3-4: 5 Bit
5: 7 Bit
6-57: 9 Bit
58-59: 7 Bit
60-61: 5 Bit
62-63: 3 Bit