从符号频次重建 Fraps 的 Huffman 解码表
FFmpeg 根据 Fraps 码流中的符号频次构造二叉前缀树，再生成实际使用的 VLC 解码表。
工程问题#
Fraps 压缩平面携带 256 个符号的频次，后续位流使用由这些频次决定的可变长编码。解码器必须重建一致的码字及符号对应关系，频次相同时也要遵守格式约定的顺序。
实际实现#
fraps2_decode_plane 读取频次并调用 ff_huff_build_tree。构建器以候选按权重正确排序为前提，反复合并最小的两个节点并重新插入父节点。父节点引用相邻的两个孩子；递归访问左、右孩子时分别追加 0 和 1，叶节点保存符号，最后将码字转换为 VLC 查表结构。
处理流程#
- 读取压缩平面携带的 256 个符号频次
- 按权重及规定的同权顺序排序待合并节点
- 反复合并最小两个节点，将父节点按新权重插回序列
- 沿二叉树生成码字与码长，再建立 VLC 解码表
- 使用 get_vlc2 解码符号，并恢复行间预测差值
源码片段#
固定版本 · 原文摘录99 for (i = 0; i < 256; i++)100 nodes[i].count = bytestream_get_le32(&src);101 size -= 1024;102 if ((ret = ff_huff_build_tree(s->avctx, &vlc, 256, VLC_BITS,103 nodes, huff_cmp,104 FF_HUFFMAN_FLAG_ZERO_COUNT)) < 0)105 return ret;106 /* we have built Huffman table and are ready to decode plane */107108 /* convert bits so they may be used by standard bitreader */109 s->bdsp.bswap_buf((uint32_t *) s->tmpbuf,110 (const uint32_t *) src, size >> 2);111112 if ((ret = init_get_bits8(&gb, s->tmpbuf, size)) < 0)113 return ret;114115 for (j = 0; j < h; j++) {116 for (i = 0; i < w*step; i += step) {117 dst[i] = get_vlc2(&gb, vlc.table, VLC_BITS, 3);从码流读取 256 个频次并调用 Huffman 建表，后续用 get_vlc2 取符号，建立实际视频解码路径的证据。
178 AV_QSORT(nodes, nb_codes, Node, cmp);179 cur_node = nb_codes;180 nodes[nb_codes*2-1].count = 0;181 for (i = 0; i < nb_codes * 2 - 1; i += 2) {182 uint32_t cur_count = nodes[i].count + nodes[i+1].count;183 // find correct place to insert new node, and184 // make space for the new node while at it185 for(j = cur_node; j > i + 2; j--){186 if(cur_count > nodes[j-1].count ||187 (cur_count == nodes[j-1].count &&188 !(flags & FF_HUFFMAN_FLAG_HNODE_FIRST)))189 break;190 nodes[j] = nodes[j - 1];191 }192 nodes[j].sym = HNODE;193 nodes[j].count = cur_count;194 nodes[j].n0 = i;195 cur_node++;196 }在候选正确按权重排序时，每轮把最小两项合成父节点，再将父节点插回；n0 与 n0 + 1 是该父节点的两个孩子。Fraps 比较器的数值限制在后续片段单独说明。
124 s = nodes[node].sym;125 if (s != HNODE || (no_zero_count && !nodes[node].count)) {126 bits[*pos] = pfx;127 lens[*pos] = pl;128 xlat[*pos] = s;129 (*pos)++;130 } else {131 pfx <<= 1;132 pl++;133 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl,134 pos, no_zero_count);135 pfx |= 1;136 get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0 + 1, pfx, pl,137 pos, no_zero_count);138 }139}内部节点递归访问两个孩子，左分支追加 0，右分支追加 1；叶节点写出码字、码长与符号，不是按键比较的搜索树。
77/**78 * Comparator - our nodes should ascend by count79 * but with preserved symbol order80 */81static int huff_cmp(const void *va, const void *vb)82{83 const Node *a = va, *b = vb;84 return (a->count - b->count)*256 + a->sym - b->sym;85}Fraps 比较器希望按频次排序并用符号打破平局，但减法和乘法有整数范围限制。因此解释后续 Huffman 合并时，必须保留频次排序正确这一前提。
片段展示频次表进入树构建器、二叉节点合并、递归生成码字及 Fraps 比较器。实际像素符号通过 VLC 表解码；比较器的数值边界不能从树的形状推出。
收益与取舍#
工程分析带来的收益
- 每个符号只出现在叶节点，根到叶的二进制路径自然形成前缀码
- 构建完成后转换成 VLC 查表结构，使解码过程无需每个比特都访问一个树节点
付出的代价
- 每个编码平面需保存频次并重建解码表；对于固定的 256 符号表，这是一笔明确的初始化成本
- 此实现用有序数组插入合并节点；若把符号数视为变量，构建过程含二次级移动成本，不能直接套用最小堆实现的 O(n log n)
- 频次比较器的整数算术有范围限制；源文件的总频次检查不等同于证明比较器在任意 32 位输入上都正确。
可比较的选择
直接遍历 Huffman 二叉树解码可复用同一套码字规则，表空间较小，但每个符号需要逐位推进；当前实现用 VLC 表换取批量位查找。
版本与适用范围#
对应 FFmpeg n7.1 的 Fraps v2 压缩平面路径。二叉树用于生成前缀码，节点不满足 BST 的按键排序约束；实际解码使用 VLC 表。该版 huff_cmp 对 32 位频次数值做减法和乘法，不能保证任意输入范围下的比较顺序；Huffman 的最优性要求候选按真实权重正确排序，不能仅凭调用了建树函数就作无条件保证。