| 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 | ␉return NULL;␊ |
| 52 | }␊ |
| 53 | |
