nx_base58.nx source
↩ module page · 188 lines · 6246 B
1// base58.nx -- Bitcoin / IPFS base58 encoder + decoder.
2//
3// Alphabet (omits 0/O/l/I to avoid visual confusion):
4// 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
5//
6// Used by: Bitcoin addresses, IPFS CID v0, Stellar account IDs,
7// Monero addresses. Less efficient than base64 (log(58)/log(256)
8// ≈ 0.73 bytes of data per char vs base64's 0.75) but preserves
9// 1:1 byte-to-copy safety when pasted into phishing-resistant
10// UI contexts.
11//
12// Leading zero bytes in input map to leading '1' chars in output.
13// This preserves information for binary protocols where leading
14// zeros are significant (Bitcoin addresses have a version prefix
15// byte that's often 0x00).
16//
17// Invariants:
18// B58_1 Alphabet is Bitcoin/IPFS canonical; no URL-safe
19// variant (unlike base64).
20// B58_2 Round-trip exact: decode(encode(x)) == x.
21// B58_3 Decoder rejects non-alphabet chars with negative err.
22
23// nx_safety_envelope:
24// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
25// sil_target: SIL1
26// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
27// verdict: NOT_YET_EVALUATED
28
29import "nx_syscalls.nx"
30
31const B58_ERR_BAD_CHAR: i64 = -1
32const B58_ERR_OVERFLOW: i64 = -2
33
34// Encode one value (0..57) as an alphabet character.
35func b58_enc_char(v: i64) -> i64 {
36 // "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
37 // indexed by v. Computed via ranges to avoid a huge lookup.
38 if v < 9 { return 0x31 + v } // '1'..'9'
39 if v < 17 { return 0x41 + (v - 9) } // 'A'..'H'
40 // skip I (index 17 would be I, which alphabet excludes)
41 if v < 22 { return 0x4A + (v - 17) } // 'J'..'N'
42 // skip O
43 if v < 33 { return 0x50 + (v - 22) } // 'P'..'Z'
44 if v < 44 { return 0x61 + (v - 33) } // 'a'..'k'
45 // skip l
46 if v < 58 { return 0x6D + (v - 44) } // 'm'..'z'
47 return 0
48}
49
50// Decode one alphabet character to value (0..57) or B58_ERR_BAD_CHAR.
51func b58_dec_val(c: i64) -> i64 {
52 if c >= 0x31 { if c <= 0x39 { return c - 0x31 } } // '1'..'9'
53 if c >= 0x41 { if c <= 0x48 { return c - 0x41 + 9 } } // 'A'..'H'
54 if c >= 0x4A { if c <= 0x4E { return c - 0x4A + 17 } } // 'J'..'N'
55 if c >= 0x50 { if c <= 0x5A { return c - 0x50 + 22 } } // 'P'..'Z'
56 if c >= 0x61 { if c <= 0x6B { return c - 0x61 + 33 } } // 'a'..'k'
57 if c >= 0x6D { if c <= 0x7A { return c - 0x6D + 44 } } // 'm'..'z'
58 return B58_ERR_BAD_CHAR
59}
60
61// Forward declaration: body after base58_encode.
62func base58_encode_after_zeros(in_bytes: *u8, n: i64, zeros: i64, out: *u8) -> i64;
63
64// Encode n bytes from in_bytes to base58 in `out`. Returns
65// length written. out must be sized >= n * 138/100 + 1 (log2
66// ratio of 256 to 58).
67func base58_encode(in_bytes: *u8, n: i64, out: *u8) -> i64 {
68 // Count leading zero bytes.
69 var zeros: i64 = 0
70 while zeros < n {
71 if in_bytes[zeros] != 0 { return base58_encode_after_zeros(in_bytes, n, zeros, out) }
72 zeros = zeros + 1
73 }
74 // All zeros: emit `zeros` number of '1' chars.
75 var i: i64 = 0
76 while i < n {
77 out[i] = 0x31
78 i = i + 1
79 }
80 return n
81}
82
83func base58_encode_after_zeros(in_bytes: *u8, n: i64, zeros: i64, out: *u8) -> i64 {
84 // Working buffer holds base58 digits, least-significant first.
85 // Max size: ceil(n * log(256) / log(58)) ≈ n * 138 / 100 + 1.
86 let cap: i64 = n * 138 / 100 + 1
87 let digits: *u8 = sys_mmap(cap + 16)
88 var i: i64 = 0
89 while i < cap { digits[i] = 0; i = i + 1 }
90 var digit_count: i64 = 0
91
92 // Convert big-endian bytes to base58 via repeated division.
93 i = zeros
94 while i < n {
95 var carry: i64 = in_bytes[i] & 0xFF
96 var j: i64 = 0
97 while j < digit_count {
98 carry = carry + (digits[j] << 8)
99 digits[j] = carry % 58
100 carry = carry / 58
101 j = j + 1
102 }
103 while carry > 0 {
104 digits[digit_count] = carry % 58
105 carry = carry / 58
106 digit_count = digit_count + 1
107 }
108 i = i + 1
109 }
110
111 // Emit leading-zero '1's.
112 var out_pos: i64 = 0
113 i = 0
114 while i < zeros {
115 out[out_pos] = 0x31
116 out_pos = out_pos + 1
117 i = i + 1
118 }
119 // Emit digits in reverse (most-significant first).
120 i = digit_count - 1
121 while i >= 0 {
122 out[out_pos] = b58_enc_char(digits[i])
123 out_pos = out_pos + 1
124 i = i - 1
125 }
126 return out_pos
127}
128
129// Decode n base58 chars to bytes in out. Returns length written
130// or negative on error.
131func base58_decode(in_chars: *u8, n: i64, out: *u8) -> i64 {
132 // Count leading '1's = leading zero bytes in output.
133 var zeros: i64 = 0
134 while zeros < n {
135 if in_chars[zeros] != 0x31 { break }
136 zeros = zeros + 1
137 }
138
139 // Accumulator in base-256, least-significant-byte first.
140 let cap: i64 = n * 733 / 1000 + 1
141 let bytes: *u8 = sys_mmap(cap + 16)
142 var i: i64 = 0
143 while i < cap { bytes[i] = 0; i = i + 1 }
144 var byte_count: i64 = 0
145
146 i = zeros
147 while i < n {
148 let d: i64 = b58_dec_val(in_chars[i])
149 if d < 0 { return B58_ERR_BAD_CHAR }
150 var carry: i64 = d
151 var j: i64 = 0
152 while j < byte_count {
153 carry = carry + (bytes[j] * 58)
154 bytes[j] = carry & 0xFF
155 carry = carry >> 8
156 j = j + 1
157 }
158 while carry > 0 {
159 bytes[byte_count] = carry & 0xFF
160 carry = carry >> 8
161 byte_count = byte_count + 1
162 }
163 i = i + 1
164 }
165
166 // Emit leading zeros + reversed bytes.
167 var out_pos: i64 = 0
168 i = 0
169 while i < zeros { out[out_pos] = 0; out_pos = out_pos + 1; i = i + 1 }
170 i = byte_count - 1
171 while i >= 0 {
172 out[out_pos] = bytes[i]
173 out_pos = out_pos + 1
174 i = i - 1
175 }
176 return out_pos
177}
178
179// Compile-only smoke. Known: base58_encode({0x00}) = "1".
180func main() -> i64 {
181 let in_bytes: *u8 = sys_mmap(8)
182 in_bytes[0] = 0
183 let out: *u8 = sys_mmap(16)
184 let n: i64 = base58_encode(in_bytes, 1, out)
185 if n != 1 { return 1 }
186 if out[0] != 0x31 { return 2 } // '1'
187 return 0
188}