memmem.c (416ba5c74546f32a993436a99516d35008e9f384) memmem.c (88521634e964e3da78a0ce54109cddb59bf3f099)
1/*-
1/*-
2 * Copyright (c) 2005 Pascal Gloor <pascal.gloor@spale.com>
2 * Copyright (c) 2005-2014 Rich Felker, et al.
3 *
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * 3. The name of the author may not be used to endorse or promote
13 * products derived from this software without specific prior written
14 * permission.
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
15 *
11 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
19 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
20 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
21 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27 */
22 */
28
29#include <sys/cdefs.h>
30__FBSDID("$FreeBSD$");
31
32#include <string.h>
23#include <sys/cdefs.h>
24__FBSDID("$FreeBSD$");
25
26#include <string.h>
27#include <stdint.h>
33
28
34/*
35 * Find the first occurrence of the byte string s in byte string l.
36 */
29static char *twobyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
30{
31 uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1];
32 for (h++, k--; k; k--, hw = hw<<8 | *++h)
33 if (hw == nw) return (char *)h-1;
34 return 0;
35}
37
36
38void *
39memmem(const void *l, size_t l_len, const void *s, size_t s_len)
37static char *threebyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
40{
38{
41 register char *cur, *last;
42 const char *cl = (const char *)l;
43 const char *cs = (const char *)s;
39 uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8;
40 uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8;
41 for (h+=2, k-=2; k; k--, hw = (hw|*++h)<<8)
42 if (hw == nw) return (char *)h-2;
43 return 0;
44}
44
45
45 /* empty "s" matches the beginning of "l" */
46 if (s_len == 0)
47 return (void *)cl;
46static char *fourbyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
47{
48 uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3];
49 uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3];
50 for (h+=3, k-=3; k; k--, hw = hw<<8 | *++h)
51 if (hw == nw) return (char *)h-3;
52 return 0;
53}
48
54
49 /* "s" must be smaller or equal to "l" */
50 if (l_len < s_len)
51 return NULL;
55#define MAX(a,b) ((a)>(b)?(a):(b))
56#define MIN(a,b) ((a)<(b)?(a):(b))
52
57
53 /* special case where s_len == 1 */
54 if (s_len == 1)
55 return memchr(l, (int)*cs, l_len);
58#define BITOP(a,b,op) \
59 ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a))))
56
60
57 /* the last position where its possible to find "s" in "l" */
58 last = (char *)cl + l_len - s_len;
61static char *twoway_memmem(const unsigned char *h, const unsigned char *z, const unsigned char *n, size_t l)
62{
63 size_t i, ip, jp, k, p, ms, p0, mem, mem0;
64 size_t byteset[32 / sizeof(size_t)] = { 0 };
65 size_t shift[256];
59
66
60 for (cur = (char *)cl; cur <= last; cur++)
61 if (cur[0] == cs[0] && memcmp(cur, cs, s_len) == 0)
62 return cur;
67 /* Computing length of needle and fill shift table */
68 for (i=0; i<l; i++)
69 BITOP(byteset, n[i], |=), shift[n[i]] = i+1;
63
70
64 return NULL;
71 /* Compute maximal suffix */
72 ip = -1; jp = 0; k = p = 1;
73 while (jp+k<l) {
74 if (n[ip+k] == n[jp+k]) {
75 if (k == p) {
76 jp += p;
77 k = 1;
78 } else k++;
79 } else if (n[ip+k] > n[jp+k]) {
80 jp += k;
81 k = 1;
82 p = jp - ip;
83 } else {
84 ip = jp++;
85 k = p = 1;
86 }
87 }
88 ms = ip;
89 p0 = p;
90
91 /* And with the opposite comparison */
92 ip = -1; jp = 0; k = p = 1;
93 while (jp+k<l) {
94 if (n[ip+k] == n[jp+k]) {
95 if (k == p) {
96 jp += p;
97 k = 1;
98 } else k++;
99 } else if (n[ip+k] < n[jp+k]) {
100 jp += k;
101 k = 1;
102 p = jp - ip;
103 } else {
104 ip = jp++;
105 k = p = 1;
106 }
107 }
108 if (ip+1 > ms+1) ms = ip;
109 else p = p0;
110
111 /* Periodic needle? */
112 if (memcmp(n, n+p, ms+1)) {
113 mem0 = 0;
114 p = MAX(ms, l-ms-1) + 1;
115 } else mem0 = l-p;
116 mem = 0;
117
118 /* Search loop */
119 for (;;) {
120 /* If remainder of haystack is shorter than needle, done */
121 if (z-h < l) return 0;
122
123 /* Check last byte first; advance by shift on mismatch */
124 if (BITOP(byteset, h[l-1], &)) {
125 k = l-shift[h[l-1]];
126 if (k) {
127 if (mem0 && mem && k < p) k = l-p;
128 h += k;
129 mem = 0;
130 continue;
131 }
132 } else {
133 h += l;
134 mem = 0;
135 continue;
136 }
137
138 /* Compare right half */
139 for (k=MAX(ms+1,mem); k<l && n[k] == h[k]; k++);
140 if (k < l) {
141 h += k-ms;
142 mem = 0;
143 continue;
144 }
145 /* Compare left half */
146 for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--);
147 if (k <= mem) return (char *)h;
148 h += p;
149 mem = mem0;
150 }
65}
151}
152
153void *memmem(const void *h0, size_t k, const void *n0, size_t l)
154{
155 const unsigned char *h = h0, *n = n0;
156
157 /* Return immediately on empty needle */
158 if (!l) return (void *)h;
159
160 /* Return immediately when needle is longer than haystack */
161 if (k<l) return 0;
162
163 /* Use faster algorithms for short needles */
164 h = memchr(h0, *n, k);
165 if (!h || l==1) return (void *)h;
166 k -= h - (const unsigned char *)h0;
167 if (k<l) return 0;
168 if (l==2) return twobyte_memmem(h, k, n);
169 if (l==3) return threebyte_memmem(h, k, n);
170 if (l==4) return fourbyte_memmem(h, k, n);
171
172 return twoway_memmem(h, h+k, n, l);
173}