LZSS compression is an enhancement to LZ78 compression which uses a sliding window over the output data rather than a dictionary.
It works by embedding certain codes in the data called "length-distance pairs", as the code contains both a length value and a distance value. When one of these codes is encountered, the decompressor looks back at the previously decompressed data and copies part of it onto the end of itself, with the amount and location of the data copied specified by the length and distance pair.
- size_length: Size of length field, in bits
- size_distance: Size of distance field, in bits
- Whether the flag bit is 0 for normal byte, 1 for length-distance pair, or the opposite
- Whether the length field comes before distance, or distance before length
Read one bit as the flag
If it's 1: (or 0 if flags are opposite)
- Read size_length bits, add 2 to the value, and use it as the LZSS length value
- Read size_distance bits, add 1 to the value, and use it as the LZSS distance value
- Look back distance bytes in the output data, and copy length bytes to the end of the output data
Otherwise: (the flag is a 0, or 1 if flags are opposite)
- Read 8 bits, and write them as a byte on the end of the output data
- If it's 1: (or 0 if flags are opposite)
- If there is more input data, go back to step 2
SkyRoads uses a variant of LZSS where the variables can be different for each file, and are stored at the start of the compressed data, as well as allowing two types of length-distance codes in the same file.
Malvineous discovered this compression algorithm was used by Prehistorik. If you find this information helpful in a project you're working on, please give credit where credit is due. (A link back to this wiki would be nice too!)