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 <limits.h>, 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.

1 files changed, 66 insertions, 32 deletions

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 <config.h>
 
+#include <limits.h>
 #include <stdint.h>
 #include <inttypes.h>
 #include <stdio.h>
@@ -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 *