Intel Extensible Firmware Interface - Manual (Page 744)

Extensible Firmware Interface Specification
17-4 12/01/02 Version 1.10
The overall structure of the compressed data is shown in Figure 17-2.
OM13174
Compressed Size
4 Bytes 4 Bytes Terminator
1 Byte
0 Block n Block 1 Block 0 Original Size
Figure 17-2. Compressed Data Structure
Note the following:
• Blocks are of variable lengths.
• Block lengths are counted by bits and not necessarily divisible by 8. Blocks are tightly packed
(there are no padding bits between blocks). Neither the starting position nor ending position of
a Block is necessarily at a byte boundary. However, if the last Block is not terminated at a byte
boundary, there should be some bits of 0 to fill up the remaining bits of the last byte of the
block, before the terminator byte of 0.
• Compressed Size =
Size in bytes of (Block 0 + Block 1 + … + Block N + Filling Bits (if any) + Terminator).
• Original Size is the size in bytes of original data.
• Both Compressed Size and Original Size are “little endian” (starting from the least
significant byte).
17.2.3 Block Structure
A Block is composed of a Block Header and a Block Body, as shown in Figure 17-3. These two
parts are packed tightly (there are no padding bits between them). The lengths in bits of Block
Header and Block Body are not necessarily divisible by eight.
OM13175
Block Header Block Body Block:
Figure 17-3. Block Structure
17.2.3.1 Block Header
The Block Header contains the Huffman encoding information for this block. Since “canonical”
Huffman Coding is being used, a Huffman tree is represented as an array of code lengths in
increasing order of the symbols in the symbol set. Code lengths are limited to be less than or equal
to 16 bits. This requires some extra handling of Huffman codes in the compressor, which is
described in section 17.3, “Compressor Design.”
There are three code length arrays for three different symbol sets in the Block Header: one for the
Extra Set, one for the Char&Len Set, and one for the Position Set.