Calcurate reedsolomon parity

reedsolomon_parity.py

'''
Calcurate reedsolomon parity
'''

from collections import OrderedDict

def gen_exp_table():
    alpha = 1
    table = []
    for i in range(256):
        table.append(alpha)
        alpha = alpha << 1
        if alpha & (1 << 8) != 0:
            alpha = alpha & ~(1 << 8) ^ (1 << 4) ^ (1 << 3) ^ (1 << 2) ^ 1

    return table

def gen_log_table(exp_table):
    it = iter(exp_table)
    dic = OrderedDict(dict(zip(range(len(exp_table)), it)))
    tmp_dic = {}
    for exp, num in dic.items():
        tmp_dic[num] = exp

    table = []
    for key in sorted(tmp_dic.keys()):
        table.append(tmp_dic[key])
    table[0] = 0 # a^0 = 1
    table = [float('-inf')] + table

    return table

def calc_generator_polynomial(code, exp_table, log_table):
    '''
    [0, 75, 249x, 78, 6] =
        x^4 + a^75x^3 + a^249x^2 + a^78x + a^6
    '''
    if code == 1:
        return [0, 0]
    a = [0, 0]
    for k in range(code-1):
        b = [0, k+1]
        c = [None] * (len(a) + 1) # g_n
        for i, _ in enumerate(a):
            for j, _ in enumerate(b):
                val = a[i] + b[j]
                if c[i+j] == None:
                    c[i+j] = a[i] + b[j]
                else:
                    c[i+j] = log_table[ exp_table[c[i+j]] ^ exp_table[ a[i] ^ b[j] ] ]
                # c[i+j] mod 255
                if c[i+j] > 255:
                    c[i+j] -= 255
        a = c
    return c

exp_table = gen_exp_table()
log_table = gen_log_table(exp_table)

def gf_add(a, b):
    return gf_inverse(log_table[a] + log_table[b])

def gf_lookup(a):
    value = a % 255
    return exp_table[value]

def gf_inverse(a):
    return log_table[a]

def gf_multiply(a, b):
    return exp_table[ value ]

def calc_parity(data, gx):
    fx = list(data)
    steps = len(fx)
    for step in range(steps):
        # division factor
        div_factor = fx[0]
        div_factor_exp = gf_inverse(div_factor)
        # adding exp
        gx_mul = [ x+div_factor_exp for x in gx]
        gx_log = [ gf_lookup(x) for x in gx_mul]
        if len(fx) < len(gx):
            fx = fx + [0] * (len(gx) - len(fx))
        else:
            gx_log = gx_log + [0] * (len(fx) - len(gx))
        fx =  [x ^ y for (x, y) in zip(fx, gx_log)]
        fx = fx[1:]
    return fx

if __name__ == '__main__':
    gx = calc_generator_polynomial(7, exp_table, log_table)
    # "I Love You"
    parity = calc_parity((64,164,146,4,198,247,102,82,5,150,247,80,236,17,236,17,236,17,236), gx)
    # expect to [169, 192, 28, 239, 17, 203, 18]
    print(parity)