1	import Base
2	import ./bytes.bend as B
3	
4	type B64.Alpha is Data:
5	  B64Std{}
6	  B64Url{}
7	
8	type B64.Pad is Data:
9	  B64Pad{}
10	  B64Raw{}
11	
12	type B64.G is Data:
13	  G0{}
14	  G1{}
15	  G2{}
16	
17	type B64.D is Data:
18	  D0{}
19	  D1{a: U32}
20	  D2{a: U32, b: U32}
21	  D3{a: U32, b: U32, c: U32}
22	  Eq1{a: U32, b: U32}
23	  PadEnd{}
24	
25	type B64.Tok is Data:
26	  TokVal{n: U32}
27	  TokPad{}
28	  TokBad{c: Char}
29	
30	type Base64.Error is Data:
31	  InvalidChar{offset: Nat, char: Char}
32	  InvalidLength{offset: Nat}
33	  NonCanonical{offset: Nat}
34	  InvalidByte{index: Nat, value: U32}
35	
36	def Base64.from_bytes_err(e: B.Bytes.Error) -> Base64.Error:
37	  match e:
38	    case B.InvalidByte{index, value}:
39	      InvalidByte{index, value}
40	
41	def B64.ch.62(alpha: B64.Alpha) -> Char:
42	  match alpha:
43	    case B64Std{}:
44	      '+'
45	    case B64Url{}:
46	      '-'
47	
48	def B64.ch.63(alpha: B64.Alpha) -> Char:
49	  match alpha:
50	    case B64Std{}:
51	      '/'
52	    case B64Url{}:
53	      '_'
54	
55	def B64.ch.pm(+alpha: B64.Alpha, is62: Bool) -> Char:
56	  match is62:
57	    case True{}:
58	      B64.ch.62(alpha)
59	    case False{}:
60	      B64.ch.63(alpha)
61	
62	def B64.ch.lt62(+n: U32, lt: Bool, +alpha: B64.Alpha) -> Char:
63	  match lt:
64	    case True{}:
65	      Char.from_u32((Char.to_u32('0') + (n - 52 : U32) : U32))
66	    case False{}:
67	      B64.ch.pm(alpha, U32.is_eq(n, 62))
68	
69	def B64.ch.lt52(+n: U32, lt: Bool, +alpha: B64.Alpha) -> Char:
70	  match lt:
71	    case True{}:
72	      Char.from_u32((Char.to_u32('a') + (n - 26 : U32) : U32))
73	    case False{}:
74	      B64.ch.lt62(n, U32.is_lt(n, 62), alpha)
75	
76	def B64.ch.lt26(+n: U32, lt: Bool, +alpha: B64.Alpha) -> Char:
77	  match lt:
78	    case True{}:
79	      Char.from_u32((Char.to_u32('A') + n : U32))
80	    case False{}:
81	      B64.ch.lt52(n, U32.is_lt(n, 52), alpha)
82	
83	def B64.ch(+n: U32, +alpha: B64.Alpha) -> Char:
84	  B64.ch.lt26(n, U32.is_lt(n, 26), alpha)
85	
86	def B64.push4(
87	  s0: U32, s1: U32, s2: U32, s3: U32, acc: String, +alpha: B64.Alpha
88	) -> String:
89	  SCon{
90	    B64.ch(s3, alpha),
91	    SCon{
92	      B64.ch(s2, alpha),
93	      SCon{B64.ch(s1, alpha), SCon{B64.ch(s0, alpha), acc}}
94	    }
95	  }
96	
97	def B64.emit3(+a: U32, +b: U32, +c: U32, acc: String, +alpha: B64.Alpha) -> String:
98	  B64.push4(
99	    U32.shrn(a, 2n),
100	    U32.or(U32.shln(U32.and(a, 3), 4n), U32.shrn(b, 4n)),
101	    U32.or(U32.shln(U32.and(b, 15), 2n), U32.shrn(c, 6n)),
102	    U32.and(c, 63),
103	    acc,
104	    alpha
105	  )
106	
107	def B64.pad1.fin(
108	  s0: U32, s1: U32, acc: String, +alpha: B64.Alpha, pad: B64.Pad
109	) -> String:
110	  match pad:
111	    case B64Pad{}:
112	      SCon{
113	        '=', SCon{'=', SCon{B64.ch(s1, alpha), SCon{B64.ch(s0, alpha), acc}}}
114	      }
115	    case B64Raw{}:
116	      SCon{B64.ch(s1, alpha), SCon{B64.ch(s0, alpha), acc}}
117	
118	def B64.pad1(+a: U32, acc: String, +alpha: B64.Alpha, pad: B64.Pad) -> String:
119	  B64.pad1.fin(U32.shrn(a, 2n), U32.shln(U32.and(a, 3), 4n), acc, alpha, pad)
120	
121	def B64.pad2.fin(
122	  s0: U32, s1: U32, s2: U32, acc: String, +alpha: B64.Alpha, pad: B64.Pad
123	) -> String:
124	  match pad:
125	    case B64Pad{}:
126	      SCon{
127	        '=',
128	        SCon{
129	          B64.ch(s2, alpha),
130	          SCon{B64.ch(s1, alpha), SCon{B64.ch(s0, alpha), acc}}
131	        }
132	      }
133	    case B64Raw{}:
134	      SCon{
135	        B64.ch(s2, alpha), SCon{B64.ch(s1, alpha), SCon{B64.ch(s0, alpha), acc}}
136	      }
137	
138	def B64.pad2(+a: U32, +b: U32, acc: String, +alpha: B64.Alpha, pad: B64.Pad) -> String:
139	  B64.pad2.fin(
140	    U32.shrn(a, 2n),
141	    U32.or(U32.shln(U32.and(a, 3), 4n), U32.shrn(b, 4n)),
142	    U32.shln(U32.and(b, 15), 2n),
143	    acc,
144	    alpha,
145	    pad
146	  )
147	
148	def Base64.encode.go(
149	  xs: List<&2, U32>, phase: B64.G, a: U32, b: U32, acc: String,
150	  +alpha: B64.Alpha, +pad: B64.Pad
151	) -> String:
152	  match xs phase:
153	    case Nil{} G0{}:
154	      String.reverse(acc)
155	    case Nil{} G1{}:
156	      String.reverse(B64.pad1(a, acc, alpha, pad))
157	    case Nil{} G2{}:
158	      String.reverse(B64.pad2(a, b, acc, alpha, pad))
159	    case Con{+h, t} G0{}:
160	      Base64.encode.go(t, G1{}, h, 0, acc, alpha, pad)
161	    case Con{+h, t} G1{}:
162	      Base64.encode.go(t, G2{}, a, h, acc, alpha, pad)
163	    case Con{+h, t} G2{}:
164	      Base64.encode.go(t, G0{}, 0, 0, B64.emit3(a, b, h, acc, alpha), alpha, pad)
165	
166	def Base64.encode.with(bytes: B.Bytes, +alpha: B64.Alpha, +pad: B64.Pad) -> String:
167	  match bytes:
168	    case B.Bytes{data}:
169	      Base64.encode.go(data, G0{}, 0, 0, SNil{}, alpha, pad)
170	
171	def Base64.encode(bytes: B.Bytes) -> String:
172	  Base64.encode.with(bytes, B64Std{}, B64Pad{})
173	
174	def Base64Url.encode.p(bytes: B.Bytes, padded: Bool) -> String:
175	  match padded:
176	    case True{}:
177	      Base64.encode.with(bytes, B64Url{}, B64Pad{})
178	    case False{}:
179	      Base64.encode.with(bytes, B64Url{}, B64Raw{})
180	
181	def Base64Url.encode(bytes: B.Bytes, padded: Bool) -> String:
182	  Base64Url.encode.p(bytes, padded)
183	
184	def B64.tok.under.yes(alpha: B64.Alpha, +c: Char) -> B64.Tok:
185	  match alpha:
186	    case B64Url{}:
187	      TokVal{63}
188	    case B64Std{}:
189	      TokBad{c}
190	
191	def B64.tok.under(under: Bool, alpha: B64.Alpha, +c: Char) -> B64.Tok:
192	  match under:
193	    case False{}:
194	      TokBad{c}
195	    case True{}:
196	      B64.tok.under.yes(alpha, c)
197	
198	def B64.tok.minus.yes(alpha: B64.Alpha, +c: Char) -> B64.Tok:
199	  match alpha:
200	    case B64Url{}:
201	      TokVal{62}
202	    case B64Std{}:
203	      TokBad{c}
204	
205	def B64.tok.minus(minus: Bool, +alpha: B64.Alpha, +c: Char) -> B64.Tok:
206	  match minus:
207	    case True{}:
208	      B64.tok.minus.yes(alpha, c)
209	    case False{}:
210	      B64.tok.under(Char.is_eq(c, '_'), alpha, c)
211	
212	def B64.tok.slash.yes(alpha: B64.Alpha, +c: Char) -> B64.Tok:
213	  match alpha:
214	    case B64Std{}:
215	      TokVal{63}
216	    case B64Url{}:
217	      TokBad{c}
218	
219	def B64.tok.slash(slash: Bool, +alpha: B64.Alpha, +c: Char) -> B64.Tok:
220	  match slash:
221	    case True{}:
222	      B64.tok.slash.yes(alpha, c)
223	    case False{}:
224	      B64.tok.minus(Char.is_eq(c, '-'), alpha, c)
225	
226	def B64.tok.plus.yes(alpha: B64.Alpha, +c: Char) -> B64.Tok:
227	  match alpha:
228	    case B64Std{}:
229	      TokVal{62}
230	    case B64Url{}:
231	      TokBad{c}
232	
233	def B64.tok.plus(plus: Bool, +alpha: B64.Alpha, +c: Char) -> B64.Tok:
234	  match plus:
235	    case True{}:
236	      B64.tok.plus.yes(alpha, c)
237	    case False{}:
238	      B64.tok.slash(Char.is_eq(c, '/'), alpha, c)
239	
240	def B64.tok.sym(+c: Char, +alpha: B64.Alpha) -> B64.Tok:
241	  B64.tok.plus(Char.is_eq(c, '+'), alpha, c)
242	
243	def B64.tok.az2(+x: U32, +c: Char, +alpha: B64.Alpha, le: Bool) -> B64.Tok:
244	  match le:
245	    case True{}:
246	      TokVal{(x - Char.to_u32('G') : U32)}
247	    case False{}:
248	      B64.tok.sym(c, alpha)
249	
250	def B64.tok.az(+x: U32, +c: Char, +alpha: B64.Alpha, ge: Bool) -> B64.Tok:
251	  match ge:
252	    case False{}:
253	      B64.tok.sym(c, alpha)
254	    case True{}:
255	      B64.tok.az2(x, c, alpha, U32.is_le(x, Char.to_u32('z')))
256	
257	def B64.tok.AZ2(+x: U32, +c: Char, +alpha: B64.Alpha, le: Bool) -> B64.Tok:
258	  match le:
259	    case True{}:
260	      TokVal{(x - Char.to_u32('A') : U32)}
261	    case False{}:
262	      B64.tok.az(x, c, alpha, U32.is_ge(x, Char.to_u32('a')))
263	
264	def B64.tok.AZ(+x: U32, +c: Char, +alpha: B64.Alpha, ge: Bool) -> B64.Tok:
265	  match ge:
266	    case False{}:
267	      B64.tok.az(x, c, alpha, U32.is_ge(x, Char.to_u32('a')))
268	    case True{}:
269	      B64.tok.AZ2(x, c, alpha, U32.is_le(x, Char.to_u32('Z')))
270	
271	def B64.tok.d092(+x: U32, +c: Char, +alpha: B64.Alpha, le: Bool) -> B64.Tok:
272	  match le:
273	    case True{}:
274	      TokVal{(x - Char.to_u32('0') + 52 : U32)}
275	    case False{}:
276	      B64.tok.AZ(x, c, alpha, U32.is_ge(x, Char.to_u32('A')))
277	
278	def B64.tok.d09(+x: U32, +c: Char, +alpha: B64.Alpha, ge: Bool) -> B64.Tok:
279	  match ge:
280	    case False{}:
281	      B64.tok.AZ(x, c, alpha, U32.is_ge(x, Char.to_u32('A')))
282	    case True{}:
283	      B64.tok.d092(x, c, alpha, U32.is_le(x, Char.to_u32('9')))
284	
285	def B64.tok.eq(+x: U32, +c: Char, +alpha: B64.Alpha, eq: Bool) -> B64.Tok:
286	  match eq:
287	    case True{}:
288	      TokPad{}
289	    case False{}:
290	      B64.tok.d09(x, c, alpha, U32.is_ge(x, Char.to_u32('0')))
291	
292	def B64.tok.u(+x: U32, +c: Char, +alpha: B64.Alpha) -> B64.Tok:
293	  B64.tok.eq(x, c, alpha, U32.is_eq(x, Char.to_u32('=')))
294	
295	def B64.tok(+c: Char, +alpha: B64.Alpha) -> B64.Tok:
296	  B64.tok.u(Char.to_u32(c), c, alpha)
297	
298	def B64.zero4(b: U32) -> Bool:
299	  U32.is_eq(U32.and(b, 15), 0)
300	
301	def B64.zero2(c: U32) -> Bool:
302	  U32.is_eq(U32.and(c, 3), 0)
303	
304	def B64.byte1(+a: U32, +b: U32) -> U32:
305	  U32.or(U32.shln(a, 2n), U32.shrn(b, 4n))
306	
307	def B64.byte2(+b: U32, +c: U32) -> U32:
308	  U32.or(U32.shln(U32.and(b, 15), 4n), U32.shrn(c, 2n))
309	
310	def B64.byte3(+c: U32, d: U32) -> U32:
311	  U32.or(U32.shln(U32.and(c, 3), 6n), d)
312	
313	def B64.fin1(
314	  ok: Bool, +a: U32, +b: U32, acc: List<&2, U32>, off: Nat
315	) -> Result<&2, &2, Base64.Error, B.Bytes>:
316	  match ok:
317	    case False{}:
318	      Fail{NonCanonical{off}}
319	    case True{}:
320	      Done{B.Bytes{List.reverse(&2, U32, Con{B64.byte1(a, b), acc})}}
321	
322	def B64.fin1.from(+a: U32, +b: U32, acc: List<&2, U32>, off: Nat) ->
323	  Result<&2, &2, Base64.Error, B.Bytes>:
324	  B64.fin1(B64.zero4(b), a, b, acc, off)
325	
326	def B64.fin2(
327	  ok: Bool, +a: U32, +b: U32, +c: U32, acc: List<&2, U32>, off: Nat
328	) -> Result<&2, &2, Base64.Error, B.Bytes>:
329	  match ok:
330	    case False{}:
331	      Fail{NonCanonical{off}}
332	    case True{}:
333	      Done{
334	        B.Bytes{
335	          List.reverse(
336	            &2, U32, Con{B64.byte2(b, c), Con{B64.byte1(a, b), acc}}
337	          )
338	        }
339	      }
340	
341	def B64.fin2.from(+a: U32, +b: U32, +c: U32, acc: List<&2, U32>, off: Nat) ->
342	  Result<&2, &2, Base64.Error, B.Bytes>:
343	  B64.fin2(B64.zero2(c), a, b, c, acc, off)
344	
345	def B64.emit2(+a: U32, +b: U32, +c: U32, acc: List<&2, U32>) -> List<&2, U32>:
346	  Con{B64.byte2(b, c), Con{B64.byte1(a, b), acc}}
347	
348	def B64.emit4(
349	  +a: U32, +b: U32, +c: U32, d: U32, acc: List<&2, U32>
350	) -> List<&2, U32>:
351	  Con{B64.byte3(c, d), Con{B64.byte2(b, c), Con{B64.byte1(a, b), acc}}}
352	
353	def Base64.decode.go(
354	  s: String, tok: B64.Tok, st: B64.D, pad: B64.Pad, acc: List<&2, U32>,
355	  off: Nat, +alpha: B64.Alpha
356	) -> Result<&2, &2, Base64.Error, B.Bytes>:
357	  match s tok st pad:
358	    case _ TokBad{c} _ _:
359	      Fail{InvalidChar{off, c}}
360	    case SNil{} TokVal{n} D0{} _:
361	      Fail{InvalidLength{off}}
362	    case SNil{} TokVal{n} D1{a} B64Raw{}:
363	      B64.fin1.from(a, n, acc, off)
364	    case SNil{} TokVal{_} D1{_} B64Pad{}:
365	      Fail{InvalidLength{off}}
366	    case SNil{} TokVal{n} D2{a, b} B64Raw{}:
367	      B64.fin2.from(a, b, n, acc, off)
368	    case SNil{} TokVal{_} D2{_, _} B64Pad{}:
369	      Fail{InvalidLength{off}}
370	    case SNil{} TokVal{n} D3{a, b, c} _:
371	      Done{B.Bytes{List.reverse(&2, U32, B64.emit4(a, b, c, n, acc))}}
372	    case SNil{} TokPad{} D2{a, b} B64Pad{}:
373	      Fail{InvalidLength{off}}
374	    case SNil{} TokPad{} D3{a, b, c} B64Pad{}:
375	      B64.fin2.from(a, b, c, acc, off)
376	    case SNil{} TokPad{} Eq1{a, b} B64Pad{}:
377	      B64.fin1.from(a, b, acc, off)
378	    case SNil{} TokPad{} PadEnd{} B64Pad{}:
379	      Fail{InvalidLength{off}}
380	    case SNil{} TokPad{} _ _:
381	      Fail{InvalidLength{off}}
382	    case SNil{} TokVal{_} Eq1{_, _} _:
383	      Fail{InvalidLength{off}}
384	    case SNil{} TokVal{_} PadEnd{} _:
385	      Fail{InvalidLength{off}}
386	    case SCon{+h, t} TokVal{n} D0{} p:
387	      Base64.decode.go(t, B64.tok(h, alpha), D1{n}, p, acc, 1n+off, alpha)
388	    case SCon{+h, t} TokVal{n} D1{a} p:
389	      Base64.decode.go(t, B64.tok(h, alpha), D2{a, n}, p, acc, 1n+off, alpha)
390	    case SCon{+h, t} TokVal{n} D2{a, b} p:
391	      Base64.decode.go(t, B64.tok(h, alpha), D3{a, b, n}, p, acc, 1n+off, alpha)
392	    case SCon{+h, t} TokVal{n} D3{a, b, c} p:
393	      Base64.decode.go(
394	        t, B64.tok(h, alpha), D0{}, p, B64.emit4(a, b, c, n, acc), 1n+off, alpha
395	      )
396	    case SCon{+h, t} TokPad{} D2{a, b} B64Pad{}:
397	      Base64.decode.go(t, B64.tok(h, alpha), Eq1{a, b}, B64Pad{}, acc, 1n+off, alpha)
398	    case SCon{+h, t} TokPad{} D3{a, b, c} B64Pad{}:
399	      Base64.decode.go(
400	        t, B64.tok(h, alpha), PadEnd{}, B64Pad{},
401	        B64.emit2(a, b, c, acc), 1n+off, alpha
402	      )
403	    case SCon{+h, t} TokPad{} Eq1{a, b} B64Pad{}:
404	      Base64.decode.go(
405	        t, B64.tok(h, alpha), PadEnd{}, B64Pad{},
406	        Con{B64.byte1(a, b), acc}, 1n+off, alpha
407	      )
408	    case SCon{_, _} TokPad{} D0{} _:
409	      Fail{InvalidChar{off, '='}}
410	    case SCon{_, _} TokPad{} D1{_} _:
411	      Fail{InvalidChar{off, '='}}
412	    case SCon{_, _} TokPad{} PadEnd{} _:
413	      Fail{InvalidChar{off, '='}}
414	    case SCon{_, _} TokVal{_} Eq1{_, _} _:
415	      Fail{InvalidChar{off, '='}}
416	    case SCon{_, _} TokVal{_} PadEnd{} _:
417	      Fail{InvalidLength{off}}
418	    case SCon{_, _} TokPad{} D2{_, _} B64Raw{}:
419	      Fail{InvalidChar{off, '='}}
420	    case SCon{_, _} TokPad{} D3{_, _, _} B64Raw{}:
421	      Fail{InvalidChar{off, '='}}
422	    case SCon{_, _} TokPad{} Eq1{_, _} B64Raw{}:
423	      Fail{InvalidChar{off, '='}}
424	
425	def Base64.decode.start(
426	  s: String, +alpha: B64.Alpha, +pad: B64.Pad
427	) -> Result<&2, &2, Base64.Error, B.Bytes>:
428	  match s:
429	    case SNil{}:
430	      Done{B.Bytes{Nil{}}}
431	    case SCon{+h, t}:
432	      Base64.decode.go(t, B64.tok(h, alpha), D0{}, pad, Nil{}, 0n, alpha)
433	
434	def Base64.decode(text: String) -> Result<&2, &2, Base64.Error, B.Bytes>:
435	  Base64.decode.start(text, B64Std{}, B64Pad{})
436	
437	def Base64Url.decode.p(
438	  text: String, padded: Bool
439	) -> Result<&2, &2, Base64.Error, B.Bytes>:
440	  match padded:
441	    case True{}:
442	      Base64.decode.start(text, B64Url{}, B64Pad{})
443	    case False{}:
444	      Base64.decode.start(text, B64Url{}, B64Raw{})
445	
446	def Base64Url.decode(
447	  text: String, padded: Bool
448	) -> Result<&2, &2, Base64.Error, B.Bytes>:
449	  Base64Url.decode.p(text, padded)
450	
451	def Base64.encode_u32_list.from(
452	  r: Result<&2, &2, B.Bytes.Error, B.Bytes>
453	) -> Result<&2, &2, Base64.Error, String>:
454	  match r:
455	    case Fail{e}:
456	      Fail{Base64.from_bytes_err(e)}
457	    case Done{b}:
458	      Done{Base64.encode(b)}
459	
460	def Base64.encode_u32_list(
461	  values: List<&2, U32>
462	) -> Result<&2, &2, Base64.Error, String>:
463	  Base64.encode_u32_list.from(B.Bytes.from_u32_list(values))
464	
465	def Base64Url.encode_u32_list.from(
466	  r: Result<&2, &2, B.Bytes.Error, B.Bytes>, padded: Bool
467	) -> Result<&2, &2, Base64.Error, String>:
468	  match r:
469	    case Fail{e}:
470	      Fail{Base64.from_bytes_err(e)}
471	    case Done{b}:
472	      Done{Base64Url.encode(b, padded)}
473	
474	def Base64Url.encode_u32_list(
475	  values: List<&2, U32>, padded: Bool
476	) -> Result<&2, &2, Base64.Error, String>:
477	  Base64Url.encode_u32_list.from(B.Bytes.from_u32_list(values), padded)
478	
479	def Base64.decode_u32_list.from(
480	  r: Result<&2, &2, Base64.Error, B.Bytes>
481	) -> Result<&2, &2, Base64.Error, List<&2, U32>>:
482	  match r:
483	    case Fail{e}:
484	      Fail{e}
485	    case Done{b}:
486	      Done{B.Bytes.to_u32_list(b)}
487	
488	def Base64.decode_u32_list(
489	  text: String
490	) -> Result<&2, &2, Base64.Error, List<&2, U32>>:
491	  Base64.decode_u32_list.from(Base64.decode(text))
492	
493	def Base64Url.decode_u32_list(
494	  text: String, padded: Bool
495	) -> Result<&2, &2, Base64.Error, List<&2, U32>>:
496	  Base64.decode_u32_list.from(Base64Url.decode(text, padded))