1	# UTF-8 encoding and decoding between text and Bytes. Source: https://github.com/paymog/bend-kit/tree/main/encoding
2	import Base
3	import 0x49814d83de8f70993a43e1002be29ecd/bytes.bend as Bytes
4	
5	# UTF-8 (RFC 3629). Text is a String of code points; octets are Bytes.
6	# Hex lives in Bytes: Bytes.to_hex and Bytes.from_hex.
7	
8	# Octets being written: the buffer, the count so far, and the word being filled.
9	type Out is Type:
10	  Out{buf: Array<U32>, n: U32, w: U32}
11	
12	# Bytes enter at the top of w, as in Bytes.from_string; every fourth byte stores the word.
13	def put(o: Out, +b: U32) -> Out:
14	  Out{buf, +n, +w} = o
15	  +w2 = ((w >> 8n) .|. (b << 24n) : U32)
16	  +full = U32.is_eq((n .&. 3 : U32), 3)
17	  Out{Bytes.flush(full, buf, (n >> 2n : U32), w2), (n + 1 : U32), Bool.pick(U32, full, 0, w2)}
18	
19	def done(o: Out) -> Bytes.Bytes:
20	  Out{buf, +n, +w} = o
21	  +r = (n .&. 3 : U32)
22	  Bytes.Bytes{n, Bytes.flush(U32.is_ne(r, 0), buf, (n >> 2n : U32), U32.shrn(w, U32.to_nat((((4 - r) .&. 3) * 8 : U32))))}
23	
24	def utf8.width(+c: U32) -> U32:
25	  Bool.pick(U32, U32.is_lt(c, 128), 1, Bool.pick(U32, U32.is_lt(c, 2048), 2, Bool.pick(U32, U32.is_lt(c, 65536), 3, 4)))
26	
27	def utf8.size(s: String, +n: U32) -> U32:
28	  match s:
29	    case SNil{}:
30	      n
31	    case SCon{Chr{+c}, t}:
32	      utf8.size(t, (n + utf8.width(c) : U32))
33	
34	def utf8.cont(c: U32, n: Nat) -> U32:
35	  (128 + U32.and(U32.shrn(c, n), 63) : U32)
36	
37	def utf8.push4(+c: U32, o: Out) -> Out:
38	  put(put(put(put(o, (240 + U32.shrn(c, 18n) : U32)), utf8.cont(c, 12n)), utf8.cont(c, 6n)), utf8.cont(c, 0n))
39	
40	def utf8.push3(+c: U32, o: Out, small: Bool) -> Out:
41	  match small:
42	    case True{}:
43	      put(put(put(o, (224 + U32.shrn(c, 12n) : U32)), utf8.cont(c, 6n)), utf8.cont(c, 0n))
44	    case False{}:
45	      utf8.push4(c, o)
46	
47	def utf8.push2(+c: U32, o: Out, small: Bool) -> Out:
48	  match small:
49	    case True{}:
50	      put(put(o, (192 + U32.shrn(c, 6n) : U32)), utf8.cont(c, 0n))
51	    case False{}:
52	      utf8.push3(c, o, U32.is_lt(c, 65536))
53	
54	def utf8.push(+c: U32, o: Out, ascii: Bool) -> Out:
55	  match ascii:
56	    case True{}:
57	      put(o, c)
58	    case False{}:
59	      utf8.push2(c, o, U32.is_lt(c, 2048))
60	
61	def utf8.encode.go(s: String, o: Out) -> Out:
62	  match s:
63	    case SNil{}:
64	      o
65	    case SCon{Chr{+c}, t}:
66	      utf8.encode.go(t, utf8.push(c, o, U32.is_lt(c, 128)))
67	
68	# Text to octets. One pass sizes the buffer; a second fills it.
69	def utf8.encode(+s: String) -> Bytes.Bytes:
70	  done(utf8.encode.go(s, Out{Bytes.alloc(utf8.size(s, 0)), 0, 0}))
71	
72	# Decoder state: continuation bytes still needed, the allowed range of the
73	# next one, the code point so far, and the output reversed.
74	type Utf8 is Data:
75	  Utf8{need: U32, lo: U32, hi: U32, cp: U32, out: String}
76	
77	def utf8.bad(out: String) -> String:
78	  SCon{Chr{65533}, out}
79	
80	def utf8.lead.multi(+b: U32, out: String) -> Utf8:
81	  +need = Bool.pick(U32, U32.is_lt(b, 224), 1, Bool.pick(U32, U32.is_lt(b, 240), 2, 3))
82	  +lo = Bool.pick(U32, U32.is_eq(b, 224), 160, Bool.pick(U32, U32.is_eq(b, 240), 144, 128))
83	  +hi = Bool.pick(U32, U32.is_eq(b, 237), 159, Bool.pick(U32, U32.is_eq(b, 244), 143, 191))
84	  Utf8{need, lo, hi, U32.and(b, U32.shrn(63, U32.to_nat(need))), out}
85	
86	def utf8.lead.high(+b: U32, out: String, bad: Bool) -> Utf8:
87	  match bad:
88	    case True{}:
89	      Utf8{0, 128, 191, 0, utf8.bad(out)}
90	    case False{}:
91	      utf8.lead.multi(b, out)
92	
93	# WHATWG: a byte that cannot start a sequence decodes to U+FFFD.
94	def utf8.lead(+b: U32, out: String, ascii: Bool) -> Utf8:
95	  match ascii:
96	    case True{}:
97	      Utf8{0, 128, 191, 0, SCon{Chr{b}, out}}
98	    case False{}:
99	      utf8.lead.high(b, out, Bool.or(U32.is_lt(b, 194), U32.is_lt(244, b)))
100	
101	def utf8.more(+need: U32, cp: U32, out: String, done: Bool) -> Utf8:
102	  match done:
103	    case True{}:
104	      Utf8{0, 128, 191, 0, SCon{Chr{cp}, out}}
105	    case False{}:
106	      Utf8{need, 128, 191, cp, out}
107	
108	# WHATWG: a byte that breaks a sequence yields U+FFFD and is read again as a lead.
109	def utf8.cont.in(+need: U32, cp: U32, +b: U32, out: String, ok: Bool) -> Utf8:
110	  match ok:
111	    case True{}:
112	      utf8.more((need - 1 : U32), (cp * 64 + U32.and(b, 63) : U32), out, U32.is_eq(need, 1))
113	    case False{}:
114	      utf8.lead(b, utf8.bad(out), U32.is_lt(b, 128))
115	
116	def utf8.step.if(+need: U32, +lo: U32, +hi: U32, cp: U32, +b: U32, out: String, idle: Bool) -> Utf8:
117	  match idle:
118	    case True{}:
119	      utf8.lead(b, out, U32.is_lt(b, 128))
120	    case False{}:
121	      utf8.cont.in(need, cp, b, out, Bool.and(U32.is_le(lo, b), U32.is_le(b, hi)))
122	
123	def utf8.step.st(st: Utf8, +b: U32) -> Utf8:
124	  Utf8{+need, +lo, +hi, cp, out} = st
125	  utf8.step.if(need, lo, hi, cp, b, out, U32.is_eq(need, 0))
126	
127	def utf8.finish(st: Utf8) -> String:
128	  Utf8{+need, lo, hi, cp, +out} = st
129	  String.reverse(Bool.pick(String, U32.is_eq(need, 0), out, utf8.bad(out)))
130	
131	def utf8.decode.go(n: Nat, r: Array<U32> & U32, +i: U32, st: Utf8) -> String:
132	  match n:
133	    case 0n:
134	      (a, v) = r
135	      utf8.finish(st)
136	    case 1n+p:
137	      (a, +b) = r
138	      utf8.decode.go(p, Bytes.peek(a, (i + 1 : U32)), (i + 1 : U32), utf8.step.st(st, b))
139	
140	# Octets to text, as WHATWG decodes UTF-8: malformed input becomes U+FFFD.
141	def utf8.decode(b: Bytes.Bytes) -> String:
142	  Bytes.Bytes{+len, buf} = b
143	  utf8.decode.go(U32.to_nat(len), Bytes.peek(buf, 0), 0, Utf8{0, 128, 191, 0, SNil{}})