11.13 Searching for a Bit Pattern

Another bit-related operation you may need is the ability to search for a particular bit pattern in a string of bits. For example, you might want to locate the bit index of the first occurrence of %1011 starting at some particular position in a bit string. In this section we'll explore some simple algorithms to accomplish this task.

To search for a particular bit pattern we're going to need to know four things: (1) the pattern to search for (the pattern), (2) the length of the pattern we're searching for, (3) the bit string that we're going to search through (the source), and (4) the length of the bit string to search through. The basic idea behind the search is to create a mask based on the length of the pattern and mask a copy of the source with this value. Then we can directly compare the pattern with the masked source for equality. If they are equal, you're done; if they're not equal, then increment a bit position counter, shift the source one position to the right, and try again. You repeat this operation length(source) - length(pattern) times. The algorithm fails if it does not detect the bit pattern after this many attempts (because we will have exhausted all the bits in the source operand that could match the pattern's length). Here's a simple algorithm that searches for a 4-bit pattern throughout the EBX register:

               mov( 28, cl );      // 28 attempts because 32-4 = 28 (len(src)-                                    // len(pat)).               mov( %1111, ch );   // Mask for the comparison.               mov( pattern, al ); // Pattern to search for.               and( ch, al );      // Mask unnecessary bits in AL.               mov( source, ebx ); // Get the source value. ScanLp:       mov( bl, dl );      // Make a copy of the L.O. four bits of EBX               and( ch, dl );      // Mask unwanted bits.               cmp( dl, al );      // See if we match the pattern.               jz Matched;               dec( cl );          // Repeat the specified number of times.               jnz ScanLp;      << If we get to this point, we failed to match the bit string >>               jmp Done; Matched:      << If we get to this point, we matched the bit string. We can >>      << compute the position in the original source as 28-cl. >> Done:

Bit string scanning is a special case of string matching. String matching is a well studied problem in computer science, and many of the algorithms you can use for string matching are applicable to bit string matching as well. Such algorithms are a bit beyond the scope of this chapter, but to give you a preview of how this works, you compute some function (like xor or sub) between the pattern and the current source bits and use the result as an index into a look-up table to determine how many bits you can skip. Such algorithms let you skip several bits rather than only shifting once for each iteration of the scanning loop (as is done by the previous algorithm).