From 1210743cad827155f4e2d4da9adbb8c1569a93a6 Mon Sep 17 00:00:00 2001
From: akr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>
Date: Sun, 7 Jul 2013 15:21:26 +0000
Subject: * bignum.c (bary_mul_karatsuba): Unreachable code removed.  Remove  
 several branches.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@41826 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
---
 ChangeLog                     |  5 +++++
 bignum.c                      | 20 ++++++--------------
 test/-ext-/bignum/test_mul.rb | 43 +++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 54 insertions(+), 14 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 2d83c9aeb1..2df68499a1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+Sun Jul  7 23:56:32 2013  Tanaka Akira  <akr@fsij.org>
+
+	* bignum.c (bary_mul_karatsuba): Unreachable code removed.  Remove
+	  several branches.
+
 Sun Jul  7 22:59:06 2013  Tanaka Akira  <akr@fsij.org>
 
 	* internal.h (rb_big_mul_normal): Declared.
diff --git a/bignum.c b/bignum.c
index 31d35b2d78..4c1c5f74a1 100644
--- a/bignum.c
+++ b/bignum.c
@@ -1593,8 +1593,8 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds,
     size_t n;
     int sub_p, borrow, carry1, carry2, carry3;
 
-    int odd_x = 0;
     int odd_y = 0;
+    int odd_xy = 0;
 
     BDIGIT *xds0, *xds1, *yds0, *yds1, *zds0, *zds1, *zds2, *zds3;
 
@@ -1606,7 +1606,7 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds,
         odd_y = 1;
         yl--;
         if (yl < xl) {
-            odd_x = 1;
+            odd_xy = 1;
             xl--;
         }
     }
@@ -1706,15 +1706,10 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds,
     if (carry2)
         bary_add_one(zds2, zl-2*n);
 
-    if (borrow && carry1)
-        borrow = carry1 = 0;
-    if (borrow && carry3)
-        borrow = carry3 = 0;
-
-    if (borrow)
+    if (carry1 + carry3 - borrow < 0)
         bary_sub_one(zds3, zl-3*n);
-    else if (carry1 || carry3) {
-        BDIGIT c = carry1 + carry3;
+    else if (carry1 + carry3 - borrow > 0) {
+        BDIGIT c = carry1 + carry3 - borrow;
         bary_add(zds3, zl-3*n, zds3, zl-3*n, &c, 1);
     }
 
@@ -1729,13 +1724,10 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zl, BDIGIT *xds, size_t xl, BDIGIT *yds,
     }
     */
 
-    if (odd_x && odd_y) {
+    if (odd_xy) {
         bary_muladd_1xN(zds+yl, zl-yl, yds[yl], xds, xl);
         bary_muladd_1xN(zds+xl, zl-xl, xds[xl], yds, yl+1);
     }
-    else if (odd_x) {
-        bary_muladd_1xN(zds+xl, zl-xl, xds[xl], yds, yl);
-    }
     else if (odd_y) {
         bary_muladd_1xN(zds+yl, zl-yl, yds[yl], xds, xl);
     }
diff --git a/test/-ext-/bignum/test_mul.rb b/test/-ext-/bignum/test_mul.rb
index ad3b38febd..539b9cf138 100644
--- a/test/-ext-/bignum/test_mul.rb
+++ b/test/-ext-/bignum/test_mul.rb
@@ -6,6 +6,7 @@ class TestBignum < Test::Unit::TestCase
 
     SIZEOF_BDIGITS = Bignum::SIZEOF_BDIGITS
     BITSPERDIG = Bignum::BITSPERDIG
+    BDIGMAX = (1 << BITSPERDIG) - 1
 
     def test_mul_normal
       x = (1 << BITSPERDIG) | 1
@@ -49,5 +50,47 @@ class TestBignum < Test::Unit::TestCase
       assert_equal(z, x.big_mul_karatsuba(y))
     end
 
+    def test_mul_karatsuba_odd_y
+      x = (1 << BITSPERDIG) | 1
+      y = (1 << (2*BITSPERDIG)) | 1
+      assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
+    end
+
+    def test_mul_karatsuba_odd_xy
+      x = (1 << (2*BITSPERDIG)) | 1
+      y = (1 << (2*BITSPERDIG)) | 1
+      assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
+    end
+
+    def test_mul_karatsuba_x1_gt_x0
+      x = (2 << BITSPERDIG) | 1
+      y = (1 << BITSPERDIG) | 2
+      assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
+    end
+
+    def test_mul_karatsuba_y1_gt_y0
+      x = (1 << BITSPERDIG) | 2
+      y = (2 << BITSPERDIG) | 1
+      assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
+    end
+
+    def test_mul_karatsuba_x1_gt_x0_and_y1_gt_y0
+      x = (2 << BITSPERDIG) | 1
+      y = (2 << BITSPERDIG) | 1
+      assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
+    end
+
+    def test_mul_karatsuba_carry2
+      x = (1 << BITSPERDIG) | BDIGMAX
+      y = (1 << BITSPERDIG) | BDIGMAX
+      assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
+    end
+
+    def test_mul_karatsuba_borrow
+      x = (BDIGMAX << BITSPERDIG) | 1
+      y = (BDIGMAX << BITSPERDIG) | 1
+      assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
+    end
+
   end
 end
-- 
cgit v1.2.3