seq: 70x faster for non-negative whole numbers and incr==1

Handle non-negative whole numbers robustly and efficiently when
the increment is 1 and when no format-changing option is specified.
On the correctness front, for very large numbers, seq now works fine:

    $ b=1000000000000000000000000000
    $ src/seq ${b}09 ${b}11
    100000000000000000000000000009
    100000000000000000000000000010
    100000000000000000000000000011

while the old one would infloop, printing garbage:

    $ seq ${b}09 ${b}11 | head -2
    99999999999999999997315645440
    99999999999999999997315645440

The new code is much more efficient, too:
Old vs new: 55.81s vs 0.82s

  $ env time --f=%e seq $((10**8)) > /dev/null
  55.81
  $ env time --f=%e src/seq $((10**8)) > /dev/null
  0.82

* seq.c (incr): New function, inspired by the one in cat.c.
(cmp, seq_fast): New functions, inspired by code in nt-factor
by Torbjörn Granlund and Niels Möller.
(trim_leading_zeros): New function, without which cmp would malfunction.
(all_digits_p): New function.
(main): Hoist the format_str-vs-equal_width check to precede first
treatment of operands, and insert code to call seq_fast when possible.
* NEWS (Bug fixes): Mention the correctness fix.
(Improvements): Mention the speed-up.
* tests/misc/seq.pl: Exercise the new code.

Improved by: Bernhard Voelker.
http://thread.gmane.org/gmane.comp.gnu.coreutils.general/3340

1 files changed, 14 insertions, 0 deletions

diff --git a/tests/misc/seq.pl b/tests/misc/seq.pl
index 2517d9993..351097b70 100755
--- a/tests/misc/seq.pl
+++ b/tests/misc/seq.pl
@@ -30,6 +30,11 @@ my $locale = $ENV{LOCALE_FR_UTF8};
 ! defined $locale || $locale eq 'none'
   and $locale = 'C';
 
+my $p = '9' x 81;
+(my $q = $p) =~ s/9/0/g;
+$q = "1$q";
+(my $r = $q) =~ s/0$/1/;
+
 my @Tests =
   (
    ['onearg-1',	qw(10),		{OUT => [(1..10)]}],
@@ -107,6 +112,15 @@ my @Tests =
     {ENV => "LC_ALL=$locale"},
     {OUT_SUBST => 's/,/./g'},
     ],
+
+   # With coreutils-8.19 and prior, this would infloop.
+   ['long-1', "$p $r", {OUT => [$p, $q, $r]}],
+
+   # Exercise the code that trims leading zeros.
+   ['long-leading-zeros1', qw(000 2), {OUT => [qw(0 1 2)]}],
+   ['long-leading-zeros2', qw(000 02), {OUT => [qw(0 1 2)]}],
+   ['long-leading-zeros3', qw(00 02), {OUT => [qw(0 1 2)]}],
+   ['long-leading-zeros4', qw(0 02), {OUT => [qw(0 1 2)]}],
   );
 
 # Append a newline to each entry in the OUT array.