Недопустимые потоки дефлятирования, созданные кодировщиком PNG - PullRequest
Новая
       96

Недопустимые потоки дефлятирования, созданные кодировщиком PNG

0 голосов
/ 09 мая 2020

Я реализовал алгоритм deflate как часть кодировщика PNG в VHDL. Большинство тестовых входов сдуваются правильно, но есть проблема с двумя заданными c входами, и я не могу найти причину.

Первый вход - это пять строк с содержимым: 0 1 1 1 1 1 1 1 1 1. I. e. это изображение 3x5 RGB со всеми нулями и добавленным типом фильтра (= 0).

Второй вход - три строки с содержимым: 0 1 1 1 1 1 1 1 1 1 1. I. e. это изображение 5x3 в оттенках серого + альфа со всеми нулями и добавленным типом фильтра (= 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'] для второго входа.

Для проверки я использую модуль zlib pythons: 

>>> 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 верна, но оба кажутся быть недопустимыми для выкачивания потоков. Затем я попытался сам декодировать потоки. Начальная точка - это двоичное и инвертированное представление потоков, которое можно читать слева направо. Заголовок 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), которая могла бы выполнять раздувание с подробным выводом?

1 Ответ

1 голос
/ 11 мая 2020

У первого слишком большое расстояние. У второго есть несоответствие Адлера-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. Это потому что дополнительные биты не инвертированы. Дополнительные биты 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. Теперь расстояние не слишком велико, скорее, недостаточно, чтобы генерировать нужные данные. Отсюда неверная проверка Адлера-32.

...