Intel Extensible Firmware Interface - Manual (Page 748)

Extensible Firmware Interface Specification
17-8 12/01/02 Version 1.10
17.3 Compressor Design
The compressor takes the source data as input and produces a compressed image. This section
describes the design used in one possible implementation of a compressor that follows the EFI 1.10
Compression Algorithm. The source code that illustrates an implementation of this specific design
is listed in Appendix H.
17.3.1 Overall Process
The compressor scans the source data from the beginning, character by character. As the scanning
proceeds, the compressor generates Original Characters or Pointers and outputs the compressed
data packed in a series of Blocks representing individual Huffman coding units.
The compressor maintains a String Info Log containing data that facilitates string comparison. Old
data items are deleted and new data items are inserted regularly.
The compressor does not output a Pointer immediately after it sees a matching string for the current
position. Instead, it delays its decision until it gets the matching string for the next position. The
compressor has two criteria at hand: one is that the former match length should be no shorter than
three characters; the other is that the former match length should be no shorter than the latter match
length. Only when these two criteria are met does the compressor output a Pointer to the former
matching string.
The overall process of compression can be described by following pseudo code:
Set the Current Position at the beginning of the source data;
Delete the outdated string info from the String Info Log;
Search the String Info Log for matching string;
Add the string info of the current position into the String Info Log;
WHILE
not end of source data DO
Remember the last match;
Advance the Current Position by 1;
Delete the outdated String Info from the String Info Log;
Search the String Info Log for matching string;
Add the string info of the Current Position into the String Info Log;
IF the last match is shorter than 3 characters or this match is longer than
the last match THEN
Call Output()
*
to output the character at the previous position as an
Original Character;
ELSE
Call Output() * to output a Pointer to the last matching string;
WHILE (--last match length) > 0 DO
Advance the Current Position by 1;
Delete the outdated piece of string info from the String Info Log;
Add the string info of the current position into the String Info Log;
ENDWHILE
ENDIF
ENDWHILE