src/seq.c

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