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

以下是单遍编码的伪代码, 不包括重复项处理, 非阻塞模式, 可用 encoder stream 流量控制以及引用跟踪.

辅助函数 (Helper Functions)

# Encode an integer using the specified prefix and length
encodeInteger(buffer, prefix, value, prefixLength)

# Encode a dynamic table insertion instruction with optional static or dynamic name index (but not both)
encodeInsert(buffer, staticNameIndex, dynamicNameIndex, fieldLine)

# Encode a static index reference
encodeStaticIndexReference(buffer, staticIndex)

# Encode a dynamic index reference relative to Base
encodeDynamicIndexReference(buffer, dynamicIndex, base)

# Encode a literal with optional static name index
encodeLiteral(buffer, staticNameIndex, fieldLine)

# Encode a literal with dynamic name index relative to 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:
        # No matching entry. Either insert+index or encode literal
        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:
        # Cannot index it, use literal
        if dynamicNameIndex is not None:
            # Encode literal with dynamic name, possibly above Base
            encodeDynamicLiteral(streamBuffer, dynamicNameIndex,
                                base, line)
            requiredInsertCount = max(requiredInsertCount,
                                    dynamicNameIndex)
        else:
            # Encode literal with static name or literal name
            encodeLiteral(streamBuffer, staticNameIndex, line)
    else:
        # Dynamic index reference
        assert(dynamicIndex is not None)
        requiredInsertCount = max(requiredInsertCount, dynamicIndex)
        # Encode dynamicIndex, possibly above Base
        encodeDynamicIndexReference(streamBuffer, dynamicIndex, base)

# Encode prefix
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

算法说明 (Algorithm Explanation)

此算法展示了单遍 encoder 的核心逻辑:

1. 初始化: 将 Base 设为当前 insert count, 并将 requiredInsertCount 初始化为 0.

2. 遍历 Field Lines: 对每个 field line:

   • 首先尝试在 static table 中查找完整匹配
   • 如果未找到, 则在 dynamic table 中查找
   • 如果两者都未找到, 则决定是插入新条目还是使用 literal

3. 决策逻辑:

   • 完整匹配: 直接引用 (static 或 dynamic)
   • 无匹配: 根据策略决定是否插入 dynamic table
   • 仅名称匹配: 使用带名称引用的 literal

4. 前缀编码: 根据 requiredInsertCount 和 Base 的值编码 field section prefix.

5. 输出: 返回 encoder stream buffer 和已编码 field section (prefix + field line representations).

要点 (Key Points)

• 单遍处理: 算法在遍历 field line 时做出编码和插入决策
• Base 跟踪: 使用 insert count 作为 Base, 从而允许 Post-Base indexing
• 灵活策略: shouldIndex() 函数封装索引策略, 可按实现需求调整
• 引用计数: requiredInsertCount 跟踪所需的最大 dynamic table 状态

---