123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273 |
- #include "libbb.h"
- #include "common_bufsiz.h"
- #if 0
- # define dbg(...) bb_error_msg(__VA_ARGS__)
- #else
- # define dbg(...) ((void)0)
- #endif
- typedef unsigned long long wide_t;
- #if ULLONG_MAX == (UINT_MAX * UINT_MAX + 2 * UINT_MAX)
- typedef unsigned half_t;
- #define HALF_MAX UINT_MAX
- #define HALF_FMT ""
- #elif ULLONG_MAX == (ULONG_MAX * ULONG_MAX + 2 * ULONG_MAX)
- typedef unsigned long half_t;
- #define HALF_MAX ULONG_MAX
- #define HALF_FMT "l"
- #else
- #error Cant find an integer type which is half as wide as ullong
- #endif
- #define R(a,b,c,d,e,f,g,h,i,j,A,B,C,D,E,F,G,H,I,J,x) \
- (((uint64_t)(a<<0) | (b<<3) | (c<<6) | (d<<9) | (e<<12) | (f<<15) | (g<<18) | (h<<21) | (i<<24) | (j<<27)) << 1) | \
- (((uint64_t)(A<<0) | (B<<3) | (C<<6) | (D<<9) | (E<<12) | (F<<15) | (G<<18) | (H<<21) | (I<<24) | (J<<27)) << 31) | \
- ((uint64_t)x << 61)
- #define P(a,b,c,d,e,f,g,h,i,j,A,B,C,D,E,F,G,H,I,J,x) \
- R( (a/2),(b/2),(c/2),(d/2),(e/2),(f/2),(g/2),(h/2),(i/2),(j/2), \
- (A/2),(B/2),(C/2),(D/2),(E/2),(F/2),(G/2),(H/2),(I/2),(J/2), \
- (x/2) \
- )
- static const uint64_t packed_wheel[] = {
-
- P( 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6),
- P( 8, 4, 2, 4, 2, 4,14, 4, 6, 2,10, 2, 6, 6, 4, 2, 4, 6, 2,10, 2),
- P( 4, 2,12,10, 2, 4, 2, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4),
- P( 6, 8, 4, 2, 4, 6, 8, 6,10, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6),
- P( 4, 2, 6,10, 2,10, 2, 4, 2, 4, 6, 8, 4, 2, 4,12, 2, 6, 4, 2, 6),
- P( 4, 6,12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6,10, 2, 4, 6, 2),
- P( 6, 4, 2, 4, 2,10, 2,10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4),
- P( 2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2,10),
- P( 2, 6, 4, 2, 4, 2,10, 2,10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2),
- P( 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4),
- P( 2, 4, 6, 2, 6, 4, 2, 4, 2,10, 2,10, 2, 6, 4, 6, 2, 6, 4, 2, 4),
- P( 6, 6, 8, 4, 2, 6,10, 8, 4, 2, 4, 2, 4, 8,10, 6, 2, 4, 8, 6, 6),
- P( 4, 2, 4, 6, 2, 6, 4, 6, 2,10, 2,10, 2, 4, 2, 4, 6, 2, 6, 4, 2),
- P( 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6),
- P( 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2,10, 2,10, 2, 4, 2, 4, 6, 2),
- P(10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 2),
- P( 4, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2,10, 2,10, 2, 4, 2, 4, 6),
- P( 2, 6, 4, 2,10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2,12, 6, 4),
- P( 6, 2, 4, 6, 2,12, 4, 2, 4, 8, 6, 4, 2, 4, 2,10, 2,10, 6, 2, 4),
- P( 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,10, 6, 8, 6, 4, 2, 4, 8, 6),
- P( 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 2, 4, 2,10,12, 2, 4),
- P( 2,10, 2, 6, 4, 2, 4, 6, 6, 2,10, 2, 6, 4,14, 4, 2, 4, 2, 4, 8),
- P( 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4,12, 2,12),
- };
- #undef P
- #undef R
- #define WHEEL_START 5
- #define WHEEL_SIZE (5 + 24 * 20)
- #define square_count (((uint8_t*)&bb_common_bufsiz1)[0])
- #define wheel_tab (((uint8_t*)&bb_common_bufsiz1) + 1)
- static void unpack_wheel(void)
- {
- int i;
- uint8_t *p;
- setup_common_bufsiz();
- wheel_tab[0] = 1;
- wheel_tab[1] = 2;
- p = &wheel_tab[2];
- for (i = 0; i < ARRAY_SIZE(packed_wheel); i++) {
- uint64_t v = packed_wheel[i];
- while ((v & 0xe) != 0) {
- *p = v & 0xe;
-
- p++;
- v >>= 3;
- }
-
- }
- }
- static NOINLINE void print_w(wide_t n)
- {
- unsigned rep = square_count;
- do
- printf(" %llu", n);
- while (--rep != 0);
- }
- static NOINLINE void print_h(half_t n)
- {
- print_w(n);
- }
- static void factorize(wide_t N);
- static half_t isqrt_odd(wide_t N)
- {
- half_t s = isqrt(N);
-
-
- if ((wide_t)s * s == N) {
-
- square_count *= 2;
- factorize(s);
-
- return 0;
- }
-
-
- s = (s - 1) | 1;
- return s;
- }
- static NOINLINE void factorize(wide_t N)
- {
- unsigned w;
- half_t factor;
- half_t max_factor;
- if (N < 4)
- goto end;
-
- max_factor = isqrt_odd(N);
- if (!max_factor)
- return;
- factor = 2;
- w = 0;
- for (;;) {
- half_t fw;
-
- while ((N % factor) == 0) {
- N = N / factor;
- print_h(factor);
- max_factor = isqrt_odd(N);
- if (!max_factor)
- return;
- }
- if (factor >= max_factor)
- break;
- fw = factor + wheel_tab[w];
- if (fw < factor)
- break;
- factor = fw;
- w++;
- if (w < WHEEL_SIZE)
- continue;
- w = WHEEL_START;
- }
- end:
- if (N > 1)
- print_w(N);
- bb_putchar('\n');
- }
- static void factorize_numstr(const char *numstr)
- {
- wide_t N;
-
- if (*numstr == '+')
- numstr++;
- N = bb_strtoull(numstr, NULL, 10);
- if (errno)
- bb_show_usage();
- printf("%llu:", N);
- square_count = 1;
- factorize(N);
- }
- int factor_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
- int factor_main(int argc UNUSED_PARAM, char **argv)
- {
- unpack_wheel();
-
-
-
- argv++;
- if (!*argv) {
-
- for (;;) {
- char *numstr, *line;
- line = xmalloc_fgetline(stdin);
- if (!line)
- return EXIT_SUCCESS;
- numstr = line;
- for (;;) {
- char *end;
- numstr = skip_whitespace(numstr);
- if (!numstr[0])
- break;
- end = skip_non_whitespace(numstr);
- if (*end != '\0')
- *end++ = '\0';
- factorize_numstr(numstr);
- numstr = end;
- }
- free(line);
- }
- }
- do {
-
- factorize_numstr(skip_whitespace(*argv));
- } while (*++argv);
- return EXIT_SUCCESS;
- }
|