nx_adler32.nx source
↩ module page · 88 lines · 2759 B
1// adler32.nx -- Adler-32 checksum (Mark Adler, zlib/gzip).
2//
3// 32-bit rolling checksum used inside zlib streams (RFC 1950)
4// and pigz / gzip integrity checks. Faster than CRC-32 at the
5// cost of worse collision resistance -- acceptable for short
6// frames, weak for megabyte-scale files.
7//
8// Algorithm:
9// a = 1; b = 0
10// for each byte x:
11// a = (a + x) mod 65521
12// b = (b + a) mod 65521
13// checksum = (b << 16) | a
14//
15// 65521 is the largest prime less than 2^16. The running
16// quantities a,b never exceed 2^32 if we reduce after every
17// NMAX = 5552 bytes (Adler's tuning so we can defer the modulo).
18// We do the naive per-byte modulo here; simplest; still trivially
19// beats a CRC table.
20//
21// Invariants:
22// A1 Empty input gives checksum = 1 (a=1, b=0).
23// A2 Output fits in a 32-bit unsigned; we return it in an i64
24// to avoid sign issues in downstream callers.
25// A3 adler32_combine not implemented (zlib has a closed-form
26// but it needs 64-bit modular arithmetic tricks -- future
27// commit if we need to concatenate streams).
28
29// nx_safety_envelope:
30// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
31// sil_target: SIL1
32// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
33// verdict: NOT_YET_EVALUATED
34
35import "nx_syscalls.nx"
36
37const ADLER_MOD: i64 = 65521
38
39func adler32(data: *u8, n: i64) -> i64 {
40 var a: i64 = 1
41 var b: i64 = 0
42 var i: i64 = 0
43 while i < n {
44 a = (a + data[i]) % ADLER_MOD
45 b = (b + a) % ADLER_MOD
46 i = i + 1
47 }
48 return (b << 16) | a
49}
50
51// Incremental API: seed with 1 (empty-input value) and feed
52// bytes in pieces. State packs (a,b) identically to final
53// checksum: low 16 = a, next 16 = b. Caller passes this around.
54func adler32_init() -> i64 {
55 return 1
56}
57
58func adler32_update(state: i64, data: *u8, n: i64) -> i64 {
59 var a: i64 = state & 0xFFFF
60 var b: i64 = (state >> 16) & 0xFFFF
61 var i: i64 = 0
62 while i < n {
63 a = (a + data[i]) % ADLER_MOD
64 b = (b + a) % ADLER_MOD
65 i = i + 1
66 }
67 return (b << 16) | a
68}
69
70// Compile-only smoke -- empty input yields 1; the ASCII string
71// "Wikipedia" (known test vector in the algorithm's references)
72// yields 0x11E60398.
73func main() -> i64 {
74 let empty: i64 = adler32(0 as *u8, 0)
75 if empty != 1 { return 1 }
76
77 // Incremental matches one-shot.
78 var st: i64 = adler32_init()
79 st = adler32_update(st, "abc", 3)
80 let direct: i64 = adler32("abc", 3)
81 if st != direct { return 2 }
82
83 // Different inputs should differ.
84 let h1: i64 = adler32("hello", 5)
85 let h2: i64 = adler32("world", 5)
86 if h1 == h2 { return 3 }
87 return 0
88}