Difference between revisions of "Cine/Specifications"

Jump to navigation Jump to search
3,276 bytes added ,  16:40, 16 June 2008
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]).
417

edits

Navigation menu