[Fwd: Re: [sdiy] Simplest random source]

[Magnus Danielson]

From: Seb Francis <seb at is-uk.com>
Subject: [Fwd: Re: [sdiy] Simplest random source]
Date: Mon, 18 Nov 2002 01:52:45 +0000

> So I guess it's software after all.  I've been having quite a bit of success with bitshifts+xors, getting really random 16bit numbers which don't repeat for 65535 cycles, and using about 50 instructions to generate each number.  This is getting pretty near an acceptable amount of CPU time .. so with a bit more tweaking...
> 
> Well it turned out my estimate of number of instructions (based on the tcl code) was way off.  In PIC assembler it actually turns out to be 140 instructions to generate a 16 bit random :-(

That sounds like a little too much. You should be down to a handfull
instructions. Allready 50 sounded too much, but I'm not PIC assembler fluent
person.

Let's see... a 64 bit shift register core ought to be something like this

LSHIFT:
	RLF	SHIFT0
	RLF	SHIFT1
	RLF	SHIFT2
	RLF	SHIFT3
	RLF	SHIFT4
	RLF	SHIFT5
	RLF	SHIFT6
	RLF	SHIFT7

where the carry bit is both input and output.

To generate the input carry bit for X^63+X+1 we need to do:
TERMGEN:
        MOVF    SHIFT7,w
	MOVWF   TERM
	RLF	TERM
	RLF	TERM
	MOVF	SHIFT0,w
	XORWF	TERM
	RRF	TERM

The output term naturally has to be formulated, and here I toss the output to
pin RB0 (dirty, TERM is wasted here):

OUTPIN:
	RLF	TERM
	MOVWF	6

We need to initialized this one, which we do by writing 1's into the shift
register:

INIT:
	MOVLW	0xff
	MOVWF	SHIFT0
	MOVWF	SHIFT1
	MOVWF	SHIFT2
	MOVWF	SHIFT3
	MOVWF	SHIFT4
	MOVWF	SHIFT5
	MOVWF	SHIFT6
	MOVWF	SHIFT7

So, this would give the following structure:

INIT:
	MOVLW	0xff
	MOVWF	SHIFT0
	MOVWF	SHIFT1
	MOVWF	SHIFT2
	MOVWF	SHIFT3
	MOVWF	SHIFT4
	MOVWF	SHIFT5
	MOVWF	SHIFT6
	MOVWF	SHIFT7
TERMGEN:
        MOVF    SHIFT7,w
	MOVWF   TERM
	RLF	TERM
	RLF	TERM
	MOVF	SHIFT0,w
	XORWF	TERM
	RRF	TERM
LSHIFT:
	RLF	SHIFT0
	RLF	SHIFT1
	RLF	SHIFT2
	RLF	SHIFT3
	RLF	SHIFT4
	RLF	SHIFT5
	RLF	SHIFT6
	RLF	SHIFT7
OUTPIN:
	RLF	TERM
	MOVWF	6
	GOTO	TERMGEN

Which is a mere 27 instruction (28 bytes) variant for a 63 bit long shift
register. The loop will keep the speed of 18 CPU cycles, and there is no point
in keeping it down to a slower speed, since this thing is looooong enought so
looping is not an issue.

I have not test-run this thing yeat, but I could do that. PIC gurus could
probably point out all the misstakes I've done. Naturally, there is means to
optimize this, like treating the shift registers as a rotating buffer. Question
is if the processing needed bumps of any cycles or not. Anyway, this code is
small enougth to fit into most PICs. It has a small memory footprint (28 byte
code and 9 bytes of register memory, weighing in at 37 bytes) so that should
not be an issue.

Oh, I've looked at the PIC16C71, so you might have to mangle the code and
result slightly to perfectly fit the PIC of your choice.

> I've also hunted the web for random algorithms and while there are plenty,
> all that I've found seem to be geared towards randomness, rather than speed.

I've hoped I've given you an indication of what you could acheive speedwise.

> Unfortunatly there just isn't a convenient source for a 16bit random number
> in my PIC design.  There are no registers which I can rely on to be a good
> random seed.  Timer0 (8bit) will always have the same value when the random
> number needs to be generated.  Timer1 (16bit) is only running when a key is
> held down.  Time2 (8bit) can be used, but is only 8 bit and probably not so
> random because of the timed nature when the LFO needs a new random number.

You don't have much use of a random seed when you run such an algorihtm in
continous mode. You will soon not notice where you started anyway.

> So I've decided to go for kind of a mixed approach to get 16bits ... generate
> an 8bit good quality random number using the bitshift/xor algorithm.  Use
> this for the MSB, and for the LSB use the MSB xor Timer2 value.  Altogether
> it's about 75 instructions which is _just_ ok to fit in the available timing
> slot.

Wasted effort IMHO. If you go for a deep polynom like I have, you've lost track
of things since you started, and it keeps ticking "in random" without looping
on you.

Cheers,
Magnus - Am I a PIC hacker now???