Previous: uticr Up: ../plot79_u.html Next: utida
INTEGER FUNCTION UTICRC (CHKSUM,BYTE)
C$ (CRC-16 Checksum Accumulation)
C$ Accumulate a CRC-16 cyclic redundancy checksum. The
C$ INTEGER arguments, neither of which are modified, are:
C$
C$ CHKSUM.........Current checksum value. It should be 0 for
C$ the first byte of a cumulative sequence, and
C$ set to the last returned function value on
C$ subsequent calls.
C$ BYTE...........Byte value to be included in the checksum.
C$ Only the low-order 8 bits are used.
C$
C$ The updated checksum returned as the function value is a
C$ 16-bit quantity, and it is required that INTEGER words
C$ contain at least 16 bits.
C$
C$ Cyclic redundancy checksums are superior to simple
C$ checksums obtained by adding or exclusive-OR'ing data byte
C$ sequences. Such methods cannot detect bytes out of
C$ sequence and can fail to detect even two single-bit errors,
C$ such as in two consecutive bytes with an inverted bit in
C$ the same position.
C$
C$ By contrast, the CRC-CCITT used by the ANSI X.25, ADCCP,
C$ HDLC, and IBM's SDLC protocols detects error bursts up to
C$ 16 bits in length, and 99 percent of error bursts greater
C$ than 12 bits. The CRC-16 used by DDCMP and Bisync, and
C$ implemented here, detects error bursts up to 16 bits, and
C$ 99 percent of bursts greater than 16 bits in length.
C$
C$ The associated CRC polynomial is written in order of
C$ increasing powers of 2 and 1-bits are assigned for each
C$ non-zero polynomial coefficients at corresponding positions
C$ in a 16-bit word with bit numbering 0 (high) to 15 (low),
C$ discarding any bits outside the word.
C$
C$ Two common CRC polynomials are
C$
C$ Bit positions: 11 1111 1
C$ 0123 4567 8901 2345 6
C$ 2 15 16 discard ---v
C$ CRC-16: 1 + x + x + x ==> 1010 0000 0000 0001 1
C$
C$ 5 12 16 discard ---v
C$ CRC-CCITT: 1 + x + x + x ==> 1000 0100 0000 1000 1
C$
C$ giving the following values in bases 8, 10, and 16:
C$
C$ CRC-16 constant = 8#120001 = 10#40961 = 16#A001
C$ CRC-CCITT constant = 8#102010 = 10#33800 = 16#8408
C$
C$ Simple code for the CRC accumulation looks as follows (all
C$ variables being INTEGERs of 16 or more bits). Only the
C$ constant CRCCON changes according to the CRC polynomial
C$ used. This is slow in software but is easily implemented
C$ by hardware shift registers and XOR gates.
C$
C$ DATA CRCCON / 40961 /
C$
C$ TEMP = IBTAND(BYTE,255)
C$ TEMP = IBTXOR(TEMP,CHKSUM)
C$ DO FOR BIT = 0,7
C$ BITLO = IBTAND(TEMP,1)
C$ TEMP = IBTSHR(TEMP,1)
C$ IF (BITLO .EQ. 1) TEMP = IBTXOR(TEMP,CRCCON)
C$ END FOR
C$ CRC = TEMP
C$
C$ That is, after exclusive-OR'ing the 8-bit byte with the
C$ current checksum, each of the low-order 8 bits of the
C$ result is used to determine whether or not to perform
C$ another exclusive-OR of the shifted value with the CRC
C$ constant. With CRC-16, CHKSUM is initially 0, while with
C$ CRC-CCITT, CHKSUM must be initialized to all 1 bits. On
C$ subsequent calls, CHKSUM must be replaced by the function
C$ value CRC.
C$
C$ By preprocessing, it is possible to reduce the inner loop
C$ to 4 steps using shifts of 2 bits and a table of 4
C$ constants, 2 steps using shifts of 4 bits and a table of 16
C$ constants, and 1 step (used here) using a shift of 8 bits
C$ and a table of 256 constants. SFTRAN3 implementations of 3
C$ of these 4 alternatives on the DEC-20/60 had timings (in
C$ microsec/byte) of about 152 (8-step) to 57 (2-step) to 40
C$ (1-step). An efficient 1-step assembly language
C$ implementation on the same machine with a compile-time
C$ constant table required only 7.9 microsec/byte and took
C$ only 8 instructions.
C$
C$ Implementation Note:
C$
C$ In order to achieve machine independence, the table of
C$ constants is constructed at run-time on the first call,
C$ since it contains values which when represented as positive
C$ decimal integers require 16 data bits. On 16-bit machines,
C$ only 15 data bits are available for positive integers. If
C$ the host FORTRAN does not preserve local variables across
C$ subroutine calls, then UNSET and TABLE should be placed in
C$ COMMON (if this would preserve them), or referenced in a
C$ FORTRAN 77 SAVE statement. For checking purposes, or
C$ system-dependent modifications which change the run-time
C$ initialization to compile-time initialization via DATA
C$ statements, the actual values of the table entries are
C$ given below in comments.
C$ (03-OCT-85)