rlm@608: #+title: Pokemon Yellow Total Control Hack rlm@608: #+author: Robert McIntyre rlm@608: #+email: rlm@mit.edu rlm@608: #+description: Taking over Pokemon Yellow from the inside. rlm@608: #+keywords: pokemon, pokemon yellow, rom, gameboy, assembly, hex, pointers, clojure rlm@608: #+SETUPFILE: ../../aurellem/org/setup.org rlm@608: #+INCLUDE: ../../aurellem/org/level-0.org rlm@608: #+BABEL: :exports both :noweb yes :cache no :mkdirp yes rlm@608: #+OPTIONS: num:2 rlm@608: rlm@608: rlm@609: Full Source : http://hg.bortreb.com/vba-clojure rlm@609: rlm@619: rlm@619: #+BEGIN_HTML html rlm@619:
rlm@619:

rlm@619: rlm@619:

rlm@619: #+END_HTML rlm@609: Youtube Video w/ Visual Keypresses: http://www.youtube.com/watch?v=p5T81yHkHtI rlm@619: #+BEGIN_HTML rlm@619:

rlm@619: #+END_HTML rlm@609: rlm@609: Special Thanks to: rlm@609: rlm@609: - http://tasvideos.org/2913S.html for the save corruption hack which rlm@609: is used at the start of this run. rlm@609: - http://www.everyponysings.com/ for providing the midi file I used rlm@609: to create the song at the end. rlm@609: - http://www.zophar.net/ for the terminal font. rlm@609: rlm@609: rlm@609: * Introduction rlm@609: rlm@609: Think of pokemon yellow as creating a little universe with certain rlm@609: rules. Inside that universe, you can buy items, defeat rival trainers, rlm@609: and raise your pokemon. But within that universe, you are bound by the rlm@609: rules of pokemon. You can't build new buildings, or change the music, rlm@609: or change your clothes.. There are some games (like chess), where it rlm@609: is not possible to alter the rules of the game from within the rlm@609: game. No matter what moves you make in chess, you can never change the rlm@609: rules of the game so that it becomes checkers or basketball. The point rlm@609: of this run is to show that you CAN change the rules in pokemon rlm@612: yellow. There is a certain sequence of valid actions (like walking rlm@612: from one place to another or buying items) that will allow you to rlm@612: transform pokemon yellow into Pacman, or Tetris, or Pong, or a MIDI rlm@612: player, or anything else you can imagine. rlm@609: rlm@609: * Background rlm@609: rlm@609: [[http://tasvideos.org/2913S.html][This speedrun]] by Felipe Lopes de Freitas (p4wn3r), beats pokemon rlm@609: yellow in only 1 minute and 36 seconds. It does it by corrupting the rlm@609: in-game item list so that he can advance the list past its normal rlm@609: limit of 20 items. The memory immediately after the item list includes rlm@609: the warp points for the current map, and by treating that data as rlm@609: items and switching and dropping them, he can make the door from his rlm@609: house take him directly to the end of the game. rlm@609: rlm@609: When I first saw that speedrun, I was amazed at how fast pokemon rlm@609: yellow could be beaten, and that it was possible to manipulate the rlm@611: game from the inside, using only the item list. I wondered how far I rlm@609: could extend the techniques found in p4wn3r's run. rlm@609: rlm@609: The gameboy is an 8 bit computer. That means that ultimately, anything rlm@609: that happens in pokemon is a result of the gameboy's CPU reading a rlm@609: stream of 8 bit numbers and doing whatever those numbers mean. For rlm@609: example, in the gameboy, the numbers: rlm@609: rlm@609: [62 16 37 224 47 240 37 230 15 55] rlm@609: rlm@609: mean to check which buttons are currently pressed and copy that result rlm@609: into the "A" register. With enough numbers, you can spell out an rlm@609: interactive program that reads input from the buttons and allows you rlm@609: to write any program you want to the gameboy. Once you have assembled rlm@609: such a program and forced the game to run it, you have won, since you rlm@611: can use that program to write any other program (like Tetris or rlm@611: Pacman) over pokemon yellow's code. I call a program that allows you rlm@609: to write any other program a "bootstrapping program". So, the goal is rlm@609: to somehow get a bootstrapping program into pokemon yellow and then rlm@609: force yellow to run that program instead of its own. rlm@609: rlm@609: How can we spell out such a program? Everything in the game is rlm@611: ultimately numbers, including all items, pokemon, levels, etc. In rlm@609: particular, the item list looks like: rlm@609: rlm@610: #+begin_example rlm@609: item-one-id (0-255) rlm@609: item-one-quantity (0-255) rlm@609: item-two-id (0-255) rlm@609: item-two-quantity (0-255) rlm@609: . rlm@609: . rlm@609: . rlm@610: #+end_example rlm@609: rlm@609: Let's consider the button measuring program [37 62 16 37 224 37 240 rlm@609: 37 230 15 55] from before. Interpreted as items and item quantities, it is rlm@609: rlm@610: #+begin_example rlm@609: lemonade x16 rlm@609: guard spec. x224 rlm@609: leaf stone x240 rlm@609: guard spec. x230 rlm@609: parlyz heal x55 rlm@610: #+end_example rlm@609: rlm@609: So, if we can get the right items in the right quantities, we can rlm@609: spell out a bootstrapping program. Likewise, when writing the rlm@609: bootstrapping program, we must be careful to only use numbers that are rlm@609: also valid items and quantities. This is hard because there aren't rlm@609: many different items to work with, and many machine instructions rlm@609: actually take 2 or even 3 numbers in a row, which severely restricts rlm@609: the types of items you can use. I ended up needing about 92 numbers to rlm@609: implement a bootstrap program. Half of those numbers were elaborate rlm@609: ways of doing nothing and were just there so that the entire program rlm@609: was also a valid item list. rlm@609: rlm@609: The final part of the hack is getting pokemon yellow to execute the rlm@609: new program after it has been assembled with items. Fortunately, rlm@609: pokemon keeps a number called a function pointer within easy reach of rlm@609: the corrupted item list. This function pointer is the starting point rlm@609: (address) of a program which the game runs every so often to check for rlm@611: poison and do general maintenance. By shifting an item over this rlm@609: function pointer, I can rewrite that address to point to the rlm@609: bootstrapping program, and make the game execute it. Without this rlm@609: function pointer, it would not be possible to take over the game. rlm@609: rlm@609: * The Run rlm@609: rlm@611: I start off and name my rival Lp/k. These characters will eventually be rlm@609: treated as items and shifted over the function pointer, causing it to rlm@609: execute the bootstrapping program that will soon be constructed. I rlm@609: start the run the same as p4wn3r's and restart the game while saving, rlm@609: so that the pokemon list is corrupted. By switching the 8th and 10th rlm@609: pokemon, I corrupt the item list and can now scroll down past the 20th rlm@609: item. I shift items around to increase the text speed to maximum and rlm@609: rewrite the warp point of my house to Celadon Dept. Store. (p4wn3r rlm@609: used this to go directly to the hall of fame and win the game in his rlm@609: run.) I deposit many 0x00 glitch items into the PC from my corrupted rlm@611: inventory for later use. Then, I withdraw the potion from the rlm@609: PC. This repairs my item list by overflowing the item counter from rlm@609: 0xFF back to 0x00, though the potion is obliterated in the process. I rlm@609: then take 255 glitch items with ID 0x00 from the computer into my rlm@609: personal items. rlm@609: rlm@609: Leaving my house takes me directly to Celadon Dept. store, where I rlm@609: sell two 0x00 items for 414925 each, giving myself essentially max rlm@609: money. I hit every floor of the department store, gathering the rlm@609: following items: rlm@609: rlm@609: #+begin_example rlm@609: +-------------------+----------+ rlm@609: |##| Item | Quantity | rlm@609: +--+----------------+----------+ rlm@609: |1 | TM02 | 98 | rlm@609: |2 | TM37 | 71 | rlm@609: |3 | TM05 | 1 | rlm@609: |4 | TM09 | 1 | rlm@609: |5 | burn-heal | 12 | rlm@609: |6 | ice-heal | 55 | rlm@609: |7 | parlyz-heal | 99 | rlm@609: |8 | parlyz-heal | 55 | rlm@609: |9 | TM18 | 1 | rlm@609: |10| fire-stone | 23 | rlm@609: |11| water-stone | 29 | rlm@609: |12| x-accuracy | 58 | rlm@609: |13| guard-spec | 99 | rlm@609: |14| guard-spec | 24 | rlm@609: |15| lemonade | 16 | rlm@609: |16| TM13 | 1 | rlm@609: +--+----------------+----------+ rlm@609: #+end_example rlm@609: rlm@609: After gathering these items, I deposit them in the appropriate order rlm@609: into the item PC to spell out my bootstrapping program. Writing a full rlm@609: bootstrap program in one go using only items turned out to be too rlm@609: hard, so I split the process up into three parts. The program that I rlm@609: actually construct using items is very limited. It reads only from the rlm@614: A, B, start, and select buttons, and writes 4 bits each frame starting rlm@614: at a fixed point in memory. After it writes 200 or so bytes, it jumps rlm@609: directly to what it just wrote. In my run, I use this program to write rlm@612: another bootstrapping program that can write any number of bytes to rlm@609: any location in memory, and then jump to any location in memory. This rlm@609: new program also can write 8 bits per frame by using all the rlm@609: buttons. Using this new bootstrap program, I write a final rlm@611: bootstrapping program that does everything the previous bootstrapping rlm@609: program does except it also displays the bytes it is writing to memory rlm@609: on the screen. rlm@609: rlm@611: After completing this bootstrapping program, I go to the Celadon rlm@609: mansion, because I find the metaness of that building to be rlm@609: sufficiently high to serve as an exit point for the pokemon rlm@609: universe. I corrupt my item list again by switching corrupted pokemon, rlm@611: scroll down to my rival's name and discard until it is equal to the rlm@609: address of my bootstrapping program, and then swap it with the rlm@611: function pointer. Once the menu is closed, the bootstrapping program rlm@609: takes over, and I write the payload.... rlm@609: rlm@609: * Infrastructure rlm@609: rlm@609: The entire video was completely produced by bots --- I didn't manually rlm@609: play the game at all to produce this speedrun. Here is a brief account rlm@618: of the infrastructure I built to make the video. The entire source of rlm@609: the project is available at http://hg.bortreb.com/vba-clojure rlm@609: rlm@611: The first step was to build a programmatic interface to pokemon rlm@609: yellow. So, I downloaded vba-rerecording from rlm@609: http://code.google.com/p/vba-rerecording/. After repairing their rlm@609: broken auto-tools scripts so that it would compile on GNU/Linux, I rlm@609: added a low level C interface that I could call from Java via rlm@609: JNI. This C interface gives me basic control over the emulator: I can rlm@609: step the emulator either one clock cycle or one frame, and I can get rlm@609: the contents of any memory location or register. The interface also rlm@609: allows me to freeze the state of the emulator, save it to a Java rlm@609: object, and reload that state again at any time. rlm@609: rlm@609: I built a layer of [[http://clojure.org/][clojure]] code on top of the JNI bindings to get an rlm@609: entirely functional interface to vba-rerecording. This interface rlm@609: treats state of the emulator as an immutable object, and allows me to rlm@609: do everything I could do with the lower level C interface in a rlm@609: functional manner. Using this functional code, I wrote search programs rlm@609: that take a particular game-state and try out different combinations rlm@611: of button presses to get any desired effect. By combining different rlm@609: styles of search with different initial conditions, I created high rlm@609: level functions that could each accomplish a certain general task, rlm@609: like walking and buying items. For example, here is some actual code: rlm@609: rlm@609: #+begin_src clojure rlm@609: (defn-memo viridian-store->oaks-lab rlm@609: ([] (viridian-store->oaks-lab rlm@609: (get-oaks-parcel))) rlm@609: ([script] rlm@609: (->> script rlm@609: (walk [↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ rlm@609: ← ← ← ← ← ← ← ← ← rlm@609: ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ rlm@609: ← ← rlm@609: ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ rlm@609: ↓ ↓ ↓ ↓ ↓ ↓ ↓ rlm@609: → → → → → → → → rlm@609: ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ rlm@609: ← ← ← ← ← rlm@609: ↓ ↓ ↓ ↓ rlm@609: ]) rlm@609: (walk-thru-grass rlm@609: [↓ ↓ ↓ ↓ ↓ ↓ ↓]) rlm@609: (walk [↓ ↓ ← ↓ ↓ ↓ ← rlm@609: ↓ ↓ ↓ ↓ ↓ ↓ rlm@609: → → → ↑]) rlm@609: rlm@609: (do-nothing 1)))) rlm@609: #+end_src rlm@609: rlm@609: This script walks from the Viridian City pokemon store to Oak's rlm@609: Lab in the most efficient way possible. The walk-thru-grass function rlm@611: guarantees that no wild battles will happen by manipulating the game's rlm@609: random number generator. rlm@609: rlm@609: #+begin_src clojure rlm@609: (defn-memo hacking-10 rlm@609: ([] (hacking-10 (hacking-9))) rlm@609: ([script] rlm@609: (->> script rlm@609: begin-deposit rlm@609: (deposit-held-item 17 230) rlm@609: (deposit-held-item-named :parlyz-heal 55) rlm@609: (deposit-held-item 14 178) rlm@609: (deposit-held-item-named :water-stone 29) rlm@609: (deposit-held-item 14 32) rlm@609: (deposit-held-item-named :TM18 1) rlm@609: (deposit-held-item 13 1) rlm@609: (deposit-held-item 13 191) rlm@609: (deposit-held-item-named :TM02 98) rlm@609: (deposit-held-item-named :TM09 1) rlm@609: close-menu))) rlm@609: #+end_src rlm@609: rlm@609: This script calculates the fastest sequence of key presses to deposit rlm@611: the requested items into a PC, assuming that the character starts out rlm@609: in front of a computer. rlm@609: rlm@611: I also wrote functions that could grovel through the game's memory and rlm@611: present the internal data structures in usable ways. For example, the rlm@609: function =print-inventory= returns the current inventory in a human rlm@609: readable format. rlm@609: rlm@612: #+begin_src clojure :results output :exports both rlm@609: (com.aurellem.gb.items/print-inventory) rlm@609: #+end_src rlm@609: rlm@609: #+results: rlm@609: #+begin_example rlm@609: +-------------------+----------+ rlm@609: |##| Item | Quantity | rlm@609: +--+----------------+----------+ rlm@609: |0 | poke-ball | 14 | rlm@609: |1 | TM28 | 1 | rlm@609: |2 | TM11 | 1 | rlm@609: |3 | TM45 | 1 | rlm@609: |4 | nugget | 1 | rlm@609: |5 | s.s.ticket | 1 | rlm@609: |6 | helix-fossil | 1 | rlm@609: |7 | moon-stone | 1 | rlm@609: +--+----------------+----------+ rlm@609: rlm@609: #+end_example rlm@609: rlm@609: rlm@609: Armed with these functions, I constructed a bootstrapping program that rlm@611: could be expressed as items. This is particularly hard, since many rlm@609: useful opcodes do not correspond any item, and the item quantities rlm@609: must all be less than 99. rlm@609: rlm@609: Here is the first bootstrapping program in all its glory. rlm@609: rlm@609: #+begin_src clojure rlm@609: (defn pc-item-writer-program rlm@609: [] rlm@609: (let [;;limit 75 rlm@609: limit 201 ;; (item-hack 201 is the smallest I could make this.) rlm@609: [target-high target-low] (disect-bytes-2 pokemon-list-start)] rlm@609: (flatten rlm@609: [[0x00 ;; (item-hack) no-op (can't buy repel (1E) at celadon) rlm@609: 0x1E ;; load limit into E rlm@609: limit rlm@609: 0x3F ;; (item-hack) set carry flag no-op rlm@609: rlm@609: ;; load 2 into C. rlm@609: 0x0E ;; C == 1 means input-first nybble rlm@609: 0x04 ;; C == 0 means input-second nybble rlm@609: rlm@609: 0x21 ;; load target into HL rlm@609: target-low rlm@609: target-high rlm@609: 0x37 ;; (item-hack) set carry flag no-op rlm@609: rlm@609: 0x00 ;; (item-hack) no-op rlm@609: 0x37 ;; (item-hack) set carry flag no-op rlm@609: rlm@609: 0x00 ;; (item-hack) no-op rlm@609: 0xF3 ;; disable interrupts rlm@609: ;; Input Section rlm@609: rlm@609: 0x3E ;; load 0x20 into A, to measure buttons rlm@609: 0x10 rlm@609: rlm@609: 0x00 ;; (item-hack) no-op rlm@609: 0xE0 ;; load A into [FF00] rlm@609: 0x00 rlm@609: rlm@609: 0xF0 ;; load 0xFF00 into A to get rlm@609: 0x00 ;; button presses rlm@609: rlm@609: 0xE6 rlm@609: 0x0F ;; select bottom four bits of A rlm@609: 0x37 ;; (item-hack) set carry flag no-op rlm@609: rlm@609: 0x00 ;; (item-hack) no-op rlm@609: 0xB8 ;; see if input is different (CP A B) rlm@609: rlm@609: 0x00 ;; (item-hack) (INC SP) rlm@609: 0x28 ;; repeat above steps if input is not different rlm@609: ;; (jump relative backwards if B != A) rlm@609: 0xED ;; (literal -19) (item-hack) -19 == egg bomb (TM37) rlm@609: rlm@609: 0x47 ;; load A into B rlm@609: rlm@609: 0x0D ;; dec C rlm@609: 0x37 ;; (item-hack) set-carry flag rlm@609: ;; branch based on C: rlm@609: 0x20 ;; JR NZ rlm@609: 23 ;; skip "input second nybble" and "jump to target" below rlm@609: rlm@609: ;; input second nybble rlm@609: rlm@609: 0x0C ;; inc C rlm@609: 0x0C ;; inc C rlm@609: rlm@609: 0x00 ;; (item-hack) no-op rlm@609: 0xE6 ;; select bottom bits rlm@609: 0x0F rlm@609: 0x37 ;; (item-hack) set-carry flag no-op rlm@609: rlm@609: 0x00 ;; (item-hack) no-op rlm@609: 0xB2 ;; (OR A D) -> A rlm@609: rlm@609: 0x22 ;; (do (A -> (HL)) (INC HL)) rlm@609: rlm@609: 0x1D ;; (DEC E) rlm@609: rlm@609: 0x00 ;; (item-hack) rlm@609: 0x20 ;; jump back to input section if not done rlm@609: 0xDA ;; literal -36 == TM 18 (counter) rlm@609: 0x01 ;; (item-hack) set BC to literal (no-op) rlm@609: rlm@609: ;; jump to target rlm@609: 0x00 ;; (item-hack) these two bytes can be anything. rlm@609: 0x01 rlm@609: rlm@609: 0x00 ;; (item-hack) no-op rlm@609: 0xBF ;; (CP A A) ensures Z rlm@609: rlm@609: 0xCA ;; (item-hack) jump if Z rlm@609: target-low rlm@609: target-high rlm@609: 0x01 ;; (item-hack) will never be reached. rlm@609: rlm@609: ;; input first nybble rlm@609: 0x00 rlm@609: 0xCB rlm@609: 0x37 ;; swap nybbles on A rlm@609: rlm@609: 0x57 ;; A -> D rlm@609: rlm@609: 0x37 ;; (item-hack) set carry flag no-op rlm@609: 0x18 ;; relative jump backwards rlm@609: 0xCD ;; literal -51 == TM05; go back to input section rlm@609: 0x01 ;; (item-hack) will never reach this instruction rlm@609: rlm@609: ] rlm@609: (repeat 8 [0x00 0x01]);; these can be anything rlm@609: rlm@609: [;; jump to actual program rlm@609: 0x00 rlm@609: 0x37 ;; (item-hack) set carry flag no-op rlm@609: rlm@609: 0x2E ;; 0x3A -> L rlm@609: 0x3A rlm@609: rlm@609: rlm@609: 0x00 ;; (item-hack) no-op rlm@609: 0x26 ;; 0xD5 -> L rlm@609: 0xD5 rlm@609: 0x01 ;; (item-hack) set-carry BC rlm@609: rlm@609: 0x00 ;; (item-hack) these can be anything rlm@609: 0x01 rlm@609: rlm@609: 0x00 rlm@609: 0xE9 ;; jump to (HL) rlm@609: ]]))) rlm@609: rlm@609: #+end_src rlm@609: rlm@609: I use the glitch items 0x00 and 0xFF to great effect in my run. 0x00 rlm@612: sells for almost half of maximum money --- I use just 3 of them to rlm@611: finance the purchase of all the other items I need. 0x00 is also a rlm@609: NO-OP in the gameboy's machine language, which means that I can stick rlm@618: them anywhere where I need to break up an otherwise illegal pair of rlm@609: opcodes. 0xFF is also extremely useful because it is the end-of-list rlm@609: sentinel. Normally, the game will "compact" your items whenever you rlm@609: make a purchase or deposit. For example, if you deposit a pokeball, rlm@609: then deposit another pokeball, the item list looks like: rlm@609: rlm@613: #+begin_example rlm@609: pokeball x2 rlm@613: #+end_example rlm@609: rlm@609: instead of: rlm@609: rlm@613: #+begin_example rlm@609: pokeball x1 rlm@609: pokeball x1 rlm@613: #+end_example rlm@609: rlm@609: However, the compaction stops after the first 0xFF item, so if there rlm@609: is an 0xFF item at the beginning of the list, it will "shield" all the rlm@609: items below it from compaction. It the beginning of the run, I stick rlm@609: an 0xFF item at the top of the PC item list, allowing me to put items rlm@609: in with impunity. At the end, I toss the 0xFF away to reveal the rlm@609: completed bootstrap program. rlm@609: rlm@614: The final payload program is multiple programs. I created a reduced rlm@614: form of MIDI and implemented it in gameboy machine language. Then I rlm@614: translated a midi file from http://www.everyponysings.com/ into this rlm@614: reduced MIDI language. The payload program contains both the music rlm@614: data and the MIDI interpreter to play that data. The picture works in rlm@614: a similar way. There is code to translate a png file into a form that rlm@614: can be displayed on a gameboy, and other code to actually display that rlm@614: image. Both the image and the display code are also written by the rlm@614: final bootstrapping program. Even though my final payload is rather rlm@614: simple, you can write any program at all as the payload. The source rlm@614: for the sound and image displaying code is at rlm@614: http://hg.bortreb.com/vba-clojure. rlm@609: rlm@609: