Archived

This topic is now archived and is closed to further replies.

Puzzler183

Random Numbers in ASM

Recommended Posts

Hello. I am currently coding a demo (possibly a 4E4 entry) in ASM. It will be done in mode 13h and my goal will be to keep it under 4K, the smallest cluster size in the NTFS. It will be a protest to outrageous system requirements and large downloads. Anyway, the problem I run into is generating random numbers... I was considering doing:
  
random:
;push dx
rdtsc
;pop dx
ret
  
Anyway, rdtsc loads edx:eax with a 64-bit counter of hwo many CPU cycles have elapsed since startup. I was wondering if people thought this would be good enough for randomness, as UI would only use the ax portion of it. I liked it because it was tiny (about 3 bytes, 5 with the push and pop) and fast (no ports, or loops) but I wanted to get some opinoins. Let me know if you have any ideas, and happy coding!

Share this post


Link to post
Share on other sites
Whether that code is good depends on how you will use it. If you just need a single random number then it is fine, but if you intend to use it to generate say 10.000 numbers in rapid succession then those numbers will not be even remotely random.

If you need something better I recommend looking up one of the official random number algorithms there exist.

Jacob Marner, M.Sc.
Console Programmer, Deadline Games

Share this post


Link to post
Share on other sites
just because something is in 4k dont mean it wont have high sytem requirments. i doubt your demo will run on an old pc (ie 486/386/heck pentium 1). i also hope you plan to keep startup time down as well (ie not too much calculating textures/sound/tables at the start). try to keep ram requirments reasonable as well (ie 32MB is all thats required).

though being mode 13h you should not be dealing with ntfs but fat12/16/32. in other words dos file systems not winnt/2k/xp.

as to your random number generator. its horrid. great for seeding a function however. realize that even using the lower bits still results in problems since its not really random. its a sequential set of numbers which will be quite predictable depending on the pc and what is running. i suggest reading about random number generators. you need to optimize things that can be optimized well.

though the real question is does that method give the results you want that are dependable across pcs? unfortunatly it probably wont.

you may need to do without random numbers completly. i dont see much for them in a 4k entry. you can use other methods or ranomness. look at perlin noise gernerators. they ussually use VERY simplistic random number generators that are fast yet some what random. also being you get the added bouns of using that to create textures or height maps you may need. maybe to create a cloud which you map to a sphere. and yes i know you are using mode13h, but it dont mean you cant do 3d mapping effects.

i hope you are very good at asm and understand the x86 cpu quite well. a 4k intro is very difficult to code well. even when using the power of modern pcs (which you dont seem to want to use and instead want to support older pcs like a pentium2 266 with 64MB of ram).

Share this post


Link to post
Share on other sites
OK. Maybe I didn''t make myself clear. I am using 320 by 200 by 8 (Mode 13h). I will not be using any textures, I will have very few sounds, and everything will fit in the DOS com file which will be under 4K. Now I am not quite sure how you expect high system requirements. Now I will expect this demo to run in windows XP because it is the latest version of windows. I do believe that 4K is the smallest cluster however in the FAT32 system. Now I have read about random number generators they are usually large peices of slow code. And I''m curoius as to how I get away from random number completely? I need them and if you are going to criticize me about size, well then go away. Michalson managed to fit fire, lightining, rain, and random dirt and grass effects in 999 bytes. I will plan to add some sound and and other effects as well. Now I am also curious as to how I am supposed to do 3D in a 4K file?

Now keep in mind that was all constructive criticism and I am not trying to be mean. I may consider a perlin noise generator. Overall, I consider myself very good at ASM and with x86 CPU''s.

To felonius: I will be locking my frame rate with the timer by stealing the interrupt. I will therefore have about 1/18.2 of a second before I generate more rnadom numbers, making everything dependent on when I start the program, and the speed of the users CPU. And with today''s CPU''s, that could mean a lot of change. I might also use upper portion of eax and/or dx for randomness.

Just to let everyone know, I did find a glitch in my code. The rdtsc instruction is only available on Pentium chips.

Share this post


Link to post
Share on other sites
You''ll find in my 999 byte 4E entry the URL where I got my random number generation code (the only code in the program I didn''t do). For convience here it is
www.df.lth.se/~john_e/gems/gem0002.html
You''ll find several different generators there, you might also look at the rest of the site, it has quite a few interesting code snippets that might give you ideas.

Share this post


Link to post
Share on other sites
OK. I'm sorry Lode and civguy. I was having a kind of bad day. Anyway, I looked there and thats some cool stuff. Not what I'm looking ofr but sitll cool.

Also Michalson, I did find that site and took a look around. I thought I might go fishing here some ideas.

[edited by - Puzzler183 on August 13, 2002 8:09:21 PM]

Share this post


Link to post
Share on other sites
puzzler a few things you should understand:

1. mode 13h assumes that you are coding for dos. this meeans it wont work correctly in winxp or other nt based OSes. stealing interrupts probably wont work either. when the x86 is in protected mode (ie 32bit) it only allows the privilaged apps (ie OS and device drivers) to mess with certain interrupts. you definatly cant hijack them. if you code a 16bit dos app you may be able to get away with it to a point on later OSes because of how dos is emulated.

2. you dont need to make it 3d to use lots of cpu. i can EASILY use tons of cpu doing 2d per pixel operations that could make even the latest athlon or pentium IV beg for mercy. kust because something is low res dont mean its dont use massive amounts of cpu. try doing plasma calling sin instead of using a LUT. heck dong motion blurring through the use of mulitple renders of the scene with full screen blur and alpha blending. fillrate is limited. you could even just read from vram and hurt your framerate far worse then lurring the entire screen.

3. dont matter if you use external data files or store the data in the actual executable. you can even generate all your data at runtime using fractals. this includes music, sounds, images, textures, etc. textures dont have to be mapped to 3d objects, they are merely images you would tile.

4. we have given you ideas, but you are expecting too much from so little. you dont seem to understand the ocmpromises involved. just because something seems to work and it uses few bytes does not make it the best way at all. rdtsc is a terrible way to generate random numbers. obviously your lazy and dont wish to research random number generators and how they work so you can create one that fits what you want. a decent random number generator can be only a few bytes long with no loops. a random number generator should be deterministic so that the demo runs the same on all pcs. your method WILL prove quite bad in any instance of semi constant cpu use. this would be most fast pcs. in fact being that it runs different each time some runs will look worse then other runs thus a judge may rate it poorly. not that you care (since you made it clear you dont). though i think protests work best when you actually can compete and show that you can use little resource to create the similar quality (ie creativity and effects). its known you cant attempt to compete on a pure effect level, but technically you can. ensure your code is tight and reliable. make sure your scene is smooth and creative. you may not want music.

5. no one said you were doing 3d. its something that can be done in software. some ppl have even done realtime raytracers as well. you dont need to have sound, yet you could have a fully orchastrated score in which you store the notes and generate the entire sample set using math.

6. with code compression its quite feasible to get a lot of code into 4k. i assume you are actually compressing your executable using a compression scheme you develop (probably a specilized huffman system would be a good start). this allows even more code and data to be stored in your executable.

7. its quite easy to allocate tones of ram and force the use of the swap file. though you probably know this.

i mean a quick search yields:
http://www.agner.org/random/randomc.htm
http://www.openmash.org/lxr/source/random.c?c=srm
http://216.239.51.100/search?q=cache:3XPqsU9uuVoC:www.snippets.org/snippets/portable/portable.php3+asm+random+number+generator+32&hl=en&ie=UTF-8
http://www.agner.org/random/
http://www.math.utah.edu/~alfeld/Random/Random.html
http://www.uni-karlsruhe.de/~RNG/

etc.
only gave some sample links since i doubt you would do a search yourself. if you feel confident with th ex86 cpu and asm then you sohuld have no trouble turning simple c code into asm code and optimizing it.
http://www.rksolution.cz/delphi/dtip0008.txt


with all that said i suggest going for a 64k demo only because it gives more options and allows you to be more competive. 4k is probably smaller then you think. unfortunatly you will be worrying too much about how to keep the code small yet fast instead of the imprtant aspect of the demo. the actual content: effects, scenes, style, motivation, etc.

also you do realize that both edx and eax get clobbered? when using rdstc for random numbers you should not make it a function like that. you should code it how it will be used. in many cases you may not care about certain registers or can ensure the ones you clobber are not being used. furthermore it removes the overhead of the call and ret.

seing that you are making this simple optimization mistake yet are very worried about byte sizes shows that you dont have all the skills required to amke a decent 4k intro yet. a 64k demo (oe 8k intro) may be beter suited for your purposes.

Share this post


Link to post
Share on other sites
OK, first of all Puzzler: lose the attitude, if someones post doesn''t help you then don''t curse them for it.

Second: as you said, rdtsc gets the number of clock cycles passed from start up. So if you did something like this:


  
rdtsc
mov ebx, eax
rdtsc


EBX and EAX would be almost the same, eax being a little bigger. What you have there is a seed generator.. not a random number generator.

Share this post


Link to post
Share on other sites
quote:
Original post by a person
1. mode 13h assumes that you are coding for dos. this meeans it wont work correctly in winxp or other nt based OSes. stealing interrupts probably wont work either. when the x86 is in protected mode (ie 32bit) it only allows the privilaged apps (ie OS and device drivers) to mess with certain interrupts. you definatly cant hijack them. if you code a 16bit dos app you may be able to get away with it to a point on later OSes because of how dos is emulated.



This point in particular is flat wrong. Please read up on how protected mode works (and its features such as aliasing/memory mapping) before you make this mistake (you should also read up on how the 9X and NT kernals run DOS programs). Now take the time to download my 999 4E program. Notice how it runs perfectly on NT (in fact NT was the OS running on my slow test machine, a P200). Notice how it is a DOS program, runs in video mode 13h, and steals the hardware timer interrupt. All versions of Windows provide a highly flexible virtual environment for running DOS programs (mapped memory, port monitoring, intelligent handling of known video modes to allow display in a window).

While you exhibit some knowledge of protected mode (such as privilege rings) you don''t seem to understand how real mode applications are run. The CPU gives the OS complete control as to what a real mode app sees, what resources it can use directly and what resources are transparently mapped elseswhere. As far a DOS program is concerned it is not running in protected mode at all.

Share this post


Link to post
Share on other sites
quote:
Original post by a person
puzzler a few things you should understand:

1. mode 13h assumes that you are coding for dos. this meeans it wont work correctly in winxp or other nt based OSes. stealing interrupts probably wont work either. when the x86 is in protected mode (ie 32bit) it only allows the privilaged apps (ie OS and device drivers) to mess with certain interrupts. you definatly cant hijack them. if you code a 16bit dos app you may be able to get away with it to a point on later OSes because of how dos is emulated.

2. you dont need to make it 3d to use lots of cpu. i can EASILY use tons of cpu doing 2d per pixel operations that could make even the latest athlon or pentium IV beg for mercy. kust because something is low res dont mean its dont use massive amounts of cpu. try doing plasma calling sin instead of using a LUT. heck dong motion blurring through the use of mulitple renders of the scene with full screen blur and alpha blending. fillrate is limited. you could even just read from vram and hurt your framerate far worse then lurring the entire screen.

3. dont matter if you use external data files or store the data in the actual executable. you can even generate all your data at runtime using fractals. this includes music, sounds, images, textures, etc. textures dont have to be mapped to 3d objects, they are merely images you would tile.

4. we have given you ideas, but you are expecting too much from so little. you dont seem to understand the ocmpromises involved. just because something seems to work and it uses few bytes does not make it the best way at all. rdtsc is a terrible way to generate random numbers. obviously your lazy and dont wish to research random number generators and how they work so you can create one that fits what you want. a decent random number generator can be only a few bytes long with no loops. a random number generator should be deterministic so that the demo runs the same on all pcs. your method WILL prove quite bad in any instance of semi constant cpu use. this would be most fast pcs. in fact being that it runs different each time some runs will look worse then other runs thus a judge may rate it poorly. not that you care (since you made it clear you dont). though i think protests work best when you actually can compete and show that you can use little resource to create the similar quality (ie creativity and effects). its known you cant attempt to compete on a pure effect level, but technically you can. ensure your code is tight and reliable. make sure your scene is smooth and creative. you may not want music.

5. no one said you were doing 3d. its something that can be done in software. some ppl have even done realtime raytracers as well. you dont need to have sound, yet you could have a fully orchastrated score in which you store the notes and generate the entire sample set using math.

6. with code compression its quite feasible to get a lot of code into 4k. i assume you are actually compressing your executable using a compression scheme you develop (probably a specilized huffman system would be a good start). this allows even more code and data to be stored in your executable.

7. its quite easy to allocate tones of ram and force the use of the swap file. though you probably know this.

i mean a quick search yields:
http://www.agner.org/random/randomc.htm
http://www.openmash.org/lxr/source/random.c?c=srm
http://216.239.51.100/search?q=cache:3XPqsU9uuVoC:www.snippets.org/snippets/portable/portable.php3+asm+random+number+generator+32&hl=en&ie=UTF-8
http://www.agner.org/random/
http://www.math.utah.edu/~alfeld/Random/Random.html
http://www.uni-karlsruhe.de/~RNG/

etc.
only gave some sample links since i doubt you would do a search yourself. if you feel confident with th ex86 cpu and asm then you sohuld have no trouble turning simple c code into asm code and optimizing it.
http://www.rksolution.cz/delphi/dtip0008.txt


with all that said i suggest going for a 64k demo only because it gives more options and allows you to be more competive. 4k is probably smaller then you think. unfortunatly you will be worrying too much about how to keep the code small yet fast instead of the imprtant aspect of the demo. the actual content: effects, scenes, style, motivation, etc.

also you do realize that both edx and eax get clobbered? when using rdstc for random numbers you should not make it a function like that. you should code it how it will be used. in many cases you may not care about certain registers or can ensure the ones you clobber are not being used. furthermore it removes the overhead of the call and ret.

seing that you are making this simple optimization mistake yet are very worried about byte sizes shows that you dont have all the skills required to amke a decent 4k intro yet. a 64k demo (oe 8k intro) may be beter suited for your purposes.


Dude, you don''t know what is in my code. I will be coding for size and will just code around edx and eax being destroyed. I understand that I don''t need 3D to be CPU intensive. And I don''t care. Just answer my question. I''m not compressing yet. I am trying to write the code now... As for calling me lazy, that is uncalled for, and I am considering deleting this thread becasue that pushed me over the edge... Also, it works in Windows XP... And by the way, try to learn how to punctuate and capitalize.

PS. I will try to disucss your points in better detail in a few minutes...

Share this post


Link to post
Share on other sites
To a person:

1. It does work correctly. Check out Micalson eye candy whore entry for 4E3.

2. I understnad that. But I'm not doing any of that becasue I want it to run on slow comps. I'm not goign to be doing any float point ops in my prog becasue they are slow, and I will avoid long operations.

3. I understand that, I just wanted to make it clear that everyhting will be sotred inthe COM file and will be under 4K.

4. RDTSC is not such a terrible way to generate ranodm numbers. It depends on when the program starts and the speed of the persons computer since I will be wait for a certain number of timer tick before I do ceratin animations. Also, if the person runs it with windows running, no one can tell you how many CPU cycles windows and other progs steal here and there. I am not lazy, I'm not. I don't know why you would say that. I have clearly stated that I have looked at others. Now as for looking different, thats a good thing and I don't know how a rain can look really bad.

5. I will be doing sound but thats not the point of the post.

6. Thankyou, I think I might try that.

7. Your right and I knew that but I won't be allocating anything. I will basically have everything in my 64K segment.

With all that said, I think you should check out Michalsons eye candy whore entry (link anyone?). Besides, I have a really neat way of conveying my character and my scene. Also, if you think I don't have the skills, you are sadly mistaken. I optimized Michalson's 999 byte entry down to 972 bytes on my comp.

Also good point, I will scratch the whole call thing, and just put an rdtsc where I need it. I am just trying to get some basic routines down right now. You know that people can make mistakes right?

Now for blueEbola. I got mad becasue people weren't really answering my original post. Anyway, it would be a seed generator if I was using the edx:eax pair but i'm only using ax so it continually wraps around and is actually pretty good.

[edited by - Puzzler183 on August 13, 2002 8:07:04 PM]

Share this post


Link to post
Share on other sites