From 46e5702bf316b7697e0496f2913a8a78c8442992 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 31 Jul 2023 13:43:19 -0700 Subject: [PATCH] factor: prefer signed types MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit When it’s easy, prefer signed types to unsigned, as they are less confusing and allow overflow checking. * src/factor.c (struct mp_factors, udiv_qrnnd) (count_leading_zeros, count_trailing_zeros) (factor_insert_multiplicity, mp_factor_clear, mp_factor_insert) (factor_insert_refind, factor_using_division) (mp_factor_using_division, powm2, millerrabin, millerrabin2) (mp_millerrabin, prime_p, prime2_p, mp_prime_p, isqrt, isqrt2) (invtab, q_freq, factor_using_squfof, strto2uintmax) (print_factors_single, main): Prefer signed integers to unsigned. --- src/factor.c | 123 +++++++++++++++++++++++++-------------------------- 1 file changed, 60 insertions(+), 63 deletions(-) diff --git a/src/factor.c b/src/factor.c index e0a98152cc..9963a5df24 100644 --- a/src/factor.c +++ b/src/factor.c @@ -246,7 +246,7 @@ struct mp_factors { mpz_t *p; unsigned long int *e; - unsigned long int nfactors; + idx_t nfactors; }; static void factor (uintmax_t, uintmax_t, struct factors *); @@ -291,7 +291,7 @@ static void factor (uintmax_t, uintmax_t, struct factors *); __r1 = (n1); __r0 = (n0); \ affirm (__r1 < __d1); \ __q = 0; \ - for (unsigned int __i = W_TYPE_SIZE; __i > 0; __i--) \ + for (int __i = W_TYPE_SIZE; __i > 0; __i--) \ { \ rsh2 (__d1, __d0, __d1, __d0, 1); \ __q <<= 1; \ @@ -347,7 +347,7 @@ static void factor (uintmax_t, uintmax_t, struct factors *); #ifndef count_leading_zeros # define count_leading_zeros(count, x) do { \ uintmax_t __clz_x = (x); \ - unsigned int __clz_c; \ + int __clz_c; \ for (__clz_c = 0; \ (__clz_x & ((uintmax_t) 0xff << (W_TYPE_SIZE - 8))) == 0; \ __clz_c += 8) \ @@ -361,7 +361,7 @@ static void factor (uintmax_t, uintmax_t, struct factors *); #ifndef count_trailing_zeros # define count_trailing_zeros(count, x) do { \ uintmax_t __ctz_x = (x); \ - unsigned int __ctz_c = 0; \ + int __ctz_c = 0; \ while ((__ctz_x & 1) == 0) \ { \ __ctz_x >>= 1; \ @@ -518,9 +518,9 @@ gcd2_odd (uintmax_t *r1, uintmax_t a1, uintmax_t a0, uintmax_t b1, uintmax_t b0) static void factor_insert_multiplicity (struct factors *factors, - uintmax_t prime, unsigned int m) + uintmax_t prime, int m) { - unsigned int nfactors = factors->nfactors; + int nfactors = factors->nfactors; uintmax_t *p = factors->p; unsigned char *e = factors->e; @@ -600,7 +600,7 @@ mp_factor_init (struct mp_factors *factors) static void mp_factor_clear (struct mp_factors *factors) { - for (unsigned int i = 0; i < factors->nfactors; i++) + for (idx_t i = 0; i < factors->nfactors; i++) mpz_clear (factors->p[i]); free (factors->p); @@ -610,10 +610,10 @@ mp_factor_clear (struct mp_factors *factors) static void mp_factor_insert (struct mp_factors *factors, mpz_t prime) { - unsigned long int nfactors = factors->nfactors; - mpz_t *p = factors->p; - unsigned long int *e = factors->e; - long i; + idx_t nfactors = factors->nfactors; + mpz_t *p = factors->p; + unsigned long int *e = factors->e; + ptrdiff_t i; /* Locate position for insert new or increment e. */ for (i = nfactors - 1; i >= 0; i--) @@ -624,8 +624,8 @@ mp_factor_insert (struct mp_factors *factors, mpz_t prime) if (i < 0 || mpz_cmp (p[i], prime) != 0) { - p = xrealloc (p, (nfactors + 1) * sizeof p[0]); - e = xrealloc (e, (nfactors + 1) * sizeof e[0]); + p = xireallocarray (p, nfactors + 1, sizeof p[0]); + e = xireallocarray (e, nfactors + 1, sizeof e[0]); mpz_init (p[nfactors]); for (long j = nfactors - 1; j > i; j--) @@ -707,10 +707,9 @@ static bool flag_prove_primality = PROVE_PRIMALITY; #define MR_REPS 25 static void -factor_insert_refind (struct factors *factors, uintmax_t p, unsigned int i, - unsigned int off) +factor_insert_refind (struct factors *factors, uintmax_t p, int i, int off) { - for (unsigned int j = 0; j < off; j++) + for (int j = 0; j < off; j++) p += primes_diff[i + j]; factor_insert (factors, p); } @@ -754,7 +753,7 @@ factor_using_division (uintmax_t *t1p, uintmax_t t1, uintmax_t t0, { if (t0 % 2 == 0) { - unsigned int cnt; + int cnt; if (t0 == 0) { @@ -773,7 +772,7 @@ factor_using_division (uintmax_t *t1p, uintmax_t t1, uintmax_t t0, } uintmax_t p = 3; - unsigned int i; + idx_t i; for (i = 0; t1 > 0 && i < PRIMES_PTAB_ENTRIES; i++) { for (;;) @@ -834,7 +833,7 @@ static void mp_factor_using_division (mpz_t t, struct mp_factors *factors) { mpz_t q; - unsigned long int p; + mp_bitcnt_t p; devmsg ("[trial division] "); @@ -848,19 +847,19 @@ mp_factor_using_division (mpz_t t, struct mp_factors *factors) --p; } - p = 3; - for (unsigned int i = 1; i <= PRIMES_PTAB_ENTRIES;) + unsigned long int d = 3; + for (idx_t i = 1; i <= PRIMES_PTAB_ENTRIES;) { - if (! mpz_divisible_ui_p (t, p)) + if (! mpz_divisible_ui_p (t, d)) { - p += primes_diff[i++]; - if (mpz_cmp_ui (t, p * p) < 0) + d += primes_diff[i++]; + if (mpz_cmp_ui (t, d * d) < 0) break; } else { - mpz_tdiv_q_ui (t, t, p); - mp_factor_insert_ui (factors, p); + mpz_tdiv_q_ui (t, t, d); + mp_factor_insert_ui (factors, d); } } @@ -1080,7 +1079,7 @@ powm2 (uintmax_t *r1m, uintmax_t ni, const uintmax_t *one) { uintmax_t r1, r0, b1, b0, n1, n0; - unsigned int i; + int i; uintmax_t e; b0 = bp[0]; @@ -1118,7 +1117,7 @@ powm2 (uintmax_t *r1m, ATTRIBUTE_CONST static bool millerrabin (uintmax_t n, uintmax_t ni, uintmax_t b, uintmax_t q, - unsigned int k, uintmax_t one) + int k, uintmax_t one) { uintmax_t y = powm (b, q, n, ni, one); @@ -1127,7 +1126,7 @@ millerrabin (uintmax_t n, uintmax_t ni, uintmax_t b, uintmax_t q, if (y == one || y == nm1) return true; - for (unsigned int i = 1; i < k; i++) + for (int i = 1; i < k; i++) { y = mulredc (y, y, n, ni); @@ -1141,7 +1140,7 @@ millerrabin (uintmax_t n, uintmax_t ni, uintmax_t b, uintmax_t q, ATTRIBUTE_PURE static bool millerrabin2 (const uintmax_t *np, uintmax_t ni, const uintmax_t *bp, - const uintmax_t *qp, unsigned int k, const uintmax_t *one) + const uintmax_t *qp, int k, const uintmax_t *one) { uintmax_t y1, y0, nm1_1, nm1_0, r1m; @@ -1156,7 +1155,7 @@ millerrabin2 (const uintmax_t *np, uintmax_t ni, const uintmax_t *bp, if (y0 == nm1_0 && y1 == nm1_1) return true; - for (unsigned int i = 1; i < k; i++) + for (int i = 1; i < k; i++) { y0 = mulredc2 (&r1m, y1, y0, y1, y0, np[1], np[0], ni); y1 = r1m; @@ -1171,14 +1170,14 @@ millerrabin2 (const uintmax_t *np, uintmax_t ni, const uintmax_t *bp, static bool mp_millerrabin (mpz_srcptr n, mpz_srcptr nm1, mpz_ptr x, mpz_ptr y, - mpz_srcptr q, unsigned long int k) + mpz_srcptr q, mp_bitcnt_t k) { mpz_powm (y, x, q, n); if (mpz_cmp_ui (y, 1) == 0 || mpz_cmp (y, nm1) == 0) return true; - for (unsigned long int i = 1; i < k; i++) + for (mp_bitcnt_t i = 1; i < k; i++) { mpz_powm_ui (y, y, 2, n); if (mpz_cmp (y, nm1) == 0) @@ -1194,7 +1193,7 @@ mp_millerrabin (mpz_srcptr n, mpz_srcptr nm1, mpz_ptr x, mpz_ptr y, static bool ATTRIBUTE_PURE prime_p (uintmax_t n) { - int k; + mp_bitcnt_t k; bool is_prime; uintmax_t a_prim, one, ni; struct factors factors; @@ -1228,12 +1227,12 @@ prime_p (uintmax_t n) /* Loop until Lucas proves our number prime, or Miller-Rabin proves our number composite. */ - for (unsigned int r = 0; r < PRIMES_PTAB_ENTRIES; r++) + for (idx_t r = 0; r < PRIMES_PTAB_ENTRIES; r++) { if (flag_prove_primality) { is_prime = true; - for (unsigned int i = 0; i < factors.nfactors && is_prime; i++) + for (int i = 0; i < factors.nfactors && is_prime; i++) { is_prime = powm (a_prim, (n - 1) / factors.p[i], n, ni, one) != one; @@ -1280,7 +1279,7 @@ prime2_p (uintmax_t n1, uintmax_t n0) uintmax_t one[2]; uintmax_t na[2]; uintmax_t ni; - unsigned int k; + int k; struct factors factors; if (n1 == 0) @@ -1322,7 +1321,7 @@ prime2_p (uintmax_t n1, uintmax_t n0) /* Loop until Lucas proves our number prime, or Miller-Rabin proves our number composite. */ - for (unsigned int r = 0; r < PRIMES_PTAB_ENTRIES; r++) + for (idx_t r = 0; r < PRIMES_PTAB_ENTRIES; r++) { bool is_prime; uintmax_t e[2], y[2]; @@ -1339,7 +1338,7 @@ prime2_p (uintmax_t n1, uintmax_t n0) y[0] = powm2 (&y[1], a_prim, e, na, ni, one); is_prime = (y[0] != one[0] || y[1] != one[1]); } - for (unsigned int i = 0; i < factors.nfactors && is_prime; i++) + for (int i = 0; i < factors.nfactors && is_prime; i++) { /* FIXME: We always have the factor 2. Do we really need to handle it here? We have done the same powering as part @@ -1391,7 +1390,7 @@ mp_prime_p (mpz_t n) mpz_sub_ui (nm1, n, 1); /* Find q and k, where q is odd and n = 1 + 2**k * q. */ - unsigned long int k = mpz_scan1 (nm1, 0); + mp_bitcnt_t k = mpz_scan1 (nm1, 0); mpz_tdiv_q_2exp (q, nm1, k); mpz_set_ui (a, 2); @@ -1412,12 +1411,12 @@ mp_prime_p (mpz_t n) /* Loop until Lucas proves our number prime, or Miller-Rabin proves our number composite. */ - for (unsigned int r = 0; r < PRIMES_PTAB_ENTRIES; r++) + for (idx_t r = 0; r < PRIMES_PTAB_ENTRIES; r++) { if (flag_prove_primality) { is_prime = true; - for (unsigned long int i = 0; i < factors.nfactors && is_prime; i++) + for (idx_t i = 0; i < factors.nfactors && is_prime; i++) { mpz_divexact (tmp, nm1, factors.p[i]); mpz_powm (tmp, a, tmp, n); @@ -1763,14 +1762,14 @@ static uintmax_t isqrt (uintmax_t n) { uintmax_t x; - unsigned c; + int c; if (n == 0) return 0; count_leading_zeros (c, n); /* Make x > sqrt(n). This will be invariant through the loop. */ - x = (uintmax_t) 1 << ((W_TYPE_SIZE + 1 - c) / 2); + x = (uintmax_t) 1 << ((W_TYPE_SIZE + 1 - c) >> 1); for (;;) { @@ -1786,7 +1785,7 @@ ATTRIBUTE_CONST static uintmax_t isqrt2 (uintmax_t nh, uintmax_t nl) { - unsigned int shift; + int shift; uintmax_t x; /* Ensures the remainder fits in an uintmax_t. */ @@ -1800,7 +1799,7 @@ isqrt2 (uintmax_t nh, uintmax_t nl) /* Make x > sqrt (n). */ x = isqrt ((nh << shift) + (nl >> (W_TYPE_SIZE - shift))) + 1; - x <<= (W_TYPE_SIZE - shift) / 2; + x <<= (W_TYPE_SIZE - shift) >> 1; /* Do we need more than one iteration? */ for (;;) @@ -1855,7 +1854,7 @@ is_square (uintmax_t x) } /* invtab[i] = floor (0x10000 / (0x100 + i) */ -static const unsigned short invtab[0x81] = +static short const invtab[0x81] = { 0x200, 0x1fc, 0x1f8, 0x1f4, 0x1f0, 0x1ec, 0x1e9, 0x1e5, 0x1e1, @@ -1952,7 +1951,7 @@ static const unsigned short invtab[0x81] = #if STAT_SQUFOF # define Q_FREQ_SIZE 50 /* Element 0 keeps the total */ -static unsigned int q_freq[Q_FREQ_SIZE + 1]; +static int q_freq[Q_FREQ_SIZE + 1]; #endif #if USE_SQUFOF @@ -1969,17 +1968,15 @@ factor_using_squfof (uintmax_t n1, uintmax_t n0, struct factors *factors) https://homes.cerias.purdue.edu/~ssw/squfof.pdf */ - static const unsigned int multipliers_1[] = + static short const multipliers_1[] = { /* = 1 (mod 4) */ 105, 165, 21, 385, 33, 5, 77, 1, 0 }; - static const unsigned int multipliers_3[] = + static short const multipliers_3[] = { /* = 3 (mod 4) */ 1155, 15, 231, 35, 3, 55, 7, 11, 0 }; - const unsigned int *m; - struct { uintmax_t Q; uintmax_t P; } queue[QUEUE_SIZE]; if (n1 >= ((uintmax_t) 1 << (W_TYPE_SIZE - 2))) @@ -2017,13 +2014,13 @@ factor_using_squfof (uintmax_t n1, uintmax_t n0, struct factors *factors) } /* Select multipliers so we always get n * mu = 3 (mod 4) */ - for (m = (n0 % 4 == 1) ? multipliers_3 : multipliers_1; + for (short const *m = (n0 % 4 == 1) ? multipliers_3 : multipliers_1; *m; m++) { uintmax_t S, Dh, Dl, Q1, Q, P, L, L1, B; unsigned int i; unsigned int mu = *m; - unsigned int qpos = 0; + int qpos = 0; affirm (mu * n0 % 4 == 3); @@ -2113,7 +2110,7 @@ factor_using_squfof (uintmax_t n1, uintmax_t n0, struct factors *factors) uintmax_t r = is_square (Q); if (r) { - for (unsigned int j = 0; j < qpos; j++) + for (int j = 0; j < qpos; j++) { if (queue[j].Q == r) { @@ -2270,7 +2267,7 @@ mp_factor (mpz_t t, struct mp_factors *factors) static strtol_error strto2uintmax (uintmax_t *hip, uintmax_t *lop, char const *s) { - unsigned int lo_carry; + int lo_carry; uintmax_t hi = 0, lo = 0; strtol_error err = LONGINT_INVALID; @@ -2279,7 +2276,7 @@ strto2uintmax (uintmax_t *hip, uintmax_t *lop, char const *s) char const *p = s; for (;;) { - unsigned int c = *p++; + unsigned char c = *p++; if (c == 0) break; @@ -2294,7 +2291,7 @@ strto2uintmax (uintmax_t *hip, uintmax_t *lop, char const *s) while (err == LONGINT_OK) { - unsigned int c = *s++; + unsigned char c = *s++; if (c == 0) break; @@ -2451,8 +2448,8 @@ print_factors_single (uintmax_t t1, uintmax_t t0) factor (t1, t0, &factors); - for (unsigned int j = 0; j < factors.nfactors; j++) - for (unsigned int k = 0; k < factors.e[j]; k++) + for (int j = 0; j < factors.nfactors; j++) + for (int k = 0; k < factors.e[j]; k++) { lbuf_putc (' '); print_uintmaxes (0, factors.p[j]); @@ -2525,8 +2522,8 @@ print_factors (char const *input) putchar (':'); mp_factor (t, &factors); - for (unsigned int j = 0; j < factors.nfactors; j++) - for (unsigned int k = 0; k < factors.e[j]; k++) + for (idx_t j = 0; j < factors.nfactors; j++) + for (unsigned long int k = 0; k < factors.e[j]; k++) { putchar (' '); mpz_out_str (stdout, 10, factors.p[j]); @@ -2651,7 +2648,7 @@ main (int argc, char **argv) { double acc_f; printf ("q freq. cum. freq.(total: %d)\n", q_freq[0]); - for (unsigned int i = 1, acc_f = 0.0; i <= Q_FREQ_SIZE; i++) + for (int i = 1, acc_f = 0.0; i <= Q_FREQ_SIZE; i++) { double f = (double) q_freq[i] / q_freq[0]; acc_f += f; -- 2.47.2