1 /*-
2  * SPDX-License-Identifier: MIT
4  * Copyright (c) 2005-2014 Rich Felker, et al.
29 twobyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)  in twobyte_memmem()  argument
32 	for (h += 2, k -= 2; k; k--, hw = hw << 8 | *h++)  in twobyte_memmem()
34 			return (char *)h - 2;  in twobyte_memmem()
35 	return hw == nw ? (char *)h - 2 : 0;  in twobyte_memmem()
39 threebyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)  in threebyte_memmem()  argument
43 	for (h += 3, k -= 3; k; k--, hw = (hw | *h++) << 8)  in threebyte_memmem()
45 			return (char *)h - 3;  in threebyte_memmem()
46 	return hw == nw ? (char *)h - 3 : 0;  in threebyte_memmem()
50 fourbyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)  in fourbyte_memmem()  argument
54 	for (h += 4, k -= 4; k; k--, hw = hw << 8 | *h++)  in fourbyte_memmem()
56 			return (char *)h - 4;  in fourbyte_memmem()
57 	return hw == nw ? (char *)h - 4 : 0;  in fourbyte_memmem()
72  * Reference: CROCHEMORE M., PERRIN D., 1991, Two-way string-matching,
73  * Journal of the ACM 38(3):651-675
79 	size_t i, ip, jp, k, p, ms, p0, mem, mem0;  in twoway_memmem()  local
88 	ip = -1;  in twoway_memmem()
90 	k = p = 1;  in twoway_memmem()
91 	while (jp + k < l) {  in twoway_memmem()
92 		if (n[ip + k] == n[jp + k]) {  in twoway_memmem()
93 			if (k == p) {  in twoway_memmem()
95 				k = 1;  in twoway_memmem()
97 				k++;  in twoway_memmem()
98 		} else if (n[ip + k] > n[jp + k]) {  in twoway_memmem()
99 			jp += k;  in twoway_memmem()
100 			k = 1;  in twoway_memmem()
101 			p = jp - ip;  in twoway_memmem()
104 			k = p = 1;  in twoway_memmem()
111 	ip = -1;  in twoway_memmem()
113 	k = p = 1;  in twoway_memmem()
114 	while (jp + k < l) {  in twoway_memmem()
115 		if (n[ip + k] == n[jp + k]) {  in twoway_memmem()
116 			if (k == p) {  in twoway_memmem()
118 				k = 1;  in twoway_memmem()
120 				k++;  in twoway_memmem()
121 		} else if (n[ip + k] < n[jp + k]) {  in twoway_memmem()
122 			jp += k;  in twoway_memmem()
123 			k = 1;  in twoway_memmem()
124 			p = jp - ip;  in twoway_memmem()
127 			k = p = 1;  in twoway_memmem()
138 		p = MAX(ms, l - ms - 1) + 1;  in twoway_memmem()
140 		mem0 = l - p;  in twoway_memmem()
146 		if (z - h < l)  in twoway_memmem()
150 		if (BITOP(byteset, h[l - 1], &)) {  in twoway_memmem()
151 			k = l - shift[h[l - 1]];  in twoway_memmem()
152 			if (k) {  in twoway_memmem()
153 				if (k < mem)  in twoway_memmem()
154 					k = mem;  in twoway_memmem()
155 				h += k;  in twoway_memmem()
166 		for (k = MAX(ms + 1, mem); k < l && n[k] == h[k]; k++)  in twoway_memmem()
168 		if (k < l) {  in twoway_memmem()
169 			h += k - ms;  in twoway_memmem()
174 		for (k = ms + 1; k > mem && n[k - 1] == h[k - 1]; k--)  in twoway_memmem()
176 		if (k <= mem)  in twoway_memmem()
184 memmem(const void *h0, size_t k, const void *n0, size_t l)  in memmem()  argument
193 	if (k < l)  in memmem()
197 	h = memchr(h0, *n, k);  in memmem()
200 	k -= h - (const unsigned char *)h0;  in memmem()
201 	if (k < l)  in memmem()
204 		return twobyte_memmem(h, k, n);  in memmem()
206 		return threebyte_memmem(h, k, n);  in memmem()
208 		return fourbyte_memmem(h, k, n);  in memmem()
210 	return twoway_memmem(h, h + k, n, l);  in memmem()