Primitives

#3.1 Unsigned varints (LEB128)

Lengths in the pack format (§12) and the integer fields inside binary CIDs (§4) are unsigned LEB128 varints — the multiformats "unsigned varint" (§2.5), under this format's strictness:

• The value is emitted 7 bits at a time, least-significant group first.
• Each byte carries 7 value bits; the high bit is set on every byte except the last.

Encoding MUST be minimal, and decoding MUST be strict:

• A decoder MUST reject a varint whose final (most-significant) byte is 0x00, unless the entire varint is the single byte 0x00 (the value 0). (Equivalently: no redundant trailing zero groups.)
• A decoder MUST reject varints longer than 8 bytes and values above 2^53 − 1 (§2.3; 2^53 − 1 itself encodes in exactly 8 bytes).
• A decoder MUST reject truncated input (a byte with the high bit set at end of input) — except that an incremental parser treats it as "need more input" (§12.4). Note that minimality and the value bound are only decidable once the final byte arrives; an incremental parser MUST NOT reject a prefix early on their account.

#3.2 Base32

The text encoding of binary identifiers — the payload of the multibase base32lower ref string form (§4) and the multihash-derived block keys (§10.1) — is RFC 4648 base32, with:

• alphabet abcdefghijklmnopqrstuvwxyz234567 (lowercase),
• no padding characters.

Encoding: process input bits most-significant first, emitting one alphabet character per 5 bits; a final partial group is left-shifted to 5 bits with zero bits.

Decoding MUST be canonical:

• Characters outside the alphabet (including uppercase) MUST be rejected.
• String lengths ≡ 1, 3, or 6 (mod 8) MUST be rejected (no byte length produces them).
• Non-zero padding bits in the final character MUST be rejected (e.g. "74" decodes to 0xff; "75" is invalid).

(Multibase specifies base32 decoding as case-insensitive; this format's decoders are deliberately stricter — the canonical lowercase form is the only accepted one, §4.)

#3.3 Name order (compareNames)

Directory entry names and page-index first-names are ordered by plain bytewise (memcmp) comparison of their UTF-8 encodings, with a shorter string that is a prefix of a longer one ordering first.

This is NOT the CBOR map-key order (§5.2), which sorts by length first. The two orders disagree (e.g. "b" < "aa" in CBOR key order, but "aa" < "b" in name order). Directory structures MUST use name order; CBOR maps MUST use key order.

Name identity is the UTF-8 byte sequence, not any host-language string identity. Two host strings that encode to the same bytes are the same name.

#3.4 Hash function

• The hash function is a multihash function: it is named by its entry in the multicodec registry (§2.5) and self-described by every ref that carries it (§4). The default is SHA2-256 — registry name sha2-256, code 0x12, 32-byte output.
• The hash function is a per-store parameter. Its output length MUST be in [20, 64] bytes (a bound of this format; multihash itself imposes none) and MUST be fixed for the lifetime of a store. Refs self-describe their hash function, but one store = one hash: every ref in a store MUST carry the store's function (§10.3), and a well-formed ref carrying any other MUST be rejected in that store's context (§4). Mixing hash functions in one store namespace is not supported.
• The identity multihash (code 0x00) is not a hash function and MUST NOT be used (§4).
• The hash of a block is the hash of its exact stored bytes. For file content, the hash input is always the uncompressed, unencoded chunk bytes.