nx_crockford32.nx source
↩ module page · 203 lines · 6624 B
1// crockford32.nx -- Crockford Base32 encoding.
2//
3// Douglas Crockford 2002: a base32 variant designed for human
4// transcription. Removes I, L, O, U (visually similar to 1, 1,
5// 0, V respectively) from the alphabet. Accepts mixed case +
6// hyphens on decode (so \"4CQ-5M4D\" and \"4cq5m4d\" both decode to
7// the same bytes).
8//
9// Alphabet: 0123456789ABCDEFGHJKMNPQRSTVWXYZ
10// 0 1
11// 0123456789012345678901234567890 1
12//
13// Used by:
14// - ULID (Universal Unique Lexicographically-sortable Identifier)
15// -- 26-char ID, Crockford-32 over 128 bits
16// - License keys, short-URL tokens, password reset tokens
17// - Voicemail PINs, serial numbers for hardware
18//
19// Not RFC-standardised (RFC 4648 base32 is similar but uses a
20// different alphabet and doesn't allow hyphens/mixed case). We
21// ship both: base32.nx (RFC 4648) and this module (Crockford).
22//
23// Invariants:
24// C1 Encoder output is upper-case only, no padding.
25// C2 Decoder accepts mixed case + '-' between groups.
26// C3 Round-trip exact: decode(encode(x)) == x.
27
28// nx_safety_envelope:
29// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
30// sil_target: SIL1
31// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
32// verdict: NOT_YET_EVALUATED
33
34import "nx_syscalls.nx"
35
36const C32_ERR_SHORT: i64 = -1
37const C32_ERR_CHAR: i64 = -2
38
39// Encode 5 bits (0..31) as one Crockford ASCII char.
40func c32_enc_char(n: i64) -> i64 {
41 if n < 10 { return 0x30 + n } // '0'..'9'
42 let m: i64 = n - 10
43 // 0..9 map to A..J (skipping I at index 8)
44 // Actually Crockford: 10='A', 11='B', 12='C', 13='D', 14='E',
45 // 15='F', 16='G', 17='H', 18='J', 19='K',
46 // 20='M', 21='N', 22='P', 23='Q', 24='R',
47 // 25='S', 26='T', 27='V', 28='W', 29='X',
48 // 30='Y', 31='Z'.
49 if m < 8 { return 0x41 + m } // A..H for 10..17
50 if m == 8 { return 0x4A } // 18 -> J (skip I)
51 if m == 9 { return 0x4B } // 19 -> K
52 if m == 10 { return 0x4D } // 20 -> M (skip L)
53 if m == 11 { return 0x4E } // 21 -> N
54 if m == 12 { return 0x50 } // 22 -> P (skip O)
55 if m == 13 { return 0x51 } // 23 -> Q
56 if m == 14 { return 0x52 } // 24 -> R
57 if m == 15 { return 0x53 } // 25 -> S
58 if m == 16 { return 0x54 } // 26 -> T
59 if m == 17 { return 0x56 } // 27 -> V (skip U)
60 if m == 18 { return 0x57 } // 28 -> W
61 if m == 19 { return 0x58 } // 29 -> X
62 if m == 20 { return 0x59 } // 30 -> Y
63 return 0x5A // 31 -> Z
64}
65
66// Decode one Crockford char. Returns 0..31 or C32_ERR_CHAR.
67// Accepts both cases + lenient I/L/O mapping to 1/1/0 per
68// Crockford spec ยง3 \"friendly decoding\".
69func c32_dec_char(c: i64) -> i64 {
70 // Uppercase the letter half.
71 var u: i64 = c
72 if u >= 0x61 {
73 if u <= 0x7A { u = u - 0x20 }
74 }
75 // Digits 0..9.
76 if u >= 0x30 {
77 if u <= 0x39 { return u - 0x30 }
78 }
79 // Skip hyphens (just error, caller pre-strips them).
80 if u == 0x49 { return 1 } // I -> 1
81 if u == 0x4C { return 1 } // L -> 1
82 if u == 0x4F { return 0 } // O -> 0
83
84 if u == 0x41 { return 10 } // A
85 if u == 0x42 { return 11 }
86 if u == 0x43 { return 12 }
87 if u == 0x44 { return 13 }
88 if u == 0x45 { return 14 }
89 if u == 0x46 { return 15 }
90 if u == 0x47 { return 16 }
91 if u == 0x48 { return 17 }
92 if u == 0x4A { return 18 }
93 if u == 0x4B { return 19 }
94 if u == 0x4D { return 20 }
95 if u == 0x4E { return 21 }
96 if u == 0x50 { return 22 }
97 if u == 0x51 { return 23 }
98 if u == 0x52 { return 24 }
99 if u == 0x53 { return 25 }
100 if u == 0x54 { return 26 }
101 if u == 0x56 { return 27 }
102 if u == 0x57 { return 28 }
103 if u == 0x58 { return 29 }
104 if u == 0x59 { return 30 }
105 if u == 0x5A { return 31 }
106 return C32_ERR_CHAR
107}
108
109// Encode `n` bytes of `in_bytes` as Crockford base32. Output
110// length = ceil(n * 8 / 5). No padding.
111func c32_encode(in_bytes: *u8, n: i64, out: *u8) -> i64 {
112 var buf: i64 = 0
113 var bits: i64 = 0
114 var out_pos: i64 = 0
115 var i: i64 = 0
116 while i < n {
117 buf = (buf << 8) | in_bytes[i]
118 bits = bits + 8
119 while bits >= 5 {
120 bits = bits - 5
121 let chunk: i64 = (buf >> bits) & 0x1F
122 out[out_pos] = c32_enc_char(chunk)
123 out_pos = out_pos + 1
124 }
125 i = i + 1
126 }
127 if bits > 0 {
128 let chunk: i64 = (buf << (5 - bits)) & 0x1F
129 out[out_pos] = c32_enc_char(chunk)
130 out_pos = out_pos + 1
131 }
132 return out_pos
133}
134
135// Decode. Skips '-' and whitespace. Returns bytes written or
136// negative.
137func c32_decode(chars: *u8, n: i64, out: *u8) -> i64 {
138 var buf: i64 = 0
139 var bits: i64 = 0
140 var out_pos: i64 = 0
141 var i: i64 = 0
142 while i < n {
143 let c: i64 = chars[i]
144 if c == 0x2D {
145 i = i + 1
146 continue
147 }
148 if c == 0x20 {
149 i = i + 1
150 continue
151 }
152 let v: i64 = c32_dec_char(c)
153 if v < 0 { return v }
154 buf = (buf << 5) | v
155 bits = bits + 5
156 if bits >= 8 {
157 bits = bits - 8
158 out[out_pos] = (buf >> bits) & 0xFF
159 out_pos = out_pos + 1
160 }
161 i = i + 1
162 }
163 return out_pos
164}
165
166// Compile-only smoke: round-trip + skip hyphens on decode.
167func main() -> i64 {
168 let out: *u8 = sys_mmap(64)
169 let n: i64 = c32_encode("hello", 5, out)
170 // 5 bytes * 8 = 40 bits / 5 = 8 chars.
171 if n != 8 { return 1 }
172
173 // Round trip.
174 let back: *u8 = sys_mmap(64)
175 let n2: i64 = c32_decode(out, n, back)
176 if n2 != 5 { return 2 }
177 let expected: *u8 = "hello"
178 var i: i64 = 0
179 while i < 5 {
180 if back[i] != expected[i] { return 3 }
181 i = i + 1
182 }
183
184 // Lenient decode: hyphens + lowercase + I/O -> 1/0.
185 // Encode \"hello\" produced uppercase C32. Insert a hyphen:
186 // e.g. out[4] kept, then hyphen, then rest.
187 let chopped: *u8 = sys_mmap(16)
188 i = 0
189 while i < 4 {
190 chopped[i] = out[i]
191 i = i + 1
192 }
193 chopped[4] = 0x2D // '-'
194 i = 4
195 while i < n {
196 chopped[i + 1] = out[i]
197 i = i + 1
198 }
199 let n3: i64 = c32_decode(chopped, n + 1, back)
200 if n3 != 5 { return 4 }
201
202 return 0
203}