1*19261079SEd Maste /* $OpenBSD: memmem.c,v 1.5 2020/04/16 12:39:28 claudio Exp $ */
2*19261079SEd Maste
3*19261079SEd Maste /*
4*19261079SEd Maste * Copyright (c) 2005-2020 Rich Felker, et al.
5*19261079SEd Maste *
6*19261079SEd Maste * Permission is hereby granted, free of charge, to any person obtaining
7*19261079SEd Maste * a copy of this software and associated documentation files (the
8*19261079SEd Maste * "Software"), to deal in the Software without restriction, including
9*19261079SEd Maste * without limitation the rights to use, copy, modify, merge, publish,
10*19261079SEd Maste * distribute, sublicense, and/or sell copies of the Software, and to
11*19261079SEd Maste * permit persons to whom the Software is furnished to do so, subject to
12*19261079SEd Maste * the following conditions:
13*19261079SEd Maste *
14*19261079SEd Maste * The above copyright notice and this permission notice shall be
15*19261079SEd Maste * included in all copies or substantial portions of the Software.
16*19261079SEd Maste *
17*19261079SEd Maste * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18*19261079SEd Maste * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19*19261079SEd Maste * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
20*19261079SEd Maste * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
21*19261079SEd Maste * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
22*19261079SEd Maste * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
23*19261079SEd Maste * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24*19261079SEd Maste */
25*19261079SEd Maste
26*19261079SEd Maste /* OPENBSD ORIGINAL: lib/libc/string/memmem.c */
27*19261079SEd Maste
28*19261079SEd Maste #include "includes.h"
29*19261079SEd Maste
30*19261079SEd Maste #ifndef HAVE_MEMMEM
31*19261079SEd Maste
32*19261079SEd Maste #include <string.h>
33*19261079SEd Maste #ifdef HAVE_STDINT_H
34*19261079SEd Maste #include <stdint.h>
35*19261079SEd Maste #endif
36*19261079SEd Maste
37*19261079SEd Maste static char *
twobyte_memmem(const unsigned char * h,size_t k,const unsigned char * n)38*19261079SEd Maste twobyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
39*19261079SEd Maste {
40*19261079SEd Maste uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1];
41*19261079SEd Maste for (h+=2, k-=2; k; k--, hw = hw<<8 | *h++)
42*19261079SEd Maste if (hw == nw) return (char *)h-2;
43*19261079SEd Maste return hw == nw ? (char *)h-2 : 0;
44*19261079SEd Maste }
45*19261079SEd Maste
46*19261079SEd Maste static char *
threebyte_memmem(const unsigned char * h,size_t k,const unsigned char * n)47*19261079SEd Maste threebyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
48*19261079SEd Maste {
49*19261079SEd Maste uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8;
50*19261079SEd Maste uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8;
51*19261079SEd Maste for (h+=3, k-=3; k; k--, hw = (hw|*h++)<<8)
52*19261079SEd Maste if (hw == nw) return (char *)h-3;
53*19261079SEd Maste return hw == nw ? (char *)h-3 : 0;
54*19261079SEd Maste }
55*19261079SEd Maste
56*19261079SEd Maste static char *
fourbyte_memmem(const unsigned char * h,size_t k,const unsigned char * n)57*19261079SEd Maste fourbyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
58*19261079SEd Maste {
59*19261079SEd Maste uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3];
60*19261079SEd Maste uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3];
61*19261079SEd Maste for (h+=4, k-=4; k; k--, hw = hw<<8 | *h++)
62*19261079SEd Maste if (hw == nw) return (char *)h-4;
63*19261079SEd Maste return hw == nw ? (char *)h-4 : 0;
64*19261079SEd Maste }
65*19261079SEd Maste
66*19261079SEd Maste #if 0
67*19261079SEd Maste /* In -portable, defines.h ensures that these are already defined. */
68*19261079SEd Maste #define MAX(a,b) ((a)>(b)?(a):(b))
69*19261079SEd Maste #define MIN(a,b) ((a)<(b)?(a):(b))
70*19261079SEd Maste #endif
71*19261079SEd Maste
72*19261079SEd Maste #define BITOP(a,b,op) \
73*19261079SEd Maste ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a))))
74*19261079SEd Maste
75*19261079SEd Maste /*
76*19261079SEd Maste * Maxime Crochemore and Dominique Perrin, Two-way string-matching,
77*19261079SEd Maste * Journal of the ACM, 38(3):651-675, July 1991.
78*19261079SEd Maste */
79*19261079SEd Maste static char *
twoway_memmem(const unsigned char * h,const unsigned char * z,const unsigned char * n,size_t l)80*19261079SEd Maste twoway_memmem(const unsigned char *h, const unsigned char *z,
81*19261079SEd Maste const unsigned char *n, size_t l)
82*19261079SEd Maste {
83*19261079SEd Maste size_t i, ip, jp, k, p, ms, p0, mem, mem0;
84*19261079SEd Maste size_t byteset[32 / sizeof(size_t)] = { 0 };
85*19261079SEd Maste size_t shift[256];
86*19261079SEd Maste
87*19261079SEd Maste /* Computing length of needle and fill shift table */
88*19261079SEd Maste for (i=0; i<l; i++)
89*19261079SEd Maste BITOP(byteset, n[i], |=), shift[n[i]] = i+1;
90*19261079SEd Maste
91*19261079SEd Maste /* Compute maximal suffix */
92*19261079SEd Maste ip = -1; jp = 0; k = p = 1;
93*19261079SEd Maste while (jp+k<l) {
94*19261079SEd Maste if (n[ip+k] == n[jp+k]) {
95*19261079SEd Maste if (k == p) {
96*19261079SEd Maste jp += p;
97*19261079SEd Maste k = 1;
98*19261079SEd Maste } else k++;
99*19261079SEd Maste } else if (n[ip+k] > n[jp+k]) {
100*19261079SEd Maste jp += k;
101*19261079SEd Maste k = 1;
102*19261079SEd Maste p = jp - ip;
103*19261079SEd Maste } else {
104*19261079SEd Maste ip = jp++;
105*19261079SEd Maste k = p = 1;
106*19261079SEd Maste }
107*19261079SEd Maste }
108*19261079SEd Maste ms = ip;
109*19261079SEd Maste p0 = p;
110*19261079SEd Maste
111*19261079SEd Maste /* And with the opposite comparison */
112*19261079SEd Maste ip = -1; jp = 0; k = p = 1;
113*19261079SEd Maste while (jp+k<l) {
114*19261079SEd Maste if (n[ip+k] == n[jp+k]) {
115*19261079SEd Maste if (k == p) {
116*19261079SEd Maste jp += p;
117*19261079SEd Maste k = 1;
118*19261079SEd Maste } else k++;
119*19261079SEd Maste } else if (n[ip+k] < n[jp+k]) {
120*19261079SEd Maste jp += k;
121*19261079SEd Maste k = 1;
122*19261079SEd Maste p = jp - ip;
123*19261079SEd Maste } else {
124*19261079SEd Maste ip = jp++;
125*19261079SEd Maste k = p = 1;
126*19261079SEd Maste }
127*19261079SEd Maste }
128*19261079SEd Maste if (ip+1 > ms+1) ms = ip;
129*19261079SEd Maste else p = p0;
130*19261079SEd Maste
131*19261079SEd Maste /* Periodic needle? */
132*19261079SEd Maste if (memcmp(n, n+p, ms+1)) {
133*19261079SEd Maste mem0 = 0;
134*19261079SEd Maste p = MAX(ms, l-ms-1) + 1;
135*19261079SEd Maste } else mem0 = l-p;
136*19261079SEd Maste mem = 0;
137*19261079SEd Maste
138*19261079SEd Maste /* Search loop */
139*19261079SEd Maste for (;;) {
140*19261079SEd Maste /* If remainder of haystack is shorter than needle, done */
141*19261079SEd Maste if (z-h < l) return 0;
142*19261079SEd Maste
143*19261079SEd Maste /* Check last byte first; advance by shift on mismatch */
144*19261079SEd Maste if (BITOP(byteset, h[l-1], &)) {
145*19261079SEd Maste k = l-shift[h[l-1]];
146*19261079SEd Maste if (k) {
147*19261079SEd Maste if (k < mem) k = mem;
148*19261079SEd Maste h += k;
149*19261079SEd Maste mem = 0;
150*19261079SEd Maste continue;
151*19261079SEd Maste }
152*19261079SEd Maste } else {
153*19261079SEd Maste h += l;
154*19261079SEd Maste mem = 0;
155*19261079SEd Maste continue;
156*19261079SEd Maste }
157*19261079SEd Maste
158*19261079SEd Maste /* Compare right half */
159*19261079SEd Maste for (k=MAX(ms+1,mem); k<l && n[k] == h[k]; k++);
160*19261079SEd Maste if (k < l) {
161*19261079SEd Maste h += k-ms;
162*19261079SEd Maste mem = 0;
163*19261079SEd Maste continue;
164*19261079SEd Maste }
165*19261079SEd Maste /* Compare left half */
166*19261079SEd Maste for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--);
167*19261079SEd Maste if (k <= mem) return (char *)h;
168*19261079SEd Maste h += p;
169*19261079SEd Maste mem = mem0;
170*19261079SEd Maste }
171*19261079SEd Maste }
172*19261079SEd Maste
173*19261079SEd Maste void *
memmem(const void * h0,size_t k,const void * n0,size_t l)174*19261079SEd Maste memmem(const void *h0, size_t k, const void *n0, size_t l)
175*19261079SEd Maste {
176*19261079SEd Maste const unsigned char *h = h0, *n = n0;
177*19261079SEd Maste
178*19261079SEd Maste /* Return immediately on empty needle */
179*19261079SEd Maste if (!l) return (void *)h;
180*19261079SEd Maste
181*19261079SEd Maste /* Return immediately when needle is longer than haystack */
182*19261079SEd Maste if (k<l) return 0;
183*19261079SEd Maste
184*19261079SEd Maste /* Use faster algorithms for short needles */
185*19261079SEd Maste h = memchr(h0, *n, k);
186*19261079SEd Maste if (!h || l==1) return (void *)h;
187*19261079SEd Maste k -= h - (const unsigned char *)h0;
188*19261079SEd Maste if (k<l) return 0;
189*19261079SEd Maste if (l==2) return twobyte_memmem(h, k, n);
190*19261079SEd Maste if (l==3) return threebyte_memmem(h, k, n);
191*19261079SEd Maste if (l==4) return fourbyte_memmem(h, k, n);
192*19261079SEd Maste
193*19261079SEd Maste return twoway_memmem(h, h+k, n, l);
194*19261079SEd Maste }
195*19261079SEd Maste DEF_WEAK(memmem);
196*19261079SEd Maste #endif /* HAVE_MEMMEM */
197