// Чтение кодов из потока
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, спасибо автору. Его пример использовал для отладки алгоритма, в качестве тестового вектора.
Комментариев нет:
Отправить комментарий