encoding.bend
bend-kit-encoding@0.4.0.0 · 143 lines · 0 definitions
1# UTF-8 encoding and decoding between text and Bytes. Source: https://github.com/paymog/bend-kit/tree/main/encoding
2import Base
3import bend-kit-bytes@0.3.2.0/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.
9type 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.
13def 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
19def 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
24def 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
27def 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
34def utf8.cont(c: U32, n: Nat) -> U32:
35 (128 + U32.and(U32.shrn(c, n), 63) : U32)
36
37def 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
40def 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
47def 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
54def 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
61def 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.
69def 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.
74type Utf8 is Data:
75 Utf8{need: U32, lo: U32, hi: U32, cp: U32, out: String}
76
77def utf8.bad(out: String) -> String:
78 SCon{Chr{65533}, out}
79
80def 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
86def 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.
94def 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
101def 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.
109def 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
116def 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
123def 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
127def 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
131def 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.
141def 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{}})