Fix APInt long division algorithm

[chfast]

Summary

This patch fixes step D4 of Knuth's division algorithm implementation. Negative sign of the step result was not always detected due to incorrect "borrow" handling.

[chfast]

Hi Yaron,

You reviewed my previous fix in the algorithm, so you might be interested.

[yaron.keren]

I'll have a look.

How do you find these bugs? by reviewing the code, fuzzing the inputs, or?

2015-04-22 18:31 GMT+03:00 Paweł Bylica <[e-mail]>:

Hi Yaron,

You reviewed my previous fix in the algorithm, so you might be interested.

REPOSITORY

rL LLVM

http://reviews.llvm.org/D9196

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

[yaron.keren]

unittests/ADT/APIntTest.cpp

307

Please factor this code segment to a helper function, it's the same in divrem_big1, divrem_big2, divrem_big3, divrem_big5 and divrem_big6.

[chfast]

In D9196#160113, @yaron.keren wrote:>

How do you find these bugs? by reviewing the code, fuzzing the inputs, or?

By fuzzy tests of my project that uses a lot of 256 and 512 bit arithmetic.

[chfast]

Unit tests refactored

[yaron.keren]

Ok, this LGTM. Commit the patch?

[chfast]

In D9196#161037, @yaron.keren wrote:

Ok, this LGTM. Commit the patch?

I can handle it myself now. Thanks for the review.

lib/Support/APInt.cpp

do {
     // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
     // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
     // consists of a simple multiplication by a one-place number, combined with
     // a subtraction.
     // The digits (u[j+n]...u[j]) should be kept positive; if the result of
     // this step is actually negative, (u[j+n]...u[j]) should be left as the
     // true value plus b**(n+1), namely as the b's complement of
     // the true value, and a "borrow" to the left should be remembered.
-    bool isNeg = false;
+    int64_t borrow = 0;
     for (unsigned i = 0; i < n; ++i) {
-      uint64_t u_tmp = (uint64_t(u[j+i+1]) << 32) | uint64_t(u[j+i]);
-      uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
-      bool borrow = subtrahend > u_tmp;
-      DEBUG(dbgs() << "KnuthDiv: u_tmp = " << u_tmp
-                   << ", subtrahend = " << subtrahend
-                   << ", borrow = " << borrow << '\n');
-
-      uint64_t result = u_tmp - subtrahend;
-      unsigned k = j + i;
-      u[k++] = (unsigned)result;         // subtraction low word
-      u[k++] = (unsigned)(result >> 32); // subtraction high word
-      while (borrow && k <= m+n) {       // deal with borrow to the left
-        borrow = u[k] == 0;
-        u[k]--;
-        k++;
-      }
-      isNeg |= borrow;
-      DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i] 
-                   << ", u[j+i+1] = " << u[j+i+1] << '\n');
+      uint64_t p = uint64_t(qp) * uint64_t(v[i]);
+      int64_t subres = int64_t(u[j+i]) - borrow - (unsigned)p;
+      u[j+i] = (unsigned)subres;
+      borrow = (p >> 32) - (subres >> 32);
+      DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
+                   << ", borrow = " << borrow << '\n');
     }
+    bool isNeg = u[j+n] < borrow;
+    u[j+n] -= (unsigned)borrow;
+
     DEBUG(dbgs() << "KnuthDiv: after subtraction:");
     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
     DEBUG(dbgs() << '\n');
 
     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
     // negative, go to step D6; otherwise go on to step D7.
     q[j] = (unsigned)qp;
     if (isNeg) {

unittests/ADT/APIntTest.cpp

TEST(APIntTest, i1) {
   EXPECT_EQ(-four, q);
   EXPECT_EQ(one, r);
   APInt::sdivrem(-nine, -two, q, r);
   EXPECT_EQ(four, q);
   EXPECT_EQ(-one, r);
   }
 }
 
-TEST(APIntTest, divrem_big1) {
-  // Tests KnuthDiv rare step D6
-  APInt a{256, "1ffffffffffffffff", 16};
-  APInt b{256, "1ffffffffffffffff", 16};
-  APInt c{256, 0};
+
+// Tests different div/rem varaints using scheme (a * b + c) / a
+void testDiv(APInt a, APInt b, APInt c) {
+  ASSERT_TRUE(a.uge(b)); // Must: a >= b
+  ASSERT_TRUE(a.ugt(c)); // Must: a > c
 
   auto p = a * b + c;
+
   auto q = p.udiv(a);
   auto r = p.urem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
+  EXPECT_EQ(b, q);
+  EXPECT_EQ(c, r);
   APInt::udivrem(p, a, q, r);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = p.udiv(b);
-  r = p.urem(b);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  APInt::udivrem(p, b, q, r);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
+  EXPECT_EQ(b, q);
+  EXPECT_EQ(c, r);
   q = p.sdiv(a);
   r = p.srem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
+  EXPECT_EQ(b, q);
+  EXPECT_EQ(c, r);
   APInt::sdivrem(p, a, q, r);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
+  EXPECT_EQ(b, q);
+  EXPECT_EQ(c, r);
+
+  if (b.ugt(c)) { // Test also symmetric case
+    q = p.udiv(b);
+    r = p.urem(b);
+    EXPECT_EQ(a, q);
+    EXPECT_EQ(c, r);
+    APInt::udivrem(p, b, q, r);
+    EXPECT_EQ(a, q);
+    EXPECT_EQ(c, r);
     q = p.sdiv(b);
     r = p.srem(b);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
+    EXPECT_EQ(a, q);
+    EXPECT_EQ(c, r);
     APInt::sdivrem(p, b, q, r);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
+    EXPECT_EQ(a, q);
+    EXPECT_EQ(c, r);
+  }
+}
+
+TEST(APIntTest, divrem_big1) {
+  // Tests KnuthDiv rare step D6
+  testDiv({256, "1ffffffffffffffff", 16},
+          {256, "1ffffffffffffffff", 16},
+          {256, 0});
 }
 
 TEST(APIntTest, divrem_big2) {
   // Tests KnuthDiv rare step D6
-  APInt a{1024,           "111111ffffffffffffffff"
-                "ffffffffffffffffffffffffffffffff"
-                "fffffffffffffffffffffffffffffccf"
-                "ffffffffffffffffffffffffffffff00", 16};
-  APInt b{1024,                       "112233ceff"
+  testDiv({1024,                       "112233ceff"
                  "cecece000000ffffffffffffffffffff"
                  "ffffffffffffffffffffffffffffffff"
                  "ffffffffffffffffffffffffffffffff"
-                "ffffffffffffffffffffffffffffff33", 16};
-  APInt c{1024, 7919};
-
-  auto p = a * b + c;
-  auto q = p.udiv(a);
-  auto r = p.urem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  APInt::udivrem(p, a, q, r);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = p.udiv(b);
-  r = p.urem(b);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  APInt::udivrem(p, b, q, r);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  q = p.sdiv(a);
-  r = p.srem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  APInt::sdivrem(p, a, q, r);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = p.sdiv(b);
-  r = p.srem(b);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  APInt::sdivrem(p, b, q, r);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
+                 "ffffffffffffffffffffffffffffff33", 16},
+          {1024,           "111111ffffffffffffffff"
+                 "ffffffffffffffffffffffffffffffff"
+                 "fffffffffffffffffffffffffffffccf"
+                 "ffffffffffffffffffffffffffffff00", 16},
+          {1024, 7919});
 }
 
 TEST(APIntTest, divrem_big3) {
   // Tests KnuthDiv case without shift
-  APInt a{256, "ffffffffffffff0000000", 16};
-  APInt b{256, "80000001ffffffffffffffff", 16};
-  APInt c{256, 4219};
-
-  auto p = a * b + c;
-  auto q = p.udiv(a);
-  auto r = p.urem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  APInt::udivrem(p, a, q, r);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = p.udiv(b);
-  r = p.urem(b);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  APInt::udivrem(p, b, q, r);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  q = p.sdiv(a);
-  r = p.srem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  APInt::sdivrem(p, a, q, r);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = p.sdiv(b);
-  r = p.srem(b);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  APInt::sdivrem(p, b, q, r);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
+  testDiv({256, "80000001ffffffffffffffff", 16},
+          {256, "ffffffffffffff0000000", 16},
+          {256, 4219});
 }
 
 TEST(APIntTest, divrem_big4) {
   // Tests heap allocation in divide() enfoced by huge numbers
-  auto a = APInt{4096, 1}.shl(2000);
-  auto b = APInt{4096, 5}.shl(2001);
-  auto c = APInt{4096, 4219*13};
-
-  auto p = a * b + c;
-  auto q = p.udiv(a);
-  auto r = p.urem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = APInt{1024, 0}; // test non-single word APInt conversion in divide()
-  r = APInt{1024, 0};
-  APInt::udivrem(p, a, q, r);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = p.udiv(b);
-  r = p.urem(b);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  q = APInt{1024, 0};
-  r = APInt{1024, 0};
-  APInt::udivrem(p, b, q, r);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  q = p.sdiv(a);
-  r = p.srem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = APInt{1024, 0};
-  r = APInt{1024, 0};
-  APInt::sdivrem(p, a, q, r);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = p.sdiv(b);
-  r = p.srem(b);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  q = APInt{1024, 0};
-  r = APInt{1024, 0};
-  APInt::sdivrem(p, b, q, r);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
+  testDiv(APInt{4096, 5}.shl(2001),
+          APInt{4096, 1}.shl(2000),
+          APInt{4096, 4219*13});
 }
 
 TEST(APIntTest, divrem_big5) {
   // Tests one word divisor case of divide()
-  auto a = APInt{1024, 19}.shl(811);
-  auto b = APInt{1024, 4356013}; // one word
-  auto c = APInt{1024, 1};
+  testDiv(APInt{1024, 19}.shl(811),
+          APInt{1024, 4356013}, // one word
+          APInt{1024, 1});
+}
 
-  auto p = a * b + c;
-  auto q = p.udiv(a);
-  auto r = p.urem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  APInt::udivrem(p, a, q, r);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = p.udiv(b);
-  r = p.urem(b);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  APInt::udivrem(p, b, q, r);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  q = p.sdiv(a);
-  r = p.srem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  APInt::sdivrem(p, a, q, r);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
-  q = p.sdiv(b);
-  r = p.srem(b);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
-  APInt::sdivrem(p, b, q, r);
-  EXPECT_EQ(q, a);
-  EXPECT_EQ(r, c);
+TEST(APIntTest, divrem_big6) {
+  // Tests some rare "borrow" cases in D4 step
+  testDiv(APInt{512, "ffffffffffffffff00000000000000000000000001", 16},
+          APInt{512, "10000000000000001000000000000001", 16},
+          APInt{512, "10000000000000000000000000000000", 16});
 }
 
 TEST(APIntTest, divrem_big7) {
   // Yet another test for KnuthDiv rare step D6.
-  APInt a{224, "800000008000000200000005", 16};
-  APInt b{224, "fffffffd", 16};
-  APInt c{224, "80000000800000010000000f", 16};
-
-  auto p = a * b + c;
-  auto q = p.udiv(a);
-  auto r = p.urem(a);
-  EXPECT_EQ(q, b);
-  EXPECT_EQ(r, c);
+  testDiv({224, "800000008000000200000005", 16},
+          {224, "fffffffd", 16},
+          {224, "80000000800000010000000f", 16});
 }
 
 TEST(APIntTest, fromString) {
   EXPECT_EQ(APInt(32, 0), APInt(32,   "0", 2));
   EXPECT_EQ(APInt(32, 1), APInt(32,   "1", 2));
   EXPECT_EQ(APInt(32, 2), APInt(32,  "10", 2));
   EXPECT_EQ(APInt(32, 3), APInt(32,  "11", 2));
   EXPECT_EQ(APInt(32, 4), APInt(32, "100", 2));