1 files changed, 89 insertions, 0 deletions
diff --git a/test/benchmarks/search-kmp.c b/test/benchmarks/search-kmp.c
new file mode 100644
index 0000000..79ba9c8
--- /dev/null
+++ b/test/benchmarks/search-kmp.c
@@ -0,0 +1,89 @@
+struct result_buf {
+	unsigned long array[24*1024*1024];
+	int len;
+};
+
+struct result_buf rbuf;
+
+int read(int fd, void *buf, unsigned long len);
+void *malloc(unsigned long);
+long strlen(char *);
+int open(char *, int flags, long mode);
+int printf(char *, ...);
+void exit(int);
+
+static void compute_pi(char *p, int len, int *pibuf)
+{
+	int k = 0;
+	int q;
+	pibuf[0] = 0;
+	for (q = 1; q < len; ++q) {
+		while (k > 0 && p[k] != p[q])
+			k = pibuf[k];
+		if (p[k] == p[q])
+			++k;
+		pibuf[q] = k;
+	}
+}
+
+void kmp(char *p, int plen, char *t, int tlen)
+{
+	int i, q = 0;
+	int *pibuf = malloc(sizeof(int) * plen);
+
+	compute_pi(p, plen, pibuf);
+
+	for (i = 0; i < tlen; ++i) {
+		while (q > 0 && p[q] != t[i])
+			q = pibuf[q-1];
+		if (p[q] == t[i])
+			++q;
+		if (q == plen) {
+			rbuf.array[rbuf.len] = i + 1 - plen;
+			++rbuf.len;
+			q = pibuf[q-1];
+		}
+	}
+
+}
+
+void *read_file(int fd, int *len)
+{
+	int size = 1500 * 1024 * 1024;
+	unsigned char *arr = malloc(size);
+	int i;
+	for (i = 0; ;) {
+		int rd = read(fd, arr + i, size - i);
+		if (rd < 0)
+			exit(2);
+		if (rd == 0)
+			break;
+		i += rd;
+	}
+
+	*len = i;
+	return arr;
+}
+
+int main(int argc, char **argv)
+{
+	int i, slen;
+	long sum = 0;
+	char *needle, *buf;
+	int fd = open(argv[1], 0, 0);
+
+	if (fd == -1)
+		return 1;
+
+	needle = argv[2];
+	buf = read_file(fd, &slen);
+	printf("len: %d\n", slen);
+
+	kmp(needle, strlen(needle), buf, slen);
+
+	for (i = 0; i < rbuf.len; ++i)
+		sum += rbuf.array[i];
+	printf("%ld\n", sum);
+
+	return 0;
+}