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.

Additional information about compression algorithms can be found in the C28x Embedded Application Binary Interface Application Report (SPRAC71) EABI specification.

Run Length Encoding (RLE):

The data following the 16-bit index is compressed using run length encoded (RLE) format. C2000 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 16 bits, Delimiter (D).
2. Read the next 16 bits (B).
3. If B != D, copy B to the output buffer and go to step 2.
4. Read the next 16 bits (L).
   1. If L == 0, then length is either a 32 bit value or we’ve reached the end of the data, read the next 16 bits (L).
      1. If L == 0, the end of the data is reached. Go to the "end of processing" step.
      2. If L !=0, then L is the most significant 16-bits of the 32-bit run length, L.hi. Read the next 16-bits, which is L.lo. Concatenate L.hi with L.lo to form the 32-bit run length.
   2. Else if L > 0 and L < 4, copy D to the output buffer L times. Go to step 2.
   3. Else, length is 16-bit value (L).
5. Read the next 16 bits (C); C is the repeat character.
6. Write C to the output buffer L times; go to step 2.
7. End of processing.

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

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

The data following the 8-bit index is compressed using LZSS compression. The C2000 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 16 bits after the 16-bit Index, and the second argument is the run address from the C auto initialization record.

The decompression algorithm for LZSS is as follows. See copy_decompress_lzss.c for details on the LZSS algorithm.

1. Read 16 bits, which are the encoding flags (F) marking the start of the next LZSS encoded packet.
2. For each bit (B) in F, starting from the least significant to the most significant bit, do the following:
   1. If (B & 0x1), read the next 16 bits and write it to the output buffer. Then advance to the next bit (B) in F and repeat this step.
   2. Else read the next 16-bits into temp (T), length (L) = (T & 0xf) + 2, and offset (O) = (T >> 4).
      1. If L == 17, read the next 16-bits (L'); then L += L'.
      2. If O == LZSS end of data (LZSS_EOD), we've reached the end of the data, and the algorithm is finished.
      3. At position (P) = output buffer - Offset (O) - 1, read L bytes from position P and write them to the output buffer.
      4. Go to step 2a.