nx_cdc_gate.nx source
↩ module page · 157 lines · 9289 B
1// nx_cdc_gate.nx -- IN-PROCESS gate over nx_cdc_lib (/compare/dataio DI5 cp_cdc_gear): content-defined chunking must
2// (1) partition the input within its declared bounds, (2) be deterministic, (3) survive an INSERTION with almost every
3// chunk digest intact while the fixed-size CONTROL loses almost every chunk after the edit -- that pair is the whole
4// claim, and neither half alone proves it -- and (4) refuse parameters that are not a chunking. The corpus is a
5// pseudo-random 1 MiB buffer from a seeded xorshift generator (no file, no clock), the parameters are the ones
6// nx_content_put derives from its wire chunk (48,402 -> max 48402, avg 24201, min 6050).
7// exit: 0 GREEN / 1 RED (gv_verdict law).
8import "nx_syscalls.nx"
9import "nx_gate_verdict.nx"
10import "nx_sha256.nx"
11import "nx_cdc_lib.nx"
12
13const CG_N: i64 = 1048576
14const CG_SEED: i64 = 88172645463325252
15const CG_MAX: i64 = 48402
16const CG_AVG: i64 = 24201
17const CG_MIN: i64 = 6050
18const CG_CAP: i64 = 4096 // plan table slots: 1 MiB / min 6050 = 174 chunks at most; 4096 is headroom, and the refusal on overflow is tested
19const CG_INS_AT: i64 = 100000
20const CG_INS_LEN: i64 = 37
21const CG_TOL: i64 = 3 // chunks that may legitimately re-key around one insertion: the one cut and its two neighbours
22// KNOWN ANSWER for the seeded corpus under strict-then-loose normalization. This is a KAT, not a bar: the gear is
23// sha256-derived and T9 proves determinism, so the count is a property of the ALGORITHM (mask order, bit counts, gear).
24// MEASURED 2026-09-05 by nx_gate_bite: a mutant that disabled the strict-mask phase (loose-only chunking) SURVIVED every
25// statistical tooth -- its mean still sat within 2x of avg and its plan still partitioned -- so only an exact count
26// separates normalized chunking from plain gear chunking. Change this number KNOWINGLY, with the algorithm.
27const CG_KAT_CHUNKS: i64 = 43
28
29// xorshift64: deterministic pseudo-random bytes
30func cg_fill(buf: *u8, n: i64, seed: i64) -> i64 {
31 var x: i64 = seed
32 var i: i64 = 0
33 while i < n {
34 x = x ^ (x * 8192)
35 x = x ^ (x / 128)
36 x = x ^ (x * 131072)
37 var v: i64 = x
38 if v < 0 { v = 0 - v }
39 buf[i] = (v % 256) as u8
40 i = i + 1
41 }
42 return n
43}
44func cg_digests(buf: *u8, offs: *i64, count: i64, out: *u8) -> i64 {
45 var k: i64 = 0
46 while k < count { cdc_chunk_digest(buf, offs, k, ((out as i64) + k * CDC_DIGEST_B) as *u8); k = k + 1 }
47 return count
48}
49
50func main() -> i64 {
51 let ctr: *i64 = gv_ctr()
52 gv_head("nx_cdc_gate -- content-defined chunking: bounded partition, deterministic, insertion-resilient against the fixed-size control" as *u8)
53 let tbl: *u8 = sys_mmap(CDC_GEAR_BYTES)
54 gv_check_eq("T1 the gear table has 256 entries" as *u8, cdc_gear_table(tbl), CDC_GEAR_N, ctr)
55 // T2 KAT of the derivation: gear[0] is the first 8 bytes of sha256("nx-cdc-gear-v1" || 0x00), recomputed here
56 let msg: *u8 = sys_mmap(32)
57 var sl: i64 = 0
58 while CDC_SEED[sl] != (0 as u8) { msg[sl] = CDC_SEED[sl]; sl = sl + 1 }
59 msg[sl] = 0 as u8
60 let dg: *u8 = sys_mmap(32)
61 sha256_digest(msg, sl + 1, dg)
62 var want0: i64 = 0
63 var j: i64 = 0
64 while j < 8 { want0 = want0 * 256 + (dg[j] as i64); j = j + 1 }
65 gv_check_eq("T2 gear[0] is derived from the named seed and the byte value (recomputed independently here)" as *u8, cdc_gear_at(tbl, 0), want0, ctr)
66 var distinct: i64 = 1
67 var a: i64 = 0
68 while a < CDC_GEAR_N {
69 var b: i64 = a + 1
70 while b < CDC_GEAR_N { if cdc_gear_at(tbl, a) == cdc_gear_at(tbl, b) { distinct = 0 } b = b + 1 }
71 a = a + 1
72 }
73 gv_check("T3 all 256 gear entries are distinct" as *u8, distinct, ctr)
74 gv_check_eq("T4 the average mask tests floor(log2(avg)) bits: 24201 -> 14" as *u8, cdc_mask_bits(CG_AVG), 14, ctr)
75 gv_check_eq("T4b a 3-bit mask is 7" as *u8, cdc_mask(3), 7, ctr)
76
77 // ---- the corpus and its plan ----
78 let buf: *u8 = sys_mmap(CG_N + CG_INS_LEN + 64)
79 cg_fill(buf, CG_N, CG_SEED)
80 let offs: *i64 = sys_mmap(CG_CAP * 8) as *i64
81 let count: i64 = cdc_plan(tbl, buf, CG_N, CG_MIN, CG_AVG, CG_MAX, offs, CG_CAP)
82 gv_kv("chunks" as *u8, count)
83 gv_check("T5 the plan yields at least one chunk over 1 MiB" as *u8, (count > 0) as i64, ctr)
84 var partition: i64 = 1
85 var bounded: i64 = 1
86 var k: i64 = 0
87 var minlen: i64 = CG_N
88 var maxlen: i64 = 0
89 if offs[0] != 0 { partition = 0 }
90 while k < count {
91 let l: i64 = offs[k + 1] - offs[k]
92 if l <= 0 { partition = 0 }
93 if l < minlen { minlen = l }
94 if l > maxlen { maxlen = l }
95 if l > CG_MAX { bounded = 0 }
96 if k + 1 < count { if l < CG_MIN { bounded = 0 } }
97 k = k + 1
98 }
99 if offs[count] != CG_N { partition = 0 }
100 gv_kv("min_len" as *u8, minlen)
101 gv_kv("max_len" as *u8, maxlen)
102 gv_kv("mean_len" as *u8, CG_N / count)
103 gv_check("T6 the plan is a PARTITION: starts at 0, strictly increasing, ends at n" as *u8, partition, ctr)
104 gv_check("T7 every chunk but the last is at least min and none exceeds max (max = the wire chunk, so every chunk still fits one call)" as *u8, bounded, ctr)
105 var meanok: i64 = 0
106 let mean: i64 = CG_N / count
107 if mean >= CG_AVG / 2 { if mean <= CG_AVG * 2 { meanok = 1 } }
108 gv_check("T8 the mean chunk length lies within a factor of two of the requested average (normalized chunking works on random bytes)" as *u8, meanok, ctr)
109 let offs2: *i64 = sys_mmap(CG_CAP * 8) as *i64
110 let count2: i64 = cdc_plan(tbl, buf, CG_N, CG_MIN, CG_AVG, CG_MAX, offs2, CG_CAP)
111 var same: i64 = 1
112 if count2 != count { same = 0 } else { k = 0; while k <= count { if offs[k] != offs2[k] { same = 0 } k = k + 1 } }
113 gv_check("T9 the plan is DETERMINISTIC: a second pass reproduces every boundary" as *u8, same, ctr)
114 gv_check_eq("T17 KAT: the seeded 1 MiB corpus chunks into exactly 43 pieces under strict-then-loose normalization (a loose-only or strict-only chunker moves this number -- the bite-surviving mutant class; change it knowingly, with the algorithm)" as *u8, count, CG_KAT_CHUNKS, ctr)
115
116 // ---- insertion resilience versus the fixed-size control ----
117 let buf2: *u8 = sys_mmap(CG_N + CG_INS_LEN + 64)
118 var i: i64 = 0
119 while i < CG_INS_AT { buf2[i] = buf[i]; i = i + 1 }
120 var q: i64 = 0
121 while q < CG_INS_LEN { buf2[CG_INS_AT + q] = (65 + (q % 26)) as u8; q = q + 1 }
122 i = CG_INS_AT
123 while i < CG_N { buf2[i + CG_INS_LEN] = buf[i]; i = i + 1 }
124 let n2: i64 = CG_N + CG_INS_LEN
125 let offs3: *i64 = sys_mmap(CG_CAP * 8) as *i64
126 let count3: i64 = cdc_plan(tbl, buf2, n2, CG_MIN, CG_AVG, CG_MAX, offs3, CG_CAP)
127 let d1: *u8 = sys_mmap(CG_CAP * CDC_DIGEST_B)
128 let d3: *u8 = sys_mmap(CG_CAP * CDC_DIGEST_B)
129 cg_digests(buf, offs, count, d1)
130 cg_digests(buf2, offs3, count3, d3)
131 let shared_cdc: i64 = cdc_shared_digests(d1, count, d3, count3)
132 gv_kv("cdc_chunks_after_insert" as *u8, count3)
133 gv_kv("cdc_shared_digests" as *u8, shared_cdc)
134 gv_check("T10 after a 37-byte insertion at 100000, all but at most 3 content-defined chunk digests survive (the boundaries re-align within one chunk)" as *u8, (shared_cdc + CG_TOL >= count) as i64, ctr)
135 // the CONTROL: fixed-size chunks of the same maximum
136 let offf1: *i64 = sys_mmap(CG_CAP * 8) as *i64
137 let offf2: *i64 = sys_mmap(CG_CAP * 8) as *i64
138 let cf1: i64 = cdc_plan_fixed(CG_N, CG_MAX, offf1, CG_CAP)
139 let cf2: i64 = cdc_plan_fixed(n2, CG_MAX, offf2, CG_CAP)
140 let df1: *u8 = sys_mmap(CG_CAP * CDC_DIGEST_B)
141 let df2: *u8 = sys_mmap(CG_CAP * CDC_DIGEST_B)
142 cg_digests(buf, offf1, cf1, df1)
143 cg_digests(buf2, offf2, cf2, df2)
144 let shared_fixed: i64 = cdc_shared_digests(df1, cf1, df2, cf2)
145 gv_kv("fixed_chunks" as *u8, cf1)
146 gv_kv("fixed_shared_digests" as *u8, shared_fixed)
147 // only the chunks wholly BEFORE the insertion can survive fixed-size chunking: floor(100000 / 48402) = 2
148 gv_check("neg-control-T11 the fixed-size control keeps only the chunks before the insertion (at most 2 of 22): every later chunk re-keys" as *u8, (shared_fixed <= CG_INS_AT / CG_MAX) as i64, ctr)
149 gv_check("T12 content-defined beats fixed-size on the same edit by construction: strictly more shared digests" as *u8, (shared_cdc > shared_fixed) as i64, ctr)
150
151 // ---- refusals ----
152 gv_check_eq("neg-control-T13 an average below the mask floor is refused (-1), never chunked by guess" as *u8, cdc_plan(tbl, buf, CG_N, 2, 8, 16, offs2, CG_CAP), CDC_ERR, ctr)
153 gv_check_eq("neg-control-T14 avg <= min is refused" as *u8, cdc_plan(tbl, buf, CG_N, 8192, 4096, 65536, offs2, CG_CAP), CDC_ERR, ctr)
154 gv_check_eq("neg-control-T15 a plan table too small for the chunks is refused, never truncated" as *u8, cdc_plan(tbl, buf, CG_N, CG_MIN, CG_AVG, CG_MAX, offs2, 4), CDC_ERR, ctr)
155 gv_check_eq("T16 a tail shorter than min becomes the final chunk (a 100-byte input is one chunk)" as *u8, cdc_plan(tbl, buf, 100, CG_MIN, CG_AVG, CG_MAX, offs2, CG_CAP), 1, ctr)
156 return gv_verdict("nx_cdc_gate" as *u8, ctr, "content-defined chunking partitions within bounds, reproduces itself, survives an insertion where the fixed-size control does not, and refuses non-chunkings" as *u8)
157}