Intel Extensible Firmware Interface - Manual (Page 755)

Protocols — Compression Algorithm Specification
Version 1.10 12/01/02 17-15
17.4 Decompressor Design
The decompressor takes the compressed data as input and produces the original source data. The
main tasks for the decompressor are decoding Huffman codes and restoring Pointers to the strings
to which they point.
The following pseudo code describes the algorithm used in the design of a decompressor. The
source code that illustrates an implementation of this design is listed in Appendix I.
WHILE not end of data DO
IF at block boundary THEN
Read in the Extra Set Code Length Array;
Generate the Huffman code mapping table for the Extra Set;
Read in and decode the Char&Len Set Code Length Array;
Generate the Huffman code mapping table for the Char&Len Set;
Read in the Position Set Code Length Array;
Generate the Huffman code mapping table for the Position Set;
ENDIF
Get next code;
Look the code up in the Char&Len Set code mapping table.
Store the result as C;
IF C < 256 (it represents an Original Character) THEN
Output this character;
ELSE (it represents a String Length)
Transform C to be the actual String Length value;
Get next code and look it up in the Position Set code mapping table, and
with some additional transformation, store the result as P;
Output C characters starting from the position “Current Position – P”;
ENDIF
ENDWHILE