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