Fixed detection of unsigned add overflow

simdjson · piotrrzysko · Sep 23, 2023 · Sep 23, 2023 · Sep 23, 2023 · c33d2fad4f8503c94c3c4397161062275bd335cf
commit c33d2fad4f8503c94c3c4397161062275bd335cf
diff --git a/src/main/java/org/simdjson/JsonStringScanner.java b/src/main/java/org/simdjson/JsonStringScanner.java
@@ -1,7 +1,6 @@
 package org.simdjson;
 
 import jdk.incubator.vector.ByteVector;
-import jdk.incubator.vector.VectorSpecies;
 
 class JsonStringScanner {
 
@@ -59,7 +58,10 @@ private long findEscaped(long backslash) {
         long oddSequenceStarts = backslash & ODD_BITS_MASK & ~followsEscape;
 
         long sequencesStartingOnEvenBits = oddSequenceStarts + backslash;
-        prevEscaped = ((oddSequenceStarts ^ sequencesStartingOnEvenBits) & (backslash ^ sequencesStartingOnEvenBits)) >>> 63;
+        // Here, we check if the unsigned addition above caused an overflow. If that's the case, we store 1 in prevEscaped.
+        // The formula used to detect overflow was taken from 'Hacker's Delight, Second Edition' by Henry S. Warren, Jr.,
+        // Chapter 2-13.
+        prevEscaped = ((oddSequenceStarts >>> 1) + (backslash >>> 1) + ((oddSequenceStarts & backslash) & 1)) >>> 63;
 
         long invertMask = sequencesStartingOnEvenBits << 1;
         return (EVEN_BITS_MASK ^ invertMask) & followsEscape;

diff --git a/src/test/java/org/simdjson/BenchmarkCorrectnessTest.java b/src/test/java/org/simdjson/BenchmarkCorrectnessTest.java
@@ -5,14 +5,14 @@
 import org.junit.jupiter.params.provider.CsvSource;
 
 import java.io.IOException;
-import java.io.InputStream;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Set;
 
 import static org.assertj.core.api.Assertions.assertThat;
-import static org.simdjson.StringUtils.padWithSpaces;
-import static org.simdjson.StringUtils.toUtf8;
+import static org.simdjson.TestUtils.loadTestFile;
+import static org.simdjson.TestUtils.padWithSpaces;
+import static org.simdjson.TestUtils.toUtf8;
 
 public class BenchmarkCorrectnessTest {
 
@@ -21,7 +21,7 @@ public void countUniqueTwitterUsersWithDefaultProfile() throws IOException {
         // given
         SimdJsonParser parser = new SimdJsonParser();
         Set<String> defaultUsers = new HashSet<>();
-        byte[] json = loadTwitterJson();
+        byte[] json = loadTestFile("/twitter.json");
 
         // when
         JsonValue simdJsonValue = parser.parse(json, json.length);
@@ -55,10 +55,4 @@ public void numberParserTest(String input, Double expected) {
         // then
         assertThat(tape.getDouble(0)).isEqualTo(expected);
     }
-
-    private static byte[] loadTwitterJson() throws IOException {
-        try (InputStream is = BenchmarkCorrectnessTest.class.getResourceAsStream("/twitter.json")) {
-            return is.readAllBytes();
-        } 
-    }
 }
diff --git a/src/test/java/org/simdjson/CharactersClassifierTest.java b/src/test/java/org/simdjson/CharactersClassifierTest.java
@@ -4,7 +4,7 @@
 
 import static java.nio.charset.StandardCharsets.UTF_8;
 import static org.assertj.core.api.Assertions.assertThat;
-import static org.simdjson.StringUtils.chunk;
+import static org.simdjson.TestUtils.chunk;
 
 public class CharactersClassifierTest {
 

diff --git a/src/test/java/org/simdjson/JsonStringScannerTest.java b/src/test/java/org/simdjson/JsonStringScannerTest.java
@@ -5,8 +5,8 @@
 import org.junit.jupiter.params.provider.ValueSource;
 
 import static org.assertj.core.api.Assertions.assertThat;
-import static org.simdjson.StringUtils.chunk;
-import static org.simdjson.StringUtils.padWithSpaces;
+import static org.simdjson.TestUtils.chunk;
+import static org.simdjson.TestUtils.padWithSpaces;
 
 public class JsonStringScannerTest {
 

diff --git a/src/test/java/org/simdjson/NumberParsingTest.java b/src/test/java/org/simdjson/NumberParsingTest.java
@@ -17,7 +17,7 @@
 import static org.assertj.core.api.Assertions.assertThat;
 import static org.junit.jupiter.api.Assertions.assertThrows;
 import static org.simdjson.JsonValueAssert.assertThat;
-import static org.simdjson.StringUtils.toUtf8;
+import static org.simdjson.TestUtils.toUtf8;
 
 public class NumberParsingTest {
 

diff --git a/src/test/java/org/simdjson/ObjectParsingTest.java b/src/test/java/org/simdjson/ObjectParsingTest.java
@@ -7,7 +7,7 @@
 
 import static org.assertj.core.api.Assertions.assertThat;
 import static org.simdjson.JsonValueAssert.assertThat;
-import static org.simdjson.StringUtils.toUtf8;
+import static org.simdjson.TestUtils.toUtf8;
 
 public class ObjectParsingTest {
 

diff --git a/src/test/java/org/simdjson/SimdJsonParserTest.java b/src/test/java/org/simdjson/SimdJsonParserTest.java
@@ -4,13 +4,15 @@
 import org.junit.jupiter.params.ParameterizedTest;
 import org.junit.jupiter.params.provider.ValueSource;
 
+import java.io.IOException;
 import java.util.Iterator;
 
 import static org.assertj.core.api.Assertions.assertThat;
 import static org.assertj.core.api.Assertions.fail;
 import static org.junit.jupiter.api.Assertions.assertThrows;
 import static org.simdjson.JsonValueAssert.assertThat;
-import static org.simdjson.StringUtils.toUtf8;
+import static org.simdjson.TestUtils.loadTestFile;
+import static org.simdjson.TestUtils.toUtf8;
 
 public class SimdJsonParserTest {
 
@@ -291,4 +293,31 @@ public void testLargeArraySize() {
         assertThat(jsonValue.isArray()).isTrue();
         assertThat(jsonValue.getSize()).isEqualTo(0xFFFFFF);
     }
+
+    @Test
+    public void issue26DeepBench() throws IOException {
+        // given
+        SimdJsonParser parser = new SimdJsonParser();
+        byte[] json = loadTestFile("/deep_bench.json");
+
+        // when
+        JsonValue jsonValue = parser.parse(json, json.length);
+
+        // then
+        assertThat(jsonValue.isObject()).isTrue();
+    }
+
+    @ParameterizedTest
+    @ValueSource(strings = {"/wide_bench.json", "/deep_bench.json"})
+    public void issue26(String file) throws IOException {
+        // given
+        SimdJsonParser parser = new SimdJsonParser();
+        byte[] json = loadTestFile(file);
+
+        // when
+        JsonValue jsonValue = parser.parse(json, json.length);
+
+        // then
+        assertThat(jsonValue.isObject()).isTrue();
+    }
 }
diff --git a/src/test/java/org/simdjson/StringParsingTest.java b/src/test/java/org/simdjson/StringParsingTest.java
@@ -15,7 +15,7 @@
 import static org.assertj.core.api.Assertions.assertThat;
 import static org.junit.jupiter.api.Assertions.assertThrows;
 import static org.simdjson.JsonValueAssert.assertThat;
-import static org.simdjson.StringUtils.toUtf8;
+import static org.simdjson.TestUtils.toUtf8;
 
 public class StringParsingTest {
 

diff --git a/src/test/java/org/simdjson/StringUtils.java → src/test/java/org/simdjson/TestUtils.java b/src/test/java/org/simdjson/StringUtils.java → src/test/java/org/simdjson/TestUtils.java
@@ -2,11 +2,13 @@
 
 import jdk.incubator.vector.ByteVector;
 
+import java.io.IOException;
+import java.io.InputStream;
 import java.util.Arrays;
 
 import static java.nio.charset.StandardCharsets.UTF_8;
 
-class StringUtils {
+class TestUtils {
 
     static String padWithSpaces(String str) {
         byte[] strBytes = toUtf8(str);
@@ -23,4 +25,10 @@ static ByteVector chunk(String str, int n) {
     static byte[] toUtf8(String str) {
         return str.getBytes(UTF_8);
     }
+
+    static byte[] loadTestFile(String name) throws IOException {
+        try (InputStream is = TestUtils.class.getResourceAsStream(name)) {
+            return is.readAllBytes();
+        }
+    }
 }