{ "cells": [ { "cell_type": "markdown", "id": "c3e4e074", "metadata": {}, "source": [ "# CRC checker generation\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": 1, "id": "5f2143fe", "metadata": {}, "outputs": [], "source": [ "from myirl import *" ] }, { "cell_type": "markdown", "id": "0720b67f", "metadata": {}, "source": [ "## Example serial CRC\n", "\n", "You may define your own serial CRC function here. For example, the CRC feedback register for the USB protocol:" ] }, { "cell_type": "code", "execution_count": 2, "id": "29c1d487", "metadata": {}, "outputs": [], "source": [ "def serial_crc5_usb(c, din, M, dummy):\n", " fb = (c >> (M-1)) ^ din\n", " mask = (1 << M) - 1\n", "\n", " return ((c << 1) & mask) ^ (fb << 2) | fb" ] }, { "cell_type": "markdown", "id": "31131b06", "metadata": {}, "source": [ "Or a generic CRC with given polynom:" ] }, { "cell_type": "code", "execution_count": 3, "id": "ff49ad1a", "metadata": {}, "outputs": [], "source": [ "def serial_crc(c, din, M, POLY):\n", "# print(type(c))\n", " mask = (1 << M) - 1\n", " fb = (c >> (M-1)) ^ din\n", "\n", " rotated = (c << 1) & mask\n", " if fb:\n", " v = rotated ^ (POLY & mask)\n", " else:\n", " v = rotated\n", " \n", " return v" ] }, { "cell_type": "markdown", "id": "9298530b", "metadata": {}, "source": [ "To determine the CRC for a data word, we just create a function that runs the serial CRC sequence `N` times:" ] }, { "cell_type": "code", "execution_count": 4, "id": "6057878d", "metadata": {}, "outputs": [], "source": [ "def crc_dataword(cstart, din, crc_serial, M, POLY):\n", " _c0 = int(cstart)\n", " N = len(din)\n", " for i in range(N):\n", " _c0 = crc_serial(_c0, din[i], M, POLY)\n", " return _c0" ] }, { "cell_type": "markdown", "id": "f1dc4bd2", "metadata": {}, "source": [ "Create the 'participation' tables for the data and current CRC bits." ] }, { "cell_type": "code", "execution_count": 5, "id": "61079ace", "metadata": { "scrolled": true }, "outputs": [], "source": [ "def gen_matrices(M, N, crc_s, POLY):\n", " \"Not so effective function to generate particular matrices\"\n", " A = N * [ None, ]\n", "\n", " c0, c1 = [ Signal(intbv(0)[M:]) for _ in range(2) ]\n", "\n", " din = intbv(1)[N+1:]\n", " for i in range(N):\n", " v = crc_dataword(0, din[N:], crc_s, M, POLY)\n", " din <<= 1\n", " A[i] = int(v)\n", "\n", " B = M * [ None, ]\n", "\n", " m = intbv(1)[M+1:]\n", " din = intbv(0)[N:]\n", "\n", " for i in range(M):\n", " v = crc_dataword(m, din, crc_s, M, POLY)\n", " m <<= 1\n", " B[i] = int(v)\n", "\n", " return A, B" ] }, { "cell_type": "markdown", "id": "253544f9", "metadata": {}, "source": [ "This function creates the wire connections and combinatorial logic according to the participation table:" ] }, { "cell_type": "code", "execution_count": 6, "id": "7affc46c", "metadata": {}, "outputs": [], "source": [ "def gen_crc_xor(A, B, din, crc0, crc1):\n", " m, n = len(B), len(A)\n", " v = 1\n", " connections = []\n", " for i in range(m):\n", " wires = []\n", " md = \"\"\n", " for j in range(n):\n", " if A[j] & v:\n", " wires += [ din[n-1-j] ]\n", " md += '1' if A[j] & v else '0'\n", " mc = \"\"\n", " for j in range(m):\n", " if B[j] & v:\n", " wires += [ crc0[j] ]\n", " mc += '1' if B[j] & v else '0'\n", "\n", " v <<= 1\n", "\n", " print(md, mc)\n", " \n", " if len(wires) > 0:\n", " first = wires[0]\n", " for e in wires[1:]:\n", " first = first ^ e\n", " connections += [ crc1[i].set(first) ]\n", " else:\n", " raise(ValueError, \"Bad CRC bit. Probably broken polynom.\")\n", " \n", " return connections\n" ] }, { "cell_type": "markdown", "id": "6bb774be", "metadata": {}, "source": [ "## The CRC unit\n", "\n", "This actually creates the hardware. Note that we don't optimize logic here. We'll leave that to the synthesizer toolchain." ] }, { "cell_type": "code", "execution_count": 7, "id": "52b772d2", "metadata": {}, "outputs": [], "source": [ "@block\n", "def crc_unit(clk, en, reset, din, crcout, M, N, POLY, STARTVAL):\n", " crc = Signal(intbv(STARTVAL)[M:])\n", " crcnext = [ Signal(bool(), name = 'c%d' % i) for i in range(M) ]\n", " \n", " print(\"generate matrices...\") \n", " M1, M2 = gen_matrices(M, N, serial_crc, POLY)\n", " print(\"create xor map\")\n", " wires = gen_crc_xor(M1, M2, din, crc, crcnext)\n", " \n", " @genprocess(clk, EDGE=clk.POS, RESET=reset)\n", " def crc_init():\n", " yield [ crc.set(concat(*reversed(crcnext))) ] \n", "\n", " connections = [ crcout.set(crc) ]\n", " \n", " return locals()" ] }, { "cell_type": "code", "execution_count": 8, "id": "92a4157e", "metadata": {}, "outputs": [], "source": [ "def test(DW, CW, POLYNOM):\n", " clk = ClkSignal()\n", " data = Signal(intbv()[DW:])\n", " crc = Signal(intbv()[CW:])\n", " r = ResetSignal(ResetSignal.POS_SYNC)\n", " inst = crc_unit(clk, True, r, data, crc, CW, DW, POLYNOM, 0xffffffff)\n", " \n", " tmp = inst.elab(targets.VHDL)\n", " return tmp" ] }, { "cell_type": "code", "execution_count": 9, "id": "d9651e49", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "FALLBACK: UNHANDLED ROOT CLASS , create new context\n", "generate matrices...\n", "create xor map\n", "01000001 00000000000000000000000010000010\n", "11000011 00000000000000000000000011000011\n", "11000111 00000000000000000000000011100011\n", "10001110 00000000000000000000000001110001\n", "01011101 00000000000000000000000010111010\n", "11111011 00000000000000000000000011011111\n", "11110110 00000000000000000000000001101111\n", "10101101 00000000000000000000000010110101\n", "00011011 10000000000000000000000011011000\n", "00110110 01000000000000000000000001101100\n", "00101101 00100000000000000000000010110100\n", "00011011 00010000000000000000000011011000\n", "01110111 00001000000000000000000011101110\n", "11101110 00000100000000000000000001110111\n", "11011100 00000010000000000000000000111011\n", "10111000 00000001000000000000000000011101\n", "00110001 00000000100000000000000010001100\n", "01100010 00000000010000000000000001000110\n", "11000100 00000000001000000000000000100011\n", "10001000 00000000000100000000000000010001\n", "00010000 00000000000010000000000000001000\n", "00100000 00000000000001000000000000000100\n", "00000001 00000000000000100000000010000000\n", "01000011 00000000000000010000000011000010\n", "10000110 00000000000000001000000001100001\n", "00001100 00000000000000000100000000110000\n", "01011001 00000000000000000010000010011010\n", "10110010 00000000000000000001000001001101\n", "01100100 00000000000000000000100000100110\n", "11001000 00000000000000000000010000010011\n", "10010000 00000000000000000000001000001001\n", "00100000 00000000000000000000000100000100\n", " Writing 'crc_unit' to file /tmp/myirl_crc_unit_d8awyayc/crc_unit.vhdl \n" ] }, { "name": "stderr", "output_type": "stream", "text": [ "/home/testing/.local/lib/python3.9/site-packages/myirl-0.0.0-py3.9-linux-x86_64.egg/myirl/kernel/components.py:189: UserWarning: @component `crc_unit` interface :Unspecified port I/O 'clk' => IN\n", " base.warnings.warn((msg + \" => IN\") % n)\n", "/home/testing/.local/lib/python3.9/site-packages/myirl-0.0.0-py3.9-linux-x86_64.egg/myirl/kernel/components.py:189: UserWarning: @component `crc_unit` interface :Unspecified port I/O 'reset' => IN\n", " base.warnings.warn((msg + \" => IN\") % n)\n", "/home/testing/.local/lib/python3.9/site-packages/myirl-0.0.0-py3.9-linux-x86_64.egg/myirl/kernel/components.py:189: UserWarning: @component `crc_unit` interface :Unspecified port I/O 'din' => IN\n", " base.warnings.warn((msg + \" => IN\") % n)\n", "/home/testing/.local/lib/python3.9/site-packages/myirl-0.0.0-py3.9-linux-x86_64.egg/myirl/kernel/components.py:186: UserWarning: @component `crc_unit` interface :Unspecified port I/O 'crcout' => OUT\n", " base.warnings.warn((msg + \" => OUT\") % n)\n" ] } ], "source": [ "POLYNOM = 0b100000100110000010001110110110111\n", "\n", "tmp = test(8, 32, POLYNOM)" ] }, { "cell_type": "code", "execution_count": 10, "id": "36213fb3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "-- File generated from source:\r\n", "-- /tmp/ipykernel_30595/2321360645.py\r\n", "-- (c) 2016-2022 section5.ch\r\n", "-- Modifications may be lost, edit the source file instead.\r\n", "\r\n", "library IEEE;\r\n", "use IEEE.std_logic_1164.all;\r\n", "use IEEE.numeric_std.all;\r\n", "\r\n", "library work;\r\n", "\r\n", "use work.txt_util.all;\r\n", "use work.myirl_conversion.all;\r\n", "\r\n", "entity crc_unit is\r\n", " port (\r\n", " clk : in std_ulogic;\r\n", " reset : in std_ulogic;\r\n", " din : in unsigned(7 downto 0);\r\n", " crcout : out unsigned(31 downto 0)\r\n", " );\r\n", "end entity crc_unit;\r\n", "\r\n", "architecture myIRL of crc_unit is\r\n", " -- Local type declarations\r\n", " -- Signal declarations\r\n", " signal crc : unsigned(31 downto 0);\r\n", " signal c31 : std_ulogic;\r\n", " signal c30 : std_ulogic;\r\n", " signal c29 : std_ulogic;\r\n", " signal c28 : std_ulogic;\r\n", " signal c27 : std_ulogic;\r\n", " signal c26 : std_ulogic;\r\n", " signal c25 : std_ulogic;\r\n", " signal c24 : std_ulogic;\r\n", " signal c23 : std_ulogic;\r\n", " signal c22 : std_ulogic;\r\n", " signal c21 : std_ulogic;\r\n", " signal c20 : std_ulogic;\r\n", " signal c19 : std_ulogic;\r\n", " signal c18 : std_ulogic;\r\n", " signal c17 : std_ulogic;\r\n", " signal c16 : std_ulogic;\r\n", " signal c15 : std_ulogic;\r\n", " signal c14 : std_ulogic;\r\n", " signal c13 : std_ulogic;\r\n", " signal c12 : std_ulogic;\r\n", " signal c11 : std_ulogic;\r\n", " signal c10 : std_ulogic;\r\n", " signal c9 : std_ulogic;\r\n", " signal c8 : std_ulogic;\r\n", " signal c7 : std_ulogic;\r\n", " signal c6 : std_ulogic;\r\n", " signal c5 : std_ulogic;\r\n", " signal c4 : std_ulogic;\r\n", " signal c3 : std_ulogic;\r\n", " signal c2 : std_ulogic;\r\n", " signal c1 : std_ulogic;\r\n", " signal c0 : std_ulogic;\r\n", "begin\r\n", " \r\n", "crc_init:\r\n", " process(clk, reset)\r\n", " begin\r\n", " if rising_edge(clk) then\r\n", " if reset = '1' then\r\n", " crc <= x\"ffffffff\";\r\n", " else\r\n", " 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);\r\n", " end if;\r\n", " end if;\r\n", " end process;\r\n", " c0 <= (((din(6) xor din(0)) xor crc(24)) xor crc(30));\r\n", " c1 <= (((((((din(7) xor din(6)) xor din(1)) xor din(0)) xor crc(24)) xor crc(25)) xor crc(30)) xor crc(31));\r\n", " 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));\r\n", " c3 <= (((((((din(7) xor din(3)) xor din(2)) xor din(1)) xor crc(25)) xor crc(26)) xor crc(27)) xor crc(31));\r\n", " 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));\r\n", " 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));\r\n", " 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));\r\n", " 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));\r\n", " 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));\r\n", " 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));\r\n", " 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));\r\n", " 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));\r\n", " 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));\r\n", " 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));\r\n", " 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));\r\n", " 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));\r\n", " c16 <= ((((((din(5) xor din(4)) xor din(0)) xor crc(8)) xor crc(24)) xor crc(28)) xor crc(29));\r\n", " c17 <= ((((((din(6) xor din(5)) xor din(1)) xor crc(9)) xor crc(25)) xor crc(29)) xor crc(30));\r\n", " c18 <= ((((((din(7) xor din(6)) xor din(2)) xor crc(10)) xor crc(26)) xor crc(30)) xor crc(31));\r\n", " c19 <= ((((din(7) xor din(3)) xor crc(11)) xor crc(27)) xor crc(31));\r\n", " c20 <= ((din(4) xor crc(12)) xor crc(28));\r\n", " c21 <= ((din(5) xor crc(13)) xor crc(29));\r\n", " c22 <= ((din(0) xor crc(14)) xor crc(24));\r\n", " c23 <= ((((((din(6) xor din(1)) xor din(0)) xor crc(15)) xor crc(24)) xor crc(25)) xor crc(30));\r\n", " c24 <= ((((((din(7) xor din(2)) xor din(1)) xor crc(16)) xor crc(25)) xor crc(26)) xor crc(31));\r\n", " c25 <= ((((din(3) xor din(2)) xor crc(17)) xor crc(26)) xor crc(27));\r\n", " 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));\r\n", " 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));\r\n", " c28 <= ((((((din(6) xor din(5)) xor din(2)) xor crc(20)) xor crc(26)) xor crc(29)) xor crc(30));\r\n", " c29 <= ((((((din(7) xor din(6)) xor din(3)) xor crc(21)) xor crc(27)) xor crc(30)) xor crc(31));\r\n", " c30 <= ((((din(7) xor din(4)) xor crc(22)) xor crc(28)) xor crc(31));\r\n", " c31 <= ((din(5) xor crc(23)) xor crc(29));\r\n", " crcout <= crc;\r\n", "end architecture myIRL;\r\n", "\r\n" ] } ], "source": [ "!cat {tmp[0]}" ] }, { "cell_type": "markdown", "id": "4155fa27-83da-4bdf-872d-987228bc0c0d", "metadata": {}, "source": [ "### TODO: Co-Simulation against 'golden' implementations" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.2" } }, "nbformat": 4, "nbformat_minor": 5 }