13 ms·

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 cha

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.

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.