Debian Codegraph @

encoding/base32/base32.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 use ascii;
5 use bytes;
6 use errors;
7 use io;
8 use memio;
9 use os;
10 use strings;
11
12 def PADDING: u8 = '=';
13
14 export type encoding = struct {
15 encmap: [32]u8,
16 decmap: [128]u8,
17 };
18
19 // Represents the standard base-32 encoding alphabet as defined in RFC 4648.
20 export const std_encoding: encoding = encoding {
21 encmap = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',
22 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y',
23 'Z', '2', '3', '4', '5', '6', '7'],
24 decmap = [
25 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
26 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
27 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
28 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
29 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
30 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
31 0xff, 0xff, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
32 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
33 0xff, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
34 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e,
35 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16,
36 0x17, 0x18, 0x19, 0xff...
37 ],
38 };
39
40 // Represents the "base32hex" alphabet as defined in RFC 4648.
41 export const hex_encoding: encoding = encoding {
42 encmap = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B',
43 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
44 'P', 'Q', 'R', 'S', 'T', 'U', 'V'],
45 decmap = [
46 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
47 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
48 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
49 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
50 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
51 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
52 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
53 0x08, 0x09, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
54 0xff, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10,
55 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
56 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0xff...
57 ],
58 };
59
60 // Initializes a new encoding based on the passed alphabet, which must be a
61 // 32-byte ASCII string.
62 export fn encoding_init(enc: *encoding, alphabet: str) void = {
63 const alphabet = strings::toutf8(alphabet);
64 assert(len(alphabet) == 32);
65 enc.decmap[..] = [0xff...];
66 for (let i: u8 = 0; i < 32; i += 1) {
67 const ch = alphabet[i];
68 assert(ascii::valid(ch: rune) && enc.decmap[ch] == 0xff);
69 enc.encmap[i] = ch;
70 enc.decmap[ch] = i;
71 };
72 };
73
74 @test fn std_encodings() void = {
75 let std = encoding { ... };
76 const std_alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
77 encoding_init(&std, std_alpha);
78 for (let i = 0z; i < len(std.encmap); i += 1) {
79 assert(std.encmap[i] == std_encoding.encmap[i]);
80 };
81 for (let i = 0z; i < len(std.decmap); i += 1) {
82 assert(std.decmap[i] == std_encoding.decmap[i]);
83 };
84
85 let hex = encoding { ... };
86 const hex_alpha = "0123456789ABCDEFGHIJKLMNOPQRSTUV";
87 encoding_init(&hex, hex_alpha);
88 for (let i = 0z; i < len(hex.encmap); i += 1) {
89 assert(hex.encmap[i] == hex_encoding.encmap[i]);
90 };
91 for (let i = 0z; i < len(hex.decmap); i += 1) {
92 assert(hex.decmap[i] == hex_encoding.decmap[i]);
93 };
94 };
95
96 export type encoder = struct {
97 stream: io::stream,
98 out: io::handle,
99 enc: *encoding,
100 buf: [4]u8, // leftover input
101 avail: size, // bytes available in buf
102 err: (void | io::error),
103 };
104
105 const encoder_vtable: io::vtable = io::vtable {
106 writer = &encode_writer,
107 closer = &encode_closer,
108 ...
109 };
110
111 // Creates a stream that encodes writes as base-32 before writing them to a
112 // secondary stream. The encoder stream must be closed to finalize any unwritten
113 // bytes. Closing this stream will not close the underlying stream.
114 export fn newencoder(
115 enc: *encoding,
116 out: io::handle,
117 ) encoder = {
118 return encoder {
119 stream = &encoder_vtable,
120 out = out,
121 enc = enc,
122 err = void,
123 ...
124 };
125 };
126
127 fn encode_writer(
128 s: *io::stream,
129 in: const []u8
130 ) (size | io::error) = {
131 let s = s: *encoder;
132 match(s.err) {
133 case let err: io::error =>
134 return err;
135 case void => void;
136 };
137 let l = len(in);
138 let i = 0z;
139 for (i + 4 < l + s.avail; i += 5) {
140 static let b: [5]u8 = [0...]; // 5 bytes -> (enc) 8 bytes
141 if (i < s.avail) {
142 for (let j = 0z; j < s.avail; j += 1) {
143 b[j] = s.buf[i];
144 };
145 for (let j = s.avail; j < 5; j += 1) {
146 b[j] = in[j - s.avail];
147 };
148 } else {
149 for (let j = 0z; j < 5; j += 1) {
150 b[j] = in[j - s.avail + i];
151 };
152 };
153 let encb: [8]u8 = [
154 s.enc.encmap[b[0] >> 3],
155 s.enc.encmap[(b[0] & 0x7) << 2 | (b[1] & 0xC0) >> 6],
156 s.enc.encmap[(b[1] & 0x3E) >> 1],
157 s.enc.encmap[(b[1] & 0x1) << 4 | (b[2] & 0xF0) >> 4],
158 s.enc.encmap[(b[2] & 0xF) << 1 | (b[3] & 0x80) >> 7],
159 s.enc.encmap[(b[3] & 0x7C) >> 2],
160 s.enc.encmap[(b[3] & 0x3) << 3 | (b[4] & 0xE0) >> 5],
161 s.enc.encmap[b[4] & 0x1F],
162 ];
163 match(io::write(s.out, encb)) {
164 case let err: io::error =>
165 s.err = err;
166 return err;
167 case size => void;
168 };
169 };
170 // storing leftover bytes
171 if (l + s.avail < 5) {
172 for (let j = s.avail; j < s.avail + l; j += 1) {
173 s.buf[j] = in[j - s.avail];
174 };
175 } else {
176 const begin = (l + s.avail) / 5 * 5;
177 for (let j = begin; j < l + s.avail; j += 1) {
178 s.buf[j - begin] = in[j - s.avail];
179 };
180 };
181 s.avail = (l + s.avail) % 5;
182 return l;
183 };
184
185 fn encode_closer(s: *io::stream) (void | io::error) = {
186 let s = s: *encoder;
187 if (s.avail == 0) {
188 return;
189 };
190 static let b: [5]u8 = [0...]; // the 5 bytes that will be encoded into 8 bytes
191 for (let i = 0z; i < 5; i += 1) {
192 b[i] = if (i < s.avail) s.buf[i] else 0;
193 };
194 let encb: [8]u8 = [
195 s.enc.encmap[b[0] >> 3],
196 s.enc.encmap[(b[0] & 0x7) << 2 | (b[1] & 0xC0) >> 6],
197 s.enc.encmap[(b[1] & 0x3E) >> 1],
198 s.enc.encmap[(b[1] & 0x1) << 4 | (b[2] & 0xF0) >> 4],
199 s.enc.encmap[(b[2] & 0xF) << 1 | (b[3] & 0x80) >> 7],
200 s.enc.encmap[(b[3] & 0x7C) >> 2],
201 s.enc.encmap[(b[3] & 0x3) << 3 | (b[4] & 0xE0) >> 5],
202 s.enc.encmap[b[4] & 0x1F],
203 ];
204 // adding padding as input length was not a multiple of 5
205 // 0 1 2 3 4
206 static const npa: []u8 = [0, 6, 4, 3, 1];
207 const np = npa[s.avail];
208 for (let i = 0z; i < np; i += 1) {
209 encb[7 - i] = PADDING;
210 };
211 io::writeall(s.out, encb)?;
212 };
213
214 // Encodes a byte slice in base-32, using the given encoding, returning a slice
215 // of ASCII bytes. The caller must free the return value.
216 export fn encodeslice(enc: *encoding, in: []u8) ([]u8 | nomem) = {
217 let out = memio::dynamic();
218 let encoder = newencoder(enc, &out);
219 match (io::writeall(&encoder, in)) {
220 case size => void;
221 case nomem =>
222 return nomem;
223 case =>
224 abort();
225 };
226 match (io::close(&encoder)) {
227 case void => void;
228 case nomem =>
229 return nomem;
230 case =>
231 abort();
232 };
233 return memio::buffer(&out);
234 };
235
236 // Encodes a byte slice in base-32, using the given encoding, returning a
237 // string. The caller must free the return value.
238 export fn encodestr(enc: *encoding, in: []u8) (str | nomem) = {
239 return strings::fromutf8(encodeslice(enc, in)?)!;
240 };
241
242 @test fn encode() void = {
243 // RFC 4648 test vectors
244 const in: [_]u8 = ['f', 'o', 'o', 'b', 'a', 'r'];
245 const expect: [_]str = [
246 "",
247 "MY======",
248 "MZXQ====",
249 "MZXW6===",
250 "MZXW6YQ=",
251 "MZXW6YTB",
252 "MZXW6YTBOI======",
253 ];
254 const expect_hex: [_]str = [
255 "",
256 "CO======",
257 "CPNG====",
258 "CPNMU===",
259 "CPNMUOG=",
260 "CPNMUOJ1",
261 "CPNMUOJ1E8======",
262 ];
263 for (let i = 0z; i <= len(in); i += 1) {
264 let out = memio::dynamic();
265 let enc = newencoder(&std_encoding, &out);
266 io::writeall(&enc, in[..i]) as size;
267 io::close(&enc)!;
268 let outb = memio::buffer(&out);
269 assert(bytes::equal(outb, strings::toutf8(expect[i])));
270 free(outb);
271 // Testing encodestr should cover encodeslice too
272 let s = encodestr(&std_encoding, in[..i])!;
273 defer free(s);
274 assert(s == expect[i]);
275
276 out = memio::dynamic();
277 enc = newencoder(&hex_encoding, &out);
278 io::writeall(&enc, in[..i]) as size;
279 io::close(&enc)!;
280 let outb = memio::buffer(&out);
281 assert(bytes::equal(outb, strings::toutf8(expect_hex[i])));
282 free(outb);
283 let s = encodestr(&hex_encoding, in[..i])!;
284 defer free(s);
285 assert(s == expect_hex[i]);
286 };
287 };
288
289 export type decoder = struct {
290 stream: io::stream,
291 in: io::handle,
292 enc: *encoding,
293 avail: []u8, // leftover decoded output
294 pad: bool, // if padding was seen in a previous read
295 state: (void | io::EOF | io::error),
296 };
297
298 const decoder_vtable: io::vtable = io::vtable {
299 reader = &decode_reader,
300 ...
301 };
302
303 // Creates a stream that reads and decodes base-32 data from a secondary stream.
304 // This stream does not need to be closed, and closing it will not close the
305 // underlying stream.
306 export fn newdecoder(
307 enc: *encoding,
308 in: io::handle,
309 ) decoder = {
310 return decoder {
311 stream = &decoder_vtable,
312 in = in,
313 enc = enc,
314 state = void,
315 ...
316 };
317 };
318
319 fn decode_reader(
320 s: *io::stream,
321 out: []u8
322 ) (size | io::EOF | io::error) = {
323 let s = s: *decoder;
324 let n = 0z;
325 let l = len(out);
326 match(s.state) {
327 case let err: (io::EOF | io ::error) =>
328 return err;
329 case void => void;
330 };
331 if (len(s.avail) > 0) {
332 n += if (l < len(s.avail)) l else len(s.avail);
333 out[..n] = s.avail[0..n];
334 s.avail = s.avail[n..];
335 if (l == n) {
336 return n;
337 };
338 };
339 static let buf: [os::BUFSZ]u8 = [0...];
340 static let obuf: [os::BUFSZ / 8 * 5]u8 = [0...];
341 const nn = ((l - n) / 5 + 1) * 8; // 8 extra bytes may be read.
342 let nr = 0z;
343 for (nr < nn) {
344 match (io::read(s.in, buf[nr..])) {
345 case let n: size =>
346 nr += n;
347 case io::EOF =>
348 s.state = io::EOF;
349 break;
350 case let err: io::error =>
351 s.state = err;
352 return err;
353 };
354 };
355 if (nr % 8 != 0) {
356 s.state = errors::invalid;
357 return errors::invalid;
358 };
359 if (nr == 0) { // io::EOF already set
360 return n;
361 };
362 // Validating read buffer
363 let valid = true;
364 let np = 0; // Number of padding chars.
365 let p = true; // Pad allowed in buf
366 for (let i = nr; i > 0; i -= 1) {
367 const ch = buf[i - 1];
368 if (ch == PADDING) {
369 if(s.pad || !p) {
370 valid = false;
371 break;
372 };
373 np += 1;
374 } else {
375 if (s.enc.decmap[ch] == 0xff) {
376 valid = false;
377 break;
378 };
379 // Disallow padding on seeing a non-padding char
380 p = false;
381 };
382 };
383 valid = valid && np <= 6 && np != 2 && np != 5;
384 if (np > 0) {
385 s.pad = true;
386 };
387 if (!valid) {
388 s.state = errors::invalid;
389 return errors::invalid;
390 };
391 for (let i = 0z; i < nr; i += 1) {
392 buf[i] = s.enc.decmap[buf[i]];
393 };
394 for (let i = 0z, j = 0z; i < nr) {
395 obuf[j] = (buf[i] << 3) | (buf[i + 1] & 0x1C) >> 2;
396 obuf[j + 1] =
397 (buf[i + 1] & 0x3) << 6 | buf[i + 2] << 1 | (buf[i + 3] & 0x10) >> 4;
398 obuf[j + 2] = (buf[i + 3] & 0x0F) << 4 | (buf[i + 4] & 0x1E) >> 1;
399 obuf[j + 3] =
400 (buf[i + 4] & 0x1) << 7 | buf[i + 5] << 2 | (buf[i + 6] & 0x18) >> 3;
401 obuf[j + 4] = (buf[i + 6] & 0x7) << 5 | buf[i + 7];
402 i += 8;
403 j += 5;
404 };
405 // Removing bytes added due to padding.
406 // 0 1 2 3 4 5 6 // np
407 static const npr: [7]u8 = [0, 1, 0, 2, 3, 0, 4]; // bytes to discard
408 const navl = nr / 8 * 5 - npr[np];
409 const rem = if(l - n < navl) l - n else navl;
410 out[n..n + rem] = obuf[..rem];
411 s.avail = obuf[rem..navl];
412 return n + rem;
413 };
414
415 // Decodes a byte slice of ASCII-encoded base-32 data, using the given encoding,
416 // returning a slice of decoded bytes. The caller must free the return value.
417 export fn decodeslice(
418 enc: *encoding,
419 in: []u8,
420 ) ([]u8 | errors::invalid | nomem) = {
421 let in = memio::fixed(in);
422 let decoder = newdecoder(enc, &in);
423 let out = memio::dynamic();
424 match (io::copy(&out, &decoder)) {
425 case size =>
426 return memio::buffer(&out);
427 case nomem =>
428 io::close(&out)!;
429 return nomem;
430 case errors::invalid =>
431 io::close(&out)!;
432 return errors::invalid;
433 case =>
434 abort(); // unreachable
435 };
436 };
437
438 // Decodes a string of ASCII-encoded base-32 data, using the given encoding,
439 // returning a slice of decoded bytes. The caller must free the return value.
440 export fn decodestr(enc: *encoding, in: str) ([]u8 | errors::invalid | nomem) = {
441 return decodeslice(enc, strings::toutf8(in));
442 };
443
444 @test fn decode() void = {
445 const cases: [_](str, str, *encoding) = [
446 ("", "", &std_encoding),
447 ("MY======", "f", &std_encoding),
448 ("MZXQ====", "fo", &std_encoding),
449 ("MZXW6===", "foo", &std_encoding),
450 ("MZXW6YQ=", "foob", &std_encoding),
451 ("MZXW6YTB", "fooba", &std_encoding),
452 ("MZXW6YTBOI======", "foobar", &std_encoding),
453 ("", "", &hex_encoding),
454 ("CO======", "f", &hex_encoding),
455 ("CPNG====", "fo", &hex_encoding),
456 ("CPNMU===", "foo", &hex_encoding),
457 ("CPNMUOG=", "foob", &hex_encoding),
458 ("CPNMUOJ1", "fooba", &hex_encoding),
459 ("CPNMUOJ1E8======", "foobar", &hex_encoding),
460 ];
461 for (let i = 0z; i < len(cases); i += 1) {
462 let in = memio::fixed(strings::toutf8(cases[i].0));
463 let dec = newdecoder(cases[i].2, &in);
464 let out: []u8 = io::drain(&dec)!;
465 defer free(out);
466 assert(bytes::equal(out, strings::toutf8(cases[i].1)));
467
468 // Testing decodestr should cover decodeslice too
469 let decb = decodestr(cases[i].2, cases[i].0) as []u8;
470 defer free(decb);
471 assert(bytes::equal(decb, strings::toutf8(cases[i].1)));
472 };
473 // Repeat of the above, but with a larger buffer
474 for (let i = 0z; i < len(cases); i += 1) {
475 let in = memio::fixed(strings::toutf8(cases[i].0));
476 let dec = newdecoder(cases[i].2, &in);
477 let out: []u8 = io::drain(&dec)!;
478 defer free(out);
479 assert(bytes::equal(out, strings::toutf8(cases[i].1)));
480 };
481
482 const invalid: [_](str, *encoding) = [
483 // invalid padding
484 ("=", &std_encoding),
485 ("==", &std_encoding),
486 ("===", &std_encoding),
487 ("=====", &std_encoding),
488 ("======", &std_encoding),
489 ("=======", &std_encoding),
490 ("========", &std_encoding),
491 ("=========", &std_encoding),
492 // invalid characters
493 ("1ZXW6YQ=", &std_encoding),
494 ("êZXW6YQ=", &std_encoding),
495 ("MZXW1YQ=", &std_encoding),
496 // data after padding is encountered
497 ("CO======CO======", &std_encoding),
498 ("CPNG====CPNG====", &std_encoding),
499 ];
500 for (let i = 0z; i < len(invalid); i += 1) {
501 let in = memio::fixed(strings::toutf8(invalid[i].0));
502 let dec = newdecoder(invalid[i].1, &in);
503 let buf: [1]u8 = [0...];
504 let valid = false;
505 for (true) match(io::read(&dec, buf)) {
506 case errors::invalid =>
507 break;
508 case size =>
509 valid = true;
510 case io::EOF =>
511 break;
512 };
513 assert(valid == false, "valid is not false");
514
515 // Testing decodestr should cover decodeslice too
516 assert(decodestr(invalid[i].1, invalid[i].0) is errors::invalid);
517 };
518 };