12 March 2007

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

## Implementation 1

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;
}
```