#!/usr/bin/python
# -*- coding: utf-8 -*-
from __future__ import division

import random

def main(N, M, d, message='This is a test message'):
    """N is the number of bits in each input symbol.
    M is the number of bits in each output symbol.
    d is the density of the M×N encoding matrix.
    """

    print 'N =', N, 'M =', M
    random.seed(0)
    r = random#.SystemRandom()
    key = [sum(2**jj * (r.random() < d) for jj in range(N)) for ii in range(M)]
    print 'key', '[%s]' % ', '.join("0x%x" % row for row in key)
    unkey = transpose(key, N)
    print 'unkey', unkey
    # If this fails, it means transposing has a bug, so nothing can
    # work.
    assert key == transpose(unkey, len(key))
    print 'message', `message`
    message_digits = to_base(2**N, bytestring_to_int(message))
    print 'digits in base', 2**N, message_digits
    encoded = [encode(digit, key, len(unkey)) for digit in message_digits]
    print 'encoded', `encoded`
    decoded = [encode(item, unkey, len(key)) for item in encoded]
    print 'decoded', `decoded`
    decoded_bytes = int_to_bytestring(from_base(2**N, decoded))
    print 'decoded bytes', `decoded_bytes`
    print 'matched' if decoded_bytes == message else 'mismatch', (
        'N ='), N, 'M =', M, 'd =', d, '+%.2f%%' % (100*(M/N-1))
    corrupted = [item ^ (1 << r.randrange(128)) for item in encoded]
    print 'corrupted', `corrupted`
    decodedc = from_base(2**N, [encode(item, unkey, len(key))
                                for item in corrupted])
    print 'corrected bytes', `int_to_bytestring(decodedc)`

def bytestring_to_int(s):
    return from_base(256, (ord(b) for b in s))

def from_base(base, digits):
    "Expects digits in big-endian order."
    i = 0
    for digit in digits:
        i = i * base + digit
    return i

def int_to_bytestring(i):
    "Loses trailing NULs."
    return ''.join(chr(b) for b in to_base(256, i))

def to_base(base, i):
    "Returns digits in big-endian order."
    digits = []
    assert i >= 0
    while i:
        i, digit = divmod(i, base)
        digits.append(digit)
    digits.reverse()
    return digits

assert int_to_bytestring(bytestring_to_int('hello')) == 'hello'

def popcount32(num):
    assert num < 2**32
    num = (num & 0x55555555) + ((num & 0xAaaaAaaa) >> 1)
    num = (num & 0x33333333) + ((num & 0xCcccCccc) >> 2)
    num = (num & 0x0f0f0f0f) + ((num & 0xf0f0f0f0) >> 4)
    num = (num & 0x00ff00ff) + ((num & 0xff00ff00) >> 8)
    num = (num & 0x0000ffff) + ((num & 0xffff0000) >> 16)
    return num

def popcount(num):
    n = 0
    while num:
        n += popcount32(num & 0xFfffFfff)
        num >>= 32
    return n

def encode(num, matrix, bitwidth):
    threshold = bitwidth / 2
    bits = [popcount(num & row) > popcount(~num & row) for row in matrix]
    return int(''.join('1' if bit else '0' for bit in bits), 2)

def transpose(matrix, bitwidth):
    return [int(''.join('1' if 2**ii & row else '0' for row in matrix), 2)
            for ii in range(bitwidth-1, -1, -1)]

if __name__ == "__main__":
    for N in [#3, 5, 7, 11, #17, 31,
              63,# 127, 255
              ]:
        for M in [#7, 15, 31, 63,
                  95,
                  #127, 191, 255, 
                  # 1023, 
                  2047
                  ]:
            if M > N:
                for d in [.001, .002, .005, .01, .02, .05, .1, .2, .3, .4, .5]:
                    main(N=N, M=M, d=d)