CRC routines as PRNGs

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

CRC routines as PRNGs

Post by Drag »

Tepples mentioned it, which made me curious.

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.
===============================
slobu
Posts: 276
Joined: Tue Jul 12, 2011 10:58 am

Re: CRC routines as PRNGs

Post by slobu »

Any data on how varied the distribution is on these modified CRC routines?
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: CRC routines as PRNGs

Post by Drag »

No data whatsoever! :D

I have reason to believe they should be acceptable though, just given the way CRC polynomials need to be created.
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: CRC routines as PRNGs

Post by rainwarrior »

It's pretty easy to test a PRNG. Just run it through its cycle and record the results.
User avatar
koitsu
Posts: 4201
Joined: Sun Sep 19, 2004 9:28 pm
Location: A world gone mad

Re: CRC routines as PRNGs

Post by koitsu »

Not having a good day (health-wise), but I wanted to chime in and say this is quite clever. I never would have thought of it (but that's not saying much, honestly).
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: CRC routines as PRNGs

Post by Drag »

Edit June 17, 2022: Read an updated generalization here!

So I looked into the CRC-16 shortcut that Greg Cook did, and essentially, the code does this:

Code: Select all

The polynomial is x^12 + x^5 + x^0, a.k.a. $1021 (00010000 00100001)
           [CRC_HI] [CRC_LO]
           abcdefgh ijklmnop
                   │
         ┌         ▼
         │ ijklmnop abcdefgh = Input, shifted left 8 bits (wraps around because x^0)
     XOR ┘ ...abcde fgh..... = x^5
Together ┐ efgh.... ....abcd = x^12
         │ abcd...a bcd..... = Feedback
         └     │       │
               ▼       ▼
           [CRC_HI] [CRC_LO]
I had to pick apart those strings and assemble them like that in order for it to make sense. The first three lines are straightforward enough; wherever there's a 1 in the polynomial, you XOR a shifted copy of the input data. However, the "feedback" line didn't make sense until I really thought about it.
If you start with an input of $0100, then you get $1021 out of it. Makes sense, because the very last of the 8 shifts will shift out a 1, and that'll make you XOR the polynomial into your input.
If you start with $0200, you get $2042, which, as expected, is the polynomial again, but shifted left once.
If you start with $1000, you get $1231. What? Why isn't this the polynomial, just shifted left 4 times?

The reason is because you need to think about what's going on when you use a traditional CRC routine. You do XOR a copy of the polynomial shifted left 4 times, but this creates a 1 bit that changes the result of one of your upcoming shifts before you've finished shifting all 8 bits.
On the fourth shift, you XOR the polynomial, which places a 1 such that in another four shifts, you're going to XOR the polynomial a second time. So basically, this is feedback.

The reason there are 4 bits of feedback in this specific case is because the polynomial, $1021, has its most significant "1" bit as the fourth bit from the top four bits away from the final shift. If the polynomial were instead $2021, then you'd have 3 5 bits of feedback. [Edited, I tested this]

So the key to creating a really quick CRC-32 routine (and thus, a very powerful PRNG) would be to find a polynomial that has the least amount of 1 bits in it.
Last edited by Drag on Fri Jun 17, 2022 5:04 pm, edited 2 times in total.
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: CRC routines as PRNGs

Post by Bregalad »

For a RNG I use something that Blargg used to post here which basically does :

Code: Select all

rand = (rand * 5 + 0x3611) & 0xffff
Works wonders, and can be done very quickly, without even using X or Y registers.
Shiru
Posts: 1161
Joined: Sat Jan 23, 2010 11:41 pm

Re: CRC routines as PRNGs

Post by Shiru »

Bregalad, is there a mistake in your code? I just tested distribution of this random, and it is really bad, practicaly no distribution at all.

I personally use a random random code, i.e. it is not mathematically designed, I just put it by a guess, which has more or less nice distribution, although I'm sure it is far from perfect. Vars are 16 bit words:

Code: Select all

seed1+=(seed2>>1);
seed2-=(15^seed1);
return seed1;
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: CRC routines as PRNGs

Post by tepples »

Bregalad wrote:For a RNG I use something that Blargg used to post here which basically does :

Code: Select all

rand = (rand * 5 + 0x3611) & 0xffff
That's called a linear congruential generator. LCGs tend to have a "hyperplanes" problem unless you use only the high byte.

I couldn't find blargg's code in my search; might it have been somebody else?
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Re: CRC routines as PRNGs

Post by blargg »

I use something like this to experiment with various LFSRs and their periods:

Code: Select all

#include <stdio.h>

static unsigned lfsr( unsigned n )
{
    unsigned c = n & 1;
    n >>= 1;
    if ( !c )
        n ^= 0x860E;
    
    return n;
}

int main()
{
    unsigned n = 1;
    
    int period = 0;
    do
    {
        period++;
        if ( period > 0x100000 )
            return 0;
        
        n = lfsr( n );
    }
    while ( n != 1 );
    
    printf( "%d\n", period );
    return 0;
}
Note how lfsr() is written similar to how the 6502 asm would be: save bit that would be shifted into carry, right shift, then test carry. There are lists of "maximal-length" lfsr seeds.

Also, CRC LFSR seeds are designed for particular characteristics that help detect bit errors, thus they are not going to be the most optimal to implement in 6502 for a random number generator. Look around for seeds that favor fewer instructions.
User avatar
Bregalad
Posts: 8056
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: CRC routines as PRNGs

Post by Bregalad »

I don't remember exactly, but I'm 100% sure I got this code from this very board, and it was by a regular. I would have bet blargg, but pehaps it was another person. Pehaps it was in the old WWWThread boards, I'm not sure.

I'll post it anyways :

Code: Select all

GetRandomNmr 		; See "linear-congruential random number generator" for more.
    			; rand = (rand * 5 + 0x3611) & 0xffff;
    			; return (rand >> 8) & 0xff;
	lda RandomH     ; multiply by 5
	sta RandomTemp
	lda RandomL
	asl a		; rand = rand * 4 + rand
	rol RandomTemp
	asl a
	rol RandomTemp
	clc
	adc RandomL
	pha
	lda RandomTemp
	adc RandomH
	sta RandomH
	pla		; rand = rand + 0x3611
	clc
	adc #$11
	sta RandomL
	lda RandomH
	adc #$36
	sta RandomH
	rts		; return high 8 bits
It works wonders to me, and is very fast.

LFSRs are great, but they are probably more suited to a hardware implementation as they can be done with N flip-flops, several inverters and a XOR gate.
This is a bit slow to emulate in software in my opinion, as you'll need at the very least 16-bit, so it means quite a lot of shift/rotate instructions to execute to get new 8 random bits. A single mult + add is definitely faster.

Back to the original topic, those CRC routines could also be very useful to generate some cryptography for passwords in a video game.
I mean, take the first byte, compute the CRC, then XOR it with the second byte, take the CRC, etc... and you get all bytes encrypted.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: CRC routines as PRNGs

Post by Drag »

Well, I'd be looking for a polynomial with as few terms as possible.

With some help of Wikipedia, I found the polynomial x^n + x^31 + x^30 + x^10 + 1, and if my math is correct, that should be
11000000 00000000 00000100 00000001 = C0000401

So, when a 1 is shifted out from an ASL, the variable is XORed with C0000401.

I may be wrong though.

C0000401 creates a lot of feedback, which requires a lot of extra XORs along with shifts. Perhaps a polynomial that begins with 00xxxxxx would be better.
Last edited by Drag on Tue Dec 11, 2012 3:07 pm, edited 1 time in total.
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: CRC routines as PRNGs

Post by rainwarrior »

I mentioned in the other thread, but the LFSR generators don't necessarily have to generate all 8 bits. For full effectiveness you should generate as many new bits as you are consuming, but in practice 2 or 3 generations might be enough for what you're doing. Even just 1 generation is okay for some purposes.

Linear congruential generators like Bregalad just suggested can be pretty good too. They're what I normally use on a platform that has a multiply. Using 5 as the multiplier isn't the greatest, but I'm sure the results are useful enough. (Any two primes for the multiply and add will work, though it's normal to choose a multiplier that is a bit larger than that.)
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: CRC routines as PRNGs

Post by rainwarrior »

Drag wrote:Well, I'd be looking for a polynomial with as few terms as possible.
The polynomials can get extremely simple, for instance the APU Noise LFSR only has two taps. This does not tend to be optimal for "quality", but again, fine for some purposes. (In this case, 1 bit noise.)
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: CRC routines as PRNGs

Post by Drag »

Well yeah, unless I can find a decent 32-bit polynomial (decent meaning maximal-length, as few 1s as possible, ideally with them spread out and away from the most significant 8 bits, while also allowing a good random distribution), it's probably a lot easier to just use a traditional LFSR instead of trying to come up with an optimized one. :P
Post Reply