Generating Random Numbers

As our next jump on this quick tour of Unix library calls from assembly, let's get seriously random. (Or modestly pseudorandom, at least.) The standard C library has a pair of functions that allow programs to generate pseudorandom numbers. The pseudo is significant here. Research indicates that there is no provable way to generate a truly random random number strictly from software. In fact, the whole notion of what random really means is a spooky one and keeps a lot of mathematicians off the streets these days. Theoretically you'd need to obtain triggers from some sort of quantum phenomenon (radioactivity is the one most often mentioned) to achieve true randomness. But lacking a nuclear-powered random-number generator, we'll have to fall back on pseudo-ness and learn to live with it.

A simplified definition of pseudorandom would run something like this: A pseudorandom-number generator yields a sequence of numbers of no recognizable pattern, but the sequence can be repeated by passing the same seed value to the generator. A seed value is simply a whole number that acts as an input value to an arcane algorithm that creates the sequence of pseudorandom numbers. Pass the same seed to the generator, and you get the same sequence. However, within the sequence, the distribution of numbers within the generator's range is reasonably scattered and random.

The standard C library contains two functions relating to pseudorandom numbers:

The srand function passes a new seed value to the random-number generator. This value must be a 32bit integer. If no seed value is passed, the value defaults to 1.

The rand function returns a 31-bit pseudorandom number. The high bit is always 0 and thus the value is always positive if treated as a 32-bit signed integer.

Once you understand how they work, using them is close to trivial.

Seeding the Generator with srand

Getting the seed value into the generator is actually more involved than making the call that pulls the next pseudorandom number in the current sequence. And it's not that the call to srand is that difficult: You push the seed value onto the stack, and then call srand:

push eax	;	Here, the seed value is in eax
call srand	;	Seed the	pseudorandom number generator
add esp,4	;	Clean up	the stack

That's all you have to do! The srand function does not return a value. But . . . what do you use as a seed value?

That's the rub.

If it's important that your programs not work with the same exact sequence of pseudorandom numbers every time they run, you clearly don't want to use an ordinary integer hard-coded into the program. You'd ideally want to get a different seed value each time you run the program. The best way to do that (though there are others) is to seed srand with the seconds count since January 1, 1970, as returned by the time function, which I explained in the previous section. This value (called time_t) is an unsigned integer that is currently (February 2000) in the high 900 millions and will flip to 1 billion in 2001. It changes every second, so with every passing second you have a new seed value at your disposal, one that by definition will never repeat.

Almost everyone does this, and the only caution is that you must make certain that you don't call srand to reseed the sequence more often than once per second. In most cases, for programs that are run, do their work, and terminate in a few minutes or hours, you only need to call srand once, when the program begins executing. If you are writing a program that will remain running for days or weeks or longer without terminating (such as a server), it might be a good idea to reseed your random-number generator once per day.

Here's a short code sequence that calls time to retrieve the time value, and then hands the time value to

srand:

push dword 0 ; Push a 32-bit null pointer to stack, since

call time	; we don't need a buffer.
	; Returns time_t value (32-bit integer) in eax
add esp,4	; Clean up stack
push eax	; Push time value in eax onto stack
call srand	; Time value is the seed value for random gen.
add esp,4	; Clean up stack

The initial push of a zero simply indicates to time that you're not passing in a variable to accept the time value. The null pointer (which is what a zero value is in this context) has to be there on the stack to keep the time function happy, however. The value you want to keep is returned in EAX.

Generating Pseudorandom Numbers

Once you've seeded the generator, getting numbers in the pseudorandom sequence is easy: You pull the next number in the sequence with each call to rand. And the rand function is as easy to use as anything in the C library: It takes no arguments (so you don't need to push anything onto the stack or clean up the stack afterward) and the pseudorandom number is returned in EAX.

The following program demonstrates how srand and rand work. It also shows off a couple of interesting assembly tricks, and I spend the rest of this section discussing them.

; Source name	: RANDTEST.ASM
; Executable name : RANDTEST
; Version	: 1.0
; Created date	: 12/1/1999
; Last update	: 12/2/1999
; Author	: Jeff Duntemann
; Description	: A demo of Unix rand & srand using NASM 0.98
;

;Build using these commands:

;nasm -f elf randtest.asm

;gcc randtest.o -o randtest

extern printf extern puts extern rand extern scanf extern srand extern time

[SECTION .text]	; Section containing code
global main	; Required so linker can find entry point
main:	; Set up stack frame for debugger
push ebp
mov ebp,esp	; Program must preserve ebp, ebx, esi, & edi
push ebx
push esi
push edi

;;; Everything before this is boilerplate; use it for all ordinary apps!

;; Start by seeding the		random number generator with a time value:
Seedit: push dword 0	;	Push a 32-bit null pointer to stack, since
call time	;	we don't need a buffer.
	; Returns time_t value (32-bit integer) in eax
add esp,4	;	Clean up stack
push eax	; Push time value in eax onto stack
call srand	; Time value is the seed value for random gen.
add esp,4	;	Clean up stack

;;All of the following code blocks are identical except for the size of

;;the random value being generated.

;;Create and display an array of 31-bit random values:

mov edi, dword pull31 ; Copy address of random # subroutine into edi

call puller	; Pull as many numbers as called for in [pulls]
push dword 32	; Size of numbers being pulled, in bits
push dword [pulls]	; Number of random numbers generated
push dword display	; Address of base display string
call printf	; Display the label
add esp,12	; Clean up stack from printf call
call shownums	; Display the rows of random numbers

;; Create and display an array of 16-bit random values:

mov edi, dword pull16 ; Copy address of random # subroutine into edi

call puller	; Pull as many numbers as called for in [pulls]
push dword 16	; Size of numbers being pulled, in bits
push dword [pulls]	; Number of random numbers generated
push dword display	; Address of base display string
call printf	; Display the label
add esp,12	; Clean up stack from printf call
call shownums	; Display the rows of random numbers
;; Create and display an array of 8-bit random values:
mov edi, dword pull8	; Copy address of random # subroutine into edi
call puller	; Pull as many numbers as called for in [pulls]
push dword 8	; Size of numbers being pulled, in bits
push dword [pulls]	; Number of random numbers generated
push dword display	; Address of base display string
call printf	; Display the label
add esp,12	; Clean up stack from printf call
call shownums	; Display the rows of random numbers
;; Create and display an array of 7-bit random values:
mov edi, dword pull7	; Copy address of random # subroutine into edi
call puller	; Pull as many numbers as called for in [pulls]
push dword 7	; Size of numbers being pulled, in bits
push dword [pulls]	; Number of random numbers generated
push dword display	; Address of base display string
call printf	; Display the label
add esp,12	; Clean up stack from printf call
call shownums	; Display the rows of random numbers
;; Create and display an array of 4-bit random values:
mov edi, dword pull4	; Copy address of random # subroutine into edi
call puller	; Pull as many numbers as called for in [pulls]
push dword 4	; Size of numbers being pulled, in bits
push dword [pulls]	; Number of random numbers generated
push dword display	; Address of base display string
call printf	; Display the label
add esp,12	; Clean up stack from printf call
call shownums	; Display the rows of random numbers

;; Clear a buffer to nulls

Bufclr: mov ecx, BUFSIZE+5 ; Fill whole buffer plus 5 for safety

.loop:	dec ecx	; BUFSIZE		is	1-based so decrement first!
mov byte [randchar+ecx],0 ; Mov				null into the buffer
cmp ecx,0		;	Are we done yet?
jnz	.loop	;	If not, go		back and stuff another null

;; Create a string of random alphanumeric characters

Pulchr: mov ebx, BUFSIZE ; BUFSIZE tells us how many chars to pull

.loop: dec ebx ; BUFSIZE is 1-based, so decrement first!

mov edi, dword pull6	; For random in the range 0-63
call puller	; Go get a random number from 0-63
mov cl,[chartbl+eax]	; Use random # in eax as offset into table
	; and copy character from table into cl
mov [randchar+ebx],cl ; Copy char from cl to character buffer
cmp ebx,0	; Are we done having fun yet?
jne .loop	; If not, go back and pull another
;; Display the string	; Output a newline
mov eax,1
call newline	;	using the newline subroutine
push dword randchar	; Push the address of the char buffer
call puts	; Call puts to display it
add esp,4	; Clean up the stack
mov eax,1	; Output a newline
call newline	;	using the newline subroutine
;;; Everything after this is boilerplate; use it for all ordinary apps!
pop edi	; Restore saved registers
pop esi
pop ebx	; Destroy stack frame before returning
mov esp,ebp
pop ebp	; Return control to Linux
ret

;;; SUBROUTINES=============================================================

;---------------------------------------------------------------

;Random number generator subroutines -- Last update 12/1/1999

;This routine provides 5 entry points, and returns 5 different "sizes" of

;pseudorandom numbers based on the value returned by rand. Note first of

;all that rand pulls a 31-bit value. The high 16 bits are the most "random"

;so to return numbers in a smaller range, you fetch a 31-bit value and then

;right shift it zero-fill all but the number of bits you want. An 8-bit

;random value will range from 0-255, a 7-bit value from 0-127, and so on.

;Respects ebp, esi, edi, ebx, and esp. Returns random value in eax.

;---------------------------------------------------------------

pull31: mov ecx,0 ; For 31 bit random, we don't shift

jmp pull

pull16: mov ecx,15 ; For 16 bit random, shift by 15 bits

pull8:	jmp pull		shift by 23	bits
	mov ecx,23 ; For 8 bit random,
pull7:	jmp pull		shift by 24	bits
	mov ecx,24 ; For 7 bit random,
pull6:	jmp pull		shift by 25	bits
	mov ecx,25 ; For 6 bit random,
pull4:	jmp pull		shift by 27	bits
	mov ecx,27 ; For 4 bit random,
pull:	push ecx	; rand trashes ecx;	save shift value on stack
	call rand	; Call rand for random value; returned in eax
	pop ecx	; Pop stashed shift value back into ecx
	shr eax,cl ; Shift the random value by the chosen factor
	ret	; keeping in mind that part we want is in cl
		; Go home with random number in eax

;---------------------------------------------------------------

;Newline outputter -- Last update 12/1/1999

;This routine allows you to output a number of newlines to stdout, given by

;the value passed in eax. Legal values are 1-10. All sacred registers are

;respected. Passing a 0 value in eax will result in no newlines being issued ;---------------------------------------------------------------

newline:	; We need a skip value, which is 10 minus the
mov ecx,10
sub ecx,eax	; number of newlines the caller wants.
add ecx, dword nl ; This skip value is added to the address of
push dword ecx	; the newline buffer nl before calling printf.
call printf	; Display the selected number of newlines
add esp,4	; Clean up the stack
ret	; Go home

nl db 10,10,10,10,10,10,10,10,10,10,0

;;This subroutine displays numbers six at a time

;;Not intended to be general-purpose...

shownums:

mov esi, dword [pulls]	; Put pull count into esi
.dorow: mov edi,6	; Put row element counter into edi
.pushr: dec edi	; Decrement row element counter
dec esi	; Decrement pulls counter
push dword [stash+esi*4] ; Push number from array onto stack
cmp edi,0	; Have we filled the row yet?
jne .pushr	; If not, go push another one
push dword showarray	; Push address of base display string
call printf	; Display the random numbers
add esp,28	; Clean up the stack
cmp esi,0	; See if pull count has gone to <> 0
jnz .dorow	; If not, we go back and do another row!
ret	; Done, so go home!

;;This subroutine pulls random values and stuffs them into an

;;integer array. Not intended to be general purpose. Note that

;;the address of the random number generator entry point must

;;be loaded into edi before this is called, or you'll seg fault! puller:

mov esi, dword [pulls] ; Put pull count into esi

.grab: dec esi		;	Decrement counter in esi
call edi		;	Pull the value; it's returned in eax
mov [stash+esi*4],eax		; Store random value in the array
cmp esi,0		;	See if we've pulled 4 yet
jne .grab		;	Do another if esi <> 0
ret		;	Otherwise, go home!
[SECTION .data]		; Section containing initialized data
pulls	dd 36	; How many numbers do we pull?
display	db 10,'Here is an		array of %d %d-bit random numbers:',10,0
showarray db '%10d %10d %10d %10d %10d %10d',10,0
chartbl	db '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-
[SECTION .bss]		;	Section containing uninitialized data
BUFSIZE equ 70		;	Reserve an integer variable
randval resd 1
stash resd 72		; Reserve an array of 72 integers for randoms
randchar resb BUFSIZE+5		;	Buffer for storing randomly chosen characters

Some Bits Are More Random than Others

Under Linux, the rand function returns a 31-bit unsigned value in a 32-bit integer. (The sign bit of the integerthe highest of all 32 bits-is always cleared.) The Unix documentation for rand and srand indicates that the low-order bits of a value generated by rand are less random than the high-order bits. This means that if you're going to use only some of the bits of the value generated by rand, you should use the highest-order bits you

can.

I honestly don't know why this should be so, nor how bad the problem is. I'm not a math guy, and I will take the word of the people who wrote the rand documentation. But it bears on the issue of how to limit the range of the random numbers that you generate.

The issue is pretty obvious: Suppose you want to pull a number of random alphanumeric ASCII characters? You don't need numbers that range from 0 to 2 billion. There are only 127 ASCII characters, and in fact only 62 are letters and numbers. (The rest are punctuation marks, whitespace, control characters, or nonprinting characters such as the smiley faces.) What you want to do is pull random numbers between 0 and 61.

Pulling numbers that range from 0 to 2 billion until you find one less than 62 will take a long time. Clearly, you need a different approach. The one I took treats the 31-bit value returned by rand as a collection of random bits. I extracted a subset of those bits just large enough to meet my needs. Six bits can express values from 0 to 63, so I took the highest-order 6 bits from the original 31-bit value and used those to specify random characters.

It's easy: I simply shifted the 31-bit value to the right until all bits but the highest-order 6 bits had been shifted off the right end of the value into oblivion. The same trick works with any (reasonable) number of bits. All you have to do is select by how many bits to shift. I created a subroutine with multiple entry points, each entry point selecting a number of bits to select from the random value:

pull31: mov ecx,0 ; For 31 bit random, we don't shift jmp pull

pull16: mov ecx,15 ; For 16 bit random, shift by 15 bits

pull8:	jmp pull		shift by 23	bits
	mov ecx,23 ; For 8 bit random,
pull7:	jmp pull		shift by 24	bits
	mov ecx,24 ; For 7 bit random,
pull6:	jmp pull		shift by 25	bits
	mov ecx,25 ; For 6 bit random,
pull4:	jmp pull		shift by 27	bits
	mov ecx,27 ; For 4 bit random,
pull:	push ecx	; rand trashes ecx;	save shift value on stack
	call rand	; Call rand for random value; returned in eax
	pop ecx	; Pop stashed shift value back into ecx
	shr eax,cl ; Shift the random value by the chosen factor
	ret	; keeping in mind that part we want is in cl
		; Go home with random number in eax

To pull a 16-bit random number, call pull16. To pull an 8-bit random number, call pull8, and so on. I did discover that the smaller numbers are not as random as the larger numbers, and the numbers returned by pull4 are probably not random enough to be useful. (I left the pull4 code in so you could see for yourself by running RANDTEST.)

The logic here should be easy to follow: You select a shift value, put it in ECX, push ECX on the stack, call rand, pop ECX from the stack, and then shift the random number (which rand returns in EAX) by the value in CL-which, of course, is the lowest 8 bits of ECX.

Why does ECX go onto the stack? ECX is not one of the sacred registers in the C calling conventions, and virtually all C library routines use ECX and trash its value. If you want to keep a value in ECX across a call to a library function, you have to save your value somewhere before the call, and restore it after the call is complete. The stack is the best place to do this.

I used the pull6 routine to pull random 6-bit numbers to select characters from a character table, thus creating a string of random alphanumeric characters. I padded the table to 64 elements with two additional characters (- and @) so that I wouldn't have to test each pulled number to see if it was less than 62. If you need to limit random values to some range that is not a power of 2, choose the next largest power of 2-but try to design your program so that you don't have to choose randoms in a range like 0 to 65. Much has been written on random numbers in the algorithm books, so if the concept fascinates you, I direct you there for further study.

Calls to Addresses in Registers

I use a technique in RANDTEST.ASM that sometimes gets forgotten by assembly newcomers: You can execute a CALL instruction to a subroutine address held in a register. You don't always have to use CALL with an immediate label. In other words, the following two CALL instructions are both completely legal and equivalent:

mov ebx, dword pull8

call pull8

call ebx

Why do this? You'll find your own reasons over time, but in general it allows you to treat subroutine calls as parameters. In RANDTEST.ASM, I factored out a lot of code into a subroutine called puller, and then called puller several times for different sizes of random number. I passed puller the address of the correct randomnumber subroutine to call by loading the address of that subroutine into EDI:

;; Create and display an array of 8-bit random values:

mov edi, dword pull8 ;		Copy	address	of random # subroutine into edi
call puller	;	Pull	as many	numbers as called for in [pulls]

Down in the puller subroutine, the code calls the requested random-number subroutine this way:

puller:

mov esi, dword [pulls] ; Put pull count into esi

.grab: dec esi	; Decrement counter in esi
call edi	; Pull the value; it's returned in eax
mov [stash+esi*4],eax	; Store random value in the array
cmp esi,0	; See if we've pulled enough yet
jne .grab	; Do another if esi <> 0
ret	; Otherwise, go home!

See the CALL EDI instruction? In this situation (where EDI was previously loaded with the address of subroutine pull8), what is called is pull8-even though the label "pull8" is nowhere present in subroutine puller. The same code in puller can be used to fill a buffer with all the different sizes of random numbers, by calling the subroutine address passed to it in EDI.

This technique was available in the 8086/8088, but was not often used because in the older processors it was very slow. Since the 486, it's been only slightly slower than calling an immediate label. Calling an address in a register gives you a lot of power to generalize code-just make sure you document what you're up to, since the label which you're calling is not contained in the CALL instruction.

Local Labels

I haven't presented any particularly long or complex programs in this book, so having problems with code labels conflicting with one another hasn't really been an issue. But as you begin to write "real" code for Linux, you'll eventually be writing programs hundreds or even (with some practice and persistence) thousands of lines long. You will soon find that duplicate code labels will be a problem. How will you always remember that you already used the label loop on line 187 of a 1,432-line program?

You won't. And sooner or later, you'll try and use the label loop again. NASM will call you on it with an error.

This is a common enough problem (especially with obviously useful labels such as loop) that NASM's authors created a feature to deal with it: local labels. Local labels are founded on the fact that nearly all labels in assembly work (outside of names of subroutines and major sections) are "local" in nature, by which I mean that they are only referenced by JMP instructions that are very close to them-perhaps only two or three instructions away. Such labels are usually parts of tight loops and are not referenced from far away in the code.

Here's an example:

;; Clear		a buffer to nulls	; Fill whole buffer plus 5 for safety
Bufclr: mov ecx, BUFSIZE+5
.loop:	dec ecx		; BUFSIZE is 1-based so decrement first!
mov byte [randchar+ecx],0 ; Mov null into the buffer
cmp ecx,0			; Are we done yet?
jnz	.loop		; If not, go back and stuff another null
;; Create a string of random alphanumeric characters
Pulchr: mov ebx, BUFSIZE			; BUFSIZE tells us how many chars to pull
.loop:	dec ebx		; BUFSIZE is 1-based, so decrement first!
mov	edi, dword pull6		; For random in the range 0-63
call puller			; Go get a random number from 0-63
mov cl,[chartbl+eax]			; Use random # in eax as offset into table
mov [randchar+ebx],cl			; and copy character from table into cl
			; Copy char from cl to character buffer
cmp ebx,0			; Are we done having fun yet?
jne .loop			; If not, go back and pull another

You'll see that throughout this code snippet the label .loop has a period in front of it. This period marks it as a local label-and there are two .loop labels here, each a separate and distinguishable label. Local labels are local to the first nonlocal label (that is, the first label not prefixed by a period; we call these global) that precedes them in the code. In the preceding code snippet, the first label .loop is local to the global label

Bufclr. It is not visible further up the source code past Bufclr, and once you get above Bufclr, there may be another local label called .loop, without any conflict with the two .loop local labels.

Going down the source code from the global label Bufclr, the local label .loop is referenceable until the next global label, Pulchr, is encountered. You'll see that after Pulchr, there is another .loop, which does not conflict with the .loop that "belongs" to Bufclr. As long as a global label exists between the two of them, NASM has no trouble distinguishing them.

Some notes on local labels:

In a library of subroutines, local labels are at least local to the subroutine in which they are defined. Each subroutine begins with a label (the name of the subroutine, which is a label), so a local label defined within a subroutine will at most be visible until the beginning of the next subroutine. You may, of course, have global labels within subroutines, which will confine visibility of local labels even further.

It's perfectly legal and often helpful to define global labels that are never referenced, simply to provide a context for local labels. If you're writing a utility program that executes in straight-through fashion without a lot of jumping or long-distance looping back, you may go a long way without needing to insert a global label. I like to use global labels to set off major functional parts of a program, whether those labels are ever called or not. This allows me to use local labels freely within those major functional modules. As a personal stylistic convention, I mark such nonreferenced global labels by using a capital letter for the first letter in the label. All labels meant to be referenced begin with lowercase letters. As a side benefit, these labels can be used as breakpoints when debugging with gdb.

Local labels, unfortunately, are not accessible as breakpoints within gdb. I'm not entirely sure why this is so, but gdb will refuse to set a breakpoint on a local label.

A rule of thumb that I use: Global labels and all references to them should occur within a single screen's worth of code. In other words, you should be able to see both a local label and everything that refers to it without scrolling your program editor. This is just a guide to help you keep sense in your programs, but I've found it very useful in my own work.

If you're writing dense code with a lot of intermixed global and local labels, be careful that you don't try to

JMP to a local label on the other side of a global label. This is one reason not to have 15 local labels called .loop within one part of a program-you can easily get them confused, and in trying to jump to one five instructions up, you may unknowingly be jumping to one seven instructions down. NASM won't warn you if there is a local label with the same name on your side of a global label and you try to jump to a local label on the other side of the global label. Bugs like this can be insanely difficult to find sometimes. Like any tool, local labels have to be used carefully to be of greatest benefit.

Placing Constant Data in a Subroutine

By now you're used to thinking of code as living in the [.text] section, and data as living in the [.data] section. In almost all cases this is a good way to organize things, but there's no absolute demand that you separate code and data in this way. It's possible to define data within a subroutine using NASM's pseudoinstructions including DB, DW, and DD. I've created a useful subroutine that shows how this is done and is a good example of when to do it.

The subroutine allows you to issue some number of newline characters to standard output, specified by a value passed to the subroutine in EAX:

newline:	; We need a skip value, which is 10 minus	the
mov ecx,10
sub ecx,eax	; number of newlines the caller wants.	of
add ecx, dword nl ; This skip value is added to the address
push dword ecx	; the newline buffer nl before calling printf.
call printf	; Display the selected number of newlines
add esp,4	; Clean up the stack
ret	; Go home

nl db 10,10,10,10,10,10,10,10,10,10,0

The buffer nl contains 10 newline characters, followed by a null. It is thus a null-terminated string of newline characters, and you can pass all of it-or any chunk starting in the middle and going to the end-to printf. If you pass printf the address of the beginning of the string, printf will output all 10 newlines, and your display will scroll by 10 lines. If you pass printf the address of the third newline, printf will output only 8 newlines, having skipped the first 2. If you only want printf to output a single newline, you pass printf the address of the very last newline, so that the only things that printf actually sends to standard output will be the final newline and the null character.

All the trickery is in calculating the address to pass to printf. The algorithm: To output x newline(s), we need to skip past 10 - x newline(s). This is why we load 10 into ECX and subtract EAX from it. The resulting value in EAX becomes the offset that, when added to the address represented by nl, gives you the address of the place in the string where printf should begin outputting.

Having the data right in the subroutine means that it's easy to cut and paste the subroutine from one program into another without leaving the essential table of newline characters behind. And because the only code that ever uses the newline table is the subroutine itself, there's no benefit to placing the newline table in the more centrally visible [.data] section.