0

我一直在尝试理解一个示例 inflate 实现，这有点令人困惑：

static int decode(struct state *s, struct huffman *h)
{
    int len;            /* current number of bits in code */
    int code;           /* len bits being decoded */
    int first;          /* first code of length len */
    int count;          /* number of codes of length len */
    int index;          /* index of first code of length len in symbol table */

    code = first = index = 0;
    for (len = 1; len <= MAXBITS; len++) {
        code |= bits(s, 1);             /* get next bit */
        count = h->count[len];
        if (code - count < first)       /* if length len, return symbol */
            return h->symbol[index + (code - first)];
        index += count;                 /* else update for next length */
        first += count;
        first <<= 1;
        code <<= 1;
    }
    return -10;                         /* ran out of codes */
}

特别是这部分：

first += count;
first <<= 1;

有人能解释一下位移或乘以常数是如何产生特定代码长度的实际第一个代码的吗？基本上，第一个代码的索引和实际的第一个代码之间的差异是“2倍”？

为简单起见，只需考虑它从 7 位长度滚动到 8 位长度，其中 7 产生第一个非零计数，在固定版本中将是 24，我猜因为间隔是 [256, 280>。

我的假设是它保留了代码和下一个长度的第一个之间的数量级，因为它们的减法关系比确定符号偏移的绝对值更相关 - 但是 - 我不太确定是这种情况.

4

1 回答 1

1

count[len]是每个比特长度的代码数。对于 deflate 格式定义的规范代码，代码只是从零开始计数。所以第一个非零的第一个代码count[len]是len零位。如果count[len]大于一个，则下一个代码比那个多一个，或者只是len-1零位和一位。

当使用该长度的代码时，在末尾添加一个零位以进入下一个长度。

因此，要从第一个长度代码i到第一个长度代码的步骤i+1，您添加count[i]然后左移一位。

示例代码：

length   code
   2     00
   2     01
   3     100
   3     101
   3     110
   4     1110
   4     1111

我们从00开始第一个代码，长度为2。有两个长度为2的代码，所以我们加2并左移一位，即乘以2，得到长度为3的第一个代码，即（ 0 + 2) * 2 = 4 = 100。要获得长度为 4 的第一个代码，它的 (4 + 3) * 2 = 14 = 1110。

于 2013-05-31T00:05:05.117 回答