Random number - Forums - ASM Community

Home » Forums » Algorithms & Source Code » Random number

Any body got a method for generating a random number?
Like for shuffling a set of cards or rolling dice.
I believe i saw someone post something like that on the old board.

thanx a gig:o

Posted on 2001-08-14 16:50:49 by titan

Linear congruent pseudorandom number generator

push the limit and call it, eax return a rnd between 0..limit-1

somebody told me once its similar to the rnd routine used by psx videogame...

ancev





rnd:

       push ebp ecx edx

       mov eax, [pseed]

       mov ecx, 41c64e6dh

       mul ecx

       add eax, 3039h

       and eax, 7ffffffh

       mov [pseed], eax

       mov ecx, [esp+(4*3)+4]

       sub edx, edx

       div ecx

       xchg eax, edx

       pop edx ecx ebp

       ret 4

Posted on 2001-08-14 17:20:55 by ancev

here it is

Hi,

This very good random number generator is written by Wiz Kid
I only suggest you to use it...go to his site etc

It only looks a little complicated because its inside a DLL but the actual function is simple and very powefull ...





;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;                                                                           ;;

;; Whiz Kid Technomagic Random Number Generator                              ;;

;;                                                                           ;;

;; Windows 95 DLL                                                            ;;

;;                                                                           ;;

;; Copyright 1998 G. Adam Stanislav                                          ;;

;; All rights reserved                                                       ;;

;;                                                                           ;;

;; Company name: Whiz Kid Technomagic                                        ;;

;; Company e-mail: [email]whizkid@bigfoot.com[/email]                                       ;;

;; Web site: [url]www.bigfoot.com/~whizkid[/url]                                        ;;

;;                                                                           ;;

;; Started: 10-Aug-1998                                                      ;;

;; Updated: 11-Aug-1998                                                      ;;

;;                                                                           ;;

;; Permission is hereby granted to use this DLL with your software under the ;;

;; following conditions:                                                     ;;

;;                                                                           ;;

;;    (1) You will not modify it in any way, including but not limited to    ;;

;;        preserving the copyright notice embeded in the DLL.                ;;

;;                                                                           ;;

;;    (2) You will install it in Windows system folder.                      ;;

;;                                                                           ;;

;;    (3) You will not install it over a later version of this DLL.          ;;

;;                                                                           ;;

;; That is quite simple...                                                   ;;

;;                                                                           ;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

TITLE Whiz Kid Technomagic Random Number Generator

.386

.model flat



option dotname



.data



; Our seed number is 39 bits wide. Our random number is a 32-bit integer

; produced from the 39-bit seed number.

.seed	dd	0

		db	11101b	; At least one of the 39 bits must be non-zero!



.code



; Microsoft linker gets really cranky if the label of the DLL entry does not start

; with an underline. Other than that, it can be named anything. However, it should

; end with @12, otherwise the linker gives us a warning.

align dword

_dll@12	proc	public



	mov	al, 1	; Windows is happy when EAX is not 0. To save bytes, we just use AL.

	ret	12



_dll@12	endp



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;

;; To make the DLL useful for everyone, we need to supply two procedures for

;; for every function. One that is fast, one that is compatible with Windows 95

;; calling conventions.

;;

;; The fast ones receive their parameters in the CPU registers. These procedures

;; can be called directly only from assembly language programs.

;;

;; The compatible ones receive parameters on the stack. The also need to have

;; their names mangled in strange ways (preceded by an underline, followed

;; by '@' and the number of bytes passed on stack). They also need to clean up

;; the stack. They can be called by programs written in presumably any language.

;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;

;; We need to allow the calling program to initialize the seed value. Otherwise,

;; the program would receive the same sequence of pseudo-random numbers every

;; time it runs.

;;

;; We shall name the "compatible" procedure _WktmrngSetSeed@4. In C, it would be

;; declared something like this:

;;

;;    unsigned __stdcall WktmrngSetSeed(unsigned);

;;

;; It could be int instead of unsigned. It could also be long or unsigned long

;; (or might have to be, depending on the compiler).

;;

;; The function returns the new seed just set. Or it can be treated as "void."

;;

;; The "Wktmrng" stands for "Whiz Kid Technomagic Random Number Generator."

;; We use it since it is theoretically possible a program may be linked to

;; another DLL which also may contain a SetSeed() function.

;;

;; Of course, we can also place the following in a header file:

;;

;;    #define SetSeed   WktmrngSetSeed

;;

;; That makes coding simpler.

;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;

;; Now, as mentioned above, a "compatible" function must clean its stack.

;; So, the first instinct may be to do something like this:

;;

;;    _WktmrngSetSeed@4 proc public

;;

;;        push    ebp

;;        mov     ebp, sp

;;        mov     eax, [ebp+8]

;;        call    wktmrngsetseed

;;        leave

;;        ret     4

;;

;;    _WktmrngSetSeed@4 endp

;;

;; Of course, that would work, but we can do it much faster. And we will:

;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



; Note: We do not use align dword here. The previous procedure is 5 bytes long,

; this one is 3 bytes long. So this procedure is all within one dword, and the

; next procedure (to which we fall through) is aligned at dword boundary.

_WktmrngSetSeed@4	proc	public



	;; Input:

	;;    [ESP+4] = bits 31-0 of new seed

	;; Output:

	;;    EAX = bits 31-0 of new seed

	;; Registers changed:

	;;    EAX, EDX



	pop	edx		; Save return address in EDX

	pop	eax		; Get new seed in EAX

	push	edx	; Restore return address on top of the stack



	; Notice, no ret here, we are falling through to wktmrngsetseed



_WktmrngSetSeed@4	endp



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;

;; Next we create our "fast" procedure, one that is not concerned with stack

;; parameters and similar plague of high-level languages.

;;

;; We shall name it wktmrngsetseed. Again, we can use a "define" or actually

;; an equ in assembly language programs, like this:

;;

;;    extrn __imp_wktmrngsetseed:dword

;;    SetSeed   equ   __imp_wktmrngsetseed

;;

;; Then to call it, just do:

;;

;;    mov    eax, newseed

;;    call   SetSeed

;;

;; The assembler will automatically interpret the call as:

;;

;;    call   dword ptr:__imp_wktmrngsetseed

;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



wktmrngsetseed	proc	public



	;; Input:

	;;    EAX = bits 31-0 of new seed

	;; Output:

	;;    EAX = same

	;; Registers modified:

	;;    None



	mov	.seed, eax		; Initialize the lower 32 bits of seed

	; Also initialize the rest of it to some fixed number other than 0

	mov	byte ptr .seed[4], 11101b

	ret



wktmrngsetseed	endp



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;

;; OK, so how do we produce a random number? Well, we do not. It is not possible

;; to create a truly random number in software alone. What we can do, however,

;; is produce a sequence of pseudo-random numbers.

;;

;; Such a sequence is cyclical. That means that after we have come up with N

;; numbers, the sequence repeats. In other words, the (N+1)st result will be

;; the same as the 1st result, the (N+2)nd result the same as the 2nd result, etc.

;;

;; That does not sound too good, but it is not a problem if N is reasonably

;; large.

;;

;; Entire volumes have been written about producing a pseudo-random sequence

;; using software methods. They typically follow this algorithm:

;;

;;    new seed      := old seed * A + B

;;    random number := new seed

;;

;; In this algorithm A and B are some constants.

;;

;; The volumes that have been written deal mostly with methods of choosing the

;; right values for A and B, so N is reasonably large.

;;

;; This is an OK method for random-number generators written in high-level

;; languages (HLL). But we can do much better in assembly language.

;;

;; Since we are as close to accessing the hardware directly as we can using

;; software methods alone, we will code a method developed by hardware

;; engineers. They use what they call a feedback shift register (FSR). You can

;; read about it in Chapter 9 (pages 655-657) of The Art of Electronics,

;; Second Edition, by Paul Horowitz and Winfield Hill, ISBN 0-521-37095-7.

;; This is a book anyone dealing with computers (and electronics in general)

;; should have anyway.

;;

;; A FSR shifts the seed value one bit to the right. It than XORs the bit

;; shifted out with one or more bits inside the old seed and stores the

;; result in the most significant bit of the new seed (which is also the

;; new random number). The choice of which bit to XOR is beyond the scope

;; of this comment -- you can find it in the book mentioned above.

;;

;; In case of a 39-bit FSR, we must XOR the bit shifted out either with

;; bit 35 or bit 4 of the old seed.

;;

;; The FSR method has several advantages: First, it is very easy to implement

;; in hardware (which makes you wonder why the Intel processor family does not

;; have a built-in random register. More importantly, with the proper choice

;; of bits to XOR, the n of the sequence is very high. For a 39-bit sequence

;; which we are implementing in this DLL, N = 549,755,813,887. Yes, you call

;; the procedure below more than half a trillion times before the sequence starts

;; repeating. That is way bigger than any of the A,B choices in the HLL design

;; mentioned above.

;;

;; The method has one slight problem: If the seed is initialized to 0, the

;; whole sequence degenerates. All remaining "random numbers" will be zeros.

;; By the same token, the sequence will never produce a zero in all bits

;; if initialized to any number but 0. We get around this problem by using

;; a larger than 32-bit sequence, and placing a 1 to some of the higher bits

;; whenever initializing the seed. And because we are only using the other

;; 32 bits for our result, we can also receive a zero as a random number.

;;

;; So, why is it not used in software much? Is it, perhaps, too hard to implement

;; using an HLL? Well, it is very simple with assembly language.

;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;

;; In this case, no parameter is passed to our procedure. That means that

;; our "compatible" function and fast funtion are one and the same.

;;

;; The assembler lets us assign any number of names to the same procedure,

;; so we will name it _WktmrngGetRandomNumber@0 for HLL programs and

;; wktmrnggetrandomnumber for assembly language program (just to be

;; consistent with the nameing convention of the above procedures.

;;

;; In C, we can declare it as:

;;

;;    unsigned WktmrngGetRandomNumber(void);

;;    #define GetRandomNumber   WktmrngGetRandomNumber

;;

;; In assembly language:

;;

;;    extrn __imp_wktmrnggetrandomnumber:dword

;;    GetRandomNumber   equ   __imp_wktmrnggetrandomnumber

;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

align dword



_WktmrngGetRandomNumber@0	proc	public

wktmrnggetrandomnumber	proc	public



	;; Input:

	;;    None

	;; Output:

	;;    EAX = 32-bit pseudo-random number

	;; Registers modified:

	;;    EAX



	; Save registers used for anything but return value

	push	ecx

	push	edx



	; Move bits 31-0 of old seed to EAX

	mov	eax, .seed

	; Move bits 38-32 of old seed to DL, set DH = 0

	movzx	edx, byte ptr .seed[4]

	; Shift bits 32-1 to bits 31-0

	shrd	eax, edx, 1

	; Save bits 31-0 of new seed

	mov	.seed, eax



	; Store bit 0 of OLD seed in DH

	adc	dh, 0		; DH = bit shifted out of EAX

	; Shift bits 38-33 of old seed to bits 37-32

	shr	dl, 1

	; Get bit 35 of old seed to the lsb of CL

	mov	cl, dl

	shr	cl, 2

	and	cl, 1		; CL = bit 35 of old seed

	xor	dh, cl		; xor it with old bit 0

	shl	dh, 6

	or	dl, dh		; store it in bit 38 ...

	mov	byte ptr .seed[4], dl	; ... of new seed



	pop	edx

	pop	ecx

	ret



	; That's all, folks!



wktmrnggetrandomnumber	endp

_WktmrngGetRandomNumber@0	endp



end	_dll@12

Posted on 2001-08-14 17:45:59 by BogdanOntanu