Date   : Mon, 13 Jun 2011 19:27:52 +0200
From   : rick@... (Rick Murray)
Subject: Calculating CRCs

On 13/06/2011 16:32, J.G.Harston wrote:

> Argh!!! That's *exactly* the useless sort of stuff I kept finding.
>> which explains by bit, by byte, and differences in various types of CRC.
> Lots of detailed theoretical analysis of what CRCs are and the
> mathematics of how they work, but no actual real cut'n'paste usable
> code. It even starts by saying "Before writing even one line of code,
> let's first examine the mechanics of modulo-2 binary division...."
> No!!! I don't care about the theory!!! I just need the code!!!!

You *what*?!?

Did you read that page?
   "Listing 1. A naive CRC implementation in C".
   "Listing 2. A more portable but still naive CRC implementation".
   "Listing 3. Computing the CRC lookup table".
   "Listing 4. A more efficient, table-driven, CRC implementation".

I've not tried compiling them after cut'n'paste, but what I can say it 
is looks to be more complete than your example on the CRC page you've 
made (i.e. where is 'crc' defined? "int8"? does that macro to unsigned 
char or unsigned short?).

Either way, there ought to be enough to get started...


Perhaps a description of what they're doing is a good thing. Take a look 
at the complications of:
   http://tomoyo.sourceforge.jp/cgi-bin/lxr/source/lib/crc32.c
and you'll see there are several ways to calculate a CRC.

Certainly, the CRC calculation in the Neuros UPK file creator (thingy 
that builds files for updating my PVR's firmware) uses the version with 
loads of bit shifting. I mean stuff like this:
--8<--------
  #  define DO_CRC4 crc = tab[3][(crc) & 255] ^ \
                  tab[2][(crc >> 8) & 255] ^ \
                  tab[1][(crc >> 16) & 255] ^ \
                  tab[0][(crc >> 24) & 255]
--8<--------

In the code I wrote to unpick those UPK files, I used the code I posted 
previously (due to not wanting to use GPL code) and, frankly, it is a 
HELL of a lot simpler and clearer.

In addition, I made, from the same source, versions that compile and run 
successfully on x86 Windows, x86 Ubuntu, ARM RISC OS, and the ARM based 
PVR itself.

Perhaps somebody with a better grasp of the maths could explain the GPL 
version, but it seems to me to be complicated for the sake of being 
complicated...


>> Because you were not specific enough in your search.
>>     "xmodem crc calculation code"
> Ah, yes, *now*. Try 15 years ago.

You neglected to mention 15 years ago. To be honest, the first place I'd 
have tried looking is a Unix kernel source. Try either:
   /lib/crc32.c
or:
   /libkern/crc32.c

;-)


> Yes, that's the document I finally managed to track down:
> http://mdfs.net/Docs/Comp/Comms/FTP/

Otherwise called "092792" in the version I pulled from Arcade a billion 
years ago. And, oh look, the edit history has your initials on it!


It is useful to consider some of the points made in the first document 
(the one with the lengthy description) as it discusses trade-offs 
between using a table and on-the-fly calculations.

To quote a pertinent section:
--8<--------
As you can see from the code in Listing 4, a number of fundamental 
operations (left and right shifts, XORs, lookups, and so on) still must 
be performed for each byte even with this lookup table approach. So to 
see exactly what has been saved (if anything) I compiled both crcSlow() 
and crcFast() with IAR's C compiler for the PIC family of eight-bit RISC 
processors. 1 I figured that compiling for such a low-end processor 
would give us a good worst-case comparison for the numbers of 
instructions to do these different types of CRC computations. The 
results of this experiment were as follows:

     * crcSlow(): 185 instructions per byte of message data
     * crcFast(): 36 instructions per byte of message data

So, at least on one processor family, switching to the lookup table 
approach results in a more than five-fold performance improvement. 
That's a pretty substantial gain considering that both implementations 
were written in C. A bit more could probably be done to improve the 
execution speed of this algorithm if an engineer with a good 
understanding of the target processor were assigned to hand-code or tune 
the assembly code. My somewhat-educated guess is that another two-fold 
performance improvement might be possible. Actually achieving that is, 
as they say in textbooks, left as an exercise for the curious reader.
--8<--------

This is why I say it would be best to calculate on-the-fly on a BBC 
micro (can you afford the space to store the lookup table?), while on 
more capable machines (B+, Master, SWRAM expanded) would benefit from 
the use of a lookup table to speed things up.


Best wishes,

Rick.

-- 
Rick Murray, eeePC901 & ADSL WiFI'd into it, all ETLAs!
BBC B: DNFS, 2 x 5.25" floppies, EPROM prog, Acorn TTX
E01S FileStore, A3000/A5000/RiscPC/various PCs/blahblah...