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
memmem(const void * haystack,size_t n,const void * needle,size_t m)14 void *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