import struct, binascii, random

import psyco; psyco.full()

alpha = "ABCDEFGHJKLMNPQRSTUVWXYZ23456789"

table = []
for c in binascii.a2b_hex("00010102010202030102020302030304010202030203030402030304030404050102020302030304020303040304040502030304030404050304040504050506010202030203030402030304030404050203030403040405030404050405050602030304030404050304040504050506030404050405050604050506050606070102020302030304020303040304040502030304030404050304040504050506020303040304040503040405040505060304040504050506040505060506060702030304030404050304040504050506030404050405050604050506050606070304040504050506040505060506060704050506050606070506060706070708"):
    table.append(ord(c))

shuftable = (0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8)
bitcount = (0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4)


def flip(v):
    return struct.unpack("<I", struct.pack(">I", v))[0]

def key_to_dwords(key):
    n = 0
    for c in key:
        v = alpha.find(c)
        if v == -1:
            continue
        n = (n << 5) | v

    last = n & 0x7fff
    n = n >> 15
    words = []
    for i in xrange(5):
        v = flip(n & 0xffffffff)
        words.append(v)
        n = n >> 32

    words = words[::-1]
    last = flip((last & 0x7f) | ((last << 1) & 0xff00)) >> 16
    words.append(last)

    return words

def dwords_to_key(words):
    n = 0
    for i in xrange(5):
        n = (n << 32) | flip(words[i])

    last = flip(words[5] << 16)
    last = ((last >> 1) & 0x7f80) | (last & 0x7f)
    n = (n << 15) | last

    s = ""
    for i in xrange(35):
        s += alpha[n & 0x1f]
        n = n >> 5
        if i % 5 == 4:
            s += "-"

    key = s[::-1][1:]
    return key

def make_checksum(words):
    s = ""
    for w in words:
        s += struct.pack("<I", w)

    bytea = 0;
    byteb = 0;
    for i in xrange(len(s)):
        v2 = bytea + ord(s[i])
        bytea = (v2 - 255 * (((v2 + (0xFFFFFFFF80808081 * v2 >> 32)) >> 7) - (v2 >> 31))) & 0xffff
        byteb = (byteb + bytea) % 255

    csum = ((byteb << 8) | bytea) & 0x7fff

    words2 = list(words)
    words2.append(csum)
    return words2

key1 = "ABCDE-FGHJK-LMNPQ-RSTUV-WXYZ2-34567-899D9"
key1 = "WTFYE-FGHJK-LMNPQ-RSTUV-WXYZ2-34567-899D9"
dwords = key_to_dwords(key1)
print dwords
for w in dwords:
    print "%08x" % w

key2 = dwords_to_key(dwords)
print key2
print key1 == key2

def scramble(n):
    res = 0
    for i in xrange(0, 64, 8):
        t = (n >> i) & 0xff
        res += table[t]
    return res

def test_word_14():
    for a1 in xrange(0x10000):
        if not (((a1 >> 12) ^ (a1 >> 8)) & 0xF):
            continue
        if not (((a1 >> 8) ^ (a1 >> 4)) & 0xF):
            continue
        if not (((a1 >> 4) ^ a1) & 0xF):
            continue
        print "%04x" % a1

def neighbor_nibbles(a1):
    t = (a1 >> 4) ^ a1
    for i in xrange(7):
        if t & 0xf == 0:
            return True
        t = t >> 4

    return False

def neighbor_bytes(a1):
    t = (a1 >> 8) ^ a1
    for i in xrange(3):
        if t & 0xff == 0:
            return True
        t = t >> 8

    return False

def is_prime(a1):
    if a1 <= 0xFFFFFE:
        return False
    n = 3
    while n*n < a1:
        if a1 % n == 0:
            return False
        n += 2
    return True

def check_word04(a1):
    v2 = 0;
    v4 = 15;
    for i in xrange(16):
        v2 = (a1 >> (2 * v4 + 1)) & 1 | 2 * v2
        v4 -= 1
    return v2 == 7 * (v2 / 7)

def check_word08(a1):
    v2 = 0;
    v4 = 15;
    for i in xrange(16):
        v2 = (a1 >> (2 * v4 + 1)) & 1 | 2 * v2
        v4 -= 1
    return v2 == 13 * ((0x4EC5 * v2 >> 16) >> 2)

def check_word10(a1):
    # t = (a1 >> 16)
    # t2 = (t * 0xa79c7b17) >> 40
    # t2 = t2 * 0x187
    # t = t - t2
    # print hex(t)
    # print hex(((a1 >> 16) - 0x187 * (a1 / 0x1870000)))
    # exit()

    if not ((a1 >> 16) - 0x187 * (a1 / 0x1870000)) == a1 & 0xff:
        return False
    if not ((a1 >> 16) & (0xffff % (((a1 & 0xff00) >> 8) + 1) == 0)):
        return False
    if not scramble(a1) > 8:
        return False
    return True


def stupidsum(w00, w04, w08):
    eax = w04
    w00 = (w00 - eax) & 0xffffffff
    eax = w08
    w00 = (w00 - eax) & 0xffffffff
    eax = w08
    eax = eax >> 0xd
    w00 ^= eax

    eax = w08
    w04 = (w04 - eax) & 0xffffffff
    eax = w00
    w04 = (w04 - eax) & 0xffffffff
    eax = w00
    eax = (eax << 8) & 0xffffffff
    w04 ^= eax

    eax = w00
    w08 = (w08 - eax) & 0xffffffff
    eax = w04
    w08 = (w08 - eax) & 0xffffffff
    eax = w04
    eax = eax >> 0xd
    w08 ^= eax

    eax = w04
    w00 = (w00 - eax) & 0xffffffff
    eax = w08
    w00 = (w00 - eax) & 0xffffffff
    eax = w08
    eax = eax >> 0xc
    w00 ^= eax

    eax = w08
    w04 = (w04 - eax) & 0xffffffff
    eax = w00
    w04 = (w04 - eax) & 0xffffffff
    eax = w00
    eax = (eax << 0x10) & 0xffffffff
    w04 ^= eax

    eax = w00
    w08 = (w08 - eax) & 0xffffffff
    eax = w04
    w08 = (w08 - eax) & 0xffffffff
    eax = w04
    eax = eax >> 5
    w08 ^= eax

    eax = w04
    w00 = (w00 - eax) & 0xffffffff
    eax = w08
    w00 = (w00 - eax) & 0xffffffff
    eax = w08
    eax = eax >> 3
    w00 ^= eax

    eax = w08
    w04 = (w04 - eax) & 0xffffffff
    eax = w00
    w04 = (w04 - eax) & 0xffffffff
    eax = w00
    eax = (eax << 0xa) & 0xffffffff
    w04 ^= eax

    eax = w00
    w08 = (w08 - eax) & 0xffffffff
    eax = w04
    w08 = (w08 - eax) & 0xffffffff
    eax = w04
    eax = eax >> 0xf
    w08 ^= eax
    return w08

def commoncheck1(w00, w04, w08):
    v4 = w00;
    v5 = 0;

    v9 = 15;
    for i in xrange(16):
        v5 = (w04 >> 2 * v9) & 1 | 2 * v5
        v9 -= 1

    if not scramble(v5) > 2:
        return False

    v6 = 0;
    v10 = 15;
    for i in xrange(16):
        v6 = (w08 >> 2 * v10) & 1 | 2 * v6
        v10 -= 1

    if not scramble(v6) > 3:
        return False

    return w00 + 1 == v5 * v6

def updatedcommon(w04r, w08r):
    if scramble(w04r) <= 2:
        return None

    if scramble(w08r) <= 3:
        return None

    return (w04r * w08r) - 1

def check_bits(w04, w08):
    res = 0
    if bitcount[shuftable[(w04 >> 28) & 0xf]] == 2:
        res |= 1
    if bitcount[shuftable[(w04 >> 28) & 0xf] ^ shuftable[(w04 >> 24) & 0xf]] == 2:
        res |= 2
    if bitcount[shuftable[(w04 >> 24) & 0xf] ^ shuftable[(w04 >> 20) & 0xf]] == 2:
        res |= 4
    if bitcount[shuftable[(w04 >> 20) & 0xf] ^ shuftable[(w04 >> 16) & 0xf]] == 2:
        res |= 8
    if bitcount[shuftable[(w04 >> 16) & 0xf] ^ shuftable[(w04 >> 12) & 0xf]] == 2:
        res |= 16
    if bitcount[shuftable[(w04 >> 12) & 0xf] ^ shuftable[(w04 >> 8) & 0xf]] == 2:
        res |= 32
    if bitcount[shuftable[(w04 >> 8) & 0xf] ^ shuftable[(w04 >> 4) & 0xf]] == 2:
        res |= 64
    if bitcount[shuftable[(w04 >> 4) & 0xf] ^ shuftable[(w04 >> 0) & 0xf]] == 2:
        res |= 128
    if bitcount[shuftable[(w04 >> 0) & 0xf] ^ shuftable[(w08 >> 28) & 0xf]] == 2:
        res |= 0x100
    if bitcount[shuftable[(w08 >> 28) & 0xf] ^ shuftable[(w08 >> 24) & 0xf]] == 2:
        res |= 0x200
    if bitcount[shuftable[(w08 >> 24) & 0xf] ^ shuftable[(w08 >> 20) & 0xf]] == 2:
        res |= 0x400
    if bitcount[shuftable[(w08 >> 20) & 0xf] ^ shuftable[(w08 >> 16) & 0xf]] == 2:
        res |= 0x800
    if bitcount[shuftable[(w08 >> 16) & 0xf] ^ shuftable[(w08 >> 12) & 0xf]] == 2:
        res |= 0x1000
    if bitcount[shuftable[(w08 >> 12) & 0xf] ^ shuftable[(w08 >> 8) & 0xf]] == 2:
        res |= 0x2000
    if bitcount[shuftable[(w08 >> 8) & 0xf] ^ shuftable[(w08 >> 4) & 0xf]] == 2:
        res |= 0x4000
    if bitcount[shuftable[(w08 >> 4) & 0xf] ^ shuftable[(w08 >> 0) & 0xf]] == 2:
        res |= 0x8000

    return res

dwords = [0x2019fab1, 0x26efb3bd, 0xc7f1cb7c, 0x7c96b08d, 0x1f5110c5]

# print hex(check_bits(0x26efb3bd, 0xc7f1cb7c))
# exit()
def main():

    w10bucket = []
    while len(w10bucket) < 20:
        w10 = random.randint(0, 0xffffffff)
        if check_word10(w10):
            w10bucket.append(w10)
    print "bucket full"

    while True:
        w04r = random.randint(0, 0xffff)
        w08r = random.randint(0, 0xffff)
        w00 = updatedcommon(w04r, w08r)

        if not is_prime(w00) or neighbor_nibbles(w00) or neighbor_bytes(w00):
            continue

        while True:
            w04l = random.randint(0, 0xffff)
            if w04l == 7 * (w04l / 7):
                break

        while True:
            w08l = random.randint(0, 0xffff)
            if w08l == 13 * ((0x4EC5 * w08l >> 16) >> 2):
                break

        w04 = 0
        for i in xrange(16):
            w04 = w04 | ((w04l & 1) << (i*2+1)) | ((w04r & 1) << (i*2))
            w04l >>= 1
            w04r >>= 1

        w08 = 0
        for i in xrange(16):
            w08 = w08 | ((w08l & 1) << (i*2+1)) | ((w08r & 1) << (i*2))
            w08l >>= 1
            w08r >>= 1

        if not check_word04(w04):
            print "BAAAAAAAAD"
            exit()

        if not check_word08(w08):
            print "BAAAAAAAAD"
            exit()

        if not commoncheck1(w00, w04, w08):
            print "AAAAAAAA"
            exit()

        w0c = stupidsum(w00, w04, w08)

        csumtarget = check_bits(w04, w08)
        if csumtarget & 0x8000:
            continue

        for w10 in w10bucket:
            dwords = [w00, w04, w08, w0c, w10]
            dwords = make_checksum(dwords)
            if dwords[-1] != csumtarget:
                print ".",
                continue
            else:
                print "0x%08x, 0x%08x, 0x%08x, 0x%08x, 0x%08x" % (w00, w04, w08, w0c, w10)
                dwords = [w00, w04, w08, w0c, w10]
                dwords = make_checksum(dwords)
                for w in dwords:
                    print "%08x" % w
                print dwords_to_key(dwords)
                print
                exit()



# two neighboring nibbles must NOT be equal
# two neighboring bytes must NOT be equal

main()