Bug 720695 - Fix uint32 overflow and INT32_MIN corner cases in CompareLexicographicInt32 (r=waldo,sgimeno)
authorLuke Wagner <luke@mozilla.com>
Wed, 25 Jan 2012 08:54:28 -0800
changeset 85624 40b1a7a5e6309a941ad41bd1986cdde93c9f91cc
parent 85623 e50a68c31b0000230a353abbb34d7be6f4322d1b
child 85625 5095046dc23cc052fc855cf9b862b3b17b93b208
push id21940
push userjdrew@mozilla.com
push dateSun, 29 Jan 2012 02:43:03 +0000
treeherdermozilla-central@ec666b4c8d84 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswaldo, sgimeno
bugs720695
milestone12.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 720695 - Fix uint32 overflow and INT32_MIN corner cases in CompareLexicographicInt32 (r=waldo,sgimeno)
js/src/jit-test/tests/basic/testBug720695.js
js/src/jsarray.cpp
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/testBug720695.js
@@ -0,0 +1,16 @@
+var v = [ -0x80000003, -0x80000002, -0x80000001, -0x80000000, -0x7fffffff, -0x7ffffffe, -0x7ffffffd,
+          -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
+          10, 11, 20, 21, 100, 101, 110, 111, 500,
+           0x7ffffffd,  0x7ffffffe,  0x7fffffff,  0x80000000,  0x80000001,  0x80000002,  0x80000003];
+
+function strcmp(x, y) {
+    return Number(String(x) > String(y))
+}
+
+for (var i = 0; i < v.length; ++i) {
+    for (var j = 0; j < v.length; ++j) {
+            var builtin = String([v[i], v[j]].sort());
+            var manual =  String([v[i], v[j]].sort(strcmp));
+            assertEq(builtin, manual);
+    }
+}
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -1968,32 +1968,45 @@ CompareStringValues(JSContext *cx, const
     int32_t result;
     if (!CompareStrings(cx, astr, bstr, &result))
         return false;
 
     *lessOrEqualp = (result <= 0);
     return true;
 }
 
-static int32_t const powersOf10Int32[] = {
+static uint32_t const powersOf10[] = {
     1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000
 };
 
-static inline int
-NumDigitsBase10(int32_t n)
+static inline unsigned
+NumDigitsBase10(uint32_t n)
 {
     /*
      * This is just floor_log10(n) + 1
      * Algorithm taken from
      * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
      */
-    int32_t log2, t;
+    uint32_t log2, t;
     JS_CEILING_LOG2(log2, n);
     t = log2 * 1233 >> 12;
-    return t - (n < powersOf10Int32[t]) + 1;
+    return t - (n < powersOf10[t]) + 1;
+}
+
+static JS_ALWAYS_INLINE uint32_t
+NegateNegativeInt32(int32_t i)
+{
+    /*
+     * We cannot simply return '-i' because this is undefined for INT32_MIN.
+     * 2s complement does actually give us what we want, however.  That is,
+     * ~0x80000000 + 1 = 0x80000000 which is correct when interpreted as a
+     * uint32_t. To avoid undefined behavior, we write out 2s complement
+     * explicitly and rely on the peephole optimizer to generate 'neg'.
+     */
+    return ~uint32_t(i) + 1;
 }
 
 inline bool
 CompareLexicographicInt32(JSContext *cx, const Value &a, const Value &b, bool *lessOrEqualp)
 {
     int32_t aint = a.toInt32();
     int32_t bint = b.toInt32();
 
@@ -2005,40 +2018,40 @@ CompareLexicographicInt32(JSContext *cx,
      * handling ...
      */
     if (aint == bint) {
         *lessOrEqualp = true;
     } else if ((aint < 0) && (bint >= 0)) {
         *lessOrEqualp = true;
     } else if ((aint >= 0) && (bint < 0)) {
         *lessOrEqualp = false;
-    } else if (bint == INT32_MIN) { /* a is negative too --> a <= b */
-        *lessOrEqualp = true;
-    } else if (aint == INT32_MIN) { /* b is negative too but not INT32_MIN --> a > b */
-        *lessOrEqualp = false;
     } else {
-        if (aint < 0) { /* b is also negative */
-            aint = -aint;
-            bint = -bint;
+        uint32_t auint, buint;
+        if (aint >= 0) {
+            auint = aint;
+            buint = bint;
+        } else {
+            auint = NegateNegativeInt32(aint);
+            buint = NegateNegativeInt32(bint);
         }
 
         /*
          *  ... get number of digits of both integers.
          * If they have the same number of digits --> arithmetic comparison.
          * If digits_a > digits_b: a < b*10e(digits_a - digits_b).
          * If digits_b > digits_a: a*10e(digits_b - digits_a) <= b.
          */
-        int digitsa = NumDigitsBase10(aint);
-        int digitsb = NumDigitsBase10(bint);
+        unsigned digitsa = NumDigitsBase10(auint);
+        unsigned digitsb = NumDigitsBase10(buint);
         if (digitsa == digitsb)
-            *lessOrEqualp = (aint <= bint);
+            *lessOrEqualp = (auint <= buint);
         else if (digitsa > digitsb)
-            *lessOrEqualp = (aint < bint*powersOf10Int32[digitsa - digitsb]);
+            *lessOrEqualp = (uint64_t(auint) < uint64_t(buint) * powersOf10[digitsa - digitsb]);
         else /* if (digitsb > digitsa) */
-            *lessOrEqualp = (aint*powersOf10Int32[digitsb - digitsa] <= bint);
+            *lessOrEqualp = (uint64_t(auint) * powersOf10[digitsb - digitsa] <= uint64_t(buint));
     }
 
     return true;
 }
 
 inline bool
 CompareSubStringValues(JSContext *cx, const jschar *s1, size_t l1,
                        const jschar *s2, size_t l2, bool *lessOrEqualp)