8 Bit Random Numbers

[Bill Bowden]

On Feb 5, 8:21 pm, Nobody <nob...@nowhere.com> wrote:

In the parallel version, the state is shifted one place, with the incoming
bit zero; if the outgoing bit is set, the state is then XOR-ed with the
tap word.

Yes, that clears things up a bit, but the incoming bit occasionally
needs to be set, otherwise it's always going to be the same.

With PIC assembly, looks like only 3 lines are needed. But the
sequence length is 2^n-2 for some reason. It loops around every 254
counts. Not sure what's missing.

The first line (RLF) shifts the register left one place with the
incomming bit "0" if the carry flag is clear, or "1" if the
flag is set.

The second line tests the carry bit and jumps over the XOR if the
bit is clear "0".

The 3rd line does the XOR and leaves the result in the random
register. The working register (w) contains the constant word B8, so a
couple extra lines are needed to load the B8 into w. But that's only
done once.

Starting at hex 01, the sequence goes.... 01,02,04,08,10,20,40,80,
B8,C9,2B,57,AE,E4,71,E3,7E,FD,42, etc.


Loop:

RLF RANDOM,f ; Shift Left
BTFSC STATUS,0 ; Test carry flag
XORWF RANDOM,f ; XOR w and random
GOTO Loop


-Bill

 

[Nobody]

On Fri, 06 Feb 2009 15:17:16 -0800, Bill Bowden wrote:

In the parallel version, the state is shifted one place, with the incoming
bit zero; if the outgoing bit is set, the state is then XOR-ed with the
tap word.

Yes, that clears things up a bit, but the incoming bit occasionally
needs to be set, otherwise it's always going to be the same.

It doesn't matter. With the parallel version, all of the tap bits get
flipped whenever the outgoing bit is set, equivalent to having XOR
gates between some of the stages.

It isn't like the serial version, where the tap bits determine the
initial value, and the bit then travels through the shift register
unchanged.

With PIC assembly, looks like only 3 lines are needed. But the
sequence length is 2^n-2 for some reason. It loops around every 254
counts. Not sure what's missing.

The first line (RLF) shifts the register left one place

The value of B8 assumes a right shift; it should be 1D (the mirror image)
for a left shift.

with the incomming bit "0" if the carry flag is clear, or "1" if the
flag is set.

The incoming bit should always be zero; i.e. use a (logical) shift rather
than a rotate. If there isn't a distinct shift operation, clear the carry
first.

 

[Nobody]

On Fri, 06 Feb 2009 09:11:19 +0000, Jasen Betts wrote:

)

[snip]

A word of caution: do not use the XOR trick for the swap();

this one?

x^=y;
y^=x;
x^=y;

it fails if x == y.

works here.

But we're not swapping x and y, we're swapping a[x] and a[y], i.e.:

a[x]^=a[y];
a[y]^=a[x];
a[x]^=a[y];

This fails if x == y, i.e. if a[x] and a[y] are the same array element;
the new value will always be zero.

The above code might make it obvious, but consider:

#define SWAP(x,y) do { x^=y; y^=x; x^=y; } while (0)
...
SWAP(a[x], a[y]);

This particular flaw was a runner-up in the 2007 Underhanded C Contest:

http://underhanded.xcott.com/?page_id=9

 

[Bill Bowden]

On Feb 7, 6:43 am, Nobody <nob...@nowhere.com> wrote:

On Fri, 06 Feb 2009 15:17:16 -0800, Bill Bowden wrote:
In the parallel version, the state is shifted one place, with the incoming
bit zero; if the outgoing bit is set, the state is then XOR-ed with the
tap word.

Yes, that clears things up a bit, but the incoming bit occasionally
needs to be set, otherwise it's always going to be the same.

It doesn't matter. With the parallel version, all of the tap bits get
flipped whenever the outgoing bit is set, equivalent to having XOR
gates between some of the stages.

Yes, but there is no tap bit at the lowest bit using B8. Therefore,
the incoming bit is always "0" and never gets flipped.
Maybe the xor word should have the lowest bit set and B8 should be
changed to "1D" ?

-Bill

It isn't like the serial version, where the tap bits determine the
initial value, and the bit then travels through the shift register
unchanged.

With PIC assembly, looks like only 3 lines are needed. But the
sequence length is 2^n-2 for some reason. It loops around every 254
counts. Not sure what's missing.

The first line (RLF) shifts the register left one place

The value of B8 assumes a right shift; it should be 1D (the mirror image)
for a left shift.

with the incomming bit "0" if the carry flag is clear, or "1" if the
flag is set.

The incoming bit should always be zero; i.e. use a (logical) shift rather
than a rotate. If there isn't a distinct shift operation, clear the carry
first.

 

[Nobody]

On Sat, 07 Feb 2009 19:37:20 -0800, Bill Bowden wrote:

In the parallel version, the state is shifted one place, with the incoming
bit zero; if the outgoing bit is set, the state is then XOR-ed with the
tap word.

Yes, that clears things up a bit, but the incoming bit occasionally
needs to be set, otherwise it's always going to be the same.

It doesn't matter. With the parallel version, all of the tap bits get
flipped whenever the outgoing bit is set, equivalent to having XOR
gates between some of the stages.

Yes, but there is no tap bit at the lowest bit using B8. Therefore,
the incoming bit is always "0" and never gets flipped.
Maybe the xor word should have the lowest bit set and B8 should be
changed to "1D" ?

B8 is for right shift, i.e. 0x80 is the incoming bit. For left shift,
use 1D.

But, you're right that the incoming bit must be set in the tap word,
otherwise half of the states will never occur. Or you could use a rotate
and leave the incoming bit clear (38 or 1C). Either way, the
incoming and outgoing bits will always be equal.

 

[Bill Bowden]

On Feb 7, 9:25 pm, Nobody <nob...@nowhere.com> wrote:

On Sat, 07 Feb 2009 19:37:20 -0800, Bill Bowden wrote:
In the parallel version, the state is shifted one place, with the incoming
bit zero; if the outgoing bit is set, the state is then XOR-ed with the
tap word.

Yes, that clears things up a bit, but the incoming bit occasionally
needs to be set, otherwise it's always going to be the same.

It doesn't matter. With the parallel version, all of the tap bits get
flipped whenever the outgoing bit is set, equivalent to having XOR
gates between some of the stages.

Yes, but there is no tap bit at the lowest bit using B8. Therefore,
the incoming bit is always "0" and never gets flipped.
Maybe the xor word should have the lowest bit set and B8 should be
changed to "1D" ?

B8 is for right shift, i.e. 0x80 is the incoming bit. For left shift,
use 1D.

But, you're right that the incoming bit must be set in the tap word,
otherwise half of the states will never occur. Or you could use a rotate
and leave the incoming bit clear (38 or 1C). Either way, the
incoming and outgoing bits will always be equal.

Yes, that works using "1D" as the tap word and clearing the carry bit
before the next shift left, so the incoming bit is always "0" and gets
flipped if the outgoing bit was "1". I get all 255 states.

Loop:

RLF RANDOM,f ; Roll left
BTFSC STATUS,0 ; Skip if flag is clear
XORWF RANDOM,f ; xor if flag is set
BCF STATUS,0 ; Clear carry bit
GOTO Loop

-Bill