Appendix C. Sample Single-Pass Encoding Algorithm (单遍编码算法示例)

单遍编码的伪代码, 不包括处理重复项、非阻塞模式、可用编码器流流量控制和引用跟踪.

辅助函数 (Helper Functions)

# 使用指定的前缀和长度编码整数
encodeInteger(buffer, prefix, value, prefixLength)

# 编码带有可选静态或动态名称索引的动态表插入指令（但不能同时有两者）
encodeInsert(buffer, staticNameIndex, dynamicNameIndex, fieldLine)

# 编码静态索引引用
encodeStaticIndexReference(buffer, staticIndex)

# 编码相对于 Base 的动态索引引用
encodeDynamicIndexReference(buffer, dynamicIndex, base)

# 编码带有可选静态名称索引的字面量
encodeLiteral(buffer, staticNameIndex, fieldLine)

# 编码带有相对于 Base 的动态名称索引的字面量
encodeDynamicLiteral(buffer, dynamicNameIndex, base, fieldLine)

编码算法 (Encoding Algorithm)

base = dynamicTable.getInsertCount()
requiredInsertCount = 0

for line in fieldLines:
    staticIndex = staticTable.findIndex(line)
    if staticIndex is not None:
        encodeStaticIndexReference(streamBuffer, staticIndex)
        continue

    dynamicIndex = dynamicTable.findIndex(line)
    if dynamicIndex is None:
        # 没有匹配的条目. 要么插入+索引, 要么编码字面量
        staticNameIndex = staticTable.findName(line.name)
        if staticNameIndex is None:
            dynamicNameIndex = dynamicTable.findName(line.name)

        if shouldIndex(line) and dynamicTable.canIndex(line):
            encodeInsert(encoderBuffer, staticNameIndex,
                        dynamicNameIndex, line)
            dynamicIndex = dynamicTable.add(line)

    if dynamicIndex is None:
        # 无法索引它, 使用字面量
        if dynamicNameIndex is not None:
            # 编码带有动态名称的字面量, 可能在 Base 之上
            encodeDynamicLiteral(streamBuffer, dynamicNameIndex,
                                base, line)
            requiredInsertCount = max(requiredInsertCount,
                                    dynamicNameIndex)
        else:
            # 编码带有静态名称或字面名称的字面量
            encodeLiteral(streamBuffer, staticNameIndex, line)
    else:
        # 动态索引引用
        assert(dynamicIndex is not None)
        requiredInsertCount = max(requiredInsertCount, dynamicIndex)
        # 编码 dynamicIndex, 可能在 Base 之上
        encodeDynamicIndexReference(streamBuffer, dynamicIndex, base)

# 编码前缀
if requiredInsertCount == 0:
    encodeInteger(prefixBuffer, 0x00, 0, 8)
    encodeInteger(prefixBuffer, 0x00, 0, 7)
else:
    wireRIC = (
        requiredInsertCount
        % (2 * getMaxEntries(maxTableCapacity))
    ) + 1
    encodeInteger(prefixBuffer, 0x00, wireRIC, 8)
    if base >= requiredInsertCount:
        encodeInteger(prefixBuffer, 0x00,
                    base - requiredInsertCount, 7)
    else:
        encodeInteger(prefixBuffer, 0x80,
                    requiredInsertCount - base - 1, 7)

return encoderBuffer, prefixBuffer + streamBuffer

算法说明

此算法演示了单遍编码器的核心逻辑:

1. 初始化: 将 Base 设置为当前插入计数, 将 requiredInsertCount 初始化为 0.

2. 遍历字段行: 对每个字段行:

   • 首先尝试在静态表中查找完全匹配
   • 如果未找到, 在动态表中查找
   • 如果两者都未找到, 决定是插入新条目还是使用字面量

3. 决策逻辑:

   • 完全匹配: 直接引用（静态或动态）
   • 无匹配: 根据策略决定是否插入到动态表
   • 仅名称匹配: 使用带名称引用的字面量

4. 前缀编码: 根据 requiredInsertCount 和 Base 的值编码字段区段前缀.

5. 输出: 返回编码器流缓冲区和已编码字段区段（前缀 + 字段行表示）.

关键点

• 单遍处理: 算法在遍历字段行时同时做出编码和插入决策
• Base 跟踪: 使用插入计数作为 Base, 允许 Post-Base 索引
• 灵活策略: shouldIndex() 函数封装了索引策略, 可根据实现需求调整
• 引用计数: requiredInsertCount 跟踪需要的最大动态表状态

---