6

I work on the reverse engineering of the ChessBase archive (.cbv).

I found the general structure of the file and can already decompress some files.

You can see my current work here.

However, some .cbv files that are bigger seems to use a second compression algorithm.

I was able to find the first compression algorithm by debugging the ChessBase Reader 2013 software, but I cannot make sense of the second compression algorithm.

I tried some tools like signsrch to find out what algorithm was used without any luck: it seems to be a custom algorithm.

Here is a file that I am able to partly decompress with my tool (my tool will print What to do? when it detects that the unknown compression algorith was used).

Do you have any idea of what compression algorithm is used?

If not, do you have any way of finding it by looking at the compressed file?

I am able to create archives so I can have files that are both compressed and not: I wonder if there is any way to find a compression pattern in such a situation.

7

After downloading ChessBase Reader and playing with ProcMon a bit to find the function that reads the archive and writes the data file, i loaded up the whole thing in IDA to analyze it. The data is Huffman-coded.

Each data block has the following structure. Note that Huffman compression works with bits, not bytes, so each size in the following table is in bits as well. The block length is 16 bits, or 2 bytes, for example.

+----------------------------------------------+
|                                              |
|16 bits - uncompressed block length (len)     |
|                                              |
+-----------+----------------------------------+
|           |                                  |
|Repeat     |  4 bits - length of entry (n)    |
|256        |                                  |
|times      +----------------------------------+
|           |                                  |
|one entry  |  n bits - tree left/right        |
|per byte   |  information for this byte       |
|(0-255)    |                                  |
|           |                                  |
+-----------+----------------------------------+
|                                              |
| Huffman encoded bit sequences. The number of |
| bits isn't stored anywhere, but the number   |
| of sequences, which is equal to the number   |
| of output bytes, is the block length (len)   |
|                                              |
+----------------------------------------------+

Assuming the word "foobar" was coded in this scheme, this would possibly result in (i made up the bit values for the characters):

+----------------+
|Huffman code for|
|character   is  |
+--------+-------+
|        |       |
| o      |   0   |
| f      |   100 |
| b      |   101 |
| a      |   110 |
| r      |   111 |
|        |       |
+--------+-------+

This would result in the word foobar being coded as 100 0 0 101 110 111. The length is 6 bytes, or 0000 0000 0000 0110 in 16 bits.

The bitarray for foobar, formatted to the above table, would read

0000 0000 0000 0110                      (16 bit output length)
.....    array index   0 for byte '\0'
.....    array index   1 for byte '\1'
.....
0011 110 array index  97 for byte 'a'    (3 bits)
0011 101 array index  98 for byte 'b'    (3 bits)
.....
0011 100 array index 102 for byte 'f'    (3 bits)
.....
0001 0   array index 111 for byte 'o'    (1 bit)
.....
0011 101 array index 114 for byte 'r'    (3 bits)
.....                                    remaining bit combos - 255

100 0 0 101 110 111                      foobar text

The implementation builds a binary tree from the code table. When it reads the data, it starts at the root of the tree; each bit moves down the tree, to the left or right, depending on the next bit value. When a leaf is reached, the corresponding byte is being output. This repeats until the length of the output stream is reached.

The related functions from the binary are these:

BECAA0: decodes the archive data. Reads 16 bits for the length; then reads the encoding table into two arrays at offsets 080A (bits) and 0E10 (bit lengths) within the decoder class. After this, call BEC930 to decode the data bytes.

BEBF30: One parameter (number of bits), gets this many bits from the input array. At the end of the function, the word at offset 1014 has these bits.

BEBAD0: Builds the tree from the arrays at 080A and 0E10

BEC930: Calls BEBAD0 to build the tree, then reads the remaining bits from the input stream. Walks the tree for each bit; emits a byte when a leaf is found. At the end, calls BEBA90 to destroy the tree.

BEBA90: Recursively delete a node by deleting the left and right children, the the node itself.

I don't think debugging the writer would be easier if you want to read the files; compression has a lot of logic and data structures, and knowing how 'one way' works doesn't neccesarily help you with the other way round. In this case, luckily, its a well known algorithm, but if the algorithm is unknown it can be quite hard to compress effectively if you just know how to decompress.

  • database encryption is certainly an option. See chesscentral.com/basic_chess_database_a/300.htm so it's possible that's what you're looking at. – broadway Mar 30 '15 at 16:28
  • @broadway Thank you for pointing this out. Howeverm in the meantime, i've massaged IDA a bit more; i'm quite sure this is a huffman decompression algorithm, although i don't have everything worked out yet. – Guntram Blohm supports Monica Mar 30 '15 at 17:02
  • Looking at the last few kilobytes, you can see 'normal text' fragments interspersed with binary codes. Definitely a Huffman variant. – usr2564301 Mar 30 '15 at 17:48
  • Thanks for your answer: I'll look at this. @Jongware: I already know the compression algorithm used when we see normal text fragments (see my tool on github). My issue is when there is no text fragments. By the way, would it be easier to figure out the algorithm by debugging the application that creates such archives (ChessBase)? – antoyo Mar 30 '15 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.