Page 381 - Programming Microcontrollers in C

366 Chapter 7 Advanced Topics

Recall in Chapter 5 the decode scheme involved intermixing jump
distances in with the decoded characters in a table. There, the decode
operation started at the zero entry in the table. The code being decoded
was examined a bit at a time. If the code bit was zero, the table index
was incremented by one. If the code bit was one, the value in that
table location would be added to the table index. Whenever the table
index fell to a location that contained a character, that character would
be output and the index would be returned to the value zero.
That approach is fine for relatively small alphabets, as used in
Chapter 5. Here, we are using the full alphabet, which makes the
creation of the table above extremely complicated. Another approach
was used this time. We still have a table that contains jump instructions
intermixed with characters to be output. The characters to be output
are each ORed with the hex value 0x80. The printable characters
here are all identified with the least significant 7 bits of the character.
Therefore, a test for a character is to determine if the value found in
the table has a value when ANDed with 0x80.
Each numeric entry in the node table is broken into two nibbles.
The left 4 bits correspond to the jump when a code 0 is found and the
right 4 bits correspond to the jump when a code 1 is found. In other
words, the decode operation starts at the beginning of the node table.
If the first bit of the encoded data is a 0, the value found in the most
significant 4 bits of the data is added to the node table index and the
decoding is continued from that point in the node table. If the encoded
data is a 1 the contents of the least significant 4 bits is added to the
node table index. Whenever the node table index is changed, the
value of that location is tested to see if the most significant bit is
turned on. If so, that bit is turned off and the result is saved in output
array. Otherwise, the process is repeated from that location until an
output character is found. At that time, the node table index is reset
to zero and the process repeated until a new line character is detected.
Then the null character is put on the end of the output data and control
is returned to the calling program.
One little problem with this approach: The number that contains
the jump data can never have its most significant bit turned on.
Therefore, the maximum jump when the encoded bit is 0 is seven.
This restriction did not cause any difficulty when writing this tree. In
fact, most of the time the jump caused by a 0 bit was 1 or 2. This