Intel Extensible Firmware Interface - Manual (Page 743)

Protocols — Compression Algorithm Specification
Version 1.10 12/01/02 17-3
17.2 Data Format
This section describes in detail the format of the compressed data produced by the compressor. The
compressed data serves as input to the decompressor and can be fully extracted to the original
source data.
17.2.1 Bit Order
In computer data representation, a byte is the minimum unit and there is no differentiation in the
order of bits within a byte. However, the compressed data is a sequence of bits rather than a
sequence of bytes and as a result the order of bits in a byte needs to be defined. In a compressed
data stream, the higher bits are defined to precede the lower bits in a byte. Figure 17-1 illustrates a
compressed data sequence written as bytes from left to right. For each byte, the bits are written in
an order with bit 7 (the highest bit) at the left and bit 0 (the lowest bit) at the right. Concatenating
the bytes from left to right forms a bit sequence.
OM13173
Bit 7 Bit 6 Bit 0 Bit 7 Bit 6 Bit 0 Bit 7 Bit 6 Bit 0
Byte 0 Byte 1 Byte N
Overall Bit Sequence of Compressed Data
Figure 17-1. Bit Sequence of Compressed Data
The bits of the compressed data are actually formed by a sequence of data units. These data units
have variable bit lengths. The bits of each data unit are arranged so that the higher bit of the data
unit precedes the lower bit of the data unit.
17.2.2 Overall Structure
The compressed data begins with two 32-bit numerical fields: the compressed size and the original
size. The compressed data following these two fields is composed of one or more Blocks. Each
Block is a unit for Huffman Coding with a coding scheme independent of the other Blocks. Each
Block is composed of a Block Header containing the Huffman code trees for this Block and a Block
Body with the data encoded using the coding scheme defined by the Huffman trees. The
compressed data is terminated by an additional byte of zero.