LCOV - code coverage report
Current view: top level - src - factor.c (source / functions) Hit Total Coverage
Test: coreutils.info Lines: 66 67 98.5 %
Date: 2018-01-30 Functions: 5 5 100.0 %

          Line data    Source code
       1             : /* factor -- print prime factors of n.
       2             :    Copyright (C) 86, 1995-2005, 2007 Free Software Foundation, Inc.
       3             : 
       4             :    This program is free software: you can redistribute it and/or modify
       5             :    it under the terms of the GNU General Public License as published by
       6             :    the Free Software Foundation, either version 3 of the License, or
       7             :    (at your option) any later version.
       8             : 
       9             :    This program is distributed in the hope that it will be useful,
      10             :    but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      12             :    GNU General Public License for more details.
      13             : 
      14             :    You should have received a copy of the GNU General Public License
      15             :    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
      16             : 
      17             : /* Written by Paul Rubin <phr@ocf.berkeley.edu>.
      18             :    Adapted for GNU, fixed to factor UINT_MAX by Jim Meyering.  */
      19             : 
      20             : #include <config.h>
      21             : #include <getopt.h>
      22             : #include <stdio.h>
      23             : #include <sys/types.h>
      24             : 
      25             : #include <assert.h>
      26             : #define NDEBUG 1
      27             : 
      28             : #include "system.h"
      29             : #include "error.h"
      30             : #include "inttostr.h"
      31             : #include "long-options.h"
      32             : #include "quote.h"
      33             : #include "readtokens.h"
      34             : #include "xstrtol.h"
      35             : 
      36             : /* The official name of this program (e.g., no `g' prefix).  */
      37             : #define PROGRAM_NAME "factor"
      38             : 
      39             : #define AUTHORS "Paul Rubin"
      40             : 
      41             : /* Token delimiters when reading from a file.  */
      42             : #define DELIM "\n\t "
      43             : 
      44             : /* The maximum number of factors, including -1, for negative numbers.  */
      45             : #define MAX_N_FACTORS (sizeof (uintmax_t) * CHAR_BIT)
      46             : 
      47             : /* The trial divisor increment wheel.  Use it to skip over divisors that
      48             :    are composites of 2, 3, 5, 7, or 11.  The part from WHEEL_START up to
      49             :    WHEEL_END is reused periodically, while the "lead in" is used to test
      50             :    for those primes and to jump onto the wheel.  For more information, see
      51             :    http://www.utm.edu/research/primes/glossary/WheelFactorization.html  */
      52             : 
      53             : #include "wheel-size.h"  /* For the definition of WHEEL_SIZE.  */
      54             : static const unsigned char wheel_tab[] =
      55             :   {
      56             : #include "wheel.h"
      57             :   };
      58             : 
      59             : #define WHEEL_START (wheel_tab + WHEEL_SIZE)
      60             : #define WHEEL_END (wheel_tab + (sizeof wheel_tab / sizeof wheel_tab[0]))
      61             : 
      62             : /* The name this program was run with. */
      63             : char *program_name;
      64             : 
      65             : void
      66           6 : usage (int status)
      67             : {
      68           6 :   if (status != EXIT_SUCCESS)
      69           5 :     fprintf (stderr, _("Try `%s --help' for more information.\n"),
      70             :              program_name);
      71             :   else
      72             :     {
      73           1 :       printf (_("\
      74             : Usage: %s [NUMBER]...\n\
      75             :   or:  %s OPTION\n\
      76             : "),
      77             :               program_name, program_name);
      78           1 :       fputs (_("\
      79             : Print the prime factors of each NUMBER.\n\
      80             : \n\
      81             : "), stdout);
      82           1 :       fputs (HELP_OPTION_DESCRIPTION, stdout);
      83           1 :       fputs (VERSION_OPTION_DESCRIPTION, stdout);
      84           1 :       fputs (_("\
      85             : \n\
      86             : Print the prime factors of all specified integer NUMBERs.  If no arguments\n\
      87             : are specified on the command line, they are read from standard input.\n\
      88             : "), stdout);
      89           1 :       emit_bug_reporting_address ();
      90             :     }
      91           6 :   exit (status);
      92             : }
      93             : 
      94             : /* FIXME: comment */
      95             : 
      96             : static size_t
      97          16 : factor (uintmax_t n0, size_t max_n_factors, uintmax_t *factors)
      98             : {
      99          16 :   uintmax_t n = n0, d, q;
     100          16 :   size_t n_factors = 0;
     101          16 :   unsigned char const *w = wheel_tab;
     102             : 
     103          16 :   if (n <= 1)
     104          11 :     return n_factors;
     105             : 
     106             :   /* The exit condition in the following loop is correct because
     107             :      any time it is tested one of these 3 conditions holds:
     108             :       (1) d divides n
     109             :       (2) n is prime
     110             :       (3) n is composite but has no factors less than d.
     111             :      If (1) or (2) obviously the right thing happens.
     112             :      If (3), then since n is composite it is >= d^2. */
     113             : 
     114           5 :   d = 2;
     115             :   do
     116             :     {
     117         514 :       q = n / d;
     118        1082 :       while (n == q * d)
     119             :         {
     120          54 :           assert (n_factors < max_n_factors);
     121          54 :           factors[n_factors++] = d;
     122          54 :           n = q;
     123          54 :           q = n / d;
     124             :         }
     125         514 :       d += *(w++);
     126         514 :       if (w == WHEEL_END)
     127           1 :         w = WHEEL_START;
     128             :     }
     129         514 :   while (d <= q);
     130             : 
     131           5 :   if (n != 1 || n0 == 1)
     132             :     {
     133           3 :       assert (n_factors < max_n_factors);
     134           3 :       factors[n_factors++] = n;
     135             :     }
     136             : 
     137           5 :   return n_factors;
     138             : }
     139             : 
     140             : /* FIXME: comment */
     141             : 
     142             : static bool
     143          82 : print_factors (const char *s)
     144             : {
     145             :   uintmax_t factors[MAX_N_FACTORS];
     146             :   uintmax_t n;
     147             :   size_t n_factors;
     148             :   size_t i;
     149             :   char buf[INT_BUFSIZE_BOUND (uintmax_t)];
     150             :   strtol_error err;
     151             : 
     152          82 :   if ((err = xstrtoumax (s, NULL, 10, &n, "")) != LONGINT_OK)
     153             :     {
     154          66 :       if (err == LONGINT_OVERFLOW)
     155           0 :         error (0, 0, _("%s is too large"), quote (s));
     156             :       else
     157          66 :         error (0, 0, _("%s is not a valid positive integer"), quote (s));
     158          66 :       return false;
     159             :     }
     160          16 :   n_factors = factor (n, MAX_N_FACTORS, factors);
     161          16 :   printf ("%s:", umaxtostr (n, buf));
     162          73 :   for (i = 0; i < n_factors; i++)
     163          57 :     printf (" %s", umaxtostr (factors[i], buf));
     164          16 :   putchar ('\n');
     165          16 :   return true;
     166             : }
     167             : 
     168             : static bool
     169           9 : do_stdin (void)
     170             : {
     171           9 :   bool ok = true;
     172             :   token_buffer tokenbuffer;
     173             : 
     174           9 :   init_tokenbuffer (&tokenbuffer);
     175             : 
     176             :   for (;;)
     177          15 :     {
     178          24 :       size_t token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,
     179             :                                        &tokenbuffer);
     180          24 :       if (token_length == (size_t) -1)
     181           9 :         break;
     182          15 :       ok &= print_factors (tokenbuffer.buffer);
     183             :     }
     184           9 :   free (tokenbuffer.buffer);
     185             : 
     186           9 :   return ok;
     187             : }
     188             : 
     189             : int
     190          49 : main (int argc, char **argv)
     191             : {
     192             :   bool ok;
     193             : 
     194             :   initialize_main (&argc, &argv);
     195          49 :   program_name = argv[0];
     196          49 :   setlocale (LC_ALL, "");
     197             :   bindtextdomain (PACKAGE, LOCALEDIR);
     198             :   textdomain (PACKAGE);
     199             : 
     200          49 :   atexit (close_stdout);
     201             : 
     202          49 :   parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE_NAME, VERSION,
     203             :                       usage, AUTHORS, (char const *) NULL);
     204          47 :   if (getopt_long (argc, argv, "", NULL, NULL) != -1)
     205           5 :     usage (EXIT_FAILURE);
     206             : 
     207          42 :   if (argc <= optind)
     208           9 :     ok = do_stdin ();
     209             :   else
     210             :     {
     211             :       int i;
     212          33 :       ok = true;
     213         100 :       for (i = optind; i < argc; i++)
     214          67 :         if (! print_factors (argv[i]))
     215          51 :           ok = false;
     216             :     }
     217             : 
     218          42 :   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
     219             : }

Generated by: LCOV version 1.10