Intel Extensible Firmware Interface - Manual (Page 754)

Extensible Firmware Interface Specification
17-14 12/01/02 Version 1.10
17.3.3.3 Code Generation
In the previous step, the count of each length was obtained. Now, each symbol is going to be
assigned a code. First, the length of the code for each symbol is determined. Naturally, the code
lengths are assigned in such a way that shorter codes are assigned to more frequently appearing
symbols. A CodeLength array is generated with CodeLength[i] = the code length of symbol i.
Given this array, a code is assigned to each symbol using the algorithm described by the pseudo
code below (the resulting codes are stored in array Code such that Code[i] = the code assigned to
symbol i):
INT32 i;
UINT16 Start[18];
Start[1] = 0;
for (i = 1; i <= 16; i++) {
Start[i + 1] = (UINT16)((Start[i] + LengthCount[i]) << 1);
}
for (i = 0; i < NumberOfSymbols; i++) {
Code[i] = Start[CodeLength[i]]++;
}
The code length adjustment process ensures that no code longer than the designated length will
be generated. As long as the decompressor has the CodeLength array at hand, it can regenerate
the codes.