HPACK中的霍夫曼编码

HTTP2.02中头部采用了二进制格式，具体编码在HPACK3也已经详细解释了。 HPACK中对于字符串使用了霍夫曼编码4来让传输更有效率，但是对于霍夫曼的解码过程一直没想 到如何仅仅使用查表的方法来进行。在看过一些论文和博客之后勉强想到了一个简单的可能不是很有效率的查表办法。

下图是简单的霍夫曼编码树的展示，简洁说明5个符号的编码构造过程：

../_images/huffman_tree.png

简单的霍夫曼编码树

从编码树中我们可以获取符号的编码表：

Symbol

code as bits

len in bits

A

00

2

B

01

2

C

10

2

D

110

3

E

111

3

霍夫曼解码的过程常规仍是构造和编码时一样的霍夫曼树，如图1，然后从根节点开始一次读取每一个bit为 0时向左孩子行进，为1时向右孩子行进，直到到达叶子节点，获取解码后的符号。 这是解码一个符号的步骤，缺点是在HAPCK中，各个符号的编码已经知晓了，这样可以根据编码去反向构造霍夫曼树， 但是需要大量的分配内存及我们仅仅想使用它的解码功能，并且当在程序中解码树根节点不方便保存及释放。

这里我考虑使用一个类似与有限自动机的方法来实现解码，首先将每一个编码按4bit分成若干组，HPACK中最长的编码 长度是30，每一个编码最多能分成8组。分好后，将所有组编码组成一颗16叉树，并且让孩子节点的索引值与分组的值相等。这样的话 可以每次读取4个比特，然后得到相对应的孩子节点，如果该节点指向了一个符号，则得到了解码结果。大概过程为

  1. 设置当前节点为根节点

  2. 读取4比特存入c

  3. 以c的值最为孩子节点的索引获取孩子节点

  4. 判断孩子节点信息

    1. 节点对应了一个有效符号A，跳转到(1)，继续解析下一个符号

    2. 节点不对应任何符号，跳转到(2)

例如，HPACK中a的编码为00011，我们先分割为0001，1xxx两组， 构造解码树时按照组中每一个值是孩子节点的位置索引，而最后一个值指向终点，代表一个解码后的符号。1xxx这类的表示多个 孩子节点对应同一个解码符号，比如下图中真实表示的几个符号：

../_images/huff_decode_state.png

部分解码树孩子索引示意图，彩色的位代表了完整字符的位编码

解码树的生成

为了生成上图中解码树，需要先对编码表进行预处理，我的方法是

  1. 将所有编码分为4位一组，最长编码30位，所以最长8组

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
        unsigned char split_bits[256][8];
    /* split huffman code to n * 4 bits */
    for (i = 0; i < 256; i++) {
        unsigned int code = huff_sym[i].code;
        int bits = huff_sym[i].bits;

        for (j = 0; j < bits / 4; j++) {
            unsigned int four_bits = code;
            four_bits <<= 32 - bits + j * 4;
            four_bits >>= 28;
            split_bits[i][j] = (unsigned char)four_bits;
        }

        if (bits % 4) {
            unsigned int remain_bits = code;
            remain_bits &= (1 << (bits % 4)) - 1;
            split_bits[i][bits / 4] = (unsigned char)remain_bits;
        }
    }

  2. 根据分割的位组构建解码树

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
    typedef struct _huff_decode_node_s {
    int idx;
    char ending;
    unsigned char sym;
    struct _huff_decode_node_s *child[16];
} huff_decode_node_t;

huff_decode_node_t *build_huff_decode_tree(unsigned char split_bits[256][8]) {
    int i, j;
    huff_decode_node_t *root;
    root = (huff_decode_node_t *)malloc(sizeof(huff_decode_node_t));
    memset(root, 0, sizeof(huff_decode_node_t));

    for (i = 0; i < 256; i++) {
        int idx;
        huff_decode_node_t *node;
        huff_decode_node_t *tmp = root;
        for (j = 0; j < huff_sym[i].bits / 4; j++) {
            idx = split_bits[i][j];
            node = tmp;
            if (node->child[idx] == NULL) {
                node->child[idx] = (huff_decode_node_t *)malloc(sizeof(huff_decode_node_t));
                memset(node->child[idx], 0, sizeof(huff_decode_node_t));
            }
            tmp = node->child[idx];
        }

        if (huff_sym[i].bits % 4) {
            idx = split_bits[i][j];
            node = tmp;
            tmp = (huff_decode_node_t *)malloc(sizeof(huff_decode_node_t));
            memset(tmp, 0, sizeof(huff_decode_node_t));
            tmp->ending = 1;
            tmp->sym = i;

            idx <<= (4 - huff_sym[i].bits % 4);
            for (j = 0; j < (1 << (4 - huff_sym[i].bits % 4)); j++) {
                assert(node->child[idx + j] == NULL);
                node->child[idx + j] = tmp;
            }
        } else {
            tmp->ending = 1;
            tmp->sym = i;
        }
    }
    return root;
}

  3. 为解码树的节点建立编号

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
    int index_decode_node(huff_decode_node_t *node, int idx) {
    int i;
    node->idx = idx++;
    for (i = 0; i < 16; i++) {
        if (node->child[i] && !node->child[i]->ending) {
            idx = index_decode_node(node->child[i], idx);
        }
    }
    return idx;
}

经过这些步骤后已经建立好一个解码树了，树中每个节点有16个孩子。这样我们解码时就可以根据 4位组的值为孩子节点索引，从根节点开始行进解码。当解码完一个字符后，重新回到根节点，解码 下一个字符。

解码树的节点建立编号是为了下一步将解码树转换为状态机的形式，固定地编码在数据区。免去 每次解码都要构建解码树的麻烦。

转换为状态表

先定义如下的解码状态，先前的每个编码树节点将会转换16个状态，其实编码过的节点有54个。 最大的编号为0x35。所以完全可以将ending和next合并为一个字节，节省 三分之一的空间。然后对所有的节点进行序号编排，这个序号作为状态转移的依据。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

typedef struct _huff_decode_state_s {
    unsigned char next;
    unsigned char sym;
    unsigned char ending;
} huff_decode_state_t;

void convert_node_to_state_table(huff_decode_node_t *node, huff_decode_state_t state[55][16]) {
    int i;
    int idx = node->idx;
    for (i = 0; i < 16; i++) {
        if (node->child[i]) {
            state[idx][i].ending = node->child[i]->ending;
            state[idx][i].next = node->child[i]->idx;
            state[idx][i].sym = node->child[i]->sym;
            convert_node_to_state_table(node->child[i], state);
        }
    }
}

完成后将state[55][16]的内容打印出来，就组成了静态的解码状态表。完整的表见源代码1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
huff_decode_state_t decode_state[][16] = {
    {
        { 0x01, 0x00, 0x00 }, { 0x02, 0x00, 0x00 },
        { 0x03, 0x00, 0x00 }, { 0x04, 0x00, 0x00 },
        { 0x05, 0x00, 0x00 }, { 0x06, 0x00, 0x00 },
        { 0x07, 0x00, 0x00 }, { 0x08, 0x00, 0x00 },
        { 0x09, 0x00, 0x00 }, { 0x0a, 0x00, 0x00 },
        { 0x0b, 0x00, 0x00 }, { 0x0c, 0x00, 0x00 },
        { 0x0d, 0x00, 0x00 }, { 0x0e, 0x00, 0x00 },
        { 0x0f, 0x00, 0x00 }, { 0x10, 0x00, 0x00 },
    },
    {
        { 0x00, 0x30, 0x01 }, { 0x00, 0x30, 0x01 },
        { 0x00, 0x30, 0x01 }, { 0x00, 0x30, 0x01 },
        { 0x00, 0x30, 0x01 }, { 0x00, 0x30, 0x01 },
        { 0x00, 0x30, 0x01 }, { 0x00, 0x30, 0x01 },
        { 0x00, 0x31, 0x01 }, { 0x00, 0x31, 0x01 },
        { 0x00, 0x31, 0x01 }, { 0x00, 0x31, 0x01 },
        { 0x00, 0x31, 0x01 }, { 0x00, 0x31, 0x01 },
        { 0x00, 0x31, 0x01 }, { 0x00, 0x31, 0x01 },
    },

解码

有了解码状态表后，就可以依据该表来进行解码了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int huff_decode(char *dst, int cap, const char *src, int src_len) {
    huff_decode_state_t *state;
    int cur = 0;
    int bits = 0;
    int src_bits = src_len * 8;
    int len = 0;
    unsigned char c = 0;
    do {
        int idx = bits / 8;
        int off = bits % 8;
        c = src[idx];
        c <<= off;
        c >>= 4;
        if (off > 4) {
            c |= (unsigned char)src[idx + 1] >> (8 - off % 4);
        }
        bits += 4;
        state = &decode_state[cur][c];
        if (state->ending) {
            dst[len++] = state->sym;
            cur = 0;
            if (huff_sym[state->sym].bits % 4)
                bits -= 4 - huff_sym[state->sym].bits % 4;
        } else {
            cur = state->next;
        }
    } while (bits + 4 <= src_bits && len < cap);
    dst[len] = 0;
    return len;
}

解码代码中需要仔细根据已解码的位长来计算待解码的数组索引和位索引。

编码

编码比较简单，计算好已编码的位长，来确定写入的数组索引和位偏移。最后不足8位的填充 EOS.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int huff_encode(char *dst, int cap, const char *src, int src_len) {
    int i, bits, off, idx, remain;
    unsigned int code;
    if (src_len == -1)
        src_len = strlen(src);
    bits = 0;
    for (i = 0; i < src_len; i++) {
        huff_sym_t *sym = &huff_sym[(unsigned char)src[i]];
        code = sym->code;
        remain = sym->bits;
        idx = bits / 8;
        off = bits % 8;
        if (off) {
            if (8 - off >= remain) {
                dst[idx] |= code << (8 - remain - off);
                bits += remain;
                remain = 0;
            } else {
                dst[idx] |= code >> (remain - (8 - off));
                bits += 8 - off;
                remain -= 8 - off;
            }
        }
        if (remain) {
            assert(bits % 8 == 0);
            for (; remain >= 8; remain -= 8) {
                code = sym->code;
                idx = bits / 8;
                code <<= 32 - remain;
                code >>= 24;
                dst[idx] = (unsigned char)code;
                bits += 8;
            }
        }
        if (remain > 0) {
            code = sym->code;
            idx = bits / 8;
            code <<= 8 - remain;
            dst[idx] = (unsigned char)code;
            bits += remain;
        }
        if (bits > cap * 8) {
            return cap;
        }
    }
    if (bits % 8) {
        idx = bits / 8;
        off = bits % 8;
        dst[idx] |= (1 << (8 - off)) - 1;
        bits += 8 - off;
    }
    assert(bits % 8 == 0);
    return bits / 8;
}

编码中所用到的符号表是在HPACK中定义的，这里不在列出了。

1

本文源代码: ../_static/hpack_huffman.c

2

HTTP2.0 RFC: https://httpwg.github.io/specs/rfc7540.html

3

HPACK RFC: https://httpwg.github.io/specs/rfc7541.html

4

huffman编码: https://en.wikipedia.org/wiki/Huffman_coding

Previous: 漂亮的原生库   Next: sphinx中使用mermaid画图