factor: new applet

thus far only able to factor up to ULLONG_MAX

function                                             old     new   delta
factor_main                                            -     378    +378
packed_usage                                       31427   31502     +75
applet_names                                        2590    2597      +7
applet_main                                         1500    1504      +4
------------------------------------------------------------------------------
(add/remove: 2/0 grow/shrink: 3/0 up/down: 464/0)             Total: 464 bytes

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>

2 files changed, 160 insertions, 0 deletions

diff --git a/coreutils/factor.c b/coreutils/factor.c
new file mode 100644
index 000000000..0f838a735
--- /dev/null
+++ b/coreutils/factor.c
@@ -0,0 +1,112 @@
+/*
+ * Copyright (C) 2017 Denys Vlasenko <vda.linux@googlemail.com>
+ *
+ * Licensed under GPLv2, see file LICENSE in this source tree.
+ */
+//config:config FACTOR
+//config:	bool "factor"
+//config:	default y
+//config:	help
+//config:	  factor factorizes integers
+
+//applet:IF_FACTOR(APPLET(factor, BB_DIR_USR_BIN, BB_SUID_DROP))
+
+//kbuild:lib-$(CONFIG_FACTOR) += factor.o
+
+//usage:#define factor_trivial_usage
+//usage:       "NUMBER..."
+//usage:#define factor_full_usage "\n\n"
+//usage:       "Print prime factors"
+
+#include "libbb.h"
+
+#if ULLONG_MAX == (UINT_MAX * UINT_MAX + 2 * UINT_MAX)
+/* "unsigned" is half as wide as ullong */
+typedef unsigned half_t;
+#define HALF_FMT ""
+#elif ULLONG_MAX == (ULONG_MAX * ULONG_MAX + 2 * ULONG_MAX)
+/* long is half as wide as ullong */
+typedef unsigned long half_t;
+#define HALF_FMT "l"
+#else
+#error Cant find an integer type which is half as wide as ullong
+#endif
+
+static void factorize(const char *numstr)
+{
+	unsigned long long N, factor2;
+	half_t factor;
+	unsigned count3;
+
+	/* Coreutils compat */
+	numstr = skip_whitespace(numstr);
+	if (*numstr == '+')
+		numstr++;
+
+	N = bb_strtoull(numstr, NULL, 10);
+	if (errno)
+		bb_show_usage();
+
+	printf("%llu:", N);
+
+	if (N < 4)
+		goto end;
+	while (!(N & 1)) {
+		printf(" 2");
+		N >>= 1;
+	}
+
+	count3 = 3;
+	factor = 3;
+	factor2 = 3 * 3;
+	for (;;) {
+		unsigned long long nfactor2;
+
+		while ((N % factor) == 0) {
+			N = N / factor;
+			printf(" %u"HALF_FMT"", factor);
+		}
+ next_factor:
+		/* (f + 2)^2 = f^2 + 4*f + 4 = f^2 + 4*(f+1) */
+		nfactor2 = factor2 + 4 * (factor + 1);
+		if (nfactor2 < factor2) /* overflow? */
+			break;
+		factor2 = nfactor2;
+		if (factor2 > N)
+			break;
+		factor += 2;
+		/* Rudimentary wheel sieving: skip multiples of 3:
+		 * Every third odd number is divisible by three and thus isn't a prime:
+		 * 5  7  9  11  13  15  17 19 21 23 25 27 29 31 33 35 37...
+		 * ^  ^     ^   ^       ^  ^     ^  _     ^  ^     _  ^ (^primes)
+		 */
+		--count3;
+		if (count3 == 0) {
+			count3 = 3;
+			goto next_factor;
+		}
+	}
+ end:
+	if (N > 1)
+		printf(" %llu", N);
+	bb_putchar('\n');
+}
+
+int factor_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
+int factor_main(int argc UNUSED_PARAM, char **argv)
+{
+	//// coreutils has undocumented option ---debug (three dashes)
+	//getopt32(argv, "");
+	//argv += optind;
+	argv++;
+
+	if (!*argv)
+		//TODO: read from stdin
+		bb_show_usage();
+
+	do {
+		factorize(*argv);
+	} while (*++argv);
+
+	fflush_stdout_and_exit(EXIT_SUCCESS);
+}
diff --git a/testsuite/factor.tests b/testsuite/factor.tests
new file mode 100755
index 000000000..2cf4a54ce
--- /dev/null
+++ b/testsuite/factor.tests
@@ -0,0 +1,48 @@
+#!/bin/sh
+
+# Copyright 2017 by Denys Vlasenko <vda.linux@googlemail.com>
+# Licensed under GPLv2, see file LICENSE in this source tree.
+
+. ./testing.sh
+
+# testing "test name" "command" "expected result" "file input" "stdin"
+#   file input will be file called "input"
+#   test can create a file "actual" instead of writing to stdout
+
+testing "factor '  0'" \
+	"factor '  0'" \
+	"0:\n" \
+	"" ""
+testing "factor +1" \
+	"factor +1" \
+	"1:\n" \
+	"" ""
+testing "factor ' +2'" \
+	"factor ' +2'" \
+	"2: 2\n" \
+	"" ""
+
+testing "factor 1024" \
+	"factor 1024" \
+	"1024: 2 2 2 2 2 2 2 2 2 2\n" \
+	"" ""
+
+testing "factor 2^61-1" \
+	"factor 2305843009213693951" \
+	"2305843009213693951: 2305843009213693951\n" \
+	"" ""
+testing "factor 2^62-1" \
+	"factor 4611686018427387903" \
+	"4611686018427387903: 3 715827883 2147483647\n" \
+	"" ""
+testing "factor 2^64-1" \
+	"factor 18446744073709551615" \
+	"18446744073709551615: 3 5 17 257 641 65537 6700417\n" \
+	"" ""
+# This is a 60-bit number (0x888 86ff db34 4692): first few primes multiplied together:
+testing "factor \$((2*3*5*7*11*13*17*19*23*29*31*37*41*43*47))" \
+	"factor \$((2*3*5*7*11*13*17*19*23*29*31*37*41*43*47))" \
+	"614889782588491410: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47\n" \
+	"" ""
+
+exit $FAILCOUNT