Merge branch 'lt/tree-2'
[git/git.git] / Documentation / technical / pack-format.txt
1 GIT pack format
2 ===============
3
4 = pack-*.pack file has the following format:
5
6 - The header appears at the beginning and consists of the following:
7
8 4-byte signature:
9 The signature is: {'P', 'A', 'C', 'K'}
10
11 4-byte version number (network byte order):
12 GIT currently accepts version number 2 or 3 but
13 generates version 2 only.
14
15 4-byte number of objects contained in the pack (network byte order)
16
17 Observation: we cannot have more than 4G versions ;-) and
18 more than 4G objects in a pack.
19
20 - The header is followed by number of object entries, each of
21 which looks like this:
22
23 (undeltified representation)
24 n-byte type and length (4-bit type, (n-1)*7+4-bit length)
25 compressed data
26
27 (deltified representation)
28 n-byte type and length (4-bit type, (n-1)*7+4-bit length)
29 20-byte base object name
30 compressed delta data
31
32 Observation: length of each object is encoded in a variable
33 length format and is not constrained to 32-bit or anything.
34
35 - The trailer records 20-byte SHA1 checksum of all of the above.
36
37 = pack-*.idx file has the following format:
38
39 - The header consists of 256 4-byte network byte order
40 integers. N-th entry of this table records the number of
41 objects in the corresponding pack, the first byte of whose
42 object name are smaller than N. This is called the
43 'first-level fan-out' table.
44
45 Observation: we would need to extend this to an array of
46 8-byte integers to go beyond 4G objects per pack, but it is
47 not strictly necessary.
48
49 - The header is followed by sorted 24-byte entries, one entry
50 per object in the pack. Each entry is:
51
52 4-byte network byte order integer, recording where the
53 object is stored in the packfile as the offset from the
54 beginning.
55
56 20-byte object name.
57
58 Observation: we would definitely need to extend this to
59 8-byte integer plus 20-byte object name to handle a packfile
60 that is larger than 4GB.
61
62 - The file is concluded with a trailer:
63
64 A copy of the 20-byte SHA1 checksum at the end of
65 corresponding packfile.
66
67 20-byte SHA1-checksum of all of the above.
68
69 Pack Idx file:
70
71 idx
72 +--------------------------------+
73 | fanout[0] = 2 |-.
74 +--------------------------------+ |
75 | fanout[1] | |
76 +--------------------------------+ |
77 | fanout[2] | |
78 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
79 | fanout[255] | |
80 +--------------------------------+ |
81 main | offset | |
82 index | object name 00XXXXXXXXXXXXXXXX | |
83 table +--------------------------------+ |
84 | offset | |
85 | object name 00XXXXXXXXXXXXXXXX | |
86 +--------------------------------+ |
87 .-| offset |<+
88 | | object name 01XXXXXXXXXXXXXXXX |
89 | +--------------------------------+
90 | | offset |
91 | | object name 01XXXXXXXXXXXXXXXX |
92 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
93 | | offset |
94 | | object name FFXXXXXXXXXXXXXXXX |
95 | +--------------------------------+
96 trailer | | packfile checksum |
97 | +--------------------------------+
98 | | idxfile checksum |
99 | +--------------------------------+
100 .-------.
101 |
102 Pack file entry: <+
103
104 packed object header:
105 1-byte type (upper 4-bit)
106 size0 (lower 4-bit)
107 n-byte sizeN (as long as MSB is set, each 7-bit)
108 size0..sizeN form 4+7+7+..+7 bit integer, size0
109 is the most significant part.
110 packed object data:
111 If it is not DELTA, then deflated bytes (the size above
112 is the size before compression).
113 If it is DELTA, then
114 20-byte base object name SHA1 (the size above is the
115 size of the delta data that follows).
116 delta data, deflated.