CRC-32 International Standard 32-Bit CRC

Wil Baden 2001-10-22

The subject of this article is calculation of the International Standard 32-bit CRC, cyclical redundancy check. It uses nonce-words as throw-away definitions to build a table to speed it up.

CRC-32-Table, Calculate-CRC-32, and CRC-32 are permanent definitions. The words between CRC-32-Table and Calculate-CRC-32 are compiled, executed, and forgotten.

For testing, Little-Endian-! and CRC-TEST are also permanent definitions.

With CRC-32 the user should precondition the check-sum to TRUE (all bits on). For every byte read, CRC-32 uses Calculate-CRC-32 to update the check-sum.

When CRC-32 has finished reading, it postconditions the check-sum with INVERT to get the CRC.

If the CRC is inverted again and added to the end of the file or string in little-endian order, the CRC of the result will be all bits on.

\  The International Standard 32-bit CRC.

CREATE CRC-32-Table   256 CELLS ALLOT

MARKER CRC-32-TABLE-INITIALIZATION

\  Define CRC-POLYNOMIAL from its coefficient terms.

: POLY
    32 26 23 22 16 12 11 10 8 7 5 4 2 1 0   ( ...)
      0 BEGIN                               ( ... poly)
          SWAP                              ( ... poly bit)
          DUP 32 <>
      WHILE
          31 XOR  1 SWAP LSHIFT  OR         ( ... poly)
      REPEAT                                ( ... poly bit)
      DROP                                  ( poly)
; POLY CONSTANT CRC-POLYNOMIAL  ( )

CR .( \ CRC-POLYNOMIAL is ) CRC-POLYNOMIAL  HEX U. DECIMAL  CR

CRC-POLYNOMIAL represents a polynomial with binary coefficients, 0 or 1, of the 32nd degree. In the literature it is usually written as a sum of powers of x in algebraic notation. But the coefficient of the highest exponent is always 1, not 0 - otherwise it wouldn't be of the 32nd degree. So it can be represented by 32 bits. A file or string to be checked is treated like a polynomial of degree 8 times the number of bytes all minus 1. That is, a 100,000 byte file or string is a 799,999 degree polynomial.

If you examine the code for Calculate-CRC-for-a-Byte you can see that it's doing long division the way you learned in third or fourth grade but with binary polynomials as dividend and divisor. XOR is subtraction - and addition. CRC-POLYNOMIAL is the divisor. When you're through with the file the check-sum is the remainder. The quotient is ignored throughout. CRC-32-Table contains the remainders when dividing by CRC-POLYNOMIAL.

The coefficients of CRC-POLYNOMIAL are in reverse order from the arithmetic value. This is the order in which they occur when the file is transmitted. In the polynomial the sign bit represents 1 and 1 AND represents x^31. 1 RSHIFT would shift the dividend to the left if you were doing it by hand.

After CRC-32-Table is built, CRC-POLYNOMIAL is no longer needed and is discarded together with the functions that were used to build CRC-32-Table.

: Calculate-CRC-for-a-Byte     ( i -- crc )
    8 0 DO
        dup  1 AND  IF
            1 RSHIFT  CRC-POLYNOMIAL XOR
        ELSE
            1 RSHIFT
        THEN
    LOOP ;

: Build-CRC-Table              ( -- )
    256 0 DO
        I Calculate-CRC-for-a-Byte  I CELLS CRC-32-Table + !
    LOOP ;

Build-CRC-Table

CRC-32-TABLE-INITIALIZATION   \  Discard everything after CRC-32-Table.

Display CRC-32-Table to see whether it looks OK.

The print-out has the form it does so you can copy and paste it as the definition of CRC-32-Table rather than re-constructing it in the future. You will still need the definitions of Calculate-CRC-32 and CRC-32 of course.

    MARKER ONCE
    : Print-CRC-Table
        CR ." CREATE CRC-32-Table "   CR ." HEX "
        256 0 DO
            I 4 MOD 0= IF
                CR  ." ( "  I 3 .R  ."  )  "
            THEN
            I CELLS CRC-32-Table + @
                HEX 0 <# # # # # # # # # #> TYPE ."  , " DECIMAL
        LOOP
        CR ." DECIMAL "
    ; Print-CRC-Table ONCE

Calculate-CRC-32    ( crc byte -- crc' )

Update CRC by a byte.

CRC-32              ( crc addr u -- crc' )

Compute CRC for a file or string.

: Calculate-CRC-32             ( crc byte -- crc' )
    OVER XOR  255 AND  CELLS CRC-32-Table +  @  SWAP  8 RSHIFT  XOR
    ;

: CRC-32                       ( crc addr u -- crc' )
    BOUNDS ?DO ( crc) I C@ Calculate-CRC-32  LOOP  INVERT ;

Little-Endian-!     ( n addr -- )

Store n at addr in little-endian order. If the environment arithmetic is already little-endian, this is equivalent to ! overriding alignment requirements.

CRC-TEST            ( str len -- )

Test the CRC-32 of a string.

: Little-Endian-!              ( n addr -- )
    4 BOUNDS DO ( n) dup  255 AND  I C!  8 RSHIFT  LOOP
    DROP ;

: CRC-TEST                     ( str len -- )
    dup >R
        \  Move string to PAD.
        PAD SWAP MOVE              ( )
        \  Calculate CRC.
        TRUE PAD R@                ( crc str len)
        CRC-32                     ( crc')
        \  Show it.
        CR ." \ "
        dup HEX U. DECIMAL
        \  Invert CRC and add to end of string.
        INVERT
        PAD R@ + Little-Endian-!   ( )
        \  Check CRC of the result.
        TRUE PAD R@ 4 +            ( crc str len)
        CRC-32                     ( crc')
        HEX U. DECIMAL             ( )  \  Should be all bits on.
    R> DROP ;

S" An Arbitrary String" CRC-TEST         \  Should be 6FBEAAE7 FFFFFFFF
S" ZYXWVUTSRQPONMLKJIHGFEDBCA" CRC-TEST  \  Should be 99CDFDB2 FFFFFFFF
S" 123456789" CRC-TEST                   \  Should be CBF43926 FFFFFFFF

Go back to home page.