NES infinite loops

[sburrow]

Hello everyone!

Just for reference, here is my 'main' topic:

viewtopic.php?f=1&t=8236

Anyways, something new, and not specifically related to my project alone. I'm wondering if y'all have any ideas on how to detect infinite loops on the NES.

Some background: The NES runs the CPU 100% of the time. There is no halting that I know of. When a game is done processing during a particular frame, it just runs an infinite loop until NMI hits. Sometimes a game will poll the V-SYNC flag from the PPU while waiting for NMI, sometimes a game will just do nothing at all while waiting for NMI. I suppose a game could also be waiting for Sprite 0 Hit (which it must poll for), or it could be waiting for an IRQ though that's somewhat rare I believe.

But how can I detect when it is doing this? Mainly so that I can then attempt to cut down on CPU usage. Essentially I want to find a way for my NES emulator to stop running infinite loops and instead devote that time to doing graphics or sound or whatever else needs attention. Optimization!

Some ideas:

1) I could just see if it's polling the V-sync or Sprite-0 flags concurrently. For V-sync I could just say "Ok, shut down until V-sync actually happens". For Sprite-0 I could just say, "Ok, I know when that is coming up again, shut down until that moment." That would help some games, but not all.

2) In many cases, games do something silly like:

Code: Select all

LDA #$00
.loop
BEQ loop

If that is the case, I can maybe see if the Program Counter hasn't moved much in a dozen or so cycles, and just wait until interrupt. The problem here is that sometimes games do something similar when clearing the screen:

Code: Select all

LDA #$00
.blank
STA ppu_data
BEQ .blank

That still qualifies as an infinite loop, but here it is actually doing something. I have seen many silly loops while building my emulator, things that don't make sense when just looking at it, so I cannot give any real qualifications to what loops are important and what loops are not.

3) I could pre-program for some known loops. Say, "Oh Mario does this, so I'll code for that. Zelda does this other thing, so I'll code for that too." Ugh, I don't want to program for specific games, but at the same time I might need to. I won't tell the emulator "oh this is Mario so do this" but I would say "hey Mario and other types of games do this, so watch for that". Again this could optimize some or even most games, but it feels a bit of a hack.

EDIT: Something else I just thought of: Some games like Donkey Kong uses this 'infinite loop' time to generate random numbers. So, is that something I can skip and reasonably get a 'good enough' experience?

Any other ideas? I'd love to hear them!

Thank you everyone.

Chad

[teamtempest]

I don't know anything about the NES, but as far as I can tell, you're trying to use otherwise 'dead' time to actually do something useful. Well, why do you need to do that? What's the penalty of just not doing anything?

What if you just took action to recover time only when you knew for sure you could (as in situatation #1), and just let whatever happens the rest of the time, happen?

[sburrow]

Yes that is true, I'm trying to use 'dead time' to do other things.

The reason why is because my emulator is not fast enough. Sure, on a desktop computer it's screamin' fast. But on my microcontroller its... not that fast. It is sufficient, but I would like it to be more than just sufficient.

The games that I know poll for this or that would be no more than half, probably less than half. There isn't just one 'standard'. So, although that might help some games, it would maybe make other games slower, since I would constantly be checking for this particular situation. The more "if" statements, the less optimized that idea becomes.

Good questions, thank you!

Chad

[sburrow]

An update:

I put in a 'loop detection' system into the emulator. Roughly this is how it works:

Before I jump into the CPU emulation section, I zero out some flags and save my A, X, and Y registers. While I'm in the CPU emulation section, I set flags if I read, write, or branch/jump. When I'm out of the CPU emulation section, I check to see if I read, wrote, or branch/jumped.

If I wrote, I'm not in an infinite loop. If my A, X, or Y registers have changed, I'm not in an infinite loop. If I read and did not branch/jump, then increment a read tally and zero out the branch/jump tally. If that read tally exceeds some preset number I choose (say like 4), I'm not in an infinite loop. Else if I did branch/jump, increment a branch/jump tally. If the branch/jump tally reaches 16 (arbitrary), then we are in an infinite loop. Halt the CPU until either Sprite 0 Hit, V-Sync, or an NMI/IRQ/BRK interrupt.

I did some debug cycle counting and Super Mario 1 has improved substantially! It now runs very smoothly at 30 FPS (previously only 20 FPS). Super Mario 3 does run smoothly at 20 FPS, but not good enough at 30 FPS. I would expect that because it is a more finely-tuned later game.

Well, there you have it. A good enough solution Thank you everyone.

Chad

[BigEd]

Interesting - I'd be inclined to use the new machinery to collect some execution traces (say 64 instructions or so) from various games in various states, to see what kind of code you are detecting. You might be able to refine what you're doing, or you might find something needs tweaking.

[commodorejohn]

Interesting notion - simple jump/branch loops should be easy to directly detect, as well (if a JMP points back to itself, or a branch if the branch is taken,) though I don't know how much it'd save you over the heuristic you've already established. This won't be 100% cycle-accurate as interrupt response on the real deal will finish out whatever instruction was executing when the interrupt triggered, introducing a variable delay on top of the time required for the interrupt sequence itself, but if you're tuning for performance on a microcontroller I imagine that's not your priority