Path: ns-mx!iowasp.physics.uiowa.edu!ceres.physics.uiowa.edu!zaphod.mps.ohio-state.edu!rpi!uwm.edu!bionet!agate!ucbvax!dog.ee.lbl.gov!nosc!crash!pro-sol.cts.com!mdavis
From: mdavis@pro-sol.cts.com (Morgan Davis)
Newsgroups: comp.sys.apple2
Subject: Re: CRCs
Message-ID: <8720@crash.cts.com>
Date: 21 Apr 91 20:36:04 GMT
Sender: root@crash.cts.com
Lines: 78

In-Reply-To: message from rhyde@ucrmath.ucr.edu

Excellent article on CRC's, Randy.  This is one to tuck away in the
programmer's notes for sure.

I went through this kind of wracking to find a more optimal algorithm.  The
table method is, by far, the best when it comes to speed.  Though,
sometimes just a quick and dirty (or maybe that should be "small and
dirty") variation is to use the following:

CalcCRC (ptr, count)
        char *ptr;
        word count;
{
        register word x;
               
        do {
                CRC ^= *ptr++ << 8;     /* XOR hi-byte with data */
                for (x = 8; x; --x)
                        if (CRC & 0x8000)
                                CRC = CRC << 1 ^ 0x1021;
                        else
                                CRC <<= 1;
        } while (--count);
}

This function operates on a global named CRC.  You call it by pointing to a
data buffer, and passing the size of the buffer.  After calling CaclCRC()
the CRC global integer is updated accordingly.

The optimizations here that differ from the original, frequently published
version is that it:

o       Counts from 8 bits down to none, so the loop
        test simply involves a test for zero instead of
        comparing to 8.

o       Bit 15 of the CRC is tested with the bitwise AND
        operation instead of shifting it around to determine
        if the CRC needs the XOR treatment.

o       It operates on a buffer, rather than having to pass
        it a byte of data to work on, one at a time.

This optimization was done with the 65816 in mind.  So these kinds of
optimizations may not make any difference on other processors, but I
doubt if they would hurt.

BTW, the 65816 variant on the above is:

CalcCRC         ldy     #0              ;index into buffer
newbyte         shortm                  ;go to 8-bits
                lda     [ptr],y         ;grab some data
                iny                     ;prepare for next byte
                eor     CRC+1           ;fix high-order byte of CRC
                sta     CRC+1
                longm                   ;back to 16-bit

                ldx     #8              ;init shift counter
shift           asl     CRC             ;always shift it once
                bcc     next            ;if bit 15 clear, skip the XOR

                lda     CRC             ;XOR CRC with $1021
                eor     #$1021
                sta     CRC
next            dex
                bne     shift           ;do this 8 times

                dec     count           ;more bytes to do?
                bne     newbyte         ;yes

                rts

--Morgan

UUCP: crash!pro-sol!mdavis           AOL, BIX: mdavis  
ARPA: crash!pro-sol!mdavis@nosc.mil  GEnie:    m.davis42
INET: mdavis@pro-sol.cts.com         ProLine:  mdavis@pro-sol