# CRC checker generation¶

This Notebook implements a simple arbitrary CRC unit generator. It makes use of the linear properties of the CRC operation and constructs 'participation' matrices out of the binary basis vector set (1 << j) (j being the coordinate). A given bit-serial implementation of a CRC is probed for each of these basis vectors and the final logic constructed out of the participation matrices.

In [1]:
from myirl import *


## Example serial CRC¶

You may define your own serial CRC function here. For example, the CRC feedback register for the USB protocol:

In [2]:
def serial_crc5_usb(c, din, M, dummy):
fb = (c >> (M-1)) ^ din
mask = (1 << M) - 1

return ((c << 1) & mask) ^ (fb << 2) | fb


Or a generic CRC with given polynom:

In [3]:
def serial_crc(c, din, M, POLY):
#     print(type(c))
mask = (1 << M) - 1
fb = (c >> (M-1)) ^ din

rotated = (c << 1) & mask
if fb:
v = rotated ^ (POLY & mask)
else:
v = rotated

return v


To determine the CRC for a data word, we just create a function that runs the serial CRC sequence N times:

In [4]:
def crc_dataword(cstart, din, crc_serial, M, POLY):
_c0 = int(cstart)
N = len(din)
for i in range(N):
_c0 = crc_serial(_c0, din[i], M, POLY)
return _c0


Create the 'participation' tables for the data and current CRC bits.

In [5]:
def gen_matrices(M, N, crc_s, POLY):
"Not so effective function to generate particular matrices"
A = N * [ None, ]

c0, c1 = [ Signal(intbv(0)[M:]) for _ in range(2) ]

din = intbv(1)[N+1:]
for i in range(N):
v = crc_dataword(0, din[N:], crc_s, M, POLY)
din <<= 1
A[i] = int(v)

B = M * [ None, ]

m = intbv(1)[M+1:]
din = intbv(0)[N:]

for i in range(M):
v = crc_dataword(m, din, crc_s, M, POLY)
m <<= 1
B[i] = int(v)

return A, B


This function creates the wire connections and combinatorial logic according to the participation table:

In [6]:
def gen_crc_xor(A, B, din, crc0, crc1):
m, n = len(B), len(A)
v = 1
connections = []
for i in range(m):
wires = []
md = ""
for j in range(n):
if A[j] & v:
wires += [ din[n-1-j] ]
md += '1' if A[j] & v else '0'
mc = ""
for j in range(m):
if B[j] & v:
wires += [ crc0[j] ]
mc += '1' if B[j] & v else '0'

v <<= 1

print(md, mc)

if len(wires) > 0:
first = wires[0]
for e in wires[1:]:
first = first ^ e
connections += [ crc1[i].set(first) ]
else:
raise(ValueError, "Bad CRC bit. Probably broken polynom.")

return connections


## The CRC unit¶

This actually creates the hardware. Note that we don't optimize logic here. We'll leave that to the synthesizer toolchain.

In [7]:
@block
def crc_unit(clk, en, reset, din, crcout, M, N, POLY, STARTVAL):
crc = Signal(intbv(STARTVAL)[M:])
crcnext = [ Signal(bool(), name = 'c%d' % i) for i in range(M) ]

print("generate matrices...")
M1, M2 = gen_matrices(M, N, serial_crc, POLY)
print("create xor map")
wires = gen_crc_xor(M1, M2, din, crc, crcnext)

@genprocess(clk, EDGE=clk.POS, RESET=reset)
def crc_init():
yield [ crc.set(concat(*reversed(crcnext))) ]

connections = [ crcout.set(crc) ]

return locals()

In [8]:
def test(DW, CW, POLYNOM):
clk = ClkSignal()
data = Signal(intbv()[DW:])
crc = Signal(intbv()[CW:])
r = ResetSignal(ResetSignal.POS_SYNC)
inst = crc_unit(clk, True, r, data, crc, CW, DW, POLYNOM, 0xffffffff)

tmp = inst.elab(targets.VHDL)
return tmp

In [9]:
POLYNOM = 0b100000100110000010001110110110111

tmp = test(8, 32, POLYNOM)

generate matrices...
create xor map
01000001 00000000000000000000000010000010
11000011 00000000000000000000000011000011
11000111 00000000000000000000000011100011
10001110 00000000000000000000000001110001
01011101 00000000000000000000000010111010
11111011 00000000000000000000000011011111
11110110 00000000000000000000000001101111
10101101 00000000000000000000000010110101
00011011 10000000000000000000000011011000
00110110 01000000000000000000000001101100
00101101 00100000000000000000000010110100
00011011 00010000000000000000000011011000
01110111 00001000000000000000000011101110
11101110 00000100000000000000000001110111
11011100 00000010000000000000000000111011
10111000 00000001000000000000000000011101
00110001 00000000100000000000000010001100
01100010 00000000010000000000000001000110
11000100 00000000001000000000000000100011
10001000 00000000000100000000000000010001
00010000 00000000000010000000000000001000
00100000 00000000000001000000000000000100
00000001 00000000000000100000000010000000
01000011 00000000000000010000000011000010
10000110 00000000000000001000000001100001
00001100 00000000000000000100000000110000
01011001 00000000000000000010000010011010
10110010 00000000000000000001000001001101
01100100 00000000000000000000100000100110
11001000 00000000000000000000010000010011
10010000 00000000000000000000001000001001
00100000 00000000000000000000000100000100
Writing 'crc_unit' to file /tmp/myirl_top_crc_unit__6m35mtu/crc_unit.vhdl

/home/testing/.local/lib/python3.9/site-packages/myirl-0.0.0-py3.9-linux-x86_64.egg/myirl/kernel/components.py:231: UserWarning: Unspecified port I/O clk => IN
base.warnings.warn("Unspecified port I/O %s => IN" % n)
/home/testing/.local/lib/python3.9/site-packages/myirl-0.0.0-py3.9-linux-x86_64.egg/myirl/kernel/components.py:231: UserWarning: Unspecified port I/O reset => IN
base.warnings.warn("Unspecified port I/O %s => IN" % n)
/home/testing/.local/lib/python3.9/site-packages/myirl-0.0.0-py3.9-linux-x86_64.egg/myirl/kernel/components.py:231: UserWarning: Unspecified port I/O din => IN
base.warnings.warn("Unspecified port I/O %s => IN" % n)
/home/testing/.local/lib/python3.9/site-packages/myirl-0.0.0-py3.9-linux-x86_64.egg/myirl/kernel/components.py:228: UserWarning: Unspecified port I/O crcout => OUT
base.warnings.warn("Unspecified port I/O %s => OUT" % n)

In [10]:
!cat {tmp[0]}

-- File generated from source:
--     /tmp/ipykernel_10223/2321360645.py
-- (c) 2016-2021 section5.ch
-- Modifications may be lost, edit the source file instead.

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;

library work;

use work.txt_util.all;
use work.myirl_conversion.all;

entity crc_unit is
port (
clk : in std_ulogic;
reset : in std_ulogic;
din : in unsigned(7 downto 0);
crcout : out unsigned(31 downto 0)
);
end entity crc_unit;

architecture MyIRL of crc_unit is
-- Local type declarations
-- Signal declarations
signal crc : unsigned(31 downto 0);
signal c31 : std_ulogic;
signal c30 : std_ulogic;
signal c29 : std_ulogic;
signal c28 : std_ulogic;
signal c27 : std_ulogic;
signal c26 : std_ulogic;
signal c25 : std_ulogic;
signal c24 : std_ulogic;
signal c23 : std_ulogic;
signal c22 : std_ulogic;
signal c21 : std_ulogic;
signal c20 : std_ulogic;
signal c19 : std_ulogic;
signal c18 : std_ulogic;
signal c17 : std_ulogic;
signal c16 : std_ulogic;
signal c15 : std_ulogic;
signal c14 : std_ulogic;
signal c13 : std_ulogic;
signal c12 : std_ulogic;
signal c11 : std_ulogic;
signal c10 : std_ulogic;
signal c9 : std_ulogic;
signal c8 : std_ulogic;
signal c7 : std_ulogic;
signal c6 : std_ulogic;
signal c5 : std_ulogic;
signal c4 : std_ulogic;
signal c3 : std_ulogic;
signal c2 : std_ulogic;
signal c1 : std_ulogic;
signal c0 : std_ulogic;
begin

crc_init:
process(clk, reset)
begin
if rising_edge(clk) then
if reset = '1' then
crc <= x"ffffffff";
else
crc <= (c31 & c30 & c29 & c28 & c27 & c26 & c25 & c24 & c23 & c22 & c21 & c20 & c19 & c18 & c17 & c16 & c15 & c14 & c13 & c12 & c11 & c10 & c9 & c8 & c7 & c6 & c5 & c4 & c3 & c2 & c1 & c0);
end if;
end if;
end process;
c0 <= (((din(6) xor din(0)) xor crc(24)) xor crc(30));
c1 <= (((((((din(7) xor din(6)) xor din(1)) xor din(0)) xor crc(24)) xor crc(25)) xor crc(30)) xor crc(31));
c2 <= (((((((((din(7) xor din(6)) xor din(2)) xor din(1)) xor din(0)) xor crc(24)) xor crc(25)) xor crc(26)) xor crc(30)) xor crc(31));
c3 <= (((((((din(7) xor din(3)) xor din(2)) xor din(1)) xor crc(25)) xor crc(26)) xor crc(27)) xor crc(31));
c4 <= (((((((((din(6) xor din(4)) xor din(3)) xor din(2)) xor din(0)) xor crc(24)) xor crc(26)) xor crc(27)) xor crc(28)) xor crc(30));
c5 <= (((((((((((((din(7) xor din(6)) xor din(5)) xor din(4)) xor din(3)) xor din(1)) xor din(0)) xor crc(24)) xor crc(25)) xor crc(27)) xor crc(28)) xor crc(29)) xor crc(30)) xor crc(31));
c6 <= (((((((((((din(7) xor din(6)) xor din(5)) xor din(4)) xor din(2)) xor din(1)) xor crc(25)) xor crc(26)) xor crc(28)) xor crc(29)) xor crc(30)) xor crc(31));
c7 <= (((((((((din(7) xor din(5)) xor din(3)) xor din(2)) xor din(0)) xor crc(24)) xor crc(26)) xor crc(27)) xor crc(29)) xor crc(31));
c8 <= ((((((((din(4) xor din(3)) xor din(1)) xor din(0)) xor crc(0)) xor crc(24)) xor crc(25)) xor crc(27)) xor crc(28));
c9 <= ((((((((din(5) xor din(4)) xor din(2)) xor din(1)) xor crc(1)) xor crc(25)) xor crc(26)) xor crc(28)) xor crc(29));
c10 <= ((((((((din(5) xor din(3)) xor din(2)) xor din(0)) xor crc(2)) xor crc(24)) xor crc(26)) xor crc(27)) xor crc(29));
c11 <= ((((((((din(4) xor din(3)) xor din(1)) xor din(0)) xor crc(3)) xor crc(24)) xor crc(25)) xor crc(27)) xor crc(28));
c12 <= ((((((((((((din(6) xor din(5)) xor din(4)) xor din(2)) xor din(1)) xor din(0)) xor crc(4)) xor crc(24)) xor crc(25)) xor crc(26)) xor crc(28)) xor crc(29)) xor crc(30));
c13 <= ((((((((((((din(7) xor din(6)) xor din(5)) xor din(3)) xor din(2)) xor din(1)) xor crc(5)) xor crc(25)) xor crc(26)) xor crc(27)) xor crc(29)) xor crc(30)) xor crc(31));
c14 <= ((((((((((din(7) xor din(6)) xor din(4)) xor din(3)) xor din(2)) xor crc(6)) xor crc(26)) xor crc(27)) xor crc(28)) xor crc(30)) xor crc(31));
c15 <= ((((((((din(7) xor din(5)) xor din(4)) xor din(3)) xor crc(7)) xor crc(27)) xor crc(28)) xor crc(29)) xor crc(31));
c16 <= ((((((din(5) xor din(4)) xor din(0)) xor crc(8)) xor crc(24)) xor crc(28)) xor crc(29));
c17 <= ((((((din(6) xor din(5)) xor din(1)) xor crc(9)) xor crc(25)) xor crc(29)) xor crc(30));
c18 <= ((((((din(7) xor din(6)) xor din(2)) xor crc(10)) xor crc(26)) xor crc(30)) xor crc(31));
c19 <= ((((din(7) xor din(3)) xor crc(11)) xor crc(27)) xor crc(31));
c20 <= ((din(4) xor crc(12)) xor crc(28));
c21 <= ((din(5) xor crc(13)) xor crc(29));
c22 <= ((din(0) xor crc(14)) xor crc(24));
c23 <= ((((((din(6) xor din(1)) xor din(0)) xor crc(15)) xor crc(24)) xor crc(25)) xor crc(30));
c24 <= ((((((din(7) xor din(2)) xor din(1)) xor crc(16)) xor crc(25)) xor crc(26)) xor crc(31));
c25 <= ((((din(3) xor din(2)) xor crc(17)) xor crc(26)) xor crc(27));
c26 <= ((((((((din(6) xor din(4)) xor din(3)) xor din(0)) xor crc(18)) xor crc(24)) xor crc(27)) xor crc(28)) xor crc(30));
c27 <= ((((((((din(7) xor din(5)) xor din(4)) xor din(1)) xor crc(19)) xor crc(25)) xor crc(28)) xor crc(29)) xor crc(31));
c28 <= ((((((din(6) xor din(5)) xor din(2)) xor crc(20)) xor crc(26)) xor crc(29)) xor crc(30));
c29 <= ((((((din(7) xor din(6)) xor din(3)) xor crc(21)) xor crc(27)) xor crc(30)) xor crc(31));
c30 <= ((((din(7) xor din(4)) xor crc(22)) xor crc(28)) xor crc(31));
c31 <= ((din(5) xor crc(23)) xor crc(29));
crcout <= crc;
end architecture MyIRL;