#include <stdio.h>
#include <stdlib.h>
//#include <stdint.h>
#include <string.h>
//#include <unistd.h>

//typedef uint32_t U32;
//typedef uint16_t U16;

typedef unsigned __int64 U64;
typedef unsigned __int32 U32;
typedef unsigned __int16 U16;
typedef unsigned __int8   U8;

enum { M = 8192, logM = 13, Mmask = M - 1, Mskip = M - logM + 1, Mnil 
+};


typedef struct {
    U16 head[M], next[M];       // index chains
} skiptab;

// extract logM bits at bit offset i. assert(logM <= 16)
static __inline size_t fbits(char *v, size_t i)
{
    U32 *x = (U32 *)&v[2 * (i >> 4)];
    return Mmask & (*x >> (i & 15));
}

// 'tis rotten. should make shifted copies of x and memcmp the middle.
static size_t xcmp(char *y, size_t j, char *x)
{
    size_t i, diff = fbits(y, j) - fbits(x, 0);

    for (i = M % logM; i < M && !diff; i += logM) {
        diff = fbits(y, i + j) - fbits(x, i);
    }
    return diff;
}

static void prep(char *x, skiptab *Z)
{
    size_t i, f;
    for (i = 0; i < M; i++) {
        Z->head[i] = Mnil;
    }
    for (i = 0; i < Mskip; i++) {
        f = fbits(x, i);
        Z->next[i] = Z->head[f];
        Z->head[f] = i;
    }
}

// y of length n is haystack; x is the needle
size_t search(char *y, size_t n, char *x, size_t m)
{
    skiptab Z[1];
    size_t i, j;        // assert(m == M);

    prep(x, Z);

    n -= logM;
    for (i = -1; (i += Mskip) <= n;) {
        j = fbits(y, i);

        for (j = Z->head[j]; j != Mnil; j = Z->next[j]) {
            if (!xcmp(y, i-j, x))
                return i-j;
        }
    }
    return -1;
}

// one-bit rotate
void rot1(char *v, size_t n)
{
    size_t i, c;
    for (c = i = 0; i < n; c >>= 8, i++) {
        v[i] = c += *(unsigned char *)(v+i) << 1;
    }
    v[0] += c;
}

int main( int argc, char **argv ) {
    U64 hay[1] = { 0xdeadbeefdeadbeef };
    U64 ndl[1] = { 0xdeadbeefdeadbeef };
    U64 start, end, found = 0;

    start = __rdtsc();
    found = search( (char*)hay, sizeof(hay)*8, (char*)ndl, sizeof(ndl)
+*8 );
    _ReadBarrier();
    end = __rdtsc();
    printf( "Result %12d\t", found );
    printf( "Took %9e secs\n", (double)( end - start ) / 2394046359.0 
+);

    return 0;
}
[download]