Path: utzoo!attcan!uunet!lll-winken!ames!apple!voder!pyramid!leadsv!practic!vlsisj!davidc
From: davidc@vlsisj.VLSI.COM (David Chapman)
Newsgroups: sci.electronics
Subject: Re: SRAM Battery backup
Summary: CRC code in C and 80x86 assembly
Keywords: CRC, C, MASM
Message-ID: <15232@vlsisj.VLSI.COM>
Date: 24 May 89 04:07:49 GMT
References: <669@serene.UUCP>
Reply-To: davidc@vlsisj.UUCP (David Chapman)
Organization: VLSI Technology Inc., San Jose, CA
Lines: 348


I've had a couple of requests for the CRC code that I mentioned.  So at the 
risk of offending the net gods by wasting all of their precious bandwidth, 
here it is (yes, I realize that it should be in comp.sources.whatever, but I
don't read them and I suspect few of you do).

If you're not interested in CRCs, type 'n' now.

There are four files encapsulated herein:  pdcrc.c, crc.h, crc.c, and crc.asm. 
Each is separated by a form feed and prefixed with a line of the form
"#file <file name>".  "pdcrc.c" is (I believe) a public domain set of CRC 
routines.  It came from an MS-DOS disk of C source code; wish I could remember 
where.  It's documented to the extreme.  Possible porting problem:  the author 
assumes that "short" is 16 bits; I've seen 8-bit shorts on some machines.  It
also assumes that adding a character to a long will be unsigned; some machines
perform signed character arithmetic.

Files crc.h and crc.c are the interface and implementation, respectively, of 
my version of the same code.  I changed the implementation from long integer 
registers to regular integers for speed (especially important on 16-bit 
processors that barely slog through 32-bit operations).  It's been a year 
since I worked on it, but I recall having tested it with the main() from 
pdcrc.c.  I recommend that you test it thoroughly yourself, of course.
Possible porting probems:  it assumes that integers are 16 bits (though it
should work regardless).  Itassumes that casting a character to an unsigned
int works (had a bug in a compler once that wouldn't allow that!).

File crc.asm is the _untested_ translation of crc.c to MASM for 80x86 
processors.  As you'll see pretty quickly, it won't even assemble yet (segment 
info is missing, etc.).  I think that the inner loop will work properly if you 
get the procedure shell around it, load the values properly, etc.  Note that 
the reference to "[00]" is a data segment load (I think - I'm not an expert 
80x86 programmer yet).  This was an exercise to see how easy and fast a CRC 
could be in assembly language, given a carry bit.  It's fewer lines, and 
generates an order of magnitude less code!  I bet it's at least one order of 
magnitude faster, too.

Files crc.c and crc.h are hereby released into the public domain for use as 
you see fit.  Since I can't prove that pdcrc.c is in the public domain 
(without more effort than my classes allow me right now), you may wish to use 
those instead.  Crc.asm is similarly released, but by the time you get it
working it won't be recognizable as my code anyway, so you're outof danger.

Remember:  you get what you paid for (don't sue me).

		David Chapman

{known world}!decwrl!vlsisj!fndry!davidc
vlsisj!fndry!davidc@decwrl.dec.com

#file pdcrc.c
/******************************************
*					  *
* Cyclic Redundancy Check (CRC) functions *
*					  *
******************************************/

/*
*   crc_clear:
*	This function clears the CRC to zero. It should be called prior to
*	the start of the processing of a block for both received messages,
*	and messages to be transmitted.
*
*	Calling sequence:
*
*	short crc;
*	crc = crc_clear();
*/
short crc_clear()
{
	return(0);
}
/*
*   crc_update:
*	this function must be called once for each character which is
*	to be included in the CRC for messages to be transmitted.
*	This function is called once for each character which is included
*	in the CRC of a received message, AND once for each of the two CRC
*	characters at the end of the received message. If the resulting
*	CRC is zero, then the message has been correctly received.
*
*   Calling sequence:
*
*	crc = crc_update(crc,next_char);
*/
short crc_update(crc,crc_char)
short crc;
char crc_char;
{
	long x;
	short i;

/* "x" will contain the character to be processed in bits 0-7 and the CRC    */
/* in bits 8-23. Bit 24 will be used to test for overflow, and then cleared  */
/* to prevent the sign bit of "x" from being set to 1. Bits 25-31 are not    */
/* used. ("x" is treated as though it is a 32 bit register).                 */
	x = ((long)crc << 8) + crc_char;    /* Get the CRC and the character */

/* Repeat the following loop 8 times (for the 8 bits of the character).      */
	for(i = 0;i < 8;i++)
	{

/* Shift the high-order bit of the character into the low-order bit of the   */
/* CRC, and shift the high-order bit of the CRC into bit 24.		     */
		x = x << 1;			   /* Shift "x" left one bit */

/* Test to see if the old high-order bit of the CRC was a 1.		     */
		if(x & 0x01000000)		       /* Test bit 24 of "x" */

/* If the old high-order bit of the CRC was a 1, exclusive-or it with a one  */
/* to set it to 0, and exclusive-or the CRC with hex 1021 to produce the     */
/* CCITT-recommended CRC generator of: X**16 + X**12 + X**5 + 1. To produce  */
/* the CRC generator of: X**16 + X**15 + X**2 + 1, change the constant from  */
/* 0x01102100 to 0x01800500. This will exclusive-or the CRC with hex 8005    */
/* and produce the same CRC that IBM uses for their synchronous transmission */
/* protocols.								     */
			x = x ^ 0x01102100;	/* Exclusive-or "x" with a...*/
					      /* ...constant of hex 01102100 */
/* And repeat 8 times.							     */
	}						/* End of "for" loop */

/* Return the CRC as the 16 low-order bits of this function's value.         */
	return(((x & 0x00ffff00) >> 8)); /* AND off the unneeded bits and... */
				  /* ...shift the result 8 bits to the right */

}
/*
*   crc_finish:
*	This function must be called once after all the characters in a block
*	have been processed for a message which is to be TRANSMITTED. It
*	returns the calculated CRC bytes, which should be transmitted as the
*	two characters following the block. The first of these 2 bytes
*	must be taken from the high-order byte of the CRC, and the second
*	must be taken from the low-order byte of the CRC. This routine is NOT
*	called for a message which has been RECEIVED.
*
*   Calling sequence:
*
*	crc = crc_finish(crc);
*/
short crc_finish(crc)
short crc;
{
/* Call crc_update twice, passing it a character of hex 00 each time, to     */
/* flush out the last 16 bits from the CRC calculation, and return the	     */
/* result as the value of this function.				     */
	return(crc_update(crc_update(crc,'\0'),'\0'));

}

/*
* This is a sample of the use of the CRC functions, which calculates the
* CRC for a 1-character message block, and then passes the resulting CRC back
* into the CRC functions to see if the "received" 1-character message and CRC
* are correct.
*/
main()
{

	short crc;				       /* The calculated CRC */
	char crc_char;				  /* The 1-character message */
	char x, y;	      /* 2 places to hold the 2 "received" CRC bytes */

	crc_char = 'A';                    /* Define the 1-character message */
	crc = crc_clear();	/* Reset the CRC to "transmit" a new message */
	crc = crc_update(crc,crc_char);   /* Update the CRC for the first... */
				   /* ...(and only) character of the message */
	crc = crc_finish(crc);	      /* Finish the transmission calculation */
	x = (char)((crc & 0xff00) >> 8);  /* Extract the high-order CRC byte */
	y = (char)(crc & 0x00ff);	   /* And extract the low-order byte */
	printf("%04x\n",crc);                           /* Print the results */

	crc = crc_clear();		   /* Prepare to "receive" a message */
	crc = crc_update(crc,crc_char);   /* Update the CRC for the first... */
				   /* ...(and only) character of the message */
	crc = crc_update(crc,x);     /* Pass both bytes of the "received"... */
	crc = crc_update(crc,y);	   /* ...CRC through crc_update, too */
	printf("%04x\n",crc);    /* If the result was 0, then the message... */
					    /* ...was received without error */

}


#file crc.h

/* crc.h - interface for 16-bit CRC routines */

/* I assume two-byte integers. */

typedef unsigned int CRCSHORT;          /* return value type */

#ifndef UNIX                            /* no function prototyping in UNIX C */

CRCSHORT crcupdate(char,CRCSHORT);      /* update the CRC with the given */
                                        /* 8-bit value. */

CRCSHORT crcval(CRCSHORT);              /* return the final CRC, given */
                                        /* working value so far */

CRCSHORT crcstr(char *);                /* compute CRC value of string */

CRCSHORT crcstrn(char *,int);           /* compute CRC value of "len" chars */

#else UNIX

CRCSHORT crcupdate(),crcval(),crcstr(),crcstrn();

#endif

/* usage:

   char *p;
   CRCSHORT crc;

   crc = 0;
   while (*p)
       crc = crcupdate(*p++,crc);
   crc = crcval(crc);

   append "crc" to the string and transmit the entire thing. at the receiving
   end, pass each character (including the trailing CRC bytes) through the
   crcupdate() function again, and 0x0000 should result. if not, something
   got corrupted.

   this particular code example is how "crcstr" is implemented.

*/

#file crc.c
/* crc.c - 16-bit cyclic redundancy check */

/* uses the CCITT-recommended function X**16 + X**12 + X**5 + 1. */

/* in the polynomial definition below, the uppermost bit is assumed. this */
/* allows the use of shorter numbers than otherwise would be required. */

#define CRC16POLY 0x1021                /* CCITT-16 polynomial in hex */

#include "crc.h"

CRCSHORT crcupdate(ch,crc)              /* update the CRC with the given */
char ch;                                /* 8-bit value. */
CRCSHORT crc;
{
    /* for speed all of this should really be done in assembly language */
    /* judicious use of the carry flag would make the temporary flags */
    /* superfluous). */

    int i;
    register unsigned c,bit,exor;

    c = (unsigned) ch;               

    for (i = 0; i < 8; ++i) {
        bit = (c > 0x7f);               /* 1 or 0 from high bit */
        c = (c << 1) & 0xff;
        exor = (crc & 0x8000);          /* just non-zero is OK here */
        crc = (crc << 1) | bit;
        if (exor)                       /* recirculation... */
            crc ^= CRC16POLY;
    }  /* end of for (i) */

    return(crc);

}  /* end of crcupdate() */

CRCSHORT crcval(crc)                    /* return the current CRC, given */
CRCSHORT crc;                           /* working value so far */
{
    /* we pass 0x0000 through, and the caller appends the resulting CRC */
    /* to its byte stream. at the other end the final CRC of the stream */
    /* (including the CRC passed in) should be 0x0000. */

    crc = crcupdate('\0',crc);
    return(crcupdate('\0',crc));

}  /* end of crcval() */

CRCSHORT crcstr(str)                    /* compute CRC of '\0' terminated */
char *str;                              /* string (not including '\0') */
{
    CRCSHORT crc;

    crc = 0;
    while (*str)
        crc = crcupdate(*str++,crc);
    return(crcval(crc));

}  /* end of crcstr() */

CRCSHORT crcstrn(str,len)               /* compute CRC of "len" chars of str */
char *str;
int len;
{
    int i;
    CRCSHORT crc;

    crc = 0;
    for (i = 0; i < len; ++i)
        crc = crcupdate(*str++,crc);
    return(crcval(crc));

}  /* end of crcstrn() */


#file crc.asm
;
;       CRCUPDATE - run a character through the CRC generator
;
;       hand optimized for the 8086, with C code for you machine-
;       independent types (several times slower! optimizing compilers
;       usually can't tell that the binary flags "bit" and "exor" are
;       really carry flag hacks...).
;
;       #define CRC16POLY 0x1021
;
;       void crcupdate(ch)
;       char ch;
;       {
;           int i;
;           register unsigned c,bit,exor;
;
;           for (i = 8; i; --i) {
;               bit = (c > 0x7f);
;               c = (c << 1) & 0xff;
;               exor = (_crc16 & 0x8000);
;               _crc16 = (_crc16 << 1) | bit;
;               if (exor)
;                   _crc16 ^= CRC16POLY;
;           }  /* end of for (i) */
;
;       }  /* end of crcupdate() */
'
crcupdate:
        mov     ax,[00]                 ;get _crc16
        mov     bl,6[bp]                ;c = (unsigned) ch;
        mov     cx,8                    ;for (i = 8; i; --i)
shiftloop:                              ;{
        shl     bl,1                    ;    bit = (c < 0x7f);
                                        ;    c = (c << 1) & 0xff;
        rcl     ax,1                    ;    exor = (_crc16 & 0x8000);
                                        ;    _crc16 = (_crc16 << 1) | bit;
        jnc     noexor                  ;    if (exor)
        xor     ax,1021H                ;        _crc16 ^= CRC16POLY;
noexor: loop    shiftloop               ;}
        mov     [00],ax                 ;save _crc16
        ;assorted stack manipulation...
        ret