1.1 --- a/org/total-control.org	Thu Nov 22 07:51:36 2012 -0600
     1.2 +++ b/org/total-control.org	Thu Nov 22 10:54:59 2012 -0600
     1.3 @@ -9,3 +9,462 @@
     1.4  #+OPTIONS: num:2
     1.5  
     1.6  
     1.7 +Full Source : http://hg.bortreb.com/vba-clojure
     1.8 +
     1.9 +Youtube Video w/ Visual Keypresses: http://www.youtube.com/watch?v=p5T81yHkHtI
    1.10 +
    1.11 +Special Thanks to: 
    1.12 +
    1.13 + - http://tasvideos.org/2913S.html for the save corruption hack which
    1.14 +   is used at the start of this run.
    1.15 + - http://www.everyponysings.com/ for providing the midi file I used
    1.16 +   to create the song at the end.
    1.17 + - http://www.zophar.net/ for the terminal font.
    1.18 +
    1.19 +
    1.20 +* Introduction
    1.21 +
    1.22 +Think of pokemon yellow as creating a little universe with certain
    1.23 +rules. Inside that universe, you can buy items, defeat rival trainers,
    1.24 +and raise your pokemon. But within that universe, you are bound by the
    1.25 +rules of pokemon. You can't build new buildings, or change the music,
    1.26 +or change your clothes.. There are some games (like chess), where it
    1.27 +is not possible to alter the rules of the game from within the
    1.28 +game. No matter what moves you make in chess, you can never change the
    1.29 +rules of the game so that it becomes checkers or basketball. The point
    1.30 +of this run is to show that you CAN change the rules in pokemon
    1.31 +yellow. There is a certain sequence of valid actions like walking from
    1.32 +one place to another or buying items that will allow you to transform
    1.33 +pokemon yellow into Pacman, or Tetris, or Pong, or a MIDI player, or
    1.34 +anything else you can imagine.
    1.35 +
    1.36 +* Background
    1.37 +
    1.38 +[[http://tasvideos.org/2913S.html][This speedrun]] by Felipe Lopes de Freitas (p4wn3r), beats pokemon
    1.39 +yellow in only 1 minute and 36 seconds. It does it by corrupting the
    1.40 +in-game item list so that he can advance the list past its normal
    1.41 +limit of 20 items. The memory immediately after the item list includes
    1.42 +the warp points for the current map, and by treating that data as
    1.43 +items and switching and dropping them, he can make the door from his
    1.44 +house take him directly to the end of the game. 
    1.45 +
    1.46 +When I first saw that speedrun, I was amazed at how fast pokemon
    1.47 +yellow could be beaten, and that it was possible to manipulate the
    1.48 +game from the inside, using only the item list. I wondeered how far I
    1.49 +could extend the techniques found in p4wn3r's run.
    1.50 +
    1.51 +The gameboy is an 8 bit computer. That means that ultimately, anything
    1.52 +that happens in pokemon is a result of the gameboy's CPU reading a
    1.53 +stream of 8 bit numbers and doing whatever those numbers mean. For
    1.54 +example, in the gameboy, the numbers: 
    1.55 +
    1.56 +[62 16 37 224 47 240 37 230 15 55] 
    1.57 +
    1.58 +mean to check which buttons are currently pressed and copy that result
    1.59 +into the "A" register. With enough numbers, you can spell out an
    1.60 +interactive program that reads input from the buttons and allows you
    1.61 +to write any program you want to the gameboy. Once you have assembled
    1.62 +such a program and forced the game to run it, you have won, since you
    1.63 +can use that program to write any other program (like tetirs or
    1.64 +pacman) over pokemon yellow's code. I call a program that allows you
    1.65 +to write any other program a "bootstrapping program". So, the goal is
    1.66 +to somehow get a bootstrapping program into pokemon yellow and then
    1.67 +force yellow to run that program instead of its own.
    1.68 +
    1.69 +How can we spell out such a program? Everything in the game is
    1.70 +ultimately nunbers, including all items, pokemon, levels, etc. In
    1.71 +particular, the item list looks like:
    1.72 +
    1.73 +item-one-id         (0-255)
    1.74 +item-one-quantity   (0-255)
    1.75 +item-two-id         (0-255)
    1.76 +item-two-quantity   (0-255)
    1.77 +.
    1.78 +.
    1.79 +.
    1.80 +
    1.81 +Let's consider the button measuring program  [37 62 16 37 224 37 240
    1.82 +37 230 15 55] from before. Interpreted as items and item quantities, it is 
    1.83 +
    1.84 +lemonade     x16
    1.85 +guard spec.  x224
    1.86 +leaf stone   x240
    1.87 +guard spec.  x230
    1.88 +parlyz heal  x55
    1.89 +
    1.90 +So, if we can get the right items in the right quantities, we can
    1.91 +spell out a bootstrapping program. Likewise, when writing the
    1.92 +bootstrapping program, we must be careful to only use numbers that are
    1.93 +also valid items and quantities. This is hard because there aren't
    1.94 +many different items to work with, and many machine instructions
    1.95 +actually take 2 or even 3 numbers in a row, which severely restricts
    1.96 +the types of items you can use. I ended up needing about 92 numbers to
    1.97 +implement a bootstrap program. Half of those numbers were elaborate
    1.98 +ways of doing nothing and were just there so that the entire program
    1.99 +was also a valid item list.
   1.100 +
   1.101 +The final part of the hack is getting pokemon yellow to execute the
   1.102 +new program after it has been assembled with items. Fortunately,
   1.103 +pokemon keeps a number called a function pointer within easy reach of
   1.104 +the corrupted item list. This function pointer is the starting point
   1.105 +(address) of a program which the game runs every so often to check for
   1.106 +poison and do general maintaiance. By shifting an item over this
   1.107 +function pointer, I can rewrite that address to point to the
   1.108 +bootstrapping program, and make the game execute it. Without this
   1.109 +function pointer, it would not be possible to take over the game.
   1.110 +
   1.111 +* The Run
   1.112 +
   1.113 +I start off and name my rival Lpk. These characters will eventually be
   1.114 +treated as items and shifted over the function pointer, causing it to
   1.115 +execute the bootstrapping program that will soon be constructed. I
   1.116 +start the run the same as p4wn3r's and restart the game while saving,
   1.117 +so that the pokemon list is corrupted. By switching the 8th and 10th
   1.118 +pokemon, I corrupt the item list and can now scroll down past the 20th
   1.119 +item. I shift items around to increase the text speed to maximum and
   1.120 +rewrite the warp point of my house to Celadon Dept. Store. (p4wn3r
   1.121 +used this to go directly to the hall of fame and win the game in his
   1.122 +run.) I deposit many 0x00 glitch items into the PC from my corrupted
   1.123 +inventory for later use. Then, I widthdraw the potion from the
   1.124 +PC. This repairs my item list by overflowing the item counter from
   1.125 +0xFF back to 0x00, though the potion is obliterated in the process. I
   1.126 +then take 255 glitch items with ID 0x00 from the computer into my
   1.127 +personal items.
   1.128 +
   1.129 +Leaving my house takes me directly to Celadon Dept. store, where I
   1.130 +sell two 0x00 items for 414925 each, giving myself essentially max
   1.131 +money. I hit every floor of the department store, gathering the
   1.132 +following items:
   1.133 +
   1.134 +#+begin_example
   1.135 ++-------------------+----------+
   1.136 +|##| Item           | Quantity |
   1.137 ++--+----------------+----------+
   1.138 +|1 | TM02           |  98      |
   1.139 +|2 | TM37           |  71      |
   1.140 +|3 | TM05           |   1      |
   1.141 +|4 | TM09           |   1      |
   1.142 +|5 | burn-heal      |  12      |
   1.143 +|6 | ice-heal       |  55      |
   1.144 +|7 | parlyz-heal    |  99      |
   1.145 +|8 | parlyz-heal    |  55      |
   1.146 +|9 | TM18           |   1      |
   1.147 +|10| fire-stone     |  23      |
   1.148 +|11| water-stone    |  29      |
   1.149 +|12| x-accuracy     |  58      |
   1.150 +|13| guard-spec     |  99      |
   1.151 +|14| guard-spec     |  24      |
   1.152 +|15| lemonade       |  16      |
   1.153 +|16| TM13           |   1      |
   1.154 ++--+----------------+----------+
   1.155 +#+end_example
   1.156 +
   1.157 +After gathering these items, I deposit them in the appropriate order
   1.158 +into the item PC to spell out my bootstrapping program. Writing a full
   1.159 +bootstrap program in one go using only items turned out to be too
   1.160 +hard, so I split the process up into three parts. The program that I
   1.161 +actually construct using items is very limited. It reads only from the
   1.162 +A, B, start, and select buttons, and writes 4 bits each frame to a
   1.163 +fixed point in memory. After it writes 200 or so bytes, it jumps
   1.164 +directly to what it just wrote. In my run, I use this program to write
   1.165 +another bootstrapping program that can write to any number of bytes to
   1.166 +any location in memory, and then jump to any location in memory. This
   1.167 +new program also can write 8 bits per frame by using all the
   1.168 +buttons. Using this new bootstrap program, I write a final
   1.169 +bootstrapping program that does everything the provious bootstrapping
   1.170 +program does except it also displays the bytes it is writing to memory
   1.171 +on the screen.
   1.172 +
   1.173 +After completing this bootstrapping program, I go to the celadon
   1.174 +mansion, because I find the metaness of that building to be
   1.175 +sufficiently high to serve as an exit point for the pokemon
   1.176 +universe. I corrupt my item list again by switching corrupted pokemon,
   1.177 +scroll down to my rival's name and discard untill it is equal to the
   1.178 +address of my bootstrapping program, and then swap it with the
   1.179 +function pointer. Once the menu is closed, the boostrapping program
   1.180 +takes over, and I write the payload....
   1.181 +
   1.182 +* Infrastructure
   1.183 +
   1.184 +The entire video was completely produced by bots --- I didn't manually
   1.185 +play the game at all to produce this speedrun. Here is a brief account
   1.186 +of the infrastructure I build to make the video.  The entire source of
   1.187 +the project is available at http://hg.bortreb.com/vba-clojure
   1.188 +
   1.189 +The first step was to build a programatic interface to pokemon
   1.190 +yellow. So, I downloaded vba-rerecording from
   1.191 +http://code.google.com/p/vba-rerecording/. After repairing their
   1.192 +broken auto-tools scripts so that it would compile on GNU/Linux, I
   1.193 +added a low level C interface that I could call from Java via
   1.194 +JNI. This C interface gives me basic control over the emulator: I can
   1.195 +step the emulator either one clock cycle or one frame, and I can get
   1.196 +the contents of any memory location or register. The interface also
   1.197 +allows me to freeze the state of the emulator, save it to a Java
   1.198 +object, and reload that state again at any time.
   1.199 +
   1.200 +I built a layer of [[http://clojure.org/][clojure]] code on top of the JNI bindings to get an
   1.201 +entirely functional interface to vba-rerecording. This interface
   1.202 +treats state of the emulator as an immutable object, and allows me to
   1.203 +do everything I could do with the lower level C interface in a
   1.204 +functional manner. Using this functional code, I wrote search programs
   1.205 +that take a particular game-state and try out different combinations
   1.206 +of button prosses to get any desired effect. By combining different
   1.207 +styles of search with different initial conditions, I created high
   1.208 +level functions that could each accomplish a certain general task,
   1.209 +like walking and buying items. For example, here is some actual code:
   1.210 +
   1.211 +#+begin_src clojure
   1.212 +(defn-memo viridian-store->oaks-lab
   1.213 +  ([] (viridian-store->oaks-lab
   1.214 +       (get-oaks-parcel)))
   1.215 +  ([script]
   1.216 +     (->> script
   1.217 +          (walk [↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
   1.218 +                 ← ← ← ← ← ← ← ← ← 
   1.219 +                 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
   1.220 +                 ← ←
   1.221 +                 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
   1.222 +                 ↓ ↓ ↓ ↓ ↓ ↓ ↓
   1.223 +                 → → → → → → → →
   1.224 +                 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
   1.225 +                 ← ← ← ← ←
   1.226 +                 ↓ ↓ ↓ ↓
   1.227 +                 ])
   1.228 +          (walk-thru-grass
   1.229 +           [↓ ↓ ↓ ↓ ↓ ↓ ↓])
   1.230 +          (walk [↓ ↓ ← ↓ ↓ ↓ ←
   1.231 +                 ↓ ↓ ↓ ↓ ↓ ↓
   1.232 +                 → → → ↑])
   1.233 +                
   1.234 +          (do-nothing 1))))
   1.235 +#+end_src
   1.236 +
   1.237 +This script walks from the Viridian City pokemon store to Oak's
   1.238 +Lab in the most efficient way possible. The walk-thru-grass function
   1.239 +gaurantees that no wild battles will happen by manipulating the game's
   1.240 +random number generator.
   1.241 +
   1.242 +#+begin_src clojure
   1.243 +(defn-memo hacking-10
   1.244 +  ([] (hacking-10 (hacking-9)))
   1.245 +  ([script]
   1.246 +     (->> script
   1.247 +          begin-deposit
   1.248 +          (deposit-held-item 17 230)
   1.249 +          (deposit-held-item-named :parlyz-heal 55)
   1.250 +          (deposit-held-item 14 178)
   1.251 +          (deposit-held-item-named :water-stone 29)
   1.252 +          (deposit-held-item 14 32)
   1.253 +          (deposit-held-item-named :TM18 1)
   1.254 +          (deposit-held-item 13 1)
   1.255 +          (deposit-held-item 13 191)
   1.256 +          (deposit-held-item-named :TM02 98)
   1.257 +          (deposit-held-item-named :TM09 1)
   1.258 +          close-menu)))
   1.259 +#+end_src
   1.260 +
   1.261 +This script calculates the fastest sequence of key presses to deposit
   1.262 +the requested items into a pc, assuming that the character starts out
   1.263 +in front of a computer.
   1.264 +
   1.265 +I also wrote functions that coudl grovel through the game's memory and
   1.266 +present the internal data structures in useable ways. For example, the
   1.267 +function =print-inventory= returns the current inventory in a human
   1.268 +readable format.
   1.269 +
   1.270 +#+begin_src clojure :results output
   1.271 +(com.aurellem.gb.items/print-inventory)
   1.272 +#+end_src
   1.273 +
   1.274 +#+results:
   1.275 +#+begin_example
   1.276 ++-------------------+----------+
   1.277 +|##| Item           | Quantity |
   1.278 ++--+----------------+----------+
   1.279 +|0 | poke-ball      |  14      |
   1.280 +|1 | TM28           |   1      |
   1.281 +|2 | TM11           |   1      |
   1.282 +|3 | TM45           |   1      |
   1.283 +|4 | nugget         |   1      |
   1.284 +|5 | s.s.ticket     |   1      |
   1.285 +|6 | helix-fossil   |   1      |
   1.286 +|7 | moon-stone     |   1      |
   1.287 ++--+----------------+----------+
   1.288 +
   1.289 +#+end_example
   1.290 +
   1.291 +
   1.292 +Armed with these functions, I constructed a bootstrapping program that
   1.293 +could be expressed as items. This is particurally hard, since many
   1.294 +useful opcodes do not correspond any item, and the item quantities
   1.295 +must all be less than 99.
   1.296 +
   1.297 +Here is the first bootstrapping program in all its glory.
   1.298 +
   1.299 +#+begin_src clojure
   1.300 +(defn pc-item-writer-program
   1.301 +  []
   1.302 +  (let [;;limit 75
   1.303 +        limit 201 ;; (item-hack 201 is the smallest I could make this.) 
   1.304 +        [target-high target-low] (disect-bytes-2 pokemon-list-start)]
   1.305 +    (flatten
   1.306 +     [[0x00  ;; (item-hack) no-op (can't buy repel (1E) at celadon)
   1.307 +       0x1E  ;; load limit into E
   1.308 +       limit
   1.309 +       0x3F  ;; (item-hack) set carry flag no-op
   1.310 +
   1.311 +       ;; load 2 into C.
   1.312 +       0x0E   ;; C == 1 means input-first nybble
   1.313 +       0x04   ;; C == 0 means input-second nybble
   1.314 +
   1.315 +       0x21 ;; load target into HL
   1.316 +       target-low
   1.317 +       target-high
   1.318 +       0x37 ;; (item-hack) set carry flag no-op
   1.319 +
   1.320 +       0x00 ;; (item-hack) no-op
   1.321 +       0x37 ;; (item-hack) set carry flag no-op
   1.322 +       
   1.323 +       0x00 ;; (item-hack) no-op
   1.324 +       0xF3 ;; disable interrupts
   1.325 +       ;; Input Section
   1.326 +
   1.327 +       0x3E ;; load 0x20 into A, to measure buttons
   1.328 +       0x10 
   1.329 +
   1.330 +       0x00 ;; (item-hack) no-op
   1.331 +       0xE0 ;; load A into [FF00]
   1.332 +       0x00
   1.333 +
   1.334 +       0xF0 ;; load 0xFF00 into A to get
   1.335 +       0x00 ;; button presses
   1.336 +       
   1.337 +       0xE6
   1.338 +       0x0F ;; select bottom four bits of A
   1.339 +       0x37 ;; (item-hack) set carry flag no-op
   1.340 +
   1.341 +       0x00 ;; (item-hack) no-op
   1.342 +       0xB8 ;; see if input is different (CP A B)
   1.343 +
   1.344 +       0x00 ;; (item-hack) (INC SP)
   1.345 +       0x28 ;; repeat above steps if input is not different
   1.346 +       ;; (jump relative backwards if B != A)
   1.347 +       0xED ;; (literal -19) (item-hack) -19 == egg bomb (TM37)
   1.348 +
   1.349 +       0x47 ;; load A into B
   1.350 +       
   1.351 +       0x0D ;; dec C
   1.352 +       0x37 ;; (item-hack) set-carry flag
   1.353 +       ;; branch based on C:
   1.354 +       0x20 ;; JR NZ
   1.355 +       23 ;; skip "input second nybble" and "jump to target" below
   1.356 +       
   1.357 +       ;; input second nybble
   1.358 +
   1.359 +       0x0C ;; inc C
   1.360 +       0x0C ;; inc C
   1.361 +
   1.362 +       0x00 ;; (item-hack) no-op
   1.363 +       0xE6 ;; select bottom bits
   1.364 +       0x0F
   1.365 +       0x37 ;; (item-hack) set-carry flag no-op
   1.366 +
   1.367 +       0x00 ;; (item-hack) no-op
   1.368 +       0xB2 ;; (OR A D) -> A
   1.369 +
   1.370 +       0x22 ;; (do (A -> (HL)) (INC HL))
   1.371 +
   1.372 +       0x1D ;; (DEC E)
   1.373 +
   1.374 +       0x00 ;; (item-hack) 
   1.375 +       0x20 ;; jump back to input section if not done
   1.376 +       0xDA ;; literal -36 == TM 18 (counter)
   1.377 +       0x01 ;; (item-hack) set BC to literal (no-op)
   1.378 +
   1.379 +       ;; jump to target
   1.380 +       0x00  ;; (item-hack) these two bytes can be anything.
   1.381 +       0x01 
   1.382 +
   1.383 +       0x00   ;; (item-hack) no-op
   1.384 +       0xBF   ;; (CP A A) ensures Z
   1.385 +       
   1.386 +       0xCA   ;; (item-hack) jump if Z
   1.387 +       target-low
   1.388 +       target-high
   1.389 +       0x01   ;; (item-hack) will never be reached.
   1.390 +       
   1.391 +       ;; input first nybble
   1.392 +       0x00
   1.393 +       0xCB
   1.394 +       0x37  ;; swap nybbles on A
   1.395 +
   1.396 +       0x57  ;; A -> D
   1.397 +
   1.398 +       0x37  ;; (item-hack) set carry flag no-op
   1.399 +       0x18  ;; relative jump backwards
   1.400 +       0xCD  ;; literal -51 == TM05; go back to input section
   1.401 +       0x01  ;; (item-hack) will never reach this instruction
   1.402 +
   1.403 +       ]
   1.404 +      (repeat 8 [0x00 0x01]);; these can be anything
   1.405 +
   1.406 +      [;; jump to actual program
   1.407 +       0x00
   1.408 +       0x37  ;; (item-hack) set carry flag no-op
   1.409 +
   1.410 +       0x2E  ;; 0x3A -> L
   1.411 +       0x3A
   1.412 +
   1.413 +
   1.414 +       0x00  ;; (item-hack) no-op
   1.415 +       0x26  ;; 0xD5 -> L
   1.416 +       0xD5  
   1.417 +       0x01  ;; (item-hack) set-carry BC
   1.418 +
   1.419 +       0x00  ;; (item-hack) these can be anything
   1.420 +       0x01  
   1.421 +
   1.422 +       0x00
   1.423 +       0xE9 ;; jump to (HL)
   1.424 +       ]])))
   1.425 +
   1.426 +#+end_src
   1.427 +
   1.428 +I use the glitch items 0x00 and 0xFF to great effect in my run. 0x00
   1.429 +sells for almost half of max_money, and I use just 3 of them to
   1.430 +finance the purchace of all the other items I need. 0x00 is also a
   1.431 +NO-OP in the gameboy's machine language, which means that I can stick
   1.432 +them anywhere where I need to break up an other wise illegal pair of
   1.433 +opcodes. 0xFF is also extremely useful because it is the end-of-list
   1.434 +sentinel. Normally, the game will "compact" your items whenever you
   1.435 +make a purchase or deposit. For example, if you deposit a pokeball,
   1.436 +then deposit another pokeball, the item list looks like:
   1.437 +
   1.438 +pokeball x2
   1.439 +
   1.440 +instead of:
   1.441 +
   1.442 +pokeball x1
   1.443 +pokeball x1
   1.444 +
   1.445 +However, the compaction stops after the first 0xFF item, so if there
   1.446 +is an 0xFF item at the beginning of the list, it will "shield" all the
   1.447 +items below it from compaction. It the beginning of the run, I stick
   1.448 +an 0xFF item at the top of the PC item list, allowing me to put items
   1.449 +in with impunity. At the end, I toss the 0xFF away to reveal the
   1.450 +completed bootstrap program.
   1.451 +
   1.452 +The final payload program is actually multiple programs. I created a
   1.453 +reduced form of MIDI and implemented it in gameboy machine
   1.454 +language. Then I translated a midi file from
   1.455 +http://www.everyponysings.com/ into this reduced MIDI language. The
   1.456 +payload program contains both the music data and the MIDI interpreter
   1.457 +to play that data. The picture works in a similiar way. There is code
   1.458 +to translate a png file into a form that can be displayed on a
   1.459 +gameboy, and other code to actually display that image. Both the image
   1.460 +and the display code are also written by the final bootstrapping
   1.461 +program.  Even though my final payload is rather simple, you can write
   1.462 +any program at all as the payload. The source for the sound and image
   1.463 +displaying code is at http://hg.bortreb.com/vba-clojure.
   1.464 +
   1.465 +