Реализация Zlib алгоритма раздувать

Question

В inftrees.c, что код, чтобы построить таблицу поиска из канонического HUFFMAN представления, автор запись:

/* 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 

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

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

Answer 1

"Обратный приращение 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