json/detail/sse2.hpp

0001 //
0002 // Copyright (c) 2019 Peter Dimov (pdimov at gmail dot com),
0003 //                    Vinnie Falco (vinnie.falco@gmail.com)
0004 // Copyright (c) 2020 Krystian Stasiowski (sdkrystian@gmail.com)
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See accompanying
0007 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // Official repository: https://github.com/boostorg/json
0010 //
0011
0012 #ifndef BOOST_JSON_DETAIL_SSE2_HPP
0013 #define BOOST_JSON_DETAIL_SSE2_HPP
0014
0015 #include <boost/json/detail/config.hpp>
0016 #include <boost/json/detail/utf8.hpp>
0017 #include <cstddef>
0018 #include <cstring>
0019 #ifdef BOOST_JSON_USE_SSE2
0020 # include <emmintrin.h>
0021 # include <xmmintrin.h>
0022 # ifdef _MSC_VER
0023 #  include <intrin.h>
0024 # endif
0025 #endif
0026
0027 namespace boost {
0028 namespace json {
0029 namespace detail {
0030
0031 #ifdef BOOST_JSON_USE_SSE2
0032
0033 template<bool AllowBadUTF8>
0034 inline
0035 const char*
0036 count_valid(
0037     char const* p,
0038     const char* end) noexcept
0039 {
0040     __m128i const q1 = _mm_set1_epi8( '\x22' ); // '"'
0041     __m128i const q2 = _mm_set1_epi8( '\\' ); // '\\'
0042     __m128i const q3 = _mm_set1_epi8( 0x1F );
0043
0044     while(end - p >= 16)
0045     {
0046         __m128i v1 = _mm_loadu_si128( (__m128i const*)p );
0047         __m128i v2 = _mm_cmpeq_epi8( v1, q1 ); // quote
0048         __m128i v3 = _mm_cmpeq_epi8( v1, q2 ); // backslash
0049         __m128i v4 = _mm_or_si128( v2, v3 ); // combine quotes and backslash
0050         __m128i v5 = _mm_min_epu8( v1, q3 );
0051         __m128i v6 = _mm_cmpeq_epi8( v5, v1 ); // controls
0052         __m128i v7 = _mm_or_si128( v4, v6 ); // combine with control
0053
0054         int w = _mm_movemask_epi8( v7 );
0055
0056         if( w != 0 )
0057         {
0058             int m;
0059 #if defined(__GNUC__) || defined(__clang__)
0060             m = __builtin_ffs( w ) - 1;
0061 #else
0062             unsigned long index;
0063             _BitScanForward( &index, w );
0064             m = index;
0065 #endif
0066             return p + m;
0067         }
0068
0069         p += 16;
0070     }
0071
0072     while(p != end)
0073     {
0074         const unsigned char c = *p;
0075         if(c == '\x22' || c == '\\' || c < 0x20)
0076             break;
0077         ++p;
0078     }
0079
0080     return p;
0081 }
0082
0083 template<>
0084 inline
0085 const char*
0086 count_valid<false>(
0087     char const* p,
0088     const char* end) noexcept
0089 {
0090     __m128i const q1 = _mm_set1_epi8( '\x22' ); // '"'
0091     __m128i const q2 = _mm_set1_epi8( '\\' );
0092     __m128i const q3 = _mm_set1_epi8( 0x20 );
0093
0094     while(end - p >= 16)
0095     {
0096         __m128i v1 = _mm_loadu_si128( (__m128i const*)p );
0097
0098         __m128i v2 = _mm_cmpeq_epi8( v1, q1 );
0099         __m128i v3 = _mm_cmpeq_epi8( v1, q2 );
0100         __m128i v4 = _mm_cmplt_epi8( v1, q3 );
0101
0102         __m128i v5 = _mm_or_si128( v2, v3 );
0103         __m128i v6 = _mm_or_si128( v5, v4 );
0104
0105         int w = _mm_movemask_epi8( v6 );
0106
0107         if( w != 0 )
0108         {
0109             int m;
0110 #if defined(__GNUC__) || defined(__clang__)
0111             m = __builtin_ffs( w ) - 1;
0112 #else
0113             unsigned long index;
0114             _BitScanForward( &index, w );
0115             m = index;
0116 #endif
0117             p += m;
0118             break;
0119         }
0120
0121         p += 16;
0122     }
0123
0124     while(p != end)
0125     {
0126         const unsigned char c = *p;
0127         if(c == '\x22' || c == '\\' || c < 0x20)
0128             break;
0129         if(c < 0x80)
0130         {
0131             ++p;
0132             continue;
0133         }
0134         // validate utf-8
0135         uint16_t first = classify_utf8(c);
0136         uint8_t len = first & 0xFF;
0137         if(BOOST_JSON_UNLIKELY(end - p < len))
0138             break;
0139         if(BOOST_JSON_UNLIKELY(! is_valid_utf8(p, first)))
0140             break;
0141         p += len;
0142     }
0143
0144     return p;
0145 }
0146
0147 #else
0148
0149 template<bool AllowBadUTF8>
0150 char const*
0151 count_valid(
0152     char const* p,
0153     char const* end) noexcept
0154 {
0155     while(p != end)
0156     {
0157         const unsigned char c = *p;
0158         if(c == '\x22' || c == '\\' || c < 0x20)
0159             break;
0160         ++p;
0161     }
0162
0163     return p;
0164 }
0165
0166 template<>
0167 inline
0168 char const*
0169 count_valid<false>(
0170     char const* p,
0171     char const* end) noexcept
0172 {
0173     while(p != end)
0174     {
0175         const unsigned char c = *p;
0176         if(c == '\x22' || c == '\\' || c < 0x20)
0177             break;
0178         if(c < 0x80)
0179         {
0180             ++p;
0181             continue;
0182         }
0183         // validate utf-8
0184         uint16_t first = classify_utf8(c);
0185         uint8_t len = first & 0xFF;
0186         if(BOOST_JSON_UNLIKELY(end - p < len))
0187             break;
0188         if(BOOST_JSON_UNLIKELY(! is_valid_utf8(p, first)))
0189             break;
0190         p += len;
0191     }
0192
0193     return p;
0194 }
0195
0196 #endif
0197
0198 // KRYSTIAN NOTE: does not stop to validate
0199 // count_unescaped
0200
0201 #ifdef BOOST_JSON_USE_SSE2
0202
0203 inline
0204 size_t
0205 count_unescaped(
0206     char const* s,
0207     size_t n) noexcept
0208 {
0209
0210     __m128i const q1 = _mm_set1_epi8( '\x22' ); // '"'
0211     __m128i const q2 = _mm_set1_epi8( '\\' ); // '\\'
0212     __m128i const q3 = _mm_set1_epi8( 0x1F );
0213
0214     char const * s0 = s;
0215
0216     while( n >= 16 )
0217     {
0218         __m128i v1 = _mm_loadu_si128( (__m128i const*)s );
0219         __m128i v2 = _mm_cmpeq_epi8( v1, q1 ); // quote
0220         __m128i v3 = _mm_cmpeq_epi8( v1, q2 ); // backslash
0221         __m128i v4 = _mm_or_si128( v2, v3 ); // combine quotes and backslash
0222         __m128i v5 = _mm_min_epu8( v1, q3 );
0223         __m128i v6 = _mm_cmpeq_epi8( v5, v1 ); // controls
0224         __m128i v7 = _mm_or_si128( v4, v6 ); // combine with control
0225
0226         int w = _mm_movemask_epi8( v7 );
0227
0228         if( w != 0 )
0229         {
0230             int m;
0231 #if defined(__GNUC__) || defined(__clang__)
0232             m = __builtin_ffs( w ) - 1;
0233 #else
0234             unsigned long index;
0235             _BitScanForward( &index, w );
0236             m = index;
0237 #endif
0238
0239             s += m;
0240             break;
0241         }
0242
0243         s += 16;
0244         n -= 16;
0245     }
0246
0247     return s - s0;
0248 }
0249
0250 #else
0251
0252 inline
0253 std::size_t
0254 count_unescaped(
0255     char const*,
0256     std::size_t) noexcept
0257 {
0258     return 0;
0259 }
0260
0261 #endif
0262
0263 // count_digits
0264
0265 #ifdef BOOST_JSON_USE_SSE2
0266
0267 // assumes p..p+15 are valid
0268 inline int count_digits( char const* p ) noexcept
0269 {
0270     __m128i v1 = _mm_loadu_si128( (__m128i const*)p );
0271     v1 = _mm_add_epi8(v1, _mm_set1_epi8(70));
0272     v1 = _mm_cmplt_epi8(v1, _mm_set1_epi8(118));
0273
0274     int m = _mm_movemask_epi8(v1);
0275
0276     int n;
0277
0278     if( m == 0 )
0279     {
0280         n = 16;
0281     }
0282     else
0283     {
0284 #if defined(__GNUC__) || defined(__clang__)
0285         n = __builtin_ffs( m ) - 1;
0286 #else
0287         unsigned long index;
0288         _BitScanForward( &index, m );
0289         n = static_cast<int>(index);
0290 #endif
0291     }
0292
0293     return n;
0294 }
0295
0296 #else
0297
0298 // assumes p..p+15 are valid
0299 inline int count_digits( char const* p ) noexcept
0300 {
0301     int n = 0;
0302
0303     for( ; n < 16; ++n )
0304     {
0305         unsigned char const d = *p++ - '0';
0306         if(d > 9) break;
0307     }
0308
0309     return n;
0310 }
0311
0312 #endif
0313
0314 // parse_unsigned
0315
0316 inline uint64_t parse_unsigned( uint64_t r, char const * p, std::size_t n ) noexcept
0317 {
0318     while( n >= 4 )
0319     {
0320         // faster on on clang for x86,
0321         // slower on gcc
0322 #ifdef __clang__
0323         r = r * 10 + p[0] - '0';
0324         r = r * 10 + p[1] - '0';
0325         r = r * 10 + p[2] - '0';
0326         r = r * 10 + p[3] - '0';
0327 #else
0328         uint32_t v;
0329         std::memcpy( &v, p, 4 );
0330         endian::native_to_little_inplace(v);
0331
0332         v -= 0x30303030;
0333
0334         unsigned w0 = v & 0xFF;
0335         unsigned w1 = (v >> 8) & 0xFF;
0336         unsigned w2 = (v >> 16) & 0xFF;
0337         unsigned w3 = (v >> 24);
0338
0339         r = (((r * 10 + w0) * 10 + w1) * 10 + w2) * 10 + w3;
0340 #endif
0341         p += 4;
0342         n -= 4;
0343     }
0344
0345     switch( n )
0346     {
0347     case 0:
0348         break;
0349     case 1:
0350         r = r * 10 + p[0] - '0';
0351         break;
0352     case 2:
0353         r = r * 10 + p[0] - '0';
0354         r = r * 10 + p[1] - '0';
0355         break;
0356     case 3:
0357         r = r * 10 + p[0] - '0';
0358         r = r * 10 + p[1] - '0';
0359         r = r * 10 + p[2] - '0';
0360         break;
0361     }
0362     return r;
0363 }
0364
0365 // KRYSTIAN: this function is unused
0366 // count_leading
0367
0368 /*
0369 #ifdef BOOST_JSON_USE_SSE2
0370
0371 // assumes p..p+15
0372 inline std::size_t count_leading( char const * p, char ch ) noexcept
0373 {
0374     __m128i const q1 = _mm_set1_epi8( ch );
0375
0376     __m128i v = _mm_loadu_si128( (__m128i const*)p );
0377
0378     __m128i w = _mm_cmpeq_epi8( v, q1 );
0379
0380     int m = _mm_movemask_epi8( w ) ^ 0xFFFF;
0381
0382     std::size_t n;
0383
0384     if( m == 0 )
0385     {
0386         n = 16;
0387     }
0388     else
0389     {
0390 #if defined(__GNUC__) || defined(__clang__)
0391         n = __builtin_ffs( m ) - 1;
0392 #else
0393         unsigned long index;
0394         _BitScanForward( &index, m );
0395         n = index;
0396 #endif
0397     }
0398
0399     return n;
0400 }
0401
0402 #else
0403
0404 // assumes p..p+15
0405 inline std::size_t count_leading( char const * p, char ch ) noexcept
0406 {
0407     std::size_t n = 0;
0408
0409     for( ; n < 16 && *p == ch; ++p, ++n );
0410
0411     return n;
0412 }
0413
0414 #endif
0415 */
0416
0417 // count_whitespace
0418
0419 #ifdef BOOST_JSON_USE_SSE2
0420
0421 inline const char* count_whitespace( char const* p, const char* end ) noexcept
0422 {
0423     if( p == end )
0424     {
0425         return p;
0426     }
0427
0428     if( static_cast<unsigned char>( *p ) > 0x20 )
0429     {
0430         return p;
0431     }
0432
0433     __m128i const q1 = _mm_set1_epi8( ' ' );
0434     __m128i const q2 = _mm_set1_epi8( '\n' );
0435     __m128i const q3 = _mm_set1_epi8( 4 ); // '\t' | 4 == '\r'
0436     __m128i const q4 = _mm_set1_epi8( '\r' );
0437
0438     while( end - p >= 16 )
0439     {
0440         __m128i v0 = _mm_loadu_si128( (__m128i const*)p );
0441
0442         __m128i w0 = _mm_or_si128(
0443             _mm_cmpeq_epi8( v0, q1 ),
0444             _mm_cmpeq_epi8( v0, q2 ));
0445         __m128i v1 = _mm_or_si128( v0, q3 );
0446         __m128i w1 = _mm_cmpeq_epi8( v1, q4 );
0447         __m128i w2 = _mm_or_si128( w0, w1 );
0448
0449         int m = _mm_movemask_epi8( w2 ) ^ 0xFFFF;
0450
0451         if( m != 0 )
0452         {
0453 #if defined(__GNUC__) || defined(__clang__)
0454             std::size_t c = __builtin_ffs( m ) - 1;
0455 #else
0456             unsigned long index;
0457             _BitScanForward( &index, m );
0458             std::size_t c = index;
0459 #endif
0460
0461             p += c;
0462             return p;
0463         }
0464
0465         p += 16;
0466     }
0467
0468     while( p != end )
0469     {
0470         if( *p != ' ' && *p != '\t' && *p != '\r' && *p != '\n' )
0471         {
0472             return p;
0473         }
0474
0475         ++p;
0476     }
0477
0478     return p;
0479 }
0480
0481 /*
0482
0483 // slightly faster on msvc-14.2, slightly slower on clang-win
0484
0485 inline std::size_t count_whitespace( char const * p, std::size_t n ) noexcept
0486 {
0487     char const * p0 = p;
0488
0489     while( n > 0 )
0490     {
0491         char ch = *p;
0492
0493         if( ch == '\n' || ch == '\r' )
0494         {
0495             ++p;
0496             --n;
0497             continue;
0498         }
0499
0500         if( ch != ' ' && ch != '\t' )
0501         {
0502             break;
0503         }
0504
0505         ++p;
0506         --n;
0507
0508         while( n >= 16 )
0509         {
0510             std::size_t n2 = count_leading( p, ch );
0511
0512             p += n2;
0513             n -= n2;
0514
0515             if( n2 < 16 )
0516             {
0517                 break;
0518             }
0519         }
0520     }
0521
0522     return p - p0;
0523 }
0524 */
0525
0526 #else
0527
0528 inline const char* count_whitespace( char const* p, const char* end ) noexcept
0529 {
0530
0531     for(; p != end; ++p)
0532     {
0533         char const c = *p;
0534         if( c != ' ' && c != '\n' && c != '\r' && c != '\t' ) break;
0535     }
0536
0537     return p;
0538 }
0539
0540 #endif
0541
0542 } // detail
0543 } // namespace json
0544 } // namespace boost
0545
0546 #endif