Debian Codegraph @

encoding/utf8/decode.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 use bytes;
5
6 export type decoder = struct {
7 offs: size,
8 src: []u8,
9 };
10
11 // Initializes a new UTF-8 decoder. You may copy the decoder to save its state.
12 export fn decode(src: []u8) decoder = decoder {
13 src = src,
14 offs = 0,
15 };
16
17 const masks: [2][8]u8 = [
18 [0x3f, 0x3f, 0x3f, 0x3f, 0x3f, 0x3f, 0x3f, 0x3f],
19 [0x7f, 0x1f, 0x0f, 0x0f, 0x0f, 0x07, 0x07, 0x07],
20 ];
21
22 // Returns the next rune from a decoder. done is returned when there are no
23 // remaining codepoints.
24 //
25 // If an invalid UTF-8 sequence is encountered, the position of the decoder is
26 // set to immediately after the first invalid byte.
27 export fn next(d: *decoder) (rune | done | more | invalid) = {
28 if (d.offs == len(d.src)) {
29 return done;
30 };
31
32 // from https://github.com/skeeto/scratch/blob/master/parsers/utf8_decode.c
33 // See https://bjoern.hoehrmann.de/utf-8/decoder/dfa/
34 // and https://nullprogram.com/blog/2020/12/31/ for an explanation of
35 // the algorithm.
36 let next = 0, state = 0;
37 let r = 0u32;
38 for (d.offs < len(d.src); d.offs += 1) {
39 next = table[state][d.src[d.offs]];
40 r = r << 6 | d.src[d.offs] & masks[(state - 1): uint >> 31][next & 7];
41 if (next <= 0) {
42 d.offs += 1;
43 return if (next == 0) r: rune else invalid;
44 };
45 state = next;
46 };
47 return more;
48 };
49
50 // Returns the previous rune from a decoder. done is returned when there are no
51 // previous codepoints.
52 export fn prev(d: *decoder) (rune | done | more | invalid) = {
53 if (d.offs == 0) {
54 return done;
55 };
56 let n = d.offs;
57 d.offs -= 1;
58 for (d.offs < len(d.src); d.offs -= 1) {
59 if (table[0][d.src[d.offs]] != -1) {
60 let t = d.offs;
61 defer d.offs = t;
62 let r = next(d);
63 return if (n != d.offs || r is more) invalid else r;
64 };
65 if (n - d.offs == 4) {
66 // Too many continuation bytes in a row
67 return invalid;
68 };
69 };
70 return more;
71 };
72
73 // Returns a subslice from the next byte in the decoder to the end of the slice.
74 export fn remaining(d: *decoder) []u8 = d.src[d.offs..];
75
76 // Return a subslice from the position of the first decoder to the position of
77 // the second decoder. The decoders must originate from the same slice and the
78 // position of the second decoder must not be before the position of the first
79 // one.
80 export fn slice(begin: *decoder, end: *decoder) []u8 = {
81 assert(begin.src: *[*]u8 == end.src: *[*]u8 && begin.offs <= end.offs);
82 return begin.src[begin.offs..end.offs];
83 };
84
85 @test fn decode() void = {
86 const input: [_]u8 = [
87 0xE3, 0x81, 0x93, 0xE3, 0x82, 0x93, 0xE3, 0x81,
88 0xAB, 0xE3, 0x81, 0xA1, 0xE3, 0x81, 0xAF, 0x00,
89 ];
90 assert(validate(input) is void);
91 const expected = ['こ', 'ん', 'に', 'ち', 'は', '\0'];
92 let decoder = decode(input);
93 for (let i = 0z; i < len(expected); i += 1) {
94 match (next(&decoder)) {
95 case (invalid | more | done) =>
96 abort();
97 case let r: rune =>
98 assert(r == expected[i]);
99 };
100 };
101 assert(next(&decoder) is done);
102 assert(decoder.offs == len(decoder.src));
103 for (let i = 0z; i < len(expected); i += 1) {
104 match (prev(&decoder)) {
105 case (invalid | more | done) =>
106 abort();
107 case let r: rune =>
108 assert(r == expected[len(expected) - i - 1]);
109 };
110 };
111 assert(prev(&decoder) is done);
112
113 const inv: [_]u8 = [0xA0, 0xA1];
114 decoder = decode(inv);
115 assert(next(&decoder) is invalid);
116 decoder.offs = 2;
117 assert(prev(&decoder) is more);
118 assert(validate(inv) is invalid);
119
120 const incomplete: [_]u8 = [0xE3, 0x81];
121 decoder = decode(incomplete);
122 assert(next(&decoder) is more);
123 decoder.offs = 2;
124 assert(prev(&decoder) is invalid);
125 assert(validate(incomplete) is invalid);
126
127 const surrogate: [_]u8 = [0xED, 0xA0, 0x80];
128 decoder = decode(surrogate);
129 assert(next(&decoder) is invalid);
130 decoder.offs = 3;
131 assert(prev(&decoder) is invalid);
132 assert(validate(surrogate) is invalid);
133
134 const overlong: [_]u8 = [0xF0, 0x82, 0x82, 0xAC];
135 decoder = decode(overlong);
136 assert(next(&decoder) is invalid);
137 decoder.offs = 4;
138 assert(prev(&decoder) is invalid);
139 assert(validate(overlong) is invalid);
140
141 const badcont: [_]u8 = [0xC2, 0xFF];
142 decoder = decode(badcont);
143 assert(next(&decoder) is invalid);
144 assert(validate(badcont) is invalid);
145
146 const extracont: [_]u8 = [0xC2, 0xA3, 0x95];
147 decoder = decode(extracont);
148 decoder.offs = 3;
149 assert(prev(&decoder) is invalid);
150 assert(validate(extracont) is invalid);
151 const maxinrange: [_]u8 = [0xF4, 0x8F, 0xBF, 0xBF];
152 decoder = decode(maxinrange);
153 match (next(&decoder)) {
154 case let r: rune =>
155 assert(r == 0x10FFFFu32: rune);
156 case => abort();
157 };
158 decoder.offs = 4;
159 match (prev(&decoder)) {
160 case let r: rune =>
161 assert(r == 0x10FFFFu32: rune);
162 case => abort();
163 };
164
165 const minoutofrange: [_]u8 = [0xF5, 0x94, 0x80, 0x80];
166 decoder = decode(minoutofrange);
167 assert(next(&decoder) is invalid);
168 decoder.offs = 4;
169 assert(prev(&decoder) is invalid);
170 };
171
172 @test fn slice() void = {
173 const input: [_]u8 = [
174 0xE3, 0x81, 0x93, 0xE3, 0x82, 0x93, 0xE3, 0x81,
175 0xAB, 0xE3, 0x81, 0xA1, 0xE3, 0x81, 0xAF, 0x00,
176 ];
177 let d1 = decode(input);
178 let d2 = d1;
179 assert(bytes::equal(remaining(&d1), input));
180 assert(len(slice(&d1, &d2)) == 0 && len(slice(&d2, &d1)) == 0);
181 for (let i = 0; i < 2; i += 1) {
182 next(&d1)!;
183 next(&d2)!;
184 };
185 assert(bytes::equal(remaining(&d1), input[6..]));
186 assert(len(slice(&d1, &d2)) == 0 && len(slice(&d2, &d1)) == 0);
187 for (let i = 0; i < 3; i += 1) {
188 next(&d2)!;
189 };
190 assert(bytes::equal(remaining(&d2), input[15..]));
191 assert(bytes::equal(slice(&d1, &d2), input[6..15]));
192 for (let i = 0; i < 3; i += 1) {
193 next(&d1)!;
194 };
195 assert(len(slice(&d1, &d2)) == 0 && len(slice(&d2, &d1)) == 0);
196 next(&d1)!;
197 assert(len(remaining(&d1)) == 0);
198 };
199
200 // Returns the position of the decoder. When possible, it's generally considered
201 // more idiomatic to use other functions in this module, such as [[remaining]]
202 // and [[slice]].
203 export fn position(d: *decoder) size = d.offs;
204
205 // Returns void if a given byte slice contains only valid UTF-8 sequences,
206 // otherwise returns invalid.
207 export fn validate(src: []u8) (void | invalid) = {
208 let state = 0;
209 for (let i = 0z; i < len(src) && state >= 0; i += 1) {
210 state = table[state][src[i]];
211 };
212 return if (state == 0) void else invalid;
213 };