Comparison of Two Implementations of strstr

12 March 2007

Today, I saw two implementations of strstr, kind of interesting.

Implementation 1

http://lynx.isc.org/lynx2.8.5/lynx2-8-5/src/strstr.c

Concise and easy to follow, I definitely prefer this one to the other one though it might be less efficient.

/* Written by Philippe De Muyter <phdm@macqel.be>.  */
char *
  strstr (buf, sub)
     register char *buf;
     register char *sub;
{
    register char *bp;
    register char *sp;

    if (!*sub)
      return buf;
    while (*buf)
    {
        bp = buf;
        sp = sub;
        do {
            if (!*sp)
              return buf;
        } while (*bp++ == *sp++);
        buf += 1;
    }
    return 0;
}

Implementation 2

This is from glibc (glibc-2.5/string/strstr.c). OK, I admit that I didn't try to understand this one.

/*
 * My personal strstr() implementation that beats most other algorithms.
 * Until someone tells me otherwise, I assume that this is the
 * fastest implementation of strstr() in C.
 * I deliberately chose not to comment it.  You should have at least
 * as much fun trying to understand it, as I had to write it :-).
 *
 * Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de */

typedef unsigned chartype;

char *
strstr (phaystack, pneedle)
     const char *phaystack;
     const char *pneedle;
{
  const unsigned char *haystack, *needle;
  chartype b;
  const unsigned char *rneedle;

  haystack = (const unsigned char *) phaystack;

  if ((b = *(needle = (const unsigned char *) pneedle)))
    {
      chartype c;
      haystack--;       /* possible ANSI violation */

      {
    chartype a;
    do
      if (!(a = *++haystack))
        goto ret0;
    while (a != b);
      }

      if (!(c = *++needle))
    goto foundneedle;
      ++needle;
      goto jin;

      for (;;)
    {
      {
        chartype a;
        if (0)
        jin:{
        if ((a = *++haystack) == c)
          goto crest;
          }
        else
          a = *++haystack;
        do
          {
        for (; a != b; a = *++haystack)
          {
            if (!a)
              goto ret0;
            if ((a = *++haystack) == b)
              break;
            if (!a)
              goto ret0;
          }
          }
        while ((a = *++haystack) != c);
      }
    crest:
      {
        chartype a;
        {
          const unsigned char *rhaystack;
          if (*(rhaystack = haystack-- + 1) == (a = *(rneedle = needle)))
        do
          {
            if (!a)
              goto foundneedle;
            if (*++rhaystack != (a = *++needle))
              break;
            if (!a)
              goto foundneedle;
          }
        while (*++rhaystack == (a = *++needle));
          needle = rneedle; /* took the register-poor aproach */
        }
        if (!a)
          break;
      }
    }
    }
foundneedle:
  return (char *) haystack;
ret0:
  return 0;
}

computer 89