BSON reader: find C-string terminators 8 bytes at a time, skip array element names

get_bson_cstr_bulk() searched for the 0x00 byte one byte at a time. It now uses
find_zero_byte() (string_scan.hpp), which tests 8 bytes per step with the
SWAR zero-byte test the lexer's scanners use.

The names of an array's elements ("0", "1", ...) are not passed to the SAX
parser, but were still copied into the key string and checked against the
error handler. They are now skipped without a copy, except with
error_handler_t::strict, which still rejects ill-formed UTF-8 in them with
the same error and position as before.

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

include/nlohmann/detail/input/binary_reader.hpp

@@ -465,15 +465,17 @@ class binary_reader
             }
 
             const std::size_t element_type_parse_position = chars_read;
+            // an array's elements are named "0", "1", ... in the wire format,
+            // and those names are not passed on: they are skipped unless
+            // error_handler_t::strict must reject ill-formed UTF-8 in them
+            const bool is_object = container_stack.back().is_object;
             key.clear();
-            if (JSON_HEDLEY_UNLIKELY(!get_bson_cstr(key)))
+            if (JSON_HEDLEY_UNLIKELY(!get_bson_cstr(key, is_object || error_handler == error_handler_t::strict)))
             {
                 return false;
             }
 
-            // an array's elements are named "0", "1", ... in the wire format,
-            // and those names are not passed on
-            if (container_stack.back().is_object && !sax->key(key))
+            if (is_object && !sax->key(key))
             {
                 return false;
             }
@@ -489,14 +491,18 @@ class binary_reader
     @brief Parses a C-style string from the BSON input.
     @param[in,out] result  A reference to the string variable where the read
                             string is to be stored.
+    @param[in] store  whether the characters are needed; if not (the names of
+                      an array's elements), they are skipped and @a result may
+                      be left unchanged, and they are not checked against
+                      @ref error_handler
     @return `true` if the \\x00-byte indicating the end of the string was
              encountered before the EOF; false` indicates an unexpected EOF.
     */
-    bool get_bson_cstr(string_t& result)
+    bool get_bson_cstr(string_t& result, const bool store = true)
     {
-        if (get_bson_cstr_bulk(result, std::integral_constant<bool, bulk_scan> {}))
+        if (get_bson_cstr_bulk(result, store, std::integral_constant<bool, bulk_scan> {}))
         {
-            return check_string_utf8(result, "key");
+            return !store || check_string_utf8(result, "key");
         }
 
         auto out = std::back_inserter(result);
@@ -509,7 +515,7 @@ class binary_reader
             }
             if (current == 0x00)
             {
-                return check_string_utf8(result, "key");
+                return !store || check_string_utf8(result, "key");
             }
             *out++ = static_cast<typename string_t::value_type>(current);
         }
@@ -519,10 +525,11 @@ class binary_reader
     @brief read a C-style string from contiguous input in one step
 
     @param[in,out] result  the string to append to
+    @param[in] store  whether to append the characters to @a result
     @return whether the string was read; if the input has no \\x00-byte, nothing
             is read, and @ref get_bson_cstr reports the end of the input
     */
-    bool get_bson_cstr_bulk(string_t& result, std::true_type /*bulk*/)
+    bool get_bson_cstr_bulk(string_t& result, const bool store, std::true_type /*bulk*/)
     {
         const std::size_t remaining = ia.bulk_remaining();
         if (remaining == 0)
@@ -530,18 +537,15 @@ class binary_reader
             return false;
         }
         const auto* const data = reinterpret_cast<const unsigned char*>(ia.bulk_data());
-        // a plain loop rather than std::memchr: most keys are short (array
-        // indices are keys, too), and the call would cost more than it saves
-        std::size_t length = 0;
-        while (length < remaining && data[length] != 0x00)
-        {
-            ++length;
-        }
+        const std::size_t length = find_zero_byte(data, remaining);
         if (length == remaining)
         {
             return false;
         }
-        result.append(reinterpret_cast<const typename string_t::value_type*>(data), length);
+        if (store)
+        {
+            result.append(reinterpret_cast<const typename string_t::value_type*>(data), length);
+        }
         // consume the string and its \x00-byte, as the byte-wise path does
         ia.bulk_skip(length + 1);
         chars_read += length + 1;
@@ -550,7 +554,7 @@ class binary_reader
     }
 
     /// input that is not contiguous: C-style strings are read byte by byte
-    bool get_bson_cstr_bulk(string_t& /*result*/, std::false_type /*bulk*/) const noexcept
+    bool get_bson_cstr_bulk(string_t& /*result*/, const bool /*store*/, std::false_type /*bulk*/) const noexcept
     {
         return false;
     }

include/nlohmann/detail/input/string_scan.hpp

@@ -90,6 +90,34 @@ JSON_HEDLEY_ALWAYS_INLINE std::size_t find_string_special(const unsigned char* d
     return n;
 }
 
+// return the index of the first 0x00 byte in [data, data+n), or n if there is
+// none; scans 8 bytes at a time (BSON's C-style strings)
+JSON_HEDLEY_ALWAYS_INLINE std::size_t find_zero_byte(const unsigned char* data, std::size_t n) noexcept
+{
+    constexpr std::uint64_t ones = 0x0101010101010101ull;
+    constexpr std::uint64_t high = 0x8080808080808080ull;
+    std::size_t i = 0;
+    for (; i + 8 <= n; i += 8)
+    {
+        const std::uint64_t v = read_eight_bytes(data + i);
+        const std::uint64_t zero = (v - ones) & ~v & high;
+        if (zero != 0)
+        {
+            // the lowest flagged byte is the first zero byte (see
+            // find_string_special())
+            return i + (static_cast<std::size_t>(count_trailing_zeros(zero)) / 8);
+        }
+    }
+    for (; i < n; ++i)
+    {
+        if (data[i] == 0x00)
+        {
+            return i;
+        }
+    }
+    return n;
+}
+
 // classify a byte as one the serializer must NOT copy verbatim when
 // ensure_ascii is requested: the closing quote, an escape, a control character
 // (< 0x20), DEL (0x7F), or any non-ASCII byte (>= 0x80). Everything else -

single_include/nlohmann/json.hpp

@@ -12458,6 +12458,34 @@ JSON_HEDLEY_ALWAYS_INLINE std::size_t find_string_special(const unsigned char* d
     return n;
 }
 
+// return the index of the first 0x00 byte in [data, data+n), or n if there is
+// none; scans 8 bytes at a time (BSON's C-style strings)
+JSON_HEDLEY_ALWAYS_INLINE std::size_t find_zero_byte(const unsigned char* data, std::size_t n) noexcept
+{
+    constexpr std::uint64_t ones = 0x0101010101010101ull;
+    constexpr std::uint64_t high = 0x8080808080808080ull;
+    std::size_t i = 0;
+    for (; i + 8 <= n; i += 8)
+    {
+        const std::uint64_t v = read_eight_bytes(data + i);
+        const std::uint64_t zero = (v - ones) & ~v & high;
+        if (zero != 0)
+        {
+            // the lowest flagged byte is the first zero byte (see
+            // find_string_special())
+            return i + (static_cast<std::size_t>(count_trailing_zeros(zero)) / 8);
+        }
+    }
+    for (; i < n; ++i)
+    {
+        if (data[i] == 0x00)
+        {
+            return i;
+        }
+    }
+    return n;
+}
+
 // classify a byte as one the serializer must NOT copy verbatim when
 // ensure_ascii is requested: the closing quote, an escape, a control character
 // (< 0x20), DEL (0x7F), or any non-ASCII byte (>= 0x80). Everything else -
@@ -18241,15 +18269,17 @@ class binary_reader
             }
 
             const std::size_t element_type_parse_position = chars_read;
+            // an array's elements are named "0", "1", ... in the wire format,
+            // and those names are not passed on: they are skipped unless
+            // error_handler_t::strict must reject ill-formed UTF-8 in them
+            const bool is_object = container_stack.back().is_object;
             key.clear();
-            if (JSON_HEDLEY_UNLIKELY(!get_bson_cstr(key)))
+            if (JSON_HEDLEY_UNLIKELY(!get_bson_cstr(key, is_object || error_handler == error_handler_t::strict)))
             {
                 return false;
             }
 
-            // an array's elements are named "0", "1", ... in the wire format,
-            // and those names are not passed on
-            if (container_stack.back().is_object && !sax->key(key))
+            if (is_object && !sax->key(key))
             {
                 return false;
             }
@@ -18265,14 +18295,18 @@ class binary_reader
     @brief Parses a C-style string from the BSON input.
     @param[in,out] result  A reference to the string variable where the read
                             string is to be stored.
+    @param[in] store  whether the characters are needed; if not (the names of
+                      an array's elements), they are skipped and @a result may
+                      be left unchanged, and they are not checked against
+                      @ref error_handler
     @return `true` if the \\x00-byte indicating the end of the string was
              encountered before the EOF; false` indicates an unexpected EOF.
     */
-    bool get_bson_cstr(string_t& result)
+    bool get_bson_cstr(string_t& result, const bool store = true)
     {
-        if (get_bson_cstr_bulk(result, std::integral_constant<bool, bulk_scan> {}))
+        if (get_bson_cstr_bulk(result, store, std::integral_constant<bool, bulk_scan> {}))
         {
-            return check_string_utf8(result, "key");
+            return !store || check_string_utf8(result, "key");
         }
 
         auto out = std::back_inserter(result);
@@ -18285,7 +18319,7 @@ class binary_reader
             }
             if (current == 0x00)
             {
-                return check_string_utf8(result, "key");
+                return !store || check_string_utf8(result, "key");
             }
             *out++ = static_cast<typename string_t::value_type>(current);
         }
@@ -18295,10 +18329,11 @@ class binary_reader
     @brief read a C-style string from contiguous input in one step
 
     @param[in,out] result  the string to append to
+    @param[in] store  whether to append the characters to @a result
     @return whether the string was read; if the input has no \\x00-byte, nothing
             is read, and @ref get_bson_cstr reports the end of the input
     */
-    bool get_bson_cstr_bulk(string_t& result, std::true_type /*bulk*/)
+    bool get_bson_cstr_bulk(string_t& result, const bool store, std::true_type /*bulk*/)
     {
         const std::size_t remaining = ia.bulk_remaining();
         if (remaining == 0)
@@ -18306,18 +18341,15 @@ class binary_reader
             return false;
         }
         const auto* const data = reinterpret_cast<const unsigned char*>(ia.bulk_data());
-        // a plain loop rather than std::memchr: most keys are short (array
-        // indices are keys, too), and the call would cost more than it saves
-        std::size_t length = 0;
-        while (length < remaining && data[length] != 0x00)
-        {
-            ++length;
-        }
+        const std::size_t length = find_zero_byte(data, remaining);
         if (length == remaining)
         {
             return false;
         }
-        result.append(reinterpret_cast<const typename string_t::value_type*>(data), length);
+        if (store)
+        {
+            result.append(reinterpret_cast<const typename string_t::value_type*>(data), length);
+        }
         // consume the string and its \x00-byte, as the byte-wise path does
         ia.bulk_skip(length + 1);
         chars_read += length + 1;
@@ -18326,7 +18358,7 @@ class binary_reader
     }
 
     /// input that is not contiguous: C-style strings are read byte by byte
-    bool get_bson_cstr_bulk(string_t& /*result*/, std::false_type /*bulk*/) const noexcept
+    bool get_bson_cstr_bulk(string_t& /*result*/, const bool /*store*/, std::false_type /*bulk*/) const noexcept
     {
         return false;
     }

tests/src/unit-bson.cpp

@@ -1164,7 +1164,13 @@ TEST_CASE("BSON keys from contiguous and stream input")
     // contiguous input reads a key up to its \x00-byte in one step, a stream
     // reads it byte by byte; both must give the same value or error for the
     // complete document and for every truncation of it
-    const json j = {{"", true}, {"k", {1, 2, 3}}, {std::string(40, 'x'), {{"nested key", "value"}}}};
+    json j = {{"", true}, {"k", {1, 2, 3}}, {std::string(40, 'x'), {{"nested key", "value"}}}};
+    // keys and array element names ("0" to "11") that end at every position of
+    // an 8-byte word, which contiguous input scans at a time
+    for (std::size_t length = 1; length <= 17; ++length)
+    {
+        j[std::string(length, static_cast<char>('a' + length))] = json::array({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, {11}});
+    }
     const std::vector<std::uint8_t> bson = json::to_bson(j);
     CHECK(json::from_bson(bson) == j);
 
@@ -1194,6 +1200,33 @@ TEST_CASE("BSON keys from contiguous and stream input")
         CHECK(from_vector == from_stream);
     }
 }
+
+TEST_CASE("BSON array element names")
+{
+    // an array's element names are not part of the value, so they are not
+    // passed on; error_handler_t::strict still rejects ill-formed UTF-8 in them
+    const std::vector<std::uint8_t> bson =
+    {
+        0x1D, 0x00, 0x00, 0x00, // size (little endian)
+        0x04, 'a', 0x00,        // entry: array "a"
+        0x15, 0x00, 0x00, 0x00, // size (little endian)
+        0x08, 0xFF, 0x00, 0x01, // entry: boolean named "\xFF", true
+        0x08, '1', '2', '3', '4', '5', '6', '7', '8', '9', 0x00, 0x00, // entry: boolean named "123456789", false
+        0x00,                   // end of the array
+        0x00                    // end of the document
+    };
+    const json expected = {{"a", {true, false}}};
+
+    CHECK(json::from_bson(bson) == expected);
+    CHECK(json::from_bson(bson, true, true, json::error_handler_t::replace) == expected);
+    CHECK(json::from_bson(bson, true, true, json::error_handler_t::ignore) == expected);
+
+    json _;
+    CHECK_THROWS_WITH_AS(_ = json::from_bson(bson, true, true, json::error_handler_t::strict), "[json.exception.parse_error.113] parse error at byte 14: syntax error while parsing BSON key: invalid string: ill-formed UTF-8 byte", json::parse_error&);
+
+    std::istringstream stream(std::string(bson.begin(), bson.end()));
+    CHECK(json::from_bson(stream) == expected);
+}
 #endif
 
 TEST_CASE("Negative size of binary value")