1GIT bitmap v1 format 2==================== 3 4 - A header appears at the beginning: 5 6 4-byte signature: {'B', 'I', 'T', 'M'} 7 8 2-byte version number (network byte order) 9 The current implementation only supports version 1 10 of the bitmap index (the same one as JGit). 11 12 2-byte flags (network byte order) 13 14 The following flags are supported: 15 16 - BITMAP_OPT_FULL_DAG (0x1) REQUIRED 17 This flag must always be present. It implies that the bitmap 18 index has been generated for a packfile with full closure 19 (i.e. where every single object in the packfile can find 20 its parent links inside the same packfile). This is a 21 requirement for the bitmap index format, also present in JGit, 22 that greatly reduces the complexity of the implementation. 23 24 4-byte entry count (network byte order) 25 26 The total count of entries (bitmapped commits) in this bitmap index. 27 28 20-byte checksum 29 30 The SHA1 checksum of the pack this bitmap index belongs to. 31 32 - 4 EWAH bitmaps that act as type indexes 33 34 Type indexes are serialized after the hash cache in the shape 35 of four EWAH bitmaps stored consecutively (see Appendix A for 36 the serialization format of an EWAH bitmap). 37 38 There is a bitmap for each Git object type, stored in the following 39 order: 40 41 - Commits 42 - Trees 43 - Blobs 44 - Tags 45 46 In each bitmap, the `n`th bit is set to true if the `n`th object 47 in the packfile is of that type. 48 49 The obvious consequence is that the OR of all 4 bitmaps will result 50 in a full set (all bits set), and the AND of all 4 bitmaps will 51 result in an empty bitmap (no bits set). 52 53 - N entries with compressed bitmaps, one for each indexed commit 54 55 Where `N` is the total amount of entries in this bitmap index. 56 Each entry contains the following: 57 58 - 4-byte object position (network byte order) 59 The position **in the index for the packfile** where the 60 bitmap for this commit is found. 61 62 - 1-byte XOR-offset 63 The xor offset used to compress this bitmap. For an entry 64 in position `x`, a XOR offset of `y` means that the actual 65 bitmap representing this commit is composed by XORing the 66 bitmap for this entry with the bitmap in entry `x-y` (i.e. 67 the bitmap `y` entries before this one). 68 69 Note that this compression can be recursive. In order to 70 XOR this entry with a previous one, the previous entry needs 71 to be decompressed first, and so on. 72 73 The hard-limit for this offset is 160 (an entry can only be 74 xor'ed against one of the 160 entries preceding it). This 75 number is always positive, and hence entries are always xor'ed 76 with **previous** bitmaps, not bitmaps that will come afterwards 77 in the index. 78 79 - 1-byte flags for this bitmap 80 At the moment the only available flag is `0x1`, which hints 81 that this bitmap can be re-used when rebuilding bitmap indexes 82 for the repository. 83 84 - The compressed bitmap itself, see Appendix A. 85 86== Appendix A: Serialization format for an EWAH bitmap 87 88Ewah bitmaps are serialized in the same protocol as the JAVAEWAH 89library, making them backwards compatible with the JGit 90implementation: 91 92 - 4-byte number of bits of the resulting UNCOMPRESSED bitmap 93 94 - 4-byte number of words of the COMPRESSED bitmap, when stored 95 96 - N x 8-byte words, as specified by the previous field 97 98 This is the actual content of the compressed bitmap. 99 100 - 4-byte position of the current RLW for the compressed 101 bitmap 102 103All words are stored in network byte order for their corresponding 104sizes. 105 106The compressed bitmap is stored in a form of run-length encoding, as 107follows. It consists of a concatenation of an arbitrary number of 108chunks. Each chunk consists of one or more 64-bit words 109 110 H L_1 L_2 L_3 .... L_M 111 112H is called RLW (run length word). It consists of (from lower to higher 113order bits): 114 115 - 1 bit: the repeated bit B 116 117 - 32 bits: repetition count K (unsigned) 118 119 - 31 bits: literal word count M (unsigned) 120 121The bitstream represented by the above chunk is then: 122 123 - K repetitions of B 124 125 - The bits stored in `L_1` through `L_M`. Within a word, bits at 126 lower order come earlier in the stream than those at higher 127 order. 128 129The next word after `L_M` (if any) must again be a RLW, for the next 130chunk. For efficient appending to the bitstream, the EWAH stores a 131pointer to the last RLW in the stream.