#!/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