Appendix C. Sample Single-Pass Encoding Algorithm

Pseudocode for single-pass encoding, excluding handling of duplicates, non-blocking mode, available encoder stream flow control, and reference tracking.

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

This algorithm demonstrates the core logic of a single-pass encoder:

1. Initialization: Set Base to the current insert count, initialize requiredInsertCount to 0.

2. Iterate Field Lines: For each field line:

   • First try to find a complete match in the static table
   • If not found, search in the dynamic table
   • If neither found, decide whether to insert a new entry or use a literal

3. Decision Logic:

   • Complete Match: Direct reference (static or dynamic)
   • No Match: Decide whether to insert into dynamic table based on policy
   • Name-Only Match: Use literal with name reference

4. Prefix Encoding: Encode the field section prefix based on requiredInsertCount and Base values.

5. Output: Return encoder stream buffer and encoded field section (prefix + field line representations).

Key Points

• Single-Pass Processing: Algorithm makes encoding and insertion decisions while iterating through field lines
• Base Tracking: Uses insert count as Base, allowing Post-Base indexing
• Flexible Strategy: shouldIndex() function encapsulates indexing strategy, adjustable per implementation needs
• Reference Counting: requiredInsertCount tracks maximum dynamic table state required

---