vba-clojure: org/total-control.org comparison

comparison org/total-control.org @ 609:65b7c5b47de1

first draft of explination.

author	Robert McIntyre <rlm@mit.edu>
date	Thu, 22 Nov 2012 10:54:59 -0600
parents	2c348cc68bac
children	4dd5ebf224cd

comparison

equal deleted inserted replaced

-:2c348cc68bac
+:65b7c5b47de1
 #+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 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.

Mercurial > vba-clojure

comparison org/total-control.org @ 609:65b7c5b47de1