1 files changed, 48 insertions, 0 deletions
diff --git a/src/base/string/raw/find.c b/src/base/string/raw/find.c
new file mode 100644
index 0000000..3faf040
--- /dev/null
+++ b/src/base/string/raw/find.c
@@ -0,0 +1,48 @@
+#include <u.h>
+#include <base/memory.h>
+#include <base/string.h>
+
+char *
+str·find(char *h, char *n)
+{
+    char *s, *ih, *in;
+    intptr i, sum, len;
+
+    if(!n || !n[0])
+        return h;
+
+    if(!h || !h[0])
+        return nil;
+
+    /* two way string matching */
+
+    /* align first characters */
+    if(!(s = str·findc(h, n[0])))
+        return nil;
+
+    ih = s+1;
+    in = n+1;
+    i = 1, sum = 0;
+    while(*ih && *in){
+        sum += *ih;
+        sum -= *in;
+        i &= (*ih++ == *in++);
+    }
+
+    if(*in) /* needle is larger than haystack! */
+        return nil;
+    else if(i) /* found match */
+        return s;
+
+    /* no hit: loop for remainder of haystack
+     * if prefix sum ever falls to zero, we have equal hashes
+     * compare! */
+    len = in - n - 1;
+    for(; *ih; ih++){
+        sum -= *s++; /* sub the last character, advance the location on haystack */
+        sum += *ih;  /* add the next character */
+        if(sum == 0 && mem·compare(s, len, n)==0)
+            return s;
+    }
+    return nil;
+}