base58.nx source
↩ module page · 182 lines · 6174 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
23import "syscalls.nx"
24
25const B58_ERR_BAD_CHAR: i64 = -1
26const B58_ERR_OVERFLOW: i64 = -2
27
28// Encode one value (0..57) as an alphabet character.
29func b58_enc_char(v: i64) -> i64 {
30 // "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
31 // indexed by v. Computed via ranges to avoid a huge lookup.
32 if v < 9 { return 0x31 + v } // '1'..'9'
33 if v < 17 { return 0x41 + (v - 9) } // 'A'..'H'
34 // skip I (index 17 would be I, which alphabet excludes)
35 if v < 22 { return 0x4A + (v - 17) } // 'J'..'N'
36 // skip O
37 if v < 33 { return 0x50 + (v - 22) } // 'P'..'Z'
38 if v < 44 { return 0x61 + (v - 33) } // 'a'..'k'
39 // skip l
40 if v < 58 { return 0x6D + (v - 44) } // 'm'..'z'
41 return 0
42}
43
44// Decode one alphabet character to value (0..57) or B58_ERR_BAD_CHAR.
45func b58_dec_val(c: i64) -> i64 {
46 if c >= 0x31 { if c <= 0x39 { return c - 0x31 } } // '1'..'9'
47 if c >= 0x41 { if c <= 0x48 { return c - 0x41 + 9 } } // 'A'..'H'
48 if c >= 0x4A { if c <= 0x4E { return c - 0x4A + 17 } } // 'J'..'N'
49 if c >= 0x50 { if c <= 0x5A { return c - 0x50 + 22 } } // 'P'..'Z'
50 if c >= 0x61 { if c <= 0x6B { return c - 0x61 + 33 } } // 'a'..'k'
51 if c >= 0x6D { if c <= 0x7A { return c - 0x6D + 44 } } // 'm'..'z'
52 return B58_ERR_BAD_CHAR
53}
54
55// Forward declaration: body after base58_encode.
56func base58_encode_after_zeros(in_bytes: *u8, n: i64, zeros: i64, out: *u8) -> i64;
57
58// Encode n bytes from in_bytes to base58 in `out`. Returns
59// length written. out must be sized >= n * 138/100 + 1 (log2
60// ratio of 256 to 58).
61func base58_encode(in_bytes: *u8, n: i64, out: *u8) -> i64 {
62 // Count leading zero bytes.
63 var zeros: i64 = 0
64 while zeros < n {
65 if in_bytes[zeros] != 0 { return base58_encode_after_zeros(in_bytes, n, zeros, out) }
66 zeros = zeros + 1
67 }
68 // All zeros: emit `zeros` number of '1' chars.
69 var i: i64 = 0
70 while i < n {
71 out[i] = 0x31
72 i = i + 1
73 }
74 return n
75}
76
77func base58_encode_after_zeros(in_bytes: *u8, n: i64, zeros: i64, out: *u8) -> i64 {
78 // Working buffer holds base58 digits, least-significant first.
79 // Max size: ceil(n * log(256) / log(58)) ≈ n * 138 / 100 + 1.
80 let cap: i64 = n * 138 / 100 + 1
81 let digits: *u8 = sys_mmap(cap + 16)
82 var i: i64 = 0
83 while i < cap { digits[i] = 0; i = i + 1 }
84 var digit_count: i64 = 0
85
86 // Convert big-endian bytes to base58 via repeated division.
87 i = zeros
88 while i < n {
89 var carry: i64 = in_bytes[i] & 0xFF
90 var j: i64 = 0
91 while j < digit_count {
92 carry = carry + (digits[j] << 8)
93 digits[j] = carry % 58
94 carry = carry / 58
95 j = j + 1
96 }
97 while carry > 0 {
98 digits[digit_count] = carry % 58
99 carry = carry / 58
100 digit_count = digit_count + 1
101 }
102 i = i + 1
103 }
104
105 // Emit leading-zero '1's.
106 var out_pos: i64 = 0
107 i = 0
108 while i < zeros {
109 out[out_pos] = 0x31
110 out_pos = out_pos + 1
111 i = i + 1
112 }
113 // Emit digits in reverse (most-significant first).
114 i = digit_count - 1
115 while i >= 0 {
116 out[out_pos] = b58_enc_char(digits[i])
117 out_pos = out_pos + 1
118 i = i - 1
119 }
120 return out_pos
121}
122
123// Decode n base58 chars to bytes in out. Returns length written
124// or negative on error.
125func base58_decode(in_chars: *u8, n: i64, out: *u8) -> i64 {
126 // Count leading '1's = leading zero bytes in output.
127 var zeros: i64 = 0
128 while zeros < n {
129 if in_chars[zeros] != 0x31 { break }
130 zeros = zeros + 1
131 }
132
133 // Accumulator in base-256, least-significant-byte first.
134 let cap: i64 = n * 733 / 1000 + 1
135 let bytes: *u8 = sys_mmap(cap + 16)
136 var i: i64 = 0
137 while i < cap { bytes[i] = 0; i = i + 1 }
138 var byte_count: i64 = 0
139
140 i = zeros
141 while i < n {
142 let d: i64 = b58_dec_val(in_chars[i])
143 if d < 0 { return B58_ERR_BAD_CHAR }
144 var carry: i64 = d
145 var j: i64 = 0
146 while j < byte_count {
147 carry = carry + (bytes[j] * 58)
148 bytes[j] = carry & 0xFF
149 carry = carry >> 8
150 j = j + 1
151 }
152 while carry > 0 {
153 bytes[byte_count] = carry & 0xFF
154 carry = carry >> 8
155 byte_count = byte_count + 1
156 }
157 i = i + 1
158 }
159
160 // Emit leading zeros + reversed bytes.
161 var out_pos: i64 = 0
162 i = 0
163 while i < zeros { out[out_pos] = 0; out_pos = out_pos + 1; i = i + 1 }
164 i = byte_count - 1
165 while i >= 0 {
166 out[out_pos] = bytes[i]
167 out_pos = out_pos + 1
168 i = i - 1
169 }
170 return out_pos
171}
172
173// Compile-only smoke. Known: base58_encode({0x00}) = "1".
174func main() -> i64 {
175 let in_bytes: *u8 = sys_mmap(8)
176 in_bytes[0] = 0
177 let out: *u8 = sys_mmap(16)
178 let n: i64 = base58_encode(in_bytes, 1, out)
179 if n != 1 { return 1 }
180 if out[0] != 0x31 { return 2 } // '1'
181 return 0
182}