这是哪种编码/压缩算法？

Question

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

现在，在经过多次尝试之后，我发现文件的某些部分使用run进行编码。每个run都以一个指示将要跟随多少个字节以及从哪里检索数据的字节开头。

• 000ddddd（1字节）
  从编码数据中取出接下来的（ddddd）+1个字节。
• 111····· ···ddddd ···bbbbb（3字节）
  回到已解密数据中（bbbbb）+1个字节，并从其后继续取出（ddddd）+9个字节。
• ddd····· ··bbbbbb（2字节）
  回到已解密数据中（bbbbbb）+1个字节，并从其后继续取出（ddd）+2个字节。

这是一个例子：

This is the start of the file, with the UTF-16 string abracadabra encoded in it:

  .     .  .  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

To decode the string:

  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

This results in (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），但到目前为止，我还没有找到任何与此描述相匹配的算法。我也不确定整个文件是否都是这样编码的，还是只有部分内容。

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

- Daniel A.A. Pelsmaeker

---

你确定这个文件包含文本吗？ - Hidde

@Hidde 我可以命令程序给我一个包含我选择的特定18个字符字符串的大文件。这些是我选择的字符串，以及它们在生成的文件中对应的编码版本。我没有在二进制文件中找到任何其他字符串，但这可能是由于编码造成的。 - Daniel A.A. Pelsmaeker

看起来第一个字节是您的十六进制字符串长度。 - Jan Nielsen

如果这种编码是为了压缩，那它一定会获得有史以来最差的压缩方法奖！ - Mark Adler

请提供空字符串、单个字符和单个非ASCII字符（即需要使用UTF-8或UTF-16进行编码的字符）的结果。 - Mark Adler

Answer 1

可能是NTFS压缩，使用的是LZNT1算法。该想法得到了平台和明显的两字节结构的支持，以及实际数据的字节对齐。

以下元素特定于此算法： 块：被压缩、未压缩或表示缓冲区结尾的数据段。 块头：压缩或未压缩数据块的头。 标志字节：一个位标志，其位从低位到高位读取，指定后续数据元素的格式。例如，第0位对应第一个数据元素，第1位对应第二个数据元素，依此类推。如果设置了对应于数据元素的比特，则该元素为 2 字节压缩字，否则为 1 字节文字值。 标志组：标志字节后跟零个或多个数据元素，每个数据元素都是单个文字字节或 2 字节压缩字。

- Ben Jackson

---

你可能有眉目了。我会调查一下。 - Daniel A.A. Pelsmaeker

我深入研究了这个文件，发现不仅是字符串，整个文件（或者至少部分内容）都被使用某种LZ变体进行了压缩。然而这不是LZNT1，因为它以16位块头开始，指示块的大小。如截图所示，第一个16位值为“1”，而且该块肯定不止1字节长。但是我会继续搜索。感谢您的建议。 - Daniel A.A. Pelsmaeker

@Virtlink：前面可能还有一个特定于应用程序的标头。如果您浏览一下，是否有任何字节看起来合理作为块大小？ - Ben Jackson

我找不到任何表明块大小的东西，也没有任何以重复间隔（例如每4K）出现的标题或边框样式。但是，我已经能够反向工程使用的编码，但我不认识它并且找不到有关它的任何信息。请查看我的更新后的帖子。 - Daniel A.A. Pelsmaeker

Answer 2

在你的编辑之后，我认为它是LZF，与你的观察有以下不同之处：

- 在你的示例中删除了魔术标头和压缩与未压缩的指示（如果它嵌入在文件中，这并不奇怪）。 - 你将块长度视为一个字节，但它是两个字节和大端序，因此先前的0x00是长度的一部分，仍然有效。

- Ben Jackson

---

是的！你似乎一针见血了。我怀疑这是一个或多个LZF压缩文件在容器中。 - Daniel A.A. Pelsmaeker