Generates CRC tables from the generating polynom.

gencrctable.py

"""
Generates CRC tables. Run as follows.

    gencrctable.py <polynom> -w <width>

    # for CRC-32
    gencrctable.py 0x04C11DB7 -w 32

    # for CRC-32C
    gencrctable.py 0x1EDC6F41 -w 32

Then use the generated table in the CRC algorithm (replace uintx_t
with the type corresponding to the CRC width).

    static uintx_t const crc_table[] = { /* ... */ };

    template <typename InputIterator>
    uintx_t crc(InputIterator first, InputIterator last, uintx_t seed = 0)
    {
        uintx_t res = ~seed;
        while (first != last)
            res = crc_table[(uint8_t)(res ^ *first++)] ^ (res >> 8);
        return ~res;
    }
"""

def _topmost_bit(n):
    res = 0
    while n != 1:
        n >>= 1
        res += 1
    return res

def _reverse_bits(value, width):
    res = 0
    for i in xrange(width):
        res <<= 1
        if value & 1:
            res |= 1
        value >>= 1
    return res

def _table_entry(val, val_width, revpoly):
    res = val
    for i in xrange(val_width):
        if res & 1:
            res = (res>>1) ^ revpoly
        else:
            res >>= 1
    return res

def _main(argv):
    import argparse
    parser = argparse.ArgumentParser(description="Generate CRC tables.")
    parser.add_argument('polynom')
    parser.add_argument('--width', '-w', type=int, required=True)
    parser.add_argument('--parallel', '-p', type=int, default=8)
    parser.add_argument('--line-width', '-l', type=int, default=80)
    args = parser.parse_args(argv[1:])

    polynom = int(args.polynom, 0)
    if args.width is None:
        width = _topmost_bit(polynom)
    else:
        width = args.width
    polynom = polynom & ((1<<width)-1)
    revpoly = _reverse_bits(polynom, width)

    table = []
    table_size = 1<<args.parallel
    for i in xrange(table_size):
        table.append(_table_entry(i, args.parallel, revpoly))

    item_width = (width + 3) // 4

    cols = 1
    while True:
        next_cols = cols << 1
        line_width = 3 + (next_cols * (4 + item_width))
        if line_width > args.line_width:
            break
        cols = next_cols

    format_entry = '0x%%0%dx,' % item_width
    while table:
        print '    ' + ' '.join((format_entry % entry for entry in table[:cols]))
        table = table[cols:]

if __name__ == '__main__':
    import sys
    _main(sys.argv)