CryptoRndIV

[dodicat]

Hi PaulSquires.
Quick run seems to be working OK here now after updating the .exe's.
Thank you.

[PaulSquires]

Hi PaulSquires.
Quick run seems to be working OK here now after updating the .exe's.
Thank you.

Excellent - thanks for letting me know. Appreciate it.

[adeyblue]

Excellent - thanks for letting me know. Appreciate it.

I don't know what's happening, but everytime some changes are made this ListView.html file gets two more of these meta lines and some blank lines at the bottom added to it. I think it's as Edge-y and theme compatible as it going to get now
https://github.com/PaulSquires/WinFBE/c ... 0a138a220b

[deltarho[1859]]

deltarho[1859], I am waiting to read your bad report

What is it Deltarho[] ?

I now have two 'real life' applications to test CryptoRndIV.

One is similar to Monte Carlo.

The other uses a Screen 800*600 with a background of yellow and a foreground of blue. We then 'Pset (CryptoS*800, CryptoS*600)' 800*600 times. We go past that 12 times. The result is almost entirely blue, with only a few yellow pixels left. The time it takes is noted.

I have a CryptoRndII which uses fxm's thread pooling and MS BCryptGenRandom and called that CryptoRndIIfxm.

I used a buffer of 5MB for all the CryptoRnd methods. The revised CryptoS runs at the same speed as the asm version, so effectively is used by all the CryptoRnd methods.

II uses MS thread pooling with MS BCryptGenRandom
II' uses MS thread pooling with RdRand
fxm uses fxm's thread pooling with MS BCryptGenRandom
fxm' uses MS thread pooling with RdRand
IV uses fxm's thread pooling with RdRand
For comparison purposes, I also used PCG32II

Monte Carlo

PCG32II was the fastest, with II and fxm not that far behind. IV was next with II' and fxm' being very bad.

We should have expected II and fxm to be similar, and II' and fxm' to be similar, and they were. IV did better than expected, but it was still bad, but not very bad.

Looks like we have an issue using RdRand.

Screen 800*600

PCG32II was the fastest, with II and II' not that far behind. fxm, fxm', and IV were all very bad.

fxm should have been similar to II - surprise there. II' did better than expected – surprise there as well.

So odd results with this test, but still a suggestion that we have an issue with RdRand

The only thing that I can think of is the buffers are not being populated fast enough when using RdRand. It appears that the buffer filling is a drain on the system until the buffer is fully populated. There is no way that I could see that coming.

The Monte Carlo test takes less than 27ms, so filling the other buffer has yet to complete. The 800*600 test takes about half a second, so the buffer fill only takes about 5% of that. However, using RdRand still had a profound effect.

The above were done in 32-bit mode.

In 64-bit mode PCG32II was blindingly fast, but the conclusion was similar except the issue with using RdRand was less pronounced. Why? In 64-bit mode, RdRand 64 is used rather than RdRand 32, so the buffers get filled twice as quickly; well, not quite, as creating RdRand 64 will take longer than creating RdRand 32. Of course, if RdRand 64 took twice as long as RdRand 32 to create then there would be no difference, but I doubt that is the case.

It seems then thread pooling, using either MS or fxm, with RdRand is not a viable design choice.

CryptoRndIV has therefore been scrapped.

I composed this post on the Ides of March when Julius Caesar was assassinated. CryptoRndIV has met a similar fate.

My utmost apologies to Linux users who have probably just put a contract out on me.

CryptoRndIV: RIP

I leant something during the tests. II', that is CryptoRndII using MS thread pooling with RdRand, in 64-bit mode, saw the console shut down prematurely. That needs looking at. I thought that I had tested all possible combinations – clearly not.

Not a good day then for yours truly or Linux users.

The osteoarthritis in my left knee has got so bad I have been reduced to using a walking stick. I have joined a physiotherapy course at my local hospital, which helps. That is a lot worse than a programming idea going to the wall. Heck, it is only a hobby, after all.

[adeyblue]

As far as assembly instructions go, rdrand is generally quite slow. According to the Agner Fog bible (#4 has the instruction timings), it's slow to the extent that on the CPU type where its throughput is the worst, the next worst instruction in your loop in the first page code (pushad) can do 460 of them per one RdRand. On the best it's more like 20. Of course, It's not as simple as that in reality, but still.

The link is what the kids would call 'deep lore', i.e. nuts-and-bolts level information that I don't entirely understand how to make use of - but essentially the higher the reciprocal throughput number is, the worse it is in tight loops like this and rdrand's is generally one of the highest. That's compared to other assembly instructions anyway, I don't know how many thousands of instructions BCryptGetRandom has to go through in comparison to know if a million plus rdrands should be slower than 1 of those.

[deltarho[1859]]

As far as assembly instructions go, rdrand is generally quite slow.

I went to your link but couldn't find a reference to RdRand.

Interestingly, I will be publishing some code shortly to time using clock cycles instead of the Performance Counter. The code is taken from stuff I did at PowerBASIC about ten years ago.

We cannot compare RdRand with other assembly instructions – we should compare it with other random number generators. RdRand came in with 134 clock cycles. FB's #2 generator, the fastest FB generator, came in with 160 clock cycles. FB #3, Mersenne Twister, came in with 2940 clock cycles. PCG32II came in with 62 clock cycles. FB #5, CryptGenRandom, came in with 28,797,473 clock cycles. However, CryptGenRandom and BCryptGenRandom were designed to fill buffers and not supply one random number.

So RdRand is not slow in of itself, but it seems it cannot compete with BCryptGenRandom filling a 5MiB buffer.

Regarding my clock cycle timing code, I timed the Performance Counter over one millisecond and my code came in with 3499345 clock cycles. My base clock is 3.5GHz, so the true value should have been, 3500000 which is close to four significant figure accuracy.

[deltarho[1859]]

Just for the record, BCryptGenRandom fills 5MiB/2 in 1.5ms, leaving RdRand just coming out of the traps.

Added: I used a different method for timing the buffer fill. It gets a bit hairy when dealing with threads. However, using the same technique as above, RdRand takes just short of 20ms to file 5MiB/2.

So BCryptGenRandom was filling at over 13 times faster than RdRand.

[deltarho[1859]]

Having stepped back from CryptoRndIV and got into other things, an idea occurred to me.

If RdRand is not filling the buffer fast enough, then how's about a smaller buffer. The buffer size has been 5MiB. If we use a buffer size of 512KiB that is only 10% of 5MiB and should fill up 10 times faster. Of course, this means the buffer switching will occur 10 times more often.

So between the buffer switching, we will be going flat out. At a buffer switch, we will have to wait for 7ms for a request to be satisfied. Now 7ms is a long time for a computer, but it is well below our radar, so we will not perceive it. After the switch, we will be going flat out again. From our perspective, it would appear that we are receiving a continuos stream of random numbers at a flat out rate.

OK, I need to do some tests, but CryptoRndIV could very well undergo a resurrection; unlike Julius Caesar.

[deltarho[1859]]

If RdRand is not filling the buffer fast enough, then how's about a smaller buffer.

Using a buffer size of 512KiB was helpful with the Monte Carlo type test.

However, the relationship between IV and the other CryptoRnds with the 'Screen 800*600' was worse than with the 5MiB buffer size approach. With the 'Screen 800*600' the buffer usage went from nine buffers to 88 buffers.

So, we reduced the buffer size because of an issue using RdRand with the Monte Carlo type test, and we are now getting penalized for using too small a buffer size for the 'Screen 800*600' test.

CryptoRndIV was taken out of the scrapyard before being crushed. It has been sent back.

The best CryptoRnd was CryptoRndII which uses Microsoft's thread pooling and BCryptGenRandom.

[deltarho[1859]]

It is swings and roundabout time folks.

The type structure used for CryptoRndIV is ThreadInitThenMultiStart. The code used is at the state reached by fxm during the initial development, when I helped a little by being a beta tester. ThreadInitThenMultiStart has undergone changes since, but I stayed with the original version, figuring that the changes wouldn't have a bearing when used in CryptoRndIV.

I had nothing to lose, so ripped out the original ThreadInitThenMultiStart and replaced it with what is in the WiKi today. It would not compile, but not much was required to achieve a successful compilation.

The 5MiB buffer and Monte Carlo type test is now the fastest and beats PCG32II. The 'Screen 800*600' test is almost identical for both the 5MiB and 512KiB buffer size. That is great - not having to think about what buffer size to use for that type of test. The actual result for the 5MiB test had not changed much. The most significant change was 'Screen 800*600' test and a 512KiB buffer size. The time for that test was halved and, as mentioned, almost identical to the 5MiB buffer size.

The two tests, Monte Carlo type test and 'Screen 800*600', are extremely diverse.

The operative statement in the Monte Carlo type test is: 'If Sqr( x*x + y*y) <= 1 Then lCount += 1' where x and y are random numbers in [0,1).

That type of statement will greatly benefit from faster generators. In fact, PCG32II sees the statement execute over three times faster than Mersenne Twister when using a 5MiB buffer size. I would call this a simple random number statement.

The operative statement in the 'Screen 800*600' is 'PSet (CryptoS*800, CryptoS*600)'. Pset is not the fastest FreeBASIC function and the random numbers play only a small part in the statement's execution time. In this case PCG32II sees the statement execute only 38% faster than Mersenne Twister when using a 5MiB buffer size. I would call this a complex random number statement.

It follows then that whilst a complex random number statement will benefit from a faster generator, it would not be as beneficial as most would expect.

This is why, of the two metrics speed and randomness, to my mind, the quality of randomness is the more important.

So, I have pulled CryptoRndIV back out of the scrapyard again.

I am also back to favouring a 5MiB buffer size, which had been problematic.

I will do further tests and do some code 'tidying up' before publishing the final version of CryptoRndIV.

Linux users: If you did put a contract out on me, please cancel it. Thank you so much.

Just for the record, with a simple random number statement, CryptoRndIV is about four times faster than Mersenne Twister with either buffer size. For a complex random number statement, there is not much between CryptoRndIV and Mersenne Twister speedwise. Of course, Mersenne Twister's randomness is not in the same league as RdRand.

[deltarho[1859]]

CryptoRndIV - final release

Note the three lines added at the end.

Code: Select all

/'
This is the same as CryptoRndII except we use fxm's FreeBASIC method
as opposed to Microsoft's thread pooling and it only uses Intel RdRand
'/

' ****************************** fxm's code

Type ThreadInitThenMultiStartData
    Dim As Function(ByVal p As Any Ptr) As String _pThread
    Dim As Any Ptr _p
    Dim As Any Ptr _mutex1
    Dim As Any Ptr _mutex2
    Dim As Any Ptr _mutex3
    Dim As Any Ptr _pt
    Dim As Byte _end
    Dim As String _returnF
    Dim As UByte _state
End Type

Type ThreadInitThenMultiStart
    Public:
        Declare Constructor()
        Declare Sub ThreadInit(ByVal pThread As Function(ByVal As Any Ptr) As String, ByVal p As Any Ptr = 0)
        Declare Sub ThreadStart()
        Declare Sub ThreadStart(ByVal p As Any Ptr)
        Declare Function ThreadWait() As String

        Declare Property ThreadState() As UByte

        Declare Destructor()
    Private:
        Dim As ThreadInitThenMultiStartData Ptr _pdata
        Declare Static Sub _Thread(ByVal p As Any Ptr)
        Declare Constructor(ByRef t As ThreadInitThenMultiStart)
        Declare Operator Let(ByRef t As ThreadInitThenMultiStart)
End Type

Constructor ThreadInitThenMultiStart()
    This._pdata = New ThreadInitThenMultiStartData
    With *This._pdata
        ._mutex1 = MutexCreate()
        MutexLock(._mutex1)
        ._mutex2 = MutexCreate()
        MutexLock(._mutex2)
        ._mutex3 = MutexCreate()
        MutexLock(._mutex3)
    End With
End Constructor

Sub ThreadInitThenMultiStart.ThreadInit(ByVal pThread As Function(ByVal As Any Ptr) As String, ByVal p As Any Ptr = 0)
    With *This._pdata
        ._pThread = pThread
        ._p = p
        If ._pt = 0 Then
            ._pt= ThreadCreate(@ThreadInitThenMultiStart._Thread, This._pdata)
            MutexUnlock(._mutex3)
            ._state = 1
        End If
    End With
End Sub

Sub ThreadInitThenMultiStart.ThreadStart()
    With *This._pdata
        MutexLock(._mutex3)
        MutexUnlock(._mutex1)
    End With
End Sub

Sub ThreadInitThenMultiStart.ThreadStart(ByVal p As Any Ptr)
    With *This._pdata
        MutexLock(._mutex3)
        ._p = p
        MutexUnlock(._mutex1)
    End With
End Sub

Function ThreadInitThenMultiStart.ThreadWait() As String
    With *This._pdata
        MutexLock(._mutex2)
        MutexUnlock(._mutex3)
        ._state = 1
        Return ._returnF
    End With
End Function

Property ThreadInitThenMultiStart.ThreadState() As UByte
    Return This._pdata->_state
End Property

Sub ThreadInitThenMultiStart._Thread(ByVal p As Any Ptr)
    Dim As ThreadInitThenMultiStartData Ptr pdata = p
    With *pdata
        Do
            MutexLock(._mutex1)
            If ._end = 1 Then Exit Sub
            ._state = 2
            ._returnF = ._pThread(._p)
            ._state = 4
            MutexUnlock(._mutex2)
        Loop
    End With
End Sub

Destructor ThreadInitThenMultiStart()
    With *This._pdata
        If ._pt > 0 Then
            ._end = 1
            MutexUnlock(._mutex1)
            ..ThreadWait(._pt)
        End If
        MutexDestroy(._mutex1)
        MutexDestroy(._mutex2)
        MutexDestroy(._mutex3)
    End With
    Delete This._pdata
End Destructor

' ****************************** End of fxm's code
 
Dim Shared As UByte Buffer0(), Buffer1()
Dim Shared As ulong BufferSize
Dim Shared As Any Ptr SwitchBufferCriteria
Dim Shared As Any Ptr ptrBuffer, ptrBaseBuffer0, ptrBaseBuffer1
Dim Shared As Any Ptr ptrBaseBuffer0plus, ptrBaseBuffer1plus
Dim Shared As ThreadInitThenMultiStart t0, t0plus, t1, t1plus

#ifdef __FB_64BIT__
#define data_size qword
#define wax rax
#define wbx rbx
#define wcx rcx
#define wdi rdi
#define wsi rsi
#else
#define data_size dword
#define wax eax
#define wbx ebx
#define wcx ecx
#define wdi edi
#define wsi esi
#endif
 
Declare Sub SwitchBuffer
Declare Function FillBuffer( ByVal As Any Ptr ) As String
Declare Sub ResetBufferPointer
Declare Sub InitializeCryptoBuffers( As Long )

BufferSize = 5*1024*1024
InitializeCryptoBuffers( BufferSize )

Private Function CryptoDW As ulong
Dim TempVar As ulong 
  If ptrBuffer >= SwitchBufferCriteria Then
    SwitchBuffer
  End If
 
  TempVar = *Cast(ulong Ptr, ptrBuffer)
  ptrBuffer += 4
  Return TempVar
  
End Function

Private Function CryptoS As Double ' [0,1)
Dim TempVar As ulong
 
  If ptrBuffer >= SwitchBufferCriteria Then
    SwitchBuffer
  End If
 
  TempVar = *Cast(ulong Ptr, ptrBuffer)
  ptrBuffer += 4
  Return TempVar/2^32
 
End Function

Private Function CryptoSX As Double ' [-1,1]
Dim TempVar As ulong
 
  If ptrBuffer >= SwitchBufferCriteria Then
    SwitchBuffer
  End If
 
  TempVar = *Cast(ulong Ptr, ptrBuffer)
  ptrBuffer += 4
  Return TempVar/2^31 - 1
 
End Function

Private Function CryptoD As Double  ' [0,1)
 
  If ptrBuffer >= SwitchBufferCriteria Then
    SwitchBuffer
  End If
 
  ' ASM by Wilbert at PureBasic forums
  Asm
    mov eax, dword Ptr [ptrBuffer]
    movd xmm0, [eax]
    movd xmm1, [eax + 4]
    punpckldq xmm0, xmm1
    psrlq xmm0, 12
    mov eax, 1
    cvtsi2sd xmm1, eax
    por xmm0, xmm1
    subsd xmm0, xmm1
    movq [Function], xmm0
  End Asm
 
  ptrBuffer += 8
 
End Function
 
Private Function CryptoDX As Double  ' [-1,1]
 
  If ptrBuffer >= SwitchBufferCriteria Then
    SwitchBuffer
  End If
 
  ' ASM adapted from CryptoD by author
  Asm
    mov eax, dword Ptr [ptrBuffer]
    movd xmm0, [eax]
    movd xmm1, [eax + 4]
    punpckldq xmm0, xmm1
    psrlq xmm0, 12
    mov eax, 2
    cvtsi2sd xmm1, eax
    por xmm0, xmm1
    subsd xmm0, xmm1
    mov eax, 1
    cvtsi2sd xmm1, eax
    subsd xmm0, xmm1
    movq [Function], xmm0
  End Asm
 
  ptrBuffer += 8
 
End Function
 
Private Function CryptoR Overload( Byval One As Long, Byval Two As Long ) As Long
Dim TempVar As ulong
 
  If ptrBuffer >= SwitchBufferCriteria Then
    SwitchBuffer
  End If
 
  TempVar = *Cast(ulong Ptr, ptrBuffer)
  ptrBuffer += 4
  return clng(TempVar Mod (Two-One+1)) + One ' By dodicat
 
End Function
 
Private Function CryptoR Overload( Byval One As Double, Byval Two As Double ) As Double
Dim TempVar As ulong
 
  If ptrBuffer >= SwitchBufferCriteria Then
    SwitchBuffer
  End If
 
  TempVar = *Cast(ulong Ptr, ptrBuffer)
  ptrBuffer += 4
  Return TempVar/2^32*( Two - One ) + One
End Function
 
Private Function Gauss As Single
Static As Long u2_cached
Static As Single u1, u2, x1, x2, w
 
  If u2_cached = -1 Then
    u2_cached = 0
    Function = u2
  Else
    Do
      x1 = CryptoS
      x2 = CryptoS
      w = x1 * x1 + x2 * x2
    Loop While w >= 1
    w = Sqr( -2 * Log(w)/w )
    u1 = x1 * w
    u2 = x2 * w
    u2_cached = -1
    Function = u1
  End If
 
End Function
 
Private Sub InitializeCryptoBuffers( Byval Buffer As Long )
  If Buffer < 1024 Then
    BufferSize = 1024
  Else
    BufferSize = Buffer - Buffer Mod 8
  End If
  Redim Buffer0( 1 To BufferSize) As UByte
  ptrBaseBuffer0 = Varptr( Buffer0(1) )
  ptrBuffer = ptrBaseBuffer0
  SwitchBufferCriteria = ptrBuffer + BufferSize
  t0.ThreadInit( @FillBuffer )
  ptrBaseBuffer0plus = ptrBaseBuffer0 + BufferSize\2
  t0plus.ThreadInit( @FillBuffer )
  t0.ThreadStart( ptrBaseBuffer0 )
  t0plus.ThreadStart( ptrBaseBuffer0plus )
  Redim Buffer1( 1 To BufferSize) As UByte
  ptrBaseBuffer1 = Varptr( Buffer1(1) )
  t1.ThreadInit( @FillBuffer )
  ptrBaseBuffer1plus = ptrBaseBuffer1 + BufferSize\2
  t1plus.ThreadInit( @FillBuffer )
  t1.ThreadStart( ptrBaseBuffer1 )
  t1plus.ThreadStart( ptrBaseBuffer1plus )
  t0.ThreadWait()
  t0plus.ThreadWait()
End Sub

' The following is a substantial rewrite by adayblue
Private Function FillBuffer( ByVal BaseBuffer As Any Ptr ) As String
Dim As ulong HalfBuffer
Dim As ulongint RecoverBuffer
Dim As Any Ptr ptrRecoverBuffer
Dim AS Any Ptr Dummy = BaseBuffer
Dim As Any Ptr wbxBuffer, wsiBuffer, wdiBuffer

ptrRecoverBuffer = cast( Any Ptr, @RecoverBuffer)

HalfBuffer = BufferSize\2

Randomize , 5

Asm
  mov edi, dword Ptr [HalfBuffer]
  xor esi, esi ' xor is shorter code than mov 0
  mov wbx, data_size Ptr [Dummy]
rptRdRand:
  mov ecx, 10 ' Max number Of tries before going into a recovery
queryAgain:
  RdRand wax
  jc OK ' A random value was available
  dec ecx
  jnz queryAgain
  jmp Recover
OK:
  mov data_size Ptr [wbx + wsi], wax ' Store RdRand
  Add esi, SizeOf(Dummy)
  cmp edi, esi
  jne rptRdRand
  jmp Done
Recover:
  mov data_size ptr [wbxBuffer], wbx
  mov data_size ptr [wdiBuffer], wdi
  mov data_size ptr [wsiBuffer], wsi
End Asm
  *(Cast( ulong Ptr, ptrRecoverBuffer )) = Int(Rnd*2^32)
#ifdef __FB_64BIT__
  *(Cast( ulong Ptr, ptrRecoverBuffer + 4 )) = Int(Rnd*2^32)
#endif
Asm
  mov wbx, data_size ptr [wbxBuffer]
  mov wdi, data_size ptr [wdiBuffer]
  mov wsi, data_size ptr [wsiBuffer]
  mov wax, data_size Ptr [ptrRecoverBuffer]
  jmp OK
Done:
End Asm
Return ""
End Function
 
Private Sub SwitchBuffer
  t1.ThreadWait()
  t1plus.ThreadWait()
  Swap ptrBaseBuffer0, ptrBaseBuffer1
  Swap ptrBaseBuffer0plus, ptrBaseBuffer1plus
  ptrBuffer = ptrBaseBuffer0
  SwitchBufferCriteria = ptrBuffer + BufferSize
  t1.ThreadStart( ptrBaseBuffer1 )
  t1plus.ThreadStart( ptrBaseBuffer1plus )
End Sub
 
Private Sub ResetBufferPointer
  ptrBuffer = ptrBaseBuffer0
End Sub

#undef data_size
#undef wax
#undef wbx
#undef wcx
#undef wdi
#undef wsi

#undef Rnd
#define Rnd CryptoS
#define Range_ CryptoR

[neil]

deltarho[1859]
I moved my post over to Cryptanalysis.

[deltarho[1859]]

You are the expert in this field.

I am not. I am a well-informed hobbyist.

Cryptography is a broad church. You are now talking about cryptanalysis. I don't do that. It requires a special mind set. Some people like crosswords – I don't.

[neil]

deltarho[1859]

RE: KnuthRangeDec, KnuthRangeEnc

My plus/minus method above has been edited to include dodicat's improvement.

The code was copied and subject to a 'Quick Run' in my editor to make sure that no typos crept in.

Thank you you for your tips about encryption and including dodicat's improvements. It works fine.

[neil]

Hi deltarho here's something I found about true random numbers.

random.org is claims it's generated numbers are true random numbers?

random.org is a "true random number service that generates randomness via atmospheric noise."

random.org is running on running a Debian based Linux system.

I tried to download numbers to test it with, but I was only allowed to download a 16K file.
This is not enough data to test it. I am not sure if anyone has tested its true random numbers with Practrand.

Do you think random.org generated numbers could be any better than our PRNG's?

It was created 25 years ago.

Here's a link to its history. It was using a transistor radio plugged into a PC's sound card; this was in 1997.
Later, it was improved using a triple radio setup. https://www.random.org/history/