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