[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:
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
}
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()
println(dut.io.prng.toLong.toHexString.padTo(8, "0").mkString)
idx += 1
}
}
}
}
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
}
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.
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.
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.
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.
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.
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.
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.
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
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.
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.
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.
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%?
Comments
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:Neat.
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 endmoduleWhen 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() println(dut.io.prng.toLong.toHexString.padTo(8, "0").mkString) idx += 1 } } } }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 } }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.
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
I want a registered PRN, to match the registered state.
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: 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!
"The generation of random numbers is indeed too important to be left to chance."
Dan Kaminsky, DEFCON 22, "Secure Random By Default".
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.
BTW: I had assumed you'd copy'n'pasted the quote, rather than hand typed it.
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.
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.
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.
Its is the exception to the rule:
Possessive : Its
Contraction of it is : it's
It's its own thing :-)
I wish we could put the Pb back in.
And I still have a couple of good sized spools of 63/37 on my bench.
“Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity”
https://arxiv.org/abs/1810.05313
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.
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.
Eutectic mixture that has the lowest melting point for a lead/tin alloy. Best choice for avoiding pad lifting when repairing old pcb's.
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?