# HG changeset patch # User Robert McIntyre # Date 1353603299 21600 # Node ID 65b7c5b47de16d817e8e3a2af542f51ea9e2f827 # Parent 2c348cc68bac52f483011d89cae9cc34cf47494a first draft of explination. diff -r 2c348cc68bac -r 65b7c5b47de1 org/total-control.org --- a/org/total-control.org Thu Nov 22 07:51:36 2012 -0600 +++ b/org/total-control.org Thu Nov 22 10:54:59 2012 -0600 @@ -9,3 +9,462 @@ #+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 wondeered 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 tetirs 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 nunbers, including all items, pokemon, levels, etc. In +particular, the item list looks like: + +item-one-id (0-255) +item-one-quantity (0-255) +item-two-id (0-255) +item-two-quantity (0-255) +. +. +. + +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 + +lemonade x16 +guard spec. x224 +leaf stone x240 +guard spec. x230 +parlyz heal x55 + +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 maintaiance. 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 Lpk. 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 widthdraw 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 to 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 to 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 provious 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 untill it is equal to the +address of my bootstrapping program, and then swap it with the +function pointer. Once the menu is closed, the boostrapping 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 programatic 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 prosses 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 +gaurantees 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 coudl grovel through the game's memory and +present the internal data structures in useable ways. For example, the +function =print-inventory= returns the current inventory in a human +readable format. + +#+begin_src clojure :results output +(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 particurally 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 max_money, and I use just 3 of them to +finance the purchace 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: + +pokeball x2 + +instead of: + +pokeball x1 +pokeball x1 + +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 actually 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 similiar 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. + +