13 #include <daw/daw_hide.h>
14 #include <daw/daw_uint_buffer.h>
16 #if defined( DAW_ALLOW_SSE42 )
17 #include <emmintrin.h>
18 #include <nmmintrin.h>
19 #include <smmintrin.h>
20 #include <tmmintrin.h>
21 #include <wmmintrin.h>
22 #include <xmmintrin.h>
32 namespace daw::json::json_details {
33 DAW_ATTRIBUTE_FLATTEN
static inline constexpr
bool
34 is_escaped(
char const *ptr,
char const *min_ptr ) {
35 if( *( ptr - 1 ) !=
'\\' ) {
38 if( ( ptr - min_ptr ) < 2 ) {
41 return *( ptr - 2 ) !=
'\\';
45 alignas( 16 )
bool values[256] = { };
47 constexpr
bool operator[](
char idx )
const {
48 return values[
static_cast<unsigned char>( idx )];
52 template<
char... keys>
53 static constexpr
inline key_table_t key_table = [] {
54 auto result = key_table_t{ };
55 (void)( ( result.values[
static_cast<unsigned char>( keys )] = true ) |
60 static inline std::ptrdiff_t find_lsb_set( runtime_exec_tag
const &,
62 #if defined( __GNUC__ ) or defined( __clang__ )
63 return __builtin_ffs(
static_cast<int>( value ) ) - 1;
66 _BitScanForward( &index,
static_cast<int>( value ) );
67 return static_cast<std::ptrdiff_t
>( index );
71 #if defined( DAW_ALLOW_SSE42 )
72 DAW_ATTRIBUTE_FLATTEN
static inline __m128i
73 set_reverse(
char c0,
char c1 = 0,
char c2 = 0,
char c3 = 0,
char c4 = 0,
74 char c5 = 0,
char c6 = 0,
char c7 = 0,
char c8 = 0,
char c9 = 0,
75 char c10 = 0,
char c11 = 0,
char c12 = 0,
char c13 = 0,
76 char c14 = 0,
char c15 = 0 ) {
77 return _mm_set_epi8( c15, c14, c13, c12, c11, c10, c9, c8, c7, c6, c5, c4,
81 DAW_ATTRIBUTE_FLATTEN
static inline __m128i
82 uload16_char_data( sse42_exec_tag
const &,
char const *ptr ) {
83 return _mm_loadu_si128(
reinterpret_cast<__m128i
const *
>( ptr ) );
87 DAW_ATTRIBUTE_FLATTEN
static inline UInt32
88 mem_find_eq( sse42_exec_tag
const &, __m128i block ) {
89 static __m128i
const keys = _mm_set1_epi8( k );
90 __m128i
const found = _mm_cmpeq_epi8( block, keys );
91 return to_uint32( _mm_movemask_epi8( found ) );
94 template<
unsigned char k>
95 DAW_ATTRIBUTE_FLATTEN
static inline UInt32
96 mem_find_gt( sse42_exec_tag
const &, __m128i block ) {
97 static __m128i
const keys = _mm_set1_epi8( k );
98 __m128i
const found = _mm_cmpgt_epi8( block, keys );
99 return to_uint32( _mm_movemask_epi8( found ) );
102 template<
bool is_unchecked_input,
char... keys>
103 DAW_ATTRIBUTE_FLATTEN
static inline char const *
104 mem_move_to_next_of( sse42_exec_tag
const &tag,
char const *first,
105 char const *
const last ) {
107 while( last - first >= 16 ) {
108 auto const val0 = uload16_char_data( tag, first );
109 auto const key_positions = ( mem_find_eq<keys>( tag, val0 ) | ... );
110 if( key_positions != 0 ) {
111 return first + find_lsb_set( tag, key_positions );
115 if( last - first >= 8 ) {
116 char const buff[16]{ first[0], first[1], first[2], first[3],
117 first[4], first[5], first[6], first[7] };
118 auto const val0 = uload16_char_data( tag, buff );
119 auto const key_positions =
120 ( mem_find_eq<keys>( tag, val0 ) | ... ) & mask_from_lsb32<8>;
121 if( key_positions != 0 ) {
122 return first + find_lsb_set( tag, key_positions );
126 if( last - first >= 4 ) {
127 char const buff[16]{ first[0], first[1], first[2], first[3] };
128 auto const val0 = uload16_char_data( tag, buff );
129 auto const key_positions =
130 ( mem_find_eq<keys>( tag, val0 ) | ... ) & mask_from_lsb32<4>;
131 if( key_positions != 0 ) {
132 return first + find_lsb_set( tag, key_positions );
136 switch( last - first ) {
141 static_cast<std::ptrdiff_t
>( not key_table<keys...>[*first] );
143 char const buff[16]{ first[0], first[1] };
144 auto const val0 = uload16_char_data( tag, buff );
145 auto const key_positions =
146 ( mem_find_eq<keys>( tag, val0 ) | ... ) & mask_from_lsb32<2>;
147 if( key_positions != 0 ) {
148 return first + find_lsb_set( tag, key_positions );
153 char const buff[16]{ first[0], first[1], first[2] };
154 auto const val0 = uload16_char_data( tag, buff );
155 auto const key_positions =
156 ( mem_find_eq<keys>( tag, val0 ) | ... ) & mask_from_lsb32<3>;
157 if( key_positions != 0 ) {
158 return first + find_lsb_set( tag, key_positions );
166 template<
bool is_unchecked_input,
char... keys>
167 DAW_ATTRIBUTE_FLATTEN
static inline char const *
168 mem_move_to_next_not_of( sse42_exec_tag
const &tag,
char const *first,
170 static constexpr
int keys_len =
static_cast<int>(
sizeof...( keys ) );
171 static_assert( keys_len <= 16 );
172 __m128i
const a = set_reverse( keys... );
173 static constexpr
int compare_mode =
174 _SIDD_SBYTE_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_NEGATIVE_POLARITY;
176 while( last - first >= 16 ) {
177 auto const b = uload16_char_data( tag, first );
178 int const b_len = 16;
179 int result = _mm_cmpestri( a, keys_len, b, b_len, compare_mode );
185 static constexpr
auto is_eq = [](
char c ) {
186 return ( ( c == keys ) | ... );
188 if constexpr( is_unchecked_input ) {
189 while( is_eq( *first ) ) {
193 while( first < last and is_eq( *first ) ) {
200 template<
typename U32>
201 DAW_ATTRIBUTE_FLATTEN
static inline bool add_overflow( U32 value1, U32 value2,
203 static_assert(
sizeof( U32 ) <=
sizeof(
unsigned long long ) );
204 static_assert(
sizeof( U32 ) == 4 );
205 #if defined( __clang__ ) or defined( __GNUC__ )
206 if constexpr(
sizeof(
unsigned ) ==
sizeof( U32 ) ) {
207 return __builtin_uadd_overflow(
static_cast<unsigned>( value1 ),
208 static_cast<unsigned>( value2 ),
209 reinterpret_cast<unsigned *
>( &result ) );
210 }
else if constexpr(
sizeof(
unsigned long ) ==
sizeof( U32 ) ) {
211 return __builtin_uaddl_overflow(
212 static_cast<unsigned long>( value1 ),
213 static_cast<unsigned long>( value2 ),
214 reinterpret_cast<unsigned long *
>( &result ) );
216 return __builtin_uaddll_overflow(
217 static_cast<unsigned long long>( value1 ),
218 static_cast<unsigned long long>( value2 ),
219 reinterpret_cast<unsigned long long *
>( &result ) );
222 return _addcarry_u32( 0,
static_cast<std::uint32_t
>( value1 ),
223 static_cast<std::uint32_t
>( value2 ),
224 reinterpret_cast<std::uint32_t *
>( &result ) );
230 DAW_ATTRIBUTE_FLATTEN
static inline constexpr UInt32
231 find_escaped_branchless( constexpr_exec_tag
const &, UInt32 &prev_escaped,
232 UInt32 backslashes ) {
233 backslashes &= ~prev_escaped;
234 UInt32 follow_escape = ( backslashes << 1 ) | prev_escaped;
235 constexpr UInt32 even_bits = 0x5555
'5555_u32;
237 UInt32 const odd_seq_start =
238 backslashes & ( ~even_bits ) & ( ~follow_escape );
239 UInt32 seq_start_on_even_bits = 0_u32;
241 auto r = odd_seq_start + backslashes;
242 seq_start_on_even_bits = 0x0000'FFFF_u32 & r;
246 UInt32 invert_mask = seq_start_on_even_bits << 1U;
248 return ( even_bits ^ invert_mask ) & follow_escape;
251 DAW_ATTRIBUTE_FLATTEN
static inline UInt32 prefix_xor( sse42_exec_tag
const &,
253 __m128i
const all_ones = _mm_set1_epi8(
'\xFF' );
254 __m128i
const result = _mm_clmulepi64_si128(
255 _mm_set_epi32( 0, 0, 0,
static_cast<std::int32_t
>( bitmask ) ), all_ones,
257 return to_uint32( _mm_cvtsi128_si32( result ) );
260 template<
bool is_unchecked_input>
261 static inline char const *
262 mem_skip_until_end_of_string(
simd_exec_tag const &tag,
char const *first,
263 char const *
const last ) {
264 UInt32 prev_escapes = 0_u32;
265 while( last - first >= 16 ) {
266 auto const val0 = uload16_char_data( tag, first );
267 UInt32
const backslashes = mem_find_eq<'\\'>( tag, val0 );
268 UInt32
const escaped =
269 find_escaped_branchless( tag, prev_escapes, backslashes );
270 UInt32
const quotes = mem_find_eq<
'"'>( tag, val0 ) & ( ~escaped );
271 UInt32
const in_string = prefix_xor( tag, quotes );
272 if( in_string != 0 ) {
273 first += find_lsb_set( tag, in_string );
278 if constexpr( is_unchecked_input ) {
279 while( *first !=
'"' ) {
280 while( not key_table<'"', '\\'>[*first] ) {
283 if( *first ==
'"' ) {
291 not key_table<'"', '\\'>[*first] ) {
294 if( first >= last ) {
297 if( *first ==
'"' ) {
303 return ( is_unchecked_input or
DAW_JSON_LIKELY( first < last ) ) ? first
307 template<
bool is_unchecked_input>
308 static inline char const *
309 mem_skip_until_end_of_string(
simd_exec_tag const &tag,
char const *first,
310 char const *
const last,
311 std::ptrdiff_t &first_escape ) {
312 char const *
const first_first = first;
313 UInt32 prev_escapes = 0_u32;
314 while( last - first >= 16 ) {
315 auto const val0 = uload16_char_data( tag, first );
316 UInt32
const backslashes = mem_find_eq<'\\'>( tag, val0 );
317 if( ( backslashes != 0 ) & ( first_escape < 0 ) ) {
318 first_escape = find_lsb_set( tag, backslashes );
320 UInt32
const escaped =
321 find_escaped_branchless( tag, prev_escapes, backslashes );
322 UInt32
const quotes = mem_find_eq<
'"'>( tag, val0 ) & ( ~escaped );
323 UInt32
const in_string = prefix_xor( tag, quotes );
324 if( in_string != 0 ) {
325 first += find_lsb_set( tag, in_string );
330 if constexpr( is_unchecked_input ) {
331 while( *first !=
'"' ) {
332 while( not key_table<'"', '\\'>[*first] ) {
335 if( *first ==
'"' ) {
338 if( first_escape < 0 ) {
339 first_escape = first_first - first;
346 not key_table<'"', '\\'>[*first] ) {
349 if( first >= last ) {
352 if( *first ==
'"' ) {
355 if( first_escape < 0 ) {
356 first_escape = first_first - first;
361 return ( is_unchecked_input or
DAW_JSON_LIKELY( first < last ) ) ? first
366 template<
bool is_unchecked_input,
char... keys>
367 DAW_ATTRIBUTE_FLATTEN
static inline char const *
368 mem_move_to_next_of( runtime_exec_tag
const &,
char const *first,
371 if(
sizeof...( keys ) == 1 ) {
372 char const key[]{ keys... };
373 char const *ptr =
reinterpret_cast<char const *
>( std::memchr(
374 first, key[0],
static_cast<std::size_t
>( last - first ) ) );
375 if( ptr ==
nullptr ) {
380 constexpr
auto eq = [](
char l,
char r ) {
return l == r; };
381 while( is_unchecked_input or first < last ) {
382 char const c = *first;
383 if( ( eq( c, keys ) | ... ) ) {
392 template<
bool is_unchecked_input,
typename ExecTag,
393 std::enable_if_t<std::is_base_of_v<runtime_exec_tag, ExecTag>,
394 std::nullptr_t> =
nullptr>
395 DAW_ATTRIBUTE_FLATTEN
static inline char const *
396 mem_skip_string( ExecTag
const &tag,
char const *first,
397 char const *
const last ) {
398 return mem_move_to_next_of<is_unchecked_input,
'"',
'\\'>( tag, first,
402 template<
bool is_unchecked_input,
typename ExecTag,
403 std::enable_if_t<std::is_base_of_v<runtime_exec_tag, ExecTag>,
404 std::nullptr_t> =
nullptr>
405 DAW_ATTRIBUTE_FLATTEN
static inline char const *
406 mem_skip_until_end_of_string( ExecTag
const &tag,
char const *first,
407 char const *
const last ) {
408 if constexpr( not is_unchecked_input ) {
412 mem_move_to_next_of<is_unchecked_input,
'\\',
'"'>( tag, first, last );
413 while( is_unchecked_input or first < last ) {
418 if constexpr( is_unchecked_input ) {
421 first +=
static_cast<int>(
static_cast<bool>( last - first ) );
427 mem_move_to_next_of<is_unchecked_input,
'\\',
'"'>( tag, first, last );
432 template<
bool is_unchecked_input>
433 DAW_ATTRIBUTE_FLATTEN
static inline char const *
434 mem_skip_until_end_of_string( runtime_exec_tag
const &tag,
char const *first,
435 char const *
const last,
436 std::ptrdiff_t &first_escape ) {
437 char const *
const first_first = first;
438 if constexpr( not is_unchecked_input ) {
442 mem_move_to_next_of<is_unchecked_input,
'\\',
'"'>( tag, first, last );
443 while( is_unchecked_input or first < last ) {
448 if( first_escape < 0 ) {
449 first_escape = first_first - first;
451 if constexpr( is_unchecked_input ) {
454 first +=
static_cast<int>(
static_cast<bool>( last - first ) );
460 mem_move_to_next_of<is_unchecked_input,
'\\',
'"'>( tag, first, last );