Re: 70x speed-up for seq's common cases

[Torbjorn Granlund]

For general seq use, I suppose we should do away with `incr' and instead
use a general `add'.  Below is a suggested implementation, and as bonus
also a `sub'.

Like `incr', `add' needs an extra byte if space, since if the end value
is within the increment from a power of 10, a number with one more digit
than the end value will be created.

Implementing negative values is a bit tricky.  If a-b is wanted and a <
b, one must of course compute b-a and separately store a minus sign.  I
just write a `sub' function, not any code actually handling negative
numbers.

The function `add' is reasonably well-tested.  The function `sub' is
minimally tested (but as a trivial edit of `add' it might b correct
anyway).

void
add (string *st, string *incr)
{
  size_t lens, leni;
  long i;
  int d, cy;
  char *s, *si;

  lens = st->len;
  leni = incr->len;

  s = st->str;

  if (lens < leni)
    {
      size_t xtra = leni - lens;
      memmove (s + xtra, s, lens);      /* make space at beginning */
      memset (s, '0', xtra);            /* pad with zeros at beginning  */
      lens = leni;                      /* target string same size as `incr' */
    }

  s += lens;
  si = incr->str + leni;

  /* Add `incr' to `st'.  */
  cy = 0;
  for (i = leni - 1; i >= 0; i--)
    {
      d = *--s + *--si - '0' + cy;
      cy = d > '9';
      d -= 10 * cy;
      *s = d;
    }

  /* Propagate carry.  */
  if (cy != 0)
    {
      for (i = lens - leni - 1; i >= 0; i--)
        {
          d = *--s + 1;
          if (d != '0' + 10)
            {
              *s = d;
              return;
            }
          *s = '0';
        }
      /* Carry beyond first string char, extend.  */
      lens++;
      memmove (s + 1, s, lens);
      *s = '1';
    }
  st->len = lens;
}

void
sub (string *st, string *incr)
{
  size_t lens, leni;
  long i;
  int d, cy;
  char *s, *si;

  lens = st->len;
  leni = incr->len;

  s = st->str;

  if (lens < leni)
    abort ();

  s += lens;
  si = incr->str + leni;

  /* Add `incr' to `st'.  */
  cy = 0;
  for (i = leni - 1; i >= 0; i--)
    {
      d = *--s - *--si + '0' - cy;
      cy = d < '0';
      d += 10 * cy;
      *s = d;
    }

  /* Propagate carry.  */
  if (cy != 0)
    {
      for (i = lens - leni - 1; i >= 0; i--)
        {
          d = *--s - 1;
          if (d != '0' - 1)
            {
              *s = d;
              return;
            }
          *s = '9';
        }
      /* Borrow beyond first string char, error.  */
      abort ();
    }
  st->len = lens;
}

-- 
Torbjörn