ptx: prefer xpalloc to x2nrealloc
[coreutils.git] / src / seq.c
blobad16f27018403ba041cdf7b941fa26f9b75b2bad
1 /* seq - print sequence of numbers to standard output.
2 Copyright (C) 1994-2024 Free Software Foundation, Inc.
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.
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.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17 /* Written by Ulrich Drepper. */
19 #include <config.h>
20 #include <ctype.h>
21 #include <getopt.h>
22 #include <stdio.h>
23 #include <sys/types.h>
25 #include "system.h"
26 #include "cl-strtod.h"
27 #include "quote.h"
28 #include "xstrtod.h"
30 /* Roll our own isfinite/isnan 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 #ifndef isnan
36 # define isnan(x) ((x) != (x))
37 #endif
39 /* Limit below which seq_fast has more throughput.
40 Determined with: seq 0 200 inf | pv > /dev/null */
41 #define SEQ_FAST_STEP_LIMIT 200 /* Keep in sync with texinfo description. */
42 #define SEQ_FAST_STEP_LIMIT_DIGITS 3
44 /* The official name of this program (e.g., no 'g' prefix). */
45 #define PROGRAM_NAME "seq"
47 #define AUTHORS proper_name ("Ulrich Drepper")
49 /* True if the locale settings were honored. */
50 static bool locale_ok;
52 /* If true print all number with equal width. */
53 static bool equal_width;
55 /* The string used to separate two numbers. */
56 static char const *separator;
58 /* The string output after all numbers have been output.
59 Usually "\n" or "\0". */
60 static char const terminator[] = "\n";
62 static struct option const long_options[] =
64 { "equal-width", no_argument, nullptr, 'w'},
65 { "format", required_argument, nullptr, 'f'},
66 { "separator", required_argument, nullptr, 's'},
67 {GETOPT_HELP_OPTION_DECL},
68 {GETOPT_VERSION_OPTION_DECL},
69 { nullptr, 0, nullptr, 0}
72 void
73 usage (int status)
75 if (status != EXIT_SUCCESS)
76 emit_try_help ();
77 else
79 printf (_("\
80 Usage: %s [OPTION]... LAST\n\
81 or: %s [OPTION]... FIRST LAST\n\
82 or: %s [OPTION]... FIRST INCREMENT LAST\n\
83 "), program_name, program_name, program_name);
84 fputs (_("\
85 Print numbers from FIRST to LAST, in steps of INCREMENT.\n\
86 "), stdout);
88 emit_mandatory_arg_note ();
90 fputs (_("\
91 -f, --format=FORMAT use printf style floating-point FORMAT\n\
92 -s, --separator=STRING use STRING to separate numbers (default: \\n)\n\
93 -w, --equal-width equalize width by padding with leading zeroes\n\
94 "), stdout);
95 fputs (HELP_OPTION_DESCRIPTION, stdout);
96 fputs (VERSION_OPTION_DESCRIPTION, stdout);
97 fputs (_("\
98 \n\
99 If FIRST or INCREMENT is omitted, it defaults to 1. That is, an\n\
100 omitted INCREMENT defaults to 1 even when LAST is smaller than FIRST.\n\
101 The sequence of numbers ends when the sum of the current number and\n\
102 INCREMENT would become greater than LAST.\n\
103 FIRST, INCREMENT, and LAST are interpreted as floating point values.\n\
104 INCREMENT is usually positive if FIRST is smaller than LAST, and\n\
105 INCREMENT is usually negative if FIRST is greater than LAST.\n\
106 INCREMENT must not be 0; none of FIRST, INCREMENT and LAST may be NaN.\n\
107 "), stdout);
108 fputs (_("\
109 FORMAT must be suitable for printing one argument of type 'double';\n\
110 it defaults to %.PRECf if FIRST, INCREMENT, and LAST are all fixed point\n\
111 decimal numbers with maximum precision PREC, and to %g otherwise.\n\
112 "), stdout);
113 emit_ancillary_info (PROGRAM_NAME);
115 exit (status);
118 /* A command-line operand. */
119 struct operand
121 /* Its value, converted to 'long double'. */
122 long double value;
124 /* Its print width, if it were printed out in a form similar to its
125 input form. An input like "-.1" is treated like "-0.1", and an
126 input like "1." is treated like "1", but otherwise widths are
127 left alone. */
128 size_t width;
130 /* Number of digits after the decimal point, or INT_MAX if the
131 number can't easily be expressed as a fixed-point number. */
132 int precision;
134 typedef struct operand operand;
136 /* Description of what a number-generating format will generate. */
137 struct layout
139 /* Number of bytes before and after the number. */
140 size_t prefix_len;
141 size_t suffix_len;
144 /* Read a long double value from the command line.
145 Return if the string is correct else signal error. */
147 static operand
148 scan_arg (char const *arg)
150 operand ret;
152 if (! xstrtold (arg, nullptr, &ret.value, cl_strtold))
154 error (0, 0, _("invalid floating point argument: %s"), quote (arg));
155 usage (EXIT_FAILURE);
158 if (isnan (ret.value))
160 error (0, 0, _("invalid %s argument: %s"), quote_n (0, "not-a-number"),
161 quote_n (1, arg));
162 usage (EXIT_FAILURE);
165 /* We don't output spaces or '+' so don't include in width */
166 while (isspace (to_uchar (*arg)) || *arg == '+')
167 arg++;
169 /* Default to auto width and precision. */
170 ret.width = 0;
171 ret.precision = INT_MAX;
173 /* Use no precision (and possibly fast generation) for integers. */
174 char const *decimal_point = strchr (arg, '.');
175 if (! decimal_point && ! strchr (arg, 'p') /* not a hex float */)
176 ret.precision = 0;
178 /* auto set width and precision for decimal inputs. */
179 if (! arg[strcspn (arg, "xX")] && isfinite (ret.value))
181 size_t fraction_len = 0;
182 ret.width = strlen (arg);
184 if (decimal_point)
186 fraction_len = strcspn (decimal_point + 1, "eE");
187 if (fraction_len <= INT_MAX)
188 ret.precision = fraction_len;
189 ret.width += (fraction_len == 0 /* #. -> # */
190 ? -1
191 : (decimal_point == arg /* .# -> 0.# */
192 || ! ISDIGIT (decimal_point[-1]))); /* -.# -> 0.# */
194 char const *e = strchr (arg, 'e');
195 if (! e)
196 e = strchr (arg, 'E');
197 if (e)
199 long exponent = MAX (strtol (e + 1, nullptr, 10), -LONG_MAX);
200 ret.precision += exponent < 0 ? -exponent
201 : - MIN (ret.precision, exponent);
202 /* Don't account for e.... in the width since this is not output. */
203 ret.width -= strlen (arg) - (e - arg);
204 /* Adjust the width as per the exponent. */
205 if (exponent < 0)
207 if (decimal_point)
209 if (e == decimal_point + 1) /* undo #. -> # above */
210 ret.width++;
212 else
213 ret.width++;
214 exponent = -exponent;
216 else
218 if (decimal_point && ret.precision == 0 && fraction_len)
219 ret.width--; /* discount space for '.' */
220 exponent -= MIN (fraction_len, exponent);
222 ret.width += exponent;
226 return ret;
229 /* If FORMAT is a valid printf format for a double argument, return
230 its long double equivalent, allocated from dynamic storage, and
231 store into *LAYOUT a description of the output layout; otherwise,
232 report an error and exit. */
234 static char const *
235 long_double_format (char const *fmt, struct layout *layout)
237 size_t i;
238 size_t prefix_len = 0;
239 size_t suffix_len = 0;
240 size_t length_modifier_offset;
241 bool has_L;
243 for (i = 0; ! (fmt[i] == '%' && fmt[i + 1] != '%'); i += (fmt[i] == '%') + 1)
245 if (!fmt[i])
246 error (EXIT_FAILURE, 0,
247 _("format %s has no %% directive"), quote (fmt));
248 prefix_len++;
251 i++;
252 i += strspn (fmt + i, "-+#0 '");
253 i += strspn (fmt + i, "0123456789");
254 if (fmt[i] == '.')
256 i++;
257 i += strspn (fmt + i, "0123456789");
260 length_modifier_offset = i;
261 has_L = (fmt[i] == 'L');
262 i += has_L;
263 if (fmt[i] == '\0')
264 error (EXIT_FAILURE, 0, _("format %s ends in %%"), quote (fmt));
265 if (! strchr ("efgaEFGA", fmt[i]))
266 error (EXIT_FAILURE, 0,
267 _("format %s has unknown %%%c directive"), quote (fmt), fmt[i]);
269 for (i++; ; i += (fmt[i] == '%') + 1)
270 if (fmt[i] == '%' && fmt[i + 1] != '%')
271 error (EXIT_FAILURE, 0, _("format %s has too many %% directives"),
272 quote (fmt));
273 else if (fmt[i])
274 suffix_len++;
275 else
277 size_t format_size = i + 1;
278 char *ldfmt = xmalloc (format_size + 1);
279 memcpy (ldfmt, fmt, length_modifier_offset);
280 ldfmt[length_modifier_offset] = 'L';
281 strcpy (ldfmt + length_modifier_offset + 1,
282 fmt + length_modifier_offset + has_L);
283 layout->prefix_len = prefix_len;
284 layout->suffix_len = suffix_len;
285 return ldfmt;
289 /* Actually print the sequence of numbers in the specified range, with the
290 given or default stepping and format. */
292 static void
293 print_numbers (char const *fmt, struct layout layout,
294 long double first, long double step, long double last)
296 bool out_of_range = (step < 0 ? first < last : last < first);
298 if (! out_of_range)
300 long double x = first;
301 long double i;
303 for (i = 1; ; i++)
305 long double x0 = x;
306 if (printf (fmt, x) < 0)
307 write_error ();
308 if (out_of_range)
309 break;
311 /* Mathematically equivalent to 'x += step;', and typically
312 less subject to rounding error. */
313 x = first + i * step;
315 out_of_range = (step < 0 ? x < last : last < x);
317 if (out_of_range)
319 /* If the number just past LAST prints as a value equal
320 to LAST, and prints differently from the previous
321 number, then print the number. This avoids problems
322 with rounding. For example, with the x86 it causes
323 "seq 0 0.000001 0.000003" to print 0.000003 instead
324 of stopping at 0.000002. */
326 bool print_extra_number = false;
327 long double x_val;
328 char *x_str;
329 int x_strlen;
330 if (locale_ok)
331 setlocale (LC_NUMERIC, "C");
332 x_strlen = asprintf (&x_str, fmt, x);
333 if (locale_ok)
334 setlocale (LC_NUMERIC, "");
335 if (x_strlen < 0)
336 xalloc_die ();
337 x_str[x_strlen - layout.suffix_len] = '\0';
339 if (xstrtold (x_str + layout.prefix_len, nullptr,
340 &x_val, cl_strtold)
341 && x_val == last)
343 char *x0_str = nullptr;
344 int x0_strlen = asprintf (&x0_str, fmt, x0);
345 if (x0_strlen < 0)
346 xalloc_die ();
347 x0_str[x0_strlen - layout.suffix_len] = '\0';
348 print_extra_number = !STREQ (x0_str, x_str);
349 free (x0_str);
352 free (x_str);
353 if (! print_extra_number)
354 break;
357 if (fputs (separator, stdout) == EOF)
358 write_error ();
361 if (fputs (terminator, stdout) == EOF)
362 write_error ();
366 /* Return the default format given FIRST, STEP, and LAST. */
367 static char const *
368 get_default_format (operand first, operand step, operand last)
370 static char format_buf[sizeof "%0.Lf" + 2 * INT_STRLEN_BOUND (int)];
372 int prec = MAX (first.precision, step.precision);
374 if (prec != INT_MAX && last.precision != INT_MAX)
376 if (equal_width)
378 /* increase first_width by any increased precision in step */
379 size_t first_width = first.width + (prec - first.precision);
380 /* adjust last_width to use precision from first/step */
381 size_t last_width = last.width + (prec - last.precision);
382 if (last.precision && prec == 0)
383 last_width--; /* don't include space for '.' */
384 if (last.precision == 0 && prec)
385 last_width++; /* include space for '.' */
386 if (first.precision == 0 && prec)
387 first_width++; /* include space for '.' */
388 size_t width = MAX (first_width, last_width);
389 if (width <= INT_MAX)
391 int w = width;
392 sprintf (format_buf, "%%0%d.%dLf", w, prec);
393 return format_buf;
396 else
398 sprintf (format_buf, "%%.%dLf", prec);
399 return format_buf;
403 return "%Lg";
406 /* The NUL-terminated string S0 of length S_LEN represents a valid
407 non-negative decimal integer. Adjust the string and length so
408 that the pair describe the next-larger value. */
409 static void
410 incr (char **s0, size_t *s_len)
412 char *s = *s0;
413 char *endp = s + *s_len - 1;
417 if ((*endp)++ < '9')
418 return;
419 *endp-- = '0';
421 while (endp >= s);
422 *--(*s0) = '1';
423 ++*s_len;
426 /* Compare A and B (each a NUL-terminated digit string), with lengths
427 given by A_LEN and B_LEN. Return +1 if A < B, -1 if B < A, else 0. */
428 static int
429 cmp (char const *a, size_t a_len, char const *b, size_t b_len)
431 if (a_len < b_len)
432 return -1;
433 if (b_len < a_len)
434 return 1;
435 return (memcmp (a, b, a_len));
438 /* Trim leading 0's from S, but if S is all 0's, leave one.
439 Return a pointer to the trimmed string. */
440 ATTRIBUTE_PURE
441 static char const *
442 trim_leading_zeros (char const *s)
444 char const *p = s;
445 while (*s == '0')
446 ++s;
448 /* If there were only 0's, back up, to leave one. */
449 if (!*s && s != p)
450 --s;
451 return s;
454 /* Print all whole numbers from A to B, inclusive -- to stdout, each
455 followed by a newline. If B < A, return and print nothing.
456 Otherwise, do all the work and exit. */
457 static void
458 seq_fast (char const *a, char const *b, uintmax_t step)
460 bool inf = STREQ (b, "inf");
462 /* Skip past any leading 0's. Without this, our naive cmp
463 function would declare 000 to be larger than 99. */
464 a = trim_leading_zeros (a);
465 b = trim_leading_zeros (b);
467 size_t p_len = strlen (a);
468 size_t q_len = inf ? 0 : strlen (b);
470 /* Allow for at least 31 digits without realloc.
471 1 more than p_len is needed for the inf case. */
472 #define INITIAL_ALLOC_DIGITS 31
473 size_t inc_size = MAX (MAX (p_len + 1, q_len), INITIAL_ALLOC_DIGITS);
474 /* Ensure we only increase by at most 1 digit at buffer boundaries. */
475 static_assert (SEQ_FAST_STEP_LIMIT_DIGITS < INITIAL_ALLOC_DIGITS - 1);
477 /* Copy input strings (incl NUL) to end of new buffers. */
478 char *p0 = xmalloc (inc_size + 1);
479 char *p = memcpy (p0 + inc_size - p_len, a, p_len + 1);
480 char *q;
481 char *q0;
482 if (! inf)
484 q0 = xmalloc (inc_size + 1);
485 q = memcpy (q0 + inc_size - q_len, b, q_len + 1);
487 else
488 q = q0 = nullptr;
490 bool ok = inf || cmp (p, p_len, q, q_len) <= 0;
491 if (ok)
493 /* Reduce number of fwrite calls which is seen to
494 give a speed-up of more than 2x over the unbuffered code
495 when printing the first 10^9 integers. */
496 size_t buf_size = MAX (BUFSIZ, (inc_size + 1) * 2);
497 char *buf = xmalloc (buf_size);
498 char const *buf_end = buf + buf_size;
500 char *bufp = buf;
502 /* Write first number to buffer. */
503 bufp = mempcpy (bufp, p, p_len);
505 /* Append separator then number. */
506 while (true)
508 for (uintmax_t n_incr = step; n_incr; n_incr--)
509 incr (&p, &p_len);
511 if (! inf && 0 < cmp (p, p_len, q, q_len))
512 break;
514 *bufp++ = *separator;
516 /* Double up the buffers when needed for the inf case. */
517 if (p_len == inc_size)
519 inc_size *= 2;
520 p0 = xrealloc (p0, inc_size + 1);
521 p = memmove (p0 + p_len, p0, p_len + 1);
523 if (buf_size < (inc_size + 1) * 2)
525 size_t buf_offset = bufp - buf;
526 buf_size = (inc_size + 1) * 2;
527 buf = xrealloc (buf, buf_size);
528 buf_end = buf + buf_size;
529 bufp = buf + buf_offset;
533 bufp = mempcpy (bufp, p, p_len);
534 /* If no place for another separator + number then
535 output buffer so far, and reset to start of buffer. */
536 if (buf_end - (p_len + 1) < bufp)
538 if (fwrite (buf, bufp - buf, 1, stdout) != 1)
539 write_error ();
540 bufp = buf;
544 /* Write any remaining buffered output, and the terminator. */
545 *bufp++ = *terminator;
546 if (fwrite (buf, bufp - buf, 1, stdout) != 1)
547 write_error ();
550 if (ok)
551 exit (EXIT_SUCCESS);
553 free (p0);
554 free (q0);
557 /* Return true if S consists of at least one digit and no non-digits. */
558 ATTRIBUTE_PURE
559 static bool
560 all_digits_p (char const *s)
562 size_t n = strlen (s);
563 return ISDIGIT (s[0]) && n == strspn (s, "0123456789");
567 main (int argc, char **argv)
569 int optc;
570 operand first = { 1, 1, 0 };
571 operand step = { 1, 1, 0 };
572 operand last;
573 struct layout layout = { 0, 0 };
575 /* The printf(3) format used for output. */
576 char const *format_str = nullptr;
578 initialize_main (&argc, &argv);
579 set_program_name (argv[0]);
580 locale_ok = !!setlocale (LC_ALL, "");
581 bindtextdomain (PACKAGE, LOCALEDIR);
582 textdomain (PACKAGE);
584 atexit (close_stdout);
586 equal_width = false;
587 separator = "\n";
589 /* We have to handle negative numbers in the command line but this
590 conflicts with the command line arguments. So explicitly check first
591 whether the next argument looks like a negative number. */
592 while (optind < argc)
594 if (argv[optind][0] == '-'
595 && ((optc = argv[optind][1]) == '.' || ISDIGIT (optc)))
597 /* means negative number */
598 break;
601 optc = getopt_long (argc, argv, "+f:s:w", long_options, nullptr);
602 if (optc == -1)
603 break;
605 switch (optc)
607 case 'f':
608 format_str = optarg;
609 break;
611 case 's':
612 separator = optarg;
613 break;
615 case 'w':
616 equal_width = true;
617 break;
619 case_GETOPT_HELP_CHAR;
621 case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
623 default:
624 usage (EXIT_FAILURE);
628 int n_args = argc - optind;
629 if (n_args < 1)
631 error (0, 0, _("missing operand"));
632 usage (EXIT_FAILURE);
635 if (3 < n_args)
637 error (0, 0, _("extra operand %s"), quote (argv[optind + 3]));
638 usage (EXIT_FAILURE);
641 if (format_str)
642 format_str = long_double_format (format_str, &layout);
644 if (format_str != nullptr && equal_width)
646 error (0, 0, _("format string may not be specified"
647 " when printing equal width strings"));
648 usage (EXIT_FAILURE);
651 /* If the following hold:
652 - no format string, [FIXME: relax this, eventually]
653 - integer start (or no start)
654 - integer end
655 - integer increment <= SEQ_FAST_STEP_LIMIT
656 then use the much more efficient integer-only code,
657 operating on arbitrarily large numbers. */
658 bool fast_step_ok = false;
659 if (n_args != 3
660 || (all_digits_p (argv[optind + 1])
661 && xstrtold (argv[optind + 1], nullptr, &step.value, cl_strtold)
662 && 0 < step.value && step.value <= SEQ_FAST_STEP_LIMIT))
663 fast_step_ok = true;
665 if (all_digits_p (argv[optind])
666 && (n_args == 1 || all_digits_p (argv[optind + 1]))
667 && (n_args < 3 || (fast_step_ok
668 && all_digits_p (argv[optind + 2])))
669 && !equal_width && !format_str && strlen (separator) == 1)
671 char const *s1 = n_args == 1 ? "1" : argv[optind];
672 char const *s2 = argv[optind + (n_args - 1)];
673 seq_fast (s1, s2, step.value);
675 /* Upon any failure, let the more general code deal with it. */
678 last = scan_arg (argv[optind++]);
680 if (optind < argc)
682 first = last;
683 last = scan_arg (argv[optind++]);
685 if (optind < argc)
687 step = last;
688 if (step.value == 0)
690 error (0, 0, _("invalid Zero increment value: %s"),
691 quote (argv[optind - 1]));
692 usage (EXIT_FAILURE);
695 last = scan_arg (argv[optind++]);
699 /* Try the fast method again, for integers of the form 1e1 etc.,
700 or "inf" end value. */
701 if (first.precision == 0 && step.precision == 0 && last.precision == 0
702 && isfinite (first.value) && 0 <= first.value && 0 <= last.value
703 && 0 < step.value && step.value <= SEQ_FAST_STEP_LIMIT
704 && !equal_width && !format_str && strlen (separator) == 1)
706 char *s1;
707 char *s2;
708 if (asprintf (&s1, "%0.Lf", first.value) < 0)
709 xalloc_die ();
710 if (! isfinite (last.value))
711 s2 = xstrdup ("inf"); /* Ensure "inf" is used. */
712 else if (asprintf (&s2, "%0.Lf", last.value) < 0)
713 xalloc_die ();
715 if (*s1 != '-' && *s2 != '-')
716 seq_fast (s1, s2, step.value);
718 free (s1);
719 free (s2);
720 /* Upon any failure, let the more general code deal with it. */
723 if (format_str == nullptr)
724 format_str = get_default_format (first, step, last);
726 print_numbers (format_str, layout, first.value, step.value, last.value);
728 main_exit (EXIT_SUCCESS);