8 ms·

Statically Recompiling NES Games into Native Executables with LLVM and Go (2013)

356 points by dcschelt 11y ago

ZenPsycho 11y ago
I have actually been rather obsessed with this lately. You'll see that there's a few problems he runs into that he deems insurmountable, which sounds like a challenge! Specifically, there's the issue with an instruction which is effectively a computed goto: A jump instruction that takes an address and then jumps to the address STORED at that address. Since there is no way to know at compile time what addresses are going to stored at a place, you're forced to then dynamically emulate the whole memory space of the actual NES to accurately calculate it, thus defeating the whole point. Is that the only solution though? a head scratcher! Further are issues with parts of code that, on some level seems to be taking inspiration from genetics: Jump to one alignment, and the instructions get interpreted one way, jump to a different alignment and the same sequence of bytes is interpreted by the CPU as an entirely different set of instructions. I wonder if that could be resolved by creating a different source code path for each alignment using flow analysis- A space saving technique effectively getting uncompressed.
- stormbrew 11y ago
  I suppose it's possible this could be considered "emulating the whole memory space," though I wouldn't consider it that, but you could just generate an offset table for all jumpable memory locations and use them to calculate the correct offset. It's quite likely you could even do that in less than O(n) space with some time trade-offs.
  - devbug 11y ago
    TLB :)
  - ZenPsycho 11y ago
    I was commenting on my memory of the article. Upon rereading it, it seems the real insurmountable challenge is interrupts! It always seems like at that level of detail with this stuff, it becomes a decision to go slower in order to simulate NES hardware accurately. But my question is: how much code depends on that accuracy, and how much can you compromise for speed? A further question I have is can you do a cross game analysis of the whole NES library and find common patterns, reused functions, that you decompile into a kind of high level conversion that would hopefully or gloss over the need for specific functions to have that low level accuracy.
    - nathancahill 11y ago
      I had a fun time playing Prince of Persia on DOSBox. You can change the number of CPU cycles the emulator uses[0], which can cause interesting glitches when it executes too fast. [0] http://www.dosbox.com/wiki/Performance http://www.dosbox.com/wiki/Performance
    - jtolmar 11y ago
      I'm pretty sure Nesticle had nothing resembling accurate timing, and it could run most games. You can go well beyond several of the NES's limitations by fiddling with PPU parameters between scanlines, but that takes careful timing and almost nothing actually does that. Might only be democoders. If you're willing to ignore the possibility that someone did that, you should be able to just process a whole frame's worth of PPU at NMI time. Super Mario Bros spends most of its time in an infinite loop, waiting for NMI to pull it out so it can start processing the next frame. If NMI triggers before this, you get a lag frame. Plenty of popular emulators get the wrong lag frames, but only speedrunners and TASers really care. So, for this game, you could possibly toss out the timing entirely and trigger NMI when you hit a busy loop. Your emulator will completely ignore all lag frames, but most people won't notice for at least this game. (It's been over a decade since I was into ROM hacking so my memory could be faulty on any of this.)
      - Drakim 11y ago
        Interrupts need to be fairly accurate. Lots of games use them to have unmoving status bars, and rely on them triggering on just the right scanline.
        ZenPsycho 11y ago
        I wonder if for things that happen between and among scan lines, how difficult it would be to statically analyse the code to find out what's running during that time, and precalculate when the writes would fire. another approach could be getting runtime information from a running emulator, and record it onto a file the compiler could use to close the gaps you need but can't get from static analysis.
- webkike 11y ago
  Well clearly it is not impossible to recompile the program, perhaps by hand, into a different instruction set. Arguably this may be considered source to source translation. Sure it is hard, and there's no program that will EVER be able to do it automatically I assume. But that does not leave out the possibility of hand translation, which may prove an effective means by super skilled programmers of the future.
- onnoonno 11y ago
  Yes, it looks like the real problems occur (as also mentioned in his post) whenever encountering self-modifying code. I wonder whether it would be possible to detect and then either pattern match or manually resolve those cases of self-modifying code, in case they are few and contained to a small section of code each?
- gulpahum 11y ago
  One major problem are games which generate code into ram and then execute it. I can't remember if there were any NES games doing that, but I've seen other 6502 based games doing that.
  - Drakim 11y ago
    Maybe a tiny VM could be added just for runtime generated code. (but to be honest I don't think there is a single NES game that does that)
    - TickleSteve 11y ago
      dynamically generated code was quite a common technique in the era of 6502. Its frowned upon now, but it was a major optimisation technique back then.
      - Drakim 11y ago
        Do you have any resources on such techniques and tricks? I'm very much into 6502 from a NES background but I know little about dynamically generated code. I understand how it works, I just can't imagine what I would potentially use for it. :)
        woodman 11y ago
        The only potential practical use that I can think of, outside of procedurally generated decompression engines, is this: You find yourself on an uncharted desert island with two sailors, a movie star, some other lady, a millionaire and his wife... and a crate of 4k roms. For reasons that would take far too long to explain here - your only salvation is to recreate the Atari game catalog on your coconut game console.
        jerf 11y ago
        Speed. 6502s are 8-bit processors running in the neighborhood of 1MHz. Anything you can do to squeeze out a cycle is worth it. Rather than writing something that will repeatedly examine the data, and makes decisions, and then does things, write code that simply does things. Much faster, if you can spare the RAM for the code. Plus if you're really careful and clever, the code to "do things" can itself be the data! Sometimes, anyhow. Also, the world has changed a lot since then. Interpreters have less penalty on a modern chip than an old stupid chip, because branch prediction, prefetching, and multiple pipelines can really help with them, so it's relatively speaking cheaper to examine data and make decisions and the CPU will spend more time "doing things" as long as the data required and the branches taken are predictable, which they often are in this sort of code. And on the flip side, modern processors really want your code to be static, precisely so that all those optimizations can work well, along with code caches, micro-op caches, etc... constantly changing the code isn't good for performance on modern chips. The 6502 doesn't care how much the code is changing, it just executes the next opcode at the same speed regardless. Very different world.
- DannyBee 11y ago
  " Since there is no way to know at compile time what addresses are going to stored at a place" Why? This sounds like symbolic evaluation. You certainly can't know in all cases. But at worst, you can come up with the set of possible jump targets.
  - RodgerTheGreat 11y ago
    Part of the issue is that even with pretty fine-grained symbolic execution there are simple programming patterns which can induce the entire memory space, or a very large portion of it, as a possible jump target.
    - theoh 11y ago
      Are those patterns likely to be used, though? If one is detected, could the tool we're hypothesizing about inform a human who'd be able to understand what was going on? I'm always confused between symbolic evaluation and abstract interpretation but, according to Wikipedia, abstract interpretation is the more general term. I'd love to have the time and the ability to work on this kind of thing, up to and including partial evaluation. Really a lot of potential in this area, I think.
      - RodgerTheGreat 11y ago
        If you're really interested, the decompiler I built as part of this project performs a symbolic execution of programs for a very simple architecture and (conservatively) tracks the values which could reach registers at a given point in the program: https://github.com/JohnEarnest/Octo/blob/gh-pages/js/decompiler.js https://github.com/JohnEarnest/Octo/blob/gh-pages/js/decompi... I call the technique "register smearing" and it's only remotely feasible because Chip8 has lots of registers (if an accumulator was constantly being clobbered you wouldn't get much useful information) and programs are exceedingly small (<3.5kb). As you'd expect, for simple programs this works great and has even helped find bugs in some of the example Chip8 ROMs in the wild. However, it rapidly breaks down when you start working with memory-intensive programs or anything involving self-modifying code. There's still room for improvement, but at the end of the day you can't solve the halting problem and there is a diminishing return on greater complexity in your decompiler.
- gregpardo 11y ago
  Back in the romhacking scene we had emulators that the longer you would play through the more they could map out the entire assembly/data. I also had a friend who wrote a disassembler that used this information as well as some tasty algorithms to get a complete disassembly of SNES games.
- ris 11y ago
  "Since there is no way to know at compile time what addresses are going to stored at a place" Well, this is exactly what LLVM's (admittedly limited) mem2reg pass is for.
deleted 11y ago
[deleted]
orik 11y ago
here's the previous discussion: https://news.ycombinator.com/item?id=5838326 https://news.ycombinator.com/item?id=5838326 (i've realized; is this even necessary with the 'past' button?)
- Splines 11y ago
  I never knew there was a "past" button...
  - noobermin 11y ago
    Oh dear, I'm coming up on two and a half years on HN (time flies!) and I didn't know either...
    - boulos 11y ago
      Don't worry, it's recent and mostly just designed to help you figure out if you should flag an article as a dupe.
- hias 11y ago
  Never seen that button. Speaks for the UI designer, that a comment about a function is more visible than the function itself ;-) Just kidding, I am a fault for not looking right!
  - ZenoArrow 11y ago
    Whilst we're on the subject, there's another function you may have missed. If you've got showdead on (via your account settings) and you see a dead post or story that you thought was worth sharing, click on the timestamp by the post and click on the 'vouch' link there to suggest that it shouldn't be hidden.
- SixSigma 11y ago
  I should really be a bit more visible
andrewvijay 11y ago
Too low level for me. But since that I've started go as my first low level statically typed language, I think I'll just bookmark this article and may be read after a few years!
- spriggan3 11y ago
  > Too low level for me. But since that I've started go as my first low level statically typed language I don't think any garbage collected language can be called "low level". If you really want to go low level, learn C and ASM. Manual memory management is the real deal.
  - dkopi 11y ago
    I don't think any compiled or assembled language can be called "low level". If you really want to go low level, learn Machine code and CPU architecture. ... I don't think any executed language can be called low level. If you really want to go low level, learn hardware design, VHDL/VERLIOG ... I don't think any hardware description language can be called low level. If you really want to go low level, build your own logic gates out of transistors ...
    - lmm 11y ago
      Go is not appreciably more low level than e.g. Haskell though. It leaves out high level constructs but it doesn't offer you any more control to make up for it.
    - andrewvijay 11y ago
      Ha ha.
    - vvanders 11y ago
      Having done all 3 of those, anything that involves manual memory management counts as low level in my book.
    - daodedickinson 11y ago
      I'm with Nietzsche, the real low-level programming involves feeling new feelings and somehow communicating/philosophizing/programming them into other people.
madez 11y ago
I can’t help it. Reading this feels a bit like hidden political propaganda. It’s ridden with subtle and not so subtle negative references to gcc, the fsf and ideals. Probably it’s me reading too much into it but it makes it hard to enjoy.
gcc_programmer 11y ago
gcc -Wall -fno-diagnostics-color If you are going to list architectures supported, also list the ones gcc supports - it's, basically, all of them. Llvm+clang is nice, but not better, drink the kool aid. Gcc performance is still higher, and gcc is free software.
- techdragon 11y ago
  Clang is also free... Just not your preferred definition of Free.
  - gcc_programmer 11y ago
    Free as in free beer, not free as in free speech :P
    - over 11y ago
      The FSF considers BSD a free software license, it's just non-copyleft. There was a lot of discussion on Groklaw about taking BSD code, modifying it, and slapping a GPL license on top. I believe the consensus was this is OK, since you are still respecting the BSD license terms.
      - sgt101 11y ago
        also from http://www.gnu.org/philosophy/free-sw.en.html.. http://www.gnu.org/philosophy/free-sw.en.html... >Freedom 3 includes the freedom to release your modified versions as free software. A free license may also permit other ways of releasing them; in other words, it does not have to be a copyleft license. However, a license that requires modified versions to be nonfree does not qualify as a free license.
tibbon 11y ago
Does anyone have information with how some of the "multi cart" games worked, like Mario/Duck Hunt/Track Meet? Surely, all 3 games didn't fit in 32k right?... right? http://nintendo.wikia.com/wiki/3-in-1_Super_Mario_Bros._/_Duck_Hunt_/_World_Class_Track_Meet http://nintendo.wikia.com/wiki/3-in-1_Super_Mario_Bros._/_Du...
- jimsmart 11y ago
  An educated guess (having coded the NES) is that it's simply a bigger ROM, and the cart contained some kind of MMC chip [0] which allows different sections from the ROM to be paged-in - the menu screen contains the code to page-in the applicable bank from the ROM, and then the game runs per normal, not being aware of any of this. [0] https://en.wikipedia.org/wiki/Memory_management_controller https://en.wikipedia.org/wiki/Memory_management_controller

356 points by dcschelt 11y ago

I have actually been rather obsessed with this lately. You'll see that there's a few problems he runs into that he deems insurmountable, which sounds like a challenge! Specifically, there's the issue with an instruction which is effectively a computed goto: A jump instruction that takes an address and then jumps to the address STORED at that address. Since there is no way to know at compile time what addresses are going to stored at a place, you're forced to then dynamically emulate the whole memory space of the actual NES to accurately calculate it, thus defeating the whole point. Is that the only solution though? a head scratcher! Further are issues with parts of code that, on some level seems to be taking inspiration from genetics: Jump to one alignment, and the instructions get interpreted one way, jump to a different alignment and the same sequence of bytes is interpreted by the CPU as an entirely different set of instructions. I wonder if that could be resolved by creating a different source code path for each alignment using flow analysis- A space saving technique effectively getting uncompressed.

stormbrew 11y ago
I suppose it's possible this could be considered "emulating the whole memory space," though I wouldn't consider it that, but you could just generate an offset table for all jumpable memory locations and use them to calculate the correct offset. It's quite likely you could even do that in less than O(n) space with some time trade-offs.
- devbug 11y ago
  TLB :)
- ZenPsycho 11y ago
  I was commenting on my memory of the article. Upon rereading it, it seems the real insurmountable challenge is interrupts! It always seems like at that level of detail with this stuff, it becomes a decision to go slower in order to simulate NES hardware accurately. But my question is: how much code depends on that accuracy, and how much can you compromise for speed? A further question I have is can you do a cross game analysis of the whole NES library and find common patterns, reused functions, that you decompile into a kind of high level conversion that would hopefully or gloss over the need for specific functions to have that low level accuracy.
  - nathancahill 11y ago
    I had a fun time playing Prince of Persia on DOSBox. You can change the number of CPU cycles the emulator uses[0], which can cause interesting glitches when it executes too fast. [0] http://www.dosbox.com/wiki/Performance http://www.dosbox.com/wiki/Performance
  - jtolmar 11y ago
    I'm pretty sure Nesticle had nothing resembling accurate timing, and it could run most games. You can go well beyond several of the NES's limitations by fiddling with PPU parameters between scanlines, but that takes careful timing and almost nothing actually does that. Might only be democoders. If you're willing to ignore the possibility that someone did that, you should be able to just process a whole frame's worth of PPU at NMI time. Super Mario Bros spends most of its time in an infinite loop, waiting for NMI to pull it out so it can start processing the next frame. If NMI triggers before this, you get a lag frame. Plenty of popular emulators get the wrong lag frames, but only speedrunners and TASers really care. So, for this game, you could possibly toss out the timing entirely and trigger NMI when you hit a busy loop. Your emulator will completely ignore all lag frames, but most people won't notice for at least this game. (It's been over a decade since I was into ROM hacking so my memory could be faulty on any of this.)
    - Drakim 11y ago
      Interrupts need to be fairly accurate. Lots of games use them to have unmoving status bars, and rely on them triggering on just the right scanline.
      - ZenPsycho 11y ago
        I wonder if for things that happen between and among scan lines, how difficult it would be to statically analyse the code to find out what's running during that time, and precalculate when the writes would fire. another approach could be getting runtime information from a running emulator, and record it onto a file the compiler could use to close the gaps you need but can't get from static analysis.
webkike 11y ago
Well clearly it is not impossible to recompile the program, perhaps by hand, into a different instruction set. Arguably this may be considered source to source translation. Sure it is hard, and there's no program that will EVER be able to do it automatically I assume. But that does not leave out the possibility of hand translation, which may prove an effective means by super skilled programmers of the future.
onnoonno 11y ago
Yes, it looks like the real problems occur (as also mentioned in his post) whenever encountering self-modifying code. I wonder whether it would be possible to detect and then either pattern match or manually resolve those cases of self-modifying code, in case they are few and contained to a small section of code each?
gulpahum 11y ago
One major problem are games which generate code into ram and then execute it. I can't remember if there were any NES games doing that, but I've seen other 6502 based games doing that.
- Drakim 11y ago
  Maybe a tiny VM could be added just for runtime generated code. (but to be honest I don't think there is a single NES game that does that)
  - TickleSteve 11y ago
    dynamically generated code was quite a common technique in the era of 6502. Its frowned upon now, but it was a major optimisation technique back then.
    - Drakim 11y ago
      Do you have any resources on such techniques and tricks? I'm very much into 6502 from a NES background but I know little about dynamically generated code. I understand how it works, I just can't imagine what I would potentially use for it. :)
      - woodman 11y ago
        The only potential practical use that I can think of, outside of procedurally generated decompression engines, is this: You find yourself on an uncharted desert island with two sailors, a movie star, some other lady, a millionaire and his wife... and a crate of 4k roms. For reasons that would take far too long to explain here - your only salvation is to recreate the Atari game catalog on your coconut game console.
      - jerf 11y ago
        Speed. 6502s are 8-bit processors running in the neighborhood of 1MHz. Anything you can do to squeeze out a cycle is worth it. Rather than writing something that will repeatedly examine the data, and makes decisions, and then does things, write code that simply does things. Much faster, if you can spare the RAM for the code. Plus if you're really careful and clever, the code to "do things" can itself be the data! Sometimes, anyhow. Also, the world has changed a lot since then. Interpreters have less penalty on a modern chip than an old stupid chip, because branch prediction, prefetching, and multiple pipelines can really help with them, so it's relatively speaking cheaper to examine data and make decisions and the CPU will spend more time "doing things" as long as the data required and the branches taken are predictable, which they often are in this sort of code. And on the flip side, modern processors really want your code to be static, precisely so that all those optimizations can work well, along with code caches, micro-op caches, etc... constantly changing the code isn't good for performance on modern chips. The 6502 doesn't care how much the code is changing, it just executes the next opcode at the same speed regardless. Very different world.
DannyBee 11y ago
" Since there is no way to know at compile time what addresses are going to stored at a place" Why? This sounds like symbolic evaluation. You certainly can't know in all cases. But at worst, you can come up with the set of possible jump targets.
- RodgerTheGreat 11y ago
  Part of the issue is that even with pretty fine-grained symbolic execution there are simple programming patterns which can induce the entire memory space, or a very large portion of it, as a possible jump target.
  - theoh 11y ago
    Are those patterns likely to be used, though? If one is detected, could the tool we're hypothesizing about inform a human who'd be able to understand what was going on? I'm always confused between symbolic evaluation and abstract interpretation but, according to Wikipedia, abstract interpretation is the more general term. I'd love to have the time and the ability to work on this kind of thing, up to and including partial evaluation. Really a lot of potential in this area, I think.
    - RodgerTheGreat 11y ago
      If you're really interested, the decompiler I built as part of this project performs a symbolic execution of programs for a very simple architecture and (conservatively) tracks the values which could reach registers at a given point in the program: https://github.com/JohnEarnest/Octo/blob/gh-pages/js/decompiler.js https://github.com/JohnEarnest/Octo/blob/gh-pages/js/decompi... I call the technique "register smearing" and it's only remotely feasible because Chip8 has lots of registers (if an accumulator was constantly being clobbered you wouldn't get much useful information) and programs are exceedingly small (<3.5kb). As you'd expect, for simple programs this works great and has even helped find bugs in some of the example Chip8 ROMs in the wild. However, it rapidly breaks down when you start working with memory-intensive programs or anything involving self-modifying code. There's still room for improvement, but at the end of the day you can't solve the halting problem and there is a diminishing return on greater complexity in your decompiler.
gregpardo 11y ago
Back in the romhacking scene we had emulators that the longer you would play through the more they could map out the entire assembly/data. I also had a friend who wrote a disassembler that used this information as well as some tasty algorithms to get a complete disassembly of SNES games.
ris 11y ago
"Since there is no way to know at compile time what addresses are going to stored at a place" Well, this is exactly what LLVM's (admittedly limited) mem2reg pass is for.

deleted 11y ago

[deleted]

orik 11y ago

here's the previous discussion: https://news.ycombinator.com/item?id=5838326 https://news.ycombinator.com/item?id=5838326 (i've realized; is this even necessary with the 'past' button?)

Splines 11y ago
I never knew there was a "past" button...
- noobermin 11y ago
  Oh dear, I'm coming up on two and a half years on HN (time flies!) and I didn't know either...
  - boulos 11y ago
    Don't worry, it's recent and mostly just designed to help you figure out if you should flag an article as a dupe.
hias 11y ago
Never seen that button. Speaks for the UI designer, that a comment about a function is more visible than the function itself ;-) Just kidding, I am a fault for not looking right!
- ZenoArrow 11y ago
  Whilst we're on the subject, there's another function you may have missed. If you've got showdead on (via your account settings) and you see a dead post or story that you thought was worth sharing, click on the timestamp by the post and click on the 'vouch' link there to suggest that it shouldn't be hidden.
SixSigma 11y ago
I should really be a bit more visible

andrewvijay 11y ago

Too low level for me. But since that I've started go as my first low level statically typed language, I think I'll just bookmark this article and may be read after a few years!

spriggan3 11y ago
> Too low level for me. But since that I've started go as my first low level statically typed language I don't think any garbage collected language can be called "low level". If you really want to go low level, learn C and ASM. Manual memory management is the real deal.
- dkopi 11y ago
  I don't think any compiled or assembled language can be called "low level". If you really want to go low level, learn Machine code and CPU architecture. ... I don't think any executed language can be called low level. If you really want to go low level, learn hardware design, VHDL/VERLIOG ... I don't think any hardware description language can be called low level. If you really want to go low level, build your own logic gates out of transistors ...
  - lmm 11y ago
    Go is not appreciably more low level than e.g. Haskell though. It leaves out high level constructs but it doesn't offer you any more control to make up for it.
  - andrewvijay 11y ago
    Ha ha.
  - vvanders 11y ago
    Having done all 3 of those, anything that involves manual memory management counts as low level in my book.
  - daodedickinson 11y ago
    I'm with Nietzsche, the real low-level programming involves feeling new feelings and somehow communicating/philosophizing/programming them into other people.

madez 11y ago

I can’t help it. Reading this feels a bit like hidden political propaganda. It’s ridden with subtle and not so subtle negative references to gcc, the fsf and ideals. Probably it’s me reading too much into it but it makes it hard to enjoy.

gcc_programmer 11y ago

gcc -Wall -fno-diagnostics-color If you are going to list architectures supported, also list the ones gcc supports - it's, basically, all of them. Llvm+clang is nice, but not better, drink the kool aid. Gcc performance is still higher, and gcc is free software.

techdragon 11y ago
Clang is also free... Just not your preferred definition of Free.
- gcc_programmer 11y ago
  Free as in free beer, not free as in free speech :P
  - over 11y ago
    The FSF considers BSD a free software license, it's just non-copyleft. There was a lot of discussion on Groklaw about taking BSD code, modifying it, and slapping a GPL license on top. I believe the consensus was this is OK, since you are still respecting the BSD license terms.
    - sgt101 11y ago
      also from http://www.gnu.org/philosophy/free-sw.en.html.. http://www.gnu.org/philosophy/free-sw.en.html... >Freedom 3 includes the freedom to release your modified versions as free software. A free license may also permit other ways of releasing them; in other words, it does not have to be a copyleft license. However, a license that requires modified versions to be nonfree does not qualify as a free license.

tibbon 11y ago

Does anyone have information with how some of the "multi cart" games worked, like Mario/Duck Hunt/Track Meet? Surely, all 3 games didn't fit in 32k right?... right? http://nintendo.wikia.com/wiki/3-in-1_Super_Mario_Bros._/_Duck_Hunt_/_World_Class_Track_Meet http://nintendo.wikia.com/wiki/3-in-1_Super_Mario_Bros._/_Du...

jimsmart 11y ago
An educated guess (having coded the NES) is that it's simply a bigger ROM, and the cart contained some kind of MMC chip [0] which allows different sections from the ROM to be paged-in - the menu screen contains the code to page-in the applicable bank from the ROM, and then the game runs per normal, not being aware of any of this. [0] https://en.wikipedia.org/wiki/Memory_management_controller https://en.wikipedia.org/wiki/Memory_management_controller