Simplify atom parsing

jkeiser · jkeiser · commit 1aaad223c00a · 2020-03-13T19:00:08.000-07:00
diff --git a/Makefile b/Makefile
@@ -58,7 +58,7 @@ endif # ifeq ($(SANITIZE),1)
 endif # ifeq ($(MEMSANITIZE),1)
 
 # Headers and sources
-SRCHEADERS_GENERIC=src/generic/numberparsing.h src/generic/stage1_find_marks.h src/generic/stage2_build_tape.h src/generic/stringparsing.h src/generic/stage2_streaming_build_tape.h src/generic/utf8_fastvalidate_algorithm.h src/generic/utf8_lookup_algorithm.h src/generic/utf8_lookup2_algorithm.h src/generic/utf8_range_algorithm.h src/generic/utf8_zwegner_algorithm.h
+SRCHEADERS_GENERIC=src/generic/atomparsing.h src/generic/numberparsing.h src/generic/stage1_find_marks.h src/generic/stage2_build_tape.h src/generic/stringparsing.h src/generic/stage2_streaming_build_tape.h src/generic/utf8_fastvalidate_algorithm.h src/generic/utf8_lookup_algorithm.h src/generic/utf8_lookup2_algorithm.h src/generic/utf8_range_algorithm.h src/generic/utf8_zwegner_algorithm.h
 SRCHEADERS_ARM64=      src/arm64/bitmanipulation.h    src/arm64/bitmask.h    src/arm64/intrinsics.h    src/arm64/numberparsing.h    src/arm64/simd.h    src/arm64/stage1_find_marks.h    src/arm64/stage2_build_tape.h    src/arm64/stringparsing.h
 SRCHEADERS_HASWELL=  src/haswell/bitmanipulation.h  src/haswell/bitmask.h  src/haswell/intrinsics.h  src/haswell/numberparsing.h  src/haswell/simd.h  src/haswell/stage1_find_marks.h  src/haswell/stage2_build_tape.h  src/haswell/stringparsing.h
 SRCHEADERS_WESTMERE=src/westmere/bitmanipulation.h src/westmere/bitmask.h src/westmere/intrinsics.h src/westmere/numberparsing.h src/westmere/simd.h src/westmere/stage1_find_marks.h src/westmere/stage2_build_tape.h src/westmere/stringparsing.h
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
@@ -33,43 +33,45 @@ set(SIMDJSON_SRC_HEADERS
   simdprune_tables.h
   stage1_find_marks.cpp
   stage2_build_tape.cpp
-  arm64/bitmask.h
-  arm64/simd.h
   arm64/bitmanipulation.h
+  arm64/bitmask.h
   arm64/implementation.h
   arm64/intrinsics.h
+  arm64/numberparsing.h
+  arm64/simd.h
   arm64/stage1_find_marks.h
   arm64/stage2_build_tape.h
   arm64/stringparsing.h
-  arm64/numberparsing.h
+  generic/atomparsing.h
+  generic/numberparsing.h
   generic/stage1_find_marks.h
   generic/stage2_build_tape.h
   generic/stage2_streaming_build_tape.h
   generic/stringparsing.h
-  generic/numberparsing.h
   generic/utf8_fastvalidate_algorithm.h
   generic/utf8_lookup_algorithm.h
   generic/utf8_lookup2_algorithm.h
   generic/utf8_range_algorithm.h
   generic/utf8_zwegner_algorithm.h
-  haswell/bitmask.h
   haswell/bitmanipulation.h
+  haswell/bitmask.h
   haswell/implementation.h
   haswell/intrinsics.h
+  haswell/numberparsing.h
   haswell/simd.h
   haswell/stage1_find_marks.h
   haswell/stage2_build_tape.h
   haswell/stringparsing.h
   document_parser_callbacks.h
   westmere/bitmanipulation.h
+  westmere/bitmask.h
   westmere/implementation.h
   westmere/intrinsics.h
-  westmere/bitmask.h
+  westmere/numberparsing.h
   westmere/simd.h
   westmere/stage1_find_marks.h
   westmere/stage2_build_tape.h
   westmere/stringparsing.h
-  westmere/numberparsing.h
 )
 set_source_files_properties(${SIMDJSON_SRC_HEADERS} PROPERTIES HEADER_FILE_ONLY TRUE)
 
diff --git a/src/arm64/stage2_build_tape.h b/src/arm64/stage2_build_tape.h
@@ -11,6 +11,7 @@
 
 namespace simdjson::arm64 {
 
+#include "generic/atomparsing.h"
 #include "generic/stage2_build_tape.h"
 #include "generic/stage2_streaming_build_tape.h"
 
diff --git a/src/generic/atomparsing.h b/src/generic/atomparsing.h
@@ -0,0 +1,49 @@
+namespace atomparsing {
+
+really_inline uint32_t string_to_uint32(const char* str) { return *reinterpret_cast<const uint32_t *>(str); }
+
+WARN_UNUSED
+really_inline bool str4ncmp(const uint8_t *src, const char* atom) {
+  uint32_t srcval; // we want to avoid unaligned 64-bit loads (undefined in C/C++)
+  static_assert(sizeof(uint32_t) <= SIMDJSON_PADDING);
+  std::memcpy(&srcval, src, sizeof(uint32_t));
+  return srcval ^ string_to_uint32(atom);
+}
+
+WARN_UNUSED
+really_inline bool is_valid_true_atom(const uint8_t *src) {
+  return (str4ncmp(src, "true") | is_not_structural_or_whitespace(src[4])) == 0;
+}
+
+WARN_UNUSED
+really_inline bool is_valid_true_atom(const uint8_t *src, size_t len) {
+  if (len > 4) { return is_valid_true_atom(src); }
+  else if (len == 4) { return !str4ncmp(src, "true"); }
+  else { return false; }
+}
+
+WARN_UNUSED
+really_inline bool is_valid_false_atom(const uint8_t *src) {
+  return (str4ncmp(src+1, "alse") | is_not_structural_or_whitespace(src[5])) == 0;
+}
+
+WARN_UNUSED
+really_inline bool is_valid_false_atom(const uint8_t *src, size_t len) {
+  if (len > 5) { return is_valid_false_atom(src); }
+  else if (len == 5) { return !str4ncmp(src+1, "alse"); }
+  else { return false; }
+}
+
+WARN_UNUSED
+really_inline bool is_valid_null_atom(const uint8_t *src) {
+  return (str4ncmp(src, "null") | is_not_structural_or_whitespace(src[4])) == 0;
+}
+
+WARN_UNUSED
+really_inline bool is_valid_null_atom(const uint8_t *src, size_t len) {
+  if (len > 4) { return is_valid_null_atom(src); }
+  else if (len == 4) { return !str4ncmp(src, "null"); }
+  else { return false; }
+}
+
+} // namespace atomparsing
diff --git a/src/generic/stage2_build_tape.h b/src/generic/stage2_build_tape.h
@@ -63,6 +63,9 @@ class structural_iterator {
   really_inline const uint8_t* current() {
     return &buf[idx];
   }
+  really_inline size_t remaining_len() {
+    return len - idx;
+  }
   template<typename F>
   really_inline bool with_space_terminated_copy(const F& f) {
     /**
@@ -172,18 +175,18 @@ struct structural_parser {
     return parse_number(structurals.current(), found_minus);
   }
 
-  WARN_UNUSED really_inline bool parse_atom(const uint8_t *src) {
+  WARN_UNUSED really_inline bool parse_atom() {
     switch (structurals.current_char()) {
       case 't':
-        if (!is_valid_true_atom(src)) { return true; }
+        if (!atomparsing::is_valid_true_atom(structurals.current())) { return true; }
         doc_parser.on_true_atom();
         break;
       case 'f':
-        if (!is_valid_false_atom(src)) { return true; }
+        if (!atomparsing::is_valid_false_atom(structurals.current())) { return true; }
         doc_parser.on_false_atom();
         break;
       case 'n':
-        if (!is_valid_null_atom(src)) { return true; }
+        if (!atomparsing::is_valid_null_atom(structurals.current())) { return true; }
         doc_parser.on_null_atom();
         break;
       default:
@@ -192,8 +195,24 @@ struct structural_parser {
     return false;
   }
 
-  WARN_UNUSED really_inline bool parse_atom() {
-    return parse_atom(structurals.current());
+  WARN_UNUSED really_inline bool parse_single_atom() {
+    switch (structurals.current_char()) {
+      case 't':
+        if (!atomparsing::is_valid_true_atom(structurals.current(), structurals.remaining_len())) { return true; }
+        doc_parser.on_true_atom();
+        break;
+      case 'f':
+        if (!atomparsing::is_valid_false_atom(structurals.current(), structurals.remaining_len())) { return true; }
+        doc_parser.on_false_atom();
+        break;
+      case 'n':
+        if (!atomparsing::is_valid_null_atom(structurals.current(), structurals.remaining_len())) { return true; }
+        doc_parser.on_null_atom();
+        break;
+      default:
+        return true;
+    }
+    return false;
   }
 
   WARN_UNUSED really_inline ret_address parse_value(const unified_machine_addresses &addresses, ret_address continue_state) {
@@ -327,11 +346,7 @@ WARN_UNUSED error_code implementation::stage2(const uint8_t *buf, size_t len, do
     FAIL_IF( parser.parse_string() );
     goto finish;
   case 't': case 'f': case 'n':
-    FAIL_IF(
-      parser.structurals.with_space_terminated_copy([&](auto copy, auto idx) {
-        return parser.parse_atom(&copy[idx]);
-      })
-    );
+    FAIL_IF( parser.parse_single_atom() );
     goto finish;
   case '0': case '1': case '2': case '3': case '4':
   case '5': case '6': case '7': case '8': case '9':
diff --git a/src/generic/stage2_streaming_build_tape.h b/src/generic/stage2_streaming_build_tape.h
@@ -58,11 +58,7 @@ WARN_UNUSED error_code implementation::stage2(const uint8_t *buf, size_t len, do
     FAIL_IF( parser.parse_string() );
     goto finish;
   case 't': case 'f': case 'n':
-    FAIL_IF(
-      parser.structurals.with_space_terminated_copy([&](auto copy, auto idx) {
-        return parser.parse_atom(&copy[idx]);
-      })
-    );
+    FAIL_IF( parser.parse_single_atom() );
     goto finish;
   case '0': case '1': case '2': case '3': case '4':
   case '5': case '6': case '7': case '8': case '9':
diff --git a/src/haswell/stage2_build_tape.h b/src/haswell/stage2_build_tape.h
@@ -12,6 +12,7 @@
 TARGET_HASWELL
 namespace simdjson::haswell {
 
+#include "generic/atomparsing.h"
 #include "generic/stage2_build_tape.h"
 #include "generic/stage2_streaming_build_tape.h"
 
diff --git a/src/stage2_build_tape.cpp b/src/stage2_build_tape.cpp
@@ -6,52 +6,6 @@
 
 using namespace simdjson;
 
-WARN_UNUSED
-really_inline bool is_valid_true_atom(const uint8_t *loc) {
-  uint32_t tv = *reinterpret_cast<const uint32_t *>("true");
-  uint32_t error = 0;
-  uint32_t
-      locval; // we want to avoid unaligned 64-bit loads (undefined in C/C++)
-  // this can read up to 3 bytes beyond the buffer size, but we require
-  // SIMDJSON_PADDING of padding
-  static_assert(sizeof(uint32_t) <= SIMDJSON_PADDING);
-  std::memcpy(&locval, loc, sizeof(uint32_t));
-  error = locval ^ tv;
-  error |= is_not_structural_or_whitespace(loc[4]);
-  return error == 0;
-}
-
-WARN_UNUSED
-really_inline bool is_valid_false_atom(const uint8_t *loc) {
-  // assume that loc starts with "f"
-  uint32_t fv = *reinterpret_cast<const uint32_t *>("alse");
-  uint32_t error = 0;
-  uint32_t
-      locval; // we want to avoid unaligned 32-bit loads (undefined in C/C++)
-  // this can read up to 4 bytes beyond the buffer size, but we require
-  // SIMDJSON_PADDING of padding
-  static_assert(sizeof(uint32_t) <= SIMDJSON_PADDING);
-  std::memcpy(&locval, loc + 1, sizeof(uint32_t));
-  error = locval ^ fv;
-  error |= is_not_structural_or_whitespace(loc[5]);
-  return error == 0;
-}
-
-WARN_UNUSED
-really_inline bool is_valid_null_atom(const uint8_t *loc) {
-  uint32_t nv = *reinterpret_cast<const uint32_t *>("null");
-  uint32_t error = 0;
-  uint32_t
-      locval; // we want to avoid unaligned 32-bit loads (undefined in C/C++)
-  // this can read up to 2 bytes beyond the buffer size, but we require
-  // SIMDJSON_PADDING of padding
-  static_assert(sizeof(uint32_t) - 1 <= SIMDJSON_PADDING);
-  std::memcpy(&locval, loc, sizeof(uint32_t));
-  error = locval ^ nv;
-  error |= is_not_structural_or_whitespace(loc[4]);
-  return error == 0;
-}
-
 #ifdef JSON_TEST_STRINGS
 void found_string(const uint8_t *buf, const uint8_t *parsed_begin,
                   const uint8_t *parsed_end);
diff --git a/src/westmere/stage2_build_tape.h b/src/westmere/stage2_build_tape.h
@@ -12,6 +12,7 @@
 TARGET_WESTMERE
 namespace simdjson::westmere {
 
+#include "generic/atomparsing.h"
 #include "generic/stage2_build_tape.h"
 #include "generic/stage2_streaming_build_tape.h"
 
