VAX Instruction of the Week

7 August 1995

CRC

Calculate Cyclic Redundancy Check

Purpose:
Communications or software redundancy checks. Format:
opcode tbl.ab, inicrc.rl, strlen.rw, stream.ab

Operation:
(Diagram omitted)

Condition Codes:
N <- R0 LSS 0;
Z <- R0 EQL 0;
V <- 0;
C <- C;

Exceptions
None

Opcodes
0B CRC

Description:
The CRC of the data stream described by the string descriptor is calculated. The initial CRC is given by inicrc and is normally 0 or -1 unless the CRC is calculated in several steps. R0 is replaced by the result. If the polynomial is less than order-32, the result must be extracted from R0. The CRC polynomial is expressed by the contents of the 16-longword table. See the notes for the calculation of the table.

Notes:

  1. If the data stream is not a multiple of 8 bits long, it must be right-adjusted with leading zero fill.
  2. If the CRC polynomial is less than order-32, the result must be extracted from the low-order bits of R0.
  3. The following algorithm can be used to calculate the CRC table given a polynomial expressed as follows:
    poly<n> <- {coefficient of x ** {order-1-n}}
    This routine is available as system library routine LIB$CRC_TABLE(poly.rl, table.ab). The table is the location of a 64-byte (16-longword) table into which the result will be written.
        SUBROUTINE LIB$CRC_TABLE (POLY, TABLE)
        INTEGER*4 POLY, TABLE(0:15), TMP, X
        DO 190 INDEX=0, 15
        TMP = INDEX
        DO 150 I=1,4
        x = TMP .AND. 1
        TMP = 1SHFT(TMP, -1) !logical shift right one bit
        IF (X .EQ. 1) TMP = TMP .XOR. POLY
        .
        .
        .
    150 CONTINUE
        TABLE(INDEX) = TMP
    190 CONTINUE
        RETURN
        END
    
  4. The following are descriptions of some commonly used CRC polynomials.

    CRC-16 (used in DDCMP and Bisync)
    polynomial: x**16 + x**15 + x**2 + 1
    poly: 120001 (octal)
    initialize: 0
    result: R0 <15:0>

    CCITT (used in ADCCP, HDLC, SDLC)
    polynomial: x**16 + x**12 + x**5 + 1
    poly: 102010 (octal)
    initialize: -1 <15:0>
    result: complement of R0 <15:0>

    AUTODIN-II
    polynomial: x**32 + x**26 + x**23 + x**22 + x**16 + x**12 + x**11 + x**10 + x**8 + x**7 + x**5 + x**4 + x**2 + x + 1
    poly: EDB88320 (hex)
    initialize: -1 <31:0>
    result: complement of R0 <31:0>

  5. This instruction produces an unpredictable result unless the table is well-formed, such as produced in Note 3. Note that for any well-formed table, entry [0] is always 0 and entry [8] is always the polynomial expressed as in Note 3. The operation can be implemented using shifts of one, two or four bits at a time as follows:
          steps index     table
          per   table     multi- use table
    shift byte  index     plier  entries
    1     8     tmp3<0>   8      [0]=0,[8]
    2     4     tmp3<1:0> 4      [0]=0,[4],[8],[12]
    4     2     tmp3<3:0> 1      all
    
  6. If the stream has zero length, the destination receives the initial CRC.


Portions of this page were taken from "VAX Architecture Handbook", Copyright © 1981 Digital Equipment Corporation, All Rights Reserved. Used without permission.
Home - Send me mail