这是什么编码/压缩算法？

Question

我试图逆向工程一个二进制文件格式，但它没有魔术字节，也没有具体的扩展名。我只能影响文件的一个方面：短字符串。通过尝试不同的字符串，我能够弄清楚数据如何存储在文件中。看来整个文件使用某种简单的编码。我希望找到确切的编码可以让我缩小搜索文件格式的范围。我知道该文件是由用C++编写的Windows程序生成的。

现在，经过多次反复试验，我发现文件的某些部分编码为运行。每次运行都从一个字节开始，指出将要检索的字节数和检索数据的位置。

• 000ddddd（1字节）
  从编码数据中取下列（ddddd）+1个字节。
• 111····· ···ddddd ···bbbbb（3字节）
  返回（bbbbb）解码后的数据+1个字节，并从中取出下一个（ddddd）+9个字节。
• ddd····· ··bbbbbb（2字节）
  返回（bbbbbb）解码数据中的+1个字节，并从中取出下一个（ddd）+2个字节。

下面是一个例子：

这是文件的开头，在它编码的UTF-16字符串abracadabra：

.  . . a . b . r  . . c  . . d  . € . 
    0C 20 03 04 61 00 62 00 72 20 05 00 63 20 03 00 64 20 03 80 0D 

为了解码字符串：

0C      number of Unicode chars: 12 (11 chars + \0) 
    20 03  . . .  ?? 
    04      next 5 
    61 00  a . 
    62 00  b . 
    72   r 
    20 05  . a .  back 6, take 3 
    00      next 1 
    63   c 
    20 03  . a .  back 4, take 3 
    00      next 1 
    64   d 
    20 03  . a .  back 4, take 3 
    80 0D  b . r . a . back 14, take 6 

所

这导致（UTF-16）：

a . b . r . a . c . a . d . a . b . r . a . 
    61 00 62 00 72 00 61 00 63 00 61 00 64 00 61 00 62 00 72 00 61 00 

不过，我没有线索是什么编码/压缩算法，这可能是。它看起来像LZ的一些变体，不使用字典（如LZ77），但到目前为止我还找不到与此描述相匹配的任何算法。我也不确定整个文件是这样编码的，还是仅仅是它的一部分。

你知道这种编码吗？或者你有什么提示，我可能会在文件中查找以识别编码？

Answer 1

您的编辑后，我认为这是LZF有以下区别，以你的观察：

• 神奇的标头和压缩VS非压缩的迹象，如果它嵌入已经在你的榜样（不算稀奇删除一份文件）。
• 您将块长度作为一个字节，但它是两个字节和big-endian，所以前面的0x00是长度的一部分，仍然有效。

Answer 2

可能是NTFS压缩，这是LZNT1。这个想法由平台和明显的2字节结构以及实际数据的字节对齐支持。

以下元素是特定于此算法。

块：压缩，未压缩或表示缓冲区结束的数据段。

Chunk header：压缩或未压缩数据块的标头。

标志字节：一个位标志，其位从低位读到高位指定后面的数据元素的格式。例如，位0对应于第一个数据元素，位1到第二个，依此类推。如果设置了与数据元素对应的位，则该元素是一个2字节的压缩字;否则，它是一个1字节的文字值。

标志组：一个标志字节，后跟零个或多个数据元素，每个数据元素是单个文字字节或2个字节的压缩字。