From eb8dd9dca1228af0cd132f515509051ecfabf6f6 Mon Sep 17 00:00:00 2001 From: cvs2svn Date: Mon, 14 Apr 2025 17:32:06 +0000 Subject: This commit was manufactured by cvs2git to create tag 'tb_20250414'. --- src/lib/libc/string/memmem.c | 184 ------------------------------------------- 1 file changed, 184 deletions(-) delete mode 100644 src/lib/libc/string/memmem.c (limited to 'src/lib/libc/string/memmem.c') diff --git a/src/lib/libc/string/memmem.c b/src/lib/libc/string/memmem.c deleted file mode 100644 index 3b180b4a62..0000000000 --- a/src/lib/libc/string/memmem.c +++ /dev/null @@ -1,184 +0,0 @@ -/* $OpenBSD: memmem.c,v 1.5 2020/04/16 12:39:28 claudio Exp $ */ - -/* - * Copyright (c) 2005-2020 Rich Felker, et al. - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. - * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY - * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, - * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE - * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - */ - -#include -#include - -static char * -twobyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) -{ - uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1]; - for (h+=2, k-=2; k; k--, hw = hw<<8 | *h++) - if (hw == nw) return (char *)h-2; - return hw == nw ? (char *)h-2 : 0; -} - -static char * -threebyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) -{ - uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8; - uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8; - for (h+=3, k-=3; k; k--, hw = (hw|*h++)<<8) - if (hw == nw) return (char *)h-3; - return hw == nw ? (char *)h-3 : 0; -} - -static char * -fourbyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) -{ - uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3]; - uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3]; - for (h+=4, k-=4; k; k--, hw = hw<<8 | *h++) - if (hw == nw) return (char *)h-4; - return hw == nw ? (char *)h-4 : 0; -} - -#define MAX(a,b) ((a)>(b)?(a):(b)) -#define MIN(a,b) ((a)<(b)?(a):(b)) - -#define BITOP(a,b,op) \ - ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) - -/* - * Maxime Crochemore and Dominique Perrin, Two-way string-matching, - * Journal of the ACM, 38(3):651-675, July 1991. - */ -static char * -twoway_memmem(const unsigned char *h, const unsigned char *z, - const unsigned char *n, size_t l) -{ - size_t i, ip, jp, k, p, ms, p0, mem, mem0; - size_t byteset[32 / sizeof(size_t)] = { 0 }; - size_t shift[256]; - - /* Computing length of needle and fill shift table */ - for (i=0; i n[jp+k]) { - jp += k; - k = 1; - p = jp - ip; - } else { - ip = jp++; - k = p = 1; - } - } - ms = ip; - p0 = p; - - /* And with the opposite comparison */ - ip = -1; jp = 0; k = p = 1; - while (jp+k ms+1) ms = ip; - else p = p0; - - /* Periodic needle? */ - if (memcmp(n, n+p, ms+1)) { - mem0 = 0; - p = MAX(ms, l-ms-1) + 1; - } else mem0 = l-p; - mem = 0; - - /* Search loop */ - for (;;) { - /* If remainder of haystack is shorter than needle, done */ - if (z-h < l) return 0; - - /* Check last byte first; advance by shift on mismatch */ - if (BITOP(byteset, h[l-1], &)) { - k = l-shift[h[l-1]]; - if (k) { - if (k < mem) k = mem; - h += k; - mem = 0; - continue; - } - } else { - h += l; - mem = 0; - continue; - } - - /* Compare right half */ - for (k=MAX(ms+1,mem); kmem && n[k-1] == h[k-1]; k--); - if (k <= mem) return (char *)h; - h += p; - mem = mem0; - } -} - -void * -memmem(const void *h0, size_t k, const void *n0, size_t l) -{ - const unsigned char *h = h0, *n = n0; - - /* Return immediately on empty needle */ - if (!l) return (void *)h; - - /* Return immediately when needle is longer than haystack */ - if (k