Repository: ultrajson/ultrajson (language: python)

Issue:
UltraJSON has inconsistent behavior on parsing large integral values.
For some integers that are too large, UltraJSON will raise a ValueError. For others, it will parse, but parse to the wrong value. This happens both for numbers that are too large in the positive direction, and numbers that are too large in the negative direction.

### What did you do?

Encoded an integer that was too big or too small.

### What did you expect to happen?

I expected UltraJSON to raise a ValueError.

### What actually happened?

UltraJSON parsed the integer...into the wrong value.

### What versions are you using?

* OS: Debian 5.7.17-1rodete4 (2020-10-01) x86_64 GNU/Linux
* Python: 3.8.5
* UltraJSON: HEAD as of Nov 9 2020 (commit hash f26f9679f1b9d7fa2d0488e1e7b1256d9391a85f)

Please include **code** that reproduces the issue.

```python3
import ujson
ujson.loads("18446744073709551615")  # Parses fine, max 64-bit value
ujson.loads("18446744073709551616") # Raises a ValueError: Value is too big!
# This value is even bigger:
ujson.loads("33333333303333333333")  # Parses, but parses into the wrong value, 14886589229623781717

# The same thing happens for negative numbers. For example:
ujson.loads("-80888888888888888888")  # Parses to the wrong value, -7101912594050682424
```



Discussion / hints:
This is happening due to incorrect overflow* detection. The decoder parses the input digit by digit. Every time, the previous value is multiplied by ten and the next digit added. After that, there is an attempt to check whether the result is smaller than the previous value. However, overflows can happen without triggering that check.

For example, let's take the input `33333333303333336789` (just changed the last few digits to make it more readable). When parsing the last digit, this has the `prevIntValue = 3333333330333333678`. Upon multiplying by ten, this wraps around to `14886589229623785164`, and the addition of the last digit then results in `...73`. This result is larger than `prevIntValue`, so the error condition is not triggered despite the overflow.

(\* Technically, unsigned ints cannot actually overflow (cause undefined behaviour etc.) in C. I'm using 'overflow' in the looser sense to mean wrapping around.)
Should `Number.MAX_SAFE_INTEGER` be used? See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER
I don't think that matching constraints caused by JavaScript's slightly questionable behaviour of munging integers and floats under the hood would make us very popular - especially given that Python's `json` handles arbitrary sized integers without complaint.
Ok, works for me ;) 



Fix patch:
diff --git a/lib/ultrajsondec.c b/lib/ultrajsondec.c
index 73e8a5db..6c59bf02 100644
--- a/lib/ultrajsondec.c
+++ b/lib/ultrajsondec.c
@@ -92,23 +92,31 @@ static FASTCALL_ATTR JSOBJ FASTCALL_MSVC decode_numeric (struct DecoderState *ds
   int intNeg = 1;
   int hasError = 0;
   JSUINT64 intValue;
-  JSUINT64 prevIntValue;
+  JSUINT64 addIntValue;
   int chr;
   char *offset = ds->start;
 
-  JSUINT64 overflowLimit = LLONG_MAX;
+  JSUINT64 maxIntValue = ULLONG_MAX;
+  JSUINT64 overflowLimit = maxIntValue / 10LLU;
 
-  if (*(offset) == 'I') {
+  if (*(offset) == 'I')
+  {
+    goto DECODE_INF;
+  }
+  else if (*(offset) == 'N')
+  {
+    goto DECODE_NAN;
+  }
+  else if (*(offset) == '-')
+  {
+    offset++;
+    intNeg = -1;
+    if (*(offset) == 'I')
+    {
       goto DECODE_INF;
-  } else if (*(offset) == 'N') {
-      goto DECODE_NAN;
-  } else if (*(offset) == '-') {
-      offset++;
-      intNeg = -1;
-      if (*(offset) == 'I') {
-          goto DECODE_INF;
-      }
-    overflowLimit = LLONG_MIN;
+    }
+    maxIntValue = -(JSUINT64) LLONG_MIN;
+    overflowLimit = maxIntValue / 10LL;
   }
 
   // Scan integer part
@@ -131,19 +139,21 @@ static FASTCALL_ATTR JSOBJ FASTCALL_MSVC decode_numeric (struct DecoderState *ds
       case '8':
       case '9':
       {
-        //PERF: Don't do 64-bit arithmetic here unless we know we have to
-        prevIntValue = intValue;
-        intValue = intValue * 10ULL + (JSLONG) (chr - 48);
-
-        if (intNeg == 1 && prevIntValue > intValue)
+        // check whether multiplication would be out of bounds
+        if (intValue > overflowLimit)
         {
           hasError = 1;
         }
-        else if (intNeg == -1 && intValue > overflowLimit)
+        intValue *= 10ULL;
+        addIntValue = (JSUINT64) (chr - 48);
+
+        // check whether addition would be out of bounds
+        if (maxIntValue - intValue < addIntValue)
         {
           hasError = 1;
         }
 
+        intValue += addIntValue;
         offset ++;
         break;
       }
@@ -163,14 +173,7 @@ static FASTCALL_ATTR JSOBJ FASTCALL_MSVC decode_numeric (struct DecoderState *ds
       {
         if (hasError)
         {
-          if (intNeg == 1)
-          {
-            return SetError(ds, -1, "Value is too big!");
-          }
-          else if (intNeg == -1)
-          {
-            return SetError(ds, -1, overflowLimit == LLONG_MAX ? "Value is too big!" : "Value is too small");
-          }
+          return SetError(ds, -1, intNeg == 1 ? "Value is too big" : "Value is too small");
         }
         goto BREAK_INT_LOOP;
         break;


Test patch:
diff --git a/tests/test_ujson.py b/tests/test_ujson.py
index 9c40b97b..3a6ee50a 100644
--- a/tests/test_ujson.py
+++ b/tests/test_ujson.py
@@ -592,7 +592,10 @@ def test_decode_range_raises(test_input, expected):
         ("[]]", ujson.JSONDecodeError),  # array unmatched bracket fail
         ("18446744073709551616", ujson.JSONDecodeError),  # too big value
         ("-90223372036854775809", ujson.JSONDecodeError),  # too small value
+        ("-23058430092136939529", ujson.JSONDecodeError),  # too small value
+        ("-11529215046068469760", ujson.JSONDecodeError),  # too small value
         ("18446744073709551616", ujson.JSONDecodeError),  # very too big value
+        ("23058430092136939529", ujson.JSONDecodeError),  # too big value
         ("-90223372036854775809", ujson.JSONDecodeError),  # very too small value
         ("{}\n\t a", ujson.JSONDecodeError),  # with trailing non whitespaces
         ("[18446744073709551616]", ujson.JSONDecodeError),  # array with big int