rarara.py

from crc64 import crc64

mem = map(chr, [65,    77,   150,  2,    54,   40,   50,   4,    1,    24,
                96,   2,    231,  191,  200,  200,  224,  221,  242,  255,
                65,    224,  221,  36,   28,   237,  200,  224,  221,  204,
                72,   63,   232,  162,  87,   122,  185,  200,  224,  221,
                65,    224,  221,  29,   230,  181,  204,  72,   63,   200,
                224,  221,  200,  224,  221,  76,   177,  34,   127,  127,
                65,    200,  224,  221,  200,  224,  221,  200,  224,  221,
                242,  255,  76,   177,  34,   200,  224,  221,  200,  224,
                65,    204,  72,   63,   200,  224,  221,  200,  224,  221,
                127,  127,  127,  36,   28,   237,  204,  72,   63,   200,
                65,    221,  200,  224,  221,  36,   28,   237,  39,   127,
                255,  200,  224,  221,  200,  224,  221,  29,   230,  181,
                65,    224,  221,  200,  224,  221,  154,  118,  131,  200,
                224,  221,  87,   122,  185,  200,  224,  221,  200,  224,
                65,    76,   177,  34,   232,  162,  36,   28,   237,  201,
                174,  255,  36,   28,   237,  204,  72,   63,   200,  224,
                65,    76,   177,  34,   200,  224,  221,  200,  224,  221,
                200,  224,  221,  200,  224,  221,  200,  224,  221,  36,
                65,    237,  200,  224,  221,  39,   127,  255,  200,  224,
                221,  200,  224,  221,  200,  224,  221,  201,  174,  255,
                65,    224,  221,  200,  224,  221,  200,  224,  221,  87,
                122,  185,  200,  224,  221,  36,   28,   237,  200,  224,
                65,    200,  0,    0,    0,    0,    0,    0,    0,    0,
                0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
                65,    0,    0,    0,    0,    0,    0,    0,    0,    0,
                0,    0,    0,    0,    0,    0])

from crc64 import crc64


def print_mat(m):
   for k in [''.join([str(i) for i in m[j]]) for j in xrange(len(m))]:
       print k

def print_mat2(m):
   print '{'
   for l in m:
       line = 'bitset<91>{"'
       for i in l[:-1]:
           if i:
               line+='1'
           else:
               line+='0'
       if l[-1]:
           line+='1"},'
       else:
           line+='0"},'
       print line
   print '}'

def print_vec(v):
   line = '{"'
   for i in v[:-1]:
       if i:
           line += '1'
       else:
           line += '0'
   if v[-1]:
       line += '1"}'
   else:
       line += '0"}'
   print line


base = crc64(mem)
ac_base = 0x15AD90B88ABA1847 ^ base
ac_base_bits = [(ac_base >> i) & 1 for i in xrange(64)]
ac_base_bits += [1]

bits_pos = []
for i in xrange(13):
   for bit in xrange(7):
       pos = 0x14 * i
       changed_byte = chr(ord(mem[pos]) ^ (1 << bit))
       bits_pos.append((pos, bit, base ^ crc64(mem[:pos] + [changed_byte] + mem[pos+1:])))

mat = [[None] * 91 for i in xrange(65)]
for i in xrange(64):
   for j in xrange(91):
       mat[i][j] = (bits_pos[j][2] >> i) & 1

for i in xrange(91):
    if i % 7 == 0:
        mat[64][i] = 1
    else:
        mat[64][i] = 0

def xor(a, b):
   return map(lambda x, y: x ^ y, a, b)


def inner(a, b):
   return reduce(lambda x, y: x ^ y, map(lambda x, y: x & y, a, b))

def rank(m, v):
   w = len(m[0])
   h = len(m)
   last_i = -1

   for j in xrange(w):
       last_i += 1
       if last_i == h:
           break
       for i in xrange(last_i, h):
           if m[i][j] == 1:
               break
       if m[i][j] == 0:
           continue
       i0 = i
       if i0 != last_i:
           m[i0], m[last_i] = m[last_i], m[i0]
           v[i0], v[last_i] = v[last_i], v[i0]
           i0 = last_i
       for i in xrange(i0 + 1, h):
           if m[i][j] == 1:
               m[i] = xor(m[i], m[i0])
               v[i] = v[i] ^ v[i0]

rank(mat, ac_base_bits)
print_mat2(mat)
print_vec(ac_base_bits)