#!/bin/tcsh
#
# Parallel CRC Equation Generator
#
# 4/7/11: added verilog equation output! and reversed the CRC bit number and
# feedback ordering to make outputs in standard sequence
# Jason R. Gilmore, 11/25/02, The Ohio State University
# I have tested this script extensively with no errors, but no warranty
# is provided! Comments/fixes/upgrades are appreciated.
# email: gilmore@mps.ohio-state.edu
# script URL: http://www.physics.ohio-state.edu/~cms/crc_generator
#
#
# Generates parallel CRC equations for any reasonable case
# -arbitrary parallel Data width (up to 100 bits)
# -arbitrary CRC width (up to 100-bit CRC)
# -arbitrary CRC polynomial (but valid CRC requires polynomial MSB=LSB=1)
# ---> Enter the binary polynomial coefficients one-per-line as indicated.
# ---> Bit 0 is ALWAYS the LSB! This includes the coefficient for x^0.
# Summarizes # of XOR inputs needed per CRC bit
# Writes algorithm results for XOR logic to files
# Writes final set of equations in verilog format
#
#
# How to interpret the result files
# =================================
# The CRC XOR logic result for each bit is stored in a file
# - the Calculated CRC result files are named cc[bit#].crc
# The XOR signal inputs are represented by a 3-character label in each file:
# - labels d00-d99 are the input data bits for a cycle
# - labels c00-c99 are the input CRC bits for a cycle
# > "cc" working files represent "current" CRC register states
# > "nc" working files represent "next" CRC states
# - the XOR of all the signals in an output file defines the equation
# for that CRC bit
# Summary information is saved in the file crc.log
#
# Notes:
# Temproary generator files named nc[bit#].crc will be created, but
# are removed at completion.
# Files nc|nnc|cc[bit#].crc will be overwritten.
# Files crc.log crceqs.v and crc_eqs.v will be overwritten.
#
#
# Some valid (common?) CRC generator primitive polynomials
# [encoded coefficients in decimal, hex (0x) or binary (b)]
# 15-bit CRC 32771 (0x8003 = 1000/0000/0000/0011 b)
# 16-bit CRC: 0x18005 (standard CRC16 = 1/1000/0000/0000/0101 b)
# 0x11021 (CCITT = 1/0001/0000/0010/0001 b)
# 17-bit CRC: 131081 (0x20009)
# 18-bit CRC: 262183 (0x40027)
# 19-bit CRC: 524327 (0x80027)
# 20-bit CRC: 1048585 (0x100009)
# 21-bit CRC: 2097157 (0x200005)
# 22-bit CRC: 4194307, 4194361 (0x400003, 0x400039)
# 32-bit CRC: 0x104c11db7 (MAC-FCS: 1/0000/0100/1100/0001/0001/1101/1011/0111 b)
#
# References:
# "Protocols & Techniques for Data Communication Networks"
# F. Kuo (ed.), 1981 SEL TK5101.5 P77
# "The Engineer's Error Coding Handbook"
# A. Houghton, 1997 SEL TK5102.9 H68
#
echo ""
echo "Parallel CRC Equation Generator "
echo "=============================== "
GetData:
echo -n " Enter Data Width (# bits): "
set wData = $<
if ( "$wData" < 1 || "$wData" > 100 ) then
echo " $wData is not a valid Data width! "
goto GetData
endif
GetCRC:
echo -n " Enter CRC Width (# bits): "
set wCRC = $<
if ( "$wCRC" < 8 || "$wCRC" > 100 ) then
echo " $wCRC is not a valid CRC width! "
goto GetCRC
endif
#Initialize polynomial to "zero" string vector:
set p = "0"
set j = 0
while ( $j < $wCRC )
set p = "${p}\n0"
@ j++
end
set poly = `echo ${p}`
# Note that the range of the poly array is [1:wCRC+1] because
# csh arrays begin from index=1 by default. This forces an offset
# of "1" conversion for bit numbering with LSB=bit0.
echo " Enter CRC-$wCRC Polynomial binary coefficients [MSB-LSB] one-per-line"
set i = $wCRC
@ maxreg = $wCRC - 1
@ i++
set maxi = $i
while ( $i > 0 )
@ j = $i - 1
echo -n " ${j}: "
set poly[$i] = $<
if ( "${poly[$i]}" != 0 && "${poly[$i]}" != 1 ) then
echo " $poly[$i] is not a valid binary coefficient! "
else if ( ( $i == $maxi ) && ( "${poly[$i]}" == 0 ) ) then
echo " $poly[$i] is not a valid polynomial MSB coefficient! "
else if ( ( $i == 1 ) && ( "${poly[$i]}" == 0 ) ) then
echo " $poly[$i] is not a valid polynomial LSB coefficient! "
else
@ i--
if ( $i < $wCRC ) then
rm -f cc${i}.crc nc${i}.crc
echo "c["$i"]" >cc${i}.crc
touch nc${i}.crc
endif
endif
end
#OuterLoop over input data bits:
set d=0
while ( $d < $wData )
echo -n " Data bit $d..."
echo "d["$d"]" >! nc0.crc # takes care of input data bit
#InnerLoop over CRC registers, calculate next CRC values:
set i = $wCRC
echo -n "nc"
cat cc${maxreg}.crc >>! nc0.crc # takes care of req. feedback from last register, so nc0 is done.
while ( $i > 0 ) # i decreases from wCRC to 1.
@ reg = $wCRC - $i # reg increase from 0 to wCRC-1.
@ j = $reg + 1 # j increases from 1 to wCRC. j > reg always
echo -n "${reg} "
# Note: poly[wCRC+1:1]-->$i, nc[0:(wCRC-1)]-->$reg, cc[1:(wCRC)]-->$j
# poly[wCRC+1] not used: it's the MSB of the polynomial (always active)
if ( $j < $wCRC ) then
cat cc${reg}.crc >>! nc${j}.crc # this is the simple shift register part: 0->1, 1->2, etc.
endif
if ( "${poly[$j]}" == 1 && $j > 1 ) then # if poly is active then attach feedback from nc0
cat nc0.crc >>! nc${reg}.crc # covers nc1 to nc[wCRC-1]
endif
@ i--
end
echo ""
#End of NextCRC calc, move the "next" values into Calculated CRC registers:
set i = $wCRC
while ( $i > 0 )
@ i--
mv -f nc${i}.crc cc${i}.crc
end
#Shift to next data bit and continue OuterLoop:
@ d++
end
#Simplify the terms in the Calculated CRC registers.
# sort, count # of repetitions for each entry;
# basic XOR rule = keep one copy if odd count, discard if even (1 xor 1 = 0)
set nx = `echo ${p}`
set i = $wCRC
rm -f crc_eqs.v crceqs.v
touch crc_eqs.v
while ( $i > 0 )
@ j = $i - 1
echo -n " sorting for bit ${j}..."
sort -u cc${j}.crc > nc${j}.crc
rm -f nnc${j}.crc
touch nnc${j}.crc
echo "simplifying..."
echo -n "assign crc["$j"] =" >>crc_eqs.v
foreach k ( `cat nc${j}.crc` )
set n = `awk -v str="$k" '{ i=0; if($i == str) print $i;i++}' cc${j}.crc | wc | awk '{print $1}'`
@ m = ( $n / 2 ) * 2
# save entry if term is present odd# of times (XOR equvalence reduction):
if ( $m != $n ) then
echo " ${k}" >> nnc${j}.crc
echo -n " ${k} ^" >>crc_eqs.v
endif
end
echo "^" >>crc_eqs.v
set nx[$i] = `wc nnc${j}.crc | awk '{print $1}'`
@ i--
end
sed 's/ ^^/;/g' crc_eqs.v > crceqs.v
# Print the result summary ON THE SCREEN: number of XOR inputs per bit, etc.
rm -f crc.log crc_eqs.v
echo ""
echo "Settings and Result Summary "
echo "--------------------------- "
echo " Data Width = $wData CRC Width = $wCRC "
echo -n " Polynomial [MSB-LSB]: ${poly[$maxi]}"
set i = $wCRC
while ( $i > 0 )
echo -n "${poly[$i]}"
@ i--
end
echo ""
echo ""
echo " Number of XOR inputs required for each CRC bit "
set i = $wCRC
while ( $i > 0 )
@ j = $i - 1
rm -f cc${j}.crc nc${j}.crc
echo " ${j}: ${nx[$i]} "
mv -f nnc${j}.crc cc${j}.crc
@ i--
end
# Now write the result summary TO FILE CRC.LOG
echo "" > crc.log
echo "Parallel CRC Equation Generator " >> crc.log
echo "=============================== " >> crc.log
echo " Settings and Result Summary " >> crc.log
echo "" >> crc.log
echo " Data Width = $wData CRC Width = $wCRC " >> crc.log
echo -n " Polynomial [MSB-LSB]: ${poly[$maxi]}" >> crc.log
set i = $wCRC
while ( $i > 0 )
echo -n "${poly[$i]}" >> crc.log
@ i--
end
echo "" >> crc.log
echo "" >> crc.log
echo " Number of XOR inputs required for each CRC bit " >> crc.log
set i = $wCRC
while ( $i > 0 )
@ j = $i - 1
echo " ${j}: ${nx[$i]} " >> crc.log
@ i--
end
XIT:
echo "CRC equation generation complete. "
exit