File content

#9.1 Layout shapes

The number of chunks the chunker produces (contract in §9.2) determines the file layout. There are exactly three shapes:

Writer algorithm (normative — it is what makes output independent of input slicing):

• Run the chunker over the content. Skip zero-length chunks.

• Hold the first non-empty chunk until a second arrives or input ends.

• If input ends with exactly one non-empty chunk held:

  • length ≤ inlineThreshold (default 1024): emit an inline entry (d = the chunk, sz = its length). No block is written.
  • otherwise: store the chunk as one raw block; entry r = its raw-codec ref.

• If input ends with zero non-empty chunks: emit the empty-file entry (sz 0, neither d nor r).

• If a second chunk arrives: store all chunks as raw blocks, collect [length, ref] pairs in chunk order, and build a balanced tree of "f" nodes bottom-up:

  layer = the chunk pairs
  while length(layer) > maxChunkRefs:
      partition layer sequentially into groups of maxChunkRefs
          (the final group may be smaller)
      layer = [ putFileNode(group) for each group ]
  entry r = dag-cbor ref of putFileNode(layer) # the single root "f" node

  where putFileNode(pairs) stores {v:1, t:"f", sz: Σ sizes, c: pairs} and yields the pair [Σ sizes, dag-cbor ref]. Nested pairs thus carry the subtree's logical size. maxChunkRefs defaults to 2048 (§14).

  A lone chunk never becomes a one-child tree (step 3 handles it), but interior one-pair "f" nodes MAY occur (e.g. 2049 chunks → groups of 2048 + 1).

• A chunker that yields no chunks at all (not even an empty one) is a contract violation and MUST be treated as an error, not as an empty file.

Reader validation (§13.2): for every fetched leaf, block length MUST equal the declared pair size (or entry sz for a single-chunk file); for every fetched "f" node, its sz MUST equal both the referencing pair's size (or the entry's sz at the top) and the sum of its own pairs; inline d length MUST equal sz. "f" node nesting deeper than 64 (MAX_DEPTH) MUST be rejected.

#9.2 Chunker contract

A chunker consumes a stream of input pieces and produces a stream of chunks such that:

• Concatenated chunks equal the concatenated input.
• At least one chunk is produced (a single empty chunk for empty input).
• Boundaries depend only on the content bytes, never on how the input was sliced into pieces (piece-slicing invariance).
• Produced chunks are stable, unaliased buffers: a producer reusing one input buffer between pieces MUST NOT corrupt already-produced chunks.

#9.3 Fixed-size chunker

fixedSize(size) (size ≥ 1): emit consecutive size-byte chunks; the final chunk carries the remainder (possibly the whole input when shorter than size; a single empty chunk for empty input).

#9.4 FastCDC chunker (default)

Content-defined chunking: cut points stick to content, so an edit re-chunks only its neighborhood and unchanged regions keep their chunk refs (and therefore dedupe across versions):

Bounds min, avg, max (defaults 8192 / 32768 / 98304): integers, 1 ≤ min ≤ avg ≤ max, avg a power of two in [16, 2^29] (the cut arithmetic is 32-bit). The bounds are parameters, recorded in the store metadata as chunkMin, chunkAvg, chunkMax (§14, §10.3).

The GEAR table is a fixed array of 256 unsigned 32-bit values, generated by splitmix32 from seed 0. All arithmetic below is modulo 2^32; ^ is XOR, >> is a logical (zero-fill) right shift:

s = 0
for i in 0 .. 255:
    s = (s + 0x9e3779b9) mod 2^32
    z = s
    z = (z ^ (z >> 16)) * 0x21f0aaad   mod 2^32
    z = (z ^ (z >> 15)) * 0x735a2d97   mod 2^32
    GEAR[i] = z ^ (z >> 15)

The GEAR table and the cut rule below are format constants: every chunk boundary — and therefore every ref of CDC-chunked content — depends on them. The bounds are not: they are parameters (§14). The first eight GEAR values are pinned in Appendix A.4.

Cut widths: with bits = log2(avg):

kS = bits + 2                   # strict, before the normal point
kL = bits − 2                   # relaxed, after it

The avg constraint (a power of two in [16, 2^29]) is exactly what guarantees 2 ≤ kL and kS ≤ 31.

Cut rule. Given a window buf of pending bytes (and knowing whether the input has ended), the next cut length is:

cut(buf):
    n = min(length(buf), max)
    if n ≤ min: return n                    # only reachable on final flush
    normal = min(avg, n)
    h = 0
    for i in min .. normal − 1:
        h = ((h << 1) + GEAR[buf[i]]) mod 2^32
        if (h >>> (32 − kS)) == 0: return i + 1
    for i in normal .. n − 1:
        h = ((h << 1) + GEAR[buf[i]]) mod 2^32
        if (h >>> (32 − kL)) == 0: return i + 1
    return n                                 # hit max, or end of data

Here >>> is a logical (zero-fill) right shift on the 32-bit value h, so the boundary test is "the top kS (resp. kL) bits of h are all zero" — equivalently h < 2^(32 − kS) (resp. h < 2^(32 − kL)).

The test is on the high bits, and this is load-bearing: under the recurrence, the low bits barely depend on the window (bit 0 of h is exactly bit 0 of GEAR[buf[i]]), so a low-bit test would collapse the shift-resistance CDC exists to provide. See Appendix B for the full argument and measurements.

Note the hash starts at zero at offset min; bytes before offset min never influence the cut (sub-minimum skipping).

Streaming discipline. A cut decision is only definitive when the window holds at least max bytes of lookahead, or the input has ended:

while pending ≥ max bytes:           # during input
    emit buf[0 .. cut(buf))
while pending > 0:                   # after input ends
    emit buf[0 .. cut(buf))
if nothing was emitted: emit one empty chunk

This is what guarantees piece-slicing invariance: a boundary is never declared while more input could still have moved it.