#include <u.h>
#include <base/memory.h>
#include <base/string.h>

char *
str·nfind(char *h, intptr len, char *n)
{
    char *s, *ih, *in;
    intptr i, sum, sz;

    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;

    len -= (s-h);
    sz = len;

    ih = s+1;
    in = n+1;
    i = 1, sum = 0;
    while(*ih && *in && len-- > 0){
        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! */
    sz = in - n - 1;
    for(len=sz; *ih && len>0; ih++,len--){
        sum -= *s++; /* sub the last character, advance the location on haystack */
        sum += *ih;  /* add the next character */
        if(sum == 0 && mem·compare(s, sz, n)==0)
            return s;
    }
    return nil;
}