nx_crc32.nx source
↩ module page · 129 lines · 4306 B
1// nx_crc32.nx -- CRC-32 (IEEE 802.3, gzip / zlib / png polynomial).
2//
3// Used for: gzip integrity, png chunk checksums, ELF .gnu.hash
4// table consistency, network protocol framing checks.
5//
6// We use the standard reflected polynomial (0xEDB88320), seed
7// 0xFFFFFFFF, and final XOR 0xFFFFFFFF. Matches:
8// - zlib crc32()
9// - python binascii.crc32()
10// - tar/gzip/png/ethernet checksums
11//
12// The 256-entry lookup table approach is the textbook method --
13// 8 bits of input per iteration, ~1 GB/s on a modern CPU. We
14// build the table at runtime (no static initialisers in NishiLang
15// yet) and cache it in BSS so subsequent calls are O(n).
16//
17// Slice-by-N (faster) is deferred until we benchmark a real bottleneck.
18
19// nx_safety_envelope:
20// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
21// sil_target: SIL1
22// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
23// verdict: NOT_YET_EVALUATED
24
25import "syscalls.nx"
26
27// CRC-32 table (256 * 4 bytes). Lazy-init on first use; we keep
28// the pointer (via the cap field) in BSS.
29static NX_CRC32_TABLE_INIT: i64
30
31// We cache the table pointer here. Address 0 = uninitialised.
32static NX_CRC32_TABLE_PTR: i64
33
34const NX_CRC32_POLY: i64 = 0xEDB88320
35
36// Build the lookup table. Entry i = 8-bit reflected CRC of the
37// single byte i.
38func nx_crc32_init() -> i64 {
39 if NX_CRC32_TABLE_INIT == 1 { return 0 }
40 let raw: *u8 = sys_mmap(256 * 4)
41 let tab: *i64 = raw as *i64
42 var i: i64 = 0
43 while i < 256 {
44 var c: i64 = i
45 var k: i64 = 0
46 while k < 8 {
47 if (c & 1) == 1 { c = (c >> 1) ^ NX_CRC32_POLY }
48 else { c = c >> 1 }
49 k = k + 1
50 }
51 // Store one byte per i64 slot to avoid alignment issues with
52 // a packed table on this codegen.
53 let off: i64 = i * 4
54 raw[off] = c & 0xFF
55 raw[off + 1] = (c >> 8) & 0xFF
56 raw[off + 2] = (c >> 16) & 0xFF
57 raw[off + 3] = (c >> 24) & 0xFF
58 i = i + 1
59 }
60 NX_CRC32_TABLE_PTR = raw as i64
61 NX_CRC32_TABLE_INIT = 1
62 return 0
63}
64
65// Read one 32-bit table entry as i64.
66func nx_crc32_table_at(idx: i64) -> i64 {
67 let raw: *u8 = NX_CRC32_TABLE_PTR as *u8
68 let off: i64 = idx * 4
69 let b0: i64 = raw[off]
70 let b1: i64 = raw[off + 1]
71 let b2: i64 = raw[off + 2]
72 let b3: i64 = raw[off + 3]
73 return b0 | (b1 << 8) | (b2 << 16) | (b3 << 24)
74}
75
76// Update an in-progress CRC with `n` bytes from `data`.
77//
78// Caller passes the previous CRC (or 0 for a fresh start). The
79// returned value is suitable to feed back in for streaming
80// (multi-chunk) checksums. Apply nx_crc32_finish to get the
81// canonical final value.
82func nx_crc32_update(crc_in: i64, data: *u8, n: i64) -> i64 {
83 nx_crc32_init()
84 var crc: i64 = crc_in ^ 0xFFFFFFFF
85 var i: i64 = 0
86 while i < n {
87 let idx: i64 = (crc ^ data[i]) & 0xFF
88 crc = (crc >> 8) ^ nx_crc32_table_at(idx)
89 crc = crc & 0xFFFFFFFF
90 i = i + 1
91 }
92 return crc ^ 0xFFFFFFFF
93}
94
95// One-shot computation: CRC-32 of `n` bytes from `data`.
96func nx_crc32(data: *u8, n: i64) -> i64 {
97 return nx_crc32_update(0, data, n)
98}
99
100// ---- self-test ---------------------------------------------------
101
102func main() -> i64 {
103 // CRC-32("") = 0
104 let empty: *u8 = sys_mmap(8)
105 if nx_crc32(empty, 0) != 0 { return __syscall(93, 1, 0, 0, 0, 0, 0) }
106
107 // CRC-32("123456789") = 0xCBF43926 (standard test vector).
108 let s: *u8 = sys_mmap(16)
109 s[0] = 0x31; s[1] = 0x32; s[2] = 0x33; s[3] = 0x34
110 s[4] = 0x35; s[5] = 0x36; s[6] = 0x37; s[7] = 0x38; s[8] = 0x39
111 let crc: i64 = nx_crc32(s, 9)
112 if crc != 0xCBF43926 { return __syscall(93, 2, 0, 0, 0, 0, 0) }
113
114 // Streaming: split "123456789" into "1234" + "5" + "6789".
115 var crc2: i64 = nx_crc32_update(0, s, 4)
116 let s5: *u8 = (((s as i64) + 4) as *u8)
117 crc2 = nx_crc32_update(crc2, s5, 1)
118 let s6: *u8 = (((s as i64) + 5) as *u8)
119 crc2 = nx_crc32_update(crc2, s6, 4)
120 if crc2 != 0xCBF43926 { return __syscall(93, 3, 0, 0, 0, 0, 0) }
121
122 // CRC-32("a") = 0xE8B7BE43
123 let a: *u8 = sys_mmap(8)
124 a[0] = 0x61
125 let crc3: i64 = nx_crc32(a, 1)
126 if crc3 != 0xE8B7BE43 { return __syscall(93, 4, 0, 0, 0, 0, 0) }
127
128 return 0
129}