1 /**
2 * https://github.com/lemire/fastvalidate-utf-8
3 */
4
5 #ifndef SIMDUTF8CHECK_H
6 #define SIMDUTF8CHECK_H
7 #include <stdbool.h>
8 #include <stddef.h>
9 #include <stdint.h>
10 #include <x86intrin.h>
11
12 #include "base/lnav_log.hh"
13
14 #ifdef __cplusplus
15 extern "C" {
16 #endif
17
18 /*
19 * legal utf-8 byte sequence
20 * http://www.unicode.org/versions/Unicode6.0.0/ch03.pdf - page 94
21 *
22 * Code Points 1st 2s 3s 4s
23 * U+0000..U+007F 00..7F
24 * U+0080..U+07FF C2..DF 80..BF
25 * U+0800..U+0FFF E0 A0..BF 80..BF
26 * U+1000..U+CFFF E1..EC 80..BF 80..BF
27 * U+D000..U+D7FF ED 80..9F 80..BF
28 * U+E000..U+FFFF EE..EF 80..BF 80..BF
29 * U+10000..U+3FFFF F0 90..BF 80..BF 80..BF
30 * U+40000..U+FFFFF F1..F3 80..BF 80..BF 80..BF
31 * U+100000..U+10FFFF F4 80..8F 80..BF 80..BF
32 *
33 */
34
35 // all byte values must be no larger than 0xF4
checkSmallerThan0xF4(__m128i current_bytes,__m128i * has_error)36 static void checkSmallerThan0xF4(__m128i current_bytes,
37 __m128i *has_error)
38 {
39 // unsigned, saturates to 0 below max
40 *has_error = _mm_or_si128(*has_error,
41 _mm_subs_epu8(current_bytes,
42 _mm_set1_epi8(0xF4)));
43 }
44
continuationLengths(__m128i high_nibbles)45 static __m128i continuationLengths(__m128i high_nibbles)
46 {
47 return _mm_shuffle_epi8(
48 _mm_setr_epi8(1, 1, 1, 1, 1, 1, 1, 1, // 0xxx (ASCII)
49 0, 0, 0, 0, // 10xx (continuation)
50 2, 2, // 110x
51 3, // 1110
52 4), // 1111, next should be 0 (not checked here)
53 high_nibbles);
54 }
55
carryContinuations(__m128i initial_lengths,__m128i previous_carries)56 static __m128i carryContinuations(__m128i initial_lengths,
57 __m128i previous_carries)
58 {
59
60 __m128i right1 = _mm_subs_epu8(
61 _mm_alignr_epi8(initial_lengths, previous_carries, 16 - 1),
62 _mm_set1_epi8(1));
63 __m128i sum = _mm_add_epi8(initial_lengths, right1);
64
65 __m128i right2 = _mm_subs_epu8(
66 _mm_alignr_epi8(sum, previous_carries, 16 - 2),
67 _mm_set1_epi8(2));
68 return _mm_add_epi8(sum, right2);
69 }
70
checkContinuations(__m128i initial_lengths,__m128i carries,__m128i * has_error)71 static void checkContinuations(__m128i initial_lengths,
72 __m128i carries,
73 __m128i *has_error)
74 {
75
76 // overlap || underlap
77 // carry > length && length > 0 || !(carry > length) && !(length > 0)
78 // (carries > length) == (lengths > 0)
79 __m128i overunder = _mm_cmpeq_epi8(
80 _mm_cmpgt_epi8(carries, initial_lengths),
81 _mm_cmpgt_epi8(initial_lengths, _mm_setzero_si128()));
82
83 *has_error = _mm_or_si128(*has_error, overunder);
84 }
85
86 // when 0xED is found, next byte must be no larger than 0x9F
87 // when 0xF4 is found, next byte must be no larger than 0x8F
88 // next byte must be continuation, ie sign bit is set, so signed < is ok
checkFirstContinuationMax(__m128i current_bytes,__m128i off1_current_bytes,__m128i * has_error)89 static void checkFirstContinuationMax(__m128i current_bytes,
90 __m128i off1_current_bytes,
91 __m128i *has_error)
92 {
93 __m128i maskED = _mm_cmpeq_epi8(off1_current_bytes, _mm_set1_epi8(0xED));
94 __m128i maskF4 = _mm_cmpeq_epi8(off1_current_bytes, _mm_set1_epi8(0xF4));
95
96 __m128i badfollowED = _mm_and_si128(
97 _mm_cmpgt_epi8(current_bytes, _mm_set1_epi8(0x9F)),
98 maskED);
99 __m128i badfollowF4 = _mm_and_si128(
100 _mm_cmpgt_epi8(current_bytes, _mm_set1_epi8(0x8F)),
101 maskF4);
102
103 *has_error = _mm_or_si128(*has_error,
104 _mm_or_si128(badfollowED, badfollowF4));
105 }
106
107 // map off1_hibits => error condition
108 // hibits off1 cur
109 // C => < C2 && true
110 // E => < E1 && < A0
111 // F => < F1 && < 90
112 // else false && false
checkOverlong(__m128i current_bytes,__m128i off1_current_bytes,__m128i hibits,__m128i previous_hibits,__m128i * has_error)113 static void checkOverlong(__m128i current_bytes,
114 __m128i off1_current_bytes,
115 __m128i hibits,
116 __m128i previous_hibits,
117 __m128i *has_error)
118 {
119 __m128i off1_hibits = _mm_alignr_epi8(hibits, previous_hibits, 16 - 1);
120 __m128i initial_mins = _mm_shuffle_epi8(
121 _mm_setr_epi8(-128, -128, -128, -128, -128, -128, -128, -128,
122 -128, -128, -128, -128, // 10xx => false
123 0xC2, -128, // 110x
124 0xE1, // 1110
125 0xF1),
126 off1_hibits);
127
128 __m128i initial_under = _mm_cmpgt_epi8(initial_mins, off1_current_bytes);
129
130 __m128i second_mins = _mm_shuffle_epi8(
131 _mm_setr_epi8(-128, -128, -128, -128, -128, -128, -128, -128,
132 -128, -128, -128, -128, // 10xx => false
133 127, 127, // 110x => true
134 0xA0, // 1110
135 0x90),
136 off1_hibits);
137 __m128i second_under = _mm_cmpgt_epi8(second_mins, current_bytes);
138 *has_error = _mm_or_si128(*has_error,
139 _mm_and_si128(initial_under, second_under));
140 }
141
142 struct processed_utf_bytes {
143 __m128i rawbytes;
144 __m128i high_nibbles;
145 __m128i carried_continuations;
146 };
147
count_nibbles(__m128i bytes,struct processed_utf_bytes * answer)148 static void count_nibbles(__m128i bytes,
149 struct processed_utf_bytes *answer)
150 {
151 answer->rawbytes = bytes;
152 answer->high_nibbles = _mm_and_si128(_mm_srli_epi16(bytes, 4),
153 _mm_set1_epi8(0x0F));
154 }
155
156 // check whether the current bytes are valid UTF-8
157 // at the end of the function, previous gets updated
158 static struct processed_utf_bytes
checkUTF8Bytes(__m128i current_bytes,struct processed_utf_bytes * previous,__m128i * has_error)159 checkUTF8Bytes(__m128i current_bytes, struct processed_utf_bytes *previous,
160 __m128i *has_error)
161 {
162 struct processed_utf_bytes pb;
163 count_nibbles(current_bytes, &pb);
164
165 checkSmallerThan0xF4(current_bytes, has_error);
166
167 __m128i initial_lengths = continuationLengths(pb.high_nibbles);
168
169 pb.carried_continuations = carryContinuations(
170 initial_lengths,
171 previous->carried_continuations);
172
173 checkContinuations(initial_lengths, pb.carried_continuations, has_error);
174
175 __m128i off1_current_bytes =
176 _mm_alignr_epi8(pb.rawbytes, previous->rawbytes, 16 - 1);
177 checkFirstContinuationMax(current_bytes, off1_current_bytes,
178 has_error);
179
180 checkOverlong(current_bytes, off1_current_bytes,
181 pb.high_nibbles, previous->high_nibbles, has_error);
182 return pb;
183 }
184
validate_utf8_fast(const char * src,size_t len,ssize_t * len_out)185 static bool validate_utf8_fast(const char *src, size_t len, ssize_t *len_out)
186 {
187 size_t i = 0, orig_len = len;
188 __m128i has_error = _mm_setzero_si128();
189 __m128i lfchars = _mm_set1_epi8('\n');
190 __m128i lfresult = _mm_setzero_si128();
191 struct processed_utf_bytes previous = {.rawbytes = _mm_setzero_si128(),
192 .high_nibbles = _mm_setzero_si128(),
193 .carried_continuations = _mm_setzero_si128()};
194 if (len >= 16) {
195 for (; i <= len - 16; i += 16) {
196 __m128i current_bytes = _mm_loadu_si128(
197 (const __m128i *) (src + i));
198 previous = checkUTF8Bytes(current_bytes, &previous, &has_error);
199 lfresult = _mm_cmpeq_epi8(current_bytes, lfchars);
200 if (_mm_movemask_epi8(lfresult)) {
201 for (; src[i] != '\n'; i++) {
202 }
203 len = i;
204 break;
205 }
206 }
207 }
208
209 //last part
210 if (i < len) {
211 char buffer[16];
212 memset(buffer, 0, 16);
213 memcpy(buffer, src + i, len - i);
214 __m128i current_bytes = _mm_loadu_si128((const __m128i *) (buffer));
215 previous = checkUTF8Bytes(current_bytes, &previous, &has_error);
216 for (; i < len && src[i] != '\n'; i++) {
217 }
218 } else {
219 has_error = _mm_or_si128(_mm_cmpgt_epi8(previous.carried_continuations,
220 _mm_setr_epi8(9, 9, 9, 9, 9, 9,
221 9, 9, 9, 9, 9, 9,
222 9, 9, 9, 1)),
223 has_error);
224 }
225
226 if (i < orig_len && src[i] == '\n') {
227 *len_out = i;
228 }
229
230 return _mm_testz_si128(has_error, has_error);
231 }
232
233 #ifdef __cplusplus
234 }
235 #endif
236
237 #endif
238