memmem, memcasemem: use kmp algorithmHEADmaster

Signed-off-by: Mattias Andrée <m@maandree.se>

1 files changed, 27 insertions, 7 deletions

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;
 }