[Gmp-commit] /var/hg/gmp: toom2{_sqr, 2_mul}.c: better handling a special case...

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/02a2ec6e1bce
changeset: 17600:02a2ec6e1bce
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Apr 23 18:12:05 2018 +0200
description:
toom2{_sqr,2_mul}.c: better handling a special case (tx Paul, Raphae"l)

diffstat:

 mpn/generic/toom22_mul.c |  27 +++++++++++++++++++--------
 mpn/generic/toom2_sqr.c  |  22 ++++++++++++++++------
 2 files changed, 35 insertions(+), 14 deletions(-)

diffs (87 lines):

diff -r ca5a00a4037c -r 02a2ec6e1bce mpn/generic/toom22_mul.c
--- a/mpn/generic/toom22_mul.c	Sun Apr 22 21:22:29 2018 +0200
+++ b/mpn/generic/toom22_mul.c	Mon Apr 23 18:12:05 2018 +0200
@@ -7,7 +7,7 @@
    SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES.  IN FACT, IT IS ALMOST
    GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
 
-Copyright 2006-2010, 2012, 2014 Free Software Foundation, Inc.
+Copyright 2006-2010, 2012, 2014, 2018 Free Software Foundation, Inc.
 
 This file is part of the GNU MP Library.
 
@@ -195,16 +195,27 @@
 
   if (vm1_neg)
     cy += mpn_add_n (pp + n, pp + n, vm1, 2 * n);
-  else
+  else {
     cy -= mpn_sub_n (pp + n, pp + n, vm1, 2 * n);
+    if (UNLIKELY (cy + 1 == 0)) { /* cy is negative */
+      /* The total contribution of v0+vinf-vm1 can not be negative. */
+#if WANT_ASSERT
+      /* The borrow in cy stops the propagation of the carry cy2, */
+      ASSERT (cy2 == 1);
+      cy += mpn_add_1 (pp + 2 * n, pp + 2 * n, n, 1);
+      ASSERT (cy == 0);
+#else
+      /* we simply fill the area with zeros. */
+      MPN_FILL (pp + 2 * n, n, 0);
+#endif
+      return;
+    }
+  }
 
-  ASSERT (cy + 1  <= 3);
+  ASSERT (cy  <= 2);
   ASSERT (cy2 <= 2);
 
   MPN_INCR_U (pp + 2 * n, s + t, cy2);
-  if (LIKELY (cy <= 2))
-    /* if s+t==n, cy is zero, but we should not access pp[3*n] at all. */
-    MPN_INCR_U (pp + 3 * n, s + t - n, cy);
-  else
-    MPN_DECR_U (pp + 3 * n, s + t - n, 1);
+  /* if s+t==n, cy is zero, but we should not access pp[3*n] at all. */
+  MPN_INCR_U (pp + 3 * n, s + t - n, cy);
 }
diff -r ca5a00a4037c -r 02a2ec6e1bce mpn/generic/toom2_sqr.c
--- a/mpn/generic/toom2_sqr.c	Sun Apr 22 21:22:29 2018 +0200
+++ b/mpn/generic/toom2_sqr.c	Mon Apr 23 18:12:05 2018 +0200
@@ -6,7 +6,7 @@
    SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES.  IN FACT, IT IS ALMOST
    GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
 
-Copyright 2006-2010, 2012, 2014 Free Software Foundation, Inc.
+Copyright 2006-2010, 2012, 2014, 2018 Free Software Foundation, Inc.
 
 This file is part of the GNU MP Library.
 
@@ -134,12 +134,22 @@
 
   cy -= mpn_sub_n (pp + n, pp + n, vm1, 2 * n);
 
-  ASSERT (cy + 1  <= 3);
+  ASSERT (cy + 1 <= 3);
   ASSERT (cy2 <= 2);
 
-  MPN_INCR_U (pp + 2 * n, s + s, cy2);
-  if (LIKELY (cy <= 2))
+  if (LIKELY (cy <= 2)) {
+    MPN_INCR_U (pp + 2 * n, s + s, cy2);
     MPN_INCR_U (pp + 3 * n, s + s - n, cy);
-  else
-    MPN_DECR_U (pp + 3 * n, s + s - n, 1);
+  } else { /* cy is negative */
+    /* The total contribution of v0+vinf-vm1 can not be negative. */
+#if WANT_ASSERT
+    /* The borrow in cy stops the propagation of the carry cy2, */
+    ASSERT (cy2 == 1);
+    cy += mpn_add_1 (pp + 2 * n, pp + 2 * n, n, 1);
+    ASSERT (cy == 0);
+#else
+    /* we simply fill the area with zeros. */
+    MPN_FILL (pp + 2 * n, n, 0);
+#endif
+  }
 }