Statically Recompiling NES Games into Native Executables with LLVM and Go
andrewkelley.me
andrewkelley.me
edit: now that I think of it, I really need to keep expanding my knowledge. I'm going to go through this post in my terminal and try to at least make the stuff work, so I can start understanding this process. I've been trying to learn Go and C better anyway. Thanks for providing a ground to learn more.
The only thing stopping you from learning 'dark magic' is your willingness to put time, study, and asking others about it. If you want to learn, just keep pushing forward.
The CMU professors who made the book also have a course at CMU which uses the book as a textbook. I TAed a course at Virginia Tech that used the textbook. I thought the course does an excellent job in demystifying many systems concepts.
[1]: http://www.nand2tetris.org/book.php
In short: It gives you a hands-on approach in designing and building your own computer and programming language, to end up writing and running your own games on the system.
* It starts with simple boolean algebra to explain and create logic gates (NAND, AND, OR, XOR, etc).
* Use these to build an ALU, memory banks and eventually a full CPU.
* Design an assembly language and assembler for this system.
* Use the assembler to create a higher level OOP language, compiler and code base.
* Use this language to write a rudimentary operating system.
* Write a game to run on the OS.
Edit: For some reason, this site has started showing malware warnings in chrome and firefox since today. Even though Google's advisory[1] makes no mention of any actual malware being detected. I've visited this site safely for a long time. Still, if you don't trust it, then wait until Google clears up the issue. I've already contacted one of the authors about it.
[1]: http://safebrowsing.clients.google.com/safebrowsing/diagnost...
Edit: just noticed the original Edit mentioning that you contacted one of the authors.
The original guy who built a CPU in minecraft actually built it based on some of the exercises in that book. Good stuff overall.
Regular Javascript should be plenty fast except for full system simulation with no custom component simulators.
I ended up doing this with a SuperH disassembler (with SH2, due to its two-byte opcode layout, indirect addressing is the order of the day), and by doing basic register assignment tracking and adding a few crude heuristics, I was able to get very usable results. No, the end result won't be "pretty"; you'll be moderately embarrassed to show it off., but it will work. :)
(Heuristics: one structure that I had to manually handle were compiler-generated jump tables; thankfully, for my project, I'd had a bit of help from the compiler that was used, and there were distinct signatures I could key off of.)
If you're even remotely interested in the disassembly aspect of this, I'd recommend learning a bit about a piece of software called IDA Pro: https://www.hex-rays.com/products/ida/ As horrible as the UI of it is, there is simply nothing better on the market for reverse engineering analysis.
I never had a NES, but I had a C64, and the 6502 code wrote there seemed nasty to translate on the surface, with lots and lots of self-modification, for example. But in the end most of the self modification was specific looping patterns because the 6502 can only index 256 values, and so many loops involved writing addresses into the looping code, iterate 256 times, increase the most significant byte directly in the code and see if you'd reached the end, and jump back to iterate 256 times.
Most of this "nasty" stuff is relatively well known by now and much of it is relatively regular and easy to detect.
+1 for IDA Pro. It's a shame this software is so expensive. The UI is actually pretty decent when you get used to it, and there are a ton of good plugins.
Props dude.
$ gcc-4.8 -std=gnu99 -Wall -o test test.c
test.c: In function 'main':
test.c:6:5: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
if (foo & 0x80 == 0x80) {
^
Cool project, though.
In general, I think dynamic approaches are ideal when you're dealing with a "hostile" environment where the software you're translating was written with no expectation that it would be translated, and possibly (like with old games) in a situation where the programmer may have tried to really maximally exploit the hardware, because it means failure to statically determine that something weird is going on can often be counteracted much simpler by detecting attempts at violating your assumptions.
You can do hybrid approaches, and statically make a "best effort" and include similar methods to trap stuff that breaks your assumptions and fall back to JIT or emulation, but if you do that then there's a tradeoff between how much dynamic stuff you need to be able to do before it's easier to just do everything dynamically from the start.
The performance thing is not so easy to ascertain. JIT'ing code takes a bit of time, but not much compared to the expected overall time the program will be run afterwards. Static compilation can spend more time doing optimisations, but JIT's at least in theory have more information to work with (can detect the specific processor version, and use specialised instructions or alter instruction selection, for example, or could at least in theory even do tricks like re-arranging data to get better cache behavior (I have no idea if any existing JITs actually do that) based on profiling access patterns for the current run.
As video game consoles start looking more and more like PCs, self mutating code starts to be less frequent and more easily detectable. On the Nintendo 3DS for example, only the OS can allocate executable pages, and executable pages are forced read-only. This means you could in theory do static recompilation of a 3DS game. This is the only case I know of though - all other recent video game consoles allow self mutating code or dynamic code loading.
You likely can't handle the general case, but that's a lot less critical. Especially for old consoles or computers where the pool of software with too complex cases that can't easily be handled with generic analysis is small enough that you can reasonably add special cases for most stuff you care about.
Before I looked at the article I immediately wondered how you were going to handle self-modifying code (running on the internal RAM of course). I guess you didn't encounter that situation?
Basically I embed an interpreter runtime and use it only when necessary, such as in the case when the program jumps to RAM.
Good point though. I should specifically mention self-modifying code.
Note that with NES games, self modifying code is uncommon, because programs are 32 KB ROM, and you only have 2KB RAM. So you'd have to first copy your subroutine from ROM to RAM, and then jump to it. And then you have that much less RAM to work with.
However, some of the emulator test ROMs[1] people have made use this technique to test every instruction.
I've been messing around with emscripten lately myself. Maybe I'll try it some time.
I mean essentially it would make NES games running natively in the browser with no emulator right?
As is, it supports Super Mario Bros. 1 only.
I don't know about the NES as I never had one, but on the C64 for example, a single cycle deviation in the emulation of interaction between the CPU, graphics chip and memory bus would make some effects impossible to reproduce. And similarly on the C64, people are still struggling to make the SID (sound) chip emulation as accurate as possible, as it used a combination of analogue filters that have proven extremely hard to accurately reproduce in emulation.
People casually testing these games might not care, but many of those of us who used these systems notice these flaws and appreciate that not all of the emulation projects focus only on speed.
For example, one such technique is to identify a section of code, make some
assumptions based on heuristics which allow for highly optimized native code
generation, and then detect if those assumptions are broken. If the assumptions
are broken, the generated native code is tossed, and emulation takes over.
However, if the assumptions are upheld, the recompiled block of code will
execute with blazing fast native speed.I also have a minor, minor nitpick on the article: I think you should point out that those INY instructions, in general, are insufficient to increase 16-bit pointers. You have to check for wraparound, and increase the high byte if a value wraps to zero. Somebody must have checked (or hoped) that that didn't happen with these tables (developing with the long, safe form and replacing it by the short form before release is tricky, as shortening the code will move entry points)
Modern hardware (GPU, sound cards,...) is also very similar to what you find on a PC so it would be more straightforward to port all this code. No messing around with the framebuffer mid-scanline to create a cool effect, no quirky special purpose hardware for very specific tasks.
So far as I know: this is unheard of with current gen consoles.
The most recent example I can think of is for a handheld console. The Pokemon Walker that was bundled with the newer Pokemon games for the Nintendo DS; which I believe has the IR hardware embedded in the cart itself.
So in addition to worrying about rather interesting use of the stock hardware, you also have to consider interesting use of _secondary_ hardware.
---
The latest batch of consoles [Xbox One, PS4] look to be x86 PCs with high-bandwidth memory; if that's the case, I'm hoping PC ports are more common, and perhaps we'll even see a virtualization based approach to running next gen games on standard PC hardware.
Games stopped embedding hardware when they went to discs. There is no way to put a parallel processor into a DVD.
Best you could do w/ current gen technolgy is bundle a dongle w/ the game, where the user plugs in some kind of co-processor through USB.
So far I haven't really seen anything like that -- the only USB dongles I've seen bundled w/ games are for games like RockBand and they're just RF receivers.
Aside from bandwidth concerns, and the poor sales of previous attempts (for e.g the SEGA's whole 32x/CD addon), there's nothing preventing a disc-based from having an external co-processor.
First, self-modifying code is still extremely present on modern consoles, at least on the current generation (PS3/X360/Wii/WiiU). Loading code from external media is basically the same problem as self-modifying code (statically recompiling it is trivially equivalent to solving the halting problem).
Second, modern hardware might be similar, but game consoles SDKs export a lot more features to the developers than PC drivers do through DX/GL. The example I take every time is fetch shaders on the WiiU: these are a kind of shaders supported by AMD R600 GPUs but completely abstracted by DX/GL.
Third, maybe there is no more mid-scanline framebuffer tricks, but you have a ton of other problems with the framebuffer: while a PC assumes separate CPU/GPU memory, on modern consoles the framebuffer (and a few textures) are often stored in memory that is shared and synchronized with both CPU and GPU. This is incredibly hard to emulate because a full GPU->CPU FB transfer induces a lot of latency (several hundreds of us last time I checked). IGPs and APUs make this problem a bit more manageable, but we're still missing the graphics API support for shared FB and shared textures.
Some things are better than older consoles but some other things are also a lot worse. JIT-ing shader bytecode is another problem that I don't think has been tackled yet (except maybe for Xbox emulation - which is still in its infancy and for a console using a very old GPU with no use of stuff like compute shaders).
Thank you so much for writing and posting this. You made my day.
It seems very well written, too.
Filed away into my magic "ZOMG INTERESTING PROJECT IDEA" folder :D
I guess one of the advantages of static recompilation is that you can port old games to new platforms if you hold the copyright of the game itself, but without running into issues with the manufacturer of the console (Nintendo)--but I might be wrong. You could also conceivably improve the game more easily during conversion (e.g., incorporate higher-resolution graphics). Finally, you could potentially have the resulting code distributed via app stores that do not allow general-purpose emulators.
It's a very interesting topic. It may be our best chance at preserving software.
It is impossible to solve this statically. This is why dynamic recompilation is more practical.
Sadly, emulation seems to be the way to go.
if (foo & 0x80 == 0x80) {
if (foo & 0x80) {
switch (mode) {
case FOO: ... break;
case BAR: ... break;
}
(Also, I think explicitly using comparison operators in conditionals might be the idiomatic thing to do in Go. Someone correct me here if I'm wrong about that.)
Consider that (foo & 0x80) is (0x16 == 0b00010000) if foo is 0x16.
(This may or may not be the intended functionality one way or the other!)
I never got past the reading phase.
Static recompilation seemed like an obvious solution to emulating games in theory, but it was fascinating to see just what it would take. Also loved to read about the clever tricks from 30 years ago and how we can or can't deal with them.
And look, the guy is not using any IDE or proprietary tools - just a terminal window and command line (what a horror!) tools. Looks like they are good enough..)
All that 9-to-5 Java coders should at least commit suicide.) More seriously - this is very clear illustration for startup founders of what a huge gap lies between mediocre and a top performer.
Convincing a top performer(s) to work for you is the real secret of a successful startup. Even pg (god forbid!) could be not so successful without rtm.))
And, except for code completion, there isn't anything an IDE can do that can't be done via the command line (just not as conveniently). Then again, I don't program in Java.