From f678de6f0edfe2ccbafc453c2a1dfcbcd6b6ea47 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Wed, 25 Sep 2024 17:50:09 -0700
Subject: [PATCH] factor: tweak gcd2_odd performance

* src/factor.c (gcd2_odd): Use stdc_trailing_zeros here too.
---
 src/factor.c | 27 ++++++++++++++++++---------
 1 file changed, 18 insertions(+), 9 deletions(-)

diff --git a/src/factor.c b/src/factor.c
index 13fb92f8d..081bb0d57 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -441,9 +441,12 @@ gcd2_odd (uintmax_t *r1, uintmax_t a1, uintmax_t a0, uintmax_t b1, uintmax_t b0)
       *r1 = b1;
       return b0;
     }
-
-  while ((a0 & 1) == 0)
-    rsh2 (a1, a0, a1, a0, 1);
+  if (!a0)
+    a0 = a1, a1 = 0;
+  assume (a0);
+  int ctz = stdc_trailing_zeros (a0);
+  if (ctz)
+    rsh2 (a1, a0, a1, a0, ctz);
 
   for (;;)
     {
@@ -456,16 +459,22 @@ gcd2_odd (uintmax_t *r1, uintmax_t a1, uintmax_t a0, uintmax_t b1, uintmax_t b0)
       if (gt2 (a1, a0, b1, b0))
         {
           sub_ddmmss (a1, a0, a1, a0, b1, b0);
-          do
-            rsh2 (a1, a0, a1, a0, 1);
-          while ((a0 & 1) == 0);
+          if (!a0)
+            a0 = a1, a1 = 0;
+          assume (a0);
+          ctz = stdc_trailing_zeros (a0);
+          if (ctz)
+            rsh2 (a1, a0, a1, a0, ctz);
         }
       else if (gt2 (b1, b0, a1, a0))
         {
           sub_ddmmss (b1, b0, b1, b0, a1, a0);
-          do
-            rsh2 (b1, b0, b1, b0, 1);
-          while ((b0 & 1) == 0);
+          if (!b0)
+            b0 = b1, b1 = 0;
+          assume (b0);
+          ctz = stdc_trailing_zeros (b0);
+          if (ctz)
+            rsh2 (b1, b0, b1, b0, ctz);
         }
       else
         break;
-- 
2.11.4.GIT