============
Introduction
============
In telecommunications applications, it is often desirable to have some
means of determining whether or not a stream of data has been transmitted
correctly. One popular method for verifying transmissions is the
checksum - the sending system performs some mathematical computation on the
original message, producing a number, which is then transmitted along with
the message itself. The receiving system then performs the same
computation on the received message, and compares its computed number with
the number that it received along with the message. If the two numbers
don't match, then the message has been garbled somehow. If the numbers do
match, the message is not guaranteed to be ungarbled, because it is
possible for a corrupted message to have the same checksum as an
uncorrupted message, but at least the likelihood of a transmission error
slipping though undetected is less when a checksum is used.
The trick, then, is to choose a checksum algorithm carefully, so that the
kinds of errors that usually occur in data transmissions (reversed bits,
dropped bits, added bits, etc.) will produce a significant change in the
checksum. The cyclic redundancy checks (CRCs) are a popular class of
checksums which have this property. Many different CRCs are possible, but
only a few of them seem to be in common use. Two of the most common
CRCs are described below - one produces a 16-bit checksum, and the other
produces a 32-bit checksum.
A CRC is essentially binary long division -- the message to be checksummed
is divided by the CRC "polynomial," and the remainder is the CRC checksum.
The difference between the CRC "division" and ordinary division is that
when a CRC is computed, exclusive-OR's are used instead of subtractions.
Computing the long division for the entire data stream a bit at a time is
slow and inefficient. Fortunately, it it not necessary to do it that way;
a considerable amount of time can be saved by pre-computing the CRCs of
the 256 possible 8-bit bytes. This allows the checksum to be computed a
byte at a time instead of a single bit at a time.
The price we pay for saving all that time is memory. A block of memory must
be set aside somewhere for 256 pre-computed remainders.
==========
16-Bit CRC
==========
The following source code is a 6502 implementation of the traditional
16-bit CRC found in such applications as Xmodem, BinSCII, and Shrinkit.
Strictly speaking, I believe this implementation is "wrong" according to
the CRC standard (it uses the wrong bit order), but this "wrong" form seems
to have a long history of usage in a wide variety of software.
These routines, though original, were heavily inspired by a similar set of
routines by Andy Nicholas. Source code for the Andy Nicholas routines can
be found in the File Type Note for file type $E0, aux type $8002 (Shrinkit
archives).
First, the initialization routine. This should be called once before
calculating any CRCs. It doesn't need to be called again unless the CRC
data tables get overwritten.
* INITCRC -- initialize CRC data table
* by Neil Parker
*
W EQU 6 ;A scratchpad variable--can be anywhere in memory
*
INITCRC LDY #0 ;Y-reg contains byte to be CRC'd
L1 LDA #0 ;Init 2nd byte of dividend to 0
STA W
TYA ;Get CRC byte into 1st byte of dividend
LDX #8 ;Loop over 8 bits
L2 ASL W ;Shift dividend & catch hi bit in C
ROL ;(some assemblers may require ROL A here)
BCC L3 ;If 0, go do next bit...
EOR #$10 ;...else EOR dividend with polynomial
PHA
LDA W
EOR #$21
STA W
PLA
L3 DEX ;Done 8 bits yet?
BNE L2 ;If not, loop...
STA CRCTAB0,Y ;...else save remainder in table
LDA W
STA CRCTAB1,Y
INY ;Done 256 bytes yet?
BNE L1 ;If not, loop...
RTS ;...else we're done
*
CRCTAB0 DS 256 ;Data table for CRC remainders
CRCTAB1 DS 256
Once the CRC remainder table is set up, you're ready to calculate CRCs. The
subroutine below performs the calculation.
* DOCRC -- accumulate a byte into CRC checksum
*
CRC0 EQU 7 ;1st byte of CRC checksum
CRC1 EQU 8 ;2nd byte of CRC checksum
*
DOCRC EOR CRC0
TAY
LDA CRCTAB0,Y
EOR CRC1
STA CRC0
LDA CRCTAB1,Y
STA CRC1
RTS
The exact steps for using these routines are as follows:
Call INITCRC.
Initialize the memory locations CRC0 and CRC1. They should
usually be initialized to 0, but not always - for example, one
of the CRCs used in Shrinkit requires that they be initialized
to $FF.
For each byte of the message:
Load the byte into the accumulator.
Call DOCRC (which will scramble the A and Y registers).
Get the checksum from CRC0 and CRC1.
Usually, CRC1 is transmitted first, followed by CRC0.
IIGS programmers will probably not be suprised to to learn that the
initialization routine is smaller and more efficient in native-mode 65816
code.
longa on
longi on
; Call with 16-bit M and X
InitCRC ldy #$1FE ;Y-reg contains index into remainder table
L1 tya ;Convert index into byte to be CRC'd
lsr A ;Compensate for two-byte table entries
xba ;CRC byte -> hi byte, 0 -> low byte
ldx #8 ;Loop over 8 bits
L2 asl A ;Catch hi bit in C flag
bcc L3 ;If clear, go onto next bit...
eor #$1021 ;...else EOR with CRC polynomial
L3 dex ;Done 8 bits yet?
bne L2 ;If not, go do more bits...
sta CRCTab,Y ;...else store remainder
dey
dey ;Done 256 bytes yet?
bpl L1 ;If not, go do more...
rts ;...else return to caller
CRCTab ds 512
The CRC calculation routine, however, does not benefit from 16-bit code.
This routine leaves the first byte of the checksum in CRC and the second
byte in CRC+1.
CRC equ 0 ;(on direct page, for max efficiency)
longa on
longi on
; Call with any size M and X
DoCRC php
rep #$30
eor