`nx_cdc_lib.nx` source

↩ module page · 172 lines · 7440 B
1// nx_cdc_lib.nx -- CONTENT-DEFINED CHUNKING (FastCDC gear, normalized) as a LIBRARY (/compare/dataio DI5, 2026-09-05).
2//
3// WHY: fixed-size chunking re-keys every chunk after an insertion, so a one-byte edit near the head of a 400 KB
4// artifact makes every following chunk "new" to a receiver that already holds the previous version -- the whole file
5// ships again. Content-defined boundaries (a rolling gear hash, cut where its low bits are zero) re-align within one
6// chunk of the edit, so only the touched region is new. This is the FastCDC shape (Xia et al., USENIX ATC 2016, the
7// dataio board's pinned reference): a 256-entry gear table, a one-shift-one-add rolling fingerprint, a minimum length
8// skipped outright, NORMALIZED chunking (a stricter mask before the average, a looser one after, so lengths cluster
9// around the average) and a hard maximum.
10//
11// EVERYTHING IS DERIVED, NOTHING TUNED. The gear table is SHA-256 of a NAMED seed and the byte value -- reproducible on
12// any host, so no table ships that could drift. The mask bit counts come from log2(avg). min, avg and max belong to the
13// CALLER: nx_content_put derives them from the ONE wire chunk constant it already owns (max = the wire chunk, so every
14// content-defined chunk still fits one call).
15//
16// HONESTY LIMITS, stated: the masks take the LOW bits of the fingerprint (the paper spreads the bits; the low-bit
17// variant is simpler and its statistics are PROVEN by nx_cdc_gate on a pseudo-random corpus rather than assumed). The
18// final chunk may be shorter than min. This lib never reads a file or the clock; it computes over a buffer.
19// license_tier: ORIGINAL   No hw writes (Rule 26).
20import "nx_syscalls.nx"
21import "nx_sha256.nx"
22
23const CDC_GEAR_N: i64 = 256
24const CDC_GEAR_W: i64 = 8                  // one i64 per gear entry
25const CDC_GEAR_BYTES: i64 = 2048           // CDC_GEAR_N x CDC_GEAR_W
26const CDC_SEED: *u8 = "nx-cdc-gear-v1" as *u8
27const CDC_DIGEST_B: i64 = 32
28const CDC_MIN_BITS: i64 = 4                // an average below 16 bytes has no meaningful mask: refused, never guessed
29const CDC_ERR: i64 = 0 - 1
30
31func cdc_slen(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } return n }
32
33// gear[i] = the first 8 bytes (big-endian) of sha256(seed || byte i), for i in 0..255. `out` holds CDC_GEAR_BYTES.
34func cdc_gear_table(out: *u8) -> i64 {
35    let sl: i64 = cdc_slen(CDC_SEED)
36    let msg: *u8 = sys_mmap(sl + 2)
37    var k: i64 = 0
38    while k < sl { msg[k] = CDC_SEED[k]; k = k + 1 }
39    let dg: *u8 = sys_mmap(CDC_DIGEST_B)
40    var i: i64 = 0
41    while i < CDC_GEAR_N {
42        msg[sl] = i as u8
43        sha256_digest(msg, sl + 1, dg)
44        var j: i64 = 0
45        while j < CDC_GEAR_W { out[i * CDC_GEAR_W + j] = dg[j]; j = j + 1 }
46        i = i + 1
47    }
48    return CDC_GEAR_N
49}
50// the gear value for byte b, assembled big-endian from the table
51func cdc_gear_at(tbl: *u8, b: i64) -> i64 {
52    var v: i64 = 0
53    var j: i64 = 0
54    while j < CDC_GEAR_W { v = v * 256 + (tbl[b * CDC_GEAR_W + j] as i64); j = j + 1 }
55    return v
56}
57// floor(log2(avg)): the number of fingerprint bits the AVERAGE mask tests
58func cdc_mask_bits(avg: i64) -> i64 { var b: i64 = 0; var v: i64 = avg; while v > 1 { v = v / 2; b = b + 1 } return b }
59// a mask of `bits` low ones (0 for bits <= 0); built by doubling so no shift operator semantics are assumed
60func cdc_mask(bits: i64) -> i64 {
61    if bits <= 0 { return 0 }
62    var m: i64 = 1
63    var i: i64 = 0
64    while i < bits { m = m * 2; i = i + 1 }
65    return m - 1
66}
67// THE CUT. Returns the END (exclusive) of the chunk that starts at `start`, in (start+min .. start+max] -- or n for a
68// tail shorter than min. Normalized: while shorter than avg the stricter mask (bits+1) must hit; after avg the looser
69// mask (bits-1) may hit; at max the cut is forced.
70func cdc_next_boundary(tbl: *u8, buf: *u8, n: i64, start: i64, min: i64, avg: i64, max: i64) -> i64 {
71    let remain: i64 = n - start
72    if remain <= min { return n }
73    var lim: i64 = max
74    if remain < max { lim = remain }
75    var normal: i64 = avg
76    if remain < avg { normal = remain }
77    let bits: i64 = cdc_mask_bits(avg)
78    let mask_s: i64 = cdc_mask(bits + 1)
79    let mask_l: i64 = cdc_mask(bits - 1)
80    var fp: i64 = 0
81    var i: i64 = min
82    var cut: i64 = 0 - 1
83    var go: i64 = 1
84    while go == 1 {
85        if i >= normal { go = 0 } else {
86            fp = fp * 2 + cdc_gear_at(tbl, buf[start + i] as i64)
87            if (fp & mask_s) == 0 { cut = start + i; go = 0 } else { i = i + 1 }
88        }
89    }
90    if cut >= 0 { return cut }
91    go = 1
92    while go == 1 {
93        if i >= lim { go = 0 } else {
94            fp = fp * 2 + cdc_gear_at(tbl, buf[start + i] as i64)
95            if (fp & mask_l) == 0 { cut = start + i; go = 0 } else { i = i + 1 }
96        }
97    }
98    if cut >= 0 { return cut }
99    return start + lim
100}
101// THE PLAN: offs[k] = start of chunk k for k in 0..count-1, offs[count] = n. Returns count, or CDC_ERR when the
102// parameters are not a chunking (min <= 0, avg <= min, max < avg, avg below the mask floor) or the table is too small.
103func cdc_plan(tbl: *u8, buf: *u8, n: i64, min: i64, avg: i64, max: i64, offs: *i64, cap: i64) -> i64 {
104    if min <= 0 { return CDC_ERR }
105    if avg <= min { return CDC_ERR }
106    if max < avg { return CDC_ERR }
107    if cdc_mask_bits(avg) < CDC_MIN_BITS { return CDC_ERR }
108    if cap < 2 { return CDC_ERR }
109    var k: i64 = 0
110    var pos: i64 = 0
111    var go: i64 = 1
112    var err: i64 = 0
113    while go == 1 {
114        if pos >= n { go = 0 } else {
115            if k + 1 >= cap { err = 1; go = 0 } else {
116                offs[k] = pos
117                pos = cdc_next_boundary(tbl, buf, n, pos, min, avg, max)
118                k = k + 1
119            }
120        }
121    }
122    if err == 1 { return CDC_ERR }
123    offs[k] = n
124    return k
125}
126// the CONTROL every content-defined claim is measured against: fixed-size chunks of `size`
127func cdc_plan_fixed(n: i64, size: i64, offs: *i64, cap: i64) -> i64 {
128    if size <= 0 { return CDC_ERR }
129    var k: i64 = 0
130    var pos: i64 = 0
131    var go: i64 = 1
132    var err: i64 = 0
133    while go == 1 {
134        if pos >= n { go = 0 } else {
135            if k + 1 >= cap { err = 1; go = 0 } else {
136                offs[k] = pos
137                pos = pos + size
138                if pos > n { pos = n }
139                k = k + 1
140            }
141        }
142    }
143    if err == 1 { return CDC_ERR }
144    offs[k] = n
145    return k
146}
147// the 32-byte digest of chunk k of a plan, into out (32 bytes)
148func cdc_chunk_digest(buf: *u8, offs: *i64, k: i64, out: *u8) -> i64 {
149    let a: i64 = offs[k]
150    let b: i64 = offs[k + 1]
151    sha256_digest(((buf as i64) + a) as *u8, b - a, out)
152    return b - a
153}
154// how many chunk digests of plan A (count na, digests da) also appear in plan B (count nb, digests db): the dedup
155// measure -- the bytes a receiver holding B would NOT need again for A
156func cdc_shared_digests(da: *u8, na: i64, db: *u8, nb: i64) -> i64 {
157    var shared: i64 = 0
158    var i: i64 = 0
159    while i < na {
160        var j: i64 = 0
161        var hit: i64 = 0
162        while j < nb {
163            var same: i64 = 1
164            var t: i64 = 0
165            while t < CDC_DIGEST_B { if da[i * CDC_DIGEST_B + t] != db[j * CDC_DIGEST_B + t] { same = 0; t = CDC_DIGEST_B } else { t = t + 1 } }
166            if same == 1 { hit = 1; j = nb } else { j = j + 1 }
167        }
168        shared = shared + hit
169        i = i + 1
170    }
171    return shared
172}
nx_cdc_lib.nx source

`nx_cdc_lib.nx` source
