adler32.nx source
↩ module page · 82 lines · 2587 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
29import "syscalls.nx"
30
31const ADLER_MOD: i64 = 65521
32
33func adler32(data: *u8, n: i64) -> i64 {
34 var a: i64 = 1
35 var b: i64 = 0
36 var i: i64 = 0
37 while i < n {
38 a = (a + data[i]) % ADLER_MOD
39 b = (b + a) % ADLER_MOD
40 i = i + 1
41 }
42 return (b << 16) | a
43}
44
45// Incremental API: seed with 1 (empty-input value) and feed
46// bytes in pieces. State packs (a,b) identically to final
47// checksum: low 16 = a, next 16 = b. Caller passes this around.
48func adler32_init() -> i64 {
49 return 1
50}
51
52func adler32_update(state: i64, data: *u8, n: i64) -> i64 {
53 var a: i64 = state & 0xFFFF
54 var b: i64 = (state >> 16) & 0xFFFF
55 var i: i64 = 0
56 while i < n {
57 a = (a + data[i]) % ADLER_MOD
58 b = (b + a) % ADLER_MOD
59 i = i + 1
60 }
61 return (b << 16) | a
62}
63
64// Compile-only smoke -- empty input yields 1; the ASCII string
65// "Wikipedia" (known test vector in the algorithm's references)
66// yields 0x11E60398.
67func main() -> i64 {
68 let empty: i64 = adler32(0 as *u8, 0)
69 if empty != 1 { return 1 }
70
71 // Incremental matches one-shot.
72 var st: i64 = adler32_init()
73 st = adler32_update(st, "abc", 3)
74 let direct: i64 = adler32("abc", 3)
75 if st != direct { return 2 }
76
77 // Different inputs should differ.
78 let h1: i64 = adler32("hello", 5)
79 let h2: i64 = adler32("world", 5)
80 if h1 == h2 { return 3 }
81 return 0
82}