1/*
2 * memmem.c
3 *
4 * Find a byte string inside a longer byte string
5 *
6 * This uses the "Not So Naive" algorithm, a very simple but
7 * usually effective algorithm, see:
8 *
9 * http://www-igm.univ-mlv.fr/~lecroq/string/
10 */
11
12#include <string.h>
13
14void *memmem(const void *haystack, size_t n, const void *needle, size_t m)
15{
16    const unsigned char *y = (const unsigned char *)haystack;
17    const unsigned char *x = (const unsigned char *)needle;
18
19    size_t j, k, l;
20
21    if (m > n || !m || !n)
22        return NULL;
23
24    if (1 != m) {
25        if (x[0] == x[1]) {
26            k = 2;
27            l = 1;
28        } else {
29            k = 1;
30            l = 2;
31        }
32
33        j = 0;
34        while (j <= n - m) {
35            if (x[1] != y[j + 1]) {
36                j += k;
37            } else {
38                if (!memcmp(x + 2, y + j + 2, m - 2)
39                    && x[0] == y[j])
40                    return (void *)&y[j];
41                j += l;
42            }
43        }
44    } else {
45        do {
46            if (*y == *x)
47                return (void *)y;
48            y++;
49        } while (--n);
50    }
51
52    return NULL;
53}
54