bit CRC
13 messages in this thread
I have come to a point in a program I'm writing that I need to calculate
the 16-bit CRC of the text I've read in. Only one minor detail comes
between me and several dozen lines of deathless code; I don't know how to
do a 16-bit CRC calculation.
I think I used to know how to do one, but I sure don't remember now. Can
anyone out there remind me how it's done?
Thanks muchly,
Mike McCormick
Mike,
Here's the explanation from an old Dr. Dobbs on how to generate a
CRC for XMODEM transfers. It's using the CCITT X*16 + X*12 + X*5 +1 as
it's polynomial.
The procedure for generating the CRC is this: A byte to be added
to the CRC is fed into the generator, one bit at a time, high bit first.
The bit is shifted into a 16-bit CRC accumulator low end. If the high bit
shifted out of the CRC accumulator is a 1, the CRC accumulator is exclusive
ORed with 0x1021 (the polynomial). The process repeats for all eight bits
of the input character. At the end, 2 zero bytes are sent thru the
accumulator to flush the last 2 actual characters thru the process.
The code is:
unsigned crcaccum;
VOID updt_crc(x)
char x;
{
unsigned shifter, i, flag;
for (shifter = 0x80; shifter ;shifter >> 1 ) {
flag = (crcaccum & 0x8000); /* is the high bit set
?*/
crcaccum << 1; /* shift right */
crcaccum |= ((shifter & x) ? 1 : 0); /* add in bit
from x */
if (flag) { /* was the high bit set ? */
crcaccum ^= 0x1021; /* xor with the
polynomial */
}
}
}
Don
Mike,
Argh! comment and code don't match.
Where it says:
crcaccum << 1; /* shift right */
it should say:
crcaccum << 1; /* shift LEFT */
Don
This method seems a little to simple to me for some reason. I found a
chapter on error checking using CRC-12, CRC-16, CRC-CTICC, and CRC-32 with
an example of the hardware setup needed to implement the CRC-16. I wrote
some code this morning that simulated the hardware method and it ends up
being a bit more involved.
Here is my code:
UWORD calc_fcs( char ) UBYTE char;
{
static fcs = 0x0000;
UWORD bit; UBYTE shift;
/* Process each bit in the character */
for( shift=0x0001; shift; shift = shift<<1 )
{
/* Determine the 'feedback' value */
bit = ( shift & char ) ? 1 : 0;
bit = ( 0x0001 & fcs ) ^ bit;
/* Right shift the FCS (Frame Check Sequence, the CRC end value ) */
fcs = fcs>>1;
/* XOR with the 16th, 14th, and 1st bit of the FCS */
fcs = ( fcs & ~(0xA001) ) | (( fcs & 0xA001 ) ^ ( bit * 0xA001 ));
} /* for */
return( fcs );
} /* calc_fcs */
You see, my function RIGHT shifts the FCS (accumulator) and reads the
character from low bit to high. I wonder if these two differences cancel
each other out somehow. I'm going to have to study the Dobbs example to see
how they can get away with such a simple last step.
I hope someone can tell me if I'm doing mine correct. A sample string
with the resultant CRC value would be real helpful.
Thanks,
Mike McCormick
Mike,
I implemented the Dobbs code in 6502 assembler for the Atari 8 bit
machines and it worked flawlessly. Somewhere around here, I have (or once
had..who knows where it is now) another text that describes how to generate
a CRC checksum, and it agreed with the Dobbs example code.
Don
I entered the Dobbs formula and I did get the same answer, sortof. All
the bits are inverted between the answers, so that when I get $9001, the
Dobbs formula gets $8009.
I download three different CRC-16 calculators from the IBM forums
yesterday. All three were specifically designed to calculate the CRC of a
specified file. All three gave me three completely different answers when
applied to *any* file I gave them. Slightly annoying that. I've yet to
implement the source code into a test program. I hope to find that the
different programs ignored or used non-text characters or some other
believable reason they shouldn't match.
Does anyone know of some data laying around the forum, IFF or GIF images
and stuff, that has its own CRC inside? I could use that to check my
program.
Thanks,
Mike McCormick
Mike,
I can only say I implemented the Dobbs formula in my Atari 8 bit
program for xmodem transfers. Worked just fine with CIS's CRC xmodem
transfers so one can only presume it gave the right answer.
Make sure you flush out the accumulator with 2 null bytes before
you use the result.
Don
If all you want do is check to see if you are getting the correct CRC, test
your program on a file that has been compressed (LHA or LZH) and then use
LZ with the v command to view the file. LZ will also show the CRC value
for the file and you can compare this with your result.
Bill
– via Whap!
Mike,
One of the big difficulties with CRC is that you sorta have to
understand which 'order' the bits are gonna be 'sent' in. CRC was designed
for SERIAL error checking, and back in the dark ages (when dinosaurs roamed
the earth) bits were sent to the serial port (still are) least significant
bit 1st…so the CRC calcs tended to RIGHT shifts. Then along came IBM
(you gotta remember they're in business to sell HARDWARE, not make it easy
to program) and changed the order for writing to floppies…so CRC's tend
to get flipped end-for-end.
Michael,
There are some substantially faster techiques for doing the CRC stuff.
The fastest that I'm aware of requires only one indexed load (from a table
of 256 precomputed CRC values) one 8 bit shift, and one XOR.
Where's this published? (The fast CRC).
The quickest place to find the algorithm is to read message 19373 here in
AmigaTech (it replies to the same message you did). Mayhaps you can get
Steve to upload the table here.
In the B+ code I'm using CRCs are calculated with the table — ie …
UWORD Upd_CRC(UWORD value) {
crc_16 = crc_table[((crc_16 >> 8) ^ (value)) & 0xff] ^ (UWORD)(crc_16 <<
8);
return(crc_16);
} // Upd_CRC
-sja