I was recently porting an application that uses memmem
from Linux to Windows.
While memmem
is available as a library function on Linux, MSDN / Windows does not offer it. I could have used strstr
but then it has a very different prototype and expects only null-terminated strings as arguments. Googling around, I discovered a few implementations of memmem
but none appeared to truly mimic memmem
.
I therefore wrote one of my own:
void *memmem(const void *haystack_start, size_t haystack_len, const void *needle_start, size_t needle_len)
{
const unsigned char *haystack = (const unsigned char *) haystack_start;
const unsigned char *needle = (const unsigned char *) needle_start;
const unsigned char *h = NULL;
const unsigned char *n = NULL;
size_t x = needle_len;
/* The first occurrence of the empty string is deemed to occur at
the beginning of the string. */
if (needle_len == 0)
return (void *) haystack_start;
/* Sanity check, otherwise the loop might search through the whole
memory. */
if (haystack_len < needle_len)
return NULL;
for (; *haystack && haystack_len--; haystack++) {
x = needle_len;
n = needle;
h = haystack;
if (haystack_len < needle_len)
break;
if ((*haystack != *needle) || ( *haystack + needle_len != *needle + needle_len))
continue;
for (; x ; h++ , n++) {
x--;
if (*h != *n)
break;
if (x == 0)
return (void *)haystack;
}
}
return NULL;
}
The code does work, but my question is: could it be done more efficiently, or faster?
I hope one of the awesome hacks here will also be kind enough to point out if this implementation has a vulnerability that I may have not noticed.
Θ(nm)
performance of the naive algorithm you're using. \$\endgroup\$