#+title: Pokemon Yellow Total Control Hack

 #+author: Robert McIntyre

 #+email: rlm@mit.edu

 #+description: Taking over Pokemon Yellow from the inside.

 #+keywords: pokemon, pokemon yellow, rom, gameboy, assembly, hex, pointers, clojure

 #+SETUPFILE: ../../aurellem/org/setup.org

 #+INCLUDE: ../../aurellem/org/level-0.org

 #+BABEL: :exports both :noweb yes :cache no :mkdirp yes

 #+OPTIONS: num:2

 

 

 Full Source : http://hg.bortreb.com/vba-clojure

 

 Youtube Video w/ Visual Keypresses: http://www.youtube.com/watch?v=p5T81yHkHtI

 

 Special Thanks to: 

 

  - http://tasvideos.org/2913S.html for the save corruption hack which

    is used at the start of this run.

  - http://www.everyponysings.com/ for providing the midi file I used

    to create the song at the end.

  - http://www.zophar.net/ for the terminal font.

 

 

 * Introduction

 

 Think of pokemon yellow as creating a little universe with certain

 rules. Inside that universe, you can buy items, defeat rival trainers,

 and raise your pokemon. But within that universe, you are bound by the

 rules of pokemon. You can't build new buildings, or change the music,

 or change your clothes.. There are some games (like chess), where it

 is not possible to alter the rules of the game from within the

 game. No matter what moves you make in chess, you can never change the

 rules of the game so that it becomes checkers or basketball. The point

 of this run is to show that you CAN change the rules in pokemon

 yellow. There is a certain sequence of valid actions (like walking

 from one place to another or buying items) that will allow you to

 transform pokemon yellow into Pacman, or Tetris, or Pong, or a MIDI

 player, or anything else you can imagine.

 

 * Background

 

 [[http://tasvideos.org/2913S.html][This speedrun]] by Felipe Lopes de Freitas (p4wn3r), beats pokemon

 yellow in only 1 minute and 36 seconds. It does it by corrupting the

 in-game item list so that he can advance the list past its normal

 limit of 20 items. The memory immediately after the item list includes

 the warp points for the current map, and by treating that data as

 items and switching and dropping them, he can make the door from his

 house take him directly to the end of the game. 

 

 When I first saw that speedrun, I was amazed at how fast pokemon

 yellow could be beaten, and that it was possible to manipulate the

 game from the inside, using only the item list. I wondered how far I

 could extend the techniques found in p4wn3r's run.

 

 The gameboy is an 8 bit computer. That means that ultimately, anything

 that happens in pokemon is a result of the gameboy's CPU reading a

 stream of 8 bit numbers and doing whatever those numbers mean. For

 example, in the gameboy, the numbers: 

 

 [62 16 37 224 47 240 37 230 15 55] 

 

 mean to check which buttons are currently pressed and copy that result

 into the "A" register. With enough numbers, you can spell out an

 interactive program that reads input from the buttons and allows you

 to write any program you want to the gameboy. Once you have assembled

 such a program and forced the game to run it, you have won, since you

 can use that program to write any other program (like Tetris or

 Pacman) over pokemon yellow's code. I call a program that allows you

 to write any other program a "bootstrapping program". So, the goal is

 to somehow get a bootstrapping program into pokemon yellow and then

 force yellow to run that program instead of its own.

 

 How can we spell out such a program? Everything in the game is

 ultimately numbers, including all items, pokemon, levels, etc. In

 particular, the item list looks like:

 

 #+begin_example

 item-one-id         (0-255)

 item-one-quantity   (0-255)

 item-two-id         (0-255)

 item-two-quantity   (0-255)

 .

 .

 .

 #+end_example

 

 Let's consider the button measuring program  [37 62 16 37 224 37 240

 37 230 15 55] from before. Interpreted as items and item quantities, it is 

 

 #+begin_example

 lemonade     x16

 guard spec.  x224

 leaf stone   x240

 guard spec.  x230

 parlyz heal  x55

 #+end_example

 

 So, if we can get the right items in the right quantities, we can

 spell out a bootstrapping program. Likewise, when writing the

 bootstrapping program, we must be careful to only use numbers that are

 also valid items and quantities. This is hard because there aren't

 many different items to work with, and many machine instructions

 actually take 2 or even 3 numbers in a row, which severely restricts

 the types of items you can use. I ended up needing about 92 numbers to

 implement a bootstrap program. Half of those numbers were elaborate

 ways of doing nothing and were just there so that the entire program

 was also a valid item list.

 

 The final part of the hack is getting pokemon yellow to execute the

 new program after it has been assembled with items. Fortunately,

 pokemon keeps a number called a function pointer within easy reach of

 the corrupted item list. This function pointer is the starting point

 (address) of a program which the game runs every so often to check for

 poison and do general maintenance. By shifting an item over this

 function pointer, I can rewrite that address to point to the

 bootstrapping program, and make the game execute it. Without this

 function pointer, it would not be possible to take over the game.

 

 * The Run

 

 I start off and name my rival Lp/k. These characters will eventually be

 treated as items and shifted over the function pointer, causing it to

 execute the bootstrapping program that will soon be constructed. I

 start the run the same as p4wn3r's and restart the game while saving,

 so that the pokemon list is corrupted. By switching the 8th and 10th

 pokemon, I corrupt the item list and can now scroll down past the 20th

 item. I shift items around to increase the text speed to maximum and

 rewrite the warp point of my house to Celadon Dept. Store. (p4wn3r

 used this to go directly to the hall of fame and win the game in his

 run.) I deposit many 0x00 glitch items into the PC from my corrupted

 inventory for later use. Then, I withdraw the potion from the

 PC. This repairs my item list by overflowing the item counter from

 0xFF back to 0x00, though the potion is obliterated in the process. I

 then take 255 glitch items with ID 0x00 from the computer into my

 personal items.

 

 Leaving my house takes me directly to Celadon Dept. store, where I

 sell two 0x00 items for 414925 each, giving myself essentially max

 money. I hit every floor of the department store, gathering the

 following items:

 

 #+begin_example

 +-------------------+----------+

 |##| Item           | Quantity |

 +--+----------------+----------+

 |1 | TM02           |  98      |

 |2 | TM37           |  71      |

 |3 | TM05           |   1      |

 |4 | TM09           |   1      |

 |5 | burn-heal      |  12      |

 |6 | ice-heal       |  55      |

 |7 | parlyz-heal    |  99      |

 |8 | parlyz-heal    |  55      |

 |9 | TM18           |   1      |

 |10| fire-stone     |  23      |

 |11| water-stone    |  29      |

 |12| x-accuracy     |  58      |

 |13| guard-spec     |  99      |

 |14| guard-spec     |  24      |

 |15| lemonade       |  16      |

 |16| TM13           |   1      |

 +--+----------------+----------+

 #+end_example

 

 After gathering these items, I deposit them in the appropriate order

 into the item PC to spell out my bootstrapping program. Writing a full

 bootstrap program in one go using only items turned out to be too

 hard, so I split the process up into three parts. The program that I

 actually construct using items is very limited. It reads only from the

 A, B, start, and select buttons, and writes 4 bits each frame starting

 at a fixed point in memory. After it writes 200 or so bytes, it jumps

 directly to what it just wrote. In my run, I use this program to write

 another bootstrapping program that can write any number of bytes to

 any location in memory, and then jump to any location in memory. This

 new program also can write 8 bits per frame by using all the

 buttons. Using this new bootstrap program, I write a final

 bootstrapping program that does everything the previous bootstrapping

 program does except it also displays the bytes it is writing to memory

 on the screen.

 

 After completing this bootstrapping program, I go to the Celadon

 mansion, because I find the metaness of that building to be

 sufficiently high to serve as an exit point for the pokemon

 universe. I corrupt my item list again by switching corrupted pokemon,

 scroll down to my rival's name and discard until it is equal to the

 address of my bootstrapping program, and then swap it with the

 function pointer. Once the menu is closed, the bootstrapping program

 takes over, and I write the payload....

 

 * Infrastructure

 

 The entire video was completely produced by bots --- I didn't manually

 play the game at all to produce this speedrun. Here is a brief account

 of the infrastructure I build to make the video.  The entire source of

 the project is available at http://hg.bortreb.com/vba-clojure

 

 The first step was to build a programmatic interface to pokemon

 yellow. So, I downloaded vba-rerecording from

 http://code.google.com/p/vba-rerecording/. After repairing their

 broken auto-tools scripts so that it would compile on GNU/Linux, I

 added a low level C interface that I could call from Java via

 JNI. This C interface gives me basic control over the emulator: I can

 step the emulator either one clock cycle or one frame, and I can get

 the contents of any memory location or register. The interface also

 allows me to freeze the state of the emulator, save it to a Java

 object, and reload that state again at any time.

 

 I built a layer of [[http://clojure.org/][clojure]] code on top of the JNI bindings to get an

 entirely functional interface to vba-rerecording. This interface

 treats state of the emulator as an immutable object, and allows me to

 do everything I could do with the lower level C interface in a

 functional manner. Using this functional code, I wrote search programs

 that take a particular game-state and try out different combinations

 of button presses to get any desired effect. By combining different

 styles of search with different initial conditions, I created high

 level functions that could each accomplish a certain general task,

 like walking and buying items. For example, here is some actual code:

 

 #+begin_src clojure

 (defn-memo viridian-store->oaks-lab

   ([] (viridian-store->oaks-lab

        (get-oaks-parcel)))

   ([script]

      (->> script

           (walk [↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

                  ← ← ← ← ← ← ← ← ← 

                  ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

                  ← ←

                  ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

                  ↓ ↓ ↓ ↓ ↓ ↓ ↓

                  → → → → → → → →

                  ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

                  ← ← ← ← ←

                  ↓ ↓ ↓ ↓

                  ])

           (walk-thru-grass

            [↓ ↓ ↓ ↓ ↓ ↓ ↓])

           (walk [↓ ↓ ← ↓ ↓ ↓ ←

                  ↓ ↓ ↓ ↓ ↓ ↓

                  → → → ↑])

                 

           (do-nothing 1))))

 #+end_src

 

 This script walks from the Viridian City pokemon store to Oak's

 Lab in the most efficient way possible. The walk-thru-grass function

 guarantees that no wild battles will happen by manipulating the game's

 random number generator.

 

 #+begin_src clojure

 (defn-memo hacking-10

   ([] (hacking-10 (hacking-9)))

   ([script]

      (->> script

           begin-deposit

           (deposit-held-item 17 230)

           (deposit-held-item-named :parlyz-heal 55)

           (deposit-held-item 14 178)

           (deposit-held-item-named :water-stone 29)

           (deposit-held-item 14 32)

           (deposit-held-item-named :TM18 1)

           (deposit-held-item 13 1)

           (deposit-held-item 13 191)

           (deposit-held-item-named :TM02 98)

           (deposit-held-item-named :TM09 1)

           close-menu)))

 #+end_src

 

 This script calculates the fastest sequence of key presses to deposit

 the requested items into a PC, assuming that the character starts out

 in front of a computer.

 

 I also wrote functions that could grovel through the game's memory and

 present the internal data structures in usable ways. For example, the

 function =print-inventory= returns the current inventory in a human

 readable format.

 

 #+begin_src clojure :results output :exports both

 (com.aurellem.gb.items/print-inventory)

 #+end_src

 

 #+results:

 #+begin_example

 +-------------------+----------+

 |##| Item           | Quantity |

 +--+----------------+----------+

 |0 | poke-ball      |  14      |

 |1 | TM28           |   1      |

 |2 | TM11           |   1      |

 |3 | TM45           |   1      |

 |4 | nugget         |   1      |

 |5 | s.s.ticket     |   1      |

 |6 | helix-fossil   |   1      |

 |7 | moon-stone     |   1      |

 +--+----------------+----------+

 

 #+end_example

 

 

 Armed with these functions, I constructed a bootstrapping program that

 could be expressed as items. This is particularly hard, since many

 useful opcodes do not correspond any item, and the item quantities

 must all be less than 99.

 

 Here is the first bootstrapping program in all its glory.

 

 #+begin_src clojure

 (defn pc-item-writer-program

   []

   (let [;;limit 75

         limit 201 ;; (item-hack 201 is the smallest I could make this.) 

         [target-high target-low] (disect-bytes-2 pokemon-list-start)]

     (flatten

      [[0x00  ;; (item-hack) no-op (can't buy repel (1E) at celadon)

        0x1E  ;; load limit into E

        limit

        0x3F  ;; (item-hack) set carry flag no-op

 

        ;; load 2 into C.

        0x0E   ;; C == 1 means input-first nybble

        0x04   ;; C == 0 means input-second nybble

 

        0x21 ;; load target into HL

        target-low

        target-high

        0x37 ;; (item-hack) set carry flag no-op

 

        0x00 ;; (item-hack) no-op

        0x37 ;; (item-hack) set carry flag no-op

        

        0x00 ;; (item-hack) no-op

        0xF3 ;; disable interrupts

        ;; Input Section

 

        0x3E ;; load 0x20 into A, to measure buttons

        0x10 

 

        0x00 ;; (item-hack) no-op

        0xE0 ;; load A into [FF00]

        0x00

 

        0xF0 ;; load 0xFF00 into A to get

        0x00 ;; button presses

        

        0xE6

        0x0F ;; select bottom four bits of A

        0x37 ;; (item-hack) set carry flag no-op

 

        0x00 ;; (item-hack) no-op

        0xB8 ;; see if input is different (CP A B)

 

        0x00 ;; (item-hack) (INC SP)

        0x28 ;; repeat above steps if input is not different

        ;; (jump relative backwards if B != A)

        0xED ;; (literal -19) (item-hack) -19 == egg bomb (TM37)

 

        0x47 ;; load A into B

        

        0x0D ;; dec C

        0x37 ;; (item-hack) set-carry flag

        ;; branch based on C:

        0x20 ;; JR NZ

        23 ;; skip "input second nybble" and "jump to target" below

        

        ;; input second nybble

 

        0x0C ;; inc C

        0x0C ;; inc C

 

        0x00 ;; (item-hack) no-op

        0xE6 ;; select bottom bits

        0x0F

        0x37 ;; (item-hack) set-carry flag no-op

 

        0x00 ;; (item-hack) no-op

        0xB2 ;; (OR A D) -> A

 

        0x22 ;; (do (A -> (HL)) (INC HL))

 

        0x1D ;; (DEC E)

 

        0x00 ;; (item-hack) 

        0x20 ;; jump back to input section if not done

        0xDA ;; literal -36 == TM 18 (counter)

        0x01 ;; (item-hack) set BC to literal (no-op)

 

        ;; jump to target

        0x00  ;; (item-hack) these two bytes can be anything.

        0x01 

 

        0x00   ;; (item-hack) no-op

        0xBF   ;; (CP A A) ensures Z

        

        0xCA   ;; (item-hack) jump if Z

        target-low

        target-high

        0x01   ;; (item-hack) will never be reached.

        

        ;; input first nybble

        0x00

        0xCB

        0x37  ;; swap nybbles on A

 

        0x57  ;; A -> D

 

        0x37  ;; (item-hack) set carry flag no-op

        0x18  ;; relative jump backwards

        0xCD  ;; literal -51 == TM05; go back to input section

        0x01  ;; (item-hack) will never reach this instruction

 

        ]

       (repeat 8 [0x00 0x01]);; these can be anything

 

       [;; jump to actual program

        0x00

        0x37  ;; (item-hack) set carry flag no-op

 

        0x2E  ;; 0x3A -> L

        0x3A

 

 

        0x00  ;; (item-hack) no-op

        0x26  ;; 0xD5 -> L

        0xD5  

        0x01  ;; (item-hack) set-carry BC

 

        0x00  ;; (item-hack) these can be anything

        0x01  

 

        0x00

        0xE9 ;; jump to (HL)

        ]])))

 

 #+end_src

 

 I use the glitch items 0x00 and 0xFF to great effect in my run. 0x00

 sells for almost half of maximum money --- I use just 3 of them to

 finance the purchase of all the other items I need. 0x00 is also a

 NO-OP in the gameboy's machine language, which means that I can stick

 them anywhere where I need to break up an other wise illegal pair of

 opcodes. 0xFF is also extremely useful because it is the end-of-list

 sentinel. Normally, the game will "compact" your items whenever you

 make a purchase or deposit. For example, if you deposit a pokeball,

 then deposit another pokeball, the item list looks like:

 

 #+begin_example

 pokeball x2

 #+end_example

 

 instead of:

 

 #+begin_example

 pokeball x1

 pokeball x1

 #+end_example

 

 However, the compaction stops after the first 0xFF item, so if there

 is an 0xFF item at the beginning of the list, it will "shield" all the

 items below it from compaction. It the beginning of the run, I stick

 an 0xFF item at the top of the PC item list, allowing me to put items

 in with impunity. At the end, I toss the 0xFF away to reveal the

 completed bootstrap program.

 

 The final payload program is multiple programs. I created a reduced

 form of MIDI and implemented it in gameboy machine language. Then I

 translated a midi file from http://www.everyponysings.com/ into this

 reduced MIDI language. The payload program contains both the music

 data and the MIDI interpreter to play that data. The picture works in

 a similar way. There is code to translate a png file into a form that

 can be displayed on a gameboy, and other code to actually display that

 image. Both the image and the display code are also written by the

 final bootstrapping program.  Even though my final payload is rather

 simple, you can write any program at all as the payload. The source

 for the sound and image displaying code is at

 http://hg.bortreb.com/vba-clojure.