1 #ifdef __aarch64__
2
3 #include <stdio.h>
4 #include <stdint.h>
5 #include <arm_neon.h>
6
7 int utf8_naive(const unsigned char *data, int len);
8
9 #if 0
10 static void print128(const char *s, const uint8x16_t v128)
11 {
12 unsigned char v8[16];
13 vst1q_u8(v8, v128);
14
15 if (s)
16 printf("%s:\t", s);
17 for (int i = 0; i < 16; ++i)
18 printf("%02x ", v8[i]);
19 printf("\n");
20 }
21 #endif
22
23 /*
24 * Map high nibble of "First Byte" to legal character length minus 1
25 * 0x00 ~ 0xBF --> 0
26 * 0xC0 ~ 0xDF --> 1
27 * 0xE0 ~ 0xEF --> 2
28 * 0xF0 ~ 0xFF --> 3
29 */
30 static const uint8_t _first_len_tbl[] = {
31 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3,
32 };
33
34 /* Map "First Byte" to 8-th item of range table (0xC2 ~ 0xF4) */
35 static const uint8_t _first_range_tbl[] = {
36 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8,
37 };
38
39 /*
40 * Range table, map range index to min and max values
41 * Index 0 : 00 ~ 7F (First Byte, ascii)
42 * Index 1,2,3: 80 ~ BF (Second, Third, Fourth Byte)
43 * Index 4 : A0 ~ BF (Second Byte after E0)
44 * Index 5 : 80 ~ 9F (Second Byte after ED)
45 * Index 6 : 90 ~ BF (Second Byte after F0)
46 * Index 7 : 80 ~ 8F (Second Byte after F4)
47 * Index 8 : C2 ~ F4 (First Byte, non ascii)
48 * Index 9~15 : illegal: u >= 255 && u <= 0
49 */
50 static const uint8_t _range_min_tbl[] = {
51 0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80,
52 0xC2, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
53 };
54 static const uint8_t _range_max_tbl[] = {
55 0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F,
56 0xF4, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
57 };
58
59 /*
60 * This table is for fast handling four special First Bytes(E0,ED,F0,F4), after
61 * which the Second Byte are not 80~BF. It contains "range index adjustment".
62 * - The idea is to minus byte with E0, use the result(0~31) as the index to
63 * lookup the "range index adjustment". Then add the adjustment to original
64 * range index to get the correct range.
65 * - Range index adjustment
66 * +------------+---------------+------------------+----------------+
67 * | First Byte | original range| range adjustment | adjusted range |
68 * +------------+---------------+------------------+----------------+
69 * | E0 | 2 | 2 | 4 |
70 * +------------+---------------+------------------+----------------+
71 * | ED | 2 | 3 | 5 |
72 * +------------+---------------+------------------+----------------+
73 * | F0 | 3 | 3 | 6 |
74 * +------------+---------------+------------------+----------------+
75 * | F4 | 4 | 4 | 8 |
76 * +------------+---------------+------------------+----------------+
77 * - Below is a uint8x16x2 table, data is interleaved in NEON register. So I'm
78 * putting it vertically. 1st column is for E0~EF, 2nd column for F0~FF.
79 */
80 static const uint8_t _range_adjust_tbl[] = {
81 /* index -> 0~15 16~31 <- index */
82 /* E0 -> */ 2, 3, /* <- F0 */
83 0, 0,
84 0, 0,
85 0, 0,
86 0, 4, /* <- F4 */
87 0, 0,
88 0, 0,
89 0, 0,
90 0, 0,
91 0, 0,
92 0, 0,
93 0, 0,
94 0, 0,
95 /* ED -> */ 3, 0,
96 0, 0,
97 0, 0,
98 };
99
100 /* 2x ~ 4x faster than naive method */
101 /* Return 0 on success, -1 on error */
utf8_range(const unsigned char * data,int len)102 int utf8_range(const unsigned char *data, int len)
103 {
104 if (len >= 16) {
105 uint8x16_t prev_input = vdupq_n_u8(0);
106 uint8x16_t prev_first_len = vdupq_n_u8(0);
107
108 /* Cached tables */
109 const uint8x16_t first_len_tbl = vld1q_u8(_first_len_tbl);
110 const uint8x16_t first_range_tbl = vld1q_u8(_first_range_tbl);
111 const uint8x16_t range_min_tbl = vld1q_u8(_range_min_tbl);
112 const uint8x16_t range_max_tbl = vld1q_u8(_range_max_tbl);
113 const uint8x16x2_t range_adjust_tbl = vld2q_u8(_range_adjust_tbl);
114
115 /* Cached values */
116 const uint8x16_t const_1 = vdupq_n_u8(1);
117 const uint8x16_t const_2 = vdupq_n_u8(2);
118 const uint8x16_t const_e0 = vdupq_n_u8(0xE0);
119
120 /* We use two error registers to remove a dependency. */
121 uint8x16_t error1 = vdupq_n_u8(0);
122 uint8x16_t error2 = vdupq_n_u8(0);
123
124 while (len >= 16) {
125 const uint8x16_t input = vld1q_u8(data);
126
127 /* high_nibbles = input >> 4 */
128 const uint8x16_t high_nibbles = vshrq_n_u8(input, 4);
129
130 /* first_len = legal character length minus 1 */
131 /* 0 for 00~7F, 1 for C0~DF, 2 for E0~EF, 3 for F0~FF */
132 /* first_len = first_len_tbl[high_nibbles] */
133 const uint8x16_t first_len =
134 vqtbl1q_u8(first_len_tbl, high_nibbles);
135
136 /* First Byte: set range index to 8 for bytes within 0xC0 ~ 0xFF */
137 /* range = first_range_tbl[high_nibbles] */
138 uint8x16_t range = vqtbl1q_u8(first_range_tbl, high_nibbles);
139
140 /* Second Byte: set range index to first_len */
141 /* 0 for 00~7F, 1 for C0~DF, 2 for E0~EF, 3 for F0~FF */
142 /* range |= (first_len, prev_first_len) << 1 byte */
143 range =
144 vorrq_u8(range, vextq_u8(prev_first_len, first_len, 15));
145
146 /* Third Byte: set range index to saturate_sub(first_len, 1) */
147 /* 0 for 00~7F, 0 for C0~DF, 1 for E0~EF, 2 for F0~FF */
148 uint8x16_t tmp1, tmp2;
149 /* tmp1 = (first_len, prev_first_len) << 2 bytes */
150 tmp1 = vextq_u8(prev_first_len, first_len, 14);
151 /* tmp1 = saturate_sub(tmp1, 1) */
152 tmp1 = vqsubq_u8(tmp1, const_1);
153 /* range |= tmp1 */
154 range = vorrq_u8(range, tmp1);
155
156 /* Fourth Byte: set range index to saturate_sub(first_len, 2) */
157 /* 0 for 00~7F, 0 for C0~DF, 0 for E0~EF, 1 for F0~FF */
158 /* tmp2 = (first_len, prev_first_len) << 3 bytes */
159 tmp2 = vextq_u8(prev_first_len, first_len, 13);
160 /* tmp2 = saturate_sub(tmp2, 2) */
161 tmp2 = vqsubq_u8(tmp2, const_2);
162 /* range |= tmp2 */
163 range = vorrq_u8(range, tmp2);
164
165 /*
166 * Now we have below range indices caluclated
167 * Correct cases:
168 * - 8 for C0~FF
169 * - 3 for 1st byte after F0~FF
170 * - 2 for 1st byte after E0~EF or 2nd byte after F0~FF
171 * - 1 for 1st byte after C0~DF or 2nd byte after E0~EF or
172 * 3rd byte after F0~FF
173 * - 0 for others
174 * Error cases:
175 * 9,10,11 if non ascii First Byte overlaps
176 * E.g., F1 80 C2 90 --> 8 3 10 2, where 10 indicates error
177 */
178
179 /* Adjust Second Byte range for special First Bytes(E0,ED,F0,F4) */
180 /* See _range_adjust_tbl[] definition for details */
181 /* Overlaps lead to index 9~15, which are illegal in range table */
182 uint8x16_t shift1 = vextq_u8(prev_input, input, 15);
183 uint8x16_t pos = vsubq_u8(shift1, const_e0);
184 range = vaddq_u8(range, vqtbl2q_u8(range_adjust_tbl, pos));
185
186 /* Load min and max values per calculated range index */
187 uint8x16_t minv = vqtbl1q_u8(range_min_tbl, range);
188 uint8x16_t maxv = vqtbl1q_u8(range_max_tbl, range);
189
190 /* Check value range */
191 error1 = vorrq_u8(error1, vcltq_u8(input, minv));
192 error2 = vorrq_u8(error2, vcgtq_u8(input, maxv));
193
194 prev_input = input;
195 prev_first_len = first_len;
196
197 data += 16;
198 len -= 16;
199 }
200 /* Merge our error counters together */
201 error1 = vorrq_u8(error1, error2);
202
203 /* Delay error check till loop ends */
204 if (vmaxvq_u8(error1))
205 return -1;
206
207 /* Find previous token (not 80~BF) */
208 uint32_t token4;
209 vst1q_lane_u32(&token4, vreinterpretq_u32_u8(prev_input), 3);
210
211 const int8_t *token = (const int8_t *)&token4;
212 int lookahead = 0;
213 if (token[3] > (int8_t)0xBF)
214 lookahead = 1;
215 else if (token[2] > (int8_t)0xBF)
216 lookahead = 2;
217 else if (token[1] > (int8_t)0xBF)
218 lookahead = 3;
219
220 data -= lookahead;
221 len += lookahead;
222 }
223
224 /* Check remaining bytes with naive method */
225 return utf8_naive(data, len);
226 }
227
228 #endif
229