Submission #3894: FractalFusion's GBC Pokémon: Yellow Version "arbitrary code execution" in 03:14.15

Game Boy Color
(Submitted: Pokémon Yellow)
arbitrary code execution
(Submitted: Executes Arbitrary Code)
VBA-rr v23.5
11596
59.7275005696058
3141
Unknown
Submitted by FractalFusion on 3/14/2013 7:14 AM
Submission Comments
All your base are belong to pi.
Download package (C++ input parser and script file): http://tasvideos-moviefiles.googlecode.com/files/piscript.zip
Information that is even more technical than what is covered here: Forum/Posts/342003

Goals

  • Pi
  • Pi
  • Pi

About the TAS

Well, this TAS is a bit different. Instead of ponies, you get pi.

What in the name of pi is going on

To hijack program control, you need two things:
  • A way to divert the program counter (PC) into RAM.
  • A way to write the right program.
Conventional thinking (such as in p4wn3r's 1:09.63 TAS) has shown that the address D36D-D36E is a well-used gateway to send the PC into RAM. Just put any 16-bit number there (little-endian) and the PC will jump to whatever it says when you close the menu. Furthermore, using memory-manipulation glitches such as switching Pokemon beyond the 6th position, and switching and tossing glitched items, you can pretty much write whatever you want from D16A onward. And how do you switch Pokemon beyond the 6th position, if such a thing is even imaginable? Just do a reset at the right time while saving and it will overwrite the Pokemon counter so the game thinks you have 255 Pokemon.
I inject the following sequence into D366 (don't ask): 22 00 76 00 F0 F5 D4 50 D3
Provided that the bytes from D350 to D365 are all 00 (which they are), these 9 bytes will magically hijack the GB and give you complete control of everything you ever wanted, only limited by the GB's hardware. Other sequences including shorter ones exist but I chose this sequence to be as fast as possible. To help out, the rival is given a completely illogical name.
Once the sequence is planted, I close the menu. The game reads D350 off the gateway address and thinks that it is a valid ROM address and so jumps there. The sequence and all future programs are craftily hacked together in a way that is hard to describe casually, so I'll just say this: given enough room (which I have more than enough of), you can write a very simple RAM-writing program. Congrats, you can now write whatever you want.
The payload (final program), which is only 152 bytes long, is a simple VRAM manipulator. It starts out by writing into the tile bank at positions F3-F7 the 8x8 tiles for pi, pi upside down, decimal point, zero, and one, where the last 3 are in Pokemon font (they were somehow erased after leaving the menu; none of the other digits were harmed). The program then enters an input-interactive state where you can feed it key input which can change the tile map. For this TAS, visible tilemap is practially divided into two spaces: topspace (top 12 rows) and bottomspace (bottom 6 rows). The two columns on both sides are unusable. For technical reasons, the bottomspace effectively extends below the bottom of the screen by two rows.
It works somewhat like this (0x means hexadecimal):
  • Feeding it a number from 0x00 to 0xED writes to a cache (at D600) representing the bottomspace (8 rows by 16 columns). Each number writes the tile for either pi or pi upside down in the cache at a given position. The cache exists in order to sync the bottomspace input. To perform a do-nothing-visible action, feed it the number 0xED. It writes off the bottom of the screen.
  • Feeding it the number 0xEE dumps the cache into bottomspace and clears it with the all-black tile.
  • Feeding it the number 0xEF ends the program. It fakes a GB crash and sends itself into an infinite loop.
  • Feeding it a number from 0xF0 to 0xFF writes directly to topspace (12 rows by 16 columns). Each number writes its own value (tile values F5-FF which are decimal point and digits) to the first available position in topspace. It writes serially (left to right, then top to bottom).
There is no guarantee that VRAM writing occurs in a safe (to a real GB) manner; it does not check for status of FF40-FF41 (for reference, pages 51-53 of http://marc.rawer.de/Gameboy/Docs/GBCPUman.pdf ).
Anyway, scripting VRAM to do what I want is a bit too hard to do entirely with manual hex-editing, so I wrote a simple C++ parser that converts ANSI (ASCII) into input. This allows me to use a text editor instead, and organize the script using characters that the parser ignores.

About the script used

I did my best to sync the "actions" of the tiles with the background music. First, note that dumping cache to bottomspace and writing directly to topspace cannot occur on the same frame, so they must be at least one frame apart.
Second, placing the frame on which the tile appears and the frame on which the peak of a sound effect first occurs on the same frame is not guaranteed to be perceived as sync. The human brain does not work that way. From my own testing, it seems best for the frame on which the tile appears to occur 5 or 6 frames back. Results may vary by person, state of mind, and method of encoding of course.
The normal beat window is 15 frames (this is the width between the first two notes of the Pokemon music when you start in the bedroom). This means that, when syncing to a 15-frame beat, each frame is limited to dumping 14 tiles into VRAM. Some notes occur with a window of 7-8 frames; I can pull this off early on, but I decided that later on it was too much of a hassle to maintain so I ignored those notes.
I threw in a few references to pi, games, or mathematical stuff that can easily be represented by dot matrix display. Otherwise, there's not much else to talk about. For more information about technical details, see this post: Forum/Posts/342003.
Well anyway, enjoy the TAS and help yourself to some pi. It's a neat soundclip from the Hard n' Phirm song "Pi"; however, you shouldn't look for the rest of the song or its music video unless you are willing to lose a few brain cells. You can also listen to "Mathematical Pi" if you wish.
Happy Pi Day!

Nach: Accepting as improvement to existing run.
Last Edited by adelikat on 10/3/2023 2:32 AM
Page History Latest diff List referrers