8.8.5.5 Compression Algorithms

The following subsections provide information about decompression algorithms for the RLE and LZSS formats. To see example decompression algorithms, refer to the following functions in the Run-Time Support library:

• RLE: The __TI_decompress_rle() function in the copy_decompress_rle.c file.
• LZSS: The __TI_decompress_lzss() function in the copy_decompress_lzss.c file.

Run Length Encoding (RLE):

The data following the 8-bit index is compressed using run length encoded (RLE) format. ARM uses a simple run length encoding that can be decompressed using the following algorithm. See copy_decompress_rle.c for details.

1. Read the first byte, Delimiter (D).
2. Read the next byte (B).
3. If B != D, copy B to the output buffer and go to step 2.
4. Read the next byte (L).
   1. If L == 0, then length is either a 16-bit or 24-bit value or we’ve reached the end of the data, read the next byte (L).
      1. If L == 0, length is a 24-bit value or the end of the data is reached, read next byte (L).
         1. If L == 0, the end of the data is reached, go to step 7.
         2. Else L <<= 16, read next two bytes into lower 16 bits of L to complete 24-bit value for L.
      2. Else L <<= 8, read next byte into lower 8 bits of L to complete 16-bit value for L.
   2. Else if L > 0 and L < 4, copy D to the output buffer L times. Go to step 2.
   3. Else, length is 8-bit value (L).
5. Read the next byte (C); C is the repeat character.
6. Write C to the output buffer L times; go to step 2.
7. End of processing.

The ARM run-time support library has a routine __TI_decompress_rle24() to decompress data compressed using RLE. The first argument to this function is the address pointing to the byte after the 8-bit index. The second argument is the run address from the C auto initialization record.

NOTE

RLE Decompression Routine

The previous decompression routine, __TI_decompress_rle(), is included in the run-time-support library for decompressing RLE encodings that are generated by older versions of the linker.

Lempel-Ziv-Storer-Szymanski Compression (LZSS):

The data following the 8-bit index is compressed using LZSS compression. The ARM run-time-support library has the routine __TI_decompress_lzss() to decompress the data compressed using LZSS. The first argument to this function is the address pointing to the byte after the 8-bit Index, and the second argument is the run address from the C auto initialization record.

See copy_decompress_lzss.c for details on the LZSS algorithm.