title: Find a repeating symmetric bit pattern in a small stream of 128 bits
body: <p>How can I quickly scan groups of 128 bits that are exact equal repeating binary patterns, such 010101... Or 0011001100...?</p>
  
  <p>I have a number of 128 bit blocks, and wish to see if they match the patterns where the number of 1s is equal to number of 0s, eg 010101.... Or 00110011...  Or 0000111100001111... But NOT 001001001...</p>
  
  <p>The problem is that patterns may not start on their boundary, so the pattern 00110011.. May begin as 0110011..., and will end 1 bit shifted also (note the 128 bits are not circular, so start doesn't join to the end)</p>
  
  <p>The 010101... Case is easy, it is simply 0xAAAA... Or 0x5555....   However as the patterns get longer, the permutations get longer. Currently I use repeating shifting values such as outlined in this question <a href="https://stackoverflow.com/questions/1572290/fastest-way-to-scan-for-bit-pattern-in-a-stream-of-bits">Fastest way to scan for bit pattern in a stream of bits</a> but something quicker would be nice, as I'm spending 70% of all CPU in this routine. Other posters have solutions for general cases but I am hoping the symmetric nature of my pattern might lead to something more optimal.</p>
  
  <p>If it helps, I am only interested in patterns up to 63 bits long, and most interested in the power of 2 patterns (0101...  00110011...   0000111100001111... Etc) while patterns such as 5 ones/5 zeros are present, these non power 2 sequences are less than 0.1%, so can be ignored if it helps the common cases go quicker.</p>
  
  <p>Other constraints for a perfect solution would be small number of assembler instructions, no wildly random memory access (ie, large rainbow tables not ideal). </p>
  
  <p>Edit. More precise pattern details.</p>
  
  <p>I am mostly interested in the patterns of 0011 and 0000,1111 and 0000,0000,1111,1111 and 16zeros/ones and 32 zeros/ones (commas for readabily only) where each pattern repeats continuously within the 128 bits. Patterns that are not 2,4,8,16,32 bits long for the repeating portion are not as interesting and can be ignored. ( eg 000111... )</p>
  
  <p>The complexity for scanning is that the pattern may start at any position, not just on the 01 or 10 transition. So for example, all of the following would match the 4 bit repeating pattern of 00001111... (commas every 4th bit for readability) (ellipses means repeats identically)</p>
  
  <p>0000,1111.... Or 0001,1110... Or 0011,1100... Or 0111,1000... Or 1111,0000... Or 1110,0001... Or 1100,0011...  Or 1000,0111</p>
  
  <p>Within the 128bits, the same pattern needs to repeat, two different patterns being present is not of interest.  Eg this is NOT a valid pattern. 0000,1111,0011,0011...  As we have changed from 4 bits repeating to 2 bits repeating.</p>
  
  <p>I have already verified the number of 1s is 64, which is true for all power 2 patterns, and now need to identify how many bits make up the repeating pattern (2,4,8,16,32) and how much the pattern is shifted.  Eg pattern 0000,1111 is a 4 bit pattern, shifted 0.  While 0111,1000... Is a 4 bit pattern shifted 3.</p>