Skip to content

Commit 7369339

Browse files
ioioioiolemire
ioioioio
authored and
lemire
committed
Neon utf8validation (simdjson#207)
* utf8 validation on neon works
1 parent 8ace2ba commit 7369339

6 files changed

Lines changed: 344 additions & 60 deletions

File tree

‎Dockerfile‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
# docker build -t simdjson .
2+
# docker run --privileged -t simdjson
3+
FROM gcc:8.3
4+
COPY . /usr/src/
5+
WORKDIR /usr/src/
6+
RUN make clean
7+
RUN make
8+
RUN make test
9+
RUN make parsingcompetition
10+
CMD ["bash", "scripts/parser.sh"]

‎include/simdjson/numberparsing.h‎

Lines changed: 15 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -114,7 +114,8 @@ is_not_structural_or_whitespace_or_exponent_or_decimal(unsigned char c) {
114114
return structural_or_whitespace_or_exponent_or_decimal_negated[c];
115115
}
116116

117-
#if defined (__AVX2__) || defined (__SSE4_2__)
117+
#ifndef SIMDJSON_DISABLE_SWAR_NUMBER_PARSING
118+
// #if defined (__AVX2__) || defined (__SSE4_2__)
118119
#define SWAR_NUMBER_PARSING
119120
#endif
120121

@@ -138,22 +139,7 @@ static inline bool is_made_of_eight_digits_fast(const char *chars) {
138139
0x3333333333333333);
139140
}
140141

141-
// clang-format off
142-
/***
143-
Should parse_eight_digits_unrolled be out of the question, one could
144-
use a standard approach like the following:
145-
146-
static inline uint32_t newparse_eight_digits_unrolled(const char *chars) {
147-
uint64_t val;
148-
memcpy(&val, chars, sizeof(uint64_t));
149-
val = (val & 0x0F0F0F0F0F0F0F0F) * 2561 >> 8;
150-
val = (val & 0x00FF00FF00FF00FF) * 6553601 >> 16;
151-
return (val & 0x0000FFFF0000FFFF) * 42949672960001 >> 32;
152-
}
153-
154-
credit: https://johnnylee-sde.github.io/Fast-numeric-string-to-int/
155-
*/
156-
// clang-format on
142+
#if defined (__AVX2__) || defined (__SSE4_2__)
157143

158144
static inline uint32_t parse_eight_digits_unrolled(const char *chars) {
159145
// this actually computes *16* values so we are being wasteful.
@@ -171,7 +157,19 @@ static inline uint32_t parse_eight_digits_unrolled(const char *chars) {
171157
return _mm_cvtsi128_si32(
172158
t4); // only captures the sum of the first 8 digits, drop the rest
173159
}
160+
#else
161+
// we don't have SSE, so let us use a scalar function
162+
// credit: https://johnnylee-sde.github.io/Fast-numeric-string-to-int/
163+
static inline uint32_t parse_eight_digits_unrolled(const char *chars) {
164+
uint64_t val;
165+
memcpy(&val, chars, sizeof(uint64_t));
166+
val = (val & 0x0F0F0F0F0F0F0F0F) * 2561 >> 8;
167+
val = (val & 0x00FF00FF00FF00FF) * 6553601 >> 16;
168+
return (val & 0x0000FFFF0000FFFF) * 42949672960001 >> 32;
169+
}
174170

171+
172+
#endif
175173
#endif
176174

177175
//

‎include/simdjson/simdutf8check_neon.h‎

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

0 commit comments

Comments
 (0)