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 86849 40b1a7a5e6309a941ad41bd1986cdde93c9f91cc
parent 86848 e50a68c31b0000230a353abbb34d7be6f4322d1b
child 86850 5095046dc23cc052fc855cf9b862b3b17b93b208
push id805
push userakeybl@mozilla.com
push dateWed, 01 Feb 2012 18:17:35 +0000
treeherdermozilla-aurora@6fb3bf232436 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswaldo, sgimeno
bugs720695
milestone12.0a1
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)