| 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 |
}; |