[Boost-commit] svn:boost r82460 - in trunk: boost/multiprecision/cpp_int libs/multiprecision/test

Subject: [Boost-commit] svn:boost r82460 - in trunk: boost/multiprecision/cpp_int libs/multiprecision/test
From: john_at_[hidden]
Date: 2013-01-12 05:51:46

Author: johnmaddock
Date: 2013-01-12 05:51:46 EST (Sat, 12 Jan 2013)
New Revision: 82460
URL: http://svn.boost.org/trac/boost/changeset/82460

Log:
Fix bug that causes division by single limb to fail when the remainder is zero and the least significant limb of the quotient is 1.
Fixes #7878.
Text files modified: 
   trunk/boost/multiprecision/cpp_int/divide.hpp   |     4 +-                                      
   trunk/libs/multiprecision/test/test_cpp_int.cpp |    56 ++++++++++++++++++++++++++++++++++++++++
   2 files changed, 58 insertions(+), 2 deletions(-)

Modified: trunk/boost/multiprecision/cpp_int/divide.hpp
==============================================================================
--- trunk/boost/multiprecision/cpp_int/divide.hpp	(original)
+++ trunk/boost/multiprecision/cpp_int/divide.hpp	2013-01-12 05:51:46 EST (Sat, 12 Jan 2013)
@@ -423,9 +423,9 @@
          }
       }
    }
-   // Termination condition is really just a check that r > y, but with two common
+   // Termination condition is really just a check that r >= y, but with two common
    // short-circuit cases handled first:
-   while(r_order || (pr[r_order] > y));
+   while(r_order || (pr[r_order] >= y));
 
    if(result)
    {

Modified: trunk/libs/multiprecision/test/test_cpp_int.cpp
==============================================================================
--- trunk/libs/multiprecision/test/test_cpp_int.cpp	(original)
+++ trunk/libs/multiprecision/test/test_cpp_int.cpp	2013-01-12 05:51:46 EST (Sat, 12 Jan 2013)
@@ -109,6 +109,24 @@
       BOOST_CHECK_EQUAL((mpz_int(-a)%=b).str(), (test_type(-a1) %= b1).str());
       BOOST_CHECK_EQUAL(mpz_int(a % d).str(), test_type(a1 % d1).str());
       BOOST_CHECK_EQUAL((mpz_int(a)%=d).str(), (test_type(a1) %= d1).str());
+
+      if(!std::numeric_limits<test_type>::is_bounded)
+      {
+         test_type p = a1 * b1;
+         test_type r;
+         divide_qr(p, b1, p, r);
+         BOOST_CHECK_EQUAL(p, a1);
+         BOOST_CHECK_EQUAL(r, test_type(0));
+
+         p = a1 * d1;
+         divide_qr(p, d1, p, r);
+         BOOST_CHECK_EQUAL(p, a1);
+         BOOST_CHECK_EQUAL(r, test_type(0));
+
+         divide_qr(p, test_type(1), p, r);
+         BOOST_CHECK_EQUAL(p, a1);
+         BOOST_CHECK_EQUAL(r, test_type(0));
+      }
    }
 
    void t2()
@@ -335,10 +353,48 @@
       BOOST_CHECK_EQUAL(lsb(a), lsb(a1));
    }
 
+   void test_bug_cases()
+   {
+      if(!std::numeric_limits<test_type>::is_bounded)
+      {
+         // https://svn.boost.org/trac/boost/ticket/7878
+         test_type a("0x1000000000000000000000000000000000000000000000000000000000000000");
+         test_type b = 0xFFFFFFFF;
+         test_type c = a * b + b;  // quotient has 1 in the final place
+         test_type q, r;
+         divide_qr(c, b, q, r);
+         BOOST_CHECK_EQUAL(a + 1, q);
+         BOOST_CHECK_EQUAL(r, 0);
+
+         b = static_cast<test_type>("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
+         c = a * b + b;  // quotient has 1 in the final place
+         divide_qr(c, b, q, r);
+         BOOST_CHECK_EQUAL(a + 1, q);
+         BOOST_CHECK_EQUAL(r, 0);
+         //
+         // Not a bug, but test some other special cases that don't otherwise occur through
+         // random testing:
+         //
+         c = a * b; // quotient has zero in the final place
+         divide_qr(c, b, q, r);
+         BOOST_CHECK_EQUAL(q, a);
+         BOOST_CHECK_EQUAL(r, 0);
+         divide_qr(c, a, q, r);
+         BOOST_CHECK_EQUAL(q, b);
+         BOOST_CHECK_EQUAL(r, 0);
+         ++c;
+         divide_qr(c, b, q, r);
+         BOOST_CHECK_EQUAL(q, a);
+         BOOST_CHECK_EQUAL(r, 1);
+      }
+   }
+
    void test()
    {
       using namespace boost::multiprecision;
 
+      test_bug_cases();
+
       last_error_count = 0;
 
       BOOST_CHECK_EQUAL(Number(), 0);