bsnes-emu / bsnes

bsnes is a Super Nintendo (SNES) emulator focused on performance, features, and ease of use.
Other
1.69k stars 158 forks source link

Ultima 7 SNES RNG is predictable in emulator and not on hardware #145

Open Arya-Iwakura opened 3 years ago

Arya-Iwakura commented 3 years ago

Looking into speedrunning Ultima VII The Black Gate (SNES), I found that the game has predictable and consistent "RNG" values on both hard and soft resets when using bsnes, however, on hardware, the values are random upon boot. This causes a discrepancy of the emulated version of the game vs the hardware version.

When disassembling the code, I found the random number generator reads in the horizontal and vertical scanline registers (OPVCT and OPHCT), and this seems to be always stable in emulator but on hardware is not exactly stable, causing non-predictable randomization.

I have confirmed with two others who were able to also show this was the case on their systems to ensure it was not simply my hardware causing issues.

near-san commented 3 years ago

There's two non-deterministic behaviors to OPHCT.

  1. after a soft-reset, sometimes Hclock=186 (OPHCT~=Hclock>>2), and sometimes Hclock=188. On some SNES consoles, it's always H=186. On others, it's one or the other, randomly. I am not sure about after a power-on event, I never had an easy way to check as any means I've ever had to test code (copiers, flash carts, 21fx) required startup code that took me too far from reset to tell what value the system started at.

  2. right near the long-dots that exist on nearly every scanline, roughly around Hdot=322 and Hdot=326, the long dot start position tends to fluctuate 2 Hclocks to the left or right each time you latch. If you wrote a test that kept latching OPHCT at the exact same cycle, you would see the Hdot value returned fluctuate around the two long dots. For all other times, the latched value is 100% stable and predictable.

I don't emulate either because aside from the option to randomize memory at startup, bsnes and higan are deterministic, ironically for the sake of TASing. Deterministic TASing on real hardware isn't possible due to the CPU<>APU oscillator fluctuations that exist on real hardware. Also to emulate the first one, I'd have to know why some systems fluctuate on reset and others don't. I didn't test on enough systems to deduce a pattern for that. And I simply don't know what happens at power-on. Someone else would have to test that who could latch OPHCT immediately as the first instruction in the reset vector, and then staggered by a half-dot (to deduce the exact Hclock value) as a second, separate test. For the second behavior ... if someone were to create a probability model of the long dot being 2 Hclocks behind, centered, or 2 Hclocks ahead, we could model that into the emulator.

Neither of these two behaviors seem likely to affect whatever Ultima VII is doing. I don't believe there is another non-determinism in OPxCT. In my experience, other than the two above, the values are extremely stable and predictable. Pretty much all of my test_* ROMs relied on this, and is the core basis for all of my cycle-accurate timings. I would suggest you to more thoroughly evaluate your theory, and provide stronger evidence. I'll never rule out that I missed something, but it's fairly unlikely in this case.

Arya-Iwakura commented 3 years ago

Thank for for the reply! I will explain in detail here, as it was fairly straight forward to find this in this particular game.

While testing the game, I noted there are random price values that are assigned to items at the start of every game. Wondering why this was, I quickly tracked it to a 2 byte value at ram 001CF2. This value is a sort of "seed" value and never changes throughout the rest of the game after the main menu appears. You can hand edit this value to observe the prices changing. Debugging what writes to that value reveals that it is stored from the accumulator via the below opperations:

Breakpoint 1 hit (2). 9fb7cd jsl $80fa1e [80fa1e] A:0402 X:0000 Y:7f00 S:1ffa D:0000 DB:80 nvmxdizc V: 66 H:182 F:27 80fa1e jsr $fb01 [80fb01] A:0402 X:0000 Y:7f00 S:1ff7 D:0000 DB:80 nvmxdizc V: 66 H:195 F:27 80fb01 php A:0402 X:0000 Y:7f00 S:1ff5 D:0000 DB:80 nvmxdizc V: 66 H:205 F:27 80fb02 rep #$30 A:0402 X:0000 Y:7f00 S:1ff4 D:0000 DB:80 nvmxdizc V: 66 H:210 F:27 80fb04 lda $022e [80022e] A:0402 X:0000 Y:7f00 S:1ff4 D:0000 DB:80 nvmxdizc V: 66 H:215 F:27 80fb07 pha A:5955 X:0000 Y:7f00 S:1ff4 D:0000 DB:80 nvmxdizc V: 66 H:223 F:27 80fb08 asl a A:5955 X:0000 Y:7f00 S:1ff2 D:0000 DB:80 nvmxdizc V: 66 H:230 F:27 80fb09 asl a A:b2aa X:0000 Y:7f00 S:1ff2 D:0000 DB:80 Nvmxdizc V: 66 H:233 F:27 80fb0a and #$2000 A:6554 X:0000 Y:7f00 S:1ff2 D:0000 DB:80 nvmxdizC V: 66 H:236 F:27 80fb0d beq $fb13 [80fb13] A:2000 X:0000 Y:7f00 S:1ff2 D:0000 DB:80 nvmxdizC V: 66 H:241 F:27 80fb0f ror a A:2000 X:0000 Y:7f00 S:1ff2 D:0000 DB:80 nvmxdizC V: 66 H:244 F:27 80fb10 bmi $fb13 [80fb13] A:9000 X:0000 Y:7f00 S:1ff2 D:0000 DB:80 Nvmxdizc V: 66 H:247 F:27 80fb13 rol $022c [80022c] A:9000 X:0000 Y:7f00 S:1ff2 D:0000 DB:80 Nvmxdizc V: 66 H:251 F:27 80fb16 pla A:9000 X:0000 Y:7f00 S:1ff2 D:0000 DB:80 Nvmxdizc V: 66 H:265 F:27 80fb17 rol a A:5955 X:0000 Y:7f00 S:1ff4 D:0000 DB:80 nvmxdizc V: 66 H:274 F:27 80fb18 sta $022e [80022e] A:b2aa X:0000 Y:7f00 S:1ff4 D:0000 DB:80 Nvmxdizc V: 66 H:277 F:27 80fb1b plp A:b2aa X:0000 Y:7f00 S:1ff4 D:0000 DB:80 Nvmxdizc V: 66 H:291 F:27 80fb1c rts A:b2aa X:0000 Y:7f00 S:1ff5 D:0000 DB:80 nvmxdizc V: 66 H:298 F:27 80fa21 rtl A:b2aa X:0000 Y:7f00 S:1ff7 D:0000 DB:80 nvmxdizc V: 66 H:308 F:27 9fb7d1 and #$0038 A:b2aa X:0000 Y:7f00 S:1ffa D:0000 DB:80 nvmxdizc V: 66 H:318 F:27 9fb7d4 ora #$0100 A:0028 X:0000 Y:7f00 S:1ffa D:0000 DB:80 nvmxdizc V: 66 H:323 F:27 9fb7d7 sta $1cf2 [801cf2] A:0128 X:0000 Y:7f00 S:1ffa D:0000 DB:80 nvmxdizc V: 66 H:327 F:27 Breakpoint 0 hit (6). 9fb7d7 sta $1cf2 [801cf2] A:0128 X:0000 Y:7f00 S:1ffa D:0000 DB:80 nvmxdizc V: 66 H:331 F:27

Seeing that the accumulator value was being read in from 022E, I found that is where the RNG values for the game are stored. Curious as to how these values are stored, I breakpointed on their initilization at the start of the rom as well as any time they are written to afterwards. Here it is clear they are created from the OPVCT and OPHCT values which are 00213C and 00213D.

94ee50 lda $2137 [802137] A:d258 X:0000 Y:1880 S:1ff5 D:0000 DB:80 NvMxdIzc V:173 H: 37 F:50 94ee53 lda $213c [80213c] A:d221 X:0000 Y:1880 S:1ff5 D:0000 DB:80 nvMxdIzc V:173 H: 43 F:50 94ee56 adc $213c [80213c] A:d22a X:0000 Y:1880 S:1ff5 D:0000 DB:80 nvMxdIzc V:173 H: 49 F:50 94ee59 xba A:d254 X:0000 Y:1880 S:1ff5 D:0000 DB:80 nvMxdIzc V:173 H: 55 F:50 94ee5a lda $213d [80213d] A:54d2 X:0000 Y:1880 S:1ff5 D:0000 DB:80 NvMxdIzc V:173 H: 59 F:50 94ee5d adc $213d [80213d] A:54ad X:0000 Y:1880 S:1ff5 D:0000 DB:80 NvMxdIzc V:173 H: 65 F:50 94ee60 rep #$20 A:5459 X:0000 Y:1880 S:1ff5 D:0000 DB:80 nVMxdIzC V:173 H: 71 F:50 94ee62 sec A:5459 X:0000 Y:1880 S:1ff5 D:0000 DB:80 nVmxdIzC V:173 H: 76 F:50 94ee63 ror a A:5459 X:0000 Y:1880 S:1ff5 D:0000 DB:80 nVmxdIzC V:173 H: 79 F:50 94ee64 sta $022c [80022c] A:aa2c X:0000 Y:1880 S:1ff5 D:0000 DB:80 NVmxdIzC V:173 H: 82 F:50 94ee67 xba A:aa2c X:0000 Y:1880 S:1ff5 D:0000 DB:80 NVmxdIzC V:173 H: 90 F:50 94ee68 sta $022e [80022e] A:2caa X:0000 Y:1880 S:1ff5 D:0000 DB:80 NVmxdIzC V:173 H: 95 F:50

The initial fluctuation is as you say only off by small amounts, but it does generate different seed values on hardware vs software. Watching these values on emulator vs hardware shows the differences and you can directly see the results of the RNG generator being slightly different and causing game differences.

near-san commented 3 years ago

What's most likely happening here is the aforementioned CPU<>APU discrepancies.

On real hardware, the CPU crystal clock is ~21.47MHz (NTSC) or ~21.28MHz (PAL), and the APU ceramic clock is ~24.576MHz. These values fluctuate between different machines, based on the age of the oscillators, based on the tolerances of the oscillator types (ceramic have higher tolerances than quartz crystals), and even based on the temperature of the machine. Yes, the actual clock rates can change while a system is running.

So now imagine that Ultima VII uploads some code to the SMP. On an emulator, we set fixed and precise CPU<>APU clock frequencies, so the transfers will always take the same amount of time. Whereas on hardware it can be different each time. It's constantly fluctuating. If the counters are latched after an SMP upload, then they will be deterministic under emulation, and non-deterministic on real hardware.

If you want to account for this, then well ... good luck. The best idea I have is to have a "clock frequency offset" value with a min/max difference level, that fluctuates up or down periodically (say, once a scanline or so?) in rare cases (say, when rand(0,10000)==0 or whatever, then rand(0,1) to determine whether to decrement or increment the clock frequency.) And do this for both the CPU and SMP clocks. This would completely break TASing in the same way it isn't reliable on real hardware, so it'd have to be an option. Good chance doing this would also result in the Super Bonk desync becoming randomized as with real hardware as well.