Site Admin, Skilled player (1234)
Joined: 4/17/2010
Posts: 11251
Location: RU
NES games usually have the ROM size that exceeds the amount of addresses NES as a console can access. To overcome that, games divide themselves into banks and switch them, feeding these segments to the console, one at a time. Megaman has enemy behavior routines in bank 6, and level configs in bank 2 (among others). There is also NMI, an interrupt that occurs 60 times per second and does things that must occur every frame no matter what, like updating the screen, playing music, etc. It always occurs at fixed time intervals and interrupts whatever logics the game was handling. Since some of the routines that NMI calls are stored in different banks, the game has to switch them during MNI. And each time a bank is switched, its value is stored to a certain address (0x42), to be restored per request, so the game could return to its usual duties, to the point when it was interrupted. There's an object system in nearly every game, where enemies, items, characters and some events are coded so that they are instances of a special struct, with common amount of attributes (like object members in programming). Objects spawn, act and get erased. In Megaman, there's an object with ID 0xFF, it appears when the game needs to read level map, and actually construct the next set of blocks. So when it spawns, we're in bank 2 (level data), then we read some values from bank 6 (objects), and execute everything this object needs us to execute. Ingenious approach found by FinalFighter a few years ago is to make the game execute a certain amount of operations in a way that NMI catches the game right in the process of switching a bank, and between the 2 critical instructions: after it is switched, but before it is saved! I remind that NMI occurs at fixed time intervals, so it is indeed possible to alter the game execution so that NMI could occur after anything. Then the routine for object 0xFF becomes this: - Be in bank 2. - Switch to bank 6. -- NMI routines, its usual bank switching -- NMI is done, return the bank to the value stored in 0x42 -- Since we haven't had time to store 6 there yet, it still keeps 2. So we are "returning" to the wrong bank! But the game doesn't know we're at the wrong location, it keeps reading its usual data. Usual data contains pointers to addresses that contain object IDs to spawn according to current map location. This is where miracles start (you thought false bank switching was one? more to come!) What usually points to new object ID when we're in correct bank, now contains zeros. It means, the game takes the bank's base address and uses offsets to get its data. Offset $A454 from base of bank 6 makes total sense and works, spawning correct objects. Offset $A454 from base of bank 2 is zeros. Since it's a pointer, the game looks at where it points to, and uses the value from there. Which is the game's RAM! It constantly changes and can be manipulated. It means we're now in charge of what object we will spawn! Then goes something I haven't yet understood. Something like another small offset seems to be involved, as it doesn't actually use the value at $00, but at $23. And $23 is a frame counter. Finally! We can spawn an object with arbitrary ID! Well, the game doesn't understand IDs above 0x80, converting them to ID = ID - 0x80. It's not expecting us to ever be calling objects above 0x4A to spawn, but due to a programming oversight, it's not properly prepared to them either. And that's what FinalFighter and pirohiko abuse so hard that it becomes even more broken later on. By using this broken routine, we can spawn object with ID 0x75. It would have some broken jump tables in it, jumping to code that calls score count (and eventually end the current level). But we need to go deeper! We wait for the counter to become 0x55, and execute all of the above to perfectly match, so that the game actually spawns a broken object with that ID. Since the game is unprepared, it keeps handling the object's behavior, jumping addresses taken from data tables, to execute values at those addresses as code. Since there's no real data for object 0x55, the game reads irrelevant bytes and jumps by them, thinking they are pointers. Some of them contains the value $0600. This is how we (once again) jump to RAM. But this time, we're not just reading its values, we're executing RAM as code!!! As a part of object usual behavior. The only thing left to prepare now is to setup the values at those addresses we'll be executing. Some of them are Y positions of objects, others are some sort of a timer for other objects. The brave Japanese TASers we're talking about here setup the values of these RAM addresses to do the following:
Language: asm

$0602: BVC $0651 ; jump to $0651 ; initially these bytes at $0602 are Y positions of 2 Buster bullets $0651: LDA $1F22 ; load 0x0A (value of $1F22) to A register ; initially these bytes are timers of 3 objects $0654: JMP ($0018) ; jump to the value at $18 ; surprisingly, this is address that stores controller input values ; it's set to be $C460 by pressing certain buttons ; initially, these are timers of some other objects $C460: STA $31 ; arrive here and set the current stage value to 0x0A, that we saved earlier ; this is finally some real code $C462: JMP $C10C ; jump to game end routine
Source: https://ch.nicovideo.jp/TASVideos/blomaga/ar529967
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Editor, Emulator Coder, Site Developer
Joined: 5/11/2011
Posts: 1108
Location: Murka
Interesting read. I've always wondered how developers handled non-atomic bankswitching with interrupts; looks like, in some cases, they just didn't.
Experienced player (538)
Joined: 5/12/2005
Posts: 707
This is indeed pretty interesting. I've followed FinalFighter's and pirohiko's discoveries for a long time but I can understand things a bit more better when reading this.
Player (36)
Joined: 9/11/2004
Posts: 2623
natt wrote:
Interesting read. I've always wondered how developers handled non-atomic bankswitching with interrupts; looks like, in some cases, they just didn't.
That's quite simple. Simply reverse the order of the instructions. Update to the new bank first, then if the interrupt happens it will restore to the new bank, and then you're just whoops, restoring to the same bank again. NBD.
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Site Admin, Skilled player (1234)
Joined: 4/17/2010
Posts: 11251
Location: RU
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.