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           size_t width = MAX (first_width, last_width);
 340           if (width <= INT_MAX)
 341             {
 342               int w = width;
 343               sprintf (format_buf, "%%0%d.%dLf", w, prec);
 344               return format_buf;
 345             }
 346         }
 347       else
 348         {
 349           sprintf (format_buf, "%%.%dLf", prec);
 350           return format_buf;
 351         }
 352     }
 353
 354   return "%Lg";
 355 }
 356
 357 /* The NUL-terminated string S0 of length S_LEN represents a valid
 358    non-negative decimal integer.  Adjust the string and length so
 359    that the pair describe the next-larger value.  */
 360 static void
 361 incr (char **s0, size_t *s_len)
 362 {
 363   char *s = *s0;
 364   char *endp = s + *s_len - 1;
 365
 366   do
 367     {
 368       if ((*endp)++ < '9')
 369         return;
 370       *endp-- = '0';
 371     }
 372   while (endp >= s);
 373   *--(*s0) = '1';
 374   ++*s_len;
 375 }
 376
 377 /* Compare A and B (each a NUL-terminated digit string), with lengths
 378    given by A_LEN and B_LEN.  Return +1 if A < B, -1 if B < A, else 0.  */
 379 static int
 380 cmp (char const *a, size_t a_len, char const *b, size_t b_len)
 381 {
 382   if (a_len < b_len)
 383     return -1;
 384   if (b_len < a_len)
 385     return 1;
 386   return (strcmp (a, b));
 387 }
 388
 389 /* Trim leading 0's from S, but if S is all 0's, leave one.
 390    Return a pointer to the trimmed string.  */
 391 static char const * _GL_ATTRIBUTE_PURE
 392 trim_leading_zeros (char const *s)
 393 {
 394   char const *p = s;
 395   while (*s == '0')
 396     ++s;
 397
 398   /* If there were only 0's, back up, to leave one.  */
 399   if (!*s && s != p)
 400     --s;
 401   return s;
 402 }
 403
 404 /* Print all whole numbers from A to B, inclusive -- to stdout, each
 405    followed by a newline.  If B < A, return false and print nothing.
 406    Otherwise, return true.  */
 407 static bool
 408 seq_fast (char const *a, char const *b)
 409 {
 410   /* Skip past any leading 0's.  Without this, our naive cmp
 411      function would declare 000 to be larger than 99.  */
 412   a = trim_leading_zeros (a);
 413   b = trim_leading_zeros (b);
 414
 415   size_t p_len = strlen (a);
 416   size_t q_len = strlen (b);
 417   size_t n = MAX (p_len, q_len);
 418   char *p0 = xmalloc (n + 1);
 419   char *p = memcpy (p0 + n - p_len, a, p_len + 1);
 420   char *q0 = xmalloc (n + 1);
 421   char *q = memcpy (q0 + n - q_len, b, q_len + 1);
 422
 423   bool ok = cmp (p, p_len, q, q_len) <= 0;
 424   if (ok)
 425     {
 426       /* Buffer at least this many numbers per fwrite call.
 427          This gives a speed-up of more than 2x over the unbuffered code
 428          when printing the first 10^9 integers.  */
 429       enum {N = 40};
 430       char *buf = xmalloc (N * (n + 1));
 431       char const *buf_end = buf + N * (n + 1);
 432
 433       char *z = buf;
 434
 435       /* Write first number to buffer.  */
 436       z = mempcpy (z, p, p_len);
 437
 438       /* Append separator then number.  */
 439       while (cmp (p, p_len, q, q_len) < 0)
 440         {
 441           *z++ = *separator;
 442           incr (&p, &p_len);
 443           z = mempcpy (z, p, p_len);
 444           /* If no place for another separator + number then
 445              output buffer so far, and reset to start of buffer.  */
 446           if (buf_end - (n + 1) < z)
 447             {
 448               fwrite (buf, z - buf, 1, stdout);
 449               z = buf;
 450             }
 451         }
 452
 453       /* Write any remaining buffered output, and the terminator.  */
 454       *z++ = *terminator;
 455       fwrite (buf, z - buf, 1, stdout);
 456
 457       IF_LINT (free (buf));
 458     }
 459
 460   free (p0);
 461   free (q0);
 462   return ok;
 463 }
 464
 465 /* Return true if S consists of at least one digit and no non-digits.  */
 466 static bool _GL_ATTRIBUTE_PURE
 467 all_digits_p (char const *s)
 468 {
 469   size_t n = strlen (s);
 470   return ISDIGIT (s[0]) && n == strspn (s, "0123456789");
 471 }
 472
 473 int
 474 main (int argc, char **argv)
 475 {
 476   int optc;
 477   operand first = { 1, 1, 0 };
 478   operand step = { 1, 1, 0 };
 479   operand last;
 480   struct layout layout = { 0, 0 };
 481
 482   /* The printf(3) format used for output.  */
 483   char const *format_str = NULL;
 484
 485   initialize_main (&argc, &argv);
 486   set_program_name (argv[0]);
 487   setlocale (LC_ALL, "");
 488   bindtextdomain (PACKAGE, LOCALEDIR);
 489   textdomain (PACKAGE);
 490
 491   atexit (close_stdout);
 492
 493   equal_width = false;
 494   separator = "\n";
 495
 496   /* We have to handle negative numbers in the command line but this
 497      conflicts with the command line arguments.  So explicitly check first
 498      whether the next argument looks like a negative number.  */
 499   while (optind < argc)
 500     {
 501       if (argv[optind][0] == '-'
 502           && ((optc = argv[optind][1]) == '.' || ISDIGIT (optc)))
 503         {
 504           /* means negative number */
 505           break;
 506         }
 507
 508       optc = getopt_long (argc, argv, "+f:s:w", long_options, NULL);
 509       if (optc == -1)
 510         break;
 511
 512       switch (optc)
 513         {
 514         case 'f':
 515           format_str = optarg;
 516           break;
 517
 518         case 's':
 519           separator = optarg;
 520           break;
 521
 522         case 'w':
 523           equal_width = true;
 524           break;
 525
 526         case_GETOPT_HELP_CHAR;
 527
 528         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 529
 530         default:
 531           usage (EXIT_FAILURE);
 532         }
 533     }
 534
 535   unsigned int n_args = argc - optind;
 536   if (n_args < 1)
 537     {
 538       error (0, 0, _("missing operand"));
 539       usage (EXIT_FAILURE);
 540     }
 541
 542   if (3 < n_args)
 543     {
 544       error (0, 0, _("extra operand %s"), quote (argv[optind + 3]));
 545       usage (EXIT_FAILURE);
 546     }
 547
 548   if (format_str)
 549     format_str = long_double_format (format_str, &layout);
 550
 551   if (format_str != NULL && equal_width)
 552     {
 553       error (0, 0, _("format string may not be specified"
 554                      " when printing equal width strings"));
 555       usage (EXIT_FAILURE);
 556     }
 557
 558   /* If the following hold:
 559      - no format string, [FIXME: relax this, eventually]
 560      - integer start (or no start)
 561      - integer end
 562      - increment == 1 or not specified [FIXME: relax this, eventually]
 563      then use the much more efficient integer-only code.  */
 564   if (all_digits_p (argv[optind])
 565       && (n_args == 1 || all_digits_p (argv[optind + 1]))
 566       && (n_args < 3 || STREQ ("1", argv[optind + 2]))
 567       && !equal_width && !format_str && strlen (separator) == 1)
 568     {
 569       char const *s1 = n_args == 1 ? "1" : argv[optind];
 570       char const *s2 = n_args == 1 ? argv[optind] : argv[optind + 1];
 571       if (seq_fast (s1, s2))
 572         exit (EXIT_SUCCESS);
 573
 574       /* Upon any failure, let the more general code deal with it.  */
 575     }
 576
 577   last = scan_arg (argv[optind++]);
 578
 579   if (optind < argc)
 580     {
 581       first = last;
 582       last = scan_arg (argv[optind++]);
 583
 584       if (optind < argc)
 585         {
 586           step = last;
 587           last = scan_arg (argv[optind++]);
 588         }
 589     }
 590
 591   if (first.precision == 0 && step.precision == 0 && last.precision == 0
 592       && 0 <= first.value && step.value == 1 && 0 <= last.value
 593       && !equal_width && !format_str && strlen (separator) == 1)
 594     {
 595       char *s1;
 596       char *s2;
 597       if (asprintf (&s1, "%0.Lf", first.value) < 0)
 598         xalloc_die ();
 599       if (asprintf (&s2, "%0.Lf", last.value) < 0)
 600         xalloc_die ();
 601
 602       if (seq_fast (s1, s2))
 603         {
 604           IF_LINT (free (s1));
 605           IF_LINT (free (s2));
 606           exit (EXIT_SUCCESS);
 607         }
 608
 609       free (s1);
 610       free (s2);
 611       /* Upon any failure, let the more general code deal with it.  */
 612     }
 613
 614   if (format_str == NULL)
 615     format_str = get_default_format (first, step, last);
 616
 617   print_numbers (format_str, layout, first.value, step.value, last.value);
 618
 619   exit (EXIT_SUCCESS);
 620 }