Deflate -- собственная реализация

Я пытался осознать как написан zlib, чтобы встроить картинки PNG в контроллер. Не понравилось, взялся за реализацию из RFC 2083 (PNG) и RFC 1951 (Deflate). Задача - реализовать Deflate с таблицами Хаффмана для распаковки изображений PNG. Интерсно, сколько Марку Адлеру лет. Нашел, что он проявлял активность в проекте zlib-ng еще совсем недавно. Марк Адлер (со)автор таких значимых форматов и утилит, как: zlib, deflate, brotli, zopfli, pigz. И все равно пишет не читабельный код. Итак, приступим. Базовая операция в формате Deflate, на которую завязано быстродействие - это чтение из битового потока по одному биту. Производительность теоретическая, которую можно на этом получить - один такт на бит. После чтения из потока одного бита выполняется поиск кодовой последовательности по дереву бинарному. Это вам повезет найти в реализации zlib бинарное дерево. Я не нашел. Захотел реализовать свою концепцию поиска в дереве двоичных кодов, без дерева.

// Чтение кодов из потока
uint32_t huffman_read_bit(uint32_t code)
{
	code = (code<<1) | (stream&1);
	stream >>= 1;
	return code;
}

Эту операцию можно оптимизировать с использованием инструкций Intel BMI и BMI2, или с использованием сдвига через флаг переноса CF.

#include <intrin.h>
code = (code<<1) + _bittest(src, offset++);

Например, такая операция с использованием псевдофункции дает производительность в цикле ровно один такт на бит. Можно ускорить работу алгоритма, если выполнять операция разворачивания бит оптом, сразу на всем потоке, просто идея.

// Алгоритм поиска кодов Хаффмана без кодовых таблиц.
uint32_t huffman_decode(uint8_t *bl_count, int max_bl)
{
    uint32_t bt_code=0, bt_offset=0, code=0;
    int i=0;
    for(i=0; i<=max_bl; i++, bt_code <<= 1) {
        code = huffman_read_bit(code, 1);
        if (bl_count[i]==0) continue;
        if (code - bt_code < bl_count[i]) break;
        bt_code   += bl_count[i];
        bt_offset += bl_count[i];
    }
    return bt_offset + (code - bt_code);
}

Алгоритм возвращает индекс в упорядоченном по кодам Хаффмана массиве представляющем собой алфавит кодов. На каждом шаге алгоритма надо выбирать один бит и совершать ветвление в дереве. Опереации с деревом оказались не нужны, все основано на вычислении индекса в таблице алфавита в соответствии с кодом. Натолкнула на мысль о вычислении индекса в массиве методика расчета начальных кодов с заданной разрядностью, которая представлена в исходном коде Deflate. Массив bl_count содержит на входе число длин кодовых последовательнстей, длина выступает индексом.

// расчет кодов Хаффмана
for (i = 1; i < MAX_BITS; i++) {
        next_code[i] = code;
        code = (code + bl_count[i]) << 1;
}
next_code[i] = code;

В оригинальной реализации обнаружил функцию разворота порядка следования бит и составление таблиц в человеческом представлении, порядок в таблице по номеру символа. В моей таблице порядок - по коду Хаффмана. Разворачивать индексы, в отличие от исходного Deflate, в нашей реализации не понадобилось. Исходный код генерации таблиц: gen_codes.

Пример алфавита и кодов
   Литерал/длина/ код
         0:  6, 3c
         1:  0, 0
         2:  7, 7c
         3:  7, 7d
         4:  4, c
         5:  5, 1c
         6:  5, 1d
         7:  4, d
         8:  2, 0
         9:  2, 1
        10:  3, 4
        11:  7, 7e
        12:  6, 3d
        13:  0, 0
        14:  0, 0
        15:  0, 0
        16:  3, 5
        17:  7, 7f
        18:  0, 0

В нашем случае алфавит укладывается по порядку кодов, коды с длинами 0 не используются. Порядок определяется значением кода. Сначала идут коды с меньшей разрядностью, потом с большей.

по порядку кодов: 8 9 10 16 4 7 5 6 0 12 2 3 11 17

Ниже привожу мой алгоритм распаковки Deflate с использованием динамических таблиц. Хотя, самих таблиц, как и дерева бинарного поиска, тут нет. Функция huffman_decode вычисляет налету индекс в алфавите литералов, длин и смещений.

while(src<s_end){
    uint32_t code = huffman_decode(cwl_count, max_cwl);
    code = cwl_alpha[code];// Алфавит литералов и длин
    if (code < 256){// Декодирование литерала
        *dst++ = code;
    } else {
        if (code==256) // код завершения
            break;
        // Декодирование длины по основному алфавиту
        int mlen = fixed_length_mlen [code-257]+3;
        int extra= fixed_length_extra[code-257];
        if (extra){ // чтение бит из потока
            mlen += stream_read_bit(extra);
        }
        // Декодирование смещения по алфавиту смещений
        code = huffman_decode(dl_count, max_dl);
        code = dl_alpha[code];// Алфавит смещений
        uint32_t offset= fixed_distance_offset[code]+1;
        extra = fixed_distance_extra [code];
        if (extra){
            offset += stream_read_bit(extra);
        }
        {// фукнция копирования подстроки
            uint8_t * s = dst-offset;
            int i;
            for(i=0; i < mlen; i++)
                *dst++ = *s++;
        }
    }
}

Исходный код на Github
Очень помогло подробное описание разбора потока Deflate, спасибо автору. Его пример использовал для отладки алгоритма, в качестве тестового вектора.