-/* $NetBSD: factor.c,v 1.33 2020/10/05 14:31:30 christos Exp $ */
+/* $NetBSD: factor.c,v 1.38 2020/10/12 13:54:51 christos Exp $ */
/*
* Copyright (c) 1989, 1993
* The Regents of the University of California. All rights reserved.
__SCCSID("@(#)factor.c 8.4 (Berkeley) 5/4/95");
#endif
#ifdef __RCSID
-__RCSID("$NetBSD: factor.c,v 1.33 2020/10/05 14:31:30 christos Exp $");
+__RCSID("$NetBSD: factor.c,v 1.38 2020/10/12 13:54:51 christos Exp $");
#endif
#ifdef __FBSDID
__FBSDID("$FreeBSD: head/usr.bin/factor/factor.c 356666 2020-01-12 20:25:11Z gad $");
* If the -x flag is specified numbers are printed in hex.
*
* If no number 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 <ctype.h>
#define PRIME_CHECKS 5
-static void pollard_pminus1(BIGNUM *, int); /* print factors for big numbers */
+/* print factors for big numbers */
+static void pollard_pminus1(BIGNUM *, int, int);
#else
#define BN_CTX int
#define BN_CTX_new() NULL
-#define BN_new() ((BIGNUM *)calloc(sizeof(BIGNUM), 1))
+#define BN_new() calloc(sizeof(BIGNUM), 1)
+#define BN_free(a) free(a)
+
+#define BN_copy(a, b) *(a) = *(b)
+#define BN_cmp(a, b) (*(a) - *(b))
#define BN_is_zero(v) (*(v) == 0)
#define BN_is_one(v) (*(v) == 1)
#define BN_mod_word(a, b) (*(a) % (b))
+static BIGNUM *BN_dup(const BIGNUM *);
static int BN_dec2bn(BIGNUM **, const char *);
static int BN_hex2bn(BIGNUM **, const char *);
static BN_ULONG BN_div_word(BIGNUM *, BN_ULONG);
static void BN_print_dec_fp(FILE *, const BIGNUM *);
static void convert_str2bn(BIGNUM **, char *);
-static bool is_hex_str(char *);
static void pr_fact(BIGNUM *, int, int); /* print factors of a value */
-static void pr_print(BIGNUM *, int); /* print a prime */
+static void pr_print(BIGNUM *, int, int); /* print a prime */
static void usage(void) __dead;
static BN_CTX *ctx; /* just use a global context */
exit(0);
}
+static void
+pr_exp(int i, int xflag)
+{
+ printf(xflag && i > 9 ? "^0x%x" : "^%d", i);
+}
+
+static void
+pr_uint64(uint64_t i, int xflag)
+{
+ printf(xflag ? " 0x%" PRIx64 : " %" PRIu64, i);
+}
+
/*
* pr_fact - print the factors of a number
*
} else
BN_print_dec_fp(stdout, val);
putchar(':');
+ fflush(stdout);
for (fact = &prime[0]; !BN_is_one(val); ++fact) {
/* Look for the smallest factor. */
do {
errx(1, "error in BN_sqr()");
if (BN_cmp(bnfact, val) > 0 ||
BN_is_prime_ex(val, PRIME_CHECKS, NULL, NULL) == 1)
- pr_print(val, xflag);
+ pr_print(val, hflag, xflag);
else
- pollard_pminus1(val, xflag);
+ pollard_pminus1(val, hflag, xflag);
#else
- pr_print(val, xflag);
+ pr_print(val, hflag, xflag);
#endif
+ pr_print(NULL, hflag, xflag);
break;
}
do {
i++;
if (!hflag)
- printf(xflag ? " 0x%" PRIx64 : " %" PRIu64,
- *fact);
+ pr_uint64(*fact, xflag);
BN_div_word(val, (BN_ULONG)*fact);
} while (BN_mod_word(val, (BN_ULONG)*fact) == 0);
if (hflag) {
- printf(xflag ? " 0x%" PRIx64 : " %" PRIu64, *fact);
+ pr_uint64(*fact, xflag);
if (i > 1)
- printf(xflag ? "^0x%x" : "^%d", i);
+ pr_exp(i, xflag);
}
/* Let the user know we're doing something. */
}
static void
-pr_print(BIGNUM *val, int xflag)
+pr_print(BIGNUM *val, int hflag, int xflag)
{
+ static BIGNUM *sval;
+ static int ex = 1;
+ BIGNUM *pval;
+
+ if (hflag) {
+ if (sval == NULL) {
+ sval = BN_dup(val);
+ return;
+ }
+
+ if (val != NULL && BN_cmp(val, sval) == 0) {
+ ex++;
+ return;
+ }
+ pval = sval;
+ } else if (val == NULL) {
+ return;
+ } else {
+ pval = val;
+ }
+
if (xflag) {
fputs(" 0x", stdout);
- BN_print_fp(stdout, val);
+ BN_print_fp(stdout, pval);
} else {
putchar(' ');
- BN_print_dec_fp(stdout, val);
+ BN_print_dec_fp(stdout, pval);
+ }
+
+ if (hflag) {
+ if (ex > 1)
+ pr_exp(ex, xflag);
+
+ if (val != NULL) {
+ BN_copy(sval, val);
+ } else {
+ BN_free(sval);
+ sval = NULL;
+ }
+ ex = 1;
}
}
static void
usage(void)
{
- fprintf(stderr, "usage: factor [-h] [value ...]\n");
+ fprintf(stderr, "Usage: %s [-hx] [value ...]\n", getprogname());
exit(1);
}
/* pollard p-1, algorithm from Jim Gillogly, May 2000 */
static void
-pollard_pminus1(BIGNUM *val, int xflag)
+pollard_pminus1(BIGNUM *val, int hflag, int xflag)
{
BIGNUM *base, *rbase, *num, *i, *x;
if (!BN_is_one(x)) {
if (BN_is_prime_ex(x, PRIME_CHECKS, NULL, NULL) == 1)
- pr_print(x, xflag);
+ pr_print(x, hflag, xflag);
else
- pollard_pminus1(x, xflag);
+ pollard_pminus1(x, hflag, xflag);
fflush(stdout);
BN_div(num, NULL, val, x, ctx);
return;
if (BN_is_prime_ex(num, PRIME_CHECKS, NULL,
NULL) == 1) {
- pr_print(num, xflag);
+ pr_print(num, hflag, xflag);
fflush(stdout);
return;
}
return mod;
}
-#endif
-
-/*
- * Scan the string from left-to-right to see if the longest substring
- * is a valid hexadecimal number.
- */
-static bool
-is_hex_str(char *str)
+static BIGNUM *
+BN_dup(const BIGNUM *a)
{
- char c, *p;
- bool saw_hex = false;
-
- for (p = str; *p; p++) {
- if (isdigit((unsigned char)*p))
- continue;
- c = tolower((unsigned char)*p);
- if (c >= 'a' && c <= 'f') {
- saw_hex = true;
- continue;
- }
- break; /* Not a hexadecimal digit. */
- }
- return saw_hex;
+ BIGNUM *b = BN_new();
+ BN_copy(b, a);
+ return b;
}
+#endif
+
/* Convert string pointed to by *str to a bignum. */
static void
convert_str2bn(BIGNUM **val, char *p)
if (*p == '0' && (p[1] == 'x' || p[1] == 'X')) {
n = BN_hex2bn(val, p + 2);
} else {
- n = is_hex_str(p) ? BN_hex2bn(val, p) : BN_dec2bn(val, p);
+ n = BN_dec2bn(val, p);
}
if (n == 0)
errx(1, "%s: illegal numeric format.", p);
git.ckatri.com / bsdgames-darwin.git / blobdiff