#!/usr/bin/env python

import random
import pprint

def to_binstr(n,len):
    bv = [ "1" if n & (1<<x) else "0" for x in range(0, len)]
    return "".join(bv)

def brute_force(needle, haystack):
    """Brute-force find all matching positions of needle in haystack"""
    positions = []
    for i in range(0, len(haystack)-len(needle)+1):
        if needle == haystack[i:i+len(needle)]:
            positions.append(i)
    return positions

def spaces(n):
    return "".join([ " " for x in range(0, n)])

haystack = "00001110100111001011101101110001111010111100111110111111100000001000100100001010010101000001101000110010011000101101010110011011000000"
needle1  =                                                                         "000010100101010000011010"
needle   =                                                                        "100001010010101000001101"

hay_len = len(haystack)
symbol_size = 8                     # each symbol is 3 bits long
num_syms = 3                        # length of needle in "symbols"
needle_len = num_syms * symbol_size # our needle is two symbols long

# Use brute force to find all matches
positions = brute_force(needle, haystack)
ruler = "".join([ "^" if x in positions else " " for x in range(0, len(haystack)) ])
print haystack
print ruler
for ofs in positions:
    print "{0}{1}".format(spaces(ofs),needle)
print " "

# Find the locations of all symbol matches for selected symbol size
delta = [ -1 for i in range(0, (1<<symbol_size)) ]
dd1 = { }
for i in range(0, (1<<symbol_size)):
    sym = to_binstr(i, symbol_size)
    tmp = brute_force(sym, needle)
    if len(tmp)>0:
        bitofs = tmp[-1]
        delta[i] = bitofs
        dd1[sym] = bitofs

print "NEEDLE: ", needle
needle_syms = [ needle[i*symbol_size:(i+1)*symbol_size] for i in range(0, num_syms)]

# Search loop

ptr = len(needle) - symbol_size
while ptr < len(haystack):
    print haystack
    print ruler
    print "{0}^ (pos={1})".format(spaces(ptr-1), ptr)
    found = haystack[ptr - symbol_size:ptr]
    print "{0}{1}".format(spaces(ptr-symbol_size), found)
    print "{0}{1}".format(spaces(ptr-len(needle)), needle)


    if found in dd1:
        print "found {0}, delta=>{1}".format(found, dd1[found])
        if dd1[found] == (num_syms-1)*symbol_size:
            print "MATCHED!"
            break
        elif dd1[found]>0:
            print "shifting"
            ptr += dd1[found]
        else:
            print "WTF?"
            break
    else:
        print "not found, big shift"
        ptr += len(needle)-symbol_size