由PNG编码器生成的无效放气流

Question

我在VHDL中将deflate算法实现为PNG编码器的一部分。大多数测试输入均已正确放气，但是两个特定的输入存在问题，我找不到原因。

第一个输入为五行，内容为：0 1 1 1 1 1 1 1 1 1。即这是一个全为零的3x5 RGB图像，并且过滤器类型（= 0）处于前置。

第二输入是三行，内容：0 1 1 1 1 1 1 1 1 1 1。即这是一个5x3灰度+带有全零的Alpha图像，并且过滤器类型（= 0）处于前置。

模拟的输出是

分别为第一个输入的[['0x78', '0x1', '0x63', '0x60', '0x84', '0x1', '0x24', '0x26', '0x12', '0x13', '0x89', '0x9', '0x5', '0x0', '0x4', '0x97', '0x0', '0x2e']

['0x78', '0x1', '0x63', '0x60', '0x84', '0x3', '0x24', '0x16', '0x12', '0xb', '0x0', '0x2', '0x10', '0x0', '0x1f']用于第二个输入。

为了验证，我正在使用pythons zlib模块：

>>> zlib.adler32(bytes(([0] + [1]*9)*5)).to_bytes(4, "big")
b'\x04\x97\x00.'
>>> deflated_data = bytes([int(b, 16) for b in ['0x78', '0x1', '0x63', '0x60', '0x84', '0x1', '0x38', '0x13', '0xce', '0x84', '0x33', '0xe1', '0x4c', '0x10', '0x0', '0x0', '0x4', '0x97', '0x0', '0x2e']])
>>> zlib.decompress(deflated_data)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
zlib.error: Error -3 while decompressing data: invalid distance too far back

>>> zlib.adler32(bytes(([0] + [1]*10)*3)).to_bytes(4, "big")
b'\x02\x10\x00\x1f'
>>> deflated_data = bytes([int(b, 16) for b in ['0x78', '0x1', '0x63', '0x60', '0x84', '0x3', '0x24', '0x16', '0x12', '0xb', '0x0', '0x2', '0x10', '0x0', '0x1f']])>>> zlib.decompress(deflated_data)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
zlib.error: Error -3 while decompressing data: incorrect data check

所以adler校验和是正确的，但是两者都对deflate流无效。接下来，我尝试自己解码流。起点是流的二进制表示形式和反向表示形式，可以从左到右读取。删除了Zlib标头和adler校验和。霍夫曼表取自https://www.ietf.org/rfc/rfc1951.txt。

['11000110', '00000110', '00100001', '10000000', '00100100', '01100100', '01001000', '11001000', '10010001', '10010000', '10100000', '00000000']

110      - block header (last block and fixed huffman code)
00110000 - literal 0  -> 0
00110001 - literal 1  -> 1
0000110  - match length 8
00000    - match distance 1  -> 11111111
--------------------------------
0001001  - match length 11/12
0        - match length 11
00110    - match distance 9-12
01       - match distance 10
-------------------------------- repeat two times  -> 01111111110, 11111111101, 11111111011
0000101  - match length 7
0        - match distance 1  -> 1111111
0000000  - end of block
00000    - will be discarded

This yields the original data:
0 1 11111111
01111111110
11111111101
11111111011
1111111

['11000110', '00000110', '00100001', '11000000', '00100100', '01101000', '01001000', '11010000', '00000000']

110      - block header (last block and fixed huffman code)
00110000 - literal 0  -> 0
00110001 - literal 1  -> 1
0000111  - match length 9
00000    - match distance 1  -> 111111111
--------------------------------
0001001  - match length 11/12
0        - match length 11
00110    - match distance 9-12
10       - match distance 11
-------------------------------- repeat one time  -> 01111111111, 01111111111
0000000  - end of block
0000     - will be discarded

This yields the original data:
0 1 111111111
01111111111
01111111111

我看不到无效的距离或任何无效/不正确的数据。有人可以指出我的错误在哪里吗？是否有一个（python）库，可以用冗长的输出来充气？

Answer 1

第一个距离太远。第二个有Adler-32不匹配。

infgen第一个输出：

! infgen 2.4 output
!
zlib
!
last
fixed
literal 0 1
match 8 1
match 11 11
infgen warning: distance too far back (11/10)
match 11 11
match 11 11
match 7 1
end
!
adler

您认为距离10实际上是距离11。这是因为多余的位被[[not颠倒了。那里的额外位是10，而不是01。因此距离11，而不是10。

对于第二个，INFGEN给出：

! infgen 2.4 output
!
zlib
!
last
fixed
literal 0 1
match 9 1
match 11 10
match 11 10
end
!
adler

相同的问题，但实际上它是10时却以为01。现在，距离并不算太远，但还远不足以生成所需的数据。因此，Adler-32检查不正确。