diff options
author | cperciva <cperciva@FreeBSD.org> | 2015-10-02 10:08:11 +0000 |
---|---|---|
committer | cperciva <cperciva@FreeBSD.org> | 2015-10-02 10:08:11 +0000 |
commit | 8cc71b38c27f2be8ba4c227078a51c63847a89de (patch) | |
tree | 0bbcb3f392def57bae56978c0da09362f7d6b426 /usr.bin/factor | |
parent | 0c2e89c50542aa374d776ce0787b4a06e0de1be2 (diff) | |
download | FreeBSD-src-8cc71b38c27f2be8ba4c227078a51c63847a89de.zip FreeBSD-src-8cc71b38c27f2be8ba4c227078a51c63847a89de.tar.gz |
Final step of eliminating the "games" distribution: Merge src/games
(or what's left of it, at least) into src/usr.bin.
This change will not be MFCed.
Discussed at: EuroBSDCon 2014
Committed from: EuroBSDCon 2015
Diffstat (limited to 'usr.bin/factor')
-rw-r--r-- | usr.bin/factor/Makefile | 20 | ||||
-rw-r--r-- | usr.bin/factor/Makefile.depend | 19 | ||||
-rw-r--r-- | usr.bin/factor/factor.6 | 127 | ||||
-rw-r--r-- | usr.bin/factor/factor.c | 374 |
4 files changed, 540 insertions, 0 deletions
diff --git a/usr.bin/factor/Makefile b/usr.bin/factor/Makefile new file mode 100644 index 0000000..afc9510 --- /dev/null +++ b/usr.bin/factor/Makefile @@ -0,0 +1,20 @@ +# @(#)Makefile 8.1 (Berkeley) 5/31/93 +# $FreeBSD$ + +.include <src.opts.mk> + +PROG= factor +SRCS= factor.c pr_tbl.c +CFLAGS+=-I${.CURDIR}/../primes + +.if ${MK_OPENSSL} != "no" +CFLAGS+=-DHAVE_OPENSSL +DPADD= ${LIBCRYPTO} +LDADD= -lcrypto +.endif + +MAN= factor.6 +MLINKS+=factor.6 primes.6 +.PATH: ${.CURDIR}/../primes + +.include <bsd.prog.mk> diff --git a/usr.bin/factor/Makefile.depend b/usr.bin/factor/Makefile.depend new file mode 100644 index 0000000..fc0b633 --- /dev/null +++ b/usr.bin/factor/Makefile.depend @@ -0,0 +1,19 @@ +# $FreeBSD$ +# Autogenerated - do NOT edit! + +DIRDEPS = \ + gnu/lib/csu \ + gnu/lib/libgcc \ + include \ + include/xlocale \ + lib/${CSU_DIR} \ + lib/libc \ + lib/libcompiler_rt \ + secure/lib/libcrypto \ + + +.include <dirdeps.mk> + +.if ${DEP_RELDIR} == ${_DEP_RELDIR} +# local dependencies - needed for -jN in clean tree +.endif diff --git a/usr.bin/factor/factor.6 b/usr.bin/factor/factor.6 new file mode 100644 index 0000000..ba82f14 --- /dev/null +++ b/usr.bin/factor/factor.6 @@ -0,0 +1,127 @@ +.\" Copyright (c) 1989, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Landon Curt Noll. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)factor.6 8.1 (Berkeley) 5/31/93 +.\" +.\" $FreeBSD$ +.\" +.\" By: Landon Curt Noll chongo@toad.com, ...!{sun,tolsoft}!hoptoad!chongo +.\" +.\" chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\ +.\" +.Dd October 10, 2002 +.Dt FACTOR 6 +.Os +.Sh NAME +.Nm factor , primes +.Nd factor a number, generate primes +.Sh SYNOPSIS +.Nm +.Op Fl h +.Op Ar number ... +.Nm primes +.Op Fl h +.Op Ar start Op Ar stop +.Sh DESCRIPTION +The +.Nm +utility will factor positive integers. +When a number is factored, it is printed, followed by a +.Ql \&: , +and the list of factors on a single line. +Factors are listed in ascending order, and are preceded by a space. +If a factor divides a value more than once, it will be printed more than once. +.Pp +When +.Nm +is invoked with one or more arguments, each argument will be factored. +.Pp +When +.Nm +is invoked with no arguments, +.Nm +reads numbers, one per line, from standard input, until end of file or error. +Leading white-space and empty lines are ignored. +Numbers may be preceded by a single +.Ql + . +Numbers are terminated by a non-digit character (such as a newline). +After a number is read, it is factored. +.Pp +The +.Nm primes +utility prints primes in ascending order, one per line, starting at or above +.Ar start +and continuing until, but not including +.Ar stop . +The +.Ar start +value must be at least 0 and not greater than +.Ar stop . +The +.Ar stop +value must not be greater than the maximum. +The default and maximum value of +.Ar stop +is 3825123056546413050. +.Pp +When the +.Nm primes +utility is invoked with no arguments, +.Ar start +is read from standard input and +.Ar stop +is taken to be the maximum. +The +.Ar start +value may be preceded by a single +.Ql + . +The +.Ar start +value is terminated by a non-digit character (such as a newline). +.Sh DIAGNOSTICS +.Bl -diag +.It "negative numbers aren't permitted" +.It "illegal numeric format" +.It "start value must be less than stop value" +.It "Result too large" +.El +.Sh BUGS +.Nm +cannot handle the +.Dq "10 most wanted" +factor list, +.Nm primes +will not get you a world record. +.Pp +.Nm primes +is unable to list primes between 3825123056546413050 and 18446744073709551615 +since it relies on strong pseudoprime tests after sieving, and nobody has +proven how many strong pseudoprime tests are required to prove primality for +integers larger than 3825123056546413050. diff --git a/usr.bin/factor/factor.c b/usr.bin/factor/factor.c new file mode 100644 index 0000000..19fe830 --- /dev/null +++ b/usr.bin/factor/factor.c @@ -0,0 +1,374 @@ +/* + * Copyright (c) 1989, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Landon Curt Noll. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef lint +#include <sys/cdefs.h> +#ifdef __COPYRIGHT +__COPYRIGHT("@(#) Copyright (c) 1989, 1993\ + The Regents of the University of California. All rights reserved."); +#endif +#ifdef __SCCSID +__SCCSID("@(#)factor.c 8.4 (Berkeley) 5/4/95"); +#endif +#ifdef __RCSID +__RCSID("$NetBSD: factor.c,v 1.19 2009/08/12 05:54:31 dholland Exp $"); +#endif +#ifdef __FBSDID +__FBSDID("$FreeBSD$"); +#endif +#endif /* not lint */ + +/* + * factor - factor a number into primes + * + * By: Landon Curt Noll chongo@toad.com, ...!{sun,tolsoft}!hoptoad!chongo + * + * chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\ + * + * usage: + * factor [-h] [number] ... + * + * The form of the output is: + * + * number: factor1 factor1 factor2 factor3 factor3 factor3 ... + * + * where factor1 <= factor2 <= factor3 <= ... + * + * If no args are given, the list of numbers are read from stdin. + */ + +#include <ctype.h> +#include <err.h> +#include <errno.h> +#include <inttypes.h> +#include <limits.h> +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> + +#include "primes.h" + +#ifdef HAVE_OPENSSL + +#include <openssl/bn.h> + +#define PRIME_CHECKS 5 + +static void pollard_pminus1(BIGNUM *); /* print factors for big numbers */ + +#else + +typedef ubig BIGNUM; +typedef u_long BN_ULONG; + +#define BN_CTX int +#define BN_CTX_new() NULL +#define BN_new() ((BIGNUM *)calloc(sizeof(BIGNUM), 1)) +#define BN_is_zero(v) (*(v) == 0) +#define BN_is_one(v) (*(v) == 1) +#define BN_mod_word(a, b) (*(a) % (b)) + +static int BN_dec2bn(BIGNUM **a, const char *str); +static int BN_hex2bn(BIGNUM **a, const char *str); +static BN_ULONG BN_div_word(BIGNUM *, BN_ULONG); +static void BN_print_fp(FILE *, const BIGNUM *); + +#endif + +static void BN_print_dec_fp(FILE *, const BIGNUM *); + +static void pr_fact(BIGNUM *); /* print factors of a value */ +static void pr_print(BIGNUM *); /* print a prime */ +static void usage(void); + +static BN_CTX *ctx; /* just use a global context */ +static int hflag; + +int +main(int argc, char *argv[]) +{ + BIGNUM *val; + int ch; + char *p, buf[LINE_MAX]; /* > max number of digits. */ + + ctx = BN_CTX_new(); + val = BN_new(); + if (val == NULL) + errx(1, "can't initialise bignum"); + + while ((ch = getopt(argc, argv, "h")) != -1) + switch (ch) { + case 'h': + hflag++; + break; + case '?': + default: + usage(); + } + argc -= optind; + argv += optind; + + /* No args supplied, read numbers from stdin. */ + if (argc == 0) + for (;;) { + if (fgets(buf, sizeof(buf), stdin) == NULL) { + if (ferror(stdin)) + err(1, "stdin"); + exit (0); + } + for (p = buf; isblank(*p); ++p); + if (*p == '\n' || *p == '\0') + continue; + if (*p == '-') + errx(1, "negative numbers aren't permitted."); + if (BN_dec2bn(&val, buf) == 0 && + BN_hex2bn(&val, buf) == 0) + errx(1, "%s: illegal numeric format.", buf); + pr_fact(val); + } + /* Factor the arguments. */ + else + for (; *argv != NULL; ++argv) { + if (argv[0][0] == '-') + errx(1, "negative numbers aren't permitted."); + if (BN_dec2bn(&val, argv[0]) == 0 && + BN_hex2bn(&val, argv[0]) == 0) + errx(1, "%s: illegal numeric format.", argv[0]); + pr_fact(val); + } + exit(0); +} + +/* + * pr_fact - print the factors of a number + * + * Print the factors of the number, from the lowest to the highest. + * A factor will be printed multiple times if it divides the value + * multiple times. + * + * Factors are printed with leading tabs. + */ +static void +pr_fact(BIGNUM *val) +{ + const ubig *fact; /* The factor found. */ + + /* Firewall - catch 0 and 1. */ + if (BN_is_zero(val)) /* Historical practice; 0 just exits. */ + exit(0); + if (BN_is_one(val)) { + printf("1: 1\n"); + return; + } + + /* Factor value. */ + + if (hflag) { + fputs("0x", stdout); + BN_print_fp(stdout, val); + } else + BN_print_dec_fp(stdout, val); + putchar(':'); + for (fact = &prime[0]; !BN_is_one(val); ++fact) { + /* Look for the smallest factor. */ + do { + if (BN_mod_word(val, (BN_ULONG)*fact) == 0) + break; + } while (++fact <= pr_limit); + + /* Watch for primes larger than the table. */ + if (fact > pr_limit) { +#ifdef HAVE_OPENSSL + BIGNUM *bnfact; + + bnfact = BN_new(); + BN_set_word(bnfact, *(fact - 1)); + if (!BN_sqr(bnfact, bnfact, ctx)) + errx(1, "error in BN_sqr()"); + if (BN_cmp(bnfact, val) > 0 || + BN_is_prime(val, PRIME_CHECKS, + NULL, NULL, NULL) == 1) + pr_print(val); + else + pollard_pminus1(val); +#else + pr_print(val); +#endif + break; + } + + /* Divide factor out until none are left. */ + do { + printf(hflag ? " 0x%" PRIx64 "" : " %" PRIu64 "", *fact); + BN_div_word(val, (BN_ULONG)*fact); + } while (BN_mod_word(val, (BN_ULONG)*fact) == 0); + + /* Let the user know we're doing something. */ + fflush(stdout); + } + putchar('\n'); +} + +static void +pr_print(BIGNUM *val) +{ + if (hflag) { + fputs(" 0x", stdout); + BN_print_fp(stdout, val); + } else { + putchar(' '); + BN_print_dec_fp(stdout, val); + } +} + +static void +usage(void) +{ + fprintf(stderr, "usage: factor [-h] [value ...]\n"); + exit(1); +} + +#ifdef HAVE_OPENSSL + +/* pollard p-1, algorithm from Jim Gillogly, May 2000 */ +static void +pollard_pminus1(BIGNUM *val) +{ + BIGNUM *base, *rbase, *num, *i, *x; + + base = BN_new(); + rbase = BN_new(); + num = BN_new(); + i = BN_new(); + x = BN_new(); + + BN_set_word(rbase, 1); +newbase: + if (!BN_add_word(rbase, 1)) + errx(1, "error in BN_add_word()"); + BN_set_word(i, 2); + BN_copy(base, rbase); + + for (;;) { + BN_mod_exp(base, base, i, val, ctx); + if (BN_is_one(base)) + goto newbase; + + BN_copy(x, base); + BN_sub_word(x, 1); + if (!BN_gcd(x, x, val, ctx)) + errx(1, "error in BN_gcd()"); + + if (!BN_is_one(x)) { + if (BN_is_prime(x, PRIME_CHECKS, NULL, NULL, + NULL) == 1) + pr_print(x); + else + pollard_pminus1(x); + fflush(stdout); + + BN_div(num, NULL, val, x, ctx); + if (BN_is_one(num)) + return; + if (BN_is_prime(num, PRIME_CHECKS, NULL, NULL, + NULL) == 1) { + pr_print(num); + fflush(stdout); + return; + } + BN_copy(val, num); + } + if (!BN_add_word(i, 1)) + errx(1, "error in BN_add_word()"); + } +} + +/* + * Sigh.. No _decimal_ output to file functions in BN. + */ +static void +BN_print_dec_fp(FILE *fp, const BIGNUM *num) +{ + char *buf; + + buf = BN_bn2dec(num); + if (buf == NULL) + return; /* XXX do anything here? */ + fprintf(fp, "%s", buf); + free(buf); +} + +#else + +static void +BN_print_fp(FILE *fp, const BIGNUM *num) +{ + fprintf(fp, "%lx", (unsigned long)*num); +} + +static void +BN_print_dec_fp(FILE *fp, const BIGNUM *num) +{ + fprintf(fp, "%lu", (unsigned long)*num); +} + +static int +BN_dec2bn(BIGNUM **a, const char *str) +{ + char *p; + + errno = 0; + **a = strtoul(str, &p, 10); + return (errno == 0 && (*p == '\n' || *p == '\0')); +} + +static int +BN_hex2bn(BIGNUM **a, const char *str) +{ + char *p; + + errno = 0; + **a = strtoul(str, &p, 16); + return (errno == 0 && (*p == '\n' || *p == '\0')); +} + +static BN_ULONG +BN_div_word(BIGNUM *a, BN_ULONG b) +{ + BN_ULONG mod; + + mod = *a % b; + *a /= b; + return mod; +} + +#endif |