ModdingWiki - User contributions [en-gb]

LZSS compression

2021-09-07T14:34:45Z

Pixenal: Fix typo

{{Compression Infobox
| Type = Stream
| UnitSize = 1-bit
| Games =
{{Game|J.R.R. Tolkien's Riders of Rohan}}
{{Game|Nomad}}
{{Game|Prehistorik}}
}}

'''LZSS''' (Lempel-Ziv-Storer-Szymanski) is a dictionary compression algorithm first proposed by James A. Storer and Thomas G. Szymanski in 1982. The method is lossless, and builds upon the existing '''LZ77''' technique.

'''LZSS''' makes use of a sliding window just like its predecessor, however differs primarily in its more selective approach to substitution. Where '''LZ77''' simply replaces every string it processes, '''LZSS''' will only substitute a string with a "length-distance" pair if the size of the string, in bits, exceeds a preset minimum, leaving the string's symbols as literals if not. This prevents a pair from ever replacing a string whose size is less than its own, and thus avoids such a case from unnecessarily increasing the size of the final output (a problem which can occur in '''LZ77'''). As alluded to above, '''LZSS''' also does away with the codeword component of '''LZ77''''s "length-distance-codeword" triple, leaving only length and distance. The algorithm also introduces a 1-bit flag which prefixes each element in the code, in order to signify whether the succeeding element is a literal or a "length-distance" pair.

Like '''LZ77''', the length and distance in '''LZSS''''s "length-distance" pair describe the location, within the search buffer, of the string that a particular pair substitutes (with the buffer containing symbols that have already been processed, or decompressed (if decoding)). During the decompression process, the decoder, upon encountering one of these pairs, can, in an informal sense, determine the string to replace said pair with by looking back into the search buffer by the amount described by "distance", and reading forward by the amount specified by "length". The string that is read is the string in which to use. It should also be noted that it is sometimes possible, depending on the implementation, for the string being read to pass into the look ahead buffer, that is to say, it is possible for "length" to be longer than "distance". The process for handling such cases is fairly straightforward however, once the string passes into the look ahead buffer, the decoder would just need to start reading from the symbols that have already been substituted as a part of processing the current pair (kind of like driving the train while placing the tracks).

== Algorithm ==

'''Variables:'''

* <tt>size_length</tt>: Size of length field, in bits
* <tt>size_distance</tt>: Size of distance field, in bits
* <tt>min_len</tt>: Minimum length of a backreference (at least 2 to break even; 3 is better as it represents a savings of 1 byte)
* 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

'''Decoding Procedure:'''

<ol>
<li>
Read one bit as the flag
<ul>
<li>
If it's 1: (or 0 if flags are opposite)
<ol style="list-style-type: lower-alpha;">
<li>Read <tt>size_length</tt> bits, add <tt>min_len</tt> to the value, and use it as the LZSS <tt>length</tt> value</li>
<li>Read <tt>size_distance</tt> bits, add 1 to the value, and use it as the LZSS <tt>distance</tt> value</li>
<li>Look back <tt>distance</tt> bytes in the output data, and copy <tt>length</tt> bytes to the end of the output data</li>
</ol>
</li>
<li>
Otherwise: (the flag is a 0, or 1 if flags are opposite)
<ol style="list-style-type: lower-roman;">
<li>Read 8 bits, and write them as a byte on the end of the output data</li>
</ol>
</li>
</ul>
</li>
<li>If there is more input data, go back to step 1</li>
</ol>

== See also ==

[[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.

== Credits ==

[[User:Malvineous|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!)

LZSS compression

2021-09-07T14:32:20Z

Pixenal: Re-add (after some modification) information regarding the use of "length-distance" pairs

{{Compression Infobox
| Type = Stream
| UnitSize = 1-bit
| Games =
{{Game|J.R.R. Tolkien's Riders of Rohan}}
{{Game|Nomad}}
{{Game|Prehistorik}}
}}

'''LZSS''' (Lempel-Ziv-Storer-Szymanski) is a dictionary compression algorithm first proposed by James A. Storer and Thomas G. Szymanski in 1982. The method is lossless, and builds upon the existing '''LZ77''' technique.

'''LZSS''' makes use of a sliding window just like its predecessor, however differs primarily in its more selective approach to substitution. Where '''LZ77''' simply replaces every string it processes, '''LZSS''' will only substitute a string with a "length-distance" pair if the size of the string, in bits, exceeds a preset minimum, leaving the string's symbols as literals if not. This prevents a pair from ever replacing a string whose size is less than its own, and thus avoids such a case from unnecessarily increasing the size of the final output (a problem which can occur in '''LZ77'''). As alluded to above, '''LZSS''' also does away with the codeword component of '''LZ77''''s "length-distance-codeword" triple, leaving only length and distance. The algorithm also introduces a 1-bit flag which prefixes each element in the code, in order to signify whether the succeeding element is a literal or a "length-distance" pair.

Like '''LZ77''', the length and distance in '''LZSS''''s "length-distance" pair describe the location, within the search buffer, of the string that a particular pair substitutes (with the buffer containing symbols that have already been processed, or decompressed (if decoding)). During the decompression process, the decoder, upon encountering one of these pairs, can, in an informal sense, determine the string to replace said pair with by looking back into the search buffer by the amount described by "distance, and reading forward by the amount specified by "length". The string that is read is the string in which to use. It should also be noted that it is sometimes possible, depending on the implementation, for the string being read to pass into the look ahead buffer, that is to say, it is possible for "length" to be longer than "distance". The process for handling such cases is fairly straightforward however, once the string passes into the look ahead buffer, the decoder would just need to start reading from the symbols that have already been substituted as a part of processing the current pair (kind of like driving the train while placing the tracks).

== Algorithm ==

'''Variables:'''

* <tt>size_length</tt>: Size of length field, in bits
* <tt>size_distance</tt>: Size of distance field, in bits
* <tt>min_len</tt>: Minimum length of a backreference (at least 2 to break even; 3 is better as it represents a savings of 1 byte)
* 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

'''Decoding Procedure:'''

<ol>
<li>
Read one bit as the flag
<ul>
<li>
If it's 1: (or 0 if flags are opposite)
<ol style="list-style-type: lower-alpha;">
<li>Read <tt>size_length</tt> bits, add <tt>min_len</tt> to the value, and use it as the LZSS <tt>length</tt> value</li>
<li>Read <tt>size_distance</tt> bits, add 1 to the value, and use it as the LZSS <tt>distance</tt> value</li>
<li>Look back <tt>distance</tt> bytes in the output data, and copy <tt>length</tt> bytes to the end of the output data</li>
</ol>
</li>
<li>
Otherwise: (the flag is a 0, or 1 if flags are opposite)
<ol style="list-style-type: lower-roman;">
<li>Read 8 bits, and write them as a byte on the end of the output data</li>
</ol>
</li>
</ul>
</li>
<li>If there is more input data, go back to step 1</li>
</ol>

== See also ==

[[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.

== Credits ==

[[User:Malvineous|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!)

LZSS compression

2021-09-07T14:00:39Z

Pixenal: Change high level description to address inaccurate information and qualify "Procedure" with "Decoding"

{{Compression Infobox
| Type = Stream
| UnitSize = 1-bit
| Games =
{{Game|J.R.R. Tolkien's Riders of Rohan}}
{{Game|Nomad}}
{{Game|Prehistorik}}
}}

'''LZSS''' (Lempel-Ziv-Storer-Szymanski) is a dictionary compression algorithm first proposed by James A. Storer and Thomas G. Szymanski in 1982. The method is lossless, and builds upon the existing '''LZ77''' technique.

'''LZSS''' makes use of a sliding window just like its predecessor, however differs primarily in its more selective approach to substitution. Where '''LZ77''' simply replaces every string it processes, '''LZSS''' will only substitute a string with a "length-distance" pair if the size of the string, in bits, exceeds a preset minimum, leaving the string's symbols as literals if not. This prevents a pair from ever replacing a string whose size is less than its own, and thus avoids such a case from unnecessarily increasing the size of the final output (a problem which can occur in '''LZ77'''). As alluded to above, '''LZSS''' also does away with the codeword component of '''LZ77''''s "length-distance-codeword" triple, leaving only length and distance. The algorithm also introduces a 1-bit flag which prefixes each element in the code, in order to signify whether the succeeding element is a literal or a "length-distance" pair.

== Algorithm ==

'''Variables:'''

* <tt>size_length</tt>: Size of length field, in bits
* <tt>size_distance</tt>: Size of distance field, in bits
* <tt>min_len</tt>: Minimum length of a backreference (at least 2 to break even; 3 is better as it represents a savings of 1 byte)
* 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

'''Decoding Procedure:'''

<ol>
<li>
Read one bit as the flag
<ul>
<li>
If it's 1: (or 0 if flags are opposite)
<ol style="list-style-type: lower-alpha;">
<li>Read <tt>size_length</tt> bits, add <tt>min_len</tt> to the value, and use it as the LZSS <tt>length</tt> value</li>
<li>Read <tt>size_distance</tt> bits, add 1 to the value, and use it as the LZSS <tt>distance</tt> value</li>
<li>Look back <tt>distance</tt> bytes in the output data, and copy <tt>length</tt> bytes to the end of the output data</li>
</ol>
</li>
<li>
Otherwise: (the flag is a 0, or 1 if flags are opposite)
<ol style="list-style-type: lower-roman;">
<li>Read 8 bits, and write them as a byte on the end of the output data</li>
</ol>
</li>
</ul>
</li>
<li>If there is more input data, go back to step 1</li>
</ol>

== See also ==

[[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.

== Credits ==

[[User:Malvineous|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!)