Hacky GF(2) polynomial long division impl

longdiv.py

"""Hacky polynomial long division implementation for testing fun.

Polynomials in GF(2) have the simple arithmetic properties:

    all polynomial coefficients are 1 or 0
    addition is subtraction is XOR on the polynomial coefficients
    polynomial powers add under multiplication
"""

import re

def pretty_bin(num):
    orig = bin(num)[2:]
    b = orig[::-1]
    b = re.sub(r'(\d{4})', r'\1_', b)
    b = b[::-1].lstrip('_')
    assert b.replace('_', '') == orig
    return '0b' + b

def poly_to_bits(*bits):
    accum = 0
    for bit in bits:
        accum |= 1 << bit
    return accum

def num_to_poly(num, verbose=False):
    bits = []
    while num:
        if verbose: print 'num is', bin(num)
        v = bin(num)[2:]
        bits.append(len(v))
        num = int(v[1:] or '0', 2)
    return bits

def bit_set(num, bitno):
    return bool(num & (1 << bitno))

def bit_len(num):
    assert num >= 0
    if num == 0:
        return 0
    return len(bin(num)) - 2

def dict_to_num(d):
    if not d:
        return 0
    bits = [('1' if i in d else '0') for i in reversed(range(max(d.keys())+1))]
    return int(''.join(bits), 2)

def long_div_poly(num, denom, verbose=False):
    assert bit_len(num) >= bit_len(denom)
    if verbose: print 'num   %20s' % pretty_bin(num)
    if verbose: print 'denom %20s' % pretty_bin(denom)
    quotient = {}
    orig_num_len = bit_len(num)
    bitnum = orig_num_len - bit_len(denom)
    if verbose: print 'starting at quotient bitnum', bitnum
    while bitnum >= 0:
        bit_to_test = bitnum + bit_len(denom) - 1
        if verbose: print 'testing bit', bit_to_test

        if bit_set(num, bit_to_test):
            if verbose: print 'bit', bit_to_test, 'is set'
            if verbose: print '  setting quotient bit', bitnum
            quotient[bitnum] = 1
            to_xor = denom << bitnum
            if verbose: print 'xoring  %20s' % pretty_bin(num)
            if verbose: print 'with    %20s' % pretty_bin(to_xor)
            num ^= to_xor
            if verbose: print 'new num %20s' % pretty_bin(num)
        else:
            if verbose: print 'bit', bit_to_test, 'is not set'
        bitnum -= 1
    result = dict_to_num(quotient)
    if verbose: print 'quot  %20s' % pretty_bin(result)
    return result, num


test_result = long_div_poly(5, 5)
assert test_result == (1, 0), test_result

test_result = long_div_poly(8, 5)
assert test_result == (2, 2), test_result

test_result = long_div_poly(0b110110, 0b11011)
assert test_result == (0b10, 0), bin(test_result)

test_result = long_div_poly(0x11d8, 0x1b)
assert test_result == (0b111010011, 0b101), bin(test_result)

test_result = long_div_poly(poly_to_bits(2, 0), poly_to_bits(1, 0))
assert test_result == (0b11, 0), test_result

test_result = long_div_poly(0b11100001, 0b11)
assert test_result == (0b1011111, 0), bin(test_result)

num = poly_to_bits(32)
denom = poly_to_bits(32, 24, 1, 0)

q, r = long_div_poly(num, denom)
print num_to_poly(q), num_to_poly(r)