Git pack format

Checksums and object IDs

従来のSHA-1を使用するリポジトリでは、以下で説明するパックチェックサム、インデックスチェックサム、およびオブジェクトID(オブジェクト名)はすべてSHA-1を使用して計算されます。同様に、SHA-256リポジトリでは、これらの値はSHA-256を使用して計算されます。

pack-*.pack files have the following format:

ヘッダーは最初にあらわれ、以下のもので構成されます

4-byte シグネチャ

The signature is: {P, A, C, K}

4-byte version number (network byte order)

Gitは現在バージョン番号2または3を受け入れますが、バージョン2のみを生成します。

4-byte パックに含まれるオブジェクトの数(network byte order)
所見: このバージョンでは、パック内のオブジェクトは4Gを超えることはできず、パックも4Gを超えることはできません。
ヘッダーの後には、オブジェクトエントリの数が続き、各エントリは以下のようになります

(非デルタ化表現)

n-byte type and length (type:3ビット幅、length: (n-1)*7+4 ビット幅)

圧縮データ

(デルタ化表現)

n-byte type and length (type:3ビット幅、length: (n-1)*7+4 ビット幅)

OBJ_REF_DELTAの場合はベースオブジェクト名、OBJ_OFS_DELTAオブジェクトの場合はパック内のデルタオブジェクトの位置からの負の相対オフセット

圧縮デルタデータ
所見: 各オブジェクトの長さは可変長形式でエンコードされ、32ビットなどに制限されません。
トレーラー(trailer)は、上記のすべてのパックチェックサムを記録します。

Object types

有効なオブジェクトタイプは以下のとおりです:

OBJ_COMMIT (1)
OBJ_TREE (2)
OBJ_BLOB (3)
OBJ_TAG (4)
OBJ_OFS_DELTA (6)
OBJ_REF_DELTA (7)

タイプ5は、将来の拡張用に予約されています。タイプ0は無効です。

Size encoding

このドキュメントでは、負でない整数で、「サイズエンコーディング」(size encoding)を使用します。つまりそれは、各バイトから、下位7ビットを使用して結果の整数を形成します。最上位ビットが1である限り、この処理は続行されます。 MSB 0 のバイトは、最後の7ビットを提供します。これら7ビットのチャンクは連結されます。後の値の方が上位です。

このサイズエンコーディング(size encoding)を、このドキュメントでも使用されている「オフセットエンコーディング」(offset encoding)と混同しないでください。

Deltified representation(デルタ化表現)

概念的には、commit、tree、tag、blobの4つのオブジェクトタイプしかありません。ただし、スペースを節約するために、オブジェクトを別の「ベース」(base)オブジェクトの「デルタ」(delta)として格納できます。これらの表現には、パックファイルでのみ有効な新しいタイプの ref-delta および ofs-delta が割り当てられます。

ofs-deltaとref-deltaはどちらも、オブジェクトを再構築するために別のオブジェクト(「ベースオブジェクト」と呼ばれる)に適用される「デルタ」を格納します。それらの違いは、ref-deltaがベースオブジェクト名を直接エンコードすることです。ベースオブジェクトが同じパックにある場合、ofs-deltaは代わりにパック内のベースオブジェクトのオフセットをエンコードします。

同一パックに含まれている場合は、ベースオブジェクトを削除することもできます。 ref-deltaは、パック外のオブジェクト(つまり、いわゆる「薄いパック」(thin pack)）を参照することもできます。ただし、ディスクに保存する場合は、循環依存を回避するためにパックを自己完結型にする必要があります。

デルタデータは、ベースオブジェクトのサイズと再構築されるオブジェクトのサイズから始まります。これらのサイズは、上記サイズエンコーディングを使用してエンコードされます。デルタデータの残りの部分は、ベースオブジェクトからオブジェクトを再構築するための一連の命令です。ベースオブジェクトが削除されている場合は、最初に標準形に変換する必要があります。各命令は、完了するまでターゲットオブジェクトにどんどんデータを追加します。現時点でサポートされている命令は2つあります。1つはソースオブジェクトからバイト範囲をコピーするためのもので、もう1つは命令自体に埋め込まれた新しいデータを挿入するためのものです。

各命令の長さは可変です。命令タイプは、最初のオクテット(訳注:1バイト(8ビット))のビット7(訳注:つまりこのバイトの最上位ビット)によって決定されます。以下の図は、RFC 1951（Deflate compressed data format;圧縮データ形式の解凍）の規則に従います。

ベースオブジェクトからのコピー命令

+----------+---------+---------+---------+---------+-------+-------+-------+
| 1xxxxxxx | offset1 | offset2 | offset3 | offset4 | size1 | size2 | size3 |
+----------+---------+---------+---------+---------+-------+-------+-------+

これは、ソースオブジェクトからバイト範囲をコピーするための命令です。コピー元のオフセットとコピーするバイト数をエンコードします。オフセットとサイズはリトルエンディアンです。

すべてのオフセットバイトとサイズバイトはオプションです。これは、小さなオフセットまたはサイズをエンコードするときに命令サイズを減らすためです。最初のオクテットの最初の7つのビット(訳注:bit6〜0)は、次の7つのオクテットのどれが存在するかを決定します。ビットゼロが設定されている場合、offset1が存在します。ビット1が設定されている場合、offset2が存在します。

注意: よりコンパクトな形式は、オフセットとサイズのエンコーディングを変更しないことに注意してください。たとえば、以下のようにoffset2のみが省略されている場合でも、offset3にはビット16〜23が含まれています。それはoffset1の隣に続くからoffset2という訳ではなくて、(offset3の)ビット8〜15が含まれています。

+----------+---------+---------+
| 10000101 | offset1 | offset3 |
+----------+---------+---------+

最もコンパクトな形式では、この命令はオフセットとサイズの両方が省略された1バイト(0x80)のみを使用し、デフォルト値はゼロになります。もうひとつ例外があります。サイズゼロは自動的に 0x10000 に変換されます。

新データ追加命令

+----------+============+
| 0xxxxxxx |    data    |
+----------+============+

これは、ベースオブジェクトなしでターゲットオブジェクトを構築するための命令です。続くデータがターゲットオブジェクトに追加されます。最初のオクテットの最初の7つのビット(訳注:bit6〜0)は、データのサイズをバイト単位で決定します。サイズはゼロ以外でなければなりません。

Reserved instruction

+----------+============
| 00000000 |
+----------+============

これは、将来の拡張のために予約されている命令です。

Original (version 1) pack-*.idx files have the following format:

ヘッダーは、256個の4バイトのネットワークバイトオーダー整数で構成されます。このテーブルのN番目のエントリは、対応するパック内のオブジェクトの数を記録します。オブジェクト名の最初のバイトはN以下です。これは、「first-level fan-out」テーブルと呼ばれます。
ヘッダーの後には、ソートされた24バイトのエントリが続きます(パック内のオブジェクトごとに1つのエントリ)。各エントリは以下のとおりです:
- 4-byte ネットワークバイトオーダー整数で、オブジェクトが格納されている場所をパックファイル先頭からのオフセットとして記録します。
- 適切なサイズの1つのオブジェクト名。
ファイルはトレーラーで締めくくられています:

対応するパックファイルの最後にあるパックチェックサムのコピー。
上記すべてのインデックスチェックサム。

パックIdxファイル:

        --  +--------------------------------+
fanout      | fanout[0] = 2 (for example)    |-.
table       +--------------------------------+ |
            | fanout[1]                      | |
            +--------------------------------+ |
            | fanout[2]                      | |
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
            | fanout[255] = total objects    |---.
        --  +--------------------------------+ | |
main        | offset                         | | |
index       | object name 00XXXXXXXXXXXXXXXX | | |
table       +--------------------------------+ | |
            | offset                         | | |
            | object name 00XXXXXXXXXXXXXXXX | | |
            +--------------------------------+<+ |
          .-| offset                         |   |
          | | object name 01XXXXXXXXXXXXXXXX |   |
          | +--------------------------------+   |
          | | offset                         |   |
          | | object name 01XXXXXXXXXXXXXXXX |   |
          | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~   |
          | | offset                         |   |
          | | object name FFXXXXXXXXXXXXXXXX |   |
        --| +--------------------------------+<--+
trailer   | | packfile checksum              |
          | +--------------------------------+
          | | idxfile checksum               |
          | +--------------------------------+
          .-------.
                  |
Pack file entry: <+

パックされたオブジェクトのヘッダー:

byte size extension bit (MSB)

type (next 3 bit)
size0 (lower 4-bit)
n-byte sizeN (MSBがセットされている限り。各7ビット) size0..sizeN form 4+7+7+..+7 ビット整数で、size0 は最も下位で、 sizeN が最も上位です。

パックされたオブジェクトのデータ

DELTAでない場合は、解凍されたバイト(上記のサイズは圧縮前のサイズです)。
REF_DELTAの場合、ベースオブジェクト名(上記サイズは後続のデルタデータのサイズです)。
圧縮されたデルタデータ。
OFS_DELTAの場合、nバイトオフセット(以下参照)は、ofs-deltaエントリのヘッダーのタイプバイトからの負のオフセットとして解釈されます(上記サイズは、後続のデルタデータのサイズです)。
圧縮されたデルタデータ。

offset encoding

最後の1つを除くすべてにMSBが設定されたnバイト。オフセットは、各バイトの下位7ビットを連結して作成された数値であり、n >= 2 の場合、結果に 2^7 + 2^14 + ... + 2^(7*(n-1)) を加算します。

バージョン2 pack-*.idx ファイルは4GiBより大きいパックをサポートし、他のいくつかの再編成があります。それらの形式は以下のとおりです:

4-byte マジックナンバー \377tOc は、 unreasonable fanout[0] 値です。
4-byte バージョン番号 (= 2)
v1と同様の256エントリのファンアウトテーブル。
ソートされたオブジェクト名のテーブル。これらはオフセット値なしで一緒にパックされ、特定のオブジェクト名のバイナリ検索のキャッシュフットプリント(cache footprint)を削減します。
パックされたオブジェクトデータの4バイトCRC32値のテーブル。これはv2の新機能で、再パック中に、未検出データ破損無しで圧縮データをパックからパックに直接コピーできます。
4バイトのオフセット値のテーブル(ネットワークバイトオーダー)。これらは通常31ビットパックファイルオフセットですが、ラージオフセットは、msbitが設定された次のテーブルへのインデックスとしてエンコードされます。
8バイトのオフセットエントリのテーブル(2 GiB未満のパックファイルの場合は空)。パックファイルは、頻繁に使用されるオブジェクトを手前に配置するように編成されているため、ほとんどのオブジェクト参照はこのテーブルを参照する必要はありません。
v1パックファイルと同一のトレーラー:

対応するパックファイルの最後にあるパックチェックサムのコピー。
上記すべてのインデックスチェックサム。

pack-*.rev ファイルは以下の形式です:

4-byte マジックナンバー 0x52494458 (RIDX).
4-byte バージョンID(= 1)。
4-byte ハッシュ機能ID(= 1:SHA-1, 2:SHA-256)。
インデックス位置のテーブル(パックされたオブジェクトごとに1つ、合計 num_objects、それぞれネットワークオーダーで4バイトの符号なし整数)。パックファイル内の対応するオフセットでソートされます。
トレーラーは、対応するパックファイルのチェックサムと、上記のすべてのチェックサムを含みます。

全ての 4-byte 数値はネットワークオーダーです。

multi-pack-index (MIDX) ファイルの形式は以下の通り:

multi-pack-indexファイルは、複数のパックファイル(pack-files)と緩いオブジェクト(loose objects)を参照します。

MIDXにデータを追加する拡張機能を使用できるようにするために、ボディを「チャンク」に編成し、ボディの先頭にルックアップテーブルを提供します。ヘッダーには、パックの数、ベースMIDXファイルの数、ハッシュの長さ、タイプなど、特定の長さ値達が含まれます。

全ての 4-byte 数値はネットワークオーダーです。

HEADER:

4-byte シグネチャ: The signature is: {M, I, D, X}
1-byte バージョン番号: Gitはバージョン 1 のみを書き込みまたは認識します。
1-byte オブジェクトIDバージョン(= 1: SHA-1, 2: SHA-256): この値からオブジェクトID(OID)の長さを推測します。ハッシュタイプがリポジトリのハッシュアルゴリズムと一致しない場合は、multi-pack-indexファイルを無視して、ユーザーに警告を表示する必要があります。
1-byte チャンクの数: チャンクの数
1-byte 「ベース multi-pack-index ファイル」の数: この値は現在のところ常にゼロです。
4-byte パックファアイルの数: パックファアイルの数

CHUNK LOOKUP:

(C + 1) * 12 bytes はチャンクオフセットを提供します

最初の4バイトはチャンクIDです。値 0 はラベル終端です。

他の8バイトは、現在のファイルでチャンクを開始するためのオフセットを提供します。(チャンクはファイル順に提供されるため、必要に応じて次のチャンク位置を使用して長さを推測できます。)
CHUNK LOOKUP は、 the chunk-based file format の「目次」(table of contents)と一致します。
ボディの残りのデータは一度に1つのチャンクで記述され、これらのチャンクは任意の順序で指定できます。特に指定がない限り、チャンクは必要です。

CHUNK DATA:

Packfile Names (ID: {P, N, A, M})

パックファイル名達を連結されたnullで終了する文字列として格納します。名前による高速ルックアップを行うには、パックファイルを辞書式順序でリストする必要があります。これは、長さが4バイトの倍数であることが保証されていない唯一のチャンクであるため、アライメント上の理由から最後のチャンクにする必要があります。

OID Fanout (ID: {O, I, D, F})

i番目のエントリF[i]は、最初のバイトが最大iのOIDの数を格納します。したがって、F[255]はオブジェクトの総数を格納します。

OID Lookup (ID: {O, I, D, L})

MIDX内のすべてのオブジェクトのOIDは、このチャンクに辞書式順序(lexicographic order)で格納されます。

Object Offsets (ID: {O, O, F, F})

オブジェクトごとに2つの4バイト値を格納します。

このオブジェクトを格納するパックの pack-int-id。
パック内のオフセット。すべてのオフセットが 2³²(2^32) 未満の場合、ラージオフセットチャンクは存在せず、オフセットは IDX v1 として保存されます。 2³²-1(2^32-1) より大きなオフセット値が少なくとも1つ存在する場合、ラージオフセットチャンクが存在しなければならず、代わりに 2³¹-1(2^31-1) より大きなオフセットがラージオフセットチャンクに格納されなければなりません。ラージオフセットチャンクが存在し、31番目のビットがオンの場合、そのビットを削除すると、このオブジェクトの8バイトオフセットを含むラージオフセットの行(row)が表示されます。

[オプション] Object Large Offsets (ID: {L, O, F, F})

8-byte 大きなパックファイル(large packfiles)へのオフセット。

TRAILER:

上記の内容のインデックスチェックサム。

multi-pack-index reverse indexes

パックベースのリバースインデックスと同様に、マルチパックインデックスを使用してリバースインデックスを生成することもできます。

この逆インデックスは、offset、pack-、index の位置の間でマッピングする代わりに、MIDX内のオブジェクトの位置と、MIDXが記述する疑似パック内のそのオブジェクトの位置の間でマッピングします(つまり、マルチパック逆インデックスのi番目のエントリは、i番目のオブジェクトのMIDX位置を疑似パック順に保持します)。

これらの順序の違いを明確にするために、マルチパック到達可能性ビットマップ(まだ存在していませんが、現在これを目指して開発中です)を検討してください。各ビットはMIDX内のオブジェクトに対応する必要があるため、ビット位置からMIDX位置への効率的なマッピングが必要です。

解決策の一つは、ビットがMIDXによって格納された、oidソートされたインデックスの同じ位置を占めるようにすることです。ただし、oidは事実上ランダムであるため、結果として得られる到達可能性ビットマップには局所性がなく、圧縮が不十分になります。 (これが、シングルパックビットマップが同じ目的で、 .idx順序ではなく、パック順序を使用する理由です。)

そのため、パックの順序に基づいてMIDX全体の順序を定義します。これにより、局所性が大幅に向上します（したがって、より効率的に圧縮されます）。 MIDX内のすべてのパックを連結して作成された疑似パックを考えることができます。たとえば、3つのパック（a、b、c）、それぞれ10、15、および20個のオブジェクトを含むMIDXがある場合、以下のようなオブジェクトの順序を想像できます:

|a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19|

ここで、パックの順序はMIDXのパックリストによって定義され、各パック内のオブジェクトの順序は実際のパックファイルでの順序と同じです。

パックのリストとオブジェクトの数を考えると、その疑似パックの順序を簡単に再構築できます(たとえば、パック「a」と「b」がスロットの25を消費したため、位置27のオブジェクトは（c、1）でなければなりません)。しかし、落とし穴があります。オブジェクトはパック間で複製される可能性があるのです。その場合、MIDXはオブジェクトへのポインターを1つだけ格納します(したがって、ビットマップに1つのスロットのみが必要です)。

呼び出し元は、ビット位置の順にオブジェクトを読み取ることで重複を処理できますが、オブジェクトの数は直線的であり、通常のビットマップルックアップにはコストがかかりすぎます。逆インデックスを作成すると、これが解決されます。これは、インデックスの論理的な逆であり、そのインデックスはすでに重複を削除しているためです。ただし、その場で逆インデックスを作成すると、コストがかかる可能性があります。パックベースの逆インデックス用のオンディスク形式がすでにあるので、MIDXの疑似パックにも再利用する事しましょう。

MIDXのオブジェクトは、疑似パックをつなぎ合わせるために次のように順序付けられます。 pack(o) がMIDXによって o が選択されたパックを返し、（MIDXによって保存された)数値IDに基づいてパックの順序を定義します。 offset(o) が pack(o) 内の o のオブジェクトオフセットを返すようにします。次に、o1 と` o2`を以下のように比較します:

pack(o1) と pack(o2) の一方が優先され、もう一方が優先されない場合、優先される方が最初にソートされます。

(詳細に言うと、これは、MIDXビットマップがビット位置0にあるオブジェクトを含むパックをMIDXに求めることができるので、パック再利用メカニズムによって使用されるべきパックを決定することを可能にします)。
pack(o1) ≠ pack(o2) の場合、パックIDに基づいて2つのオブジェクトを降順で並べ替えます。
それ以外の場合、 pack(o1) = pack(o2) であり、オブジェクトはパック順に並べ替えられます(つまり、 offset(o1) < offset(o2) の場合、o1 は o2 よりも先に並べ替えられます)。

要するに、MIDXの擬似パックは、MIDXによって保存されたパック内のオブジェクトをパック順に並べ、パックをMIDX順(優先パックが先に来る)に並べたものを重複排除して連結したものです。

注意: 最後に、MIDXの逆インデックスはマルチパックインデックス自体のチャンクとして保存されないことに注意してください。これは逆インデックスが属するパックやMIDXのチェックサムを含んでいるため、MIDXでの書き込みが不可能になるためです。 MIDXの書き換え時の競合を避けるために、MIDXの逆インデックスはそのファイル名にMIDXのチェックサムを含んでいます(例: multi-pack-index-xyz.rev)。