crc32.nx source
↩ module page · 91 lines · 3464 B
1// crc32.nx -- CRC-32 checksum (IEEE 802.3 + Castagnoli).
2//
3// Two widely-used variants:
4//
5// crc32 IEEE 802.3 polynomial 0xEDB88320 (reversed).
6// Used by: ZIP, PNG, gzip, Ethernet, PNG, Adler (old TCP).
7//
8// crc32c Castagnoli polynomial 0x82F63B78 (reversed).
9// Used by: iSCSI, SCTP, ZFS, BTRFS, Google Wire Format,
10// AWS S3 checksum-algorithm-CRC32C. Better error
11// detection + hardware-accelerated on x86 (CRC32Q op)
12// and ARMv8.
13//
14// Not cryptographic -- trivial to forge. Good only as an integrity
15// check against random bit-flips (storage, transmission).
16//
17// Algorithm: table-less bit-by-bit variant. 8 iterations per input
18// byte; each iteration xor-shifts the current CRC by 1 and
19// conditionally xors in the polynomial. ~50 CPU cycles per byte;
20// for high-throughput callers, a future 256-entry table lookup
21// lands when NishiLang gets proper const-array literals.
22//
23// Both variants start with CRC = 0xFFFFFFFF and end by xor'ing
24// with 0xFFFFFFFF (i.e., complement) -- matches every reference
25// implementation (zlib, CRC-32/BZIP2 identical handling).
26//
27// Invariants:
28// CRC1 Output is exact match for zlib's crc32() / crc32c() for
29// the same input. Known-answer: crc32("") = 0x00000000;
30// crc32("123456789") = 0xCBF43926; crc32c("123456789") =
31// 0xE3069283.
32// CRC2 Input read-only; returns u32 result packed into the low
33// 32 bits of i64.
34// CRC3 No branch on data: the "conditionally xor" is a mask-
35// multiply (0 or 1 times polynomial) -- not secret-time
36// critical (CRC isn't crypto) but keeps the loop shape
37// predictable.
38
39import "syscalls.nx"
40
41const CRC32_POLY: i64 = 0xEDB88320
42const CRC32C_POLY: i64 = 0x82F63B78
43const U32_MASK: i64 = 0xFFFFFFFF
44const U32_INIT: i64 = 0xFFFFFFFF
45
46// Core bit-by-bit CRC loop. Parameterised by polynomial so both
47// crc32 and crc32c share the kernel.
48func crc32_core(poly: i64, bytes: *u8, n: i64, initial: i64) -> i64 {
49 var crc: i64 = initial
50 var i: i64 = 0
51 while i < n {
52 crc = crc ^ bytes[i]
53 var bit: i64 = 0
54 while bit < 8 {
55 let lsb: i64 = crc & 1
56 let mask: i64 = 0 - lsb // 0 or all-ones
57 crc = ((crc >> 1) & 0x7FFFFFFFFFFFFFFF) ^ (mask & poly)
58 // NishiLang >> on i64 is arithmetic; mask high bits
59 // above 32 to keep the CRC a true u32.
60 crc = crc & U32_MASK
61 bit = bit + 1
62 }
63 i = i + 1
64 }
65 return crc & U32_MASK
66}
67
68// IEEE 802.3 / zlib CRC-32.
69func crc32(bytes: *u8, n: i64) -> i64 {
70 let raw: i64 = crc32_core(CRC32_POLY, bytes, n, U32_INIT)
71 return (raw ^ U32_INIT) & U32_MASK
72}
73
74// Castagnoli CRC-32C.
75func crc32c(bytes: *u8, n: i64) -> i64 {
76 let raw: i64 = crc32_core(CRC32C_POLY, bytes, n, U32_INIT)
77 return (raw ^ U32_INIT) & U32_MASK
78}
79
80// Compile-only smoke. Known answer crc32("123456789") = 0xCBF43926
81// from RFC 3720. We can't verify the numeric output without
82// execution; structure-check is what we have today.
83func main() -> i64 {
84 let msg: *u8 = "123456789"
85 let c1: i64 = crc32(msg, 9)
86 let c2: i64 = crc32c(msg, 9)
87 // Return xor of the two -- nonzero if they differ (they
88 // should; different polynomials).
89 if c1 == c2 { return 1 }
90 return 0
91}