Module oid_index 

__gunnar_oid__ — the reserved oid index.

A raw (non-Arrow) section holding an stree keyspace over the first eight bytes of every object id, plus, per entry, the full oid, the first lookup row of that object’s chunk run, and its object ordinal.

Why stree and not the stock fst trie

Git oids are fixed-width and uniformly random, so they share no prefixes: an fst gets no prefix compression, still walks its automaton byte by byte, and has no batch path. stree (znippy-zoomies/src/stree.rs) is built for sorted fixed-width keys — one cache-line node, branchless AVX2 compare, and a software-pipelined batch traversal. Serving one git pack is thousands of lookups, so the batch path is the whole point.

The 8-byte prefix is NOT a key — it is a filter

Two distinct oids can share their first eight bytes. It is vanishingly unlikely and it is not impossible, so the key is treated as what it is: a filter that narrows to a short candidate run, after which the full oid is compared. lookup is only ever correct because of that comparison; GitOidIndex::candidate_run exposes the unverified run precisely so a test can prove the verify step is load-bearing rather than decoration.

Section layout (little-endian; keys are 8-byte aligned for stree)

  0  magic  b"ZNPYGOID"                8
  8  u32 version                       4
 12  u8  hash code (1=sha1, 2=sha256)  1
 13  u8  oid_len (20 or 32)            1
 14  u16 reserved (0)                  2
 16  u64 count                         8
 24  i64 keys   [count]                8*count   ← sorted ascending, the stree keyspace
     u64 rows   [count]                8*count   ← first lookup row of that oid
     u32 ords   [count]                4*count   ← object ordinal (oid-lexicographic)
     u8  oids   [count * oid_len]                ← full oid, for the verify step

The key is order-preserving, and the sign bit is why

i64::from_be_bytes(oid[..8]) — the literal reading of “the first eight bytes as an i64” — is not order-preserving over oid bytes: an oid whose first byte is 0x80 or higher goes negative and sorts before every oid starting 0x00..0x7f, which is roughly half the keyspace on the wrong side. The key here therefore flips the top bit, (u64::from_be_bytes(first8) ^ (1 << 63)) as i64, which maps unsigned order onto signed order exactly. Key rank is then oid-lexicographic rank.

…and the parallel arrays are still not redundant

With an order-preserving key it is tempting to drop both parallel arrays and read them off the rank. Only one of the two can go:

• ords equals the rank for every index crate::sections::GitIndexBuilder builds, because that is where the ordinal is defined and it numbers the same oid-lexicographic sequence. It is still stored, because build_section is the lower-level API and its contract does not require the caller’s ordinal to be a rank — the ordinal is the __gunnar_reach__ bitmap space, and a caller indexing a subset of a larger archive has ordinals from the larger space. Dropping the array is 4 bytes per object and a narrower contract; it is not free, and it is not done here.
• rows is not the rank and cannot become it. A lookup row is a chunk row: an object above file_split_block_size occupies several consecutive rows, and the lookup covers every path in the archive, not only git objects — an archive holding anything besides the object store has git rows that are not contiguous at all. rows is monotonic in rank and equal to it only in the special case of a single-chunk, git-only archive.

Structs

GitOidIndex

Reader over a __gunnar_oid__ section.

OidEntry

One object as the index records it.

OidHit

What a successful lookup resolved to.

Constants

GIT_OID_MAGIC

GIT_OID_VERSION

Bumped 1 → 2 when the key became order-preserving. A v1 section holds the same bytes in the same places but sorted on a different key, so a v2 reader walking it would return wrong rows rather than fail — which is why the reader below requires an exact match instead of <=.

Functions

build_section

Serialize the __gunnar_oid__ section. entries may be in any order; they are sorted by key here, which is what stree requires.

key_for_oid

The key an oid maps into: its first eight bytes as a big-endian unsigned integer, with the top bit flipped so that unsigned order becomes signed order.