Xref: utzoo comp.dcom.lans:6307 comp.sys.m68k:1906 comp.sys.ncr:585
Path: utzoo!attcan!uunet!midway!ncar!zaphod.mps.ohio-state.edu!wuarchive!emory!gatech!bloom-beacon!eru!hagbard!sunic!mcsun!cernvax!rbt
From: rbt@cernvax.UUCP (roberto divia)
Newsgroups: comp.dcom.lans,comp.sys.m68k,comp.sys.ncr
Subject: Re: crc32 algorithm
Keywords: crc32, fcs, 802.3
Message-ID: <2935@cernvax.UUCP>
Date: 25 Oct 90 12:52:09 GMT
References: <2117@ncrcam.Cambridge.NCR.COM>
Followup-To: comp.dcom.lans
Organization: CERN, European Laboratory for Particle Physics
Lines: 276

Fred Larimer asked for an implementation of the Autodin II CRC32 cheker.
This is written using CERN macros. Hope it will be readable...

	IDENT	CHIFC_CRC_CHECK
	TTL	'CHIFC CRC Generator/Checker'
	STTL	'Module history'
********************************************************************************
*
*	CHIFC CRC Generator/Checker
*	===========================
*
* Modification history:
*	 5 Sep 89	Created (RD)
*
* General comment: this code is completely reentrant and it should be extremely
* fast since the kernel is small enough to be cached in the program cache of the
* 68020/68030. The data cache should not make a big difference.
*
********************************************************************************
	STTL	'EQU Declarations'
	PAGE
********************************************************************************
*
*	EQU Declarations
*	================
*
PROGRAM	SECTION	R
*
	OPT	P=68020
*
	NOLIST
	SYSTEXT
	LIST	CREF
*
* CRC polynomial term:
* --------------------
*
POLY	EQU	%00000100110000010001110110110111	As for Ethernet prot.
*
EXPECT	EQU	%11000111000001001101110101111011	As before, this is the
*							expected value by the
*							CRC checker.
*
********************************************************************************
	STTL	'CRC Generator initialisation'
	PAGE
********************************************************************************
*
* CRC Generator initialisation
* ----------------------------
*
*	procedure initialise_CRC;
*
* This entry must be called before using the CRC generator/checker, to "warm up"
* the table of CRC constants.
*
	S_Entry	initialise_CRC		Main entry point
	S_Entry	_initialise_CRC		For C programs
	S_Entry	iniCRC			For FORTRAN programs
*
	lea	CRC_t,a0		Load the CRC table base address (low b)
	clr.l	d1			Initial byte value
	move.l	#POLY,d7		Load the polynomial term
IextL	move.b	d1,d2			Load the current byte value
	moveq.l	#7,d3			Initialise the bit counter (7 + 1)
	clr.l	d0			Initial CRC value (all zeros)
IintL	rol.b	#1,d2			Get the top bit (# 7) in position 0
	lsl.l	#1,d0			Prepare the next CRC
	roxl.b	#1,d4			Get the top bit of the CRC into d4 bit 0
	eor.b	d2,d4			Xor the patterns
	btst.b	#0,d4			Bit 0 is zero?
	beq.b	IdivZ			Skip if true
	eor.l	d7,d0			Otherwise xor the CRC with the POLY...
	or.b	#1,d0			...and set bit 0
IdivZ	dbra.w	d3,IintL		Loop on all bits
	move.l	d0,(a0)+		Done: save the generated CRC value
	addq.b	#1,d1			Increment the byte count
	bne.b	IextL			And loop on all the possible patterns
	rts
*
********************************************************************************
	STTL	'CRC Generator'
	PAGE
********************************************************************************
*
* CRC Generator
* -------------
*
*	procedure generate_CRC(	VAR data_buffer : INTEGER [1..num_longwords];
*				VAR num_longwords : INTEGER );
*
* The data_buffer is scanned and the generated CRC is appended after
* num_longwords + 1.
*
* All input parameters are passed by ADDRESS for FORTRAN compatibility.
*
	S_Entry	generate_CRC		Main entry point
	S_Entry	_generate_CRC		For C programs
	S_Entry	genCRC			For FORTRAN programs
*
	bsr.b	do_CRC			Generate the CRC
	eor.l	#-1,d0			Negate the pattern...
	move.l	d0,(a0)			...and save it
	rts
*
********************************************************************************
	STTL	'CRC Checker'
	PAGE
********************************************************************************
*
* CRC Checker
* -----------
*
*	function check_CRC (	VAR data_buffer : INTEGER [1..num_longwords];
*				VAR num_longwords : INTEGER ) : UNSIGNED;
*
* The data_buffer is scanned for num_longwords and the CRC is checked. The
* function returns 0 if the check succedes. This procedure assumes that the
* last longword if the data_buffer contains the CRC generated by generate_CRC.
*
* All input parameters are passed by ADDRESS for FORTRAN compatibility.
*
	S_Entry	check_CRC		Main entry point
	S_Entry	_check_CRC		For C programs
	S_Entry	chkCRC			For FORTRAN programs
*
	bsr.b	do_CRC			Generate the expected CRC
	sub.l	#EXPECT,d0		Expected value? d0 MUST be = 0
	rts
*
********************************************************************************
	STTL	'CRC generator'
	PAGE
********************************************************************************
*
*	CRC generator
*	=============
*
* This procedure is called with this stack organisation:
*
* a7 ->	"internal" return address
* +4 ->	"external" return address
* +8 -> buffer address
* +C -> number of longwords in the buffer
*
* It returns in d0 the generated CRC and in a0 the address of the first
* unused longword.
*
do_CRC	move.l	8(a7),a0		Fetch the data array address
	move.l	([$C,a7]),d1		Fetch the number of longwords counter
	asl.l	#2,d1			Compute the byte count
	moveq.l	#-1,d0			Preload the Remainder
	lea	CRC_t,a1		Fetch the CRC table base address
	moveq.l	#0,d2
	bra	endOfL			Start looping
*
* Here starts the Main Loop
*
mainL	rol.l	#8,d0			Get the top remainder byte in low byte
	move.b	(a0)+,d3		Get current data pattern
	move.b	d0,d2			Move the bottom CRC byte into d2
	move.b	#0,d0			Clear the remainder bottom byte
	eor.b	d3,d2			Compute the table index
	move.l	(a1,d2.W*4),d4		Retrieve the remainder from the table...
	eor.l	d4,d0			...and compute the current CRC
endOfL	dbra.w	d1,mainL		Loop on all the bytes
	rts
*
********************************************************************************
	STTL	'CRC Generator (Bit oriented)'
	PAGE
********************************************************************************
*
* CRC Generator (Bit oriented)
* ----------------------------
*
*	procedure Bgenerate_CRC(VAR data_buffer : INTEGER [1..num_longwords];
*				VAR num_longwords : INTEGER );
*
* The data_buffer is scanned and the generated CRC is appended after
* num_longwords + 1.
*
* All input parameters are passed by ADDRESS for FORTRAN compatibility.
*
	S_Entry	Bgenerate_CRC		Main entry point
*
	bsr.b	private			Generate the CRC
	eor.l	#-1,d0			Negate the pattern...
	move.l	d0,(a0)			...and save it
	rts
*
********************************************************************************
	STTL	'CRC Checker (Bit oriented)'
	PAGE
********************************************************************************
*
* CRC Checker (Bit oriented)
* --------------------------
*
*	function Bcheck_CRC (	VAR data_buffer : INTEGER [1..num_longwords];
*				VAR num_longwords : INTEGER ) : UNSIGNED;
*
* The data_buffer is scanned for num_longwords and the CRC is checked. The
* function returns 0 if the check succedes. This procedure assumes that the
* last longword if the data_buffer contains the CRC generated by generate_CRC.
*
* All input parameters are passed by ADDRESS for FORTRAN compatibility.
*
	S_Entry	Bcheck_CRC		Main entry point
*
	bsr.b	private			Generate the expected CRC
	sub.l	#EXPECT,d0		Expected value? d0 MUST be = 0
	rts
*
********************************************************************************
	STTL	'CRC generator (Bit oriented)'
	PAGE
********************************************************************************
*
*	CRC generator (Bit oriented)
*	============================
*
* This procedure is called with this stack organisation:
*
* a7 ->	"internal" return address
* +4 ->	"external" return address
* +8 -> buffer address
* +C -> number of longwords in the buffer
*
* It returns in d0 the generated CRC and in a0 the address of the first
* unused longword.
*
private	move.l	8(a7),a0		Fetch the data array address
	move.l	([$C,a7]),d1		Fetch the number of longwords counter
	moveq.l	#-1,d0			Preload the CRC accumulator to all 1s
	move.l	#POLY,d7		d7 contains the polynomial term
	bra	BendOfL			Start looping
*
* Here starts the Main Loop
*
BmainL	move.l	(a0)+,d2		Fetch the current Lw
	moveq.l	#31,d3			Load the bits count - 1
BbitsL	rol.l	#1,d2			Get the current bit in position 0
	lsl.l	#1,d0			Start making the next CRC
	roxl.b	#1,d4			Get into d4 bit 0 the Shift out
	eor.b	d2,d4			Exor (only bit 0 is interesting)
	btst.b	#0,d4			Bit is zero?
	beq.b	BdivZ			If true, skip next phase
	eor.l	d7,d0			Otherwise xor CRC with the POLY...
	or.b	#1,d0			...and set bit 0
BdivZ	dbra.w	d3,BbitsL		Loop on all the data bits
BendOfL	dbra.w	d1,BmainL		Loop on all the Lws in the buffer
	rts
*
********************************************************************************
	STTL	'Data area'
	PAGE
********************************************************************************
*
* Data area
* ---------
*
UNINDATA	SECTION	R
*
	ENTRY	CRC_t		For debugging...
CRC_t	DS.L	256		CRC table (loaded by initialise_CRC)
*
********************************************************************************
	STTL	''
	PAGE
	END
-- 
|   Roberto Divia`      | Love at  first sight  is one of the greatest |
|   =============       | labor-saving devices the world has ever seen |
|  CERN :  European Laboratory for Particle Physics,  1211  Geneva  23 |
|  Switzerland (CH)                                                    |