It is currently Mon Sep 24, 2018 11:44 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 58 posts ]  Go to page Previous  1, 2, 3, 4
Author Message
PostPosted: Tue Mar 19, 2013 2:51 pm 
Offline

Joined: Tue Mar 08, 2011 9:45 am
Posts: 64
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?


Top
 Profile  
 
PostPosted: Tue Mar 19, 2013 9:17 pm 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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.


Attachments:
oam_at_reset.txt [74.13 KiB]
Downloaded 130 times
oam_at_reset.nes [40.02 KiB]
Downloaded 105 times
Top
 Profile  
 
PostPosted: Wed Mar 20, 2013 2:19 pm 
Offline
User avatar

Joined: Thu Jan 03, 2008 1:48 pm
Posts: 568
Does a consistent pattern happen from a particular OAM "seed" if the end of the mainloop is BRK and BRK loops back to mainloop?


Top
 Profile  
 
PostPosted: Wed Mar 20, 2013 6:12 pm 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
I don't follow. Can you elaborate on the scenario you're describing?


Top
 Profile  
 
PostPosted: Thu Mar 21, 2013 5:49 am 
Offline
User avatar

Joined: Mon Jan 03, 2005 10:36 am
Posts: 3127
Location: Tampere, Finland
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.

_________________
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi


Top
 Profile  
 
PostPosted: Thu Mar 21, 2013 7:48 am 
Offline
User avatar

Joined: Thu Jan 03, 2008 1:48 pm
Posts: 568
OK. Good to know. Thanks.


Top
 Profile  
 
PostPosted: Sun Mar 24, 2013 3:36 pm 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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.


Top
 Profile  
 
PostPosted: Mon Mar 25, 2013 9:56 pm 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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.


Top
 Profile  
 
PostPosted: Tue Mar 26, 2013 5:38 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20573
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Tue Mar 26, 2013 5:53 pm 
Offline
User avatar

Joined: Mon Sep 27, 2004 8:33 am
Posts: 3715
Location: Central Texas, USA
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


Attachments:
oam_entropy.nes [40.02 KiB]
Downloaded 104 times
Top
 Profile  
 
PostPosted: Mon Aug 12, 2013 9:03 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20573
Location: NE Indiana, USA (NTSC)
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.zip

This 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?


Attachments:
File comment: Local mirror of Pretendo, a hardware RNG demo for NES
pretendo-0.02.zip [14.66 KiB]
Downloaded 70 times
Top
 Profile  
 
PostPosted: Mon Aug 12, 2013 11:09 am 
Offline
User avatar

Joined: Mon Feb 07, 2011 12:46 pm
Posts: 1013
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
I 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.

_________________
.


Top
 Profile  
 
PostPosted: Mon Aug 12, 2013 1:20 pm 
Offline

Joined: Mon Apr 01, 2013 11:17 pm
Posts: 437
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 58 posts ]  Go to page Previous  1, 2, 3, 4

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group