缩短长度为258的双重编码（Deflate）

Question

7

在Deflate算法中有两种编码258长度的方法：

乍一看，这并不是最优的，因为正确使用代码285可以编码长度为259；

这种二元性是一些规范错误导致的吗？它没有被修复是因为兼容性原因吗？还是有一些关于它的论据-例如，必须使用更短的代码（0个额外的位）来编码长度为258，因为某种原因？

- johnfound

2个回答

5

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

在像6502这样的8位处理器上，好处更加明显。它从长度解码开始。符号257到264表示匹配长度分别为3到10。如果您取这些符号的低字节（1到8），则得到的值恰好比匹配长度小2。

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

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位内的好处。

- George Phillips

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Adler · Accepted Answer

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

我的理论是，匹配长度被限制为258，这样在范围为3..258的匹配长度可以适合一个字节中，编码为0..255。这种格式是在大约1990年开发的，在汇编实现中可能会有所不同。