逆向工程 - 解码 LZSS 缓冲区查找索引 - 吾爱随笔录

我正在解压缩一个相机固件文件，该文件由我能够正确拆分和验证的各个部分组成。该文件中的一个部分使用此处描述的 LZSS 形式另外压缩，我无法确定查找字节的正确格式。

数据以 2 个未压缩的数据块开始，每个块为 4096 字节（或单个 8192 字节的块，但是您想查看它），然后跟随压缩数据。

压缩数据以标志字节开始，其位（从 LSB 开始）告诉以下哪些字节将被复制（位设置），哪些是查找信息（位未设置）。查找信息由 2 个字节/16 位组成，我正在寻找帮助以解码其确切格式。

我已经知道：

MSB 包含index在查找缓冲区中
LSB 包含length查找的字节数，即要从给定索引处的查找缓冲区复制的字节数
的length是至少3个比特
实际查找长度是length + 3（因为 3 是查找有意义的最小长度，例如位指示长度 2 等于 5 个字节的实际查找长度）

我猜测：

查找长度是 3 位或 4 位（在我可以手动解码的数据中，我没有发现需要 4 位的长度）
由于查找是 3 位或 4 位，因此索引应为 13 或 12 位。12 位使查找缓冲区大小为 4096 字节，13 位使大小为 8192，对应于顶部的未压缩数据块，可以是缓冲区的初始化数据

让我们解压一段摘录，从00675CCE：

00675CC0  65 0D 0A 0D FD 0A 33 C0 3C 68 74 6D 6C 3E FF 3C  e...ý.3À<html>ÿ<
00675CD0  68 65 61 64 3E 3C 74 BF 69 74 6C 65 3E 34 40 C0  head><t¿itle>4@À
00675CE0  42 FF 61 64 20 52 65 71 75 65 6F 73 74 3C 2F 5F  Bÿad Requeost</_
00675CF0  C3 3C 2F 59 C3 6F 62 6F 64 79 57 C0 31 3E 69 CA  Ã</YÃobodyWÀ1>iÊ
00675D00  FE 8A C0 3C 70 3E 59 6F 75 72 FF 20 62 72 6F 77  þŠÀ<p>Yourÿ brow

解码顺序：

00675CCE FF: read 8 bytes ("<head><t")
00675CD7 BF: read 6 bytes ("itle>4")
             lookup 40C0 -> read 3 bytes @ ? index ("00 ")
             read 1 byte  ("B")
00675CE0 FF: read 8 bytes ("ad Reque")
00675CEA 6F: read 4 bytes ("st</")
             lookup 5FC3 -> read 6 bytes @ ? index ("title>")
             read 2 bytes ("</")
             lookup 59C3 -> read 6 bytes @ ? index ("head><")
00675CF5 6F: read 4 bytes ("body")
             ...

解码结果：

00000000  3C 68 65 61 64 3E 3C 74 69 74 6C 65 3E 34 30 30  <head><title>400
00000010  20 42 61 64 20 52 65 71 75 65 73 74 3C 2F 74 69   Bad Request</ti
00000020  74 6C 65 3E 3C 2F 68 65 61 64 3E 3C 62 6F 64 79  tle></head><body

现在让我们看看最后两个查找及其潜在的解码：

0x5FC3 = 0101111111000011b
         0101111111000 011 -> index 3064, length 6 (3 + 3 per above rule)
         010111111100 0011 -> index 1532, length 6

0x59C3 = 0101100111000011b
         0101100111000 011 -> index 2872, length 6
         010110011100 0011 -> index 1436, length 6

我特意选择了这个例子，因为两个查找都只返回几个字节。在解码的输出/查找缓冲区中，0x5FC3回溯 23 个字节并0x59C3回溯 38 个字节。长度绝对正确，但索引号对我来说没有意义。无论我假设哪个缓冲区大小，或者索引是从缓冲区的前面还是后面开始，甚至区分字节顺序，数字都不适合。我假设查找索引，由于只回顾几个字节，应该在缓冲区的下边缘或上边缘。同样由于它们在压缩数据和查找数据中的附近，它们的索引应该非常接近。

所以问题是如何正确解释查找索引，或者，假设它们是正确的，查找缓冲区如何工作，因为在这种情况下它不能是标准的循环缓冲区。任何帮助将不胜感激！

ps：如果有人感兴趣，YI M1 和 Fujifilm X-A10 相机使用的是有问题的固件格式。固件解包器的当前状态可在 GitHub 上获得。

更新： 进一步的调查使我想到了这个相关的 RE 问题和LZRW 压缩系列，其中查找索引也可能引用某种查找表，而不是直接引用到数据中。

更新 2： 发现查找长度至少需要 4 位的证据。还发现查找字节是按大端顺序存储的（好像我上次尝试时犯了一个错误）。

0x5FC3 = 0101111111000011b
         110001011111 0011 -> index 3167, length 6 (big endian)

0x59C3 = 0101100111000011b
         110001011001 0011 -> index 3161, length 6 (big endian)

在我在链接代码存储库中设置的测试用例中，我注意到许多查找关闭了 709 字节，所以我添加了一个 709 的初始查找缓冲区写入偏移量，现在我能够正确解码大部分数据，包括上面的例子。其他部分似乎需要另一个偏移量，所以这仍然有待弄清楚。

更新 3： 通过分析查找偏移量变化的位置，我注意到更长的 0x00 字节序列如果数据被压缩显然不会存在。仔细观察它们，结果发现它们是 2048 字节对齐的填充，并且压缩数据部分再次由几个子部分组成。一旦我将它们分开并分别解压缩，改变缓冲区查找偏移的问题就解决了。所以最后似乎 LZSS 算法的工作原理与我上面已经发布的链接完全一样。奥秘不在于压缩本身，而在于文件结构。对此仍有一些问题未解决，一旦我完成，我将发布更详细的答案。