zat.dev
atproto utils for zig
zat.dev
atproto
sdk
zig
zzstoatzz.io
1//! multibase codec
2//!
3//! encodes and decodes multibase-encoded strings (prefix + encoded data).
4//! supports base58btc (z prefix) and base32lower (b prefix).
5//!
6//! see: https://github.com/multiformats/multibase
7
8const std = @import("std");
9
10/// multibase encoding types
11pub const Encoding = enum {
12 base58btc, // z prefix
13 base32lower, // b prefix
14
15 pub fn fromPrefix(prefix: u8) ?Encoding {
16 return switch (prefix) {
17 'z' => .base58btc,
18 'b' => .base32lower,
19 else => null,
20 };
21 }
22};
23
24/// decode a multibase string, returning the raw bytes
25/// the first character is the encoding prefix
26pub fn decode(allocator: std.mem.Allocator, input: []const u8) ![]u8 {
27 if (input.len == 0) return error.EmptyInput;
28
29 const encoding = Encoding.fromPrefix(input[0]) orelse return error.UnsupportedEncoding;
30
31 return switch (encoding) {
32 .base58btc => try base58btc.decode(allocator, input[1..]),
33 .base32lower => try base32lower.decode(allocator, input[1..]),
34 };
35}
36
37/// encode raw bytes to a multibase string with the given encoding
38pub fn encode(allocator: std.mem.Allocator, encoding: Encoding, data: []const u8) ![]u8 {
39 return switch (encoding) {
40 .base58btc => try base58btc.encode(allocator, data),
41 .base32lower => try base32lower.encode(allocator, data),
42 };
43}
44
45/// base58btc codec (bitcoin alphabet)
46pub const base58btc = struct {
47 /// bitcoin base58 alphabet
48 const alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
49
50 /// reverse lookup table
51 const decode_table: [256]i8 = blk: {
52 var table: [256]i8 = .{-1} ** 256;
53 for (alphabet, 0..) |c, i| {
54 table[c] = @intCast(i);
55 }
56 break :blk table;
57 };
58
59 /// encode bytes to base58btc string with 'z' multibase prefix
60 pub fn encode(allocator: std.mem.Allocator, input: []const u8) ![]u8 {
61 // count leading zero bytes → leading '1's
62 var leading_zeros: usize = 0;
63 for (input) |b| {
64 if (b != 0) break;
65 leading_zeros += 1;
66 }
67
68 if (input.len == 0 or leading_zeros == input.len) {
69 // all zeros (or empty)
70 const result = try allocator.alloc(u8, 1 + leading_zeros);
71 result[0] = 'z'; // multibase prefix
72 @memset(result[1..], '1');
73 return result;
74 }
75
76 // load bytes into big integer (big-endian)
77 var acc = try std.math.big.int.Managed.init(allocator);
78 defer acc.deinit();
79
80 for (input) |b| {
81 try acc.shiftLeft(&acc, 8);
82 try acc.addScalar(&acc, b);
83 }
84
85 // repeatedly divide by 58 to extract base58 digits
86 var digits: std.ArrayList(u8) = .{};
87 defer digits.deinit(allocator);
88
89 var divisor = try std.math.big.int.Managed.initSet(allocator, @as(u64, 58));
90 defer divisor.deinit();
91
92 var quotient = try std.math.big.int.Managed.init(allocator);
93 defer quotient.deinit();
94
95 var remainder = try std.math.big.int.Managed.init(allocator);
96 defer remainder.deinit();
97
98 while (!acc.toConst().eqlZero()) {
99 try quotient.divFloor(&remainder, &acc, &divisor);
100 const digit: usize = @intCast(remainder.toConst().toInt(u64) catch 0);
101 try digits.append(allocator, alphabet[digit]);
102 try acc.copy(quotient.toConst());
103 }
104
105 // result: 'z' prefix + leading '1's + reversed digits
106 const total_len = 1 + leading_zeros + digits.items.len;
107 const result = try allocator.alloc(u8, total_len);
108 result[0] = 'z'; // multibase prefix
109 @memset(result[1 .. 1 + leading_zeros], '1');
110
111 // digits were accumulated LSB-first, reverse into result
112 const digit_slice = result[1 + leading_zeros ..];
113 for (digits.items, 0..) |d, i| {
114 digit_slice[digits.items.len - 1 - i] = d;
115 }
116
117 return result;
118 }
119
120 /// decode base58btc string to bytes
121 pub fn decode(allocator: std.mem.Allocator, input: []const u8) ![]u8 {
122 if (input.len == 0) return allocator.alloc(u8, 0);
123
124 // count leading zeros (1s in base58)
125 var leading_zeros: usize = 0;
126 for (input) |c| {
127 if (c != '1') break;
128 leading_zeros += 1;
129 }
130
131 // decode using big integer arithmetic
132 var acc = try std.math.big.int.Managed.init(allocator);
133 defer acc.deinit();
134
135 var multiplier = try std.math.big.int.Managed.initSet(allocator, @as(u64, 58));
136 defer multiplier.deinit();
137
138 var temp = try std.math.big.int.Managed.init(allocator);
139 defer temp.deinit();
140
141 for (input) |c| {
142 const digit = decode_table[c];
143 if (digit < 0) return error.InvalidCharacter;
144
145 try temp.mul(&acc, &multiplier);
146 try acc.copy(temp.toConst());
147 try acc.addScalar(&acc, @as(u8, @intCast(digit)));
148 }
149
150 // convert big int to bytes (big-endian)
151 const limbs = acc.toConst().limbs;
152 const limb_count = acc.len();
153
154 var byte_count: usize = 0;
155 if (limb_count > 0 and !acc.toConst().eqlZero()) {
156 byte_count = (acc.toConst().bitCountAbs() + 7) / 8;
157 }
158
159 const result = try allocator.alloc(u8, leading_zeros + byte_count);
160 @memset(result[0..leading_zeros], 0);
161
162 // convert limbs to big-endian bytes
163 if (byte_count > 0) {
164 const output_slice = result[leading_zeros..];
165 var pos: usize = byte_count;
166 for (limbs[0..limb_count]) |limb| {
167 const limb_bytes = @sizeOf(@TypeOf(limb));
168 var i: usize = 0;
169 while (i < limb_bytes and pos > 0) : (i += 1) {
170 pos -= 1;
171 output_slice[pos] = @truncate(limb >> @intCast(i * 8));
172 }
173 }
174 }
175
176 return result;
177 }
178};
179
180/// base32lower codec (RFC 4648, lowercase, no padding)
181pub const base32lower = struct {
182 const alphabet = "abcdefghijklmnopqrstuvwxyz234567";
183
184 const decode_table: [256]i8 = blk: {
185 var table: [256]i8 = .{-1} ** 256;
186 for (alphabet, 0..) |c, i| {
187 table[c] = @intCast(i);
188 }
189 break :blk table;
190 };
191
192 /// encode bytes to base32lower string with 'b' multibase prefix
193 pub fn encode(allocator: std.mem.Allocator, input: []const u8) ![]u8 {
194 if (input.len == 0) {
195 const result = try allocator.alloc(u8, 1);
196 result[0] = 'b';
197 return result;
198 }
199
200 // base32: 5 bytes → 8 chars
201 const out_len = (input.len * 8 + 4) / 5; // ceil(bits / 5)
202 const result = try allocator.alloc(u8, 1 + out_len);
203 result[0] = 'b'; // multibase prefix
204
205 var bit_buf: u32 = 0;
206 var bits: u5 = 0;
207 var pos: usize = 1;
208
209 for (input) |byte| {
210 bit_buf = (bit_buf << 8) | byte;
211 bits += 8;
212 while (bits >= 5) {
213 bits -= 5;
214 const idx: u5 = @truncate(bit_buf >> bits);
215 result[pos] = alphabet[idx];
216 pos += 1;
217 }
218 }
219
220 // remaining bits (left-aligned)
221 if (bits > 0) {
222 const idx: u5 = @truncate(bit_buf << (@as(u5, 5) - bits));
223 result[pos] = alphabet[idx];
224 pos += 1;
225 }
226
227 return result[0..pos];
228 }
229
230 /// decode base32lower string (no multibase prefix) to bytes
231 pub fn decode(allocator: std.mem.Allocator, input: []const u8) ![]u8 {
232 if (input.len == 0) return allocator.alloc(u8, 0);
233
234 const out_len = input.len * 5 / 8;
235 const result = try allocator.alloc(u8, out_len);
236 errdefer allocator.free(result);
237
238 var bit_buf: u32 = 0;
239 var bits: u4 = 0;
240 var pos: usize = 0;
241
242 for (input) |c| {
243 if (c == '=') break; // stop at padding
244 const digit = decode_table[c];
245 if (digit < 0) return error.InvalidCharacter;
246
247 bit_buf = (bit_buf << 5) | @as(u32, @intCast(digit));
248 bits += 5;
249 if (bits >= 8) {
250 bits -= 8;
251 result[pos] = @truncate(bit_buf >> bits);
252 pos += 1;
253 }
254 }
255
256 return allocator.realloc(result, pos);
257 }
258};
259
260// === tests ===
261
262test "base58btc decode" {
263 const alloc = std.testing.allocator;
264
265 // "abc" in base58btc
266 // "abc" = 0x616263 = 6382179
267 // expected base58btc: "ZiCa" (verify with external tool)
268 {
269 const decoded = try base58btc.decode(alloc, "ZiCa");
270 defer alloc.free(decoded);
271 try std.testing.expectEqualSlices(u8, "abc", decoded);
272 }
273}
274
275test "base58btc decode with leading zeros" {
276 const alloc = std.testing.allocator;
277
278 // leading 1s map to leading zero bytes
279 {
280 const decoded = try base58btc.decode(alloc, "111");
281 defer alloc.free(decoded);
282 try std.testing.expectEqual(@as(usize, 3), decoded.len);
283 try std.testing.expectEqualSlices(u8, &[_]u8{ 0, 0, 0 }, decoded);
284 }
285}
286
287test "multibase decode base58btc" {
288 const alloc = std.testing.allocator;
289
290 // z prefix = base58btc
291 {
292 const decoded = try decode(alloc, "zZiCa");
293 defer alloc.free(decoded);
294 try std.testing.expectEqualSlices(u8, "abc", decoded);
295 }
296}
297
298test "base58btc decode real multibase key - secp256k1" {
299 const alloc = std.testing.allocator;
300 const multicodec = @import("multicodec.zig");
301
302 // from a real DID document: zQ3shXjHeiBuRCKmM36cuYnm7YEMzhGnCmCyW92sRJ9pribSF
303 // this is a compressed secp256k1 public key with multicodec prefix
304 const key = "zQ3shXjHeiBuRCKmM36cuYnm7YEMzhGnCmCyW92sRJ9pribSF";
305 const decoded = try decode(alloc, key);
306 defer alloc.free(decoded);
307
308 // should decode to 35 bytes: 2-byte multicodec prefix (0xe7 0x01 varint) + 33-byte compressed key
309 try std.testing.expectEqual(@as(usize, 35), decoded.len);
310
311 // first two bytes should be secp256k1-pub multicodec prefix (0xe7 0x01 varint for 231)
312 try std.testing.expectEqual(@as(u8, 0xe7), decoded[0]);
313 try std.testing.expectEqual(@as(u8, 0x01), decoded[1]);
314
315 // parse with multicodec
316 const parsed = try multicodec.parsePublicKey(decoded);
317 try std.testing.expectEqual(multicodec.KeyType.secp256k1, parsed.key_type);
318 try std.testing.expectEqual(@as(usize, 33), parsed.raw.len);
319
320 // compressed point prefix should be 0x02 or 0x03
321 try std.testing.expect(parsed.raw[0] == 0x02 or parsed.raw[0] == 0x03);
322}
323
324test "base58btc encode-decode round-trip" {
325 const alloc = std.testing.allocator;
326
327 {
328 const original = "abc";
329 const encoded = try base58btc.encode(alloc, original);
330 defer alloc.free(encoded);
331 // should have 'z' prefix
332 try std.testing.expectEqual(@as(u8, 'z'), encoded[0]);
333
334 const decoded = try decode(alloc, encoded);
335 defer alloc.free(decoded);
336 try std.testing.expectEqualSlices(u8, original, decoded);
337 }
338
339 // round-trip with leading zeros
340 {
341 const original = &[_]u8{ 0, 0, 0x01 };
342 const encoded = try base58btc.encode(alloc, original);
343 defer alloc.free(encoded);
344 const decoded = try decode(alloc, encoded);
345 defer alloc.free(decoded);
346 try std.testing.expectEqualSlices(u8, original, decoded);
347 }
348}
349
350test "base32lower encode-decode round-trip" {
351 const alloc = std.testing.allocator;
352
353 {
354 const original = "hello";
355 const encoded = try base32lower.encode(alloc, original);
356 defer alloc.free(encoded);
357 try std.testing.expectEqual(@as(u8, 'b'), encoded[0]);
358
359 const decoded = try decode(alloc, encoded);
360 defer alloc.free(decoded);
361 try std.testing.expectEqualSlices(u8, original, decoded);
362 }
363
364 // empty
365 {
366 const encoded = try base32lower.encode(alloc, "");
367 defer alloc.free(encoded);
368 try std.testing.expectEqualStrings("b", encoded);
369 }
370}
371
372test "base32lower decode bafyrei prefix" {
373 const alloc = std.testing.allocator;
374 // CIDv1 dag-cbor sha2-256 always starts with "bafyrei" in base32lower
375 // "bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454"
376 const input = "afyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454";
377 const decoded = try base32lower.decode(alloc, input);
378 defer alloc.free(decoded);
379 // CIDv1: version=1(0x01), codec=dag-cbor(0x71), hash=sha2-256(0x12), len=32(0x20)
380 try std.testing.expectEqual(@as(u8, 0x01), decoded[0]);
381 try std.testing.expectEqual(@as(u8, 0x71), decoded[1]);
382 try std.testing.expectEqual(@as(u8, 0x12), decoded[2]);
383 try std.testing.expectEqual(@as(u8, 0x20), decoded[3]);
384}