Okay. I succeeded in getting the caching variant to compile, but it crashes for needles > 20 bits. (Note: almost certainly down to changes I have to make to get it to compile here (LLP64 v lp64 changes), but since I do not understand the code, and there's nothing to reference it against, introducing bugs was almost inevitable.)

But, 2 days banging my head is enough. I don't need to prove your point for you. Here is a simple version of my brute-force bitstrnstrn(), if you're motivated to finish your code and compare, be my guest.

Note:the eclectic ordering of the parameters bitstrnstrn( &hay, &pin, bit_offset_hay, bit_offset_pin, bit_len_hay, bit_len_pin ), means that the values most needing to be in registers, automatically are as a consequence of the x64 calling convention (for my compiler).

#define SL( v, o ) __shiftleft128( *((v)+1), *((v)), o )

__forceinline
U8 cmpBits( const register U64 *hay, const register U64 *pin, U8 regis
+ter ohay, U8 register opin, U64 lpin ) {
    U64 register i;

    for( i=0; i < lpin/64; ++i, ++hay, ++pin ) {
        if( SL( hay, ohay ) != SL( pin, opin ) ) return 0;
    }
    {
        U8 lastbits = lpin % 64;
        U64 mask = ( ( 1ull << ( lastbits ) ) -1 ) << ( 64 - lastbits 
+);
        if( ( SL( hay, ohay ) & mask ) != ( SL( pin, opin ) & mask ) )
+ return 0;
    }
    return 1;
}

U64 bitstrnstrn( const register U64 *hay, const register U64 *pin, U8 
+register ohay, U8 register opin, U64 lhay, U64 lpin ) {
    U64 register i;

    for( i = ohay; i < lhay+ohay; ++i ) {
        if( cmpBits( hay+(i/64), pin, i%64, opin, lpin ) ) return i;
    }
    return -1;
}
[download]