src/seq.c

   1 /* seq - print sequence of numbers to standard output.
   2    Copyright (C) 1994-2015 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 Ulrich Drepper.  */
  18
  19 #include <config.h>
  20 #include <getopt.h>
  21 #include <stdio.h>
  22 #include <sys/types.h>
  23
  24 #include "system.h"
  25 #include "c-strtod.h"
  26 #include "error.h"
  27 #include "quote.h"
  28 #include "xstrtod.h"
  29
  30 /* Roll our own isfinite rather than using <math.h>, so that we don't
  31    have to worry about linking -lm just for isfinite.  */
  32 #ifndef isfinite
  33 # define isfinite(x) ((x) * 0 == 0)
  34 #endif
  35
  36 /* The official name of this program (e.g., no 'g' prefix).  */
  37 #define PROGRAM_NAME "seq"
  38
  39 #define AUTHORS proper_name ("Ulrich Drepper")
  40
  41 /* If true print all number with equal width.  */
  42 static bool equal_width;
  43
  44 /* The string used to separate two numbers.  */
  45 static char const *separator;
  46
  47 /* The string output after all numbers have been output.
  48    Usually "\n" or "\0".  */
  49 static char const terminator[] = "\n";
  50
  51 static struct option const long_options[] =
  52 {
  53   { "equal-width", no_argument, NULL, 'w'},
  54   { "format", required_argument, NULL, 'f'},
  55   { "separator", required_argument, NULL, 's'},
  56   {GETOPT_HELP_OPTION_DECL},
  57   {GETOPT_VERSION_OPTION_DECL},
  58   { NULL, 0, NULL, 0}
  59 };
  60
  61 void
  62 usage (int status)
  63 {
  64   if (status != EXIT_SUCCESS)
  65     emit_try_help ();
  66   else
  67     {
  68       printf (_("\
  69 Usage: %s [OPTION]... LAST\n\
  70   or:  %s [OPTION]... FIRST LAST\n\
  71   or:  %s [OPTION]... FIRST INCREMENT LAST\n\
  72 "), program_name, program_name, program_name);
  73       fputs (_("\
  74 Print numbers from FIRST to LAST, in steps of INCREMENT.\n\
  75 "), stdout);
  76
  77       emit_mandatory_arg_note ();
  78
  79       fputs (_("\
  80   -f, --format=FORMAT      use printf style floating-point FORMAT\n\
  81   -s, --separator=STRING   use STRING to separate numbers (default: \\n)\n\
  82   -w, --equal-width        equalize width by padding with leading zeroes\n\
  83 "), stdout);
  84       fputs (HELP_OPTION_DESCRIPTION, stdout);
  85       fputs (VERSION_OPTION_DESCRIPTION, stdout);
  86       fputs (_("\
  87 \n\
  88 If FIRST or INCREMENT is omitted, it defaults to 1.  That is, an\n\
  89 omitted INCREMENT defaults to 1 even when LAST is smaller than FIRST.\n\
  90 The sequence of numbers ends when the sum of the current number and\n\
  91 INCREMENT would become greater than LAST.\n\
  92 FIRST, INCREMENT, and LAST are interpreted as floating point values.\n\
  93 INCREMENT is usually positive if FIRST is smaller than LAST, and\n\
  94 INCREMENT is usually negative if FIRST is greater than LAST.\n\
  95 "), stdout);
  96       fputs (_("\
  97 FORMAT must be suitable for printing one argument of type 'double';\n\
  98 it defaults to %.PRECf if FIRST, INCREMENT, and LAST are all fixed point\n\
  99 decimal numbers with maximum precision PREC, and to %g otherwise.\n\
 100 "), stdout);
 101       emit_ancillary_info (PROGRAM_NAME);
 102     }
 103   exit (status);
 104 }
 105
 106 /* A command-line operand.  */
 107 struct operand
 108 {
 109   /* Its value, converted to 'long double'.  */
 110   long double value;
 111
 112   /* Its print width, if it were printed out in a form similar to its
 113      input form.  An input like "-.1" is treated like "-0.1", and an
 114      input like "1." is treated like "1", but otherwise widths are
 115      left alone.  */
 116   size_t width;
 117
 118   /* Number of digits after the decimal point, or INT_MAX if the
 119      number can't easily be expressed as a fixed-point number.  */
 120   int precision;
 121 };
 122 typedef struct operand operand;
 123
 124 /* Description of what a number-generating format will generate.  */
 125 struct layout
 126 {
 127   /* Number of bytes before and after the number.  */
 128   size_t prefix_len;
 129   size_t suffix_len;
 130 };
 131
 132 /* Read a long double value from the command line.
 133    Return if the string is correct else signal error.  */
 134
 135 static operand
 136 scan_arg (const char *arg)
 137 {
 138   operand ret;
 139
 140   if (! xstrtold (arg, NULL, &ret.value, c_strtold))
 141     {
 142       error (0, 0, _("invalid floating point argument: %s"), arg);
 143       usage (EXIT_FAILURE);
 144     }
 145
 146   /* We don't output spaces or '+' so don't include in width */
 147   while (isspace (to_uchar (*arg)) || *arg == '+')
 148     arg++;
 149
 150   ret.width = strlen (arg);
 151   ret.precision = INT_MAX;
 152
 153   if (! arg[strcspn (arg, "xX")] && isfinite (ret.value))
 154     {
 155       char const *decimal_point = strchr (arg, '.');
 156       if (! decimal_point)
 157         ret.precision = 0;
 158       else
 159         {
 160           size_t fraction_len = strcspn (decimal_point + 1, "eE");
 161           if (fraction_len <= INT_MAX)
 162             ret.precision = fraction_len;
 163           ret.width += (fraction_len == 0                      /* #.  -> #   */
 164                         ? -1
 165                         : (decimal_point == arg                /* .#  -> 0.# */
 166                            || ! ISDIGIT (decimal_point[-1]))); /* -.# -> 0.# */
 167         }
 168       char const *e = strchr (arg, 'e');
 169       if (! e)
 170         e = strchr (arg, 'E');
 171       if (e)
 172         {
 173           long exponent = strtol (e + 1, NULL, 10);
 174           ret.precision += exponent < 0 ? -exponent : 0;
 175           /* Don't account for e.... in the width since this is not output.  */
 176           ret.width -= strlen (arg) - (e - arg);
 177           /* Adjust the width as per the exponent.  */
 178           if (exponent < 0)
 179             {
 180               if (decimal_point)
 181                 {
 182                   if (e == decimal_point + 1) /* undo #. -> # above  */
 183                     ret.width++;
 184                 }
 185               else
 186                 ret.width++;
 187               exponent = -exponent;
 188             }
 189           ret.width += exponent;
 190         }
 191     }
 192
 193   return ret;
 194 }
 195
 196 /* If FORMAT is a valid printf format for a double argument, return
 197    its long double equivalent, allocated from dynamic storage, and
 198    store into *LAYOUT a description of the output layout; otherwise,
 199    report an error and exit.  */
 200
 201 static char const *
 202 long_double_format (char const *fmt, struct layout *layout)
 203 {
 204   size_t i;
 205   size_t prefix_len = 0;
 206   size_t suffix_len = 0;
 207   size_t length_modifier_offset;
 208   bool has_L;
 209
 210   for (i = 0; ! (fmt[i] == '%' && fmt[i + 1] != '%'); i += (fmt[i] == '%') + 1)
 211     {
 212       if (!fmt[i])
 213         error (EXIT_FAILURE, 0,
 214                _("format %s has no %% directive"), quote (fmt));
 215       prefix_len++;
 216     }
 217
 218   i++;
 219   i += strspn (fmt + i, "-+#0 '");
 220   i += strspn (fmt + i, "0123456789");
 221   if (fmt[i] == '.')
 222     {
 223       i++;
 224       i += strspn (fmt + i, "0123456789");
 225     }
 226
 227   length_modifier_offset = i;
 228   has_L = (fmt[i] == 'L');
 229   i += has_L;
 230   if (fmt[i] == '\0')
 231     error (EXIT_FAILURE, 0, _("format %s ends in %%"), quote (fmt));
 232   if (! strchr ("efgaEFGA", fmt[i]))
 233     error (EXIT_FAILURE, 0,
 234            _("format %s has unknown %%%c directive"), quote (fmt), fmt[i]);
 235
 236   for (i++; ; i += (fmt[i] == '%') + 1)
 237     if (fmt[i] == '%' && fmt[i + 1] != '%')
 238       error (EXIT_FAILURE, 0, _("format %s has too many %% directives"),
 239              quote (fmt));
 240     else if (fmt[i])
 241       suffix_len++;
 242     else
 243       {
 244         size_t format_size = i + 1;
 245         char *ldfmt = xmalloc (format_size + 1);
 246         memcpy (ldfmt, fmt, length_modifier_offset);
 247         ldfmt[length_modifier_offset] = 'L';
 248         strcpy (ldfmt + length_modifier_offset + 1,
 249                 fmt + length_modifier_offset + has_L);
 250         layout->prefix_len = prefix_len;
 251         layout->suffix_len = suffix_len;
 252         return ldfmt;
 253       }
 254 }
 255
 256 /* Actually print the sequence of numbers in the specified range, with the
 257    given or default stepping and format.  */
 258
 259 static void
 260 print_numbers (char const *fmt, struct layout layout,
 261                long double first, long double step, long double last)
 262 {
 263   bool out_of_range = (step < 0 ? first < last : last < first);
 264
 265   if (! out_of_range)
 266     {
 267       long double x = first;
 268       long double i;
 269
 270       for (i = 1; ; i++)
 271         {
 272           long double x0 = x;
 273           printf (fmt, x);
 274           if (out_of_range)
 275             break;
 276           x = first + i * step;
 277           out_of_range = (step < 0 ? x < last : last < x);
 278
 279           if (out_of_range)
 280             {
 281               /* If the number just past LAST prints as a value equal
 282                  to LAST, and prints differently from the previous
 283                  number, then print the number.  This avoids problems
 284                  with rounding.  For example, with the x86 it causes
 285                  "seq 0 0.000001 0.000003" to print 0.000003 instead
 286                  of stopping at 0.000002.  */
 287
 288               bool print_extra_number = false;
 289               long double x_val;
 290               char *x_str;
 291               int x_strlen;
 292               setlocale (LC_NUMERIC, "C");
 293               x_strlen = asprintf (&x_str, fmt, x);
 294               setlocale (LC_NUMERIC, "");
 295               if (x_strlen < 0)
 296                 xalloc_die ();
 297               x_str[x_strlen - layout.suffix_len] = '\0';
 298
 299               if (xstrtold (x_str + layout.prefix_len, NULL, &x_val, c_strtold)
 300                   && x_val == last)
 301                 {
 302                   char *x0_str = NULL;
 303                   if (asprintf (&x0_str, fmt, x0) < 0)
 304                     xalloc_die ();
 305                   print_extra_number = !STREQ (x0_str, x_str);
 306                   free (x0_str);
 307                 }
 308
 309               free (x_str);
 310               if (! print_extra_number)
 311                 break;
 312             }
 313
 314           fputs (separator, stdout);
 315         }
 316
 317       fputs (terminator, stdout);
 318     }
 319 }
 320
 321 /* Return the default format given FIRST, STEP, and LAST.  */
 322 static char const *
 323 get_default_format (operand first, operand step, operand last)
 324 {
 325   static char format_buf[sizeof "%0.Lf" + 2 * INT_STRLEN_BOUND (int)];
 326
 327   int prec = MAX (first.precision, step.precision);
 328
 329   if (prec != INT_MAX && last.precision != INT_MAX)
 330     {
 331       if (equal_width)
 332         {
 333           /* increase first_width by any increased precision in step */
 334           size_t first_width = first.width + (prec - first.precision);
 335           /* adjust last_width to use precision from first/step */
 336           size_t last_width = last.width + (prec - last.precision);
 337           if (last.precision && prec == 0)
 338             last_width--;  /* don't include space for '.' */
 339           if (last.precision == 0 && prec)
 340             last_width++;  /* include space for '.' */
 341           if (first.precision == 0 && prec)
 342             first_width++;  /* include space for '.' */
 343           size_t width = MAX (first_width, last_width);
 344           if (width <= INT_MAX)
 345             {
 346               int w = width;
 347               sprintf (format_buf, "%%0%d.%dLf", w, prec);
 348               return format_buf;
 349             }
 350         }
 351       else
 352         {
 353           sprintf (format_buf, "%%.%dLf", prec);
 354           return format_buf;
 355         }
 356     }
 357
 358   return "%Lg";
 359 }
 360
 361 /* The NUL-terminated string S0 of length S_LEN represents a valid
 362    non-negative decimal integer.  Adjust the string and length so
 363    that the pair describe the next-larger value.  */
 364 static void
 365 incr (char **s0, size_t *s_len)
 366 {
 367   char *s = *s0;
 368   char *endp = s + *s_len - 1;
 369
 370   do
 371     {
 372       if ((*endp)++ < '9')
 373         return;
 374       *endp-- = '0';
 375     }
 376   while (endp >= s);
 377   *--(*s0) = '1';
 378   ++*s_len;
 379 }
 380
 381 /* Compare A and B (each a NUL-terminated digit string), with lengths
 382    given by A_LEN and B_LEN.  Return +1 if A < B, -1 if B < A, else 0.  */
 383 static int
 384 cmp (char const *a, size_t a_len, char const *b, size_t b_len)
 385 {
 386   if (a_len < b_len)
 387     return -1;
 388   if (b_len < a_len)
 389     return 1;
 390   return (strcmp (a, b));
 391 }
 392
 393 /* Trim leading 0's from S, but if S is all 0's, leave one.
 394    Return a pointer to the trimmed string.  */
 395 static char const * _GL_ATTRIBUTE_PURE
 396 trim_leading_zeros (char const *s)
 397 {
 398   char const *p = s;
 399   while (*s == '0')
 400     ++s;
 401
 402   /* If there were only 0's, back up, to leave one.  */
 403   if (!*s && s != p)
 404     --s;
 405   return s;
 406 }
 407
 408 /* Print all whole numbers from A to B, inclusive -- to stdout, each
 409    followed by a newline.  If B < A, return false and print nothing.
 410    Otherwise, return true.  */
 411 static bool
 412 seq_fast (char const *a, char const *b)
 413 {
 414   /* Skip past any leading 0's.  Without this, our naive cmp
 415      function would declare 000 to be larger than 99.  */
 416   a = trim_leading_zeros (a);
 417   b = trim_leading_zeros (b);
 418
 419   size_t p_len = strlen (a);
 420   size_t q_len = strlen (b);
 421   size_t n = MAX (p_len, q_len);
 422   char *p0 = xmalloc (n + 1);
 423   char *p = memcpy (p0 + n - p_len, a, p_len + 1);
 424   char *q0 = xmalloc (n + 1);
 425   char *q = memcpy (q0 + n - q_len, b, q_len + 1);
 426
 427   bool ok = cmp (p, p_len, q, q_len) <= 0;
 428   if (ok)
 429     {
 430       /* Buffer at least this many numbers per fwrite call.
 431          This gives a speed-up of more than 2x over the unbuffered code
 432          when printing the first 10^9 integers.  */
 433       enum {N = 40};
 434       char *buf = xmalloc (N * (n + 1));
 435       char const *buf_end = buf + N * (n + 1);
 436
 437       char *z = buf;
 438
 439       /* Write first number to buffer.  */
 440       z = mempcpy (z, p, p_len);
 441
 442       /* Append separator then number.  */
 443       while (cmp (p, p_len, q, q_len) < 0)
 444         {
 445           *z++ = *separator;
 446           incr (&p, &p_len);
 447           z = mempcpy (z, p, p_len);
 448           /* If no place for another separator + number then
 449              output buffer so far, and reset to start of buffer.  */
 450           if (buf_end - (n + 1) < z)
 451             {
 452               fwrite (buf, z - buf, 1, stdout);
 453               z = buf;
 454             }
 455         }
 456
 457       /* Write any remaining buffered output, and the terminator.  */
 458       *z++ = *terminator;
 459       fwrite (buf, z - buf, 1, stdout);
 460
 461       IF_LINT (free (buf));
 462     }
 463
 464   free (p0);
 465   free (q0);
 466   return ok;
 467 }
 468
 469 /* Return true if S consists of at least one digit and no non-digits.  */
 470 static bool _GL_ATTRIBUTE_PURE
 471 all_digits_p (char const *s)
 472 {
 473   size_t n = strlen (s);
 474   return ISDIGIT (s[0]) && n == strspn (s, "0123456789");
 475 }
 476
 477 int
 478 main (int argc, char **argv)
 479 {
 480   int optc;
 481   operand first = { 1, 1, 0 };
 482   operand step = { 1, 1, 0 };
 483   operand last;
 484   struct layout layout = { 0, 0 };
 485
 486   /* The printf(3) format used for output.  */
 487   char const *format_str = NULL;
 488
 489   initialize_main (&argc, &argv);
 490   set_program_name (argv[0]);
 491   setlocale (LC_ALL, "");
 492   bindtextdomain (PACKAGE, LOCALEDIR);
 493   textdomain (PACKAGE);
 494
 495   atexit (close_stdout);
 496
 497   equal_width = false;
 498   separator = "\n";
 499
 500   /* We have to handle negative numbers in the command line but this
 501      conflicts with the command line arguments.  So explicitly check first
 502      whether the next argument looks like a negative number.  */
 503   while (optind < argc)
 504     {
 505       if (argv[optind][0] == '-'
 506           && ((optc = argv[optind][1]) == '.' || ISDIGIT (optc)))
 507         {
 508           /* means negative number */
 509           break;
 510         }
 511
 512       optc = getopt_long (argc, argv, "+f:s:w", long_options, NULL);
 513       if (optc == -1)
 514         break;
 515
 516       switch (optc)
 517         {
 518         case 'f':
 519           format_str = optarg;
 520           break;
 521
 522         case 's':
 523           separator = optarg;
 524           break;
 525
 526         case 'w':
 527           equal_width = true;
 528           break;
 529
 530         case_GETOPT_HELP_CHAR;
 531
 532         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 533
 534         default:
 535           usage (EXIT_FAILURE);
 536         }
 537     }
 538
 539   unsigned int n_args = argc - optind;
 540   if (n_args < 1)
 541     {
 542       error (0, 0, _("missing operand"));
 543       usage (EXIT_FAILURE);
 544     }
 545
 546   if (3 < n_args)
 547     {
 548       error (0, 0, _("extra operand %s"), quote (argv[optind + 3]));
 549       usage (EXIT_FAILURE);
 550     }
 551
 552   if (format_str)
 553     format_str = long_double_format (format_str, &layout);
 554
 555   if (format_str != NULL && equal_width)
 556     {
 557       error (0, 0, _("format string may not be specified"
 558                      " when printing equal width strings"));
 559       usage (EXIT_FAILURE);
 560     }
 561
 562   /* If the following hold:
 563      - no format string, [FIXME: relax this, eventually]
 564      - integer start (or no start)
 565      - integer end
 566      - increment == 1 or not specified [FIXME: relax this, eventually]
 567      then use the much more efficient integer-only code.  */
 568   if (all_digits_p (argv[optind])
 569       && (n_args == 1 || all_digits_p (argv[optind + 1]))
 570       && (n_args < 3 || (STREQ ("1", argv[optind + 1])
 571                          && all_digits_p (argv[optind + 2])))
 572       && !equal_width && !format_str && strlen (separator) == 1)
 573     {
 574       char const *s1 = n_args == 1 ? "1" : argv[optind];
 575       char const *s2 = argv[optind + (n_args - 1)];
 576       if (seq_fast (s1, s2))
 577         return EXIT_SUCCESS;
 578
 579       /* Upon any failure, let the more general code deal with it.  */
 580     }
 581
 582   last = scan_arg (argv[optind++]);
 583
 584   if (optind < argc)
 585     {
 586       first = last;
 587       last = scan_arg (argv[optind++]);
 588
 589       if (optind < argc)
 590         {
 591           step = last;
 592           last = scan_arg (argv[optind++]);
 593         }
 594     }
 595
 596   if (first.precision == 0 && step.precision == 0 && last.precision == 0
 597       && 0 <= first.value && step.value == 1 && 0 <= last.value
 598       && !equal_width && !format_str && strlen (separator) == 1)
 599     {
 600       char *s1;
 601       char *s2;
 602       if (asprintf (&s1, "%0.Lf", first.value) < 0)
 603         xalloc_die ();
 604       if (asprintf (&s2, "%0.Lf", last.value) < 0)
 605         xalloc_die ();
 606
 607       if (*s1 != '-' && *s2 != '-' && seq_fast (s1, s2))
 608         {
 609           IF_LINT (free (s1));
 610           IF_LINT (free (s2));
 611           return EXIT_SUCCESS;
 612         }
 613
 614       free (s1);
 615       free (s2);
 616       /* Upon any failure, let the more general code deal with it.  */
 617     }
 618
 619   if (format_str == NULL)
 620     format_str = get_default_format (first, step, last);
 621
 622   print_numbers (format_str, layout, first.value, step.value, last.value);
 623
 624   return EXIT_SUCCESS;
 625 }