1	# UTF-8 and hex encoding for byte strings. Source: https://github.com/paymog/bend-kit/tree/main/encoding
2	import Base
3	
4	# Hex of each char as two nibbles. ASCII-oriented.
5	
6	def nibble(+n: U32) -> U32:
7	  Bool.pick(U32, U32.is_le(n, 9), (48 + n : U32), (87 + n : U32))
8	
9	@unsafe
10	def hi.go(+n: U32, +acc: U32, small: Bool) -> U32:
11	  match small:
12	    case True{}:
13	      acc
14	    case False{}:
15	      hi.go((n - 16 : U32), (acc + 1 : U32), U32.is_le((n - 16 : U32), 15))
16	
17	def hi(+n: U32) -> U32:
18	  hi.go(n, 0, U32.is_le(n, 15))
19	
20	def lo(+n: U32) -> U32:
21	  (n - (hi(n) * 16 : U32) : U32)
22	
23	def encode.go(s: String, acc: String) -> String:
24	  match s:
25	    case SNil{}:
26	      String.reverse(acc)
27	    case SCon{Chr{+c}, t}:
28	      encode.go(t, SCon{Chr{nibble(lo(c))}, SCon{Chr{nibble(hi(c))}, acc}})
29	
30	def encode(s: String) -> String:
31	  encode.go(s, SNil{})
32	
33	def unhex.h(c: U32, hex: Bool) -> Maybe<&2, U32>:
34	  match hex:
35	    case True{}:
36	      Some{(c - 87 : U32)}
37	    case False{}:
38	      None{}
39	
40	def unhex.d(+c: U32, dec: Bool, hex: Bool) -> Maybe<&2, U32>:
41	  match dec:
42	    case True{}:
43	      Some{(c - 48 : U32)}
44	    case False{}:
45	      unhex.h(c, hex)
46	
47	def unhex(+c: U32) -> Maybe<&2, U32>:
48	  unhex.d(c, Bool.and(U32.is_le(48, c), U32.is_le(c, 57)), Bool.and(U32.is_le(97, c), U32.is_le(c, 102)))
49	
50	def decode.cons(byte: U32, rest: Maybe<&2, String>) -> Maybe<&2, String>:
51	  match rest:
52	    case None{}:
53	      None{}
54	    case Some{s}:
55	      Some{SCon{Chr{byte}, s}}
56	
57	def decode.join2(x: U32, b: Maybe<&2, U32>, rest: Maybe<&2, String>) -> Maybe<&2, String>:
58	  match b:
59	    case None{}:
60	      None{}
61	    case Some{y}:
62	      decode.cons((x * 16 + y : U32), rest)
63	
64	def decode.join(a: Maybe<&2, U32>, b: Maybe<&2, U32>, rest: Maybe<&2, String>) -> Maybe<&2, String>:
65	  match a:
66	    case None{}:
67	      None{}
68	    case Some{x}:
69	      decode.join2(x, b, rest)
70	
71	@unsafe
72	def decode.go(s: String) -> Maybe<&2, String>:
73	  match s:
74	    case SNil{}:
75	      Some{SNil{}}
76	    case SCon{Chr{+c}, t}:
77	      match t:
78	        case SNil{}:
79	          None{}
80	        case SCon{Chr{+d}, r}:
81	          decode.join(unhex(c), unhex(d), decode.go(r))
82	
83	def decode(s: String) -> Maybe<&2, String>:
84	  decode.go(s)
85	
86	# UTF-8 (RFC 3629). Byte strings hold one Char per octet (0..255).
87	
88	def utf8.cont(c: U32, n: Nat) -> U32:
89	  (128 + U32.and(U32.shrn(c, n), 63) : U32)
90	
91	def utf8.push4(+c: U32, acc: String) -> String:
92	  SCon{Chr{utf8.cont(c, 0n)}, SCon{Chr{utf8.cont(c, 6n)}, SCon{Chr{utf8.cont(c, 12n)}, SCon{Chr{(240 + U32.shrn(c, 18n) : U32)}, acc}}}}
93	
94	def utf8.push3(+c: U32, acc: String, small: Bool) -> String:
95	  match small:
96	    case True{}:
97	      SCon{Chr{utf8.cont(c, 0n)}, SCon{Chr{utf8.cont(c, 6n)}, SCon{Chr{(224 + U32.shrn(c, 12n) : U32)}, acc}}}
98	    case False{}:
99	      utf8.push4(c, acc)
100	
101	def utf8.push2(+c: U32, acc: String, small: Bool) -> String:
102	  match small:
103	    case True{}:
104	      SCon{Chr{utf8.cont(c, 0n)}, SCon{Chr{(192 + U32.shrn(c, 6n) : U32)}, acc}}
105	    case False{}:
106	      utf8.push3(c, acc, U32.is_lt(c, 65536))
107	
108	def utf8.push(+c: U32, acc: String, ascii: Bool) -> String:
109	  match ascii:
110	    case True{}:
111	      SCon{Chr{c}, acc}
112	    case False{}:
113	      utf8.push2(c, acc, U32.is_lt(c, 2048))
114	
115	def utf8.encode.go(s: String, acc: String) -> String:
116	  match s:
117	    case SNil{}:
118	      String.reverse(acc)
119	    case SCon{Chr{+c}, t}:
120	      utf8.encode.go(t, utf8.push(c, acc, U32.is_lt(c, 128)))
121	
122	# Text to octets.
123	def utf8.encode(s: String) -> String:
124	  utf8.encode.go(s, SNil{})
125	
126	# Decoder state: continuation bytes still needed, the allowed range of the
127	# next one, the code point so far, and the output reversed.
128	type Utf8 is Data:
129	  Utf8{need: U32, lo: U32, hi: U32, cp: U32, out: String}
130	
131	def utf8.bad(out: String) -> String:
132	  SCon{Chr{65533}, out}
133	
134	def utf8.lead.multi(+b: U32, out: String) -> Utf8:
135	  +need = Bool.pick(U32, U32.is_lt(b, 224), 1, Bool.pick(U32, U32.is_lt(b, 240), 2, 3))
136	  +lo = Bool.pick(U32, U32.is_eq(b, 224), 160, Bool.pick(U32, U32.is_eq(b, 240), 144, 128))
137	  +hi = Bool.pick(U32, U32.is_eq(b, 237), 159, Bool.pick(U32, U32.is_eq(b, 244), 143, 191))
138	  Utf8{need, lo, hi, U32.and(b, U32.shrn(63, U32.to_nat(need))), out}
139	
140	def utf8.lead.high(+b: U32, out: String, bad: Bool) -> Utf8:
141	  match bad:
142	    case True{}:
143	      Utf8{0, 128, 191, 0, utf8.bad(out)}
144	    case False{}:
145	      utf8.lead.multi(b, out)
146	
147	# WHATWG: a byte that cannot start a sequence decodes to U+FFFD.
148	def utf8.lead(+b: U32, out: String, ascii: Bool) -> Utf8:
149	  match ascii:
150	    case True{}:
151	      Utf8{0, 128, 191, 0, SCon{Chr{b}, out}}
152	    case False{}:
153	      utf8.lead.high(b, out, Bool.or(U32.is_lt(b, 194), U32.is_lt(244, b)))
154	
155	def utf8.more(+need: U32, cp: U32, out: String, done: Bool) -> Utf8:
156	  match done:
157	    case True{}:
158	      Utf8{0, 128, 191, 0, SCon{Chr{cp}, out}}
159	    case False{}:
160	      Utf8{need, 128, 191, cp, out}
161	
162	# WHATWG: a byte that breaks a sequence yields U+FFFD and is read again as a lead.
163	def utf8.cont.in(+need: U32, cp: U32, +b: U32, out: String, ok: Bool) -> Utf8:
164	  match ok:
165	    case True{}:
166	      utf8.more((need - 1 : U32), (cp * 64 + U32.and(b, 63) : U32), out, U32.is_eq(need, 1))
167	    case False{}:
168	      utf8.lead(b, utf8.bad(out), U32.is_lt(b, 128))
169	
170	def utf8.step.if(+need: U32, +lo: U32, +hi: U32, cp: U32, +b: U32, out: String, idle: Bool) -> Utf8:
171	  match idle:
172	    case True{}:
173	      utf8.lead(b, out, U32.is_lt(b, 128))
174	    case False{}:
175	      utf8.cont.in(need, cp, b, out, Bool.and(U32.is_le(lo, b), U32.is_le(b, hi)))
176	
177	def utf8.step.st(st: Utf8, +b: U32) -> Utf8:
178	  Utf8{+need, +lo, +hi, cp, out} = st
179	  utf8.step.if(need, lo, hi, cp, b, out, U32.is_eq(need, 0))
180	
181	def utf8.finish(st: Utf8) -> String:
182	  Utf8{+need, lo, hi, cp, +out} = st
183	  String.reverse(Bool.pick(String, U32.is_eq(need, 0), out, utf8.bad(out)))
184	
185	def utf8.decode.go(s: String, st: Utf8) -> String:
186	  match s:
187	    case SNil{}:
188	      utf8.finish(st)
189	    case SCon{Chr{b}, t}:
190	      utf8.decode.go(t, utf8.step.st(st, b))
191	
192	# Octets to text, as WHATWG decodes UTF-8: malformed input becomes U+FFFD.
193	def utf8.decode(s: String) -> String:
194	  utf8.decode.go(s, Utf8{0, 128, 191, 0, SNil{}})