SWAR: test for special bytes in the reduced form

The usual test for a zero byte, (x - ones) & ~x & high, needs `& ~x` only
to keep bytes from 0x80 out. The tests for quotes, backslashes and control
characters in string_scan.hpp and the serializer also flag every byte from
0x80 with `v & high`, so the `& ~x` terms can be dropped. Clang finds this
reduction itself; GCC does not and emits 24 instead of 16 instructions.

The masks are the same for 1.3 billion random words and for every pair of
adjacent byte values. With GCC 15 on x86-64: accept() -2 to -4 %,
sax_parse() -2 %, dump() -3 %. Clang is unchanged.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>

include/nlohmann/detail/input/string_scan.hpp

@@ -58,11 +58,10 @@ inline std::uint64_t swar_string_special(std::uint64_t v) noexcept
     constexpr std::uint64_t high = 0x8080808080808080ull;
     const std::uint64_t q = v ^ 0x2222222222222222ull; // '"'  (0x22)
     const std::uint64_t b = v ^ 0x5C5C5C5C5C5C5C5Cull; // '\\' (0x5C)
-    const std::uint64_t has_quote     = (q - ones) & ~q & high;
+    // The usual test for a zero byte is (x - ones) & ~x & high. The `& ~x`
-    const std::uint64_t has_backslash = (b - ones) & ~b & high;
+    // only removes bytes from 0x80, and `v & high` flags those anyway, so it
-    const std::uint64_t has_control   = (v - 0x2020202020202020ull) & ~v & high; // < 0x20
+    // can be dropped. Clang finds this reduction itself; GCC does not.
-    const std::uint64_t has_non_ascii = v & high;                                // >= 0x80
+    return ((q - ones) | (b - ones) | (v - 0x2020202020202020ull) | v) & high;
-    return has_quote | has_backslash | has_control | has_non_ascii;
 }
 
 // return the index of the first is_string_special() byte in [data, data+n), or
@@ -143,11 +142,8 @@ inline std::size_t find_ascii_copyable_run(const unsigned char* data, std::size_
         const std::uint64_t q = v ^ 0x2222222222222222ull; // '"'  (0x22)
         const std::uint64_t b = v ^ 0x5C5C5C5C5C5C5C5Cull; // '\\' (0x5C)
         const std::uint64_t d = v ^ 0x7F7F7F7F7F7F7F7Full; // DEL  (0x7F)
-        const std::uint64_t stop = ((q - ones) & ~q & high)   // == '"'
+        // (see swar_string_special(): the bytes from 0x80 are stops anyway)
-                                   | ((b - ones) & ~b & high)  // == '\\'
+        const std::uint64_t stop = ((q - ones) | (b - ones) | (d - ones) | (v - 0x2020202020202020ull) | v) & high;
-                                   | ((d - ones) & ~d & high)  // == 0x7F
-                                   | ((v - 0x2020202020202020ull) & ~v & high) // < 0x20
-                                   | (v & high);               // >= 0x80
         if (stop != 0)
         {
             // the lowest flagged byte is the first one to stop at (see

include/nlohmann/detail/output/serializer.hpp

@@ -724,10 +724,8 @@ class serializer
         constexpr std::uint64_t ones = 0x0101010101010101ull;
         const std::uint64_t q = v ^ 0x2222222222222222ull; // '"'
         const std::uint64_t b = v ^ 0x5C5C5C5C5C5C5C5Cull; // '\\'
-        return (((q - ones) & ~q) | ((b - ones) & ~b)         // == '"', == '\\'
+        // (see swar_string_special(): the bytes from 0x80 are flagged anyway)
-                | ((v - 0x2020202020202020ull) & ~v)          // < 0x20
+        return ((q - ones) | (b - ones) | (v - 0x2020202020202020ull) | v | (v + ones)) & 0x8080808080808080ull;
-                | v | (v + ones))                             // >= 0x7F
-               & 0x8080808080808080ull;
     }
 
     template<typename WordType>

single_include/nlohmann/json.hpp

@@ -12537,11 +12537,10 @@ inline std::uint64_t swar_string_special(std::uint64_t v) noexcept
     constexpr std::uint64_t high = 0x8080808080808080ull;
     const std::uint64_t q = v ^ 0x2222222222222222ull; // '"'  (0x22)
     const std::uint64_t b = v ^ 0x5C5C5C5C5C5C5C5Cull; // '\\' (0x5C)
-    const std::uint64_t has_quote     = (q - ones) & ~q & high;
+    // The usual test for a zero byte is (x - ones) & ~x & high. The `& ~x`
-    const std::uint64_t has_backslash = (b - ones) & ~b & high;
+    // only removes bytes from 0x80, and `v & high` flags those anyway, so it
-    const std::uint64_t has_control   = (v - 0x2020202020202020ull) & ~v & high; // < 0x20
+    // can be dropped. Clang finds this reduction itself; GCC does not.
-    const std::uint64_t has_non_ascii = v & high;                                // >= 0x80
+    return ((q - ones) | (b - ones) | (v - 0x2020202020202020ull) | v) & high;
-    return has_quote | has_backslash | has_control | has_non_ascii;
 }
 
 // return the index of the first is_string_special() byte in [data, data+n), or
@@ -12622,11 +12621,8 @@ inline std::size_t find_ascii_copyable_run(const unsigned char* data, std::size_
         const std::uint64_t q = v ^ 0x2222222222222222ull; // '"'  (0x22)
         const std::uint64_t b = v ^ 0x5C5C5C5C5C5C5C5Cull; // '\\' (0x5C)
         const std::uint64_t d = v ^ 0x7F7F7F7F7F7F7F7Full; // DEL  (0x7F)
-        const std::uint64_t stop = ((q - ones) & ~q & high)   // == '"'
+        // (see swar_string_special(): the bytes from 0x80 are stops anyway)
-                                   | ((b - ones) & ~b & high)  // == '\\'
+        const std::uint64_t stop = ((q - ones) | (b - ones) | (d - ones) | (v - 0x2020202020202020ull) | v) & high;
-                                   | ((d - ones) & ~d & high)  // == 0x7F
-                                   | ((v - 0x2020202020202020ull) & ~v & high) // < 0x20
-                                   | (v & high);               // >= 0x80
         if (stop != 0)
         {
             // the lowest flagged byte is the first one to stop at (see
@@ -37015,10 +37011,8 @@ class serializer
         constexpr std::uint64_t ones = 0x0101010101010101ull;
         const std::uint64_t q = v ^ 0x2222222222222222ull; // '"'
         const std::uint64_t b = v ^ 0x5C5C5C5C5C5C5C5Cull; // '\\'
-        return (((q - ones) & ~q) | ((b - ones) & ~b)         // == '"', == '\\'
+        // (see swar_string_special(): the bytes from 0x80 are flagged anyway)
-                | ((v - 0x2020202020202020ull) & ~v)          // < 0x20
+        return ((q - ones) | (b - ones) | (v - 0x2020202020202020ull) | v | (v + ones)) & 0x8080808080808080ull;
-                | v | (v + ones))                             // >= 0x7F
-               & 0x8080808080808080ull;
     }
 
     template<typename WordType>