Table CRC vs Bit-Shifting CRC question

RKnapp · Joined: 23 Feb 2004 Posts: 51

Friends,

A while back a table-based CRCITT-16 algorithm was posted here which was clean and undoubtedly quite fast:

Neutone · Joined: 08 Sep 2003 Posts: 839 Location: Houston

In general both methods work. I did some testing with some very large packets and determined the time to encode/decode at around 150 instructions per byte using the bit shift method. That was after doing all the optimizing I could. I haven't done that testing for the loolkup table routines but they looked like they would run faster. The bitshift method has much smaller program space footprint though. The routines I use are different by the polynomial factor used. The methods are the same. Have a look at the routines I posted if you like. I don't think they will help because the lookup table has to be solved for the polynomial factor.

RKnapp · Joined: 23 Feb 2004 Posts: 51

Neutone,

Yiih -- 150 instructions per byte for bit shifting. Thanks for checking this out.

But both methods should compute the same answer, right? Something is funky about the table-CRC method I've posted. It appears to be quite simple so I'm wondering if:

a) There's an error in one / both of the tables -- does anyone know how to regenerate them?

b) something else quite obvious about the length of the message... something.

My application requires lots of these CRCs but I'm already up to 40% duty cycle with bit-shifting, so table-CRC seems attractive if I could make it work.

?

Thanks,

Smile

Robert

ps. CCS Compiler v3.187, PIC18F8720.

guest · Guest

Well, yes, given the same input sequence, and assuming both are using the same polynomial, then of course you must expect the same result.

In the past, I've had problems with typos in the tables, and they can be devastating because everything seems to work except once in a while unexpected CRC errors are detected.

How I've dealt with that in the past is to use the bit-cycle method to build the table. This can be done "at compile time" by generating the ascii hex for the tables and then including it in a source file, or it can be done at run time during initialisation. This last idea is very good when program space is limited but RAM is plenty. In fact, by using conditional defines, any of the three methods can be selected at compile time.

In terms of speed, table lookups are by far the fastest.

cheers

Neutone · Joined: 08 Sep 2003 Posts: 839 Location: Houston

For what it's worth this works for me. My tables are defined much like yours.

PCM programmer · Joined: 06 Sep 2003 Posts: 21708

RKnapp · Joined: 23 Feb 2004 Posts: 51

Neutone & PCM,

THANKS! Sure enough, the table-based algorithm works if one simply swaps the names on the tables -- lo to hi & vice versa. The table as posted is not damaged.

Working through Neutone's algorithm, I was beginning to wonder if the way the table-based CRC (as posted above) was processing the message in "reverse order."

I'm posting my "restatement" of Neutone's algorithm. I use these for both Rx & Tx so I can't load the buffer right there, as he does, but it's otherwise his code. I'm posting it so that others can choose between tables & bit shifting.

But here's what's weird: I can't find any time difference in using a table vs. bit shifting on my PIC18F8720 (20 Mhz). I can't imagine how this is true; has anyone else timed the two methods?

Thanks again,

Smile

Robert

Neutone · Joined: 08 Sep 2003 Posts: 839 Location: Houston

To solve for timing I turned on a pin before performing the CRC and off right after. I took the pulse time and divided by the known packet size in bytes. I never did this for the lookup table method but looking at the assembly it looked like around 20 to 40 instruction per byte. If you are seeing no change in timing then you might be measuring the wrong thing.

RKnapp · Joined: 23 Feb 2004 Posts: 51

I have to admit that your method of measuring time is much better; I'm not directly measuring calculation times as you did. I was measuring "duty cycle" of the processor, which includes many other things as well as this calculation.

Because I'm implementing a real-time loop, I strive for 30% max usage in the loop, with 70% "idling time." My last system was marginal, with 50% duty cycle -- some frame overruns were noted.

Thank you very much,

Smile

Robert

Neutone · Joined: 08 Sep 2003 Posts: 839 Location: Houston

I did some further measurements to CRC calculation time. Basic bit shifting was running around 150 instruction(per byte). Using a ROM base lookup table it takes around 75 instructions. With a RAM based lookup table it takes around 35 instructions. This is all done testing the on time of a pin during a 100 byte packet being encoded.