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 <egg...@cs.ucla.edu>
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
