Bitmaps store reachability information about the set of objects in a packfile,
or a multi-pack index (MIDX). The former is defined obviously, and the latter is
defined as the union of objects in packs contained in the MIDX.
A bitmap may belong to either one pack, or the repository’s multi-pack index (if
it exists). A repository may have at most one bitmap.
An object is uniquely described by its bit position within a bitmap:
-
If the bitmap belongs to a packfile, the nth bit corresponds to
the nth object in pack order. For a function offset which maps
objects to their byte offset within a pack, pack order is defined as
follows:
o1 <= o2 <==> offset(o1) <= offset(o2)
-
If the bitmap belongs to a MIDX, the nth bit corresponds to the
nth object in MIDX order. With an additional function pack which
maps objects to the pack they were selected from by the MIDX, MIDX order
is defined as follows:
o1 <= o2 <==> pack(o1) <= pack(o2) /\ offset(o1) <= offset(o2)
The ordering between packs is done according to the MIDX’s .rev file.
Notably, the preferred pack sorts ahead of all other packs.
The on-disk representation (described below) of a bitmap is the same regardless
of whether or not that bitmap belongs to a packfile or a MIDX. The only
difference is the interpretation of the bits, which is described above.
Certain bitmap extensions are supported (see: Appendix B). No extensions are
required for bitmaps corresponding to packfiles. For bitmaps that correspond to
MIDXs, both the bit-cache and rev-cache extensions are required.