Traditional CRC routines look a lot like LFSR-based PRNGs. Basically, you start with a variable, SEED, and you shift it left once, and if you shift out a 1, you XOR SEED with a constant. If you shift out a 0, you do nothing else. You typically want to shift these 8 times each time you want a random number, to ensure that you get 8 random bits in your byte.
CRC generators work the exact same way, except SEED is called CRC, your xor-constant is called the "polynomial", and it typically performs 8 shifts at a time. CRC generators XOR with a byte of data before it does any shifting, so to use a CRC routine as a pseudoranom number generator, you either pass a constant to it, or you remove that data-byte-XOR all together (equivalent to passing a constant of $00 to it). With an 8-bit generator, you're going to want to keep the data-XOR in and just pass it a constant, because if the generator ever outputs zero, it'll get stuck outputting zeros indefinitely.
Now more to the point of my research, Greg Cook somehow managed to simplify the entire routine to run in (near)-constant time, without needing to individually shift each bit. I figured out his shortcut for CRC-8 (which I'll put at the end of my post), but I'm having trouble figuring out how he did the CRC-16 routine. Ultimately, I would like a CRC-32 routine that is superefficient like his CRC-16 routine, so that's why I want to figure this out. The best advantage to these routines is that they're the equivalent of doing 8 shifts, so you get 8 random bits with each call, but it takes significantly less time than actually doing 8 shifts.
Code: Select all
== Shortcut method for CRC-8 ==
Your polynomial must be an odd number. (all CRC-8 polynomials I've seen are odd anyway).
Your polynomial cannot be $01. (This would result in your new byte being the exact same as your starting byte)
Start with the MOST SIGNIFICANT 1 BIT of the polynomial, and with each shift, move to the next bit right.
Shift.
If there's an overflow, xor with the polynomial.
If the current bit of the polynomial is 1, xor with your starting value.
Repeat until you're out of bits in the polynomial.
So, if your polynomial is $07 (which is actually in one of the CRC-8 specs), you only need to perform two shifts.
===============================