| 1 |
#ifdef __AVX2__ |
| 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 print256(const char *s, const __m256i v256) |
| 11 |
{ |
| 12 |
const unsigned char *v8 = (const unsigned char *)&v256; |
| 13 |
if (s) |
| 14 |
printf("%s:\t", s); |
| 15 |
for (int i = 0; i < 32; 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 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, |
| 31 |
}; |
| 32 |
|
| 33 |
/* Map "First Byte" to 8-th item of range table (0xC2 ~ 0xF4) */ |
| 34 |
static const int8_t _first_range_tbl[] = { |
| 35 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, |
| 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: i >= 127 && i <= -128 |
| 49 |
*/ |
| 50 |
static const int8_t _range_min_tbl[] = { |
| 51 |
0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80, |
| 52 |
0xC2, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, |
| 53 |
0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80, |
| 54 |
0xC2, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, |
| 55 |
}; |
| 56 |
static const int8_t _range_max_tbl[] = { |
| 57 |
0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F, |
| 58 |
0xF4, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, |
| 59 |
0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F, |
| 60 |
0xF4, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, |
| 61 |
}; |
| 62 |
|
| 63 |
/* |
| 64 |
* Tables for fast handling of four special First Bytes(E0,ED,F0,F4), after |
| 65 |
* which the Second Byte are not 80~BF. It contains "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 |
*/ |
| 78 |
/* index1 -> E0, index14 -> ED */ |
| 79 |
static const int8_t _df_ee_tbl[] = { |
| 80 |
0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, |
| 81 |
0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, |
| 82 |
}; |
| 83 |
/* index1 -> F0, index5 -> F4 */ |
| 84 |
static const int8_t _ef_fe_tbl[] = { |
| 85 |
0, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
| 86 |
0, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
| 87 |
}; |
| 88 |
|
| 89 |
#define RET_ERR_IDX 0 /* Define 1 to return index of first error char */ |
| 90 |
|
| 91 |
static inline __m256i push_last_byte_of_a_to_b(__m256i a, __m256i b) { |
| 92 |
return _mm256_alignr_epi8(b, _mm256_permute2x128_si256(a, b, 0x21), 15); |
| 93 |
} |
| 94 |
|
| 95 |
static inline __m256i push_last_2bytes_of_a_to_b(__m256i a, __m256i b) { |
| 96 |
return _mm256_alignr_epi8(b, _mm256_permute2x128_si256(a, b, 0x21), 14); |
| 97 |
} |
| 98 |
|
| 99 |
static inline __m256i push_last_3bytes_of_a_to_b(__m256i a, __m256i b) { |
| 100 |
return _mm256_alignr_epi8(b, _mm256_permute2x128_si256(a, b, 0x21), 13); |
| 101 |
} |
| 102 |
|
| 103 |
/* 5x faster than naive method */ |
| 104 |
/* Return 0 - success, -1 - error, >0 - first error char(if RET_ERR_IDX = 1) */ |
| 105 |
int utf8_range_avx2(const unsigned char *data, int len) |
| 106 |
{ |
| 107 |
#if RET_ERR_IDX |
| 108 |
int err_pos = 1; |
| 109 |
#endif |
| 110 |
|
| 111 |
if (len >= 32) { |
| 112 |
__m256i prev_input = _mm256_set1_epi8(0); |
| 113 |
__m256i prev_first_len = _mm256_set1_epi8(0); |
| 114 |
|
| 115 |
/* Cached tables */ |
| 116 |
const __m256i first_len_tbl = |
| 117 |
_mm256_loadu_si256((const __m256i *)_first_len_tbl); |
| 118 |
const __m256i first_range_tbl = |
| 119 |
_mm256_loadu_si256((const __m256i *)_first_range_tbl); |
| 120 |
const __m256i range_min_tbl = |
| 121 |
_mm256_loadu_si256((const __m256i *)_range_min_tbl); |
| 122 |
const __m256i range_max_tbl = |
| 123 |
_mm256_loadu_si256((const __m256i *)_range_max_tbl); |
| 124 |
const __m256i df_ee_tbl = |
| 125 |
_mm256_loadu_si256((const __m256i *)_df_ee_tbl); |
| 126 |
const __m256i ef_fe_tbl = |
| 127 |
_mm256_loadu_si256((const __m256i *)_ef_fe_tbl); |
| 128 |
|
| 129 |
#if !RET_ERR_IDX |
| 130 |
__m256i error1 = _mm256_set1_epi8(0); |
| 131 |
__m256i error2 = _mm256_set1_epi8(0); |
| 132 |
#endif |
| 133 |
|
| 134 |
while (len >= 32) { |
| 135 |
const __m256i input = _mm256_loadu_si256((const __m256i *)data); |
| 136 |
|
| 137 |
/* high_nibbles = input >> 4 */ |
| 138 |
const __m256i high_nibbles = |
| 139 |
_mm256_and_si256(_mm256_srli_epi16(input, 4), _mm256_set1_epi8(0x0F)); |
| 140 |
|
| 141 |
/* first_len = legal character length minus 1 */ |
| 142 |
/* 0 for 00~7F, 1 for C0~DF, 2 for E0~EF, 3 for F0~FF */ |
| 143 |
/* first_len = first_len_tbl[high_nibbles] */ |
| 144 |
__m256i first_len = _mm256_shuffle_epi8(first_len_tbl, high_nibbles); |
| 145 |
|
| 146 |
/* First Byte: set range index to 8 for bytes within 0xC0 ~ 0xFF */ |
| 147 |
/* range = first_range_tbl[high_nibbles] */ |
| 148 |
__m256i range = _mm256_shuffle_epi8(first_range_tbl, high_nibbles); |
| 149 |
|
| 150 |
/* Second Byte: set range index to first_len */ |
| 151 |
/* 0 for 00~7F, 1 for C0~DF, 2 for E0~EF, 3 for F0~FF */ |
| 152 |
/* range |= (first_len, prev_first_len) << 1 byte */ |
| 153 |
range = _mm256_or_si256( |
| 154 |
range, push_last_byte_of_a_to_b(prev_first_len, first_len)); |
| 155 |
|
| 156 |
/* Third Byte: set range index to saturate_sub(first_len, 1) */ |
| 157 |
/* 0 for 00~7F, 0 for C0~DF, 1 for E0~EF, 2 for F0~FF */ |
| 158 |
__m256i tmp1, tmp2; |
| 159 |
|
| 160 |
/* tmp1 = (first_len, prev_first_len) << 2 bytes */ |
| 161 |
tmp1 = push_last_2bytes_of_a_to_b(prev_first_len, first_len); |
| 162 |
/* tmp2 = saturate_sub(tmp1, 1) */ |
| 163 |
tmp2 = _mm256_subs_epu8(tmp1, _mm256_set1_epi8(1)); |
| 164 |
|
| 165 |
/* range |= tmp2 */ |
| 166 |
range = _mm256_or_si256(range, tmp2); |
| 167 |
|
| 168 |
/* Fourth Byte: set range index to saturate_sub(first_len, 2) */ |
| 169 |
/* 0 for 00~7F, 0 for C0~DF, 0 for E0~EF, 1 for F0~FF */ |
| 170 |
/* tmp1 = (first_len, prev_first_len) << 3 bytes */ |
| 171 |
tmp1 = push_last_3bytes_of_a_to_b(prev_first_len, first_len); |
| 172 |
/* tmp2 = saturate_sub(tmp1, 2) */ |
| 173 |
tmp2 = _mm256_subs_epu8(tmp1, _mm256_set1_epi8(2)); |
| 174 |
/* range |= tmp2 */ |
| 175 |
range = _mm256_or_si256(range, tmp2); |
| 176 |
|
| 177 |
/* |
| 178 |
* Now we have below range indices caluclated |
| 179 |
* Correct cases: |
| 180 |
* - 8 for C0~FF |
| 181 |
* - 3 for 1st byte after F0~FF |
| 182 |
* - 2 for 1st byte after E0~EF or 2nd byte after F0~FF |
| 183 |
* - 1 for 1st byte after C0~DF or 2nd byte after E0~EF or |
| 184 |
* 3rd byte after F0~FF |
| 185 |
* - 0 for others |
| 186 |
* Error cases: |
| 187 |
* 9,10,11 if non ascii First Byte overlaps |
| 188 |
* E.g., F1 80 C2 90 --> 8 3 10 2, where 10 indicates error |
| 189 |
*/ |
| 190 |
|
| 191 |
/* Adjust Second Byte range for special First Bytes(E0,ED,F0,F4) */ |
| 192 |
/* Overlaps lead to index 9~15, which are illegal in range table */ |
| 193 |
__m256i shift1, pos, range2; |
| 194 |
/* shift1 = (input, prev_input) << 1 byte */ |
| 195 |
shift1 = push_last_byte_of_a_to_b(prev_input, input); |
| 196 |
pos = _mm256_sub_epi8(shift1, _mm256_set1_epi8(0xEF)); |
| 197 |
/* |
| 198 |
* shift1: | EF F0 ... FE | FF 00 ... ... DE | DF E0 ... EE | |
| 199 |
* pos: | 0 1 15 | 16 17 239| 240 241 255| |
| 200 |
* pos-240: | 0 0 0 | 0 0 0 | 0 1 15 | |
| 201 |
* pos+112: | 112 113 127| >= 128 | >= 128 | |
| 202 |
*/ |
| 203 |
tmp1 = _mm256_subs_epu8(pos, _mm256_set1_epi8(240)); |
| 204 |
range2 = _mm256_shuffle_epi8(df_ee_tbl, tmp1); |
| 205 |
tmp2 = _mm256_adds_epu8(pos, _mm256_set1_epi8(112)); |
| 206 |
range2 = _mm256_add_epi8(range2, _mm256_shuffle_epi8(ef_fe_tbl, tmp2)); |
| 207 |
|
| 208 |
range = _mm256_add_epi8(range, range2); |
| 209 |
|
| 210 |
/* Load min and max values per calculated range index */ |
| 211 |
__m256i minv = _mm256_shuffle_epi8(range_min_tbl, range); |
| 212 |
__m256i maxv = _mm256_shuffle_epi8(range_max_tbl, range); |
| 213 |
|
| 214 |
/* Check value range */ |
| 215 |
#if RET_ERR_IDX |
| 216 |
__m256i error = _mm256_cmpgt_epi8(minv, input); |
| 217 |
error = _mm256_or_si256(error, _mm256_cmpgt_epi8(input, maxv)); |
| 218 |
/* 5% performance drop from this conditional branch */ |
| 219 |
if (!_mm256_testz_si256(error, error)) |
| 220 |
break; |
| 221 |
#else |
| 222 |
error1 = _mm256_or_si256(error1, _mm256_cmpgt_epi8(minv, input)); |
| 223 |
error2 = _mm256_or_si256(error2, _mm256_cmpgt_epi8(input, maxv)); |
| 224 |
#endif |
| 225 |
|
| 226 |
prev_input = input; |
| 227 |
prev_first_len = first_len; |
| 228 |
|
| 229 |
data += 32; |
| 230 |
len -= 32; |
| 231 |
#if RET_ERR_IDX |
| 232 |
err_pos += 32; |
| 233 |
#endif |
| 234 |
} |
| 235 |
|
| 236 |
#if RET_ERR_IDX |
| 237 |
/* Error in first 16 bytes */ |
| 238 |
if (err_pos == 1) |
| 239 |
goto do_naive; |
| 240 |
#else |
| 241 |
__m256i error = _mm256_or_si256(error1, error2); |
| 242 |
if (!_mm256_testz_si256(error, error)) |
| 243 |
return -1; |
| 244 |
#endif |
| 245 |
|
| 246 |
/* Find previous token (not 80~BF) */ |
| 247 |
int32_t token4 = _mm256_extract_epi32(prev_input, 7); |
| 248 |
const int8_t *token = (const int8_t *)&token4; |
| 249 |
int lookahead = 0; |
| 250 |
if (token[3] > (int8_t)0xBF) |
| 251 |
lookahead = 1; |
| 252 |
else if (token[2] > (int8_t)0xBF) |
| 253 |
lookahead = 2; |
| 254 |
else if (token[1] > (int8_t)0xBF) |
| 255 |
lookahead = 3; |
| 256 |
|
| 257 |
data -= lookahead; |
| 258 |
len += lookahead; |
| 259 |
#if RET_ERR_IDX |
| 260 |
err_pos -= lookahead; |
| 261 |
#endif |
| 262 |
} |
| 263 |
|
| 264 |
/* Check remaining bytes with naive method */ |
| 265 |
#if RET_ERR_IDX |
| 266 |
int err_pos2; |
| 267 |
do_naive: |
| 268 |
err_pos2 = utf8_naive(data, len); |
| 269 |
if (err_pos2) |
| 270 |
return err_pos + err_pos2 - 1; |
| 271 |
return 0; |
| 272 |
#else |
| 273 |
return utf8_naive(data, len); |
| 274 |
#endif |
| 275 |
} |
| 276 |
|
| 277 |
#endif |