Debian Codegraph @

encoding/base64/base64.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: [64]u8,
16 decmap: [128]u8,
17 };
18
19 // Represents the standard base-64 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', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
24 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y',
25 'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '/'],
26 decmap = [
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, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
32 0xff, 0xff, 0xff, 0x3e, 0xff, 0xff, 0xff, 0x3f,
33 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b,
34 0x3c, 0x3d, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
35 0xff, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
36 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e,
37 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16,
38 0x17, 0x18, 0x19, 0xff, 0xff, 0xff, 0xff, 0xff,
39 0xff, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
40 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28,
41 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x30,
42 0x31, 0x32, 0x33, 0xff...
43 ],
44 };
45
46 // Represents the "base64url" alphabet as defined in RFC 4648, suitable for use
47 // in URLs and file paths.
48 export const url_encoding: encoding = encoding {
49 encmap = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',
50 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y',
51 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
52 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y',
53 'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '-', '_'],
54 decmap = [
55 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
56 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
57 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
58 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
59 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
60 0xff, 0xff, 0xff, 0xff, 0xff, 0x3e, 0xff, 0xff,
61 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b,
62 0x3c, 0x3d, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
63 0xff, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
64 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e,
65 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16,
66 0x17, 0x18, 0x19, 0xff, 0xff, 0xff, 0xff, 0x3f,
67 0xff, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
68 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28,
69 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x30,
70 0x31, 0x32, 0x33, 0xff...
71 ],
72 };
73
74 // Initializes a new encoding based on the passed alphabet, which must be a
75 // 64-byte ASCII string.
76 export fn encoding_init(enc: *encoding, alphabet: str) void = {
77 const alphabet = strings::toutf8(alphabet);
78 assert(len(alphabet) == 64);
79 enc.decmap[..] = [0xff...];
80 for (let i: u8 = 0; i < 64; i += 1) {
81 const ch = alphabet[i];
82 assert(ascii::valid(ch: rune) && enc.decmap[ch] == 0xff);
83 enc.encmap[i] = ch;
84 enc.decmap[ch] = i;
85 };
86 };
87
88 @test fn std_encodings() void = {
89 let std = encoding { ... };
90 const std_alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
91 encoding_init(&std, std_alpha);
92 for (let i = 0z; i < len(std.encmap); i += 1) {
93 assert(std.encmap[i] == std_encoding.encmap[i]);
94 };
95 for (let i = 0z; i < len(std.decmap); i += 1) {
96 assert(std.decmap[i] == std_encoding.decmap[i]);
97 };
98
99 let url = encoding { ... };
100 const url_alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";
101 encoding_init(&url, url_alpha);
102 for (let i = 0z; i < len(url.encmap); i += 1) {
103 assert(url.encmap[i] == url_encoding.encmap[i]);
104 };
105 for (let i = 0z; i < len(url.decmap); i += 1) {
106 assert(url.decmap[i] == url_encoding.decmap[i]);
107 };
108 };
109
110 export type encoder = struct {
111 stream: io::stream,
112 out: io::handle,
113 enc: *encoding,
114 ibuf: [3]u8,
115 obuf: [4]u8,
116 iavail: u8,
117 oavail: u8,
118 };
119
120 const encoder_vtable: io::vtable = io::vtable {
121 writer = &encode_writer,
122 closer = &encode_closer,
123 ...
124 };
125
126 // Creates a stream that encodes writes as base64 before writing them to a
127 // secondary stream. Afterwards [[io::close]] must be called to write any
128 // unwritten bytes, in case of padding. Closing this stream will not close the
129 // underlying stream. After a write returns an error, the stream must not be
130 // written to again or closed.
131 export fn newencoder(
132 enc: *encoding,
133 out: io::handle,
134 ) encoder = {
135 return encoder {
136 stream = &encoder_vtable,
137 out = out,
138 enc = enc,
139 ...
140 };
141 };
142
143 fn encode_writer(
144 s: *io::stream,
145 in: const []u8
146 ) (size | io::error) = {
147 let s = s: *encoder;
148 let i = 0z;
149 for (i < len(in)) {
150 let b = s.ibuf[..];
151 // fill ibuf
152 for (let j = s.iavail; j < 3 && i < len(in); j += 1) {
153 b[j] = in[i];
154 i += 1;
155 s.iavail += 1;
156 };
157
158 if (s.iavail != 3) {
159 return i;
160 };
161
162 fillobuf(s);
163
164 match (writeavail(s)) {
165 case let e: io::error =>
166 if (i == 0) {
167 return e;
168 };
169 return i;
170 case void => void;
171 };
172 };
173
174 return i;
175 };
176
177 fn fillobuf(s: *encoder) void = {
178 assert(s.iavail == 3);
179 let b = s.ibuf[..];
180 s.obuf[..] = [
181 s.enc.encmap[b[0] >> 2],
182 s.enc.encmap[(b[0] & 0x3) << 4 | b[1] >> 4],
183 s.enc.encmap[(b[1] & 0xf) << 2 | b[2] >> 6],
184 s.enc.encmap[b[2] & 0x3f],
185 ][..];
186 s.oavail = 4;
187 };
188
189 fn writeavail(s: *encoder) (void | io::error) = {
190 if (s.oavail == 0) {
191 return;
192 };
193
194 for (s.oavail > 0) {
195 let n = io::write(s.out, s.obuf[len(s.obuf) - s.oavail..])?;
196 s.oavail -= n: u8;
197 };
198
199 if (s.oavail == 0) {
200 s.iavail = 0;
201 };
202 };
203
204 // Flushes pending writes to the underlying stream.
205 fn encode_closer(s: *io::stream) (void | io::error) = {
206 let s = s: *encoder;
207 let finished = false;
208 defer if (finished) clear(s);
209
210 if (s.oavail > 0) {
211 for (s.oavail > 0) {
212 writeavail(s)?;
213 };
214 finished = true;
215 return;
216 };
217
218 if (s.iavail == 0) {
219 finished = true;
220 return;
221 };
222
223 // prepare padding as input length was not a multiple of 3
224 // 0 1 2
225 static const npa: []u8 = [0, 2, 1];
226 const np = npa[s.iavail];
227
228 for (let i = s.iavail; i < 3; i += 1) {
229 s.ibuf[i] = 0;
230 s.iavail += 1;
231 };
232
233 fillobuf(s);
234 for (let i = 0z; i < np; i += 1) {
235 s.obuf[3 - i] = PADDING;
236 };
237
238 for (s.oavail > 0) {
239 writeavail(s)?;
240 };
241 finished = true;
242 };
243
244 fn clear(e: *encoder) void = {
245 bytes::zero(e.ibuf);
246 bytes::zero(e.obuf);
247 };
248
249 @test fn partialwrite() void = {
250 const raw: [_]u8 = [
251 0x00, 0x00, 0x00, 0x07, 0x73, 0x73, 0x68, 0x2d, 0x72, 0x73,
252 0x61, 0x00,
253 ];
254 const expected: str = `AAAAB3NzaC1yc2EA`;
255
256 let buf = memio::dynamic();
257 let e = newencoder(&std_encoding, &buf);
258 io::writeall(&e, raw[..4])!;
259 io::writeall(&e, raw[4..11])!;
260 io::writeall(&e, raw[11..])!;
261 io::close(&e)!;
262
263 assert(memio::string(&buf)! == expected);
264
265 let encb = memio::buffer(&buf);
266 free(encb);
267 };
268
269 // Encodes a byte slice in base 64, using the given encoding, returning a slice
270 // of ASCII bytes. The caller must free the return value.
271 export fn encodeslice(enc: *encoding, in: []u8) ([]u8 | nomem) = {
272 let out = memio::dynamic();
273 let encoder = newencoder(enc, &out);
274 match (io::writeall(&encoder, in)) {
275 case size => void;
276 case nomem =>
277 io::close(&out)!;
278 return nomem;
279 case => abort(); // unreachable
280 };
281 match (io::close(&encoder)) {
282 case void => void;
283 case nomem =>
284 io::close(&out)!;
285 return nomem;
286 case => abort(); // unreachable
287 };
288 return memio::buffer(&out);
289 };
290
291 // Encodes base64 data using the given alphabet and writes it to a stream,
292 // returning the number of bytes of data written (i.e. len(buf)).
293 export fn encode(
294 out: io::handle,
295 enc: *encoding,
296 buf: []u8,
297 ) (size | io::error) = {
298 const enc = newencoder(enc, out);
299 match (io::writeall(&enc, buf)) {
300 case let z: size =>
301 io::close(&enc)?;
302 return z;
303 case let err: io::error =>
304 clear(&enc);
305 return err;
306 };
307 };
308
309 // Encodes a byte slice in base 64, using the given encoding, returning a
310 // string. The caller must free the return value.
311 export fn encodestr(enc: *encoding, in: []u8) (str | nomem) = {
312 return strings::fromutf8(encodeslice(enc, in)?)!;
313 };
314
315 @test fn encode() void = {
316 // RFC 4648 test vectors
317 const in: [_]u8 = ['f', 'o', 'o', 'b', 'a', 'r'];
318 const expect: [_]str = [
319 "",
320 "Zg==",
321 "Zm8=",
322 "Zm9v",
323 "Zm9vYg==",
324 "Zm9vYmE=",
325 "Zm9vYmFy"
326 ];
327 for (let i = 0z; i <= len(in); i += 1) {
328 let out = memio::dynamic();
329 let encoder = newencoder(&std_encoding, &out);
330 io::writeall(&encoder, in[..i])!;
331 io::close(&encoder)!;
332 let encb = memio::buffer(&out);
333 defer free(encb);
334 assert(bytes::equal(encb, strings::toutf8(expect[i])));
335
336 // Testing encodestr should cover encodeslice too
337 let s = encodestr(&std_encoding, in[..i])!;
338 defer free(s);
339 assert(s == expect[i]);
340 };
341 };
342
343 export type decoder = struct {
344 stream: io::stream,
345 in: io::handle,
346 enc: *encoding,
347 obuf: [3]u8, // leftover decoded output
348 ibuf: [4]u8,
349 iavail: u8,
350 oavail: u8,
351 pad: bool, // if padding was seen in a previous read
352 };
353
354 const decoder_vtable: io::vtable = io::vtable {
355 reader = &decode_reader,
356 ...
357 };
358
359 // Creates a stream that reads and decodes base 64 data from a secondary stream.
360 // This stream does not need to be closed, and closing it will not close the
361 // underlying stream. If a read returns an error, the stream must not be read
362 // from again.
363 export fn newdecoder(
364 enc: *encoding,
365 in: io::handle,
366 ) decoder = {
367 return decoder {
368 stream = &decoder_vtable,
369 in = in,
370 enc = enc,
371 ...
372 };
373 };
374
375 fn decode_reader(
376 s: *io::stream,
377 out: []u8
378 ) (size | io::EOF | io::error) = {
379 let s = s: *decoder;
380 if (len(out) == 0) {
381 return 0z;
382 };
383 let n = 0z;
384 if (s.oavail != 0) {
385 if (len(out) <= s.oavail) {
386 out[..] = s.obuf[..len(out)];
387 s.obuf[..len(s.obuf) - len(out)] = s.obuf[len(out)..];
388 s.oavail = s.oavail - len(out): u8;
389 return len(out);
390 };
391 n = s.oavail;
392 s.oavail = 0;
393 out[..n] = s.obuf[..n];
394 out = out[n..];
395 };
396 let buf: [os::BUFSZ]u8 = [0...];
397 buf[..s.iavail] = s.ibuf[..s.iavail];
398
399 let want = encodedsize(len(out));
400 let nr = s.iavail: size;
401 let lim = if (want > len(buf)) len(buf) else want;
402 match (io::readall(s.in, buf[s.iavail..lim])) {
403 case let n: size =>
404 nr += n;
405 case io::EOF =>
406 return if (s.iavail != 0) errors::invalid
407 else if (n != 0) n
408 else io::EOF;
409 case let err: io::error =>
410 if (!(err is io::underread)) {
411 return err;
412 };
413 nr += err: io::underread;
414 };
415 if (s.pad) {
416 return errors::invalid;
417 };
418 s.iavail = nr: u8 % 4;
419 s.ibuf[..s.iavail] = buf[nr - s.iavail..nr];
420 nr -= s.iavail;
421 if (nr == 0) {
422 return 0z;
423 };
424 // Validating read buffer
425 let np = 0z; // Number of padding chars.
426 for (let i = 0z; i < nr; i += 1) {
427 if (buf[i] == PADDING) {
428 for (i + np < nr; np += 1) {
429 if (np > 2 || buf[i + np] != PADDING) {
430 return errors::invalid;
431 };
432 };
433 s.pad = true;
434 break;
435 };
436 if (!ascii::valid(buf[i]: u32: rune)
437 || s.enc.decmap[buf[i]] == 0xff) {
438 return errors::invalid;
439 };
440 buf[i] = s.enc.decmap[buf[i]];
441 };
442
443 if (nr / 4 * 3 - np < len(out)) {
444 out = out[..nr / 4 * 3 - np];
445 };
446 let i = 0z, j = 0z;
447 nr -= 4;
448 for (i < nr) {
449 out[j ] = buf[i ] << 2 | buf[i + 1] >> 4;
450 out[j + 1] = buf[i + 1] << 4 | buf[i + 2] >> 2;
451 out[j + 2] = buf[i + 2] << 6 | buf[i + 3];
452
453 i += 4;
454 j += 3;
455 };
456 s.obuf = [
457 buf[i ] << 2 | buf[i + 1] >> 4,
458 buf[i + 1] << 4 | buf[i + 2] >> 2,
459 buf[i + 2] << 6 | buf[i + 3],
460 ];
461 out[j..] = s.obuf[..len(out) - j];
462 s.oavail = (len(s.obuf) - (len(out) - j)): u8;
463 s.obuf[..s.oavail] = s.obuf[len(s.obuf) - s.oavail..];
464 s.oavail -= np: u8;
465 return n + len(out);
466 };
467
468 // Decodes a byte slice of ASCII-encoded base 64 data, using the given encoding,
469 // returning a slice of decoded bytes. The caller must free the return value.
470 export fn decodeslice(
471 enc: *encoding,
472 in: []u8,
473 ) ([]u8 | errors::invalid | nomem) = {
474 if (len(in) == 0) {
475 return [];
476 };
477 if (len(in) % 4 != 0) {
478 return errors::invalid;
479 };
480 let ins = memio::fixed(in);
481 let decoder = newdecoder(enc, &ins);
482 let out = alloc([0u8...], decodedsize(len(in)))?;
483 let outs = memio::fixed(out);
484 match (io::copy(&outs, &decoder)) {
485 case nomem =>
486 free(out);
487 return nomem;
488 case errors::invalid =>
489 free(out);
490 return errors::invalid;
491 case let sz: size =>
492 return memio::buffer(&outs)[..sz];
493 case => abort(); // unreachable
494 };
495 };
496
497 // Decodes a string of ASCII-encoded base 64 data, using the given encoding,
498 // returning a slice of decoded bytes. The caller must free the return value.
499 export fn decodestr(enc: *encoding, in: str) ([]u8 | errors::invalid | nomem) = {
500 return decodeslice(enc, strings::toutf8(in));
501 };
502
503 // Decodes base64 data from a stream using the given alphabet, returning the
504 // number of bytes of bytes read (i.e. len(buf)).
505 export fn decode(
506 in: io::handle,
507 enc: *encoding,
508 buf: []u8,
509 ) (size | io::EOF | io::error) = {
510 const dec = newdecoder(enc, in);
511 return io::readall(&dec, buf);
512 };
513
514 @test fn decode() void = {
515 // RFC 4648 test vectors
516 const cases: [_](str, str, *encoding) = [
517 ("", "", &std_encoding),
518 ("Zg==", "f", &std_encoding),
519 ("Zm8=", "fo", &std_encoding),
520 ("Zm9v", "foo", &std_encoding),
521 ("Zm9vYg==", "foob", &std_encoding),
522 ("Zm9vYmE=", "fooba", &std_encoding),
523 ("Zm9vYmFy", "foobar", &std_encoding),
524 ];
525 const invalid: [_](str, *encoding) = [
526 // invalid padding
527 ("=", &std_encoding),
528 ("==", &std_encoding),
529 ("===", &std_encoding),
530 ("=====", &std_encoding),
531 ("======", &std_encoding),
532 // invalid characters
533 ("@Zg=", &std_encoding),
534 ("ê==", &std_encoding),
535 ("êg==", &std_encoding),
536 ("$3d==", &std_encoding),
537 ("%3d==", &std_encoding),
538 ("[==", &std_encoding),
539 ("!", &std_encoding),
540 // data after padding is encountered
541 ("Zg===", &std_encoding),
542 ("Zg====", &std_encoding),
543 ("Zg==Zg==", &std_encoding),
544 ("Zm8=Zm8=", &std_encoding),
545 ];
546 let buf: [12]u8 = [0...];
547 for (let bufsz = 1z; bufsz <= 12; bufsz += 1) {
548 for (let (input, expected, encoding) .. cases) {
549 let in = memio::fixed(strings::toutf8(input));
550 let decoder = newdecoder(encoding, &in);
551 let buf = buf[..bufsz];
552 let decb: []u8 = [];
553 defer free(decb);
554 for (true) match (io::read(&decoder, buf)!) {
555 case let z: size =>
556 if (z > 0) {
557 append(decb, buf[..z]...)!;
558 };
559 case io::EOF =>
560 break;
561 };
562 assert(bytes::equal(decb, strings::toutf8(expected)));
563
564 // Testing decodestr should cover decodeslice too
565 let decb = decodestr(encoding, input) as []u8;
566 defer free(decb);
567 assert(bytes::equal(decb, strings::toutf8(expected)));
568 };
569
570 for (let (input, encoding) .. invalid) {
571 let in = memio::fixed(strings::toutf8(input));
572 let decoder = newdecoder(encoding, &in);
573 let buf = buf[..bufsz];
574 let valid = false;
575 for (true) match(io::read(&decoder, buf)) {
576 case errors::invalid =>
577 break;
578 case size =>
579 void;
580 case io::EOF =>
581 abort();
582 };
583
584 // Testing decodestr should cover decodeslice too
585 assert(decodestr(encoding, input) is errors::invalid);
586 };
587 };
588 };
589
590 // Given the length of the message, returns the size of its base64 encoding
591 export fn encodedsize(sz: size) size = if (sz == 0) 0 else ((sz - 1)/ 3 + 1) * 4;
592
593 // Given the size of base64 encoded data, returns maximal length of decoded message.
594 // The message may be at most 2 bytes shorter than the returned value. Input
595 // size must be a multiple of 4.
596 export fn decodedsize(sz: size) size = {
597 assert(sz % 4 == 0);
598 return sz / 4 * 3;
599 };
600
601 @test fn sizecalc() void = {
602 let enc: [_](size, size) = [(1, 4), (2, 4), (3, 4), (4, 8), (10, 16),
603 (119, 160), (120, 160), (121, 164), (122, 164), (123, 164)
604 ];
605 assert(encodedsize(0) == 0 && decodedsize(0) == 0);
606 for (let i = 0z; i < len(enc); i += 1) {
607 let (decoded, encoded) = enc[i];
608 assert(encodedsize(decoded) == encoded);
609 assert(decodedsize(encoded) == ((decoded - 1) / 3 + 1) * 3);
610 };
611 };