QIC Tape help with CRC - Dwight?

Chuck Guzis cclist at sydex.com
Sun Nov 15 12:35:43 CST 2015


I guess I should throw my own experience on this.

First off, it's useful to think about a CRC as just another checksum. 
Instead of using a simple addition, however, a somewhat more complex 
(table-drive) operation is used (that's your polynomial).

In other words, if S is the CRC sum and I is the current input, a CRC is 
nothing more than S = sum(S,I) for every I.  In the case of an 
arithmetic checksum the function "sum" is a simple addition.  In a CRC 
it's more involved.  You can see that the initial value of S is important.

In CRCs, this initial value can be anything, but usually, it's 0 or all 
binary ones.  Note that CRC calculation doesn't use arithmetic per se, 
but rather boolean ops and shifts.  The character of the operation is 
dictated by the CRC polynomial.

I'll go out on a limb here and say that most often the polynomial used 
in storage devices, where a 16-bit CRC is calculated is the standard 
CCITT CRC-16 one.  There are exceptions, but really, assuming that 
polynomial is an excellent starting point.

Once you've selected a polynomial candidate, the second thing to do is 
to determine exactly what the input to the CRC computation is.  You'd 
think, for example, that on most IBM-type floppy disks, that it's the 
data in a sector--and you'd be wrong.  Most floppy CRC computation 
includes the data address mark (DAM) as well.  So, in a typical 1.44M 
IBM floppy, that data address mark would be hex "FB", followed by sector 
data.

The third thing to consider is what order that bits are presented to the 
CRC calculator--that is, high-order or low-order bit first.  Floppy 
disks mostly go one way and USRTs (synchronous comm) go the other way. 
So you could have the same value treated two different ways and get two 
completely different CRCs, based on the same polynomial.  This is a real 
gotcha when dealing with early disk formats, as many of those used an 
inexpensive USRT or shift register rather than an expensive-for-the-time 
LSI controller.

I find it useful to have a pair of simple test programs that, given a 
CRC polynomial and initial value and an input file, produce a CRC for 
comparison.  One routine calculates little-bit endian and the other does 
the same for big-endian calculations.

CRC_reveng is a great routine, but much of the time, it's overkill.

For whatever it's worth,
Chuck





More information about the cctalk mailing list