3.1.8.1.4.1 Literal, EOS, and Copy-Offset Tables
The length, in bits, for each of the 293 Huffman-encoded LiteralOrEosOrCopyOffset codes are listed in the following table (HuffLengthLEC).
Codes with an index value of 0 to 255 represent a single literal character with that value. Code index 256 indicates that the end of the encoding has been reached. Index values 257 to 288 must be translated by subtracting 257 to find the index value 0 to 31 in the CopyOffsetBitsLUT and CopyOffsetBaseLUT tables, to find the number of bits and base values for a copy operation. Index values 289 to 292 must be translated by subtracting 289 to find the index value 0 to 3 to identify one of the four most recently-used offsets.
|
Code index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|---|---|---|---|---|---|---|---|---|
|
0 |
0x6 |
0x6 |
0x6 |
0x7 |
0x7 |
0x7 |
0x7 |
0x7 |
|
8 |
0x7 |
0x7 |
0x7 |
0x8 |
0x8 |
0x8 |
0x8 |
0x8 |
|
16 |
0x8 |
0x8 |
0x9 |
0x8 |
0x9 |
0x9 |
0x9 |
0x9 |
|
24 |
0x8 |
0x8 |
0x9 |
0x9 |
0x9 |
0x9 |
0x9 |
0x9 |
|
32 |
0x8 |
0x9 |
0x9 |
0xa |
0x9 |
0x9 |
0x9 |
0x9 |
|
40 |
0x9 |
0x9 |
0x9 |
0xa |
0x9 |
0xa |
0xa |
0xa |
|
48 |
0x9 |
0x9 |
0xa |
0x9 |
0xa |
0x9 |
0xa |
0x9 |
|
56 |
0x9 |
0x9 |
0xa |
0xa |
0x9 |
0xa |
0x9 |
0x9 |
|
64 |
0x8 |
0x9 |
0x9 |
0x9 |
0x9 |
0xa |
0xa |
0xa |
|
72 |
0x9 |
0x9 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
80 |
0x9 |
0x9 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
88 |
0xa |
0x9 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
96 |
0x8 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
104 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
112 |
0x9 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
120 |
0x9 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0x9 |
|
128 |
0x7 |
0x9 |
0x9 |
0xa |
0x9 |
0xa |
0xa |
0xa |
|
136 |
0x9 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
144 |
0x9 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
152 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
160 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
168 |
0xa |
0xa |
0xa |
0xd |
0xa |
0xa |
0xa |
0xa |
|
176 |
0xa |
0xa |
0xb |
0xa |
0xa |
0xa |
0xa |
0xa |
|
184 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
192 |
0x9 |
0xa |
0xa |
0xa |
0xa |
0xa |
0x9 |
0xa |
|
200 |
0xa |
0xa |
0xa |
0xa |
0x9 |
0xa |
0xa |
0xa |
|
208 |
0x9 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
216 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
224 |
0x9 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
|
232 |
0xa |
0xa |
0xa |
0xa |
0xa |
0xa |
0x9 |
0xa |
|
240 |
0x8 |
0x9 |
0x9 |
0xa |
0x9 |
0xa |
0xa |
0xa |
|
248 |
0x9 |
0xa |
0xa |
0xa |
0x9 |
0x9 |
0x8 |
0x7 |
|
256 |
0xd |
0xd |
0x7 |
0x7 |
0xa |
0x7 |
0x7 |
0x6 |
|
264 |
0x6 |
0x6 |
0x6 |
0x5 |
0x6 |
0x6 |
0x6 |
0x5 |
|
272 |
0x6 |
0x5 |
0x6 |
0x6 |
0x6 |
0x6 |
0x6 |
0x6 |
|
280 |
0x6 |
0x6 |
0x6 |
0x6 |
0x6 |
0x6 |
0x6 |
0x6 |
|
288 |
0x8 |
0x5 |
0x6 |
0x7 |
0x7 |
|
|
|
Table 1: Bit lengths for the 293 Huffman-encoded LiteralOrEosOrCopyOffset codes
For example, it can be determined from the previous table that the 0th Huffman-encoded LiteralOrEosOrCopyOffset code has a length of 6 bits, and the 131st Huffman-encoded LiteralOrEosOrCopyOffset code has a length of 10 (0x0A) bits.
Using the canonical Huffman algorithm ([SAYOOD] section 4.2.4), the Huffman codebook table shown in the following table (HuffCodeLEC) can be obtained. The bit lengths in the previous table MUST be used to isolate the appropriate bits.
|
Code index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|---|---|---|---|---|---|---|---|---|
|
0 |
0x0004 |
0x0024 |
0x0014 |
0x0011 |
0x0051 |
0x0031 |
0x0071 |
0x0009 |
|
8 |
0x0049 |
0x0029 |
0x0069 |
0x0015 |
0x0095 |
0x0055 |
0x00d5 |
0x0035 |
|
16 |
0x00b5 |
0x0075 |
0x001d |
0x00f5 |
0x011d |
0x009d |
0x019d |
0x005d |
|
24 |
0x000d |
0x008d |
0x015d |
0x00dd |
0x01dd |
0x003d |
0x013d |
0x00bd |
|
32 |
0x004d |
0x01bd |
0x007d |
0x006b |
0x017d |
0x00fd |
0x01fd |
0x0003 |
|
40 |
0x0103 |
0x0083 |
0x0183 |
0x026b |
0x0043 |
0x016b |
0x036b |
0x00eb |
|
48 |
0x0143 |
0x00c3 |
0x02eb |
0x01c3 |
0x01eb |
0x0023 |
0x03eb |
0x0123 |
|
56 |
0x00a3 |
0x01a3 |
0x001b |
0x021b |
0x0063 |
0x011b |
0x0163 |
0x00e3 |
|
64 |
0x00cd |
0x01e3 |
0x0013 |
0x0113 |
0x0093 |
0x031b |
0x009b |
0x029b |
|
72 |
0x0193 |
0x0053 |
0x019b |
0x039b |
0x005b |
0x025b |
0x015b |
0x035b |
|
80 |
0x0153 |
0x00d3 |
0x00db |
0x02db |
0x01db |
0x03db |
0x003b |
0x023b |
|
88 |
0x013b |
0x01d3 |
0x033b |
0x00bb |
0x02bb |
0x01bb |
0x03bb |
0x007b |
|
96 |
0x002d |
0x027b |
0x017b |
0x037b |
0x00fb |
0x02fb |
0x01fb |
0x03fb |
|
104 |
0x0007 |
0x0207 |
0x0107 |
0x0307 |
0x0087 |
0x0287 |
0x0187 |
0x0387 |
|
112 |
0x0033 |
0x0047 |
0x0247 |
0x0147 |
0x0347 |
0x00c7 |
0x02c7 |
0x01c7 |
|
120 |
0x0133 |
0x03c7 |
0x0027 |
0x0227 |
0x0127 |
0x0327 |
0x00a7 |
0x00b3 |
|
128 |
0x0019 |
0x01b3 |
0x0073 |
0x02a7 |
0x0173 |
0x01a7 |
0x03a7 |
0x0067 |
|
136 |
0x00f3 |
0x0267 |
0x0167 |
0x0367 |
0x00e7 |
0x02e7 |
0x01e7 |
0x03e7 |
|
144 |
0x01f3 |
0x0017 |
0x0217 |
0x0117 |
0x0317 |
0x0097 |
0x0297 |
0x0197 |
|
152 |
0x0397 |
0x0057 |
0x0257 |
0x0157 |
0x0357 |
0x00d7 |
0x02d7 |
0x01d7 |
|
160 |
0x03d7 |
0x0037 |
0x0237 |
0x0137 |
0x0337 |
0x00b7 |
0x02b7 |
0x01b7 |
|
168 |
0x03b7 |
0x0077 |
0x0277 |
0x07ff |
0x0177 |
0x0377 |
0x00f7 |
0x02f7 |
|
176 |
0x01f7 |
0x03f7 |
0x03ff |
0x000f |
0x020f |
0x010f |
0x030f |
0x008f |
|
184 |
0x028f |
0x018f |
0x038f |
0x004f |
0x024f |
0x014f |
0x034f |
0x00cf |
|
192 |
0x000b |
0x02cf |
0x01cf |
0x03cf |
0x002f |
0x022f |
0x010b |
0x012f |
|
200 |
0x032f |
0x00af |
0x02af |
0x01af |
0x008b |
0x03af |
0x006f |
0x026f |
|
208 |
0x018b |
0x016f |
0x036f |
0x00ef |
0x02ef |
0x01ef |
0x03ef |
0x001f |
|
216 |
0x021f |
0x011f |
0x031f |
0x009f |
0x029f |
0x019f |
0x039f |
0x005f |
|
224 |
0x004b |
0x025f |
0x015f |
0x035f |
0x00df |
0x02df |
0x01df |
0x03df |
|
232 |
0x003f |
0x023f |
0x013f |
0x033f |
0x00bf |
0x02bf |
0x014b |
0x01bf |
|
240 |
0x00ad |
0x00cb |
0x01cb |
0x03bf |
0x002b |
0x007f |
0x027f |
0x017f |
|
248 |
0x012b |
0x037f |
0x00ff |
0x02ff |
0x00ab |
0x01ab |
0x006d |
0x0059 |
|
256 |
0x17ff |
0x0fff |
0x0039 |
0x0079 |
0x01ff |
0x0005 |
0x0045 |
0x0034 |
|
264 |
0x000c |
0x002c |
0x001c |
0x0000 |
0x003c |
0x0002 |
0x0022 |
0x0010 |
|
272 |
0x0012 |
0x0008 |
0x0032 |
0x000a |
0x002a |
0x001a |
0x003a |
0x0006 |
|
280 |
0x0026 |
0x0016 |
0x0036 |
0x000e |
0x002e |
0x001e |
0x003e |
0x0001 |
|
288 |
0x00ed |
0x0018 |
0x0021 |
0x0025 |
0x0065 |
|
|
|
Table 2: Huffman codebook for the 293 Huffman-encoded LiteralOrEosOrCopyOffset codes
For example, it can be determined from the HuffCodeLEC table that the 0th Huffman-encoded LiteralOrEosOrCopyOffset code has a value of 0x0004. Applying the bit-length information from the HuffLengthLEC table, it can be determined that the Huffman code MUST be 6 bits in length. Hence the final code in binary MUST be 000100.
As another example, it can be determined from the HuffCodeLEC table that the 131st Huffman-encoded LiteralOrEosOrCopyOffset code has a value of 0x02a7. Applying the bit-length information from the HuffLengthLEC table, it can be determined that the Huffman code MUST be 10 bits in length. Hence the final code in binary MUST be 1010100111.
The two lookup tables in the following table (CopyOffsetBitsLUT and CopyOffsetBaseLUT) are used during encoding and decoding of the copy-offset for a given copy-tuple to determine the extra bits that will follow the LiteralOrEosOrCopyOffset code.
|
Index |
CopyOffsetBitsLUT |
CopyOffsetBaseLUT |
|---|---|---|
|
0 |
0 |
1 |
|
1 |
0 |
2 |
|
2 |
0 |
3 |
|
3 |
0 |
4 |
|
4 |
1 |
5 |
|
5 |
1 |
7 |
|
6 |
2 |
9 |
|
7 |
2 |
13 |
|
8 |
3 |
17 |
|
9 |
3 |
25 |
|
10 |
4 |
33 |
|
11 |
4 |
49 |
|
12 |
5 |
65 |
|
13 |
5 |
97 |
|
14 |
6 |
129 |
|
15 |
6 |
193 |
|
16 |
7 |
257 |
|
17 |
7 |
385 |
|
18 |
8 |
513 |
|
19 |
8 |
769 |
|
20 |
9 |
1025 |
|
21 |
9 |
1537 |
|
22 |
10 |
2049 |
|
23 |
10 |
3073 |
|
24 |
11 |
4097 |
|
25 |
11 |
6145 |
|
26 |
12 |
8193 |
|
27 |
12 |
12289 |
|
28 |
13 |
16385 |
|
29 |
13 |
24577 |
|
30 |
14 |
32769 |
|
31 |
14 |
49153 |
Table 3: Bit count and base value lookup tables to encode and decode copy-offset values