1 #ifdef __x86_64__
2
3 #include <stdio.h>
4 #include <stdint.h>
5 #include <x86intrin.h>
6
7 int utf8_naive(const unsigned char *data, int len);
8
9 #if 0
10 static void print128(const char *s, const __m128i v128)
11 {
12 const unsigned char *v8 = (const unsigned char *)&v128;
13 if (s)
14 printf("%s:\t", s);
15 for (int i = 0; i < 16; i++)
16 printf("%02x ", v8[i]);
17 printf("\n");
18 }
19 #endif
20
21 /*
22 * Map high nibble of "First Byte" to legal character length minus 1
23 * 0x00 ~ 0xBF --> 0
24 * 0xC0 ~ 0xDF --> 1
25 * 0xE0 ~ 0xEF --> 2
26 * 0xF0 ~ 0xFF --> 3
27 */
28 static const int8_t _first_len_tbl[] = {
29 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3,
30 };
31
32 /* Map "First Byte" to 8-th item of range table (0xC2 ~ 0xF4) */
33 static const int8_t _first_range_tbl[] = {
34 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8,
35 };
36
37 /*
38 * Range table, map range index to min and max values
39 * Index 0 : 00 ~ 7F (First Byte, ascii)
40 * Index 1,2,3: 80 ~ BF (Second, Third, Fourth Byte)
41 * Index 4 : A0 ~ BF (Second Byte after E0)
42 * Index 5 : 80 ~ 9F (Second Byte after ED)
43 * Index 6 : 90 ~ BF (Second Byte after F0)
44 * Index 7 : 80 ~ 8F (Second Byte after F4)
45 * Index 8 : C2 ~ F4 (First Byte, non ascii)
46 * Index 9~15 : illegal: i >= 127 && i <= -128
47 */
48 static const int8_t _range_min_tbl[] = {
49 0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80,
50 0xC2, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F,
51 };
52 static const int8_t _range_max_tbl[] = {
53 0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F,
54 0xF4, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
55 };
56
57 /*
58 * Tables for fast handling of four special First Bytes(E0,ED,F0,F4), after
59 * which the Second Byte are not 80~BF. It contains "range index adjustment".
60 * +------------+---------------+------------------+----------------+
61 * | First Byte | original range| range adjustment | adjusted range |
62 * +------------+---------------+------------------+----------------+
63 * | E0 | 2 | 2 | 4 |
64 * +------------+---------------+------------------+----------------+
65 * | ED | 2 | 3 | 5 |
66 * +------------+---------------+------------------+----------------+
67 * | F0 | 3 | 3 | 6 |
68 * +------------+---------------+------------------+----------------+
69 * | F4 | 4 | 4 | 8 |
70 * +------------+---------------+------------------+----------------+
71 */
72 /* index1 -> E0, index14 -> ED */
73 static const int8_t _df_ee_tbl[] = {
74 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0,
75 };
76 /* index1 -> F0, index5 -> F4 */
77 static const int8_t _ef_fe_tbl[] = {
78 0, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
79 };
80
81 #define RET_ERR_IDX 0 /* Define 1 to return index of first error char */
82
83 /* 5x faster than naive method */
84 /* Return 0 - success, -1 - error, >0 - first error char(if RET_ERR_IDX = 1) */
utf8_range(const unsigned char * data,int len)85 int utf8_range(const unsigned char *data, int len)
86 {
87 #if RET_ERR_IDX
88 int err_pos = 1;
89 #endif
90
91 if (len >= 16) {
92 __m128i prev_input = _mm_set1_epi8(0);
93 __m128i prev_first_len = _mm_set1_epi8(0);
94
95 /* Cached tables */
96 const __m128i first_len_tbl =
97 _mm_loadu_si128((const __m128i *)_first_len_tbl);
98 const __m128i first_range_tbl =
99 _mm_loadu_si128((const __m128i *)_first_range_tbl);
100 const __m128i range_min_tbl =
101 _mm_loadu_si128((const __m128i *)_range_min_tbl);
102 const __m128i range_max_tbl =
103 _mm_loadu_si128((const __m128i *)_range_max_tbl);
104 const __m128i df_ee_tbl =
105 _mm_loadu_si128((const __m128i *)_df_ee_tbl);
106 const __m128i ef_fe_tbl =
107 _mm_loadu_si128((const __m128i *)_ef_fe_tbl);
108
109 __m128i error = _mm_set1_epi8(0);
110
111 while (len >= 16) {
112 const __m128i input = _mm_loadu_si128((const __m128i *)data);
113
114 /* high_nibbles = input >> 4 */
115 const __m128i high_nibbles =
116 _mm_and_si128(_mm_srli_epi16(input, 4), _mm_set1_epi8(0x0F));
117
118 /* first_len = legal character length minus 1 */
119 /* 0 for 00~7F, 1 for C0~DF, 2 for E0~EF, 3 for F0~FF */
120 /* first_len = first_len_tbl[high_nibbles] */
121 __m128i first_len = _mm_shuffle_epi8(first_len_tbl, high_nibbles);
122
123 /* First Byte: set range index to 8 for bytes within 0xC0 ~ 0xFF */
124 /* range = first_range_tbl[high_nibbles] */
125 __m128i range = _mm_shuffle_epi8(first_range_tbl, high_nibbles);
126
127 /* Second Byte: set range index to first_len */
128 /* 0 for 00~7F, 1 for C0~DF, 2 for E0~EF, 3 for F0~FF */
129 /* range |= (first_len, prev_first_len) << 1 byte */
130 range = _mm_or_si128(
131 range, _mm_alignr_epi8(first_len, prev_first_len, 15));
132
133 /* Third Byte: set range index to saturate_sub(first_len, 1) */
134 /* 0 for 00~7F, 0 for C0~DF, 1 for E0~EF, 2 for F0~FF */
135 __m128i tmp;
136 /* tmp = (first_len, prev_first_len) << 2 bytes */
137 tmp = _mm_alignr_epi8(first_len, prev_first_len, 14);
138 /* tmp = saturate_sub(tmp, 1) */
139 tmp = _mm_subs_epu8(tmp, _mm_set1_epi8(1));
140 /* range |= tmp */
141 range = _mm_or_si128(range, tmp);
142
143 /* Fourth Byte: set range index to saturate_sub(first_len, 2) */
144 /* 0 for 00~7F, 0 for C0~DF, 0 for E0~EF, 1 for F0~FF */
145 /* tmp = (first_len, prev_first_len) << 3 bytes */
146 tmp = _mm_alignr_epi8(first_len, prev_first_len, 13);
147 /* tmp = saturate_sub(tmp, 2) */
148 tmp = _mm_subs_epu8(tmp, _mm_set1_epi8(2));
149 /* range |= tmp */
150 range = _mm_or_si128(range, tmp);
151
152 /*
153 * Now we have below range indices caluclated
154 * Correct cases:
155 * - 8 for C0~FF
156 * - 3 for 1st byte after F0~FF
157 * - 2 for 1st byte after E0~EF or 2nd byte after F0~FF
158 * - 1 for 1st byte after C0~DF or 2nd byte after E0~EF or
159 * 3rd byte after F0~FF
160 * - 0 for others
161 * Error cases:
162 * 9,10,11 if non ascii First Byte overlaps
163 * E.g., F1 80 C2 90 --> 8 3 10 2, where 10 indicates error
164 */
165
166 /* Adjust Second Byte range for special First Bytes(E0,ED,F0,F4) */
167 /* Overlaps lead to index 9~15, which are illegal in range table */
168 __m128i shift1, pos, range2;
169 /* shift1 = (input, prev_input) << 1 byte */
170 shift1 = _mm_alignr_epi8(input, prev_input, 15);
171 pos = _mm_sub_epi8(shift1, _mm_set1_epi8(0xEF));
172 /*
173 * shift1: | EF F0 ... FE | FF 00 ... ... DE | DF E0 ... EE |
174 * pos: | 0 1 15 | 16 17 239| 240 241 255|
175 * pos-240: | 0 0 0 | 0 0 0 | 0 1 15 |
176 * pos+112: | 112 113 127| >= 128 | >= 128 |
177 */
178 tmp = _mm_subs_epu8(pos, _mm_set1_epi8(0xF0));
179 range2 = _mm_shuffle_epi8(df_ee_tbl, tmp);
180 tmp = _mm_adds_epu8(pos, _mm_set1_epi8(0x70));
181 range2 = _mm_add_epi8(range2, _mm_shuffle_epi8(ef_fe_tbl, tmp));
182
183 range = _mm_add_epi8(range, range2);
184
185 /* Load min and max values per calculated range index */
186 __m128i minv = _mm_shuffle_epi8(range_min_tbl, range);
187 __m128i maxv = _mm_shuffle_epi8(range_max_tbl, range);
188
189 /* Check value range */
190 #if RET_ERR_IDX
191 error = _mm_cmplt_epi8(input, minv);
192 error = _mm_or_si128(error, _mm_cmpgt_epi8(input, maxv));
193 /* 5% performance drop from this conditional branch */
194 if (!_mm_testz_si128(error, error))
195 break;
196 #else
197 /* error |= (input < minv) | (input > maxv) */
198 tmp = _mm_or_si128(
199 _mm_cmplt_epi8(input, minv),
200 _mm_cmpgt_epi8(input, maxv)
201 );
202 error = _mm_or_si128(error, tmp);
203 #endif
204
205 prev_input = input;
206 prev_first_len = first_len;
207
208 data += 16;
209 len -= 16;
210 #if RET_ERR_IDX
211 err_pos += 16;
212 #endif
213 }
214
215 #if RET_ERR_IDX
216 /* Error in first 16 bytes */
217 if (err_pos == 1)
218 goto do_naive;
219 #else
220 if (!_mm_testz_si128(error, error))
221 return -1;
222 #endif
223
224 /* Find previous token (not 80~BF) */
225 int32_t token4 = _mm_extract_epi32(prev_input, 3);
226 const int8_t *token = (const int8_t *)&token4;
227 int lookahead = 0;
228 if (token[3] > (int8_t)0xBF)
229 lookahead = 1;
230 else if (token[2] > (int8_t)0xBF)
231 lookahead = 2;
232 else if (token[1] > (int8_t)0xBF)
233 lookahead = 3;
234
235 data -= lookahead;
236 len += lookahead;
237 #if RET_ERR_IDX
238 err_pos -= lookahead;
239 #endif
240 }
241
242 /* Check remaining bytes with naive method */
243 #if RET_ERR_IDX
244 int err_pos2;
245 do_naive:
246 err_pos2 = utf8_naive(data, len);
247 if (err_pos2)
248 return err_pos + err_pos2 - 1;
249 return 0;
250 #else
251 return utf8_naive(data, len);
252 #endif
253 }
254
255 #endif
256