Deflate длина 258 двойное кодирование

В алгоритме Deflate есть два способа кодирования длины 258:

  1. Код 284 + 5 дополнительных битов всех 1

  2. Код 285 + 0 дополнительных битов;

На первый взгляд, это не оптимально, потому что правильное использование кода 285 позволит кодировать длину 259;

Является ли эта двойственность ошибкой спецификации, не исправленной по причинам совместимости, или есть некоторые аргументы об этом - например, длина 258 должна быть закодирована с более коротким кодом (0 дополнительных битов) по какой-то причине?

Источник

2 ответа

Решение

Возможно, мы никогда не узнаем. Фил Кац, разработчик формата deflate, скончался много лет назад в молодом возрасте.

Моя теория состоит в том, что длина совпадения была ограничена 258, так что длина совпадения в диапазоне 3..258 могла бы помещаться в байт, закодированный как 0..255. Этот формат был разработан примерно в 1990 году, когда это могло иметь значение в реализации на ассемблере.

Источник

Добавление второго ответа здесь, чтобы подчеркнуть предположение Марка о том, что разрешение кодировать длину в байте полезно для реализаций ассемблера. В то время ассемблер уровня 8086 все еще был распространен, и использование 8-битных регистров дало вам больше возможностей для работы с ними, чем использование их в 16-битном размере.

Преимущество еще более заметно на 8-битных процессорах, таких как 6502. Он начинается с декодирования длины. Символы 257 .. 264 обозначают длину совпадения 3... 10 соответственно. Если вы возьмете младший байт этих символов (1 .. 8), вы получите ровно на 2 меньше длины совпадения.

Более сложная, но достаточно простая для вычисления формула дает на 2 меньше длины совпадения символов с 265 по 284. 2 меньше, чем длина совпадения символа 285, равна 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.

Мне бы пришлось подумать, что Фил Кац интуитивно понимал, если не явно, преимущества сохранения длины совпадений в пределах 8 бит.

Источник
Другие вопросы по тегам