Random/LFSR on P2 - Page 63 — Parallax Forums

# Random/LFSR on P2

• Posts: 21,233
TonyB_,

Thanks for posting xoroshiro64++ results. I had just adapted my little class above to 64++ like so:
```class Xoroshiro64PlusPlus
{
const uint32_t a = 26;
const uint32_t b = 9;
const uint32_t c = 13;
const uint32_t d = 17;

static inline uint32_t rol(uint32_t x, uint32_t bits) noexcept
{
return (x << bits) | (x >> ((sizeof(x) * 8) - bits));
}

uint32_t s0;
uint32_t s1;

public:
explicit Xoroshiro64PlusPlus(uint32_t s0 = 1, uint32_t s1 = 0) noexcept
: s0(s0), s1(s1)
{
}

inline uint32_t operator()() noexcept
{
uint32_t result = rol(s0 + s1, d) + s0;

s1 ^= s0;
s0 = rol(s0, a ) ^ s1 ^ (s1 << b);
s1 = rol(s1, c);

return result;
}
};
```
And it reproduces your results like so:
```00020001
48020a01
81662931
cd2b5253
d3e6cbe6
cd5af43d
860aa4ba
b7bea7fb
63dcaff3
762d74c9
3e7d7e8f
e10e0616
5788242d
d8ece2a3
7a242fab
```

Neat.

• Posts: 11,614
edited 2018-10-12 08:15
evanh wrote: »
TonyB_ wrote: »
[2,6,7,2] is best for simulating a 16-bit PRN. Is the d = 0 binary slot for xoroshiro16+? If so, [2,6,7] is not the best for pair distributions, as shown by the worst scores:
``` 2,  6,  3,  0,   86,   85,   84,   84
2,  6,  7,  1,   82,   88,   86,   85
2,  6,  5,  0,   88,   86,   85,   86
2,  6,  7,  0,   85,   84,   91,   87
5,  6,  2,  0,   89,   87,   88,   88
5,  5,  2,  0,   90,   89,   87,   89
3,  7,  4,  0,   91,   91,   89,   90
7,  6,  2,  0,   92,   90,   90,   91
2,  5,  5,  0,   87,   92,   94,   92
5,  7,  6,  0,   93,   93,   96,   93
3,  6,  2,  0,   94,   94,   95,   94
4,  7,  3,  0,   95,   95,   93,   95
6,  7,  5,  0,   96,   96,   92,   96
```

Yep, d=0 is the single summing (+) scrambler. Hmm, maybe need to verify generated number sequences like Heater is ...
```Xoroshiro16++/+
[2 6 7 2] [2 6 7] [2 6 3]
05       01      01
5c       c5      4d
59       72      82
57       e9      25
4a       cf      13
4b       0a      07
f2       aa      47
0d       a0      8e
2d       7f      9e
77       3e      76
b3       9d      d7
47       97      83
2f       c3      7f
d5       84      28
c7       8e      98
ba       00      81
68       94      2d
c1       64      2d
df       c6      db
37       b8      92
```
• Posts: 21,233
Here is Xoroshiro64PlusPlus in the hardware description language SpinalHDL:
```class  Xoroshiro64PlusPlus extends Component {
val io = new Bundle {
val prng = out UInt(32 bits)
val next = in Bool
}

// The PRNG state
val s0 = Reg(UInt(32 bits)) init(1)
val s1 = Reg(UInt(32 bits)) init(0)

// Xoroshiro64PlusPlus magic numbers
val a = 26
val b = 9
val c = 13
val d = 17

when(io.next) {
s0 := s0.rotateLeft(a) ^ (s1 ^ s0) ^ ((s1 ^ s0) |<< b)
s1 := (s1 ^ s0).rotateLeft(c)
}
io.prng := (s0 + s1).rotateLeft(d) + s0
}
```
Which compiles to the Verilog code:
```module Xoroshiro64PlusPlus (
output [31:0] io_prng,
input   io_next,
input   clk,
input   reset);
wire [31:0] _zz_2;
reg [31:0] s0;
reg [31:0] s1;
wire [31:0] _zz_1;
assign _zz_2 = (s1 <<< 9);
assign _zz_1 = (s0 + s1);
assign io_prng = ({_zz_1[14 : 0],_zz_1[31 : 15]} + s0);
always @ (posedge clk or posedge reset) begin
if (reset) begin
s0 <= (32'b00000000000000000000000000000001);
s1 <= (32'b00000000000000000000000000000000);
end else begin
if(io_next)begin
s0 <= (({s0[5 : 0],s0[31 : 6]} ^ (s1 ^ s0)) ^ _zz_2);
s1 <= {s1[18 : 0],s1[31 : 19]};
end
end
end
endmodule
```
When simulated with the Verilator it produces the same results as above.

Of course we don't mess with Verilog or C++ when using the Verilator, we let Spinal do it all with a test harness in Spinal:
```object Xoroshiro64PlusPlusSim {
def main(args: Array[String]) {

val compiled = SimConfig.withWave.compile{
val dut = new Xoroshiro64PlusPlus ;
dut
}

compiled.doSim("test_Xoroshiro64PlusPlus"){dut =>
// Fork a process to generate the reset and the clock on the dut
dut.clockDomain.forkStimulus(period = 10)

var idx = 0
while(idx < 16){
// Drive the dut input to enable random generation
dut.io.next #= true

// Wait a rising edge on the clock
dut.clockDomain.waitRisingEdge()

idx += 1
}
}
}
}
```
• Posts: 1,757
Heater. wrote: »
Here is Xoroshiro64PlusPlus in the hardware description language SpinalHDL:
```class  Xoroshiro64PlusPlus extends Component {
val io = new Bundle {
val prng = out UInt(32 bits)
val next = in Bool
}

// The PRNG state
val s0 = Reg(UInt(32 bits)) init(1)
val s1 = Reg(UInt(32 bits)) init(0)

// Xoroshiro64PlusPlus magic numbers
val a = 26
val b = 9
val c = 13
val d = 17

when(io.next) {
s0 := s0.rotateLeft(a) ^ (s1 ^ s0) ^ ((s1 ^ s0) |<< b)
s1 := (s1 ^ s0).rotateLeft(c)
}
io.prng := (s0 + s1).rotateLeft(d) + s0
}
```

Or the following?
```...
when(io.next) {
s0 := s0.rotateLeft(a) ^ (s1 ^ s0) ^ ((s1 ^ s0) |<< b)
s1 := (s1 ^ s0).rotateLeft(c)
io.prng := (s0 + s1).rotateLeft(d) + s0
}
}
```
• Posts: 1,757
edited 2018-10-13 23:51
P2 asm version of xoroshiro64++ [a,b,c,d]
```con				' xoroshiro64 constants
a = 26
b = 9
c = 13
d = 17			' ++ only

dat	org

xoro64				' xoroshiro64 prng
xor	s1,s0
rol	s0,#a
mov	prn,s1
xor	s0,prn
shl	prn,#b
xor	s0,prn		' new state low
rol	s1,#c		' new state high
mov	prn,s1
add	prn,s0		' xoroshiro64+ prn
rol	prn,#d
_ret_	add	prn,s0		' xoroshiro64++ prn

s1	long	0		' state high
s0	long	1		' state low
prn	long	0		' pseudo-random number
```

There are various ways of writing the routine and shortest length is 11 instructions, considerably more than the two for XORO32. Code above calculates PRN after new state iterated, which saves a register. xoroshiro64++ has period of 2^64-1 and is only really required if XORO32 period of 2^32-1 is considered to be too short.
• Posts: 21,233
edited 2018-10-13 23:52
TonyB_

No you can't do that. The idea is that the stuff inside a "when" updates state. That is to say it clocks new values into the state registers ("Reg").

Trying to update something that is not a register in the "when" produces the error "LATCH DETECTED from the combinatorial signal". Which is a correct response because what we actually want here is a continuous assignment (Just wire connections) from the state registers to the io output bus.

The problem is that if we could have "io.prng := ..." in the "when" clause then io.prng is not defined until io.next becomes true. Which it might never do. We can't have an output with nothing driving it!

In the Verilog world this is known as an "inferred latch" and is a problem that can catch you out as it's easy to create inferred latches accidentally when you don't really want a register.

In fact this is an example of a great feature of SpinalHDL, it does a much better job of catching all kind of mistakes that cause a lot of head scratching to Verilog writers.

See here https://stackoverflow.com/questions/22459413/what-is-inferred-latch-and-how-it-is-created-when-it-is-missing-else-statement-i and here https://www.nandland.com/articles/how-to-avoid-transparent-latches-in-vhdl-and-verlog.html

• Posts: 1,757
Heater. wrote: »
TonyB_

No you can't do that. The idea is that the stuff inside a "when" updates state. That is to say it clocks new values into the state registers ("Reg").

Trying to update something that is not a register in the "when" produces the error "LATCH DETECTED from the combinatorial signal". Which is a correct response because what we actually want here is a continuous assignment (Just wire connections) from the state registers to the io output bus.

I want a registered PRN, to match the registered state.
• Posts: 21,233
edited 2018-10-14 06:16
I'm not sure I follow what you mean. Currently the prng output exactly follows the current state register values via some sequential logic. It is effectively registered.

I'll assume you mean you want the equivalent of moving the ++ scrambler to the end of the C code function.

In that case we have to calculate the next PRNG state and scrambler output using sequential logic but only actually update the state registers in the "when" clause. Something like this:
```class  Xoroshiro64PlusPlus extends Component {
val io = new Bundle {
val prng = out UInt(32 bits)
val next = in Bool
}

// The PRNG state
val s0 = Reg(UInt(32 bits)) init(1)
val s1 = Reg(UInt(32 bits)) init(0)

// Xoroshiro64PlusPlus magic numbers
val a = 26
val b = 9
val c = 13
val d = 17

// Pre-calculate the next PRNG state.
val s0_ = s0.rotateLeft(a) ^ (s1 ^ s0) ^ ((s1 ^ s0) |<< b)
val s1_ = (s1 ^ s0).rotateLeft(c)

when(io.next) {
// Update the PRNG state
s0 := s0_
s1 := s1_
}
io.prng := (s0_ + s1_).rotateLeft(d) + s0_
}
```
Note: that this does not require any new registers, it just moves the sequential logic around w.r.t the state registers we have already. I'm guessing the number of gates used is the same.

Which produces the following result:
```48020a01
81662931
cd2b5253
d3e6cbe6
cd5af43d
860aa4ba
b7bea7fb
63dcaff3
762d74c9
3e7d7e8f
e10e0616
5788242d
d8ece2a3
7a242fab
98ef01be
```
Same as before but missing the initial 00020001 we had.

I like it. This does not give you your seed value back as the first random number which would not be very random now world it!
• Posts: 21,233
edited 2018-10-15 08:24
Thought for the day:

"The generation of random numbers is indeed too important to be left to chance."

Dan Kaminsky, DEFCON 22, "Secure Random By Default".

• Posts: 11,614
edited 2018-10-15 04:59
Funnies work better with correct spelling when the right words are used!

• Posts: 21,233
Well spotted. That was not misspelling or the wrong word, it was a typo
I was mostly asleep when I heard that on utube last night. It's not so funny anyway but I could not resist sharing after the massively long discussions about PRNG we have had here.
• Posts: 11,614
Huh, I'd always equated typo as same as misspelling, whether by accident or not.

• Posts: 11,614
edited 2018-10-15 10:00
For me, an example of a wrong word would be using "your" to mean "you are" and thinking you've got it right.

BTW: I had assumed you'd copy'n'pasted the quote, rather than hand typed it.

• Posts: 21,233
edited 2018-10-15 11:11
Wrong word, misspelling, typo, the results are all the same I guess.

To me "typo" implies the writer probably has the correct word and probably knows how to spell it, they just happened to hit the wrong key. "your"/"you are", "its"/"it's", "to"/too", "due"/"do" mistakes are all over the net. Now I find I'm doing it!

The quote is somewhere in this presentation "Secure Random by Default"

I scribbled it down because it made me chuckle.

The problem of getting sufficient randomness first hit me whilst working on a crypto algorithm for some mobile military gear thirty years ago. I was surprised that such a simple sounding thing was so difficult and so easy to get wrong.

• Posts: 11,614
I've never noticed anyone use "do" in place of "due". They're not even pronounced the same. Due is pronounced same as dew.

I can understand "too" being accidentally shortened by some, and I mean some. But I'm pretty certain others don't have a clue they're doing wrong at all, particularly with "you're" vs "your".

"its" vs "it's" is one I have trouble with. Having three meanings doens't help. Sometimes I've been typing "it's" so much, as a shortened "it is", that I add the apostrophe through repetitive habit, so that's typo then. Other times I'm actually not sure what is correct, so can be a wrong word then. I think it's called possessive when using the apostrophe. Something like that.

I prefer apostrophes always be used on acronyms, possessive or not. It's a lot easy to read the acronym then.

• Posts: 21,233
I think the "do"/"due" thing is limited to some particular American accents where they begin to sound the same.
• Posts: 425
Heater. wrote: »
I think the "do"/"due" thing is limited to some particular American accents where they begin to sound the same.

Similarly, the 'moot point' vs 'mute point' confusion only makes sense in those accents.

Of course, in some parts of the USA these words all sound the same:
merry
marry
Mary
while where I'm from they are all distinct.
• Posts: 425
evanh wrote: »
I've never noticed anyone use "do" in place of "due". They're not even pronounced the same. Due is pronounced same as dew.

I can understand "too" being accidentally shortened by some, and I mean some. But I'm pretty certain others don't have a clue they're doing wrong at all, particularly with "you're" vs "your".

"its" vs "it's" is one I have trouble with. Having three meanings doens't help. Sometimes I've been typing "it's" so much, as a shortened "it is", that I add the apostrophe through repetitive habit, so that's typo then. Other times I'm actually not sure what is correct, so can be a wrong word then. I think it's called possessive when using the apostrophe. Something like that.

I prefer apostrophes always be used on acronyms, possessive or not. It's a lot easy to read the acronym then.

Its is the exception to the rule:
Possessive : Its
Contraction of it is : it's

It's its own thing :-)
• Posts: 21,233
I just wish Americans would put the "l" back into "solder"
• Posts: 13,610
Heater. wrote: »
I just wish Americans would put the "l" back into "solder"

I wish we could put the Pb back in.
• Posts: 21,233
Ha, round here solder is pronounced "60/40"!
• Posts: 8,693
Heater. wrote: »
Ha, round here solder is pronounced "60/40"!

And I still have a couple of good sized spools of 63/37 on my bench.
• Posts: 21,233
• Posts: 957
Is this old news?

“Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity”

https://arxiv.org/abs/1810.05313
• Posts: 11,614
KeithE wrote: »
Is this old news?

In short, yep.

We've gone through a number of changes since then. The free-running shared hardware generator in the hub is using Xoroshiro128**. The XORO32 instruction in each cog is using Xoroshiro32++. You'll note neither is a single + suffix.

• Posts: 11,614
edited 2018-10-15 16:48
Seba and Dave (The authors of the Xoroshiro/Xoshiro generator algorithms) have been hard at work to improve things. And we've even been privy to early info from them. Tony has been keeping the lines open.

• Posts: 11,614
These aren't the best of the best in quality, but the trade-off is performance and compactness in hardware.

Quality of the XORO32 is reaching about 10% of full period. 10% may sound like a low number but trust me it is as good as you get without hitting 100%. Lower quality can quickly drop below 1%, which is about where Xoroshiro+ sits with truncated output data.

Without truncation, Xoroshiro+ sits a long way below 0.1%. This will be what Melissa tore into.

• Posts: 8,693
Heater. wrote: »

Eutectic mixture that has the lowest melting point for a lead/tin alloy. Best choice for avoiding pad lifting when repairing old pcb's.
• Posts: 21,233
evanh,
Quality of the XORO32 is reaching about 10% of full period. 10% may sound like a low number but trust me it is as good as you get without hitting 100%. Lower quality can quickly drop below 1%, which is about where Xoroshiro+ sits with truncated output data.
Wait up a minute. XORO32 is a PRNG with 32 bits of state. Right? I thought it was common for such PRNG to have a cycle length that reached all that state space. About 4 billion in this case.

Is it so that XORO32 only reaches 10% of it. I.e 400 million ?

Or is it that it has a 4 billion length cycle but some obscure statistical test fails after 10%?

Or am I misunderstanding something again?

• Posts: 11,614
Number two. Particular tests start to fail at about 400 Mega-Iteration of output collected.