From c44da115063bfea7ef8b2afd1c9d52737e2b7f70 Mon Sep 17 00:00:00 2001
From: Niels Möller <nisse@lysator.liu.se>
Date: Thu, 8 Dec 2016 09:48:50 +0000
Subject: factor: fix infinite loop in gcd2_odd

* src/factor.c (gcd2_odd): Fix the case a1 == 0, a0 == 0.
* NEWS: Mention the bug fix.
Fixes http://bugs.gnu.org/25135
---
 NEWS                 |  6 ++++++
 src/factor.c         | 10 ++++++++--
 tests/misc/factor.pl |  5 +++++
 3 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/NEWS b/NEWS
index 9899aff8d..179c19b4d 100644
--- a/NEWS
+++ b/NEWS
@@ -2,6 +2,12 @@ GNU coreutils NEWS                                    -*- outline -*-
 
 * Noteworthy changes in release ?.? (????-??-??) [?]
 
+** Bug fixes
+
+  factor no longer goes into an infinite loop for certain numbers like
+  158909489063877810457 and 222087527029934481871.
+  [bug introduced in coreutils-8.20]
+
 
 * Noteworthy changes in release 8.26 (2016-11-30) [stable]
 
diff --git a/src/factor.c b/src/factor.c
index d271de907..115a635f9 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -480,10 +480,16 @@ gcd_odd (uintmax_t a, uintmax_t b)
 static uintmax_t
 gcd2_odd (uintmax_t *r1, uintmax_t a1, uintmax_t a0, uintmax_t b1, uintmax_t b0)
 {
+  assert (b0 & 1);
+
+  if ( (a0 | a1) == 0)
+    {
+      *r1 = b1;
+      return b0;
+    }
+
   while ((a0 & 1) == 0)
     rsh2 (a1, a0, a1, a0, 1);
-  while ((b0 & 1) == 0)
-    rsh2 (b1, b0, b1, b0, 1);
 
   for (;;)
     {
diff --git a/tests/misc/factor.pl b/tests/misc/factor.pl
index 4c2975366..e37df9d61 100755
--- a/tests/misc/factor.pl
+++ b/tests/misc/factor.pl
@@ -73,6 +73,11 @@ my @Tests =
      ['bug-2012-c', '6635692801', {OUT => '57601 115201'}],
      ['bug-2012-d', '17709149503', {OUT => '94099 188197'}],
      ['bug-2012-e', '17754345703', {OUT => '94219 188437'}],
+     # Infinite loop bugs in v8.20 to 8.26 inclusive
+     ['bug-2016-a', '158909489063877810457',
+      {OUT => '3401347 3861211 12099721'}],
+     ['bug-2016-b', '222087527029934481871',
+      {OUT => '15601 26449 111427 4830277'}],
     );
 
 # If we have GMP support, append tests to exercise it.
-- 
cgit v1.2.3-54-g00ecf