| 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 |