Реализация алгоритма инфляции в zlib - PullRequest
Новая
       5

Реализация алгоритма инфляции в zlib

1 голос
/ 18 декабря 2011

В inftrees.c , который является кодом для построения таблицы поиска из канонического представления Хаффмана, автор пишет: 

 /* replicate for those indices with low len bits equal to huff */
    incr = 1U << (len - drop);
    fill = 1U << curr;
    min = fill;                 /* save offset to next table */
    do {
        fill -= incr;
        next[(huff >> drop) + fill] = here;
    } while (fill != 0);

    /* backwards increment the len-bit code huff */
    incr = 1U << (len - 1);
    while (huff & incr)
        incr >>= 1;
    if (incr != 0) {
        huff &= incr - 1;
        huff += incr;
    }
    else
        huff = 0

Я мог бы понять, что означает падение, хотя я прочитал комментарий много раз. Другой вопрос: какой метод использует автор для создания кода Хаффмана? Что такое назад приращение?

Не могли бы вы объяснить это для меня, спасибо.

1 Ответ

2 голосов
/ 18 декабря 2011

«Обратный прирост huff» означает huff = rev(rev(huff) + 1), где rev инвертирует биты 0, ..., len - 1.

Предположим, len == 7 и huff равно 1110100 в двоичном виде.Мы ищем первый бит сброса, очищаем все ниже (значение) / выше (шаблон бит) и устанавливаем этот бит. 

1110100
^
1000000 == incr: loop continues
 ^
0100000 == incr: loop continues
  ^
0010000 == incr: loop continues
   ^
0001000 == incr: loop breaks

1110100: huff
0000111: incr - 1
0000100: huff &= (incr - 1)
0001100: huff += incr
...