メインコンテンツまでスキップ

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 は必要な最大動的テーブル状態を追跡します
に最終更新