Home-brewed encryption

[dodicat]

OK deltarho- sorry.
I was using the 64 bit compiler, official build.
My main thrust in this thread was to say that using the mod method with local mapping is perfectly viable for a ranger.
Of course mapping the whole range (your method) is equally viable.

-Wc -O3 (with 64 bits)

ten timed runs next, press a key

. . .

total time asm 0.6279848997946829
total time map 0.3212012003641576

But the 32 bit compiler is consistently slower.

[deltarho[1859]]

With 64-bit I get

Code: Select all

total time asm  0.3178004999936093
total time map  0.1374289000086719

The 64-bit native code of the fb code may look very different to that of the 32-bit native code of the fb code. On the other hand the asm code is the same for both 32-bit and 64-bit. Having said that, there is another issue in that the PowerBASIC compiler is an asm emitter and any asm it encounters is not interfered with, as with gas. With gcc goodness knows what it does with our asm. We may use an asm trick that the gcc compiler rides roughshod over and optimizes it into slower code. There is a good argument not to use asm when using the gcc compiler. As I have mentioned, if we use asm then we should write a BASIC equivalent and test for a difference - second guessing will not work.

With the situation here the best solution is to use asm for 32-bit mode and map for 64-bit mode. It would be nice to switch from 32-bit mode to 64-bit without having to think but with the gcc compiler we cannot do that. Life is getting more complicated.

[deltarho[1859]]

I got Ollydbug to look at the 32-bit and 64-bit asm code and it was honoured to the letter.

In 64-bit mode the asm 'mul' is 32-bit and needs extra work for 64-bit arithmetic but, other than that, it should work in our context ie 32-bit ranges.

So, why the 64-bit asm is getting beaten by the map code I don't know. The next step is to use Ollydbug to see what the gcc compiler is making of the map code but, I suspect, I will probably have a job reading that, so I'll not bother.

Added: I also rewrote the asm using 64-bit registers for 64-bit mode but that didn't help. I don't think that 'mul' is dragging its feet in 64-bit mode but more to do with 64-bit compilation of the 'map' code is better than the 32-bit compilation - the 64-bit compiler is not just about using 64-bit registers, it is a different animal. I have some code which works with gcc 8.3 32-bit mode and fails with 64-bit mode unless I drop from -O3 to -O2.

[albert]

Sorry for interrupting.

Try thinking of data compression formulas..
If it doesn't "compress" ; then it's encryption.
Providing , you can undo the attempted compression...

Look on the projects page for "Vari_Cyph" , Version 14 is the latest , but some prefer version 8 , with every char in it's own edit control.

I took message bytes in blocks and scrambled them into a block of random garbage.
The key is the scramble order.

You can select message a message block of , 64 to 1024 characters, and garbage blocks of 1x to 128x the message block...
It then scrambles the message bits into the random garbage to a key.

You can scramble multiple times , with the same , or different keys...

I tried to email it , to a person in Israel , and the govt. blocked the email , citing security concerns..

I don't think it can be hacked...


To cypher multiple times:
Just click the "Copy to input" button , and it will copy the output to the input , to be re-cypherd with the same or different key..

[deltarho[1859]]

@dodicat

I take my hat off to you!

I wrote some test code very different to your tests and the conclusion was that there wasn't much difference between the asm code and your (<random 32-bit number> Mod ((Two-One)+1)) + One code. I looked at the deviations from expectation and found that the distribution was pretty much the same for both methods.

However, with a random number of 2^32-1 I should be getting the top of the range, ie Two, but it was always wrong with your method.

I wrote another piece of code which looked at:

Code: Select all

For i = 1 to 10^6
  tot += (pcg.rand Mod ((Two-One)+1)) + one ' Using PCG32II's 32-bit rand function
Next
tot = tot/10^6
Print (Two+One)/2;" ";tot

What this is saying is: "Determine 10^6 'landing positions' and then give me the average"

The average was bang in the middle of the range.

The asm code also gives an average bang in the middle of the range but with a linear mapping from the 32-bit random number to the range.

Of course, at the end of the day it doesn't matter where the landing positions are so long as the average is bang in the middle of the range. This is analogous to Monte Carlo methods where the quality of the random numbers, ie how they 'come in', is not important. What is important is the quality of the distribution, ie how uniform is it. People tend to use top quality randomness generators because they have very uniform distributions. With the Mod method it is anybody's guess where we land in the range but that doesn't matter as it is random - its uniformity of distribution is as good as the asm linear mapping method.

I would dearly like to see a mathematical proof of why the Mod method works, don't hold your breath waiting for me - I don't have the same number of brain cells as I did over forty years ago.

I have some code which tests the speed of PRNGs with the For/Next loop overhead eliminated. Without the elimination we get an underestimate of the 'real' speed and false conclusions when comparing generators.

This is what I got:

ASM Mod
367 595 32-bit, 62% increase
391 487 64-bit, 25% increase

So, this 'real' speed test gives the Mod method faster than the asm method for both 32-bit and 64-bit. In fact the speed is almost identical to PCG32II's floating point range, suggesting that Mod and '/2^32' are taking very much the same time as the two methods are similar otherwise.

It would be nice to switch from 32-bit mode to 64-bit without having to think

Well, in this case we don't now.

Notice the drop in speed with the Mod method going from 32-bit to 64-bit. I had noticed that a lot of my various PRNGs suffered at the hands of the 64-bit compiler whereas others did better. I think with the 64-bit compiler it is anybodies guess as to what will happen.

I will do further testing but if the above is borne out I will publish an update to PCG32II.

By the way, in your speed test post, starting with "Here this fb code beats the asm speed wise,", you are using '(tempvar))\p2' and not Mod. When I use Mod it is faster than the asm for both 32-bit and 64-bit agreeing with what I got above. p2 should have been 2^32 - remembering that 0 to 2^32-1 has 2^32 values.

I repeat, I take my hat off to you, dodicat, you Scottish rascal.

[deltarho[1859]]

STOP PRESS

I have hit a snag, a weird one. When I test, do I do a test!

If One is negative and Two = Abs(One) the average should be zero and it is most of the time but, occasionally, I get 4295 regardless of the value of One.

"4295 regardless of the value of One"? What on earth is that all about?

I did this test and changed the range

Code: Select all

If One < 0 and Two = Abs(One) Then
  corr = Abs(One)
  One = 0
  Two = Two + corr
End If 

and then corrected tot with 'tot - corr'

I asked for 'tot - corr' if tot - corr <> 0.

For a given One, Two pairing I did 1000 tests.

I got some errors, most of which were '1', which we can live with, but I got some at 4294967295 which is 2^32-1. Notice the 4295 at the beginning of this post.

I changed the test to

Code: Select all

If One < 0 and Two = Abs(One) Then
  corr = Abs(One)
  One = 1
  Two = Two + corr + 1
End If

This time I got printed "******" if tot - corr = 2^32-1.

This was much better.

With One = -299 and two = 299 I got no errors with quite a few tests.

So, I pushed the boat out with One = -857 and Two = 857

Some runs saw no "******", some saw one, some saw two and some saw three. Oddly, the larger Abs(One) the more errors.

Remember this is with 1000 runs.

After all the testing it is worth going back to "If One is negative and Two = Abs(One) the average should be zero and it is most of the time ...". It does not follow that is the only pairing which gives an issue - it is the only pairing that I have found. However, I have done quite a few tests with both One and Two positive without issue.

With '(pcg.rand Mod ((Two-One)+1)) + One', '(Two-One)+1' is always positive so that should not be a problem. It looks like the problem is with adding One at the end, which we have to do, and when One is < 0 and, very strangely, when Two = Abs(One).

With One < 0 and Two = Abs(One) we have a rare event. When we do, we have a rare event if we employ 'corr' but the 'corr' code which will drastically slow down the throughput.

We need to modify the Mod method, or we are stuffed.

I am sure that we have been here before with the Mod method on a different subject but, for the life of me, I cannot remember where. I will find it.

[dodicat]

What about double mod (same as fmod in crt)
Doubles are nearly as fast as integers, and here, faster in 64 bits.

Code: Select all

#define dmod(x,y) (y)*Frac((x)/(y))

dim as longint ans1,ans2

for n as long=1 to 10000000
    var n1=1+int(rnd*5000000)
    var n2=int(rnd*5000000)
    ans1=n2 mod n1
    ans2=dmod(n2,n1)
   if n<20 then print ans1,ans2
   if n=20 then print "please wait . . .  completing the test loop to ten million"
   if ans1<>ans2 then print "Error"
next

dim as double t1,t2,totmod,totdmod
dim as longint lim=10000000,res
print
print "five runs . . ."
for z as long=1 to 5
    
randomize z
t1=timer
for n as long=1 to lim
   var n1=1+int(rnd*5000000)
    var n2=int(rnd*5000000)
    res=n2 mod n1
next
t2=timer
totmod+=t2-t1
print t2-t1,res," Mod time + result"

randomize z
t1=timer
for n as long=1 to lim
   var n1=1+int(rnd*5000000)
    var n2=int(rnd*5000000)
    res=dmod(n2,n1)
next
t2=timer
totdmod+=t2-t1
print t2-t1,res," dMod time + result"
print
next z
print "time mod  ";totmod
print "time dmod ";totdmod
sleep

  

[deltarho[1859]]

Is that supposed to solve the problem in my last post?

[dodicat]

No, it was just a curiosity, I'll study your problem.

[deltarho[1859]]

[srvaldez]

here's a FBfied version of your asm range function, sadly, much slower
the reason I am so late in posting this is that the following union doesn't work

Code: Select all

union mt
	as ulongint uli
	as long l1, l2
end union

apparently

Code: Select all

as long l1, l2

is the same as

Code: Select all

as long l1
as long l2

Code: Select all

union eax_edx
	as ulongint eaxedx
	type
		as long eax_
		as long edx_
	end type
end union
Function MsWsParams.Rangeasm( ByVal One As Long, ByVal Two As Long ) As Long

	static tmp as eax_edx
  static As Ulong TempVar, edx_, ecx_, eax_
  This.Seed0 *= This.Seed0 : This.Sequence0 +=  &hb5ad4eceda1ce2a9ULL: This.Seed0 += This.Sequence0
  This.Seed0 = ( This.Seed0 Shr 32 ) Or ( This.Seed0 Shl 32 )
  This.Seed1 *= This.Seed1 : This.Sequence1 += &hb5ad4eceda1ce2abULL : This.Seed1 += This.Sequence1
  This.Seed1 = ( This.Seed1 Shr 32 ) Or ( This.Seed1 Shl 32 )
  TempVar = This.Seed0 Xor This.Seed1
  ' print "t1 "; tempvar
  edx_=TempVar
  ecx_=One
  eax_=Two
  if eax_<ecx_ then swap eax_, ecx_
  eax_=eax_-ecx_+1
  if eax_<>0 then
	tmp.eaxedx=culngint(eax_)*edx_+ecx_
  end if
  return tmp.edx_+1
End Function

[fxm]

Or:

Code: Select all

union mt
   as ulongint uli
   type
      as long l1
      as long l2
   end type
end union

[srvaldez]

thank you fxm :-)

[srvaldez]

actually, in 64-bit it's 2 times faster than the asm version but 32% slower in 32-bit

[dodicat]

Hi deltarho, sorry for the delay, I've had a busy couple of days.
I cannot replicate your error.
Are you sure you go from -limit to limit in all your test cases, and haven't skipped -limit somewhere?
Here are the three, my own 64 bit generator, and your ulong generator both ways (using mod and not)
(I even tested with dmod)

Code: Select all

#define dmod(x,y) (y)*Frac((x)/(y))

Type MsWsParams
  Declare Constructor
  Declare Sub MyRandomize( ByVal Seed0 As Ulongint = 0, ByVal Sequence0 As Ulongint = 0, _
                           ByVal Seed1 As Ulongint = 0, ByVal Sequence1 As Ulongint = 0 )
  Declare Function Range ( First As Long, Last As Long,flag as long=0 ) As Long
  Seed0 As Ulongint
  Sequence0 As Ulongint
  Seed1 As Ulongint
  Sequence1 As Ulongint
End Type

Sub MsWsParams.MyRandomize( ByVal Seed0 As Ulongint = 0, ByVal Sequence0 As Ulongint = 0, _
                            ByVal Seed1 As Ulongint = 0, ByVal Sequence1 As Ulongint = 0 )
  this.Seed0 = Seed0 : this.Sequence0 = Sequence0
  this.Seed1 = Seed1 : this.Sequence1 = Sequence1
  ' Warm up generator - may be not needed for MsWs but I warm
  ' up every generator; 1.2 microseconds on my machine  <smile>
  For i As Ulong = 1 To 200
    this.Range(1,2)
  Next
End Sub



Function MsWsParams.Range( ByVal One As Long, ByVal Two As Long,flag as long ) As Long
  Dim TempVar As Ulong
  This.Seed0 *= This.Seed0 : This.Sequence0 +=  &hb5ad4eceda1ce2a9ULL: This.Seed0 += This.Sequence0
  This.Seed0 = ( This.Seed0 Shr 32 ) Or ( This.Seed0 Shl 32 )
  This.Seed1 *= This.Seed1 : This.Sequence1 += &hb5ad4eceda1ce2abULL : This.Seed1 += This.Sequence1
  This.Seed1 = ( This.Seed1 Shr 32 ) Or ( This.Seed1 Shl 32 )
  TempVar = This.Seed0 Xor This.Seed1
  if flag=1 then
      
      return (tempvar mod (two-one+1)) + one
      'return one+dmod(tempvar,(two-one+1))
  else
  Asm
    mov edx, Dword Ptr [TempVar]
    mov ecx, [One]
    mov eax, [Two]
    cmp ecx, eax
    jl 0f
    xchg eax, ecx
  0:
    Sub eax, ecx
    inc eax
    jz 1f
    mul edx
    Add edx, ecx
  1:
    mov [Function], edx
  End Asm
  end if
End Function

Constructor MsWsParams
  This.MyRandomize()
End Constructor

Dim Shared As MsWsParams MsWs0, MsWs1
MsWs0.MyRandomize( 85, 14)

'a ulongint generator
type Rand
   a as ulongint
   b as ulongint
   c as ulongint
   d as ulongint
end type

function ranulong(x as rand) as ulongint
   dim e as ulongint = x.a - ((x.b shl 7) or (x.b shr (64 - 7)))
   x.a = x.b xor ((x.c shl 13) or (x.c shr (64 - 13)))
   x.b = x.c + ((x.d shl 37) or (x.d shr (64 - 37)))
   x.c = x.d + e
   x.d = e + x.a
   return x.d
end function

function randouble(x as rand) as double 
    return ranulong(x)/18446744073709551615ull
end function

 sub init(x as rand, byval seed as ulongint=100)
   dim i as ulongint
    x=type(4058668781,seed,seed,seed)
    for i as ulongint=1 to 200
        ranulong(x)
        next
end sub

dim shared as rand z
init(z,rnd*2^19)

function range overload(f as longint,l as longint) as longint
    return (ranulong(z) mod ((l-f)+1)) + f
end function

dim as double tot1,tot2,tot3
dim as long lim=8570

print "warming up for 1 to 10^4 "
randomize
For i as long = 1 to 10^4+rnd*100
   MsWs0.Range(1,lim)
   range(1,lim)
next
print "OK, looping 10^8 with three functions, please wait . . ."

for n as long=1 to 10^8
    tot1+=range(-lim,lim)   'my own
    tot2+=msws0.range(-lim,lim,1) ' deltarho + mod
    tot3+=MsWs0.Range(-lim,lim)   'deltarho orig
next
print
tot1/= 10^8
tot2/= 10^8
tot3/= 10^8
print tot1,tot2,tot3
print "Done"
sleep


  

The limitation with the mod method is:
If you have a very large range (say .8* ulongint), you might have a tail effect.

Imagine if you have a datatype of say 1 to 19
Then you want 1 to 11. (which is a large chunk of the datatype)
01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19
01,02,03,04,05,06,07,08,09,10,11,01,02,03,04,05,06,07,08
You then have two shots at 01 to 08, and one shot at 09,10,11.
Having the ulongint generator gives more accuracy for a range than a ulong generator.