build - Significantly improve parallel buildworld times
[dragonfly.git] / games / factor / factor.c
1 /*-
2  * Copyright (c) 1989, 1993
3  *      The Regents of the University of California.  All rights reserved.
4  *
5  * This code is derived from software contributed to Berkeley by
6  * Landon Curt Noll.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in the
15  *    documentation and/or other materials provided with the distribution.
16  * 3. Neither the name of the University nor the names of its contributors
17  *    may be used to endorse or promote products derived from this software
18  *    without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30  * SUCH DAMAGE.
31  *
32  * @(#) Copyright (c) 1989, 1993 The Regents of the University of California.  All rights reserved.
33  * @(#)factor.c 8.4 (Berkeley) 5/4/95
34  * $NetBSD: factor.c,v 1.13 2002/06/18 23:07:36 simonb Exp $
35  * $FreeBSD: src/games/factor/factor.c,v 1.9.2.2 2002/10/23 14:59:14 fanf Exp $
36  * $DragonFly: src/games/factor/factor.c,v 1.2 2003/06/17 04:25:23 dillon Exp $
37  */
38
39 /*
40  * factor - factor a number into primes
41  *
42  * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
43  *
44  *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
45  *
46  * usage:
47  *      factor [-h] [number] ...
48  *
49  * The form of the output is:
50  *
51  *      number: factor1 factor1 factor2 factor3 factor3 factor3 ...
52  *
53  * where factor1 < factor2 < factor3 < ...
54  *
55  * If no args are given, the list of numbers are read from stdin.
56  */
57
58 #include <ctype.h>
59 #include <err.h>
60 #include <errno.h>
61 #include <limits.h>
62 #include <stdio.h>
63 #include <stdlib.h>
64 #include <unistd.h>
65
66 #include "primes.h"
67
68 #ifdef HAVE_OPENSSL
69 #include <openssl/bn.h>
70 #define PRIME_CHECKS    5
71 static void     pollard_pminus1(BIGNUM *); /* print factors for big numbers */
72 #else
73 typedef ubig    BIGNUM;
74 typedef u_long  BN_ULONG;
75
76 #define BN_CTX                  int
77 #define BN_CTX_new()            NULL
78 #define BN_new()                ((BIGNUM *)calloc(sizeof(BIGNUM), 1))
79 #define BN_is_zero(v)           (*(v) == 0)
80 #define BN_is_one(v)            (*(v) == 1)
81 #define BN_mod_word(a, b)       (*(a) % (b))
82
83 static int      BN_dec2bn(BIGNUM **a, const char *str);
84 static int      BN_hex2bn(BIGNUM **a, const char *str);
85 static BN_ULONG BN_div_word(BIGNUM *, BN_ULONG);
86 static void     BN_print_fp(FILE *, const BIGNUM *);
87 #endif
88
89 static void     BN_print_dec_fp(FILE *, const BIGNUM *);
90
91 static void     pr_fact(BIGNUM *);      /* print factors of a value */
92 static void     pr_print(BIGNUM *);     /* print a prime */
93 static void     usage(void);
94
95 static BN_CTX   *ctx;                   /* just use a global context */
96 static int      hflag;
97
98 int
99 main(int argc, char *argv[])
100 {
101         BIGNUM *val;
102         int ch;
103         char *p, buf[LINE_MAX];         /* > max number of digits. */
104
105         ctx = BN_CTX_new();
106         val = BN_new();
107         if (val == NULL)
108                 errx(1, "can't initialise bignum");
109
110         while ((ch = getopt(argc, argv, "h")) != -1)
111                 switch (ch) {
112                 case 'h':
113                         hflag++;
114                         break;
115                 case '?':
116                 default:
117                         usage();
118                 }
119         argc -= optind;
120         argv += optind;
121
122         /* No args supplied, read numbers from stdin. */
123         if (argc == 0)
124                 for (;;) {
125                         if (fgets(buf, sizeof(buf), stdin) == NULL) {
126                                 if (ferror(stdin))
127                                         err(1, "stdin");
128                                 exit (0);
129                         }
130                         for (p = buf; isblank(*p); ++p);
131                         if (*p == '\n' || *p == '\0')
132                                 continue;
133                         if (*p == '-')
134                                 errx(1, "negative numbers aren't permitted.");
135                         if (BN_dec2bn(&val, buf) == 0 &&
136                             BN_hex2bn(&val, buf) == 0)
137                                 errx(1, "%s: illegal numeric format.", buf);
138                         pr_fact(val);
139                 }
140         /* Factor the arguments. */
141         else
142                 for (; *argv != NULL; ++argv) {
143                         if (argv[0][0] == '-')
144                                 errx(1, "negative numbers aren't permitted.");
145                         if (BN_dec2bn(&val, argv[0]) == 0 &&
146                             BN_hex2bn(&val, argv[0]) == 0)
147                                 errx(1, "%s: illegal numeric format.", argv[0]);
148                         pr_fact(val);
149                 }
150         exit(0);
151 }
152
153 /*
154  * pr_fact - print the factors of a number
155  *
156  * Print the factors of the number, from the lowest to the highest.
157  * A factor will be printed multiple times if it divides the value
158  * multiple times.
159  *
160  * Factors are printed with leading tabs.
161  */
162 static void
163 pr_fact(BIGNUM *val)
164 {
165         const ubig *fact;       /* The factor found. */
166
167         /* Firewall - catch 0 and 1. */
168         if (BN_is_zero(val))    /* Historical practice; 0 just exits. */
169                 exit(0);
170         if (BN_is_one(val)) {
171                 printf("1: 1\n");
172                 return;
173         }
174
175         /* Factor value. */
176
177         if (hflag) {
178                 fputs("0x", stdout);
179                 BN_print_fp(stdout, val);
180         } else
181                 BN_print_dec_fp(stdout, val);
182         putchar(':');
183         for (fact = &prime[0]; !BN_is_one(val); ++fact) {
184                 /* Look for the smallest factor. */
185                 do {
186                         if (BN_mod_word(val, (BN_ULONG)*fact) == 0)
187                                 break;
188                 } while (++fact <= pr_limit);
189
190                 /* Watch for primes larger than the table. */
191                 if (fact > pr_limit) {
192 #ifdef HAVE_OPENSSL
193                         BIGNUM *bnfact;
194
195                         bnfact = BN_new();
196                         BN_set_word(bnfact, *(fact - 1));
197                         BN_sqr(bnfact, bnfact, ctx);
198                         if (BN_cmp(bnfact, val) > 0)
199                                 pr_print(val);
200                         else
201                                 pollard_pminus1(val);
202 #else
203                         pr_print(val);
204 #endif
205                         break;
206                 }
207
208                 /* Divide factor out until none are left. */
209                 do {
210                         printf(hflag ? " 0x%lx" : " %lu", *fact);
211                         BN_div_word(val, (BN_ULONG)*fact);
212                 } while (BN_mod_word(val, (BN_ULONG)*fact) == 0);
213
214                 /* Let the user know we're doing something. */
215                 fflush(stdout);
216         }
217         putchar('\n');
218 }
219
220 static void
221 pr_print(BIGNUM *val)
222 {
223         if (hflag) {
224                 fputs(" 0x", stdout);
225                 BN_print_fp(stdout, val);
226         } else {
227                 putchar(' ');
228                 BN_print_dec_fp(stdout, val);
229         }
230 }
231
232 static void
233 usage(void)
234 {
235         fprintf(stderr, "usage: factor [-h] [value ...]\n");
236         exit(1);
237 }
238
239 #ifdef HAVE_OPENSSL
240
241 /* pollard p-1, algorithm from Jim Gillogly, May 2000 */
242 static void
243 pollard_pminus1(BIGNUM *val)
244 {
245         BIGNUM *base, *num, *i, *x;
246
247         base = BN_new();
248         num = BN_new();
249         i = BN_new();
250         x = BN_new();
251
252         BN_set_word(i, 2);
253         BN_set_word(base, 2);
254
255         for (;;) {
256                 BN_mod_exp(base, base, i, val, ctx);
257
258                 BN_copy(x, base);
259                 BN_sub_word(x, 1);
260                 BN_gcd(x, x, val, ctx);
261
262                 if (!BN_is_one(x)) {
263                         if (BN_is_prime(x, PRIME_CHECKS, NULL, NULL,
264                             NULL) == 1)
265                                 pr_print(x);
266                         else
267                                 pollard_pminus1(x);
268                         fflush(stdout);
269
270                         BN_div(num, NULL, val, x, ctx);
271                         if (BN_is_one(num))
272                                 return;
273                         if (BN_is_prime(num, PRIME_CHECKS, NULL, NULL,
274                             NULL) == 1) {
275                                 pr_print(num);
276                                 fflush(stdout);
277                                 return;
278                         }
279                         BN_copy(val, num);
280                 }
281                 BN_add_word(i, 1);
282         }
283 }
284
285 /*
286  * Sigh..  No _decimal_ output to file functions in BN.
287  */
288 static void
289 BN_print_dec_fp(FILE *fp, const BIGNUM *num)
290 {
291         char *buf;
292
293         buf = BN_bn2dec(num);
294         if (buf == NULL)
295                 return; /* XXX do anything here? */
296         fprintf(fp, buf);
297         free(buf);
298 }
299
300 #else
301
302 static void
303 BN_print_fp(FILE *fp, const BIGNUM *num)
304 {
305         fprintf(fp, "%lx", (unsigned long)*num);
306 }
307
308 static void
309 BN_print_dec_fp(FILE *fp, const BIGNUM *num)
310 {
311         fprintf(fp, "%lu", (unsigned long)*num);
312 }
313
314 static int
315 BN_dec2bn(BIGNUM **a, const char *str)
316 {
317         char *p;
318
319         errno = 0;
320         **a = strtoul(str, &p, 10);
321         return (errno == 0 && (*p == '\n' || *p == '\0'));
322 }
323
324 static int
325 BN_hex2bn(BIGNUM **a, const char *str)
326 {
327         char *p;
328
329         errno = 0;
330         **a = strtoul(str, &p, 16);
331         return (errno == 0 && (*p == '\n' || *p == '\0'));
332 }
333
334 static BN_ULONG
335 BN_div_word(BIGNUM *a, BN_ULONG b)
336 {
337         BN_ULONG mod;
338
339         mod = *a % b;
340         *a /= b;
341         return mod;
342 }
343
344 #endif