First commit

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

20 files changed, 521 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..0878514
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,16 @@
+*\#*
+*~
+*.o
+*.a
+*.lo
+*.su
+*.so
+*.so.*
+*.dll
+*.dylib
+*.gch
+*.gcov
+*.gcno
+*.gcda
+*.to
+*.t
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..0e6be1c
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,15 @@
+ISC License
+
+© 2025 Mattias Andrée <m@maandree.se>
+
+Permission to use, copy, modify, and/or distribute this software for any
+purpose with or without fee is hereby granted, provided that the above
+copyright notice and this permission notice appear in all copies.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..285f70e
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,102 @@
+.POSIX:
+
+CONFIGFILE = config.mk
+include $(CONFIGFILE)
+
+OS = linux
+# Linux:   linux
+# Mac OS:  macos
+# Windows: windows
+include mk/$(OS).mk
+
+
+LIB_MAJOR = 1
+LIB_MINOR = 0
+LIB_VERSION = $(LIB_MAJOR).$(LIB_MINOR)
+LIB_NAME = automata
+
+
+OBJ =\
+	libautomata_reset_kmp_automaton.o\
+	libautomata_clone_kmp_automaton.o\
+	libautomata_compile_kmp_automaton.o\
+	libautomata_execute_kmp_automaton.o\
+	libautomata_reset_mp_automaton.o\
+	libautomata_clone_mp_automaton.o\
+	libautomata_compile_mp_automaton.o\
+	libautomata_execute_mp_automaton.o
+
+TOBJ =\
+	test_kmp_automaton.to\
+	test_mp_automaton.to
+
+HDR =\
+	libautomata.h\
+	common.h
+
+LOBJ = $(OBJ:.o=.lo)
+TEST = $(TOBJ:.to=.t)
+
+
+all: libautomata.a libautomata.$(LIBEXT) $(TEST)
+$(OBJ): $(HDR)
+$(LOBJ): $(HDR)
+$(TOBJ): $(HDR)
+$(TEST): libautomata.a
+
+.c.o:
+	$(CC) -c -o $@ $< $(CFLAGS) $(CPPFLAGS)
+
+.c.lo:
+	$(CC) -fPIC -c -o $@ $< $(CFLAGS) $(CPPFLAGS)
+
+.c.to:
+	$(CC) -DTEST -c -o $@ $< $(CFLAGS) $(CPPFLAGS)
+
+.to.t:
+	$(CC) -o $@ $< libautomata.a $(LDFLAGS)
+
+.c.t:
+	$(CC) -DTEST -o $@ $< libautomata.a $(CFLAGS) $(CPPFLAGS) $(LDFLAGS)
+
+libautomata.a: $(OBJ)
+	@rm -f -- $@
+	$(AR) rc $@ $(OBJ)
+	$(AR) ts $@ > /dev/null
+
+libautomata.$(LIBEXT): $(LOBJ)
+	$(CC) $(LIBFLAGS) -o $@ $(LOBJ) $(LDFLAGS)
+
+check: $(TEST)
+	@set -e;\
+	for t in $(TEST); do\
+		printf '%s ' $(CHECK_PREFIX) "./$$t"; printf '\n';\
+		$(CHECK_PREFIX) ./"$$t";\
+	done
+
+install: libautomata.a libautomata.$(LIBEXT)
+	mkdir -p -- "$(DESTDIR)$(PREFIX)/lib"
+	mkdir -p -- "$(DESTDIR)$(PREFIX)/include"
+	cp -- libautomata.a "$(DESTDIR)$(PREFIX)/lib/"
+	cp -- libautomata.$(LIBEXT) "$(DESTDIR)$(PREFIX)/lib/libautomata.$(LIBMINOREXT)"
+	$(FIX_INSTALL_NAME) "$(DESTDIR)$(PREFIX)/lib/libautomata.$(LIBMINOREXT)"
+	ln -sf -- libautomata.$(LIBMINOREXT) "$(DESTDIR)$(PREFIX)/lib/libautomata.$(LIBMAJOREXT)"
+	ln -sf -- libautomata.$(LIBMAJOREXT) "$(DESTDIR)$(PREFIX)/lib/libautomata.$(LIBEXT)"
+	cp -- libautomata.h "$(DESTDIR)$(PREFIX)/include/"
+
+uninstall:
+	-rm -f -- "$(DESTDIR)$(PREFIX)/lib/libautomata.a"
+	-rm -f -- "$(DESTDIR)$(PREFIX)/lib/libautomata.$(LIBMAJOREXT)"
+	-rm -f -- "$(DESTDIR)$(PREFIX)/lib/libautomata.$(LIBMINOREXT)"
+	-rm -f -- "$(DESTDIR)$(PREFIX)/lib/libautomata.$(LIBEXT)"
+	-rm -f -- "$(DESTDIR)$(PREFIX)/include/libautomata.h"
+
+clean:
+	-rm -f -- *.o *.a *.lo *.su *.so *.so.* *.dll *.dylib
+	-rm -f -- *.gch *.gcov *.gcno *.gcda *.$(LIBEXT)
+	-rm -f -- *.t *.to
+
+.SUFFIXES:
+.SUFFIXES: .lo .o .c .t .to
+
+.PHONY: all check install uninstall clean
diff --git a/README b/README
new file mode 100644
index 0000000..e65fa24
--- /dev/null
+++ b/README
@@ -0,0 +1,18 @@
+NAME
+	libautomata - Stateful automata based string matching
+
+SYNOPSIS
+	#include <libautomata.h>
+
+	Link with -lautomata.
+
+DESCRIPTION
+	libautomata provides function for creating, string
+	matching automata that can be feed in chunks, allowing
+	online processing of massive data sets. The automata
+	are resetable and clonable, allowing the user to search
+	multiple data sets but only run the automata building
+	phase once.
+
+SEE ALSO
+	None.
diff --git a/common.h b/common.h
new file mode 100644
index 0000000..0e132a1
--- /dev/null
+++ b/common.h
@@ -0,0 +1,45 @@
+/* See LICENSE file for copyright and license details. */
+#include "libautomata.h"
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+#define sizeof_flexstruct(STRUCT, MEMBER, COUNT)\
+	(offsetof(STRUCT, MEMBER) + (COUNT) * sizeof(*((STRUCT *)NULL)->MEMBER))
+
+
+#define sizeof_kmp_automaton(LENGTH, ELEMSIZE)\
+	(sizeof_flexstruct(struct libautomata_kmp_automaton, next, (LENGTH) + 1U) + (LENGTH) * (ELEMSIZE))
+struct libautomata_kmp_automaton {
+	size_t position;
+	size_t length;
+	size_t elemsize;
+	size_t next[/* .length + 1U */];
+	/* char pattern[.length * .elemsize] */
+};
+
+
+#define sizeof_mp_automaton(LENGTH, ELEMSIZE)\
+	(sizeof_flexstruct(struct libautomata_mp_automaton, next, (LENGTH) + 1U) + (LENGTH) * (ELEMSIZE))
+struct libautomata_mp_automaton {
+	size_t position;
+	size_t length;
+	size_t elemsize;
+	size_t next[/* .length + 1U */];
+	/* char pattern[.length * .elemsize] */
+};
+
+
+#ifdef TEST
+# include <stdio.h>
+# define MEM(STR) STR, (sizeof(STR) - 1U)
+# define EXPECT(EXPR)\
+	do {\
+		if (EXPR)\
+			break;\
+		fprintf(stderr, "Assertion failed at %s:%i: %s\n", __FILE__, __LINE__, #EXPR);\
+		exit(1);\
+	} while (0)
+#endif
diff --git a/config.mk b/config.mk
new file mode 100644
index 0000000..f4adf12
--- /dev/null
+++ b/config.mk
@@ -0,0 +1,8 @@
+PREFIX    = /usr
+MANPREFIX = $(PREFIX)/share/man
+
+CC = c99
+
+CPPFLAGS = -D_DEFAULT_SOURCE -D_BSD_SOURCE -D_XOPEN_SOURCE=700 -D_GNU_SOURCE
+CFLAGS   =
+LDFLAGS  =
diff --git a/libautomata.h b/libautomata.h
new file mode 100644
index 0000000..4f6caeb
--- /dev/null
+++ b/libautomata.h
@@ -0,0 +1,24 @@
+/* See LICENSE file for copyright and license details. */
+#ifndef LIBAUTOMATA_H
+#define LIBAUTOMATA_H
+
+#include <stddef.h>
+
+
+/* Knuth–Morris–Pratt substring search (finds end of substring) */
+typedef struct libautomata_kmp_automaton LIBAUTOMATA_KMP_AUTOMATON;
+void libautomata_reset_kmp_automaton(LIBAUTOMATA_KMP_AUTOMATON *automaton);
+LIBAUTOMATA_KMP_AUTOMATON *libautomata_clone_kmp_automaton(const LIBAUTOMATA_KMP_AUTOMATON *automaton);
+LIBAUTOMATA_KMP_AUTOMATON *libautomata_compile_kmp_automaton(const void *pattern, size_t length, size_t elemsize);
+void *libautomata_execute_kmp_automaton(const void *haystack, size_t length, LIBAUTOMATA_KMP_AUTOMATON *automaton);
+
+
+/* Morris–Pratt substring search (finds end of substring) */
+typedef struct libautomata_mp_automaton LIBAUTOMATA_MP_AUTOMATON;
+void libautomata_reset_mp_automaton(LIBAUTOMATA_MP_AUTOMATON *automaton);
+LIBAUTOMATA_MP_AUTOMATON *libautomata_clone_mp_automaton(const LIBAUTOMATA_MP_AUTOMATON *automaton);
+LIBAUTOMATA_MP_AUTOMATON *libautomata_compile_mp_automaton(const void *pattern, size_t length, size_t elemsize);
+void *libautomata_execute_mp_automaton(const void *haystack, size_t length, LIBAUTOMATA_MP_AUTOMATON *automaton);
+
+
+#endif
diff --git a/libautomata_clone_kmp_automaton.c b/libautomata_clone_kmp_automaton.c
new file mode 100644
index 0000000..b862f23
--- /dev/null
+++ b/libautomata_clone_kmp_automaton.c
@@ -0,0 +1,13 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+
+
+LIBAUTOMATA_KMP_AUTOMATON *
+libautomata_clone_kmp_automaton(const LIBAUTOMATA_KMP_AUTOMATON *automaton)
+{
+	size_t size = sizeof_kmp_automaton(automaton->length, automaton->elemsize);
+	LIBAUTOMATA_KMP_AUTOMATON *ret = malloc(size);
+	if (ret)
+		memcpy(ret, automaton, size);
+	return ret;
+}
diff --git a/libautomata_clone_mp_automaton.c b/libautomata_clone_mp_automaton.c
new file mode 100644
index 0000000..f72d268
--- /dev/null
+++ b/libautomata_clone_mp_automaton.c
@@ -0,0 +1,9 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+
+
+LIBAUTOMATA_MP_AUTOMATON *
+libautomata_clone_mp_automaton(const LIBAUTOMATA_MP_AUTOMATON *automaton)
+{
+	return (void *)libautomata_clone_kmp_automaton((const void *)automaton);
+}
diff --git a/libautomata_compile_kmp_automaton.c b/libautomata_compile_kmp_automaton.c
new file mode 100644
index 0000000..3917b00
--- /dev/null
+++ b/libautomata_compile_kmp_automaton.c
@@ -0,0 +1,46 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+
+
+LIBAUTOMATA_KMP_AUTOMATON *
+libautomata_compile_kmp_automaton(const void *pattern, size_t length, size_t elemsize)
+{
+	size_t i = 0, j = SIZE_MAX;
+	size_t size = sizeof_kmp_automaton(length, elemsize);
+	LIBAUTOMATA_KMP_AUTOMATON *ret = malloc(size);
+
+	if (!ret)
+		return NULL;
+
+	ret->position = 0;
+	ret->length = length;
+	ret->elemsize = elemsize;
+	memcpy((void *)&ret->next[length + 1U], pattern, length * elemsize);
+
+#define INTRINSIC(TYPE)\
+	(((const TYPE *)pattern)[i] == ((const TYPE *)pattern)[j])
+
+#define MEMCMP(WIDTH)\
+	(!memcmp(&((const char *)pattern)[i * (WIDTH)], &((const char *)pattern)[j * (WIDTH)], (WIDTH)))
+
+#define IMPLEMENT(EQ, EQ_PARAM, CASE)\
+	while (i < length) {\
+		if (j != SIZE_MAX && !(EQ(EQ_PARAM)))\
+			j = ret->next[j];\
+		i++;\
+		j++;\
+		if (EQ(EQ_PARAM))\
+			ret->next[i] = ret->next[j];\
+		else CASE:\
+			ret->next[i] = j;\
+	}\
+	return ret
+
+	switch (elemsize) {
+		IMPLEMENT(INTRINSIC, uint8_t, case sizeof(uint8_t));
+		IMPLEMENT(INTRINSIC, uint16_t, case sizeof(uint16_t));
+		IMPLEMENT(INTRINSIC, uint32_t, case sizeof(uint32_t));
+		IMPLEMENT(INTRINSIC, uint64_t, case sizeof(uint64_t));
+		IMPLEMENT(MEMCMP, elemsize, default);
+	}
+}
diff --git a/libautomata_compile_mp_automaton.c b/libautomata_compile_mp_automaton.c
new file mode 100644
index 0000000..b9e8739
--- /dev/null
+++ b/libautomata_compile_mp_automaton.c
@@ -0,0 +1,44 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+
+
+LIBAUTOMATA_MP_AUTOMATON *
+libautomata_compile_mp_automaton(const void *pattern, size_t length, size_t elemsize)
+{
+	size_t i = 0, j = SIZE_MAX;
+	size_t size = sizeof_mp_automaton(length, elemsize);
+	LIBAUTOMATA_MP_AUTOMATON *ret = malloc(size);
+
+	if (!ret)
+		return NULL;
+
+	ret->position = 0;
+	ret->length = length;
+	ret->elemsize = elemsize;
+	memcpy((void *)&ret->next[length + 1U], pattern, length * elemsize);
+
+#define INTRINSIC(TYPE)\
+	(((const TYPE *)pattern)[i] == ((const TYPE *)pattern)[j])
+
+#define MEMCMP(WIDTH)\
+	(!memcmp(&((const char *)pattern)[i * (WIDTH)], &((const char *)pattern)[j * (WIDTH)], (WIDTH)))
+
+#define IMPLEMENT(EQ, EQ_PARAM, CASE)\
+	while (i < length) {\
+		if (j != SIZE_MAX && !(EQ(EQ_PARAM)))\
+			j = ret->next[j];\
+		i++;\
+		j++;\
+	CASE:\
+		ret->next[i] = j;\
+	}\
+	return ret
+
+	switch (elemsize) {
+		IMPLEMENT(INTRINSIC, uint8_t, case sizeof(uint8_t));
+		IMPLEMENT(INTRINSIC, uint16_t, case sizeof(uint16_t));
+		IMPLEMENT(INTRINSIC, uint32_t, case sizeof(uint32_t));
+		IMPLEMENT(INTRINSIC, uint64_t, case sizeof(uint64_t));
+		IMPLEMENT(MEMCMP, elemsize, default);
+	}
+}
diff --git a/libautomata_execute_kmp_automaton.c b/libautomata_execute_kmp_automaton.c
new file mode 100644
index 0000000..69ffcce
--- /dev/null
+++ b/libautomata_execute_kmp_automaton.c
@@ -0,0 +1,40 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+
+
+void *
+libautomata_execute_kmp_automaton(const void *haystack, size_t length, LIBAUTOMATA_KMP_AUTOMATON *automaton)
+{
+	const void *pattern = (void *)&automaton->next[automaton->length + 1U];
+	size_t i = 0;
+
+#define INTRINSIC(TYPE)\
+	(((const TYPE *)pattern)[automaton->position] == ((const TYPE *)haystack)[i])
+
+#define MEMCMP(WIDTH)\
+	(!memcmp(&((const char *)pattern)[automaton->position * automaton->elemsize],\
+	         &((const char *)haystack)[i * automaton->elemsize],\
+	         automaton->elemsize))
+
+#define IMPLEMENT(EQ, EQ_PARAM)\
+	while (i < length) {\
+		while (automaton->position != SIZE_MAX && !(EQ(EQ_PARAM)))\
+			automaton->position = automaton->next[automaton->position];\
+		i++;\
+		if (++automaton->position == automaton->length)\
+			goto found;\
+	}\
+	return NULL
+
+	switch (automaton->elemsize) {
+	case sizeof(uint8_t):  IMPLEMENT(INTRINSIC, uint8_t);
+	case sizeof(uint16_t): IMPLEMENT(INTRINSIC, uint16_t);
+	case sizeof(uint32_t): IMPLEMENT(INTRINSIC, uint32_t);
+	case sizeof(uint64_t): IMPLEMENT(INTRINSIC, uint64_t);
+	default:               IMPLEMENT(MEMCMP, elemsize);
+	}
+
+found:
+	automaton->position = automaton->next[automaton->position];
+	return &(*(char **)(void *)&haystack)[i];
+}
diff --git a/libautomata_execute_mp_automaton.c b/libautomata_execute_mp_automaton.c
new file mode 100644
index 0000000..13692dd
--- /dev/null
+++ b/libautomata_execute_mp_automaton.c
@@ -0,0 +1,9 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+
+
+void *
+libautomata_execute_mp_automaton(const void *haystack, size_t length, LIBAUTOMATA_MP_AUTOMATON *automaton)
+{
+	return libautomata_execute_kmp_automaton(haystack, length, (void *)automaton);
+}
diff --git a/libautomata_reset_kmp_automaton.c b/libautomata_reset_kmp_automaton.c
new file mode 100644
index 0000000..23f6049
--- /dev/null
+++ b/libautomata_reset_kmp_automaton.c
@@ -0,0 +1,9 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+
+
+void
+libautomata_reset_kmp_automaton(LIBAUTOMATA_KMP_AUTOMATON *automaton)
+{
+	automaton->position = 0;
+}
diff --git a/libautomata_reset_mp_automaton.c b/libautomata_reset_mp_automaton.c
new file mode 100644
index 0000000..f3f78da
--- /dev/null
+++ b/libautomata_reset_mp_automaton.c
@@ -0,0 +1,9 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+
+
+void
+libautomata_reset_mp_automaton(LIBAUTOMATA_MP_AUTOMATON *automaton)
+{
+	automaton->position = 0;
+}
diff --git a/mk/linux.mk b/mk/linux.mk
new file mode 100644
index 0000000..ad58f69
--- /dev/null
+++ b/mk/linux.mk
@@ -0,0 +1,6 @@
+LIBEXT      = so
+LIBFLAGS    = -shared -Wl,-soname,lib$(LIB_NAME).$(LIBEXT).$(LIB_MAJOR)
+LIBMAJOREXT = $(LIBEXT).$(LIB_MAJOR)
+LIBMINOREXT = $(LIBEXT).$(LIB_VERSION)
+
+FIX_INSTALL_NAME = :
diff --git a/mk/macos.mk b/mk/macos.mk
new file mode 100644
index 0000000..b7d9358
--- /dev/null
+++ b/mk/macos.mk
@@ -0,0 +1,6 @@
+LIBEXT      = dylib
+LIBFLAGS    = -dynamiclib -Wl,-compatibility_version,$(LIB_MAJOR) -Wl,-current_version,$(LIB_VERSION)
+LIBMAJOREXT = $(LIB_MAJOR).$(LIBEXT)
+LIBMINOREXT = $(LIB_VERSION).$(LIBEXT)
+
+FIX_INSTALL_NAME = install_name_tool -id "$(PREFIX)/lib/libautomata.$(LIBMAJOREXT)"
diff --git a/mk/windows.mk b/mk/windows.mk
new file mode 100644
index 0000000..ed5ec8d
--- /dev/null
+++ b/mk/windows.mk
@@ -0,0 +1,6 @@
+LIBEXT      = dll
+LIBFLAGS    = -shared
+LIBMAJOREXT = $(LIB_MAJOR).$(LIBEXT)
+LIBMINOREXT = $(LIB_VERSION).$(LIBEXT)
+
+FIX_INSTALL_NAME = :
diff --git a/test_kmp_automaton.c b/test_kmp_automaton.c
new file mode 100644
index 0000000..fa824e4
--- /dev/null
+++ b/test_kmp_automaton.c
@@ -0,0 +1,48 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+
+
+int
+main(void)
+{
+	LIBAUTOMATA_KMP_AUTOMATON *a1, *a2;
+	const char *r;
+
+	EXPECT((a1 = libautomata_compile_kmp_automaton(MEM("es"), 1)));
+	EXPECT((a2 = libautomata_clone_kmp_automaton(a1)));
+
+	r = libautomata_execute_kmp_automaton(MEM("test"), a1);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "t"));
+	r = libautomata_execute_kmp_automaton(MEM("test"), a1);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "t"));
+	libautomata_reset_kmp_automaton(a1);
+	r = libautomata_execute_kmp_automaton(MEM("test"), a1);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "t"));
+	r = libautomata_execute_kmp_automaton(MEM("test"), a2);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "t"));
+	r = libautomata_execute_kmp_automaton(MEM("te"), a1);
+	EXPECT(!r);
+	r = libautomata_execute_kmp_automaton(MEM("sting"), a1);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "ting"));
+	r = libautomata_execute_kmp_automaton(MEM("te"), a1);
+	EXPECT(!r);
+	libautomata_reset_kmp_automaton(a1);
+	r = libautomata_execute_kmp_automaton(MEM("sting"), a1);
+	EXPECT(!r);
+
+	free(a1);
+	free(a2);
+
+	EXPECT((a1 = libautomata_compile_kmp_automaton(MEM("nano"), 1)));
+	r = libautomata_execute_kmp_automaton(MEM("searching for a nanostring"), a1);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "string"));
+	free(a1);
+
+	return 0;
+}
diff --git a/test_mp_automaton.c b/test_mp_automaton.c
new file mode 100644
index 0000000..f6b41ff
--- /dev/null
+++ b/test_mp_automaton.c
@@ -0,0 +1,48 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+
+
+int
+main(void)
+{
+	LIBAUTOMATA_MP_AUTOMATON *a1, *a2;
+	const char *r;
+
+	EXPECT((a1 = libautomata_compile_mp_automaton(MEM("es"), 1)));
+	EXPECT((a2 = libautomata_clone_mp_automaton(a1)));
+
+	r = libautomata_execute_mp_automaton(MEM("test"), a1);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "t"));
+	r = libautomata_execute_mp_automaton(MEM("test"), a1);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "t"));
+	libautomata_reset_mp_automaton(a1);
+	r = libautomata_execute_mp_automaton(MEM("test"), a1);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "t"));
+	r = libautomata_execute_mp_automaton(MEM("test"), a2);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "t"));
+	r = libautomata_execute_mp_automaton(MEM("te"), a1);
+	EXPECT(!r);
+	r = libautomata_execute_mp_automaton(MEM("sting"), a1);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "ting"));
+	r = libautomata_execute_mp_automaton(MEM("te"), a1);
+	EXPECT(!r);
+	libautomata_reset_mp_automaton(a1);
+	r = libautomata_execute_mp_automaton(MEM("sting"), a1);
+	EXPECT(!r);
+
+	free(a1);
+	free(a2);
+
+	EXPECT((a1 = libautomata_compile_mp_automaton(MEM("nano"), 1)));
+	r = libautomata_execute_mp_automaton(MEM("searching for a nanostring"), a1);
+	EXPECT(r);
+	EXPECT(!strcmp(r, "string"));
+	free(a1);
+
+	return 0;
+}