Steve M. Taylor wrote:
"Out of interest, isn't a table based method a hell of a lot faster ?"

No one exploits tables more than me, but it depends on the application whether its worth consuming the table space. I'd NEVER let a c compiler code my crc16 routine; you can do it much quicker in assembly language by planning out the process with the right micromachine construct.

As I've mentioned previously, I've done a packet radio protocol that did message reconstruction by running block permutations, crc16 validated, from the collected sets of garbled transmissions (circa 1985). I wrote an optimal crc16 algorithm (Z80/8085 code) since so much time was spent in that module during reconstruction; I didn't use the table method.

The interesting thing I discovered is that I could hold the partial results of the entire message on the stack as I tried a permutation block. Anytime a permutation branch was declared exhausted or abandoned early, I could back up one block level and grab the pre-computed partial results from the stack and proceed down the next permutation path without recomputing the crc16 to that point.

This observation meant I didn't have to compute crc16 for the entire message permutation, over and over again as each possibility was considered. If you know your data structures runtime comparisons, you can appreciate the significance of that observation.

That was included in a patent application by my employer (1985) but I've never found the patent in searchs since I left that company. They were notorious for removing the names of patent inventors if they left the company during the application process - which is entirely illegal and would invalidate the patent. But when has that stopped any business? :)

Hmmm, I bet if I searched on my old crooked manager's name, I'd find that patent...

duh