Changes

=== LZS Compressed archive for PSX by [[User:Ficedula|Ficedula]] ===

==== Format ====

==== LZS compression ====

FF7 uses LZS compression on some of their files - more properly, a slightly modified version of LZSS compression as devised by Professor Haruhiko Okumura. LZS data works on a control byte scheme. So each block in the file begins with a single byte indicating how much of the block is uncompressed ('literal data'), and how much is compressed ('references'). You read the byte right-to-left, with 1=literal, 0=reference.

Literal data means just that: read one byte in from the source (compressed) data, and write it straight to the output.

References take up two bytes, and are essentially a pointer to a piece of data that's been written out (i.e. is part of the data you've already decompressed). LZSS uses a 4K buffer, so it can only reference data in the last 4K of data.

==== Reference format ====

A reference takes up two bytes, and has two pieces of information in it: offset (where to find the data, or which piece of data is going to be repeated), and length (how long the piece of data is going to be). The two reference bytes look like this:

Here, 'tail' is your current output position (eg. 10,000), 'raw_offset' is the 12-bit data value you've retrieved from the compressed reference, and 'real_offset' is the position in your output buffer you can begin reading from. This is a bit complex because it's not exactly the way LZSS traditionally does (de)compression; it uses a 4K circular buffer; if you do that, the offset is more or less usable directly.

==== Example ====

If we're at position 1000 in our output, and we need to read in a new control byte because we've finished with the last one. The next data to look it is:

<nowiki>= 1000 - ((1000 - 18 - 339) and $FFF) </nowiki>

The 339 is just $153 in decimal.The (and $FFF) is a quick way to do modulus 4096.

<nowiki>= 1000 - (643 and 0xFFF)

==== Complications ====

First, if you end up with an negative offset, i.e. reading data from 'before the beginning of the file', write out nulls (zero bytes). That's because the compression buffer is, by default, initialized to zeros; so it's possible, if the start of the file contains a run of zeros, that the file may reference a block you haven't written. For example, if you're at position 50 in your output, it's possible you may get an offset indicating to go back 60 bytes to offset -10. If you have to read 5 bytes from there, you just write out 5 nulls. However, you could have to read 15 bytes from there. In that case, you write out 10 nulls (the part of the data 'before' the file start), then the 5 bytes from the beginning of the file.

Secondly, you can have a repeated run. This is almost the opposite problem: when you go off the end of your output. Say you're at offset 100 in your output, and you have to go to offset 95 to read in a reference. This is okay, but if the reference length is >5, you loop the output. So if you had to write out 15 bytes, you'd write out the five bytes that were available, then write them out again, then again, to make up the 15 bytes you needed.