258 双编码的放气长度

Question

在 Deflate 算法中，有两种方法可以对长度为 258 进行编码：

乍一看，这不是最佳选择，因为正确使用代码 285 将允许编码长度为 259；

这种对偶性是某种规范错误，由于兼容性原因而未修复，还是存在一些争论 - 例如，由于某种原因，长度 258 必须用较短的代码（0 个额外位）进行编码？

Answer 1

我们可能永远不知道。deflate 格式的开发者 Phil Katz 多年前在年轻时就去世了。

我的理论是匹配长度限制为 258，因此 3..258 范围内的匹配长度可以放入一个字节中，编码为 0..255。这种格式是在 1990 年左右开发的，当时这可能会对汇编程序的实现产生影响。

Answer 2

在这里添加第二个答案是为了强调 Mark 的猜测，即允许将长度编码为字节有助于汇编器实现。当时 8086 级汇编器仍然很常见，使用 8 位形式的寄存器比使用 16 位大小的寄存器可以让您使用更多的寄存器。

这种优势在 6502 等 8 位处理器上更为明显。它从长度解码开始。符号257..264分别表示3..10的匹配长度。如果您采用这些符号的低字节 (1 .. 8)，您将得到比匹配长度精确 2 的值。

一个更复杂但相当容易计算的公式给出了比符号 265 到 284 的匹配长度小 2。比符号 285 的匹配长度小 2 的是 256。这不适合一个字节，但我们可以存储 0，结果是是等价的。

zlib6502利用这一点获得了相当大的优势。它计算中的匹配长度inflateCodes_lengthMinus2。一旦确定了进入窗口的后向指针，它就会像这样复制数据：

    jsr copyByte
    jsr copyByte
inflateCodes_copyByte
    jsr copyByte
    dec inflateCodes_lengthMinus2
    bne inflateCodes_copyByte

它进行两次显式调用来复制一个字节，然后在长度小于 2 的长度上循环。对于长度 1 到 255，它的工作原理与您所期望的一样。对于长度 0，它实际上会按照我们的期望迭代 256 次。第一次循环时，长度 0 减少到非零的 255，因此循环又继续 255 次，总共 256 次。

我不得不认为 Phil Katz 直观地理解了将匹配长度保持在 8 位以内的好处（如果不是明确的话）。