Subject: Re: bug#73474: Bug in factor utility of coreutils

From: Paul Eggert <[email-masked]>
Date: Fri, 27 Sep 2024 17:50:51 -0700

On 2024-09-25 13:48, Pádraig Brady wrote:
> 
> Note factor does give the correct result on amd64 at least
> without the asserts:

Yes, as far as I know the existing code works correctly on all practical 
platforms. It's only pedantic/checking platforms, where shifts by 
negative or by too-large result in crashes or diagnostics, where the 
existing code fails.

The bug is easy to fix and the fixdoesn't hurt performance 
significantly, so I installed the attached. Closing the bug report.

While looking into this I got seduced by the prospect of making 'factor' 
a bit better (e.g., eliminate some recursion and fix some buffering 
issues) and installed a bunch of followup patches for 'factor'. Yeah, 
yeah, I should know better....

From 5867465510d023ece420e9921fc1034e3abd6455 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Wed, 25 Sep 2024 15:59:09 -0700
Subject: [PATCH] factor: port to platforms

* src/factor.c (mod2): Work even if cntd <= cnta.  The old version
of the code assumed that shifts by N had unspecified behavior
unless 0 <= N < wordsize.  Although this assumption is portable to
all known practical platforms, the C standard says these shifts
have undefined behavior and some pedantic platforms check this.
* tests/factor/create-test.sh:
* tests/local.mk (factor_tests): New test t37.
---
 src/factor.c                | 15 ++++++++++-----
 tests/factor/create-test.sh |  4 ++++
 tests/local.mk              |  2 +-
 3 files changed, 15 insertions(+), 6 deletions(-)

diff --git a/src/factor.c b/src/factor.c
index 2649e9fc6..f4dd6f6d4 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -317,12 +317,14 @@ static void factor (uintmax_t, uintmax_t, struct factors *);
   } while (0)
 #endif
 
+/* Set (rh,rl) = (ah,al) >> cnt, where 0 < cnt < W_TYPE_SIZE.  */
 #define rsh2(rh, rl, ah, al, cnt)                                       \
   do {                                                                  \
     (rl) = ((ah) << (W_TYPE_SIZE - (cnt))) | ((al) >> (cnt));           \
     (rh) = (ah) >> (cnt);                                               \
   } while (0)
 
+/* Set (rh,rl) = (ah,al) << cnt, where 0 < cnt < W_TYPE_SIZE.  */
 #define lsh2(rh, rl, ah, al, cnt)                                       \
   do {                                                                  \
     (rh) = ((ah) << cnt) | ((al) >> (W_TYPE_SIZE - (cnt)));             \
@@ -422,12 +424,15 @@ mod2 (uintmax_t *r1, uintmax_t a1, uintmax_t a0, uintmax_t d1, uintmax_t d0)
   count_leading_zeros (cntd, d1);
   count_leading_zeros (cnta, a1);
   int cnt = cntd - cnta;
-  lsh2 (d1, d0, d1, d0, cnt);
-  for (int i = 0; i < cnt; i++)
+  if (0 < cnt)
     {
-      if (ge2 (a1, a0, d1, d0))
-        sub_ddmmss (a1, a0, a1, a0, d1, d0);
-      rsh2 (d1, d0, d1, d0, 1);
+      lsh2 (d1, d0, d1, d0, cnt);
+      for (int i = 0; i < cnt; i++)
+        {
+          if (ge2 (a1, a0, d1, d0))
+            sub_ddmmss (a1, a0, a1, a0, d1, d0);
+          rsh2 (d1, d0, d1, d0, 1);
+        }
     }
 
   *r1 = a1;
diff --git a/tests/factor/create-test.sh b/tests/factor/create-test.sh
index eda52f89c..2d587c0d9 100755
--- a/tests/factor/create-test.sh
+++ b/tests/factor/create-test.sh
@@ -24,6 +24,9 @@ t2=170141183460469229545748130981302223887
 # t1: 9223372036854775421 18446744073709551709
 # t2: 9223372036854775643 18446744073709551709
 
+# https://bugs.gnu.org/73474
+bug73474=22222222222222222202111121111
+
 # Each test is a triple: lo, hi, sha1 of result.
 # The test script, run.sh, runs seq lo hi|factor|sha1sum
 # and verifies that the actual and expected checksums are the same.
@@ -66,6 +69,7 @@ case $t in
   t34) set   ${q}956336   ${q}958335 d1ae6bc712d994f35edf55c785d71ddf31f16535 ;;
   t35) set   ${q}958336   ${q}960335 2374919a89196e1fce93adfe779cb4664556d4b6 ;;
   t36) set   ${q}960336   ${q}962335 569e4363e8d9e8830a187d9ab27365eef08abde1 ;;
+  t37) set    $bug73474    $bug73474 61d04aaf757acc5a37eb1d5581a98eea78ef50e8 ;;
   *)
     echo "$0: error: unknown test: '$test_name' -> '$t'" >&2
     exit 1
diff --git a/tests/local.mk b/tests/local.mk
index f72353862..2b885798a 100644
--- a/tests/local.mk
+++ b/tests/local.mk
@@ -759,7 +759,7 @@ factor_tests = \
   $(tf)/t20.sh $(tf)/t21.sh $(tf)/t22.sh $(tf)/t23.sh $(tf)/t24.sh \
   $(tf)/t25.sh $(tf)/t26.sh $(tf)/t27.sh $(tf)/t28.sh $(tf)/t29.sh \
   $(tf)/t30.sh $(tf)/t31.sh $(tf)/t32.sh $(tf)/t33.sh $(tf)/t34.sh \
-  $(tf)/t35.sh $(tf)/t36.sh
+  $(tf)/t35.sh $(tf)/t36.sh $(tf)/t37.sh
 
 $(factor_tests): $(tf)/run.sh $(tf)/create-test.sh
 	$(AM_V_GEN)$(MKDIR_P) $(tf)
-- 
2.43.0