[Q]CRC16
Russell A. Schultz
I need a fast, CORRECT, 16 crc routine to work on an 8051 (and potentially
others).
I've searched the net and found a lot of different routines, but they all seem
to come up with different CRC values for the same input.
What things do I need to specify so that two people get the same CRC value?
It seems that there's the polynomial and the seed, but I've seen two different
code sources claim to use the same polynomial and come up with different
answers! HELP!
Charles Ader
try this:
; Last change: MIS 14 Oct 97 2:20 pm
;-----------------------------------------------------------------------
$NOMOD51
$NOLIST
$INCLUDE(DS5001.INC)
$LIST
NAME CRC_test
?DT?CRC_test SEGMENT DATA
rseg ?DT?CRC_test
CRCH: ds 1
CRCL: ds 1
DCRCH: ds 1
DCRCL: ds 1
SCRC_16: ds 2
SCRC_32: ds 4
CRC_CONST16 equ 0A001h
CRC_CONST3 equ 0EDh ;reverse of ethernet poly 04c11db7h
CRC_CONST2 equ 0B8h ;reverse of ethernet poly 04c11db7h
CRC_CONST1 equ 083h ;reverse of ethernet poly 04c11db7h
CRC_CONST0 equ 020h ;reverse of ethernet poly 04c11db7h
?CO?CRC_test SEGMENT CODE
RSEG ?CO?CRC_test
public CRC_test
; extrn code(init_crc32, crc32)
; extrn data(crc_msg);
CRC_test:
mov CRCLOW,CRCLOW
nop
mov CRCLOW,CRCLOW ;Clear Dallas CRC16 register
mov CRCH,#0
mov CRCL,#0
mov SCRC_16,#0
mov SCRC_16+1,#0
mov SCRC_32,#0
mov SCRC_32+1,#0
mov SCRC_32+2,#0
mov SCRC_32+3,#0
; call init_crc32
mov A,#080H
call CRC16
call DCRC16
call SCRC16
call SCRC32
; mov crc_msg,#80h
; call crc32
mov A,#075H
call CRC16
call DCRC16
call SCRC16
call SCRC32
mov A,#08AH
call CRC16
call DCRC16
call SCRC16
call SCRC32
mov A,#00BH
call CRC16
call DCRC16
call SCRC16
call SCRC32
mov A,#075H
call CRC16
call DCRC16
call SCRC16
call SCRC32
mov A,#0C7H
call CRC16
call DCRC16
call SCRC16
call SCRC32
mov A,#0AAH
call CRC16
call DCRC16
call SCRC16
call SCRC32
mov A,#075H
call CRC16
call DCRC16
call SCRC16
call SCRC32
mov A,#0C7H
call CRC16
call DCRC16
call SCRC16
call SCRC32
mov A,#055H
call CRC16
call DCRC16
call SCRC16
call SCRC32
mov A,#043H
call CRC16
call DCRC16
call SCRC16
call SCRC32
ljmp CRC_test
;
; Use Dallas CRC hardware
;
DCRC16:
mov CRCLOW,A
nop
mov DCRCH,CRCHIGH
mov DCRCL,CRCLOW
ret
;CALCULATE CRC16 IN PARALLEL TO THE GREATEST EXTENT PRACTICAL
; INPUT: BYTE TO BE INCUDED IN CRC CALCULATION IS IN ACC
; OUTPUT: CRCH:CRCL UPDATED TO INCLUDE THE NEW BYTE
;
CRC16:
PUSH ACC ;save this in case the caller needs it
XRL A,CRCL
MOV CRCL,CRCH ;put the high byte of the crc in dest
MOV CRCH,A ;save data xor low(crc) for later
MOV C,P
JNC CRC0
XRL CRCL,#001H
CRC0:
RRC A ;get the low bit in c
JNC CRC1
XRL CRCL,#040H
CRC1:
MOV C,ACC.7
XRL A,CRCH ;compute the results for bits P...U
RRC A ;shift them into place
MOV CRCH,A ;and save them
JNC CRC2
XRL CRCL,#080H
CRC2:
POP ACC ;and restore everything and return
RET
;
; Serial CRC 16
;
SCRC16:
PUSH ACC
MOV R3,A
MOV R2,#8
LOOP:
MOV R0,#SCRC_16 ;16 bit shift
CLR C
MOV A,@R0
RRC A
MOV @R0,A
INC R0
MOV A,@R0
RRC A
MOV @R0,A
MOV A,R3 ;MSB input bit
RR A ;8 bit rotate
MOV R3,A
JNB ACC.7,IN_BIT0
CPL C
IN_BIT0:
JNC NO_XOR
MOV A,@R0 ;16 bit xor with polynomial const
XRL A,#LOW CRC_CONST16
MOV @R0,A
DEC R0
MOV A,@R0
XRL A,#HIGH CRC_CONST16
MOV @R0,A
NO_XOR:
DJNZ R2,LOOP
MOV A,R3
POP ACC
RET
;
; Serial CRC 32
;
SCRC32:
PUSH ACC
MOV R3,A
MOV R2,#8
LOOP32:
MOV R0,#SCRC_32 ;32 bit shift
CLR C
MOV A,@R0
RRC A
MOV @R0,A
INC R0
MOV A,@R0
RRC A
MOV @R0,A
INC R0
MOV A,@R0
RRC A
MOV @R0,A
INC R0
MOV A,@R0
RRC A
MOV @R0,A
MOV A,R3 ;MSB input bit
RR A ;8 bit rotate
MOV R3,A
JNB ACC.7,IN_BIT032
CPL C
IN_BIT032:
JNC NO_XOR32
MOV A,@R0 ;16 bit xor with polynomial const
XRL A,#CRC_CONST0
MOV @R0,A
DEC R0
MOV A,@R0
XRL A,#CRC_CONST1
MOV @R0,A
DEC R0
MOV A,@R0
XRL A,#CRC_CONST2
MOV @R0,A
DEC R0
MOV A,@R0
XRL A,#CRC_CONST3
MOV @R0,A
NO_XOR32:
DJNZ R2,LOOP32
MOV A,R3
POP ACC
RET
end
Eric G Roesinger
rsch...@flash.net (Russell A. Schultz) wrote in <6ccsvt$a2h$1...@excalibur.flash.net>:
> I need a fast, CORRECT, 16 crc routine to work on an 8051 (and potentially
> others).
>
> I've searched the net and found a lot of different routines, but they all seem
>
> to come up with different CRC values for the same input.
>
> What things do I need to specify so that two people get the same CRC value?
> It seems that there's the polynomial and the seed, but I've seen two different
>
> code sources claim to use the same polynomial and come up with different
> answers! HELP!
You need to specify polynomial, seed, bit order of each codeword, bit
order of CRC presentation, and complemented or non-complemented CRC
presentation. Variation in any of these, or failure to pass trailing
zeroes if the non-lookahed form of the algorithm is used, will all cause
"different" (but perfectly usable, with an adequate polynomial) answers.
One fairly decent article on CRC algorithms, which I encountered
recently, is available on the internet:
ftp://ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
(or so it says in its header). It's pretty solid, but does focus on fast
table-driven implementations. Thus, it covers the rotation from simple
to direct, or "lookahead" form at codeword, rather than bit resolution,
as I might have preferred (which is really a matter of taste and habit).
Since the ROM space available on typical 8051's is a bit scarce, you may
want to avoid eating up 256 bytes for a table, plus code. If so, or even
if you're just curious, read on.
For the CCITT polynomial (X^16+X^12+X^5+X^0), there is also a compact,
intermediate form, for 8-bit codewords, which is approximately an order
of magnitude faster than the bitwise form, and an order of magnitude
slower than the table lookup. Its derivation consists of tracking the
bits from a previous CRC remainder, and new input data, through the
course of eight successive bit inputs.
First, note that the running remainder of the polynomial division may be
modeled by the following linear feedback shift register (LFSR), where
"X" represents polynomial sum or difference in binary notation (both
operations reduce to XOR). Note we have implemented the direct, or
"lookahead" form, obviating the need to process a trailing zero pad.
.--.--.--.--
.-: : : : incoming data stream
: '--'--'--'--
X->--------------.-------------------------.-------------------.
: .--.--.--.--. : .--.--.--.--.--.--.--. : .--.--.--.--.--. :
`-: : : : :<-X-: : : : : : : :<-X-: : : : : :<-'
'--'--'--'--' '--'--'--'--'--'--'--' '--'--'--'--'--'
If the contents of the remainder and an incoming codeword are then
modeled as arbitrary coefficients {a,...,p} and {q,...,x}:
.------------------. .------------------. .------------------.
: Initial state: : : 1st Shift: : : 2nd Shift: :
: : : : : :
: QRSTUVWX : : RSTUVWX : : STUVWX :
: ----=======----- : : ----=======----- : : ----=======----- :
: ABCDEFGHIJKLMNOP : : BCDEFGHIJKLMNOP : : CDEFGHIJKLMNOP :
: : : : : :
: : : : : :
: : : A : : AB :
: : : Q : : QR :
: : : A : : AB :
: : : Q : : QR :
: : : A : : AB :
: : : Q : : QR :
: : : : : :
'------------------' '------------------' '------------------'
.------------------. .------------------. .------------------.
: 3rd Shift: : : 4th Shift: : : 5th Shift: :
: : : : : :
: TUVWX : : UVWX : : VWX :
: ----=======----- : : ----=======----- : : ----=======----- :
: DEFGHIJKLMNOP : : EFGHIJKLMNOP : : FGHIJKLMNOP :
: : : : : A :
: : : : : Q :
: ABC : : ABCD : : BCDE A :
: QRS : : QRST : : RSTU Q :
: ABC : : ABCD : : ABCDE A :
: QRS : : QRST : : QRSTU Q :
: ABC : : ABCD : : ABCDE :
: QRS : : QRST : : QRSTU :
'------------------' '------------------' '------------------'
.------------------. .------------------. .------------------.
: 6th Shift: : : 7th Shift: : : 8th Shift: :
: : : : : :
: WX : : X : : :
: ----=======----- : : ----=======----- : : ----=======----- :
: GHIJKLMNOP : : HIJKLMNOP : : IJKLMNOP :
: AB : : ABC : : ABCD :
: QR : : QRS : : QRST :
: CDEF AB : : DEFG ABC : : EFGH ABCD :
: STUV QR : : TUVW QRS : : UVWX QRST :
: ABCDEF AB : : ABCDEFG ABC : : ABCDEFGH ABCD :
: QRSTUV QR : : QRSTUVW QRS : : QRSTUVWX QRST :
: ABCDEF : : ABCDEFG : : ABCDEFGH :
: QRSTUV : : QRSTUVW : : QRSTUVWX :
'------------------' '------------------' '------------------'
Expressed in a pseudocode, then, the remainder after eight shifts may be
computed:
group[ 7: 0] := remainder[15: 8] xor input[7:0]
group[ 3: 0] := group[ 3: 0] xor group[7:4]
remainder[15: 8] := remainder[ 7: 0]
remainder[ 7: 0] := group[ 7: 0]
remainder[12: 5] := remainder[12: 5] xor group[7:0]
remainder[15:12] := remainder[15:12] xor group[7:0]
in which every bit group processed is either four our eight bits wide,
and with only one exception, is aligned on a four or eight bit boundary.
This makes the solution for this particular polynomial especially well
fit to use in four bit microcontrollers, and in the 8051, with its half-
byte SWAP instruction. FWIW, I do believe that the CCITT was aware of
this consideration when the polynomial was chosen.
If we wish to pass the acutual CRC at the end of the data, we can simply
include it in the computation and check for zero; on the other hand, if
we with to pass the complemented CRC (as is done in some systems), we
will need to compute the check value (here abbreviated):
.------------------. .------------------.
: 8th Shift: : : 16th Shift: :
: IJKLMNOP : : 11110000 :
: 1111 : : 1110 :
: 1111 1111 : : 0001 1110 :
: 11111111 1111 : : 11100001 1110 :
: 11111111 : : 11100001 :
: : : :
: Equivalent to: : : Equivalent to: :
: : : :
: 0001111011110000 : : 0001110100001111 :
: IJKLMNOP : : 1 D 0 F :
'------------------' '------------------'
Hopefully, this will be of some help.
Best Regards,
--
Eric Roesinger / SW Engineer *speaking for myself, not for my employer*
Comm. RF Product Development
Thomson Consumer Electronics Practice, in theory, is no dif- _:_Mt.27
roesi...@indy.tce.com ferent than theory in practice. : 45-54
Kerry Graham
Russel,
At the bottom of this message you will find the table and routine that we
use for CRC calculation. The U16_t type is a 16 bit unsigned int.
Kerry Graham
Software Designer
Fitel-PMX
Russell A. Schultz wrote in message <6ccsvt$a2h$1...@excalibur.flash.net>...
>I need a fast, CORRECT, 16 crc routine to work on an 8051 (and potentially
>others).
>
>I've searched the net and found a lot of different routines, but they all
seem
>to come up with different CRC values for the same input.
>
>What things do I need to specify so that two people get the same CRC value?
>It seems that there's the polynomial and the seed, but I've seen two
different
>code sources claim to use the same polynomial and come up with different
>answers! HELP!
=====================================
/*************************************************************************/
/* Copyright 1995 FITEL-Photomatrix */
/*************************************************************************/
/*************************************************************************/
/*
TITLE :
FILENAME : gccrc16.c
ABSTRACT :
-
HISTORY :
DATE NAME DESCRIPTION
9?/??/?? ?????? Created
96/11/26 kgraham Changed name from crc16.c to gccrc16.c
*/
/*************************************************************************/
#include "fpmx.h"
#include "gccrc16.h"
/*
* gccrc16.c
*
* This file contains the routines needed to perform 16 bit CRC
* calculations on a block.
*
* Contains: CalculateBlockCRC16()
*
*/
/*
* This is the table used to by the table lookup method of
* generating CRC values.
*/
static unsigned short int ccitt_16[ 256 ] =
{
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,
0x2462, 0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485,
0xA56A, 0xB54B, 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695, 0x46B4,
0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC,
0x48C4, 0x58E5, 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969, 0xA90A, 0xB92B,
0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12,
0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03, 0x0C60, 0x1C41,
0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD, 0xAD2A, 0xBD0B, 0x8D68, 0x9D49,
0x7E97, 0x6EB6, 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A, 0x9F59, 0x8F78,
0x9188, 0x81A9, 0xB1CA, 0xA1EB, 0xD10C, 0xC12D, 0xF14E, 0xE16F,
0x1080, 0x00A1, 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E,
0x02B1, 0x1290, 0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256,
0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C,
0x26D3, 0x36F2, 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9, 0xB98A, 0xA9AB,
0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3,
0xCB7D, 0xDB5C, 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0, 0x2AB3, 0x3A92,
0xFD2E, 0xED0F, 0xDD6C, 0xCD4D, 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9,
0x7C26, 0x6C07, 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8,
0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
};
/*
* unsigned int CalculateBlockCRC16( unsigned int count,
* unsigned int crc,
* void *buffer )
*
*
* ARGUMENTS
*
* unsigned int count : The number of bytes in the buffer
*
* unsigned int crc : The initial value of the crc
*
* void *buffer : The buffer whose CRC is to be calculated.
*
* DESCRIPTION
*
* This routine is called to calculate the CRC-16 value of a block of
* data. The CRC-16 is the block error checking mechanism used by
* XMODEM, YMODEM, and sometimes ZMODEM. *
*
* RETURNS
*
* A crc value.
*
*/
U16_t CalculateBlockCRC16( unsigned int count,
U16_t crc,
void *buffer )
{
unsigned char *p = buffer;
while ( count-- != 0 )
crc = (U16_t) ( ( crc << 8 ) ^ ccitt_16[ ( crc >> 8 ) ^ *p++ ] );
return( crc );
}
/* -=[EOF]=- */
Thad Smith
In article <6ccsvt$a2h$1...@excalibur.flash.net>,
rsch...@flash.net (Russell A. Schultz) wrote:
>I need a fast, CORRECT, 16 crc routine to work on an 8051 (and potentially
>others).
>
>I've searched the net and found a lot of different routines, but they all seem
>to come up with different CRC values for the same input.
>
>What things do I need to specify so that two people get the same CRC value?
>It seems that there's the polynomial and the seed, but I've seen two different
>code sources claim to use the same polynomial and come up with different
>answers! HELP!
I have read a tutorial from somewhere on the net that explains the
many variations of CRCs. The result: it is difficult to properly
determine the actual function from the formal parameters.
My solution: a C code snippet that does the calculation, either as
standalone function code, or, if it uses a table, with either the
table or the generating function that computes the table (my
preference). This can be accompanied by a test case, such as a few
data bytes and the CRC which is normally added to the data stream as a
result.
The C code can be massaged into the desired form.
Thad
J Hecker
Russell A. Schultz wrote:
>
> I need a fast, CORRECT, 16 crc routine to work on an 8051 (and potentially
> others).
>
> I've searched the net and found a lot of different routines, but they all seem
> to come up with different CRC values for the same input.
>
> What things do I need to specify so that two people get the same CRC value?
> It seems that there's the polynomial and the seed, but I've seen two different
> code sources claim to use the same polynomial and come up with different
> answers! HELP!
Hi,
Here is a short and probably quick 16-CRC routine I used in an Xmodem
implementation. It's actually out of the Xmodem spec. by Chuck Forsburg
who in turn nicked it from someone else.
This one is designed to work on a block of data pointed to by ptr of
size count. It looks so damned simple I am sure you could whip up a
nice efficient version in 8051 assembly and adapt it to continuous
streams of data.
Cheers,
jASON
------------------------
unsigned short int calcrc(unsigned char *ptr, int count)
{
short int crc=0, i;
while(--count >= 0)
{
crc = crc ^ (int)*ptr++ << 8;
for(i=0;i<8;++i)
{
if(crc & 0x8000)
crc = crc << 1 ^ 0x1021;
else
crc = crc << 1;
}
}
return (crc & 0xFFFF);
}