1 /*-
2  * SPDX-License-Identifier: MIT
4  * Copyright (c) 2005-2014 Rich Felker, et al.
29 twobyte_strstr(const unsigned char *h, const unsigned char *n)  in twobyte_strstr()  argument
31 	uint16_t nw = n[0] << 8 | n[1], hw = h[0] << 8 | h[1];  in twobyte_strstr()
32 	for (h++; *h && hw != nw; hw = hw << 8 | *++h)  in twobyte_strstr()
34 	return *h ? (char *)h - 1 : 0;  in twobyte_strstr()
38 threebyte_strstr(const unsigned char *h, const unsigned char *n)  in threebyte_strstr()  argument
40 	uint32_t nw = (uint32_t)n[0] << 24 | n[1] << 16 | n[2] << 8;  in threebyte_strstr()
41 	uint32_t hw = (uint32_t)h[0] << 24 | h[1] << 16 | h[2] << 8;  in threebyte_strstr()
42 	for (h += 2; *h && hw != nw; hw = (hw | *++h) << 8)  in threebyte_strstr()
44 	return *h ? (char *)h - 2 : 0;  in threebyte_strstr()
48 fourbyte_strstr(const unsigned char *h, const unsigned char *n)  in fourbyte_strstr()  argument
50 	uint32_t nw = (uint32_t)n[0] << 24 | n[1] << 16 | n[2] << 8 | n[3];  in fourbyte_strstr()
51 	uint32_t hw = (uint32_t)h[0] << 24 | h[1] << 16 | h[2] << 8 | h[3];  in fourbyte_strstr()
52 	for (h += 3; *h && hw != nw; hw = hw << 8 | *++h)  in fourbyte_strstr()
54 	return *h ? (char *)h - 3 : 0;  in fourbyte_strstr()
61 	((a)[(size_t)(b) / (8 * sizeof *(a))] op \
62 	    (size_t)1 << ((size_t)(b) % (8 * sizeof *(a))))
67  * initialized to avoid fully initializing a 1kb/2kb table.
69  * Reference: CROCHEMORE M., PERRIN D., 1991, Two-way string-matching,
70  * Journal of the ACM 38(3):651-675
73 twoway_strstr(const unsigned char *h, const unsigned char *n)  in twoway_strstr()  argument
81 	for (l = 0; n[l] && h[l]; l++)  in twoway_strstr()
82 		BITOP(byteset, n[l], |=), shift[n[l]] = l + 1;  in twoway_strstr()
83 	if (n[l])  in twoway_strstr()
87 	ip = -1;  in twoway_strstr()
89 	k = p = 1;  in twoway_strstr()
91 		if (n[ip + k] == n[jp + k]) {  in twoway_strstr()
94 				k = 1;  in twoway_strstr()
97 		} else if (n[ip + k] > n[jp + k]) {  in twoway_strstr()
99 			k = 1;  in twoway_strstr()
100 			p = jp - ip;  in twoway_strstr()
103 			k = p = 1;  in twoway_strstr()
110 	ip = -1;  in twoway_strstr()
112 	k = p = 1;  in twoway_strstr()
114 		if (n[ip + k] == n[jp + k]) {  in twoway_strstr()
117 				k = 1;  in twoway_strstr()
120 		} else if (n[ip + k] < n[jp + k]) {  in twoway_strstr()
122 			k = 1;  in twoway_strstr()
123 			p = jp - ip;  in twoway_strstr()
126 			k = p = 1;  in twoway_strstr()
129 	if (ip + 1 > ms + 1)  in twoway_strstr()
135 	if (memcmp(n, n + p, ms + 1)) {  in twoway_strstr()
137 		p = MAX(ms, l - ms - 1) + 1;  in twoway_strstr()
139 		mem0 = l - p;  in twoway_strstr()
142 	/* Initialize incremental end-of-haystack pointer */  in twoway_strstr()
147 		/* Update incremental end-of-haystack pointer */  in twoway_strstr()
148 		if (z - h < l) {  in twoway_strstr()
154 				if (z - h < l)  in twoway_strstr()
161 		if (BITOP(byteset, h[l - 1], &)) {  in twoway_strstr()
162 			k = l - shift[h[l - 1]];  in twoway_strstr()
177 		for (k = MAX(ms + 1, mem); n[k] && n[k] == h[k]; k++)  in twoway_strstr()
179 		if (n[k]) {  in twoway_strstr()
180 			h += k - ms;  in twoway_strstr()
185 		for (k = ms + 1; k > mem && n[k - 1] == h[k - 1]; k--)  in twoway_strstr()
195 strstr(const char *h, const char *n)  in strstr()  argument
198 	if (!n[0])  in strstr()
202 	h = strchr(h, *n);  in strstr()
203 	if (!h || !n[1])  in strstr()
205 	if (!h[1])  in strstr()
207 	if (!n[2])  in strstr()
208 		return twobyte_strstr((void *)h, (void *)n);  in strstr()
211 	if (!n[3])  in strstr()
212 		return threebyte_strstr((void *)h, (void *)n);  in strstr()
215 	if (!n[4])  in strstr()
216 		return fourbyte_strstr((void *)h, (void *)n);  in strstr()
218 	return twoway_strstr((void *)h, (void *)n);  in strstr()