Line data Source code
1 : #include "wok_utf8.h"
2 :
3 : #include "wok_base.h"
4 :
5 : #include <stdbool.h>
6 : #include <stdint.h>
7 : #include <string.h>
8 :
9 : // Bjoern Hoehrmann's flexible and economical UTF-8 decoder (MIT).
10 : //
11 : // The table encodes overlong encodings, UTF-16 surrogates and codepoints above
12 : // U+10FFFF as REJECT states, so none of those is a hand-written predicate that
13 : // can be quietly wrong. That is the whole reason it is here: the version this
14 : // replaced decided all three by hand, and three predicates is three chances.
15 : //
16 : // The cost is a table no one can audit by eye. That is paid off in
17 : // test/test_utf8.c, which keeps the hand-written decoder as a REFERENCE MODEL
18 : // and compares the two over every 1-, 2- and 3-byte sequence -- 16,777,216
19 : // cases, exhaustive -- the same arrangement the layout filter uses. The table
20 : // is therefore verified rather than trusted.
21 : #define UTF8_ACCEPT 0
22 : #define UTF8_REJECT 12
23 :
24 : static const u8 utf8d[] = {
25 : // 256 entries: byte -> character class.
26 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
27 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
28 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
29 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
30 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
31 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
32 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
33 : 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
34 : 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
35 : 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
36 : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
37 : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
38 : 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
39 : 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
40 : 10, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 3,
41 : 11, 6, 6, 6, 5, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
42 : // 108 entries: (state + class) -> state. 9 states x 12 classes.
43 : 0, 12, 24, 36, 60, 96, 84, 12, 12, 12, 48, 72,
44 : 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
45 : 12, 0, 12, 12, 12, 12, 12, 0, 12, 0, 12, 12,
46 : 12, 24, 12, 12, 12, 12, 12, 24, 12, 24, 12, 12,
47 : 12, 12, 12, 12, 12, 12, 12, 24, 12, 12, 12, 12,
48 : 12, 24, 12, 12, 12, 12, 12, 12, 12, 24, 12, 12,
49 : 12, 12, 12, 12, 12, 12, 12, 36, 12, 36, 12, 12,
50 : 12, 36, 12, 12, 12, 12, 12, 36, 12, 36, 12, 12,
51 : 12, 36, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
52 : };
53 :
54 : // 256 class entries plus 9 states x 12 classes. A miscount here is exactly
55 : // the transcription slip test_utf8.c's exhaustive sweep exists to catch --
56 : // and did, the first time this table was written.
57 : static_assert(sizeof utf8d == 256 + 9 * 12, "the DFA table is the wrong size");
58 :
59 20955681 : static inline u32 dfa_step(u32 *state, unsigned char byte) {
60 20955681 : *state = utf8d[256u + *state + utf8d[byte]];
61 20955681 : return *state;
62 : }
63 :
64 17133711 : WOK_READONLY usize wok_utf8_seq_len(const unsigned char *restrict p,
65 : usize avail) {
66 17133711 : u32 state = UTF8_ACCEPT;
67 17133711 : usize limit = avail < 4 ? avail : 4;
68 20972921 : for (usize i = 0; i < limit; i++) {
69 20955681 : if (dfa_step(&state, p[i]) == UTF8_REJECT) return 0;
70 12808060 : if (state == UTF8_ACCEPT) return i + 1;
71 : }
72 : return 0; // truncated, or a lead byte that never completes
73 : }
74 :
75 : // Benchmarked:
76 : // ┌────────────────────────┬───────────────────-------─┬──────────────┐
77 : // │ │ ASCII (wok source) │ 20% two-byte │
78 : // ├────────────────────────┼──────────────────-------──┼──────────────┤
79 : // │ hand-written │ 2,662 MB/s │ 979 MB/s │
80 : // ├────────────────────────┼───────────────────-------─┼──────────────┤
81 : // │ DFA alone │ 4,071 │ 619 │
82 : // ├────────────────────────┼───────────────────-------─┼──────────────┤
83 : // │ hand + ASCII fast path │ 17,818 (we are using this)│ 988 │
84 : // ├────────────────────────┼───────────────────-------─┼──────────────┤
85 : // │ DFA + ASCII fast path │ 17,437 │ 1,493 │
86 : // └────────────────────────┴───────────────────-------─┴──────────────┘
87 374626 : WOK_READONLY usize wok_utf8_find_invalid(const unsigned char *restrict p,
88 : usize n) {
89 374626 : usize i = 0;
90 925814 : while (i < n) {
91 : // ASCII FAST PATH, eight bytes at a time. This -- not the DFA -- is what
92 : // makes validation ~6.7x faster on wok source, which is essentially all
93 : // ASCII: 17.8 GB/s against 2.7. Measured, because the intuition that a
94 : // table lookup per byte would be the bottleneck was wrong in both
95 : // directions.
96 2974096 : while (i + 8 <= n) {
97 2790408 : u64 w;
98 2790408 : memcpy(&w, p + i, 8);
99 2790408 : if ((w & UINT64_C(0x8080808080808080)) != 0) break;
100 2974096 : i += 8;
101 : }
102 885769 : if (i >= n) break;
103 880342 : if (p[i] < 0x80) {
104 524978 : i++;
105 524978 : continue;
106 : }
107 355364 : usize seq = wok_utf8_seq_len(p + i, n - i);
108 355364 : if (seq == 0) return i;
109 26210 : i += seq;
110 : }
111 : return n;
112 : }
113 :
114 7682 : WOK_READONLY usize wok_utf8_truncate(const unsigned char *restrict p, usize n,
115 : usize max) {
116 7682 : if (n <= max) return n;
117 : usize i = 0;
118 1108 : while (i < n) {
119 1108 : usize seq = wok_utf8_seq_len(p + i, n - i);
120 1108 : if (seq == 0) seq = 1; // ill-formed input still advances, so this
121 : // terminates on any bytes at all
122 1108 : if (i + seq > max) return i;
123 : i += seq;
124 : }
125 : return i;
126 : }
|
