Announcement

Collapse
No announcement yet.

Steve's random seed in Source Code

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Steve's random seed in Source Code

    question at bottom of following source code -
    '
    Code:
    #compile exe
    #dim all
    
    function pbmain () as long
      #register none
      local X, Y, X2, Y2 as dword''
      ! rdtsc
      ! mov ebx, eax  '2nd rdtsc quick, so register to register save of 1st
      ! mov ecx, edx
      ! rdtsc
      ! mov x, ebx    'now move to variables for display
      ! mov y, ecx
      ! mov x2, eax
      ! mov y2, edx
      ? " " , "EDX",,"EAX"
      ? bin$(y, 32);  " "; bin$(x,32) ; " 1st RDTSC"
      ? bin$(y2, 32); " "; bin$(x2,32); " 2nd RDTSC"
      ? "EAX contains the fast changing bits."
      ? '- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
      ! rdtsc
      ! mov ebx, eax
      ! bswap eax
      ! mov x, ebx
      ! mov y, eax
      X2 = varptr(x) + 3
      Y2 = varptr(Y) + 3
      ? bin$(peek(byte, x2), 8); " ";
      decr x2
      ? bin$(peek(byte, x2), 8); " ";
      decr x2
      ? bin$(peek(byte, x2), 8); " ";
      decr x2
      ? bin$(peek(byte, x2), 8); " "; "An unswapped RDTSC result."
      '. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
      ? bin$(peek(byte, y2), 8); " ";
      decr y2
      ? bin$(peek(byte, y2), 8); " ";
      decr y2
      ? bin$(peek(byte, y2), 8); " ";
      decr y2
      ? bin$(peek(byte, y2), 8); " "; "The same RDTSC result BSWAPped."
      ? '. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
      ? "The question -"
      ? "The unswapped and swapped seeds would lead to different sequences from"
      ? "PRNGs. But I don't see any advantage in a BSWAP unless only the upper 8,"
      ? "or upper 16, bits are used for the seed.
      ? "With a relativly good PRNG, it should produce radically different sequences"
      ? "with even a single bit difference between seeds."
      ?
      ? "(liked the post 'cuz I had to look up RDTSC, thanx)"
      waitkey$
    end function '
    Cheers,
    Dale

  • #2
    Hi Dale,

    This test code shows why the BSWAP is used. as RDTSC is a sequential counter, the end of the counter value is changing very quickly, fast enough to beat repeated calls to RDTSC. The output in HEX shows the last 2 bytes as barely changing but the first 2 bytes are radically different because by inverting the result you get the most movement in the date time counter.
    Code:
    5ED95270
    7FD95270
    ACD95270
    CDD95270
    FAD95270
    24DA5270
    48DA5270
    72DA5270
    9FDA5270
    C0DA5270
    F3DA5270
    14DB5270
    41DB5270
    6BDB5270
    8FDB5270
    B9DB5270
    This is the test piece below.
    Code:
    ' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
    
        #include "\basic\include\win32api.inc"
    
        MACRO FUNCTION randomseed
          MACROTEMP tvar
          LOCAL tvar as DWORD
          ! rdtsc               ' get a fast changing number from the processor
          ! bswap eax           ' reverse byte order to get fast changing end
          ! mov tvar, eax
        END MACRO = tvar
    
    ' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
    
    FUNCTION PBmain as LONG
    
        LOCAL cnt as DWORD
        LOCAL lnt as DWORD
        DIM rarr(16) as DWORD
    
        rarr(0) = randomseed
        rarr(1) = randomseed
        rarr(2) = randomseed
        rarr(3) = randomseed
        rarr(4) = randomseed
        rarr(5) = randomseed
        rarr(6) = randomseed
        rarr(7) = randomseed
    
        rarr(8) = randomseed
        rarr(9) = randomseed
        rarr(10) = randomseed
        rarr(11) = randomseed
        rarr(12) = randomseed
        rarr(13) = randomseed
        rarr(14) = randomseed
        rarr(15) = randomseed
    
        cnt = 16
        lnt = 0
    
        Do
          StdOut hex$(rarr(lnt),8)
          ! add lnt, 1
        Loop While lnt < cnt
    
        waitkey$
    
    End FUNCTION
    
    ' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
    hutch at movsd dot com
    The MASM Forum

    www.masm32.com

    Comment


    • #3
      Yes, the difference (by subtraction) between the seeds is greater by doing BSWAP. But the entropy of generated sequences is not improved. By itself, a handy game quality random seed generator.

      Cheers,
      Dale

      Comment


      • #4
        Yep, whether two DWORD seeds differ by 1 or by 2 000 000 000 should be immaterial to the "randomness" of the output from a PRNG. Just the lower 32 bits of the Time Stamp Counter by itself should suffice. Just get the value of eax after the rdtsc.

        Added:

        You could equally use:
        queryperformancecounter qp
        seed=LO(DWORD,qp)
        (although HPET access is slower than TSC, you probably aren't going to be generating lots of random seeds in a short period of time

        Comment


        • #5
          As a random seed generator, the target is the seed being something like unique and with the range of RDTSC, it would be extremely difficult to ever intentionally duplicate a seed generated in this manner. While you could use it as a base for a random sequence generator, there are better techniques for generating random number sequences but the method is useful for seeding and its small and fast.
          hutch at movsd dot com
          The MASM Forum

          www.masm32.com

          Comment


          • #6
            How often are you reseeding? On my PC a long is overflowed in about a second with RDTSC. So, used as a seed it will be unique and probably widely "spread" from previous seed. The BSWAP is completely, utterly, absolutely useless.
            Dale

            Comment


            • #7
              I don't know what you have done to get a result like that, all RDTSC does (ALA The Intel manual) is write a single DWORD into the EAX register and you can run it till the cows come home and it will only be a 32 bit DWORD value.

              BSWAP does just what it says, produce a number 00112233 hex, run it through BSWAP and it becomes 33221100 hex. Now to get a distribution that is very widely spread and thus very hard to duplicate, if you BSWAP the original 00112233 hex so that the end that is changing very fast you distribute each seed very widely across the whole DWORD range.

              Now differing from a random sequence, what you are after with a random seed is extremely difficult duplication conditions that fall into the practical "impossible" and that is done with two (2) instructions,
              Code:
                  rdtsc
                  bswap eax
              The original macro does what it is supposed to do, produce a random seed that is close enough to impossible to duplicate.
              hutch at movsd dot com
              The MASM Forum

              www.masm32.com

              Comment


              • #8
                Originally posted by Dale Yarker View Post
                How often are you reseeding? On my PC a long is overflowed in about a second with RDTSC. So, used as a seed it will be unique and probably widely "spread" from previous seed. The BSWAP is completely, utterly, absolutely useless.
                Agree.
                RDTSC gets a 64 bit unsigned "long long" integer (QWORD) into edx:eax. That integer is the current value of the Time Stamp Counter which is the number of CPU cycles since the last reset.
                EAX contains the low DWORD of that QWORD.

                A 2.4GHZ processor, (2 400 000 000 cycles per second) will cycle that LOW DWORD through every value from 00000000 to FFFFFFFF (0 to 4 294 967 295) in less that two seconds. Every time you sample it, you will get one of those 4 294 967 296 values

                Reversing the bits in that DWORD does absolutely nothing in terms of making the seed used harder to determine or duplicate or in terms of the randomness of the values returned by a PRNG which uses that seed,

                Comment


                • #9
                  That is right, all it does is count. When EAX gets to hFFFFFFFF the next count makes EAX h00000000 and carries into EDX. When EDX and EAX get to hFFFFFFFF:FFFFFFFF (in around a hundred days), the next count is to h00000000:00000000, and so on round and round.

                  Like I said, (in different words) is about 1 second to count to 2G, or about 2 seconds for DWORD to roll over (depends on clock cycle speed).

                  Just EAX from RDTSC makes nice non-secure seed all by itself. Unless you can control mouse clicks within a microsecond the seed will be random.

                  BSWAP is great for endian swapping. Just not needed here.

                  I never said your macro did not do what it is supposed to. Only that BSWAP was not needed.




                  Dale

                  Comment


                  • #10
                    As MACRO can be placed anywhere in a BASIC procedure, how does EAX get returned to value it held prior to the MACRO?

                    Cheers,
                    Dale

                    Comment


                    • #11
                      Originally posted by Dale Yarker View Post
                      As MACRO can be placed anywhere in a BASIC procedure, how does EAX get returned to value it held prior to the MACRO?

                      Cheers,
                      Presumably by using a MACRO FUNCTION rather than a simple MACRO, so that the old EAX value is PUSHed and POPed around the macro ( with the concomitant overhead)

                      Comment


                      • #12
                        Had to add PUSH and POP around "X1 = randomseed" here. So I do not believe MACRO FUNCTION automatically does PUSH/POP like regular FUNCTIONs/SUBs. (tried while you were posting)

                        Cheers,
                        Dale

                        Comment


                        • #13
                          This should work equally as well
                          TIX q1
                          seed = LO(DWORD,q1)

                          Comment


                          • #14
                            Originally posted by Dale Yarker View Post
                            Had to add PUSH and POP around "X1 = randomseed" here. So I do not believe MACRO FUNCTION automatically does PUSH/POP like regular FUNCTIONs/SUBs. (tried while you were posting)

                            Cheers,
                            Apparently you are correct.
                            If you are using edx or eax for something else in the same function and need to retain their values across the macro substitution, you would have to PUSH/POP them yourself.
                            If you are not using their value for something else both before and after the macro in your code, there is no need to preserve them.

                            Comment


                            • #15
                              If working high level (BASIC) how do you know which registers the compiler uses? When mixing assembly and BASIC the registers must be restored.
                              Dale

                              Comment


                              • #16
                                I think something has been missed here, if you use the direct output from RTDSC without swapping the byte order, you get a LINEAR sequence, when you swap the byte order you get a highly NON LINEAR sequence which is far more useful for seeding a random number generator. RDTSC simply outputs a value to EAX, as soon as you have to put it somewhere (at an address) you must use more instructions but then that is not a problem as the design of a seed generator has little to do with high speed repetition and more to do with distribution across the DWORD range.

                                LINEAR is very badly distributed across the DWORD range, NON LINEAR is very well distributed across the DWORD range and that is why BSWAP has been used to reverse the byte order in EAX. If you look at the original macro,
                                Code:
                                    MACRO FUNCTION randomseed
                                      MACROTEMP tvar
                                      LOCAL tvar as DWORD
                                      ! rdtsc               ' get a fast changing number from the processor
                                      ! bswap eax           ' reverse byte order to get fast changing end
                                      ! mov tvar, eax
                                    END MACRO = tvar
                                You have 2 assembler instructions doing the work, RDTSC and BSWAP, the next instruction is simply putting the result into a memory operand as you have very few registers to use in 32 bit.

                                I suggest that something has been missed with this conversation, the repeat rate simply does not matter as reseeding a random number generator does not need to be done at a high repeat rate, this type of code is not well suited for random number generation, there are many better suited techniques for doing that. For the occasional reseeding a widely distributed result is far better than a linear result, if a linear result was good enough, you could start at 1 and increment it for each required iteration.
                                hutch at movsd dot com
                                The MASM Forum

                                www.masm32.com

                                Comment


                                • #17
                                  Originally posted by Dale Yarker View Post
                                  If working high level (BASIC) how do you know which registers the compiler uses? When mixing assembly and BASIC the registers must be restored.
                                  Help:
                                  Each group of ASM statements must preserve the following CPU registers if the assembler code causes them to change: EBX, ESI, EDI, ESP, EBP, and all segment registers

                                  Comment


                                  • #18
                                    Here is the difference, without BSWAP the use of RDTSC does nothing better than simply incrementing a number from 1 up to count.
                                    Code:
                                    ' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
                                    
                                        #include "\basic\include\win32api.inc"
                                    
                                        MACRO FUNCTION nonrandomseed
                                          MACROTEMP tvar
                                          LOCAL tvar as DWORD
                                          ! rdtsc               ' get a fast changing number from the processor
                                          '''' ! bswap eax           ' reverse byte order to get fast changing end
                                          ! mov tvar, eax
                                        END MACRO = tvar
                                    
                                    
                                    ' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
                                    
                                    FUNCTION PBmain as LONG
                                    
                                        LOCAL cnt as DWORD
                                        LOCAL tot as DWORD
                                    
                                        cnt = 0
                                        tot = 1000
                                    
                                        Do
                                          StdOut format$(nonrandomseed)
                                          ! add cnt, 1
                                        Loop while cnt < tot
                                    
                                        StdOut $CRLF+" Press any key for next"
                                    
                                        waitkey$
                                    
                                        cnt = 0
                                        tot = 1000
                                    
                                        Do
                                          StdOut format$(cnt)
                                          ! add cnt, 1
                                        Loop while cnt < tot
                                    
                                        waitkey$
                                    
                                    End FUNCTION
                                    
                                    ' ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
                                    hutch at movsd dot com
                                    The MASM Forum

                                    www.masm32.com

                                    Comment


                                    • #19
                                      With registers, PB already preserves all of the non transient registers IF #REGISTER NONE is specified. If you are only using EAX ECX and EDX you don't need to preserve anything as they are transient. If you need more registers AND you are using a FASTPROC you need to preserve EBX ESI EDI EBP and ESP if you use any of them.
                                      hutch at movsd dot com
                                      The MASM Forum

                                      www.masm32.com

                                      Comment


                                      • #20
                                        I think something has been missed here,
                                        No, nothing Again. how often are you reseeding? It it not a linear sequence because the count would have gone around many times and a random part of a time. Reseeding multiple times in a second (which would be linear) probably needs a rethink in any case..

                                        If you want to use BSWAP, then go ahead. Even if it were linear the generated sequences would be random (depending on the PRNG) and random between the sequences.

                                        Want to worry about something. Worry about restoring registers when your assembly containing MACRO FUNCTION is mixed with BASIC code. (added - cross posted with #19. 1st mention of #REGISTER NONE)

                                        When I started this I thought it would be 2 or 3 posts, then finished.

                                        One more time, IT IS NOT INCREMENTED EVERY TIME YOU USE RDTSC, THE COUNTER THAT IS COPIED INTO EDX:EAX IS INCREMENTED CONTINUOUSLY AT A GIGAHERTZ RATE. IF YOU CALL LESS OFTEN THAN EVERY SECOND IT IS NOT LENEAR, IF IT MAKES YOU FEEL GOOD TO USE BSWAP THEN GO FOR IT.
                                        Dale

                                        Comment

                                        Working...
                                        X