Re: [OT] The interesting problem of comparing bit-strings.

[marinersk]

Quick thought, as I won't have time to dedicate to code-example before tonight, but in case it sparks a line of thought for you -- This is specifically to address the "I don't want it to keep rotating the bits over and over again" problem.

Might a combination of rotation and mask help?

Have an initializer which sets up all possible aligned bitmask searches, and then a routine which loops through all the pre-built masks looking for a match?

In this short example which will likely be fraught with errors, assuming we are looking for 0b1010 in 0b00110100101. For readability's sake, this example plays on an 8-bit alignment requirement; simply increase the work of the initializer and searcher routines to take advantage of 64-bit alignment capabilities.

The initializer sets up the following array of pre-rotated bitmasks:

    mask[0] = 0b11110000;
    mask[1] = 0b01111000;
    mask[2] = 0b00111100;
    mask[3] = 0b00011110;
    mask[4] = 0b00001111;

I'm running on light air here, I think you'll need to also set up an array of pre-rotated comparison bitstrings:

    seabits[0] = 0b10100000;
    seabits[1] = 0b01010000;
    seabits[2] = 0b00101000;
    seabits[3] = 0b00010100;
    seabits[4] = 0b00001010;

Then the main comparison routine iterates across the main bit buffer using these pre-built masks and values to ascertain if there is a match.

Multilingual psuedocode for the main comparison routine:

    for (chunkcol = 0; chunkcol < (BitBufferLength / CHUNKSIZE); chunk
+col++)
    {
         foreach $masknum (@mask)
         {
              if ( ( BitBuffer[chunkcol] & mask[$masknum] ) == $seabit
+s[$masknum])
              {
                   return ( ( chunkcol * CHUNKSIZE) + $masknum );     
+# FIXME:  Check for fenceposting error(s)
              }
         }
    }
    
    return ($RET_NOTFOUND);

I should think a static accumulator can track which bit column you find the match in and simply exit the loop returning that value?

I started coding a proof-of-concept in Perl but as soon as I got into the guts of it I knew this was going to take me longer than I have left this morning.

Hope this got my point across and hope it either yields some inspiration or you already thought of it and have moved on. :-)

Update: Fixed bitmask and searchbits arrays.
Update: Added psuedocode.
Update: Updated chunking in psuedocode.