From 44b3bb9bcb34fc8ebed0b04f667fecef15d7bc82 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Sun, 28 Dec 2025 11:00:41 +0100 Subject: memmem, memcasemem: use kmp algorithm MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- memmem.c | 34 +++++++++++++++++++++++++++------- 1 file changed, 27 insertions(+), 7 deletions(-) (limited to 'memmem.c') diff --git a/memmem.c b/memmem.c index 1c537d0..5d6e711 100644 --- a/memmem.c +++ b/memmem.c @@ -6,20 +6,40 @@ void * libsimple_memmem(const void *hay_, size_t hayn, const void *sub_, size_t subn) { - const char *hay = hay_, *end; - const char *sub = sub_; + const unsigned char *hay = hay_; + const unsigned char *sub = sub_; + size_t *next, i, j; if (!subn) - return REMOVE_CONST(hay, char *); + return REMOVE_CONST(hay, unsigned char *); if (hayn < subn) return NULL; if (subn == 1) return memchr(hay, *sub, hayn); - /* TODO optimise */ - for (end = &hay[hayn - subn + 1]; hay != end; hay++) - if (*hay == *sub && !memcmp(hay, sub, subn)) - return REMOVE_CONST(hay, char *); + next = alloca((subn + 1U) * sizeof(*next)); + i = 0, j = SIZE_MAX; + goto beginning; + for (; i < subn; i++, j++) { + if (sub[i] == sub[j]) { + next[i] = next[j]; + } else { + beginning: + next[i] = j; + while (j != SIZE_MAX && sub[i] != sub[j]) + j = next[j]; + } + } + + for (i = j = 0; i < hayn;) { + while (j != SIZE_MAX && sub[j] != hay[i]) + j = next[j]; + i++; + if (++j == subn) { + hay = &hay[i - j]; + return REMOVE_CONST(hay, unsigned char *); + } + } return NULL; } -- cgit v1.2.3-70-g09d2