A Very Fast Linear CRC Routine

a new and novel approach to calculating a real-time CRC written over a couple of days in 1984 by Ivars Vilums & Aubrey McIntosh

"We did a 16 bit CRC in about 10 assembly instructions with
1) no loops
2) no tables
and it ran 34Kb data rates on a 4 MHz 8086 (1984). It would run faster for you if you do not have to use the brain dead reverse bit order defined by the existing CRC definitions. Ivars Vilums had the code posted on his web page (see Internet Archive Wayback Machine for archived copy of http://www.underware.com/ijv/crc.htm as of Dec. 27, 1997). Our algorithm is easily extended to other polynomials, and the standard polynomials may be changed by the change of a 16 bit constant. The processor must have a parity bit, and a jump on parity instruction, which the 8086 did have. It is my offhand opinion that this code could be adapted to 8 bit CRC easily."
--from a Usenet posting by Aubrey McIntosh on 11/7/1998

"It was actually a few instructions longer and did have a short table to quickly reverse the bit order of the nybble. Even so, it was still the fastest CRC routine around. The original code was written for a Z80 processor where it was actually shorter and then translated to the 8086/8088 for use in a BiSync Communications module for a 3741 Data Entry Station emulator being written by Ivars Vilums for the then-new IBM PC. It had to be fast because back then a fast CPU ran at 4MHz and all of the details of the BiSync communications had to be handled by the application code, including on-the-fly ASCII/EBCDIC and EBCDIC/ASCII conversions in real time.

I was unhappy with the existing algorithms available to generate a CRC at the time so Aubrey and I, over the course of a weekend, took a step back and discovered an entirely new approach that always produced the identical results in a not so obvious but very efficient manner."
--Ivars Vilums

;A Very Fast Linear CRC Routine
;by Ivars Vilums & Aubrey McIntosh - 1984
;------------------------------------------------------------------
;8086 assembly language

;------------------------------------------------------------------
                ;Magic Constant - change for other polynomials
PCONSTANT       EQU             08003H          ;constant xor'd if parity odd
                                                ;during crc.
                                                ;8003H is for Bisync Protocol CRC
;------------------------------------------------------------------
                ;CRC routines
                ;=============
                ;reverses bit order of byte in AL
                ; destroys AH
REVBYTE         PROC            NEAR
                MOV             AH,AL           ;save it
                MOV             BX,OFFSET REVTABLE
                AND             AL,0FH          ;mask for lo nybble
                XLAT                            ;flip nybble
                XCHG            AL,AH           ;get other nybble
                SHR             AL,1
                SHR             AL,1
                SHR             AL,1
                SHR             AL,1
                XLAT
                SHL             AH,1
                SHL             AH,1
                SHL             AH,1
                SHL             AH,1
                OR              AL,AH
                RET
REVTABLE:
                DB              0,8,4,0CH       ;table of reverse nybbles
                DB              2,0AH,6,0EH
                DB              1,9,5,0DH
                DB              3,0BH,7,0FH
REVBYTE         ENDP
                ;-------------------
                ;insert argument into crc and return new value
ADDTOCRC        PROC            NEAR
                CALL            REVBYTE
                XOR             AH,AH
                MOV             DH,CRCHI
                MOV             DL,CRCLO
                ;really starts here
                XCHG            DH,DL           ;create struct. 2 in place
                XOR             AL,DL           ;create mask for struct. 3
                                                ;and test for struct. 1
                XCHG            DL,AH           ;clear out DL
                JP              PDONE           ;XOR all bits is same as parity
                XOR             DX,PCONSTANT    ;xor struct. 1 if needed
PDONE:          XOR             AH,AH           ;clear out the reg again
                SHL             AX,1            ;position and place struct. 3
                XOR             DX,AX
                SHL             AX,1
                XOR             DX,AX
                MOV             CRCLO,DL
                MOV             CRCHI,DH
                RET
ADDTOCRC        ENDP
                ;-------------------

Go to the home page of