Someone I know has a fast way to compute CRCs without tables that use only a single loop. The method seems broken to some people... [snip]
I don't doubt that this is possible but is it really faster than using tables on any actual existing processor? Even CRC-32 only needs a 1K table, it fits into cache, it's really fast unless you're doing CRC of very short strings. And is he perchance using his own non-standard polynomial to make this trick work? Has he proven that it's as strong as the standard polynomials?
I first came across what I think was the grandparent's "hack" when writing code back in the 1980s for an 8085-based EPOS-terminal. With a total address space of 64KB (albeit we did have paged ROM and RAM to extend that), any but the smallest look-up tables were a ridiculous luxury.
First time I saw the hack, I thought "you WHAT now?!" and so one bored Friday afternoon I followed it all through and bloody hell, yes, it worked. Kinda melted my head as to how on earth the (since-departed) author had come up with it, but it worked.
We used it to calculate CRC-16-CCITT and CRC-16-IBM in both normal and reversed versions (four in total), so it seemed to be flexible enough to use any polynomial you wanted.
I'd be very interested to see the code
Sadly, although I probably still have the code (only slightly naughtily, since I was also the guy responsible for doing the backups, including offsite backups), it'll be on a 5.25" floppy somewhere, and a quick Google doesn't turn up anything I recognise... so you'll have to wait for another day.