Pack and multi-pack bitmaps

ビットマップは、オブジェクトのセットに関する到達可能性情報をパックファイルまたはマルチパック インデックス (MIDX) に格納します。 前者の定義は明白であり、後者は MIDX に含まれるパック内のオブジェクトの結合として定義されます。

ビットマップは、1 つのパックまたはリポジトリのマルチパック インデックス (存在する場合) のいずれかに属します。 リポジトリには、最大で 1 つのビットマップを含めることができます。

オブジェクトは、ビットマップ内のビット位置によって一意に記述されます:

  • ビットマップがパックファイルに属している場合、n 番目のビットはパック順で n 番目のオブジェクトに対応します。 オブジェクトをパック内のバイト オフセットにマップする関数 offset の場合、パックの順序は以下のように定義されます: 

    o1 <= o2 <==> offset(o1) <= offset(o2)

  • ビットマップが MIDX に属する場合、n 番目のビットは MIDX 順で n 番目のオブジェクトに対応します。 オブジェクトを MIDX によって選択されたパックにマップする追加関数「pack」を使用すると、MIDX の順序は以下のように定義されます: 

    o1 <= o2 <==> pack(o1) <= pack(o2) /\ offset(o1) <= offset(o2)

    パック間の順序付けは、MIDX の .rev ファイルに従って行われます。 特に、優先パックは他のすべてのパックよりも先にソートされます。

ビットマップのディスク上の表現 (後述) は、そのビットマップがパックファイルまたは MIDX に属しているかどうかに関係なく同じです。 唯一の違いは、上記で説明したビットの解釈です。

特定のビットマップ拡張がサポートされています (付録 B を参照)。 パックファイルに対応するビットマップには拡張子は必要ありません。 MIDX に対応するビットマップの場合、bit-cache 拡張と rev-cache 拡張の両方が必要です。

On-disk format

ヘッダーから始まります:

  • 4バイト シグネチャ: {B, I, T, M}

  • 2バイト バージョン番号(ネットワークバイトオーダー)

    現在の実装では、ビットマップ インデックスのバージョン 1 のみがサポートされています(JGitも同一)。

  • 2バイト フラグ達 (ネットワークバイトオーダー)

    以下のフラグがサポートされています:

    • BITMAP_OPT_FULL_DAG (0x1) 必須

      このフラグは常に存在する必要があります。 これは、パックファイルまたはマルチパックインデックス (MIDX) のビットマップ インデックスが完全閉鎖(closure)(つまり、 パックファイル/MIDX 内のすべての単一オブジェクトが 同一 パックファイル/MIDX 内に親リンクを見つけることができる)で生成されたことを意味します。 これは、JGit にも存在するビットマップ インデックス形式の要件であり、実装の複雑さを大幅に軽減します。

    • BITMAP_OPT_HASH_CACHE (0x4)

      存在する場合、ビットマップ ファイルの末尾には、パック/MIDX 内のオブジェクトごとに 1 つの 32 ビットの名前ハッシュ値(Nとする)が含まれます。 name-hash の形式と意味については後述します。

  • 4バイト エントリ数(ネットワークバイトオーダー)

    このビットマップ インデックス内のエントリ(ビットマップ化したコミット)の総数。

  • 20バイト チェックサム

    このビットマップ インデックスが属する パック/MIDX の SHA1 チェックサム。

型インデックスとして機能する 4 つの EWAH ビットマップ

タイプ インデックスは、ハッシュ キャッシュの後ろに、連続して格納された 4 つの EWAH ビットマップの形でシリアル化されます (EWAH ビットマップのシリアル化形式については、付録 A を参照してください)。

Git オブジェクト タイプごとにビットマップがあり、以下の順序で格納されます:

  • Commits

  • Trees

  • Blobs

  • Tags

各ビットマップでは、パックファイルまたはマルチパック インデックスの n 番目のオブジェクトがそのタイプの場合、n 番目のビットが true に設定されます。

よって、 4 つのビットマップすべての OR はフル セット (すべてのビット セット) になり、4 つのビットマップすべての AND は空のビットマップ (ビット セットなし) になります。

インデックス付きコミットごとに 1 つずつの、圧縮されたビットマップを含む N エントリ

「N」は、このビットマップ インデックス内のエントリの合計量です。 各エントリには以下のものが含まれます:

  • 4バイト オブジェクト位置(ネットワークバイトオーダー)

    このコミットのビットマップが見つかった「パックファイルまたはマルチパックインデックス内」の位置。

  • 1バイト XORオフセット

    このビットマップの圧縮に使用される xor オフセット。 位置 x のエントリの場合、y という XOR オフセットは、このコミットを表す実際のビットマップが、エントリ x-y のビットマップ (つまり、このエントリより前のビットマップ y エントリ) との XOR によって構成されることを意味します。

    注意: この圧縮は再帰的に行うことができることに注意してください。 このエントリを前のエントリと XOR するには、前のエントリを最初に解凍する必要があります。

    このオフセットのハード リミットは 160 です (エントリは、その前の 160 エントリの 1 つに対してのみ xor できます)。 この数は常に正であるため、エントリは常に 前の ビットマップと xor 演算されます。後でインデックスに追加されるビットマップではありません。

  • 1バイト このビットマップのフラグ達

    現時点で使用可能なフラグは「0x1」のみです。これは、リポジトリのビットマップ インデックスを再構築するときに、このビットマップを再利用できることを示唆しています。

  • 圧縮されたビットマップ自体については、付録 A を参照してください。

付録 A: EWAH ビットマップのシリアル化形式

Ewah ビットマップは JAVAEWAH ライブラリと同じプロトコルでシリアル化されるため、JGit 実装と下位互換性があります。

  • 4バイト 結果の非圧縮ビットマップのビット数

  • 4バイト 保存時の「圧縮」ビットマップのワード数

  • N × 8バイト ワード。Nは前のフィールドで指定されたとおり

    これは、圧縮されたビットマップの実際の内容です。

  • 4バイト 圧縮されたビットマップの現在の RLW の位置

すべてのワードは、対応するサイズのネットワークバイトオーダーで格納されます。

圧縮されたビットマップは、以下のようにランレングス エンコーディングの形式で格納されます。 これは、任意の数のチャンクの連結で構成されます。 各チャンクは 1 つ以上の 64 ビット ワードで構成されます

H  L_1  L_2  L_3 .... L_M

H は RLW (run length word)と呼ばれる。 それは（下位ビットから上位ビットへの順番で)で構成されています:

  • 1 bit: 繰り返しビット B

  • 32 bits: 繰り返し回数 K (unsigned)

  • 31 bits: literal word count M (unsigned)

上記のチャンクで表されるビットストリームは以下のようになります:

  • B の K 回の繰り返し

  • L_1 〜 L_M に格納されているビット。 ワード内では、下位のビットが上位のビットよりもストリーム内で先に到着します。

L_M の後の次のワード (存在する場合) は、次のチャンクの RLW でなければなりません。 ビットストリームに効率的に追加するために、EWAH はストリーム内の最後の RLW へのポインターを格納します。

Appendix B: Optional Bitmap Sections

これらのセクションは、 .bitmap ファイルに存在する場合と存在しない場合があります。 それらの存在は、上記のヘッダー フラグ セクションによって示されます。

Name-hash cache

BITMAP_OPT_HASH_CACHE フラグが設定されている場合、ビットマップの末尾には、pack/MIDX 内のオブジェクトごとに 1 つずつ、32 ビット値のキャッシュが含まれます。 位置 i の値は、パック/MIDX 内の i 番目のオブジェクト (インデックスまたはマルチパック インデックス順でカウント) が見つかるパス名のハッシュです。 これをデルタ ヒューリスティックに入力して、同様のパス名を持つオブジェクトを比較できます。

使用されるハッシュ アルゴリズムは以下のとおりです:

hash = 0;
while ((c = *name++))
        if (!isspace(c))
                hash = (hash >> 2) + (c << 24);

注意: このハッシュ スキームは、BITMAP_OPT_HASH_CACHE フラグに関連付けられていることに注意してください。 実装が別のハッシュ スキームを選択する場合は、自由に選択できますが、新しいヘッダー フラグを割り当てなければなりません (2 つの異なるスキームで作成されたハッシュを比較しても意味がないため)。