uniq.

[bsdgames-darwin.git] / factor / factor.c

diff --git a/factor/factor.c b/factor/factor.c
index c578a747e2220e35300d6dad313fdb34a02541e2..23fce2b7d198d31d46f5ff1b45154aa9079581e7 100644 (file)
--- a/factor/factor.c
+++ b/factor/factor.c
@@ -1,4 +1,4 @@
-/*     $NetBSD: factor.c,v 1.5 1995/03/23 08:28:07 cgd Exp $   */
+/*     $NetBSD: factor.c,v 1.13 2002/06/18 23:07:36 simonb Exp $       */

 
 /*
  * Copyright (c) 1989, 1993
 
 /*
  * Copyright (c) 1989, 1993


@@ -36,17 +36,17 @@
  * SUCH DAMAGE.
  */
 
  * SUCH DAMAGE.
  */
 

+#include <sys/cdefs.h>

 #ifndef lint
 #ifndef lint

-static char copyright[] =
-"@(#) Copyright (c) 1989, 1993\n\
-       The Regents of the University of California.  All rights reserved.\n";
+__COPYRIGHT("@(#) Copyright (c) 1989, 1993\n\
+       The Regents of the University of California.  All rights reserved.\n");

 #endif /* not lint */
 
 #ifndef lint
 #if 0
 #endif /* not lint */
 
 #ifndef lint
 #if 0

-static char sccsid[] = "@(#)factor.c   8.3 (Berkeley) 3/30/94";
+static char sccsid[] = "@(#)factor.c   8.4 (Berkeley) 5/4/95";

 #else
 #else

-static char rcsid[] = "$NetBSD: factor.c,v 1.5 1995/03/23 08:28:07 cgd Exp $";
+__RCSID("$NetBSD: factor.c,v 1.13 2002/06/18 23:07:36 simonb Exp $");

 #endif
 #endif /* not lint */
 
 #endif
 #endif /* not lint */
 


@@ -69,37 +69,87 @@ static char rcsid[] = "$NetBSD: factor.c,v 1.5 1995/03/23 08:28:07 cgd Exp $";
  * If no args are given, the list of numbers are read from stdin.
  */
 
  * If no args are given, the list of numbers are read from stdin.
  */
 

-#include <err.h>

 #include <ctype.h>
 #include <ctype.h>

+#include <err.h>

 #include <errno.h>
 #include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <errno.h>
 #include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>

+#include <unistd.h>
+
+#ifdef HAVE_OPENSSL
+#include <openssl/bn.h>
+#else
+typedef long   BIGNUM;
+typedef u_long BN_ULONG;
+int    BN_dec2bn(BIGNUM **a, const char *str);
+#define BN_new()               ((BIGNUM *)calloc(sizeof(BIGNUM), 1))
+#define BN_is_zero(v)          (*(v) == 0)
+#define BN_is_one(v)           (*(v) == 1)
+#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))
+#endif

 
 #include "primes.h"
 
 /*
  * prime[i] is the (i-1)th prime.
  *
 
 #include "primes.h"
 
 /*
  * prime[i] is the (i-1)th prime.
  *

- * We are able to sieve 2^32-1 because this byte table yields all primes 
+ * We are able to sieve 2^32-1 because this byte table yields all primes

  * up to 65537 and 65537^2 > 2^32-1.
  */
  * up to 65537 and 65537^2 > 2^32-1.
  */

-extern ubig prime[];
-extern ubig *pr_limit;         /* largest prime in the prime array */
+extern const ubig prime[];
+extern const ubig *pr_limit;           /* largest prime in the prime array */
+
+#define        PRIME_CHECKS    5
+
+#ifdef HAVE_OPENSSL 
+BN_CTX *ctx;                           /* just use a global context */
+#endif
+
+int    main(int, char *[]);
+void   pr_fact(BIGNUM *);              /* print factors of a value */
+void   BN_print_dec_fp(FILE *, const BIGNUM *);
+void   usage(void) __attribute__((__noreturn__));
+#ifdef HAVE_OPENSSL
+void   pollard_pminus1(BIGNUM *);      /* print factors for big numbers */
+#else
+char   *BN_bn2dec(const BIGNUM *);
+BN_ULONG BN_div_word(BIGNUM *, BN_ULONG);
+#endif
+
+
+#ifndef HAVE_OPENSSL
+int
+BN_dec2bn(BIGNUM **a, const char *str)
+{
+       char *p;

 
 

-void   pr_fact __P((ubig));    /* print factors of a value */
-void   usage __P((void));
+       errno = 0;
+       **a = strtoul(str, &p, 10);
+       if (errno)
+               err(1, "%s", str);
+       return (*p == '\n' || *p == '\0');
+}
+#endif

 
 int
 
 int

-main(argc, argv)
-       int argc;
-       char *argv[];
+main(int argc, char *argv[])

 {
 {

-       ubig val;
+       BIGNUM *val;

        int ch;
        int ch;

-       char *p, buf[100];              /* > max number of digits. */
+       char *p, buf[LINE_MAX];         /* > max number of digits. */

 
 

-       while ((ch = getopt(argc, argv, "")) != EOF)
+#ifdef HAVE_OPENSSL 
+       ctx = BN_CTX_new();
+#endif
+       val = BN_new();
+       if (val == NULL)
+               errx(1, "can't initialise bignum");
+
+       while ((ch = getopt(argc, argv, "")) != -1)

                switch (ch) {
                case '?':
                default:
                switch (ch) {
                case '?':
                default:


@@ -121,12 +171,8 @@ main(argc, argv)
                                continue;
                        if (*p == '-')
                                errx(1, "negative numbers aren't permitted.");
                                continue;
                        if (*p == '-')
                                errx(1, "negative numbers aren't permitted.");

-                       errno = 0;
-                       val = strtoul(buf, &p, 10);
-                       if (errno)
-                               err(1, "%s", buf);
-                       if (*p != '\n')
-                               errx(1, "%s: illegal numeric format.", buf);
+                       if (BN_dec2bn(&val, buf) == 0)
+                               errx(1, "%s: illegal numeric format.", argv[0]);

                        pr_fact(val);
                }
        /* Factor the arguments. */
                        pr_fact(val);
                }
        /* Factor the arguments. */


@@ -134,11 +180,7 @@ main(argc, argv)
                for (; *argv != NULL; ++argv) {
                        if (argv[0][0] == '-')
                                errx(1, "negative numbers aren't permitted.");
                for (; *argv != NULL; ++argv) {
                        if (argv[0][0] == '-')
                                errx(1, "negative numbers aren't permitted.");

-                       errno = 0;
-                       val = strtoul(argv[0], &p, 10);
-                       if (errno)
-                               err(1, "%s", argv[0]);
-                       if (*p != '\0')
+                       if (BN_dec2bn(&val, argv[0]) == 0)

                                errx(1, "%s: illegal numeric format.", argv[0]);
                        pr_fact(val);
                }
                                errx(1, "%s: illegal numeric format.", argv[0]);
                        pr_fact(val);
                }


@@ -159,49 +201,152 @@ main(argc, argv)
  * Factors are printed with leading tabs.
  */
 void
  * Factors are printed with leading tabs.
  */
 void

-pr_fact(val)
-       ubig val;               /* Factor this value. */
+pr_fact(BIGNUM *val)

 {
 {

-       ubig *fact;             /* The factor found. */
+       const ubig *fact;               /* The factor found. */

 
        /* Firewall - catch 0 and 1. */
 
        /* Firewall - catch 0 and 1. */

-       if (val == 0)           /* Historical practice; 0 just exits. */
+       if (BN_is_zero(val))    /* Historical practice; 0 just exits. */

                exit(0);
                exit(0);

-       if (val == 1) {
-               (void)printf("1: 1\n");
+       if (BN_is_one(val)) {
+               printf("1: 1\n");

                return;
        }
 
        /* Factor value. */
                return;
        }
 
        /* Factor value. */

-       (void)printf("%lu:", val);
-       for (fact = &prime[0]; val > 1; ++fact) {
+
+       BN_print_dec_fp(stdout, val);
+       putchar(':');
+       for (fact = &prime[0]; !BN_is_one(val); ++fact) {

                /* Look for the smallest factor. */
                do {
                /* Look for the smallest factor. */
                do {

-                       if (val % (long)*fact == 0)
+                       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) {
                                break;
                } while (++fact <= pr_limit);
 
                /* Watch for primes larger than the table. */
                if (fact > pr_limit) {

-                       (void)printf(" %lu", val);
+#ifdef HAVE_OPENSSL
+                       BIGNUM *bnfact;
+
+                       bnfact = BN_new();
+                       BN_set_word(bnfact, *(fact - 1));
+                       BN_sqr(bnfact, bnfact, ctx);
+                       if (BN_cmp(bnfact, val) > 0) {
+                               putchar(' ');
+                               BN_print_dec_fp(stdout, val);
+                       } else
+                               pollard_pminus1(val);
+#else
+                       printf(" %s", BN_bn2dec(val));
+#endif

                        break;
                }
 
                /* Divide factor out until none are left. */
                do {
                        break;
                }
 
                /* Divide factor out until none are left. */
                do {

-                       (void)printf(" %lu", *fact);
-                       val /= (long)*fact;
-               } while ((val % (long)*fact) == 0);
+                       printf(" %lu", *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. */
 
                /* Let the user know we're doing something. */

-               (void)fflush(stdout);
+               fflush(stdout);

        }
        }

-       (void)putchar('\n');
+       putchar('\n');
+}
+
+/*
+ * Sigh..  No _decimal_ output to file functions in BN.
+ */
+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, buf);
+       free(buf);

 }
 
 void
 }
 
 void

-usage()
+usage(void)

 {
 {

-       (void)fprintf(stderr, "usage: factor [value ...]\n");
+       fprintf(stderr, "usage: factor [value ...]\n");

        exit (0);
 }
        exit (0);
 }

+
+
+
+
+#ifdef HAVE_OPENSSL
+/* pollard rho, algorithm from Jim Gillogly, May 2000 */
+
+void
+pollard_pminus1(BIGNUM *val)
+{
+       BIGNUM *base, *num, *i, *x;
+
+       base = BN_new();
+       num = BN_new();
+       i = BN_new();
+       x = BN_new();
+
+       BN_set_word(i, 2);
+       BN_set_word(base, 2);
+
+       for (;;) {
+               BN_mod_exp(base, base, i, val, ctx);
+
+               BN_copy(x, base);
+               BN_sub_word(x, 1);
+               BN_gcd(x, x, val, ctx);
+
+               if (!BN_is_one(x)) {
+                       if (BN_is_prime(x, PRIME_CHECKS, NULL, NULL,
+                           NULL) == 1) {
+                               putchar(' ');
+                               BN_print_dec_fp(stdout, 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) {
+                               putchar(' ');
+                               BN_print_dec_fp(stdout, num);
+                               fflush(stdout);
+                               return;
+                       }
+                       BN_copy(val, num);
+               }
+               BN_add_word(i, 1);
+       }
+}
+#else
+char *
+BN_bn2dec(const BIGNUM *val)
+{
+       char *buf;
+
+       buf = malloc(100);
+       if (!buf)
+               return buf;
+       snprintf(buf, 100, "%ld", (long)*val);
+       return buf;
+}
+
+BN_ULONG
+BN_div_word(BIGNUM *a, BN_ULONG b)
+{
+       BN_ULONG mod;
+
+       mod = *a % b;
+       *a /= b;
+       return mod;
+}
+#endif