[src/trunk]: src/games Imported and adapted from FreeBSD svn r272166 and r272...

[ast <ast%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/4f43adadabd8
branches:  trunk
changeset: 802810:4f43adadabd8
user:      ast <ast%NetBSD.org@localhost>
date:      Thu Oct 02 21:36:37 2014 +0000

description:
Imported and adapted from FreeBSD svn r272166 and r272207; this fixes
false positives for products of primes larger than 2^16. For example,
before this commit:

  $ /usr/games/primes 4295360521 4295360522
  4295360521
but
  $ /usr/games/factor 4295360521
  4295360521: 65539 65539

or
  $ /usr/games/primes 3825123056546413049 3825123056546413050
  3825123056546413049
yet
  $ /usr/games/factor 3825123056546413049
  3825123056546413049: 165479 23115459100831

or
  $ /usr/games/primes 18446744073709551577
  18446744073709551577
although
  $ /usr/games/factor 18446744073709551577
  18446744073709551577: 139646831 132095686967

Incidentally, the above examples show the smallest and largest cases that
were erroneously stated as prime in the range 2^32 .. 3825123056546413049
.. 2^64; the primes(6) program now stops at 3825123056546413050 as
primality tests on larger integers would be by brute force factorization.

In addition, special to the NetBSD version:
. for -d option, skip first difference when start is >65537 as it is incorrect
. corrected usage to mention both the existing -d as well as the new -h option

For original FreeBSD commit message by Colin Percival, see:
http://svnweb.freebsd.org/base?view=revision&revision=272166

diffstat:

 games/factor/factor.6  |   17 +--
 games/factor/factor.c  |   16 +--
 games/primes/Makefile  |    4 +-
 games/primes/pattern.c |   13 +-
 games/primes/pr_tbl.c  |   16 ++--
 games/primes/primes.6  |   42 +++++++---
 games/primes/primes.c  |  129 +++++++++++++++-----------------
 games/primes/primes.h  |   36 +++++++-
 games/primes/spsp.c    |  195 +++++++++++++++++++++++++++++++++++++++++++++++++
 9 files changed, 344 insertions(+), 124 deletions(-)

diffs (truncated from 843 to 300 lines):

diff -r cfc442c84ac0 -r 4f43adadabd8 games/factor/factor.6
--- a/games/factor/factor.6     Thu Oct 02 21:29:44 2014 +0000
+++ b/games/factor/factor.6     Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-.\"    $NetBSD: factor.6,v 1.12 2010/05/15 21:22:39 joerg Exp $
+.\"    $NetBSD: factor.6,v 1.13 2014/10/02 21:36:37 ast Exp $
 .\"
 .\" Copyright (c) 1989, 1993
 .\"    The Regents of the University of California.  All rights reserved.
@@ -33,9 +33,7 @@
 .\"    @(#)factor.6    8.1 (Berkeley) 5/31/93
 .\"
 .\"
-.\" By: Landon Curt Noll   chongo%toad.com@localhost,   ...!{sun,tolsoft}!hoptoad!chongo
-.\"
-.\"   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
+.\" By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
 .\"
 .Dd May 15, 2010
 .Dt FACTOR 6
@@ -88,10 +86,7 @@
 .Vt unsigned long .
 .Sh DIAGNOSTICS
 Out of range or invalid input results in
-an appropriate error message
-being written to standard error.
-.\".Sh BUGS
-.\".Nm
-.\"cannot handle the
-.\".Dq 10 most wanted
-.\"factor list.
+an appropriate error message to standard error.
+.Sh AUTHORS
+Originally by
+.An Landon Curt Noll .
diff -r cfc442c84ac0 -r 4f43adadabd8 games/factor/factor.c
--- a/games/factor/factor.c     Thu Oct 02 21:29:44 2014 +0000
+++ b/games/factor/factor.c     Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: factor.c,v 1.26 2011/11/09 20:17:44 drochner Exp $     */
+/*     $NetBSD: factor.c,v 1.27 2014/10/02 21:36:37 ast Exp $  */
 
 /*
  * Copyright (c) 1989, 1993
@@ -42,16 +42,14 @@
 #if 0
 static char sccsid[] = "@(#)factor.c   8.4 (Berkeley) 5/4/95";
 #else
-__RCSID("$NetBSD: factor.c,v 1.26 2011/11/09 20:17:44 drochner Exp $");
+__RCSID("$NetBSD: factor.c,v 1.27 2014/10/02 21:36:37 ast Exp $");
 #endif
 #endif /* not lint */
 
 /*
  * factor - factor a number into primes
  *
- * By: Landon Curt Noll   chongo%toad.com@localhost,   ...!{sun,tolsoft}!hoptoad!chongo
- *
- *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
+ * By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
  *
  * usage:
  *     factor [number] ...
@@ -72,6 +70,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <unistd.h>
+#include <inttypes.h>
 
 #ifdef HAVE_OPENSSL
 #include <openssl/bn.h>
@@ -93,8 +92,7 @@
  * We are able to sieve 2^32-1 because this byte table yields all primes
  * up to 65537 and 65537^2 > 2^32-1.
  */
-extern const ubig prime[];
-extern const ubig *pr_limit;           /* largest prime in the prime array */
+
 #if 0 /* debugging: limit table use to stress the "pollard" code */
 #define pr_limit &prime[0]
 #endif
@@ -198,7 +196,7 @@
 static void
 pr_fact(BIGNUM *val)
 {
-       const ubig *fact;               /* The factor found. */
+       const uint64_t *fact;           /* The factor found. */
 
        /* Firewall - catch 0 and 1. */
        if (BN_is_zero(val) || BN_is_one(val))
@@ -239,7 +237,7 @@
 
                /* Divide factor out until none are left. */
                do {
-                       printf(" %lu", *fact);
+                       printf(" %" PRIu64, *fact);
                        BN_div_word(val, (BN_ULONG)*fact);
                } while (BN_mod_word(val, (BN_ULONG)*fact) == 0);
 
diff -r cfc442c84ac0 -r 4f43adadabd8 games/primes/Makefile
--- a/games/primes/Makefile     Thu Oct 02 21:29:44 2014 +0000
+++ b/games/primes/Makefile     Thu Oct 02 21:36:37 2014 +0000
@@ -1,8 +1,8 @@
-#      $NetBSD: Makefile,v 1.7 2004/02/08 13:16:25 jsm Exp $
+#      $NetBSD: Makefile,v 1.8 2014/10/02 21:36:37 ast Exp $
 #      @(#)Makefile    8.1 (Berkeley) 5/31/93
 
 PROG=          primes
-SRCS=          pattern.c pr_tbl.c primes.c
+SRCS=          pattern.c pr_tbl.c primes.c spsp.c
 MAN=           primes.6
 DPADD=         ${LIBM}
 LDADD=         -lm
diff -r cfc442c84ac0 -r 4f43adadabd8 games/primes/pattern.c
--- a/games/primes/pattern.c    Thu Oct 02 21:29:44 2014 +0000
+++ b/games/primes/pattern.c    Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: pattern.c,v 1.6 2003/08/07 09:37:33 agc Exp $  */
+/*     $NetBSD: pattern.c,v 1.7 2014/10/02 21:36:37 ast Exp $  */
 
 /*
  * Copyright (c) 1989, 1993
@@ -32,21 +32,20 @@
  * SUCH DAMAGE.
  */
 
-#include <sys/cdefs.h>
+#include <sys/types.h>
+
 #ifndef lint
 #if 0
 static char sccsid[] = "@(#)pattern.c  8.1 (Berkeley) 5/31/93";
 #else
-__RCSID("$NetBSD: pattern.c,v 1.6 2003/08/07 09:37:33 agc Exp $");
+__RCSID("$NetBSD: pattern.c,v 1.7 2014/10/02 21:36:37 ast Exp $");
 #endif
 #endif /* not lint */
 
 /*
  * pattern - the Eratosthenes sieve on odd numbers for 3,5,7,11 and 13
  *
- * By: Landon Curt Noll                             chongo%toad.com@localhost
- *
- *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
+ * By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
  *
  * To avoid excessive sieves for small factors, we use the table below to 
  * setup our sieve blocks.  Each element represents a odd number starting 
@@ -440,4 +439,4 @@
 0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
 0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,0,0,0,1
 };
-const int pattern_size = (sizeof(pattern)/sizeof(pattern[0]));
+const size_t pattern_size = (sizeof(pattern)/sizeof(pattern[0]));
diff -r cfc442c84ac0 -r 4f43adadabd8 games/primes/pr_tbl.c
--- a/games/primes/pr_tbl.c     Thu Oct 02 21:29:44 2014 +0000
+++ b/games/primes/pr_tbl.c     Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: pr_tbl.c,v 1.7 2003/08/07 09:37:33 agc Exp $   */
+/*     $NetBSD: pr_tbl.c,v 1.8 2014/10/02 21:36:37 ast Exp $   */
 
 /*
  * Copyright (c) 1989, 1993
@@ -37,24 +37,24 @@
 #if 0
 static char sccsid[] = "@(#)pr_tbl.c   8.1 (Berkeley) 5/31/93";
 #else
-__RCSID("$NetBSD: pr_tbl.c,v 1.7 2003/08/07 09:37:33 agc Exp $");
+__RCSID("$NetBSD: pr_tbl.c,v 1.8 2014/10/02 21:36:37 ast Exp $");
 #endif
 #endif /* not lint */
 
 /*
  * prime - prime table
  *
- * By: Landon Curt Noll   chongo%toad.com@localhost,   ...!{sun,tolsoft}!hoptoad!chongo
+ * By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
  *
- *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
- *
- * We are able to sieve 2^32-1 because this table has primes up to 65537 
+ * We are able to sieve 2^32-1 because this table has primes up to 65537
  * and 65537^2 > 2^32-1.
  */
 
+#include <stddef.h>
+
 #include "primes.h"
 
-const ubig prime[] = {
+const uint64_t prime[] = {
 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
 107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,
 211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,
@@ -546,4 +546,4 @@
 };
 
 /* pr_limit - largest prime in the prime table */
-const ubig *pr_limit = &prime[(sizeof(prime)/sizeof(prime[0]))-1];
+const uint64_t *const pr_limit = &prime[(sizeof(prime)/sizeof(prime[0]))-1];
diff -r cfc442c84ac0 -r 4f43adadabd8 games/primes/primes.6
--- a/games/primes/primes.6     Thu Oct 02 21:29:44 2014 +0000
+++ b/games/primes/primes.6     Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-.\"    $NetBSD: primes.6,v 1.3 2008/02/03 03:29:17 wiz Exp $
+.\"    $NetBSD: primes.6,v 1.4 2014/10/02 21:36:37 ast Exp $
 .\"
 .\" Copyright (c) 1989, 1993
 .\"    The Regents of the University of California.  All rights reserved.
@@ -33,9 +33,7 @@
 .\"    @(#)factor.6    8.1 (Berkeley) 5/31/93
 .\"
 .\"
-.\" By: Landon Curt Noll   chongo%toad.com@localhost,   ...!{sun,tolsoft}!hoptoad!chongo
-.\"
-.\"   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
+.\" By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
 .\"
 .Dd February 3, 2008
 .Dt PRIMES 6
@@ -46,6 +44,7 @@
 .Sh SYNOPSIS
 .Nm primes
 .Op Fl d
+.Op Fl h
 .Op Ar start Op Ar stop
 .Sh DESCRIPTION
 The
@@ -61,18 +60,18 @@
 .Ar stop .
 The
 .Ar stop
-value must not be greater than 4294967295.
+value must not be greater than 3825123056546413050.
 The default value of
 .Ar stop
-is 4294967295.
+is 3825123056546413050.
 .Pp
 When the
 .Nm
 utility is invoked with no arguments,
 .Ar start
-is read from standard input.
+is read from standard input and
 .Ar stop
-is taken to be 4294967295.
+is taken to be 3825123056546413050.
 The
 .Ar start
 value may be preceded by a single
@@ -81,15 +80,34 @@
 .Ar start
 value is terminated by a non-digit character (such as a newline).
 The input line must not be longer than 255 characters.
+.Pp
 When given the
 .Fl d
 argument,
 .Nm
 prints the difference between the current and the previous prime.
+.Pp
+When given the
+.Fl h
+argument,
+.Nm
+prints the prime numbers in hexadecimal.
 .Sh DIAGNOSTICS
 Out of range or invalid input results in
-an appropriate error message
-being written to standard error.
-.Sh BUGS
+an appropriate error message to standard error.
+.Sh AUTHORS
+Originally by
+.An Landon Curt Noll ,
+extended to some 64-bit primes by
+.An Colin Percival .
+.Sh CAVEATS
+This
 .Nm
-won't get you a world record.
+program won't get you a world record.
+.Pp
+The program is not able to list primes between
+3825123056546413050 and 18446744073709551615 (2^64
+- 1) as it relies on strong pseudoprime tests after
+sieving, and it is yet unknown how many of those
+tests are needed to prove primality for integers
+larger than 3825123056546413050.
diff -r cfc442c84ac0 -r 4f43adadabd8 games/primes/primes.c
--- a/games/primes/primes.c     Thu Oct 02 21:29:44 2014 +0000
+++ b/games/primes/primes.c     Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: primes.c,v 1.19 2011/08/30 02:58:04 jakllsch Exp $     */
+/*     $NetBSD: primes.c,v 1.20 2014/10/02 21:36:37 ast Exp $  */
 
 /*
  * Copyright (c) 1989, 1993
@@ -42,23 +42,23 @@