Hello fellow TASers --- I wanted to share a TAS Pokemon
Yellow video I've been working on for the past three
months. This is my first post to this site so I wanted to
get some feedback before posting it as an actual run.
This is not a speedrun but an entertainment run which shows
off an intricite glitch I've constructed.
I was inspired by http://tasvideos.org/2913S.html which
basically turns the in-game item list into a hex editor. I
wanted to see how far I could take that concept. In this run
I use items to spell out a program in the gameboy's machine
language. After multiple stages of bootstrapping I create a
program that allows me to completely rewrite Pokemon
Yellow's RAM. I use this ability to insert my own image and
song into the game.
As far as I know no other hack can completely reprogram a
game from within.
I created an encoded video of the run at youtube and at
aurellem.org,
http://www.youtube.com/watch?v=p5T81yHkHtILink to videohttp://aurellem.org/pokemon-hack/rlm-yellow-hack.avi
Here is the vbm file. It should work with the latest version
of VisualBoyAdvance.
http://aurellem.org/pokemon-hack/rlm-yellow-hack.vbm
And finally, the entire source code for the project:
http://hg.bortreb.com/vba-clojure
You can browse the link or get the project with 'hg clone'
* Technical Details
To make this run, I took the source for VisualBoyAdvance and
added JNI bindings so that I could drive the emulator from
Java and then through clojure, a dialect of LISP which runs
on the JVM. The entire run was constructed from clojure
statements which search the pokemon game tree to find the
most efficient ways to accomplish high level goals.
For example, a section of the run which buys items at the
celadon store is expressed as:
This is brilliant! Groundbreaking, too; this must be the first time a game has been reprogrammed from within using nothing but controller input. All of your work really paid off!
I'm glad you're submitting this to the site. When you do, I would really appreciate it if you explained in your submission text how the various actions in the run (like buying a lot of lemonade) help get you closer to reprogramming the game.
Epic!
I knew there was this possibility of a concept run when I submitted my last movie, and BrandonE even showed some interest in working on it, but the input limitations of the game made the job difficult. In fact, reading your YT description, this took three months! I'm glad you took this huge amount of work and finished the run!
For people who are confused, this is basically how the most severe attacks in computer security work. The attacker normally uses a buffer overflow to inject code instructions in RAM and uses stack smashing, function pointer corruption, etc. to make the program execute the malicious code. Normally this is just some instructions to make the computer bring up a shell, but the GB has no operating system, so this is not a possibility here.
bortreb's run seems to write a program in machine code to fetch bytes from the joystick input and putting them on RAM, I had this idea some time ago, but obviously the hard part is to get the data for the program in RAM without taking a huge amount of time.
Anyway, congratulations, man! I know how frustrating breaking this game can be and appreciate your effort to keep R/B TASing alive.
This is pretty neat; the principle's been around for ages (e.g. the infamous Twilight Hack, which does something similar except using a corrupted save file), but it's nice to see someone actually go through with it and work out all the input required.
(Incidentally, someone at SDA managed to replicate the Pokémon Yellow TAS in realtime, so this may be doable on console. Alternatively, the same glitched state can be achieved via the ZZAZZ glitch without resetting during a save; it might be interesting to modify the code to achieve that, which would allow this glitch to be done "safely", well as safely as the ZZAZZ glitch ever gets :). It'd be something hilarious to show off as bonus material during speedrun demonstrations.)
This is pretty neat; the principle's been around for ages (e.g. the infamous Twilight Hack, which does something similar except using a corrupted save file), but it's nice to see someone actually go through with it and work out all the input required.
This is a step further than the Twilight Hack - the Twilight Hack had to use a dirty save edited with out-of-game tools. This starts from a fresh save.
Joined: 6/25/2007
Posts: 732
Location: Vancouver, British Columbia, Canada
I'm astounded! This is the reversing feat of our time! Code injection via TASing is really awesome.
One last thing to do would be to make an guide for turning Pokémon Yellow into an IDE for real-time programming so people can write and run homebrew on their Game Boys with just a Pokémon Yellow cart; one which somehow turns the game into an IDE whenever you load your SRAM save from the main menu. Haha!
This is pretty neat; the principle's been around for ages (e.g. the infamous Twilight Hack, which does something similar except using a corrupted save file), but it's nice to see someone actually go through with it and work out all the input required.
This is a step further than the Twilight Hack - the Twilight Hack had to use a dirty save edited with out-of-game tools. This starts from a fresh save.
It's better than the Twilight Hack --- it's the Pinkie Pie hack! It breaks out of the game world from within!
Thanks for all the comments! I'll write up a detailed report of everything that's going on in the video and submit it to the site soon. I'll also annotate the source code with more detailed explainations and post it to my blog in html.
I'm glad to be part of such an excellent community!
This is pretty neat; the principle's been around for ages (e.g. the infamous Twilight Hack, which does something similar except using a corrupted save file), but it's nice to see someone actually go through with it and work out all the input required.
This is a step further than the Twilight Hack - the Twilight Hack had to use a dirty save edited with out-of-game tools. This starts from a fresh save.
I know. It's just the Twilight Hack principle + an arbitrary execution glitch, combining two things that have been known for ages. But that doesn't make it any less impressive; it's one thing to know it should be possible in theory, and another thing to actually do it.
Hmm. After watching this, I'm interested in, specifically, the shellcode that you load into memory via the items, that you then use in order to get the rest of the program into memory. Making it shorter, or limiting the opcodes you use, could make the item-buying sequence a lot shorter, and I'm interested in how optimized it is.
It may also be worth writing a short decompressor towards the end, if you haven't already. I saw several screens full of zeros; it's probably going to be faster to define a compression algorithm then use it, than it is to enter the code all at once.
bortreb, do you understand the data manipulation in the latest Yellow run? I use a trick there that swaps chunks of 11 bytes. It changes the alignment of the data and allows you to change the bytes with bad parity. It seems to me that you could remove the entire Celadon shopping by manipulating these.
(defn pc-item-writer-program
[]
(let [limit 201 ;; should be more like 92
[target-high target-low] (disect-bytes-2 pokemon-list-start)]
(flatten
[[0x00 ;; (item-hack) set increment stack pointer no-op
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)
]])))
Items like [0 1] are glich items with id==0.
I name the rival L[pk] so that I can start the program at the [0 55] item.
p4wn3r, could you explain the parity manupulation hack?
Starting at D1CA there are 6 spaces for pokemon data, each pokemon data is 44 bytes. After those, starting at D272 there are six chunks of 11 bytes (I think they are the nickname or OID, I don't remember). After those six, there are another six chunks of 11 bytes, one for each pokemon. After those, pokedex and inventory follow.
As you can see, since the game doesn't check bounds, when you have a pokemon of number higher than 6 these areas overlap.
When you switch pokemon, the game swaps the 44 bytes that have its main data and then their two corresponding 11 byte chunks (in that order).
Since the size of these chunks is odd, by switching the correct pokemon, you can make data that was in even addresses change to odd addresses and vice versa.
EDIT: Also, why does your code get the input byte like that? The game already has a function that gets the 8 bits and stores them at FFF5, I checked just now and it's in bank 3, address 4004. It looks easier to do something like "switch to bank three" (don't remember how you do that), "call 4004", and take the contents from fff5.
p4wn3r, that input function looks promising. I didn't use it because I didn't know about it. With that function, it should be possible to decrease the total items required to begin the bootstrapping process. I will also look into the possibility of using pokemon switching to create the necessary opcodes without items. However, the total time to switch pokemon and then switch the generated item into a "protected region" so that the next pokemon switch doesn't corrupt it may be longer than just buying the items (also, scrolling through the glitched items is slow). I bet that ultimately a combination of items and pokemon switching could shorten the item-buying time by maybe three or four minutes if everything went well.
Since it might be possible to improve the run with these new methods, should I submit the run as it is now or should I spend a some more time to try to get the time down? I think that the pokemon-switching trick could take several weeks to do properly, but using pokemon yellow's input function might be doable in only a few days. How does the fact that it's an entertainment run play in here?
I think you should incorporate the improvements and make the run as optimized as possible before submitting it. A lot of members here are hard to impress with the same innovative glitch twice in a row (and more people watch the Workbench than the forum). Plus, it's better if this run isn't obsoleted in a little less than a few weeks because of a few improvements despite the majority of the run being the same.
I think you should incorporate the improvements and make the run as optimized as possible before submitting it. A lot of members here are hard to impress with the same innovative glitch twice in a row (and more people watch the Workbench than the forum). Plus, it's better if this run isn't obsoleted in a little less than a few weeks because of a few improvements despite the majority of the run being the same.
There isn't a well-defined goal for the run*, though, so I think it should be optimized in whatever way is the most entertaining way to watch.
*When do you end the run? When the entirety of RAM is overridden? You don't need to overwrite all of RAM to have full control (for example, you might write into some of it a program to rewrite the rest later, or just deign not to use all of it). You could also deign to write a different program that is less general, but faster in the specific case of what the author wants to write.
There isn't a well-defined goal for the run*, though, so I think it should be optimized in whatever way is the most entertaining way to watch.
*When do you end the run?
If three to four minutes of scrolling through menus could be saved, I think that would greatly increase the run's entertainment value.
Also, I believe the run ends when he finishes programming his own graphic and song into the game and lets it play.
Since the point of the run is to "do something cool" with total control of the game's RAM, I think that it's a valid point to decrease the bootstrapping time as much as possible since scrolling through menus is boring. (Though, I like going to the celadon PC for flavor). I think I'll spend a few weeks trying to incorporate the pokemon frame shifting trick into the run. It may be possible to shave off a few minutes.
There isn't a well-defined goal for the run*, though, so I think it should be optimized in whatever way is the most entertaining way to watch.
*When do you end the run?
If three to four minutes of scrolling through menus could be saved, I think that would greatly increase the run's entertainment value.
Agreed.
Also, I believe the run ends when he finishes programming his own graphic and song into the game and lets it play.
Under this criteria, a run that can reprogram the RAM generally could be obsoleted by one that more specifically implements the desired ending (through cutting corners or otherwise).
Maybe something like 'The run ends after a RAM-written routine that allows all RAM to be rewritten loses control, having gained control'? Ugh, verbose.
Maybe it could be a new type of run -- get the game to execute a new kernel which allows for interactive reprogramming of arbitray RAM. Prove you did it by writing and then executing a demo program that does something interesting. Maybe the run ends when the total-control program begins running (because you wouldn't want to penalize more elaborate demo programs that take longer to input)? Or maybe the run ends on the last input, and is judged by total setup time versus coolness of the demo program? (to reward clever compression / bootstrapping of more elaborate programs) I wonder how many other games could be reprogrammed in this way?
I wonder how many other games could be reprogrammed in this way?
I'm not aware of any other. Probably there's an obscure title somewhere that allows this, but probably no one did the reversing necessary to do it.
Some runs in this site exploit buffer overflows, most just change some data to allow warping somewhere or getting an item way before intended. I think the SMW glitched run manages to corrupt a function pointer, but even this is useless if you don't have a plausible way to store the malicious code.
One possible way to do a run like this in other games would be to corrupt the length limit for a routine that names a character, so you can write letters in arbitrary memory locations. The opcodes would be limited to alphanumeric characters, but it's usually possible to get around this with self-modifying code.
Alternatively, for games like RPGs that have complex save data, it should be possible to put the code in SRAM. With this, we'd be relying on an overflow of few bytes in a stack variable to corrupt the stack to the code location.
