Skip to content

Commit 7356b45

Browse files
jkeiserjkeiser
committed
Perform UTF-8 detection via flag lookup algorithm
- adds the alternative zwegner, range and lookup utf8 algorithms as well, for ability to do "shootouts"
1 parent 7d7bec8 commit 7356b45

12 files changed

Lines changed: 1000 additions & 28 deletions

‎Makefile‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -64,7 +64,7 @@ COMPARISONEXECUTABLES=minifiercompetition parsingcompetition parseandstatcompeti
6464
SUPPLEMENTARYEXECUTABLES=parse_noutf8validation parse_nonumberparsing parse_nostringparsing
6565

6666
# Load headers and sources
67-
LIBHEADERS=src/simdprune_tables.h src/numberparsing.h src/jsoncharutils.h src/arm64/bitmask.h src/arm64/simd.h src/arm64/stage1_find_marks.h src/arm64/stage2_build_tape.h src/arm64/stringparsing.h src/generic/stage1_find_marks.h src/generic/stage2_build_tape.h src/generic/stringparsing.h src/haswell/bitmask.h src/haswell/simd.h src/generic/simdutf8check.h src/haswell/stage1_find_marks.h src/haswell/stage2_build_tape.h src/haswell/stringparsing.h src/westmere/bitmask.h src/westmere/simd.h src/westmere/stage1_find_marks.h src/westmere/stage2_build_tape.h src/westmere/stringparsing.h src/generic/stage2_streaming_build_tape.h
67+
LIBHEADERS=src/simdprune_tables.h src/numberparsing.h src/jsoncharutils.h src/arm64/bitmask.h src/arm64/simd.h src/arm64/stage1_find_marks.h src/arm64/stage2_build_tape.h src/arm64/stringparsing.h src/generic/stage1_find_marks.h src/generic/stage2_build_tape.h src/generic/stringparsing.h src/haswell/bitmask.h src/haswell/simd.h src/generic/utf8_fastvalidate_algorithm.h src/generic/utf8_lookup_algorithm.h src/generic/utf8_range_algorithm.h src/generic/utf8_zwegner_algorithm.h src/haswell/stage1_find_marks.h src/haswell/stage2_build_tape.h src/haswell/stringparsing.h src/westmere/bitmask.h src/westmere/simd.h src/westmere/stage1_find_marks.h src/westmere/stage2_build_tape.h src/westmere/stringparsing.h src/generic/stage2_streaming_build_tape.h
6868
PUBHEADERS=include/simdjson/common_defs.h include/simdjson/isadetection.h include/simdjson/jsonformatutils.h include/simdjson/jsonioutil.h include/simdjson/jsonminifier.h include/simdjson/jsonparser.h include/simdjson/padded_string.h include/simdjson/parsedjson.h include/simdjson/parsedjsoniterator.h include/simdjson/portability.h include/simdjson/simdjson.h include/simdjson/simdjson_version.h include/simdjson/stage1_find_marks.h include/simdjson/stage2_build_tape.h
6969
HEADERS=$(PUBHEADERS) $(LIBHEADERS)
7070

‎src/CMakeLists.txt‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -47,7 +47,10 @@ set(SIMDJSON_SRC_HEADERS
4747
generic/stage2_build_tape.h
4848
generic/stage2_streaming_build_tape.h
4949
generic/stringparsing.h
50-
generic/simdutf8check.h
50+
generic/utf8_fastvalidate_algorithm.h
51+
generic/utf8_lookup_algorithm.h
52+
generic/utf8_range_algorithm.h
53+
generic/utf8_zwegner_algorithm.h
5154
haswell/bitmask.h
5255
haswell/simd.h
5356
haswell/stage1_find_marks.h

‎src/arm64/simd.h‎

Lines changed: 22 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -47,7 +47,8 @@ namespace simdjson::arm64::simd {
4747
// SIMD byte mask type (returned by things like eq and gt)
4848
template<>
4949
struct simd8<bool>: base_u8<bool> {
50-
typedef uint32_t bitmask_t;
50+
typedef uint16_t bitmask_t;
51+
typedef uint32_t bitmask2_t;
5152

5253
static really_inline simd8<bool> splat(bool _value) { return vmovq_n_u8(-(!!_value)); }
5354

@@ -57,7 +58,9 @@ namespace simdjson::arm64::simd {
5758
// Splat constructor
5859
really_inline simd8(bool _value) : simd8(splat(_value)) {}
5960

60-
really_inline simd8<bool>::bitmask_t to_bitmask() const {
61+
// We return uint32_t instead of uint16_t because that seems to be more efficient for most
62+
// purposes (cutting it down to uint16_t costs performance in some compilers).
63+
really_inline uint32_t to_bitmask() const {
6164
const uint8x16_t bit_mask = {0x01, 0x02, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80,
6265
0x01, 0x02, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};
6366
auto minput = *this & bit_mask;
@@ -119,6 +122,8 @@ namespace simdjson::arm64::simd {
119122
really_inline simd8<uint8_t> max(const simd8<uint8_t> other) const { return vmaxq_u8(*this, other); }
120123
really_inline simd8<uint8_t> min(const simd8<uint8_t> other) const { return vminq_u8(*this, other); }
121124
really_inline simd8<bool> operator<=(const simd8<uint8_t> other) const { return vcleq_u8(*this, other); }
125+
really_inline simd8<bool> operator>=(const simd8<uint8_t> other) const { return vcgeq_u8(*this, other); }
126+
really_inline simd8<bool> operator>(const simd8<uint8_t> other) const { return vcgtq_u8(*this, other); }
122127

123128
// Bit-specific operations
124129
really_inline simd8<bool> any_bits_set(simd8<uint8_t> bits) const { return vtstq_u8(*this, bits); }
@@ -131,18 +136,21 @@ namespace simdjson::arm64::simd {
131136

132137
// Perform a lookup assuming the value is between 0 and 16 (undefined behavior for out of range values)
133138
template<typename L>
139+
really_inline simd8<L> lookup_16(simd8<L> lookup_table) const {
140+
return lookup_table.apply_lookup_16_to(*this);
141+
}
142+
template<typename L>
134143
really_inline simd8<L> lookup_16(
135144
L replace0, L replace1, L replace2, L replace3,
136145
L replace4, L replace5, L replace6, L replace7,
137146
L replace8, L replace9, L replace10, L replace11,
138147
L replace12, L replace13, L replace14, L replace15) const {
139-
simd8<L> lookup_table(
148+
return lookup_16(simd8<L>::repeat_16(
140149
replace0, replace1, replace2, replace3,
141150
replace4, replace5, replace6, replace7,
142151
replace8, replace9, replace10, replace11,
143152
replace12, replace13, replace14, replace15
144-
);
145-
return lookup_table.apply_lookup_16_to(*this);
153+
));
146154
}
147155

148156
template<typename T>
@@ -178,7 +186,7 @@ namespace simdjson::arm64::simd {
178186
) : simd8(int8x16_t{
179187
v0, v1, v2, v3, v4, v5, v6, v7,
180188
v8, v9, v10,v11,v12,v13,v14,v15
181-
}) {}
189+
}) {}
182190
// Repeat 16 values as many times as necessary (usually for lookup tables)
183191
really_inline static simd8<int8_t> repeat_16(
184192
int8_t v0, int8_t v1, int8_t v2, int8_t v3, int8_t v4, int8_t v5, int8_t v6, int8_t v7,
@@ -214,24 +222,28 @@ namespace simdjson::arm64::simd {
214222
return vextq_s8(prev_chunk, *this, 16 - N);
215223
}
216224

217-
// Perform a lookup of the lower 4 bits
225+
// Perform a lookup assuming no value is larger than 16
226+
template<typename L>
227+
really_inline simd8<L> lookup_16(simd8<L> lookup_table) const {
228+
return lookup_table.apply_lookup_16_to(*this);
229+
}
218230
template<typename L>
219231
really_inline simd8<L> lookup_16(
220232
L replace0, L replace1, L replace2, L replace3,
221233
L replace4, L replace5, L replace6, L replace7,
222234
L replace8, L replace9, L replace10, L replace11,
223235
L replace12, L replace13, L replace14, L replace15) const {
224-
return simd8<uint8_t>(*this).lookup_16(
236+
return lookup_16(simd8<L>::repeat_16(
225237
replace0, replace1, replace2, replace3,
226238
replace4, replace5, replace6, replace7,
227239
replace8, replace9, replace10, replace11,
228240
replace12, replace13, replace14, replace15
229-
);
241+
));
230242
}
231243

232244
template<typename T>
233245
really_inline simd8<int8_t> apply_lookup_16_to(const simd8<T> original) {
234-
return vqtbl1q_s8(*this, original);
246+
return vqtbl1q_s8(*this, simd8<uint8_t>(original));
235247
}
236248
};
237249

‎src/arm64/stage1_find_marks.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -29,7 +29,7 @@ really_inline void find_whitespace_and_operators(
2929
whitespace = v.map([&](simd8<uint8_t> _v) { return _v.any_bits_set(0x18); }).to_bitmask();
3030
}
3131

32-
#include "generic/simdutf8check.h"
32+
#include "generic/utf8_fastvalidate_algorithm.h"
3333
#include "generic/stage1_find_marks.h"
3434

3535
} // namespace simdjson::arm64

src/generic/simdutf8check.h renamed to src/generic/utf8_fastvalidate_algorithm.h

File renamed without changes.

0 commit comments

Comments
 (0)