4 == Checksums and object IDs
6 In a repository using the traditional SHA-1, pack checksums, index checksums,
7 and object IDs (object names) mentioned below are all computed using SHA-1.
8 Similarly, in SHA-256 repositories, these values are computed using SHA-256.
10 == pack-*.pack files have the following format:
12 - A header appears at the beginning and consists of the following:
15 The signature is: {'P', 'A', 'C', 'K'}
17 4-byte version number (network byte order):
18 Git currently accepts version number 2 or 3 but
19 generates version 2 only.
21 4-byte number of objects contained in the pack (network byte order)
23 Observation: we cannot have more than 4G versions ;-) and
24 more than 4G objects in a pack.
26 - The header is followed by number of object entries, each of
27 which looks like this:
29 (undeltified representation)
30 n-byte type and length (3-bit type, (n-1)*7+4-bit length)
33 (deltified representation)
34 n-byte type and length (3-bit type, (n-1)*7+4-bit length)
35 base object name if OBJ_REF_DELTA or a negative relative
36 offset from the delta object's position in the pack if this
37 is an OBJ_OFS_DELTA object
40 Observation: length of each object is encoded in a variable
41 length format and is not constrained to 32-bit or anything.
43 - The trailer records a pack checksum of all of the above.
47 Valid object types are:
56 Type 5 is reserved for future expansion. Type 0 is invalid.
60 This document uses the following "size encoding" of non-negative
61 integers: From each byte, the seven least significant bits are
62 used to form the resulting integer. As long as the most significant
63 bit is 1, this process continues; the byte with MSB 0 provides the
64 last seven bits. The seven-bit chunks are concatenated. Later
65 values are more significant.
67 This size encoding should not be confused with the "offset encoding",
68 which is also used in this document.
70 === Deltified representation
72 Conceptually there are only four object types: commit, tree, tag and
73 blob. However to save space, an object could be stored as a "delta" of
74 another "base" object. These representations are assigned new types
75 ofs-delta and ref-delta, which is only valid in a pack file.
77 Both ofs-delta and ref-delta store the "delta" to be applied to
78 another object (called 'base object') to reconstruct the object. The
79 difference between them is, ref-delta directly encodes base object
80 name. If the base object is in the same pack, ofs-delta encodes
81 the offset of the base object in the pack instead.
83 The base object could also be deltified if it's in the same pack.
84 Ref-delta can also refer to an object outside the pack (i.e. the
85 so-called "thin pack"). When stored on disk however, the pack should
86 be self contained to avoid cyclic dependency.
88 The delta data starts with the size of the base object and the
89 size of the object to be reconstructed. These sizes are
90 encoded using the size encoding from above. The remainder of
91 the delta data is a sequence of instructions to reconstruct the object
92 from the base object. If the base object is deltified, it must be
93 converted to canonical form first. Each instruction appends more and
94 more data to the target object until it's complete. There are two
95 supported instructions so far: one for copy a byte range from the
96 source object and one for inserting new data embedded in the
99 Each instruction has variable length. Instruction type is determined
100 by the seventh bit of the first octet. The following diagrams follow
101 the convention in RFC 1951 (Deflate compressed data format).
103 ==== Instruction to copy from base object
105 +----------+---------+---------+---------+---------+-------+-------+-------+
106 | 1xxxxxxx | offset1 | offset2 | offset3 | offset4 | size1 | size2 | size3 |
107 +----------+---------+---------+---------+---------+-------+-------+-------+
109 This is the instruction format to copy a byte range from the source
110 object. It encodes the offset to copy from and the number of bytes to
111 copy. Offset and size are in little-endian order.
113 All offset and size bytes are optional. This is to reduce the
114 instruction size when encoding small offsets or sizes. The first seven
115 bits in the first octet determines which of the next seven octets is
116 present. If bit zero is set, offset1 is present. If bit one is set
117 offset2 is present and so on.
119 Note that a more compact instruction does not change offset and size
120 encoding. For example, if only offset2 is omitted like below, offset3
121 still contains bits 16-23. It does not become offset2 and contains
122 bits 8-15 even if it's right next to offset1.
124 +----------+---------+---------+
125 | 10000101 | offset1 | offset3 |
126 +----------+---------+---------+
128 In its most compact form, this instruction only takes up one byte
129 (0x80) with both offset and size omitted, which will have default
130 values zero. There is another exception: size zero is automatically
131 converted to 0x10000.
133 ==== Instruction to add new data
135 +----------+============+
137 +----------+============+
139 This is the instruction to construct target object without the base
140 object. The following data is appended to the target object. The first
141 seven bits of the first octet determines the size of data in
142 bytes. The size must be non-zero.
144 ==== Reserved instruction
146 +----------+============
148 +----------+============
150 This is the instruction reserved for future expansion.
152 == Original (version 1) pack-*.idx files have the following format:
154 - The header consists of 256 4-byte network byte order
155 integers. N-th entry of this table records the number of
156 objects in the corresponding pack, the first byte of whose
157 object name is less than or equal to N. This is called the
158 'first-level fan-out' table.
160 - The header is followed by sorted 24-byte entries, one entry
161 per object in the pack. Each entry is:
163 4-byte network byte order integer, recording where the
164 object is stored in the packfile as the offset from the
167 one object name of the appropriate size.
169 - The file is concluded with a trailer:
171 A copy of the pack checksum at the end of the corresponding
174 Index checksum of all of the above.
178 -- +--------------------------------+
179 fanout | fanout[0] = 2 (for example) |-.
180 table +--------------------------------+ |
182 +--------------------------------+ |
184 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
185 | fanout[255] = total objects |---.
186 -- +--------------------------------+ | |
188 index | object name 00XXXXXXXXXXXXXXXX | | |
189 table +--------------------------------+ | |
191 | object name 00XXXXXXXXXXXXXXXX | | |
192 +--------------------------------+<+ |
194 | | object name 01XXXXXXXXXXXXXXXX | |
195 | +--------------------------------+ |
197 | | object name 01XXXXXXXXXXXXXXXX | |
198 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
200 | | object name FFXXXXXXXXXXXXXXXX | |
201 --| +--------------------------------+<--+
202 trailer | | packfile checksum |
203 | +--------------------------------+
204 | | idxfile checksum |
205 | +--------------------------------+
210 packed object header:
211 1-byte size extension bit (MSB)
214 n-byte sizeN (as long as MSB is set, each 7-bit)
215 size0..sizeN form 4+7+7+..+7 bit integer, size0
216 is the least significant part, and sizeN is the
217 most significant part.
219 If it is not DELTA, then deflated bytes (the size above
220 is the size before compression).
221 If it is REF_DELTA, then
222 base object name (the size above is the
223 size of the delta data that follows).
224 delta data, deflated.
225 If it is OFS_DELTA, then
226 n-byte offset (see below) interpreted as a negative
227 offset from the type-byte of the header of the
228 ofs-delta entry (the size above is the size of
229 the delta data that follows).
230 delta data, deflated.
233 n bytes with MSB set in all but the last one.
234 The offset is then the number constructed by
235 concatenating the lower 7 bit of each byte, and
236 for n >= 2 adding 2^7 + 2^14 + ... + 2^(7*(n-1))
241 == Version 2 pack-*.idx files support packs larger than 4 GiB, and
242 have some other reorganizations. They have the format:
244 - A 4-byte magic number '\377tOc' which is an unreasonable
247 - A 4-byte version number (= 2)
249 - A 256-entry fan-out table just like v1.
251 - A table of sorted object names. These are packed together
252 without offset values to reduce the cache footprint of the
253 binary search for a specific object name.
255 - A table of 4-byte CRC32 values of the packed object data.
256 This is new in v2 so compressed data can be copied directly
257 from pack to pack during repacking without undetected
260 - A table of 4-byte offset values (in network byte order).
261 These are usually 31-bit pack file offsets, but large
262 offsets are encoded as an index into the next table with
265 - A table of 8-byte offset entries (empty for pack files less
266 than 2 GiB). Pack files are organized with heavily used
267 objects toward the front, so most object references should
268 not need to refer to this table.
270 - The same trailer as a v1 pack file:
272 A copy of the pack checksum at the end of
273 corresponding packfile.
275 Index checksum of all of the above.
277 == pack-*.rev files have the format:
279 - A 4-byte magic number '0x52494458' ('RIDX').
281 - A 4-byte version identifier (= 1).
283 - A 4-byte hash function identifier (= 1 for SHA-1, 2 for SHA-256).
285 - A table of index positions (one per packed object, num_objects in
286 total, each a 4-byte unsigned integer in network order), sorted by
287 their corresponding offsets in the packfile.
289 - A trailer, containing a:
291 checksum of the corresponding packfile, and
293 a checksum of all of the above.
295 All 4-byte numbers are in network order.
297 == pack-*.mtimes files have the format:
299 All 4-byte numbers are in network byte order.
301 - A 4-byte magic number '0x4d544d45' ('MTME').
303 - A 4-byte version identifier (= 1).
305 - A 4-byte hash function identifier (= 1 for SHA-1, 2 for SHA-256).
307 - A table of 4-byte unsigned integers. The ith value is the
308 modification time (mtime) of the ith object in the corresponding
309 pack by lexicographic (index) order. The mtimes count standard
312 - A trailer, containing a checksum of the corresponding packfile,
313 and a checksum of all of the above (each having length according
314 to the specified hash function).
316 == multi-pack-index (MIDX) files have the following format:
318 The multi-pack-index files refer to multiple pack-files and loose objects.
320 In order to allow extensions that add extra data to the MIDX, we organize
321 the body into "chunks" and provide a lookup table at the beginning of the
322 body. The header includes certain length values, such as the number of packs,
323 the number of base MIDX files, hash lengths and types.
325 All 4-byte numbers are in network order.
330 The signature is: {'M', 'I', 'D', 'X'}
332 1-byte version number:
333 Git only writes or recognizes version 1.
335 1-byte Object Id Version
336 We infer the length of object IDs (OIDs) from this value:
339 If the hash type does not match the repository's hash algorithm,
340 the multi-pack-index file should be ignored with a warning
341 presented to the user.
343 1-byte number of "chunks"
345 1-byte number of base multi-pack-index files:
346 This value is currently always zero.
348 4-byte number of pack files
352 (C + 1) * 12 bytes providing the chunk offsets:
353 First 4 bytes describe chunk id. Value 0 is a terminating label.
354 Other 8 bytes provide offset in current file for chunk to start.
355 (Chunks are provided in file-order, so you can infer the length
356 using the next chunk position if necessary.)
358 The CHUNK LOOKUP matches the table of contents from
359 link:technical/chunk-format.html[the chunk-based file format].
361 The remaining data in the body is described one chunk at a time, and
362 these chunks may be given in any order. Chunks are required unless
367 Packfile Names (ID: {'P', 'N', 'A', 'M'})
368 Stores the packfile names as concatenated, null-terminated strings.
369 Packfiles must be listed in lexicographic order for fast lookups by
370 name. This is the only chunk not guaranteed to be a multiple of four
371 bytes in length, so should be the last chunk for alignment reasons.
373 OID Fanout (ID: {'O', 'I', 'D', 'F'})
374 The ith entry, F[i], stores the number of OIDs with first
375 byte at most i. Thus F[255] stores the total
378 OID Lookup (ID: {'O', 'I', 'D', 'L'})
379 The OIDs for all objects in the MIDX are stored in lexicographic
382 Object Offsets (ID: {'O', 'O', 'F', 'F'})
383 Stores two 4-byte values for every object.
384 1: The pack-int-id for the pack storing this object.
385 2: The offset within the pack.
386 If all offsets are less than 2^32, then the large offset chunk
387 will not exist and offsets are stored as in IDX v1.
388 If there is at least one offset value larger than 2^32-1, then
389 the large offset chunk must exist, and offsets larger than
390 2^31-1 must be stored in it instead. If the large offset chunk
391 exists and the 31st bit is on, then removing that bit reveals
392 the row in the large offsets containing the 8-byte offset of
395 [Optional] Object Large Offsets (ID: {'L', 'O', 'F', 'F'})
396 8-byte offsets into large packfiles.
398 [Optional] Bitmap pack order (ID: {'R', 'I', 'D', 'X'})
399 A list of MIDX positions (one per object in the MIDX, num_objects in
400 total, each a 4-byte unsigned integer in network byte order), sorted
401 according to their relative bitmap/pseudo-pack positions.
405 Index checksum of the above contents.
407 == multi-pack-index reverse indexes
409 Similar to the pack-based reverse index, the multi-pack index can also
410 be used to generate a reverse index.
412 Instead of mapping between offset, pack-, and index position, this
413 reverse index maps between an object's position within the MIDX, and
414 that object's position within a pseudo-pack that the MIDX describes
415 (i.e., the ith entry of the multi-pack reverse index holds the MIDX
416 position of ith object in pseudo-pack order).
418 To clarify the difference between these orderings, consider a multi-pack
419 reachability bitmap (which does not yet exist, but is what we are
420 building towards here). Each bit needs to correspond to an object in the
421 MIDX, and so we need an efficient mapping from bit position to MIDX
424 One solution is to let bits occupy the same position in the oid-sorted
425 index stored by the MIDX. But because oids are effectively random, their
426 resulting reachability bitmaps would have no locality, and thus compress
427 poorly. (This is the reason that single-pack bitmaps use the pack
428 ordering, and not the .idx ordering, for the same purpose.)
430 So we'd like to define an ordering for the whole MIDX based around
431 pack ordering, which has far better locality (and thus compresses more
432 efficiently). We can think of a pseudo-pack created by the concatenation
433 of all of the packs in the MIDX. E.g., if we had a MIDX with three packs
434 (a, b, c), with 10, 15, and 20 objects respectively, we can imagine an
435 ordering of the objects like:
437 |a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19|
439 where the ordering of the packs is defined by the MIDX's pack list,
440 and then the ordering of objects within each pack is the same as the
441 order in the actual packfile.
443 Given the list of packs and their counts of objects, you can
444 naïvely reconstruct that pseudo-pack ordering (e.g., the object at
445 position 27 must be (c,1) because packs "a" and "b" consumed 25 of the
446 slots). But there's a catch. Objects may be duplicated between packs, in
447 which case the MIDX only stores one pointer to the object (and thus we'd
448 want only one slot in the bitmap).
450 Callers could handle duplicates themselves by reading objects in order
451 of their bit-position, but that's linear in the number of objects, and
452 much too expensive for ordinary bitmap lookups. Building a reverse index
453 solves this, since it is the logical inverse of the index, and that
454 index has already removed duplicates. But, building a reverse index on
455 the fly can be expensive. Since we already have an on-disk format for
456 pack-based reverse indexes, let's reuse it for the MIDX's pseudo-pack,
459 Objects from the MIDX are ordered as follows to string together the
460 pseudo-pack. Let `pack(o)` return the pack from which `o` was selected
461 by the MIDX, and define an ordering of packs based on their numeric ID
462 (as stored by the MIDX). Let `offset(o)` return the object offset of `o`
463 within `pack(o)`. Then, compare `o1` and `o2` as follows:
465 - If one of `pack(o1)` and `pack(o2)` is preferred and the other
466 is not, then the preferred one sorts first.
468 (This is a detail that allows the MIDX bitmap to determine which
469 pack should be used by the pack-reuse mechanism, since it can ask
470 the MIDX for the pack containing the object at bit position 0).
472 - If `pack(o1) ≠ pack(o2)`, then sort the two objects in descending
473 order based on the pack ID.
475 - Otherwise, `pack(o1) = pack(o2)`, and the objects are sorted in
476 pack-order (i.e., `o1` sorts ahead of `o2` exactly when `offset(o1)
479 In short, a MIDX's pseudo-pack is the de-duplicated concatenation of
480 objects in packs stored by the MIDX, laid out in pack order, and the
481 packs arranged in MIDX order (with the preferred pack coming first).
483 The MIDX's reverse index is stored in the optional 'RIDX' chunk within