The interesting problem of comparing bit-strings.

Perl's vec and bitwise string operators are very useful and powerful for manipulating (large) bitstrings; but they are limited in several ways.

Namely, there are no left & right shift operators for them; and the bitwise string operators operate with 8-bit boundaries.

One common operation needed for programming with bitstrings is the ability to search one bitstring for another bitstring, looking for matches that occur even at non-byte or integer-sized alignments.

So graphically, using 8-bit units instead of 64 for brevity, the problem is this:

Find (the first occurance of):

    needle = x1001010 10101001 10100xxx  (x represents bits we are not
+ interested in)
[download]

in:

    haystk = xxxxx001 10001101 01110010 10101010 01101001 01100011 100
+11001 00010001 .....
[download]

The specification of needle requires three values:

• *ndl : points to the first unit (8-bits above, 64-bits in reality) of the bitstring to find.
• oNdl : the offset, in bits, into the first unit, of the needle.
• lNdl : the length in bits of what we are looking for.

Similarly, the haystack requires 3 values:

• *hay : the address of the first unit of the bitstring to search.
• oHay : the offset, in bits, into the first unit of the haystack.
• lHay : the length, in bits, of the haystack.

The function required thus takes six arguments:

    U64 bsSearch( U64 *hay, U8 oHay, U64 lHay, U64 *ndl, U8 oNdl, U64 
+lNdl ) {
        ...
    }
[download]

Return value

In an ideal world (Perl) the function would return the unit number(or address), and the offset into that unit, where the match is found (or 0).

As C doesn't permit multiple return values, I've opted for a single 64-bit value indicating the offset from the start of the first unit of the haystack (or -1?).

Found:

    haystk = xxxxx001 10001101 01110010 10101010 01101001 01100011 100
+11001 00010001 .....
    needle =                     x10010 10101010 0110100x xx (note the
+ alignment change!)
    return = 01234567 89012345 6789 = 19th bit 
                                    = unit 2/ bit 3
[download]

There are 128-bit shift instructions available on Intel/AMD 64-bit processors (and probably most others):

 
    REX.W + 0F A5    SHLD r/m64, r64, CL     B  Valid    N.E.    Shift
+ r/m64 to left CL places while shifting bits from r64 in from the rig
+ht.
    REX.W + 0F AD    SHRD r/m64, r64, CL     B  Valid    N.E.    Shift
+ r/m64 to right CL places while shifting bits from r64 in from the le
+ft.
[download]

which are available on the MS compiler as intrinsics:

    unsigned __int64 __shiftleft128( unsigned __int64 LowPart, unsigne
+d __int64 HighPart, unsigned char Shift );
    unsigned __int64 __shiftright128( unsigned __int64 LowPart, unsign
+ed __int64 HighPart, unsigned char Shift );
[download]

and probably in gcc (though I couldn't locate the names).

Using these, you can load two registers with two units of one of the bitstrings and when shifting the first register, bits from the second are shifted in.

Thus to process through the bitstrings 1 bit at a time, you use loops something like:

    for( i = 0; i < ( lHay % 64 )+1; ++i ) {
        r1 = *( hay + i ); r2 = *( hay + i + 1 );
        for( b1 = 0; b1 < 64; ++b1 ){
            __shiftleft128( r2, r1, 1 );
        }
    }
[download]

and:

    for( j = 0; j < ( lNdl % 64 )+1; ++j ) {
        r3 = *( ndl + j ); r4 = *( ndl +j + 1 );
        for( b2 = 0; b2 < 64; ++b2 ) {
            __shiftleft128( r4, r3, 1 );
        }
    }
[download]

Except that:

1. the terminating conditions of the outer loops need work; (especially in light of b below).
2. the initialisation/repopulation of the two registers needs to take account of the bit offsets oHay & oNdl respectively.
3. the two loops need to run concurrently; with the second loop resetting to the starting condition everytime r1 != r3;
4. We might successfully match & advance through several units before hitting a mismatch.

   At which point we not only need to reset the needle (inner pair?) loop;

   we also need to reset the hay loop by the distance we successfully advanced before the failure, then advance one bit.

What have I tried so far?

In answer to the traditional question: You've just pretty much read it!

The function definition and a few local variables:

    U64 bsSearch( U64 *hay, U8 oHay, U64 lHay, U64 *ndl, U8 oNdl, U64 
+lNdl ) {
        register U64 r1, r2, r3, r4;
        U64 i, j, rv;
        U8  b1, b2;

        ...
        
        return rv;
    }
[download]

And the two separate loops above, and little else, despite many hours of though and scribbling on post-its.

I suspect that the right approach might include another subroutine that compares the needle to the haystack at a given, fixed offset; but I'm stuck for how to code that such that it doesn't repeatedly shift one or both by an increasing number of bits each time it is called?

I also thought that it might make sense to copy the needle to an aligned chunk of memory, to eliminate its offset from the problem; but it could be a very large piece of memory, which would be expensive.

Update:I suspect one or even two gotos may be needed; though I'd avoid them if I can.

What am I looking for?

Cluebats; pseudo-code; real-code of any flavour.

Basically anything that will make the penny drop as to how to code this beast?