The compression / decompression routines were developed as a general purpose file compression tool that has the ability to perform random reads from a compressed file without full decompression. To satisfy this, a block compression / decompression technique was implemented.
KKFChess compresses data in two passes - the first pass is an ordinary LZW compressor with 16-bit codes (it is easier to implement and debug than a 12-bit code); the second a dedicated compressor that works on the high order byte of the 16-bit LZW codes.
The second pass works on the LZW compressed data from the first pass. First the low order bytes are collected and de-interleaved to form a set of data, then the high order bytes are compressed with a simple delta instruction compressor and appended to previously created block.
This compressor works best with data that have small differences between elements. It scans the data serially and outputs a stream of 2-bit instructions based on the differences between two "adjacent" data items. The two 2-bit instructions are:
00 Output last value
01 Increment last value by 1
10 Decrement last value by 1
11 End of instruction stream
The initial "last" value is always 0. Below is an example of compressing the data stream of 1, 2, 1, 0, -1, 2, 4, 4, 3:
| 1 | 2 | 1 | 0 | -1 | 2 | 4 | 4 | 3 | 9*8 = 72 bits |
| 01 00 | 01 01 00 | 10 00 | 10 00 | 10 00 | 01 01 01 00 | 01 01 00 | 00 | 10 00 11 | 4+6+4+4+4+8+6+2+6 = 44 bits |
As seen above, compression occurs when the difference between two elements is less than 3. Since the high byte output of the 16-bit LZW compressor changes very little (with small blocking size), this method of compression gives acceptable results. The compressed data block after two pass now looks like:
| Low order bytes of LZW codes | Delta compressed high order bytes of LZW codes |
From V2.6.0 onwards, KKFChess decodes two delta instructions (4-bits) at a time and is faster than previous versions that only decodes 2-bits at a time. I have no plan to implement a 4 instructions at a time decoder.
If enabled, KKFChess will create a fully indexed compressed file. This file differs from an non-indexed one by the appearance of an indexing block at the end of the compressed data. Random access to a non-indexed file requires the serial reading of each compressed block's header to fine the start of the next block until the correct data block is found. With indexing, a read is made to the indexing block to locate the start position of the compressed block. This saves time by performing less reads. However, an indexed file can be much larger than a non-indexed one, especially when the blocking size is small and the source file is large.
An indexed compressed file looks like:
| File header | Compressed block | Compressed block | Compressed block | Compressed block | ... | Last compressed block | Indexing block |
The LZW compression works best on data with repetitions and patterns. If such features are lacking, the compressed file may be larger then the uncompressed one. Since a block compression method is used, the compression will not be as good as one that is done over the whole source file.
One poor candidate for LZW compression is the indexing file for an opening book. It holds unique 64-bit key values (sorted) for each position hence has little byte-to-byte pattern.