未知的解压缩算法

#1 楼

在下载ChessBase Reader并使用ProcMon进行一些查找以找到读取存档并写入数据文件的功能之后，我将整个内容加载到IDA中进行分析。数据是霍夫曼编码的。

每个数据块具有以下结构。请注意，霍夫曼压缩仅适用于位，而不适用于字节，因此下表中的每个大小也以位为单位。例如，块长度为16位或2个字节。

+----------------------------------------------+
|                                              |
|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)   |
|                                              |
+----------------------------------------------+

假设在此方案中将单词“ foobar”编码，则可能导致组成字符的位值）：

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

这将导致单词foobar被编码为
100 0 0 101 110 111。长度为6个字节，即16位0000 0000 0000 0110。

格式化为上表的foobar的位数组将读取为
该实现从代码表构建一个二叉树。当它读取数据时，它从树的根开始。每一位根据下一位的值在树上向左或向右移动。当到达叶子时，正在输出相应的字节。一直重复直到达到输出流的长度为止。

二进制文件中的相关函数如下：读取16位的长度；然后在解码器类中将编码表读入偏移量为BECAA0（位）和080A（位长）的两个数组中。此后，调用0E10解码数据字节。在函数的结尾，偏移量为BEC930的单词具有这些位。BEBF30：调用1014来构建树，然后从输入流中读取剩余的位。每走一棵树；找到叶子时发出一个字节。最后，调用BEBAD0销毁树。

080A：通过删除左右子节点（节点本身）来递归删除节点。

我不这样做如果您想读取文件，则认为调试编写器会更容易；压缩具有大量的逻辑和数据结构，并且知道“一种方式”的工作方式并不一定会对另一种方式有所帮助。幸运的是，在这种情况下，它是一种众所周知的算法，但是如果该算法未知，则仅知道如何解压缩就很难有效地进行压缩。