417
edits
Difference between revisions of "Cine/Specifications"
Added info about the Delphine's compression format's parsing.
(Revised compression format part's introduction a bit.) |
(Added info about the Delphine's compression format's parsing.) |
||
| Line 114: | Line 114: | ||
The compression algorithm used by all Delphine's adventure games uses | The compression algorithm used by all Delphine's adventure games uses | ||
sliding window compression (Quite like [http://en.wikipedia.org/wiki/LZ77 LZ77]) | sliding window compression (Quite like [http://en.wikipedia.org/wiki/LZ77 LZ77]) | ||
combined with a fixed [http://en.wikipedia.org/wiki/Entropy_coding entropy coding] scheme (Not of any type I could recognize). | combined with a fixed non-adaptive [http://en.wikipedia.org/wiki/Entropy_coding entropy coding] scheme (Not of any type I could recognize). | ||
The compressed data is in big endian 32-bit chunks, working backwards from the buffer's end. | The compressed data is in big endian 32-bit chunks, working backwards from the buffer's end. | ||
| Line 134: | Line 134: | ||
-------- ------------------------------------------------------------------------ | -------- ------------------------------------------------------------------------ | ||
</pre> | </pre> | ||
===Bit sequences in the compressed stream=== | |||
First bit of a command always tells how many bits the whole command takes. | |||
If the first bit of a command is zero, then the whole command (Including the | |||
first bit) takes two bits total, otherwise it takes three bits (i.e. the first bit is one). | |||
There are two possible types of commands: | |||
* unpackRawBytes(N) | |||
** Copies N bytes straight from the source stream and writes them to the destination | |||
* copyRelocatedBytes(OFFSET, N) | |||
** Copies N bytes from position OFFSET in the sliding window (i.e. from the unpacked buffer) | |||
Commands may have predefined values or a restricted value range for some of their parameters. | |||
Here are all the possible commands (Including their first bit that tells the command's length): | |||
<pre> | |||
Bits => Action: | |||
0 0 => unpackRawBytes(3 bits + 1) i.e. unpackRawBytes(1..9) | |||
1 1 1 => unpackRawBytes(8 bits + 9) i.e. unpackRawBytes(9..264) | |||
0 1 => copyRelocatedBytes(8 bits, 2) i.e. copyRelocatedBytes(0..255, 2) | |||
1 0 0 => copyRelocatedBytes(9 bits, 3) i.e. copyRelocatedBytes(0..511, 3) | |||
1 0 1 => copyRelocatedBytes(10 bits, 4) i.e. copyRelocatedBytes(0..1023, 4) | |||
1 1 0 => copyRelocatedBytes(12 bits, 8 bits + 1) i.e. copyRelocatedBytes(0..4095, 1..256) | |||
</pre> | |||
Some examples of parsing the commands: | |||
* We read one bit from the stream, it's 0. Okay, so the command has length of two bits. We read the second bit, it's 0, so the command is unpackRawBytes(3 bits + 1). That means we read 3 bits from the source stream, let's call that number X. Then we call unpackRawBytes(X + 1). | |||
* We read one bit from the stream, it's 1. So the command has length of three bits. We read two more bits, they're 1 and 0 (i.e. 10b). So we've got command copyRelocatedBytes(12 bits, 8 bits + 1). Let's first read 12 bits from the source stream and call that OFFSET. Then let's read 8 bits from the source stream and call that X. Then we'll call copyRelocatedBytes(OFFSET, X + 1). | |||
* We read one bit from the stream, it's 1. So the command has length of three bits. We read two more bits, they're 1 and 1 (i.e. 11b). So we've got command unpackedRawBytes(8 bits + 9). Let's then read 8 bits from the source stream and call that X. Then we'll call unpackRawBytes(X + 9). | |||
* We read one bit from the stream, it's 1. So the command has length of three bits. We read two more bits, they're 0 and 0 (i.e. 00b). So we've got command copyRelocatedBytes(9 bits, 3). Let's read 9 bits from the source stream and call that OFFSET. Then we'll call copyRelocatedBytes(OFFSET, 3). | |||
===End of decompression=== | |||
The unpacking ends when we've written <i>unpacked length</i> bytes into the destination buffer. | |||
If at that point the [http://en.wikipedia.org/wiki/XOR exclusive-or] of all the read source stream | |||
chunks together equals the <i>error code</i> from the source stream's header (i.e. their exclusive-or is zero), | |||
that means the packed data is probably intact (Only probably because the exclusive-or of 32-bit chunks isn't a very good | |||
error detection method, it lets errors through relatively easily if compared to other more robust | |||
error detection methods like [http://en.wikipedia.org/wiki/SHA-1 SHA-1] or even [http://en.wikipedia.org/wiki/Cyclic_redundancy_check CRC]). | |||