encoding.bend
bend-kit-encoding@0.2.1.0 · 194 lines · 0 definitions
1# UTF-8 and hex encoding for byte strings. Source: https://github.com/paymog/bend-kit/tree/main/encoding
2import Base
3
4# Hex of each char as two nibbles. ASCII-oriented.
5
6def nibble(+n: U32) -> U32:
7 Bool.pick(U32, U32.is_le(n, 9), (48 + n : U32), (87 + n : U32))
8
9@unsafe
10def 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
17def hi(+n: U32) -> U32:
18 hi.go(n, 0, U32.is_le(n, 15))
19
20def lo(+n: U32) -> U32:
21 (n - (hi(n) * 16 : U32) : U32)
22
23def 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
30def encode(s: String) -> String:
31 encode.go(s, SNil{})
32
33def 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
40def 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
47def 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
50def 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
57def 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
64def 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
72def 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
83def 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
88def utf8.cont(c: U32, n: Nat) -> U32:
89 (128 + U32.and(U32.shrn(c, n), 63) : U32)
90
91def 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
94def 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
101def 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
108def 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
115def 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.
123def 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.
128type Utf8 is Data:
129 Utf8{need: U32, lo: U32, hi: U32, cp: U32, out: String}
130
131def utf8.bad(out: String) -> String:
132 SCon{Chr{65533}, out}
133
134def 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
140def 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.
148def 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
155def 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.
163def 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
170def 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
177def 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
181def 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
185def 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.
193def utf8.decode(s: String) -> String:
194 utf8.decode.go(s, Utf8{0, 128, 191, 0, SNil{}})