Other aspects of the NES that might be random (such as register and memory contents) are probably not random enough for seeding a pseudo-random number generator.
Something glitchy this way comes.
¿Pretendo? ¿Innuendo?
No entiendo.
Wintendo? Nesticle? Ninten
don't.
Kevtris clued me in on how to get randomness before the player presses anything, without using a battery circuit. I'll have something to show you later this week.
No offence, but are you getting senile or something ?
I was on the point to report this as spam, when I suddenly saw : oh, this post was made by tepples ?
If you bump a 4 year old thread, at least write something sensible in it.
Bregalad wrote:
If you bump a 4 year old thread, at least write something sensible in it.
The nonsensical links are expected from tepples, but I'd expect more than a "teaser" to justify the necrobump.
tepples wrote:
Kevtris clued me in on how to get randomness before the player presses anything, without using a battery circuit.
What was unclear about this post?
Let me explain further: Last night I was in #nesdev with kevtris, and I asked about potential sources of randomness to choose one of six opening cut scenes before the player has a chance to press Start. He told me about a way to read values resulting from analog effects in the PPU.
tepples wrote:
What was unclear about this post?
Nothing was unclear, it's just that it had no actual content, it's a teaser for content you intend to post in the future.
Not that it bothers me or anything, I just found it weird.
Quote:
Let me explain further: Last night I was in #nesdev with kevtris, and I asked about potential sources of randomness to choose one of six opening cut scenes before the player has a chance to press Start. He told me about a way to read values resulting from analog effects in the PPU.
Oh, and we were supposed to guess this by looking at your jargon post ?
I guess the time between reset and the first VBlank could be random... on real hardware but most (if not all) emus will not simulate this.
Think back to
that topic about Young Indiana Jones. Reading from $2007 during rendering causes the PPU to skip a line and possibly a byte. Young Indy and the title screen of Zelda II use this to skip some scanlines, and I had made a demo called
Boing 2007 that uses this same effect to stretch a background.
As for the value itself, Kev tells me a whole bunch of things get enabled at once inside the PPU, which causes not-very-predictable "analog" effects. So I used a CRC16 routine to take a hash of 256 reads from $2007 in order to establish a random seed. I'll post a demo with source later, and I'll need people's help to test it on an NES without the PowerPak menu getting in the way.
Oh, and by now, I'm starting to agree that the necro-bump might not have been the best choice here.
I completely forgot about this, but I guess this was because you can't really do things that writes to $2005/6 can't do with this effect, so I quickly forgot about it.
* Initial RAM contents
* Initial timing of things (how many cycles until first event)
* Indeterminate hardware behavior (double write to $2007)
If you have battery RAM, keep RNG's state in it or even just a reset counter, then no need for HW randomness
blargg wrote:
If you have battery RAM, keep RNG's state in it or even just a reset counter, then no need for HW randomness
Or flash that's writable via the NES. Flash is the only reasonable memory choice if something is going to be produced in sizable quantity. Admittedly though, a solution that would allow writing to it would need to be devised.
Tepples wrote:
I'll post a demo with source later, and I'll need people's help to test it on an NES without the PowerPak menu getting in the way.
I can help you out.
blargg wrote:
* Initial RAM contents
When I start reading this topic, I had same idea. But it is not emulated, is it?
http://pics.pineight.com/nes/pretendo-0.01.zipDoes it have the same 4-digit number every time?
The initial RAM content will vary from NES to NES, but will be likely the same at power up on the same console.
Denine:Tepples
0:1
So, RAM viewer in FCEUX just shows 00's and FF's?
At any rate, this may be very useful information, thanks!
EDIT:
Bregalad wrote:
The initial RAM content will vary from NES to NES, but will be likely the same at power up on the same console.
yeahh... So player need to reset the game to have different initial value.
Yes but then I think a soft reset is assimilable to a "button press".
Bregalad wrote:
The initial RAM content will vary from NES to NES, but will be likely the same at power up on the same console.
Are you sure? The whole reason RAM is garbage on start up is because the values aren't stable, resulting in pretty much the equivalent to random. Otherwise RAM would always be filled with 00 or FF at startup, since all cells would be probably stable to the same value.
(there's an exception regarding leaving a value in RAM for
really long periods of time can actually affect the value on power-on, but I doubt there's any such place in the NES' 2KB of RAM =P)
eric_j_ in #nesdev tried power cycles, waiting a few seconds after each, and got CF84, 20A7, 3EAE, 4DA1, E72E, 4EE8, FE6A
He noticed that the third digit was far more likely to be even than odd, and I have no idea why that is.
Bregalad wrote:
The initial RAM content will vary from NES to NES, but will be likely the same at power up on the same console.
I don't find this is true, exactly. The same console is subject to random static/capacitance/etc. Individual bits have a tendency to go one way or the other on startup, but there's plenty of uncontrollable environmental factors that can sway them one way or another.
Denine wrote:
blargg wrote:
* Initial RAM contents
When I start reading this topic, I had same idea. But it is not emulated, is it?
You're suggesting that we not program things that depend on things not emulated? Chicken-and-egg situation there. By relying on unemulated features, we give incentive to emulator authors to emulate these things.
blargg wrote:
Denine wrote:
blargg wrote:
* Initial RAM contents
When I start reading this topic, I had same idea. But it is not emulated, is it?
You're suggesting that we not program things that depend on things not emulated? Chicken-and-egg situation there. By relying on unemulated features, we give incentive to emulator authors to emulate these things.
Agreed, I am mystified when this backwards logic is used...
So it looks like you already got your data, but more data is always better
AC92, 0D5F, CC4B, D600, 66C1, 8C67, 3460, 2DCC, 56EA, 726C, E0BC, CB09, F292, B78F, C769, 779A, 04A4, 0C9E, B6F4, 4988, 1955, ACFC, 0318, 0C43...
Those were all from power on/power cycling. I didn't wait a few seconds like eric did....
A few from reset if you're curious: 5969, 5211, 2CE2, 7E96, F3A2, 0DDB, 6CCD, D841, 085E, 9621, C5EA, 1C17, 9308, F903, 0291, 060F, 40F8, B553, D89A, 08CA, 9CB3.
Thanks. So we appear to have something usable as a hardware RNG, at least at power-on. Now all I need are more puns on "Nintendo".
tepples wrote:
Now all I need are more puns on "Nintendo".
No, thanks.
tepples wrote:
Thanks. So we appear to have something usable as a hardware RNG, at least at power-on. Now all I need are more puns on "Nintendo".
What I do on the Mega Drive is take several samples from RAM scattered around (won't waste time reading all RAM!) and add them, gives a good enough value for a seed. Then add it to whatever value is in the seed variable (which is already random anyway). I imagine this should work for the NES too.
On reset the values of RAM aren't random anymore, although you still are unlikely to know what was going on when the system was reset so for all effects and purposes it's the same - and since we add to whatever value was in the seed before, it will still have the random factor from the initial boot up.
The Mega Drive has the added randomness factor that the HV counter (the position of the TV beam) can start at a completely different place each time, so I add that into the mix too. Does the NES have something similar?
(and yes, I'm aware that adding many random sources isn't always a good idea - if the sources are completely different and the output results can't have repeats (e.g. an addition will always yield an unique result for each possible value) this shouldn't be an issue)
I'll say it again - the content of RAM is NOT random :
http://wiki.nesdev.com/w/index.php/CPU_power_up_stateNesdev Wiki wrote:
All internal memory ($0000-$07FF) was consistently set to $ff except for a few bytes, which probably vary from console to console:
$0008=$F7
$0009=$EF
$000a=$DF
$000f=$BF
Against how many consoles was that wiki page tested? Besides, this technique relies on "analog effects" of bus conflicts in the PPU.
tepples wrote:
Against how many consoles was that wiki page tested?
Still would mean it isn't safe. Though also you'd need to ask for the flashcart that was used to test - unless it was something that only showed the program itself and nothing else (i.e. as if it was a normal cartridge with pure ROM, no firmware at all), any initialization-time testing goes out of the window =/
Also Nintendo was trying to make hardware as cheap as possible, if they had used some RAM that was that much stable, wouldn't everybody be using RAM that is cleared on power up these days? =X
PS: I notice a really curious pattern in the values that are the exception to the rule:
$08 ... 11110111
$09 ... 11101111
$0A ... 11011111
$0F ... 10111111
What's with that 0? o_O;
I think a very close approach to the transistors that makes the SRAM cell only could explain the power up state, and why there is this strange pattern.
Since a SRAM cell is basically a positive feedback loop, only the dimensions of the transistors and parasitic resistors will actually determine if the loop goes one way or the other (I guess).
Sik wrote:
if they had used some RAM that was that much stable, wouldn't everybody be using RAM that is cleared on power up these days?
I guess that even though RAM isn't 100% stable, bits have a tendency to go one way or the other, which results in poor randomness.
Most bits in SRAM are at 1 on power up
Sik wrote:
if they had used some RAM that was that much stable, wouldn't everybody be using RAM that is cleared on power up these days? =X
"Guarantee of cleared on power-up" is not the strict opposite of "Powers up with a different value each time"
My take? The only variables you can control in an already-assembled NES that would affect how the RAM would be filled at power up are 1-how Vcc rises when you turn it on, and 2- what temperature the RAM is. Given the way the power switch is wired, 1 is fully predictable. (charge a 100uF capacitor through a 7805 from a 2200uF capacitor)
That said, some
really old computers did require that the DRAM boot up with a specific contents.
Many emulators will not randomize the RAM, and the microphone is not always available, but I might call a random number generator several times per frame until a button pushed, but also using the initial contents of RAM and microphone, to do random numbers generation; it works very well even in emulator but should work on real hardware too, a bit better, and perhaps even a bit more better on the RF Famicom. (This is what I have used, with ARCFOUR as the random number generator.)
zzo38 wrote:
Many emulators will not randomize the RAM,
In 2013? You might be right, but I thought (and hoped) that modern emulators had gotten past such trivial, and easily fixable things. I wouldn't use an emulator that doesn't randomize RAM, because it's very likely to emulate most other things inaccurately too.
nitro2k01 wrote:
zzo38 wrote:
Many emulators will not randomize the RAM,
In 2013? You might be right, but I thought (and hoped) that modern emulators had gotten past such trivial, and easily fixable things. I wouldn't use an emulator that doesn't randomize RAM, because it's very likely to emulate most other things inaccurately too.
Randomizing and initializing are two different things though. Even the real system isn't random. When it comes to emulators, I know FCEUX initializes RAM to a pattern of $00 and $FF, Nestopia initializes to some other pattern (including at least $FF, possibly based on
these results) and Nintendulator initializes to 0.
A lot of emulator authors are trying to serve the TAS crowd, who want a defined state of the machine at power-on so that the movie will sync.
nitro2k01 wrote:
zzo38 wrote:
Many emulators will not randomize the RAM,
In 2013? You might be right, but I thought (and hoped) that modern emulators had gotten past such trivial, and easily fixable things. I wouldn't use an emulator that doesn't randomize RAM, because it's very likely to emulate most other things inaccurately too.
Care to share an algorithm that accurately emulates the power-up state of the RAM in a NES of your choosing? I've got to be able to write my own tests that your algorithm is able to fool into thinking it's on a NES.
nitro2k01 wrote:
I wouldn't use an emulator that doesn't randomize RAM, because it's very likely to emulate most other things inaccurately too.
There's no advantage to randomizing RAM for the vast majority of users (i.e. anybody who isn't using it to develop NES software).
For developers, it's
extremely trivial to initialize the NES RAM on startup. In the rare case where this is not appropriate for your software, randomizing the RAM on startup is still not a very effective tool for finding problems. A much better thing to do is to use a R/W access log to check what you have and have not initialized, and check for reads that occur before any writes to a location. So... in my opinion even for the developer the use of a randomized RAM feature is kind of pitiful.
Really all it does is randomize the behaviour of uninitialized variable bugs. I don't think that's particularly helpful, especially if you have a bug that's caused by a very specific byte value in RAM. Good luck reproducing that one.
How could this possibly be a make-or-break feature for your choice of emulator?
Edit: BTW, with a few years hindsight after having implemented memory a randomization option in FCEUX, I still don't find it useful for developing my own software, but it has been extremely useful for finding software that does not initialize RAM. I have very easily and casually found many games that fail to do it without effort, just because of having random RAM. So, not directly helpful for me, but when testing the work of new NES programmers especially it has been quite useful. Still not make-or-break, IMO, but it's been even nicer than expected as a feature.
tepples wrote:
A lot of emulator authors are trying to serve the TAS crowd, who want a defined state of the machine at power-on so that the movie will sync.
Perhaps the playback file should have optional RAM initialization block? I don't know if that can sometimes be considered as cheating?
Call a "RAM initialization block" what it is: a save state. Yes, that is considered cheating in a TAS, as it isn't something the player has control over from the exterior of the machine.
A RAM initialization block (and starting the NES up with known timing synchronizations where they can vary) is a necessary evil for almost all TAS plays to work, otherwise games can respond unpredictably to the same sequence of presses. One can look at this in a charitable way: that TAS was possible when the NES powered up that particular way. Perhaps to be more realistic they would choose a starting state that a NES was actually observed to start up into, rather than RAM cleared to zero or whatever they use.
tepples wrote:
Call a "RAM initialization block" what it is: a save state.
An entire save state, though, also contains the CPU flags and registers (such as the program counter), while TAS always will start from reset, instead. So it is like a partial save state, I guess.
But not all games initialize variables on reset (i.e. only power on), and many of those do the check by looking at some value in RAM, you could easily force a predefined status with those variables to give you an unfair advantage (e.g. to enable cheats and such).
The whole point of a TAS is that it can be recreated on stock real hardware.
TAS is about something that could be done in real-time if one were superhuman. We could put the game in, power up a NES, then play it in an unbelievable way, all through the controller.
Since we aren't superhuman, we use tools to give us those powers as far as the NES and game are concerned. Our tools essentially allow time travel. We can stop time and think about the next buttons to press/release. We can also let time go forward, see what would happen, then go back and use that information in choosing what to press. We can also of course go back and redo something that we realize was an error.
So, to make a TAS, we put the game in, power up the NES, freeze time, make a note of the entire state of the NES, then construct our controller states while we run the NES forward and backward. When we're finally done, we rewind time back to the initial power-up state and play our TAS movie in real-time while everyone enjoys it. If someone wants to see it again, they can go back in time to this NES in its same initial state and replay the TAS.
Since this requires an actual time machine, we can approximate stopping time by stopping the NES clock or something similar, and approximate going back in time by restoring the same initial state to the NES before replaying the TAS. Rather than leave the NES on while we make the TAS, we might turn it off and then restore the state when we want to play it back for the first time. These, like the TAS tools, we are overcoming our own limitations when restoring the initial state before playback, not altering the essential TAS process.
Thus, I don't see the initial NES state issue as being a violation of TAS at all. It's still turning on a NES and feeding it just a series of button presses, created with the assistance of tools, that result in an unbelievable play.
I meant that it should be theoretically possible to do it on stock real hardware as-is =P Of course in practice you'll need some sort of superhuman for that, though I believe somebody was making a TAS player with an Arduino that'd just press buttons on the controller.
Sik wrote:
I meant that it should be theoretically possible to do it on stock real hardware as-is =P Of course in practice you'll need some sort of superhuman for that, though I believe somebody was making a TAS player with an Arduino that'd just press buttons on the controller.
Since it matter the initial RAM, then to do that, would require first you put one cartridge which initialize the RAM, and then jumps to RAM and then you remove the ROM cartridge and insert a different one, and then push RESET. Doing this requires that the RAM contains a machine code for a loop to please wait forever, so it cannot be all zero.
What about holding Reset while swapping cartridges? Reset is level sensitive; otherwise, battery-backed MMC1 games couldn't have used it for RAM protection during power off.
Just a thought, if you want some randomness at powerup, why not take advantage of the initial lack of PPU/CPU synchronization?
As we all know (
http://wiki.nesdev.com/w/index.php/PPU_frame_timing), there is a technique to get the PPU and CPU clocks aligned. Would it be possible to do that and count how many cycles/frames/etc it took for things be aligned.
This would at least give you a random value for each each of the 3 startup alignments (4 for PAL). Plus because the PPU and CPU use different dividers, most likely many more possible values.
Obviously this only works on power up, not reset, but I am thinking of this more of an initial seed of sorts.
Thoughts? Am I way off?
I did some testing today and found that OAM is a pretty good source of entropy on my NES, at least for pressing reset on it and powering it down for varying lengths of time under 15 minutes. If I can set up an automatic timer to turn it on and off for a precise amount of time over and over all day, I'll get a better idea of how good it is.
The ROM captures OAM at reset (after a 100 msec delay), prints its CRC-32 and content, then fills OAM with $FF to ensure that the next test's randomness can't be helped by this one's (this prevents it from merely acting like a pseudo RNG with the OAM storing its current state).
If you run the ROM, be sure that your cart is really running it right when the NES powers up/resets, and not after a menu of any kind, otherwise the OAM will probably have been initialized by it before this gets to look at it.
The text file tells a little more about the ROM and also has my results.
Does a consistent pattern happen from a particular OAM "seed" if the end of the mainloop is BRK and BRK loops back to mainloop?
I don't follow. Can you elaborate on the scenario you're describing?
B00daW wrote:
Does a consistent pattern happen from a particular OAM "seed" if the end of the mainloop is BRK and BRK loops back to mainloop?
PPU does not see the BRK interrupt in any way, so it doesn't affect what happens to OAM. RESET is different, because the reset signal is also connected to the PPU.
OK. Good to know. Thanks.
OAM is looking like the ideal source of power-on randomness (and fairly good reset randomness). Results of more long-term power off tests:
Code:
CRC-32 amount of time off
8C65947F ~2 days
E5106E4D 2h 13m
04079501 11m
F7400CA4 2h 6m
F36449DE 41m)
9FAB4919 2h 19m
491539D4 3h 14m
926A3C53 37m
F6508295 17h 44m
The point of the CRC-32 is just an easy way to tell whether it's powering up with the same state ever, without having to list and compare all 256 bytes of OAM.
A few more:
Code:
9FDAB13D 1h 13m
F523E092 2h 52m
96C2E0D3 7h 58m
1B2C239F 1h 23m
Is this worth refining into a reusable routine we can test on several of our NES consoles and then post to the wiki for anyone to use? It sure seems to be a great source of entropy at power.
This test waits 100 msec before reading OAM. The routine should be tested running at a more typical time, the usual 1-2 refreshes after power up, in case for whatever reason we find less entropy at that time (earlier than I've been testing at).
There's also the question of how to hash things. How many bits of entropy would typically be desired? I'm guessing just a byte, so the hash wouldn't need to be as involved as CRC-32. It should at least have a version that produces a byte, since users might try to "optimize" it down to a byte if it's more, and might break the hash and get some bits having very low entropy.
blargg wrote:
How many bits of entropy would typically be desired? I'm guessing just a byte, so the hash wouldn't need to be as involved as CRC-32.
Shuffling a deck of 52 cards with Fisher-Yates takes 226 bits at the bare minimum, and about 250 bits for a good distribution in practice. On the other hand, if the game isn't one like Freecell solitaire that needs all cards visible from frame one, it could use "lazy shuffling" where the Fisher-Yates routine hits the RNG only when the user requests that a card become visible. Klondike solitaire, for example, can get by with about 56 bits at power on: seven for the face-up card at the top of each fan on the tableau and three for cards pulled from stock to waste. Blackjack and Texas Hold'em poker likewise rarely deal more than one or two cards at a time. These bits could be added from sub-frame keypress timing, possibly gathered through DMC IRQ-triggered controller reading.
Quote:
It should at least have a version that produces a byte, since users might try to "optimize" it down to a byte if it's more, and might break the hash and get some bits having very low entropy.
Then run CRC-8 on the final result.
Here's a first cut of an 8-bit OAM entropy routine, using CRC-8 as the hash. I've run it through a test that ensures that it's really reading all 256 bytes of OAM and incorporating each into the final value. The test ROM JSRs to it first thing, before
any other init code, and it works fine, so there's little restriction on when it's called in init code. It just prints the entropy. The routine uses temp, a variable somewhere in RAM.
Code:
; In: PPU rendering disabled, OAM uninitialized
; Out: A=8 bits of entropy
; Preserved: Y
get_entropy_oam:
ldx #0
@next: stx $2003
eor $2004
sta temp
asl
bcc :+
eor #$07
: eor temp
asl
bcc :+
eor #$07
: eor temp
inx
bne @next
rts
Since the last post, I became aware of
Who Moved My Cheese? and its parodies by Mason Brown, Stilton Jarlsberg, Ilene Hochberg, and Deepak Malhotra. At one point, I realized that one of the species in the
Cheese books was the same thing as a species from the first voyage in
Gulliver's Travels. I briefly considered writing a
Cheese/Travels crossover fic, and during my research for this, I became aware of
something else that rhymes with Nintendo. So for the record I'll update my logo joke ROM to include two more possibilities. Modifying the included source code to read $2004 instead of $2007 is an exercise for the reader.
http://pics.pineight.com/nes/pretendo-0.02.zipThis leaves the Freecell problem, with a buttload of entropy needed up front. I've got a bunch of
cards, and they need to be
shuffled face up. Can oam_entropy.nes run its entropy gatherer more than once per reset? Does it work on models whose $2004 readback differs, such as the Famicom?
tepples wrote:
This leaves the Freecell problem, with a buttload of entropy needed up front. I've got a bunch of
cards, and they need
shuffled face upI have wanted something like this and thought of using a variant of ARCFOUR (which is shuffling, already) where the modulo amount is different than 256 (and may vary; due to how modulo is used in ARCFOUR, you don't need to use an actual modulo and just a compare is good enough), but I don't know how well this will work.
tepples wrote:
This leaves the Freecell problem, with a buttload of entropy needed up front. I've got a bunch of
cards, and they need
shuffled face up.
The Windows 95 version of FreeCell got away with
fifteen bits of entropy.