Root/
Source at commit 2517 created 9 years 6 months ago. By ifabio, sync with trunk | |
---|---|
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 |