LZSS - Revision history

imported>Ikskoks at 23:14, 24 July 2021

2021-07-24T23:14:30Z

← Older revision	Revision as of 23:14, 24 July 2021
(No difference)

imported>Ikskoks at 23:14, 24 July 2021

2021-07-24T23:14:30Z

← Older revision		Revision as of 23:14, 24 July 2021
Line 78:		Line 78:
	== Games ==		== Games ==

	* [[Star Trek: 25th Anniversary]]		* Star Trek: 25th Anniversary
	* [[The 7th Guest]]		* The 7th Guest


			<br><br>
			[[Category:Articles]]

92.50.144.206 at 06:03, 13 September 2011

2011-09-13T06:03:03Z

← Older revision	Revision as of 06:03, 13 September 2011
(No difference)

92.50.144.206 at 06:03, 13 September 2011

2011-09-13T06:03:03Z

← Older revision		Revision as of 06:03, 13 September 2011
Line 50:		Line 50:
	Exit;		Exit;
	Length := OfsLen and LengthMask + Threshold		Length := OfsLen and LengthMask + Threshold
	Offset := (BufPos - (OfsLen ~~<b>~~shr~~</b>~~ LengthBits)) and (N - 1)		Offset := (BufPos - (OfsLen shr LengthBits)) and (N - 1)
	{ copy Length bytes from Buffer[Offset] onwards while increasing BufPos }		{ copy Length bytes from Buffer[Offset] onwards while increasing BufPos }
	end		end

92.50.144.206 at 06:02, 13 September 2011

2011-09-13T06:02:00Z

← Older revision	Revision as of 06:02, 13 September 2011
(No difference)

92.50.144.206 at 06:02, 13 September 2011

2011-09-13T06:02:00Z

← Older revision		Revision as of 06:02, 13 September 2011
Line 1:		Line 1:
	== General Description ==		== General Description ==

	The LZSS (Lempel-Ziv-Storer-Szymanski) algorithm is a compression scheme which tries to use its knowledge of past ("already seen") data to compress the current data.~~<br>~~		The LZSS (Lempel-Ziv-Storer-Szymanski) algorithm is a compression scheme which tries to use its knowledge of past ("already seen") data to compress the current data.
	To achieve this, the compressor holds a fixed-length buffer in memory which contains the last read bytes. The goal is to find a match for the current data in the buffer in order to store just a buffer reference instead of the actual data. During decompression, the algorithm reconstructs this buffer from the compressed data.~~<br><br>~~
			To achieve this, the compressor holds a fixed-length buffer in memory which contains the last read bytes. The goal is to find a match for the current data in the buffer in order to store just a buffer reference instead of the actual data. During decompression, the algorithm reconstructs this buffer from the compressed data.

	This particular algorithm was often used to compress data in older games since decompression is quite easy to achieve and fast to do in memory.		This particular algorithm was often used to compress data in older games since decompression is quite easy to achieve and fast to do in memory.

Line 35:		Line 37:
	To decompress data, the above process has to be reversed. Obviously, the parameters mentioned above have to be known to successfully restore the original data. Often enough, a good guess by looking at the compressed data (especially areas with patterns) will work here. As soon as the parameters are known, the decompression process is fairly simple. Assuming that everything is set up correctly, the pseudo code below will illustrate a rough example of how such a routine could work:		To decompress data, the above process has to be reversed. Obviously, the parameters mentioned above have to be known to successfully restore the original data. Often enough, a good guess by looking at the compressed data (especially areas with patterns) will work here. As soon as the parameters are known, the decompression process is fairly simple. Assuming that everything is set up correctly, the pseudo code below will illustrate a rough example of how such a routine could work:

	<br>		<syntaxhighlight lang="pascal">
	~~<tt>~~		while InputPos < InputSize do
	~~<b>~~while~~</b>~~ InputPos < InputSize ~~<b>~~do~~</b><br>~~		begin
	~~<b>~~begin~~</b><br>~~		FlagByte := Input[InputPos++]
	: FlagByte := Input[InputPos++]~~<br>~~		for i := 1 to 8 do
	~~: <b>~~for~~</b>~~ i := 1 ~~<b>~~to~~</b>~~ 8 ~~<b>~~do~~</b><br>~~		begin
	~~: <b>~~begin~~</b><br>~~		if (FlagByte and 1) = 0 then
	~~:: <b>~~if~~</b>~~ (FlagByte ~~<b>~~and~~</b>~~ 1) = 0 ~~<b>~~then~~</b><br>~~		begin
	~~:: <b>~~begin~~</b><br>~~		OfsLen := Input[InputPos] + Input[InputPos + 1] shl 8
	~~:::~~ OfsLen := Input[InputPos] + Input[InputPos + 1] ~~<b>~~shl~~</b>~~ 8~~<br>~~		InputPos += 2
	~~:::~~ InputPos += 2~~<br>~~		if OfsLen = 0 then
	~~::: <b>~~if~~</b>~~ OfsLen = 0 ~~<b>~~then~~</b><br>~~		Exit;
	~~::::~~ Exit;~~<br>~~		Length := OfsLen and LengthMask + Threshold
	~~:::~~ Length := OfsLen ~~<b>~~and~~</b>~~ LengthMask + Threshold~~<br>~~		Offset := (BufPos - (OfsLen <b>shr</b> LengthBits)) and (N - 1)
	~~:::~~ Offset := (BufPos - (OfsLen <b>shr</b> LengthBits)) ~~<b>~~and~~</b>~~ (N - 1)~~<br>~~		{ copy Length bytes from Buffer[Offset] onwards while increasing BufPos }
	~~::: ''~~copy Length bytes from Buffer[Offset] onwards~~''<br>~~		end
	~~::: ''~~while increasing BufPos''		else
	~~:: <b>~~end~~</b><br>~~		begin
	~~:: <b>~~else~~</b><br>~~		{ copy 1 byte from Input[InputPos] }
	~~:: <b>~~begin~~</b><br>~~		InputPos += 1
	~~::: ''~~copy 1 byte from Input[InputPos]~~''<br>~~		end
	~~:::~~ InputPos += 1~~<br>~~		FlagByte := FlagByte shr 1
	~~:: <b>~~end~~</b><br>~~		end
	:: FlagByte := FlagByte ~~<b>~~shr~~</b>~~ 1~~<br>~~		end
	~~: <b>~~end~~</b><br>~~		</syntaxhighlight>
	~~<b>~~end</~~b><br~~>
	~~</tt>~~
	~~<br>~~
	Note the following:		Note the following:
	* <tt>LengthBits </tt>describes the number of bits needed to describe the<tt> F </tt>parameter. The above code assumes that the length of the buffer reference is saved in the lower bits of the word. This does not have to be the case.<tt> LengthMask </tt> is derived from this via<br><tt>(1 <b>shl</b> LengthBits) - 1</tt>.		* <tt>LengthBits </tt>describes the number of bits needed to describe the<tt> F </tt>parameter. The above code assumes that the length of the buffer reference is saved in the lower bits of the word. This does not have to be the case.<tt> LengthMask </tt> is derived from this via<br><tt>(1 <b>shl</b> LengthBits) - 1</tt>.
Line 77:		Line 78:
	== Games ==		== Games ==

	* Star Trek: 25th Anniversary		* [[Star Trek: 25th Anniversary]]
	* The 7th Guest		* [[The 7th Guest]]

imported>DenizOezmen: fix in flag handling

2007-01-09T15:41:03Z

fix in flag handling

← Older revision	Revision as of 15:41, 9 January 2007
(No difference)

imported>DenizOezmen: fix in flag handling

2007-01-09T15:41:03Z

fix in flag handling

← Older revision		Revision as of 15:41, 9 January 2007
Line 42:		Line 42:
	: <b>for</b> i := 1 <b>to</b> 8 <b>do</b><br>		: <b>for</b> i := 1 <b>to</b> 8 <b>do</b><br>
	: <b>begin</b><br>		: <b>begin</b><br>
	:: <b>if</b> FlagByte <b>and</b> 1 <b>then</b><br>		:: <b>if</b> (FlagByte <b>and</b> 1) = 0 <b>then</b><br>
	:: <b>begin</b><br>		:: <b>begin</b><br>
	::: OfsLen := Input[InputPos] + Input[InputPos + 1] <b>shl</b> 8<br>		::: OfsLen := Input[InputPos] + Input[InputPos + 1] <b>shl</b> 8<br>
Line 69:		Line 69:
	* Always mirror any writes to the output into the history buffer.		* Always mirror any writes to the output into the history buffer.
	* In most cases copying the data out of the history buffer will be implemented byte-wise. While you could also copy the whole sequence at once, some implementations you might come across "abuse" cross-over situations between the buffer read and write positions during lookup and actually expect a byte-wise copy! (This situation might arise if you are supposed to read a certain number of bytes out of the buffer, but will cross the initial write position while doing so, thus effectively repeating the pattern you have already read.)		* In most cases copying the data out of the history buffer will be implemented byte-wise. While you could also copy the whole sequence at once, some implementations you might come across "abuse" cross-over situations between the buffer read and write positions during lookup and actually expect a byte-wise copy! (This situation might arise if you are supposed to read a certain number of bytes out of the buffer, but will cross the initial write position while doing so, thus effectively repeating the pattern you have already read.)


	== Further Information ==		== Further Information ==

imported>WATTO: /* Games */

2005-12-20T11:26:32Z

Games

← Older revision	Revision as of 11:26, 20 December 2005
(No difference)

imported>WATTO: /* Games */

2005-12-20T11:26:32Z

Games

← Older revision		Revision as of 11:26, 20 December 2005
Line 78:		Line 78:
	== Games ==		== Games ==

	* ~~[[Star Trek - 25th Anniversary \|~~ Star Trek: 25th Anniversary]]		* Star Trek: 25th Anniversary
	* [[The 7th Guest]]		* The 7th Guest