CRC Lookup Table Generation

[dkinzer]

In some circumstances, the iterative algorithm used by the built-in CRC16 and CRC32 functions may take too long for a particular application. In such cases, using a lookup table may provide the increase in speed that is needed. If you cannot find a lookup table for the particular CRC algorithm that you need, the code below can be used to generate the table if you know the Rocksoft model parameters for the CRC algorithm. The Rocksoft model parameters for some popular CRC algorithms can be found at http://regregex.bbcmicro.net/crc-catalogue.htm.

Code: Select all

#pragma warning(7:off)
'----------------------------------------------------------------------
'
' This code is intended to produce the data for a CRC lookup table
' in the form of an initialized ProgMem data table.  The program
' is essentially a translation to ZBasic of the C code published
' by Ross Williams (see http://www.ross.net/crc/crcpaper.html).
' The code will only produce a suitable table for a CRC having
' Rocksoft model parameters refIn and refOut that are the same,
' either both True or both False.  Only CRC widths 8, 16 and 32
' are supported.
'
' Once the program is configured (by modifying the Const definitions
' below), running it will output a 256-entry table.  If you run
' this program in the ZBasic IDE, you can select the output using
' the mouse, copy it to the clipboard and then paste it into 
' your program.
'
' This code is placed in the public domain by the author (Donald Kinzer)
' and may be used freely for any purpose.  No warranty is made as to
' correctness nor as to suitability for any particular purpose.  Use at
' your own risk.
'
'----------------------------------------------------------------------

'Rocksoft CRC model parameters
Private Const reflect as Boolean = False     ' if the input (and output) are reflected
Private Const poly as UnsignedLong = &H31    ' the CRC polynomial
Private Const crcBits as Byte = 8            ' the number of bits in the CRC value

' output format control
Private Const hexFormat as Boolean = True   ' if output shoud be in hexadecimal form
Private Const entriesPerLine as Byte = 16   ' number of entries per line in output

Sub Main()
    If &#40;&#40;crcBits <> 8&#41; And &#40;crcBits <> 16&#41; And &#40;crcBits <> 32&#41;&#41; Then
        Debug.Print "The CRC bit width must be 8, 16 or 32"
    Else
        ' generate the lookup table
        Dim i as UnsignedInteger
        Dim entry as UnsignedLong
        Dim cnt as Byte = 0
        For i = 0 to 255
            ' compute and output an entry
            entry = computeEntry&#40;CByte&#40;i&#41;&#41;
            Call outputEntry&#40;entry&#41;

            ' emit spacing, EOL, etc.
            cnt = cnt + 1
            If &#40;i = 255&#41; Then
                Debug.Print
            ElseIf &#40;entriesPerLine > 1&#41; And &#40;cnt >= entriesPerLine&#41; Then
                Debug.Print ","
                cnt = 0
            Else
                Debug.Print ", ";
            End If
        Next i
    End If
End Sub

'
'' computeEntry
'
' Compute the Nth entry of the CRC lookup table.
'
Private Function computeEntry&#40;ByVal n as Byte&#41; as UnsignedLong
    Const bitMask as UnsignedLong = Shl&#40;1, crcBits - 1&#41;

    ' compute the value of the entry
    Dim val as UnsignedLong
    If &#40;reflect&#41; Then
        val = CULng&#40;FlipBits&#40;n&#41;&#41;
    Else
        val = CULng&#40;n&#41;
    End If
    If &#40;crcBits > 8&#41; Then
        val = Shl&#40;val, crcBits - 8&#41;
    End If
    Dim i as Byte
    For i = 1 to 8
        If &#40;&#40;val And bitMask&#41; <> 0&#41; Then
            val = Shl&#40;val, 1&#41; Xor poly
        Else
            val = Shl&#40;val, 1&#41;
        End If
    Next i
    computeEntry = val
End Function

'
'' outputEntry
'
' Output an entry of the CRC lookup table.
'
Private Sub outputEntry&#40;ByVal entry as UnsignedLong&#41;
    ' output the entry
    Select Case crcBits
    Case 8        ' 8-bit CRC
        Dim val as Byte = LoByte&#40;entry&#41;
        If &#40;reflect&#41; Then
            val = FlipBits&#40;val&#41;
        End If
        If &#40;hexFormat&#41; Then
            Debug.Print "&H"; CStrHex&#40;val&#41;;
        Else
            Dim str as String = "  " & CStr&#40;val&#41;
            Debug.Print Right&#40;str, 3&#41;;
        End If

    Case 16        ' 16-bit CRC
        Dim val as UnsignedInteger = LoWord&#40;entry&#41;
        If &#40;reflect&#41; Then
            val = MakeWord&#40;FlipBits&#40;HiByte&#40;val&#41;&#41;, FlipBits&#40;LoByte&#40;val&#41;&#41;&#41;
        End If
        If &#40;hexFormat&#41; Then
            Debug.Print "&H"; CStrHex&#40;val&#41;;
        Else
            Dim str as String = "    " & CStr&#40;val&#41;
            Debug.Print Right&#40;str, 5&#41;;
        End If

    Case 32        ' 32-bit CRC
        If &#40;reflect&#41; Then
            Dim lo as UnsignedInteger = HiWord&#40;entry&#41;
            Dim hi as UnsignedInteger = LoWord&#40;entry&#41;
            lo = MakeWord&#40;FlipBits&#40;HiByte&#40;lo&#41;&#41;, FlipBits&#40;LoByte&#40;lo&#41;&#41;&#41;
            hi = MakeWord&#40;FlipBits&#40;HiByte&#40;hi&#41;&#41;, FlipBits&#40;LoByte&#40;hi&#41;&#41;&#41;
            entry = MakeDWord&#40;lo, hi&#41;
        End If
        If &#40;hexFormat&#41; Then
            Debug.Print "&H"; CStrHex&#40;entry&#41;;
        Else
            Dim str as String = "         " & CStr&#40;entry&#41;
            Debug.Print Right&#40;str, 10&#41;;
        End If
    End Select
End Sub