Debian Codegraph @

plumbing/format/idxfile/doc.go

raw
1 // Package idxfile implements encoding and decoding of packfile idx files.
2 //
3 // == Original (version 1) pack-*.idx files have the following format:
4 //
5 // - The header consists of 256 4-byte network byte order
6 // integers. N-th entry of this table records the number of
7 // objects in the corresponding pack, the first byte of whose
8 // object name is less than or equal to N. This is called the
9 // 'first-level fan-out' table.
10 //
11 // - The header is followed by sorted 24-byte entries, one entry
12 // per object in the pack. Each entry is:
13 //
14 // 4-byte network byte order integer, recording where the
15 // object is stored in the packfile as the offset from the
16 // beginning.
17 //
18 // 20-byte object name.
19 //
20 // - The file is concluded with a trailer:
21 //
22 // A copy of the 20-byte SHA1 checksum at the end of
23 // corresponding packfile.
24 //
25 // 20-byte SHA1-checksum of all of the above.
26 //
27 // Pack Idx file:
28 //
29 // -- +--------------------------------+
30 // fanout | fanout[0] = 2 (for example) |-.
31 // table +--------------------------------+ |
32 // | fanout[1] | |
33 // +--------------------------------+ |
34 // | fanout[2] | |
35 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
36 // | fanout[255] = total objects |---.
37 // -- +--------------------------------+ | |
38 // main | offset | | |
39 // index | object name 00XXXXXXXXXXXXXXXX | | |
40 // tab +--------------------------------+ | |
41 // | offset | | |
42 // | object name 00XXXXXXXXXXXXXXXX | | |
43 // +--------------------------------+<+ |
44 // .-| offset | |
45 // | | object name 01XXXXXXXXXXXXXXXX | |
46 // | +--------------------------------+ |
47 // | | offset | |
48 // | | object name 01XXXXXXXXXXXXXXXX | |
49 // | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
50 // | | offset | |
51 // | | object name FFXXXXXXXXXXXXXXXX | |
52 // --| +--------------------------------+<--+
53 // trailer | | packfile checksum |
54 // | +--------------------------------+
55 // | | idxfile checksum |
56 // | +--------------------------------+
57 // .---------.
58 // |
59 // Pack file entry: <+
60 //
61 // packed object header:
62 // 1-byte size extension bit (MSB)
63 // type (next 3 bit)
64 // size0 (lower 4-bit)
65 // n-byte sizeN (as long as MSB is set, each 7-bit)
66 // size0..sizeN form 4+7+7+..+7 bit integer, size0
67 // is the least significant part, and sizeN is the
68 // most significant part.
69 // packed object data:
70 // If it is not DELTA, then deflated bytes (the size above
71 // is the size before compression).
72 // If it is REF_DELTA, then
73 // 20-byte base object name SHA1 (the size above is the
74 // size of the delta data that follows).
75 // delta data, deflated.
76 // If it is OFS_DELTA, then
77 // n-byte offset (see below) interpreted as a negative
78 // offset from the type-byte of the header of the
79 // ofs-delta entry (the size above is the size of
80 // the delta data that follows).
81 // delta data, deflated.
82 //
83 // offset encoding:
84 // n bytes with MSB set in all but the last one.
85 // The offset is then the number constructed by
86 // concatenating the lower 7 bit of each byte, and
87 // for n >= 2 adding 2^7 + 2^14 + ... + 2^(7*(n-1))
88 // to the result.
89 //
90 // == Version 2 pack-*.idx files support packs larger than 4 GiB, and
91 // have some other reorganizations. They have the format:
92 //
93 // - A 4-byte magic number '\377tOc' which is an unreasonable
94 // fanout[0] value.
95 //
96 // - A 4-byte version number (= 2)
97 //
98 // - A 256-entry fan-out table just like v1.
99 //
100 // - A table of sorted 20-byte SHA1 object names. These are
101 // packed together without offset values to reduce the cache
102 // footprint of the binary search for a specific object name.
103 //
104 // - A table of 4-byte CRC32 values of the packed object data.
105 // This is new in v2 so compressed data can be copied directly
106 // from pack to pack during repacking without undetected
107 // data corruption.
108 //
109 // - A table of 4-byte offset values (in network byte order).
110 // These are usually 31-bit pack file offsets, but large
111 // offsets are encoded as an index into the next table with
112 // the msbit set.
113 //
114 // - A table of 8-byte offset entries (empty for pack files less
115 // than 2 GiB). Pack files are organized with heavily used
116 // objects toward the front, so most object references should
117 // not need to refer to this table.
118 //
119 // - The same trailer as a v1 pack file:
120 //
121 // A copy of the 20-byte SHA1 checksum at the end of
122 // corresponding packfile.
123 //
124 // 20-byte SHA1-checksum of all of the above.
125 //
126 // Source:
127 // https://www.kernel.org/pub/software/scm/git/docs/v1.7.5/technical/pack-format.txt
128 package idxfile