#!/usr/bin/env python
import string

def denary2binary(n):
    '''convert denary integer n to binary string bStr'''
    bStr = ''
    if n < 0: raise ValueError, "must be a positive integer"
    if n == 0: return '0'
    while n > 0:
        bStr = str(n % 2) + bStr
        n = n >> 1
    return bStr

def lfsr2a(r, iterations):
        j = 0
        while j < iterations:
                yield r[0]
                i1 = (r[0] + r[2] + r[3] + r[6] + r[7] + r[9] + r[11] + r[12]) % 2

                i = 0
                while i < len(r)-1:
                        r[i] = r[i+1]
                        i += 1

                r[13-1] = (i1) % 2
                j += 1

def lfsr2b(r, iterations):
        j = 0
        while j < iterations:
                yield r[0]
                i1 = (r[0] + r[2] + r[4] + r[5] + r[8] + r[9] + r[11] + r[13]) % 2

                i = 0
                while i < len(r)-1:
                        r[i] = r[i+1]
                        i += 1

                r[15-1] = (i1) % 2
                j += 1

def lfsr2c(r, iterations):
        j = 0
        while j < iterations:
                yield r[0]
                i1 = (r[0] + r[1] + r[4] + r[7] + r[9] + r[12] + r[13] + r[15]) % 2

                i = 0
                while i < len(r)-1:
                        r[i] = r[i+1]
                        i += 1

                r[17-1] = (i1) % 2
                j += 1

def similarity(test_seq):
    output_seq = map(int, list("0111011010111000010001111111111011110000010111111001111011101011111100000000110000011001011111000001000110000000001111011011101011111011101100010001101011101011111010100000101110011111100101000"))

    diff = 0;
    for i in range(0, len(output_seq)):
        if output_seq[i] != test_seq[i]:
            diff += 1

    return 1 - float(diff)/len(output_seq)

def test_all_lfsr(r1, r2, r3, n):
    a = list(lfsr2a(r1, n))
    b = list(lfsr2b(r2, n))
    c = list(lfsr2c(r3, n))

    for i in range(0, n):
        if a[i]+b[i]+c[i] >= 2:
            print 1,
        else:
            print 0,

    print "\n"

# First LFSR
highest = 0
highest_seq = 0
for i in range(0,8192):
    test = list(denary2binary(i).zfill(13))
    test = map(int, test)

    #print "-----------"
    #print test
    lfsr_seq = list(lfsr2a(list(test), 193)) #Additional list to get it as a copy so we don't modify #test
    #print lfsr_seq

    score = similarity(lfsr_seq)
    if score > highest:
        highest = score
        highest_seq = test
        #print test
        #print "New max: " + str(score) + " out=" + "".join(map(str,lfsr_seq)) + " in=" +  "".join(map(str,test))

r1 = highest_seq
print "Best for LFSR A: "  + str(highest) + " " + "".join(map(str,highest_seq))

# Second LFSR
highest = 0
highest_seq = 0
for i in range(0,32768):
    test = list(denary2binary(i).zfill(15))
    test = map(int, test)

    lfsr_seq = list(lfsr2b(list(test), 193)) #Additional list to get it as a copy so we don't modify #test

    score = similarity (lfsr_seq)
    if score > highest:
        highest = score
        highest_seq = test
        #print "New max: " + str(score) + " out=" + "".join(map(str,lfsr_seq)) + " in=" +  "".join(map(str,test))

r2 = highest_seq
print "Best for LFSR B: "  + str(highest) + " " + "".join(map(str,highest_seq))

# Third LFSR
highest = 0
highest_seq = 0
for i in range(0,131072):
    test = list(denary2binary(i).zfill(17))
    test = map(int, test)

    lfsr_seq = list(lfsr2c(list(test), 193)) #Additional list to get it as a copy so we don't modify #test

    score = similarity (lfsr_seq)
    if score > highest:
        highest = score
        highest_seq = test
        #print "New max: " + str(score) + " out=" + "".join(map(str,lfsr_seq)) + " in=" +  "".join(map(str,test))

r3 = highest_seq
print "Best for LFSR C: "  + str(highest) + " " + "".join(map(str,highest_seq))


print "Feeding back sequence into LFSR"

test_all_lfsr(r1, r2, r3, 193)

"""
#test_all_lfsr(map(int,list("0111110110111")), map(int,list("000001101101100")), map(int,list("11110010101010100")), 193)

for a in ['0111110110111', '0101001000110', '0001001010001']:
    for b in ['000001101101100', '000001001101011', '000000110001001']:
        for c in ['11110010101010100', '01110100000100001', '01110001111010110']:
            test_all_lfsr(map(int,list(a)), map(int,list(b)), map(int,list(c)), 193)
"""