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