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 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
