============ 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