zlib數據執行充氣算法的

Question

在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 

我能想出什麼下降，雖然我的意思多次閱讀評論。另一個問題是作者用什麼方法來構建huffman代碼？什麼是向後增量？

您能否爲我解釋一下，謝謝。

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