From f16e251dae43117c2cd19359c26ce7b5e05165b6 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 12 Nov 2012 08:32:04 -0800 Subject: factor: maintainer builds primes.h, not builder With this change, the maintainer builds primes.h and it is part of the tarball. primes.h's contents are not architecture-specific. * .gitignore: Remove /src/primes.h. * src/factor.c: Include verify.h. (W): New constant. Verify that uintmax_t lacks holes and that W is no wider than the integers used to generate primes.h. * src/local.mk (EXTRA_DIST): Add src/primes.h. (BUILT_SOURCES, CLEANFILES): Remove src/primes.h. ($(top_srcdir)/src/primes.h): Rename from src/primes.h. Do not depend on src/make-prime-list. Instead, use sub-make to build, so that we build primes.h only if it does not exist. * src/make-prime-list.c: Include , for ULONG_MAX. (wide_uint): Define to uintmax_t or unsigned __int128 if not #defined. (struct prime, binvert, process_prime): Use it instead of uintmax_t. (print_wide_uint): New function. This generates the proper pinv value regardless of the width of uintmax_t on the target, so long as the width doesn't exceed that of the width of wide_uint on the maintainer host that generated src/primes.h. (output_primes): Use it. Output WIDE_UINT_BITS, too. Let the target compute its own lim, since its uintmax_t may be narrower than ours. (SZ): Remove. * src/primes.h: New file, generated with 128-bit integers and usable on any host where uintmax_t's width is no greater than 128 bits. --- src/make-prime-list.c | 98 ++++++++++++++++++++++++++++++++++----------------- 1 file changed, 66 insertions(+), 32 deletions(-) (limited to 'src/make-prime-list.c') diff --git a/src/make-prime-list.c b/src/make-prime-list.c index 24a7cdace..ab0352ea7 100644 --- a/src/make-prime-list.c +++ b/src/make-prime-list.c @@ -19,6 +19,7 @@ this program. If not, see http://www.gnu.org/licenses/. */ #include +#include #include #include #include @@ -31,20 +32,34 @@ this program. If not, see http://www.gnu.org/licenses/. */ #undef malloc #undef strerror +/* An unsigned type that is no narrower than 32 bits and no narrower + than unsigned int. It's best to make it as wide as possible. + For GCC 4.6 and later, use a heuristic to guess whether unsigned + __int128 works on your platform. If this heuristic does not work + for you, please report a bug; in the meantime compile with, e.g., + -Dwide_uint='unsigned __int128' to override the heuristic. */ +#ifndef wide_uint +# if 4 < __GNUC__ + (6 <= __GNUC_MINOR__) && ULONG_MAX >> 31 >> 31 >> 1 != 0 +typedef unsigned __int128 wide_uint; +# else +typedef uintmax_t wide_uint; +# endif +#endif + struct prime { unsigned p; - uintmax_t pinv; /* Inverse mod b = 2^{bitsize of uintmax_t} */ - uintmax_t lim; /* floor(UINTMAX_MAX / p) */ + wide_uint pinv; /* Inverse mod b = 2^{bitsize of wide_uint} */ + wide_uint lim; /* floor ((wide_uint) -1 / p) */ }; -static uintmax_t _GL_ATTRIBUTE_CONST -binvert (uintmax_t a) +static wide_uint _GL_ATTRIBUTE_CONST +binvert (wide_uint a) { - uintmax_t x = 0xf5397db1 >> (4*((a/2) & 0x7)); + wide_uint x = 0xf5397db1 >> (4*((a/2) & 0x7)); for (;;) { - uintmax_t y = 2*x - x*x*a; + wide_uint y = 2*x - x*x*a; if (y == x) return x; x = y; @@ -54,9 +69,39 @@ binvert (uintmax_t a) static void process_prime (struct prime *info, unsigned p) { + wide_uint max = -1; info->p = p; info->pinv = binvert (p); - info->lim = UINTMAX_MAX / (uintmax_t) p; + info->lim = max / p; +} + +static void +print_wide_uint (wide_uint n, int nested, unsigned wide_uint_bits) +{ + /* Number of bits per integer literal. 8 is too many, because + uintmax_t is 32 bits on some machines so we cannot shift by 32 bits. + So use 7. */ + int hex_digits_per_literal = 7; + int bits_per_literal = hex_digits_per_literal * 4; + + unsigned remainder = n & ((1 << bits_per_literal) - 1); + + if (n != remainder) + { + int needs_parentheses = n >> bits_per_literal >> bits_per_literal != 0; + if (needs_parentheses) + printf ("("); + print_wide_uint (n >> bits_per_literal, 1, wide_uint_bits); + printf (") << %d | " + !needs_parentheses, bits_per_literal); + } + else if (nested) + { + printf ("(uintmax_t) "); + hex_digits_per_literal + = ((wide_uint_bits - 1) % bits_per_literal) % 4 + 1; + } + + printf ("0x%0*xU", hex_digits_per_literal, remainder); } static void @@ -65,37 +110,26 @@ output_primes (const struct prime *primes, unsigned nprimes) unsigned i; unsigned p; int is_prime; - const char *suffix; - puts ("/* Generated file -- DO NOT EDIT */\n"); + /* Compute wide_uint_bits by repeated shifting, rather than by + multiplying sizeof by CHAR_BIT, as this works even if the + wide_uint representation has holes. */ + unsigned wide_uint_bits = 0; + wide_uint mask = -1; + for (wide_uint_bits = 0; mask; wide_uint_bits++) + mask >>= 1; - if (sizeof (uintmax_t) <= sizeof (unsigned long)) - suffix = "UL"; - else if (sizeof (uintmax_t) <= sizeof (unsigned long long)) - suffix = "ULL"; - else - { - fprintf (stderr, "Don't know how to write uintmax_t constants.\n"); - exit (EXIT_FAILURE); - } - -#if UINTMAX_MAX == UINT32_MAX -# define SZ "8" /* 8 hex digits. */ -#elif UINTMAX_MAX == UINT64_MAX -# define SZ "16" /* 16 hex digits. */ -#elif UINTMAX_MAX == UINT128_MAX -# define SZ "32" /* 32 hex digits. */ -#endif + puts ("/* Generated file -- DO NOT EDIT */\n"); + printf ("#define WIDE_UINT_BITS %u\n", wide_uint_bits); for (i = 0, p = 2; i < nprimes; i++) { unsigned int d8 = i + 8 < nprimes ? primes[i + 8].p - primes[i].p : 0xff; if (255 < d8) /* this happens at 668221 */ abort (); - printf ("P (%2u, %3u, 0x%0"SZ PRIxMAX"%s, 0x%0"SZ PRIxMAX"%s) /* %d */\n", - primes[i].p - p, d8, - primes[i].pinv, suffix, - primes[i].lim, suffix, primes[i].p); + printf ("P (%u, %u,\n ", primes[i].p - p, d8); + print_wide_uint (primes[i].pinv, 0, wide_uint_bits); + printf (",\n UINTMAX_MAX / %d)\n", primes[i].p); p = primes[i].p; } @@ -109,7 +143,7 @@ output_primes (const struct prime *primes, unsigned nprimes) { if (primes[i].p * primes[i].p > p) break; - if ( (uintmax_t) p * primes[i].pinv <= primes[i].lim) + if (p * primes[i].pinv <= primes[i].lim) { is_prime = 0; break; @@ -118,7 +152,7 @@ output_primes (const struct prime *primes, unsigned nprimes) } while (!is_prime); - printf ("#define FIRST_OMITTED_PRIME %d\n", p); + printf ("#define FIRST_OMITTED_PRIME %u\n", p); } static void * -- cgit v1.2.3-54-g00ecf