Writing a disassembler and tile editor...

Writing a disassembler and tile editor...
by Cheesemeister on 2009-02-06 (#42988)

Hello,

I've been lurking here for a bit, learning 6502 and poking around at some disassemblies, working up to taking on a from-scratch or mod project at some point. In the process of doing so, I've been writing my own disassembler and tile editor to help pick apart existing ROMs. Although it might just be a throwaway tool, it might be useful to folks with some feedback and further development.

As far as the disassembler goes, rather than simply dump the entire contents of the ROM into what may or may not be valid 6502 code, it traces the program's execution and tries to identify subroutine and data table symbols to create some meaningful output. Getting it to handle jumptables was interesting, but there are still many more spots in code that mislead the program, particularly with bank switching. What I'd like to do is have it do a "best effort" and then allow the user to interactively continue the disassembly when it gets stuck, then automatically continue the disassembly until it stops again. Symbols will be able to be named something more meaningful than the default "SR_0F_C000" and such. With a completed disassembly, it'd be able to accept code/data changes and re-compile with its symbol table.

As for the tile editor side of the program, right now I've just got it reading from the ROM and displaying either PRG or CHR data on the left-hand column and displaying various patterns of tiles on the right-hand side with whatever palette is selected. It won't be long before it can edit and save changes to the tile data. Here's a preview of what it currently looks like...

So my question for all of you is, would a tool like I've described be useful, and what kind of features would you like to see? Thanks!

Re: Writing a disassembler and tile editor...
by Hamtaro126 on 2009-02-07 (#42992)

Cheesemeister wrote:

As far as the disassembler goes, rather than simply dump the entire contents of the ROM into what may or may not be valid 6502 code, it traces the program's execution and tries to identify subroutine and data table symbols to create some meaningful output. Getting it to handle jumptables was interesting, but there are still many more spots in code that mislead the program, particularly with bank switching. What I'd like to do is have it do a "best effort" and then allow the user to interactively continue the disassembly when it gets stuck, then automatically continue the disassembly until it stops again. Symbols will be able to be named something more meaningful than the default "SR_0F_C000" and such. With a completed disassembly, it'd be able to accept code/data changes and re-compile with its symbol table.

. . . . . .

So my question for all of you is, would a tool like I've described be useful, and what kind of features would you like to see?

Do mind that the ''BEST, Automated'' disassemblies is made by:

#1: Generate the info from an selected (probably Super Mario 3/2US) ROM to FCEUABS by Beneficii at http://sm2.beneficii.net with Code Data Log format (*.CDL) and after enabling that, use the Address Use Logger format (*.AUL) Until you beat every part of the game

#2: Make the changes for both CDL and AUL Formats from FCEUABS are in your Disassembler, Then add a Option menu to select ROM size for each bank (Banks $01-$04, PRG-ROM 8000-FFFF)...

$2000 (NES 8k)
$4000 (NES 16k)
$8000 (NES 32k)

...Although the mapping in Bank $00, $6000-7FFF (8K only) is PRG-RAM, an optional 8k of ROM is offered in that range while using Mapper $69/FME7/Sunsoft-5b!

by Disch on 2009-02-07 (#43030)

I've made a disassembly of FF1 which had code and data serpated. To do it I had to make a custom emulator and disassembler and had play through the whole game to figure out which parts of the game were code and which were data (this was before FCEUXD was released -- so there was no existing code/data logger at the time). Even after that, the disassembly took quite a bit of manual editing to get to work right.

Something like this is a bigger job than you might be expecting, but I do think it's possible. Here are some (unorganized) ideas I've kicked around and thoughts I've had on the subject.

- tracing program flow will be straightforward for the most part. The two things to watch for would be branches and jump tables. For branches you can dump the state of the tracer into a list, take one path of the branch, and when it ends, restore the state and trace the other path.

- a path ends when either 1) you run into code that's already been marked as code. Or 2) you run into something that obviously isn't code (like, say, an 'illegal' opcode). In the case of #2, I would undo all the marking the path did since it 'split' (ie -- undo up to the last branch or whatever).

- jump tables can be very ugly, but most of them (99.99%) are stored one of two ways:

Code:
JumpTable: ;"type 1"
.word $8000, $9010, $A020

--or--

Jump_Lo: ;"type 2"
.byte $00, $10, $20

Jump_Hi:
.byte $80, $90, $A0

To handle jump tables, in addition to tracking the state of RAM when you trace through this code, you'll also need to keep track of where in ROM the RAM came from, for example:

Code:
LDA $20
ASL A
TAX
LDA $8000,X
STA $10
LDA $8001,X
STA $11
JMP ($0010)

Here, you'd have to track that the pointer at $10 came from $8000 and $8001. Since the high byte came from 1+ the low byte you could assume "type 1" jump table. Otherwise you could assume "type 2". Rather than attempt to figure out all the possible valeus of X when loading from this jump table, I say just keep reading pointers from the jump table until you find a path that 'obviously' isn't code (ie: illegal opcode) and stop running through the jump table at that point.

- As for bankswitching -- unless you want to code individual mapper nonsense, you could treat any jump to the $6000-FFFF range as a jump to potentially any 8K bank in the ROM. So, like you would branches or jump tables, you could fork into several paths (one in each 8K portion of the ROM) and filter out paths which are 'obviously' not code.

- You could check for special case always-branch scenarios like "LDA #0, BEQ somewhere" or "SEC, BCS somewhere" to cut down on the number of paths you have to test.

Anyway those were my ideas. Of course none of it is fullproof, and it fails to properly assign labels to data blocks, so you'd have to have things like "LDA $8000" instead of things like "LDA bnk05_8000" or somesuch, where labels are assigned. I've tried to think of a practical way to assign this stuff but it does get crazy complicated with bankswitching, and it's next to impossible to get indirect reads (LDA (blah),Y) all handled well.

by Cheesemeister on 2009-02-09 (#43131)

Thank you both for your thoughtful replies. I appreciate the info.

Hamtaro126 wrote:
Do mind that the ''BEST, Automated'' disassemblies is made by:

#1: Generate the info from an selected (probably Super Mario 3/2US) ROM to FCEUABS by Beneficii at http://sm2.beneficii.net with Code Data Log format (*.CDL) and after enabling that, use the Address Use Logger format (*.AUL) Until you beat every part of the game

#2: Make the changes for both CDL and AUL Formats from FCEUABS are in your Disassembler, Then add a Option menu to select ROM size for each bank (Banks $01-$04, PRG-ROM 8000-FFFF)...

$2000 (NES 8k)
$4000 (NES 16k)
$8000 (NES 32k)

...Although the mapping in Bank $00, $6000-7FFF (8K only) is PRG-RAM, an optional 8k of ROM is offered in that range while using Mapper $69/FME7/Sunsoft-5b!

I've noticed this feature in FCEU before, though the logs aren't quite human-readable. I may incorporate this style of logging in my program, use it to generate a generic symbol table, and paint the graphic representation of the bank on the left-hand side according to the access type. Even so, having to actually play through the game is less-than-ideal. My program identified over 89% of the bytes in DK, whereas FCEU logged over 95%. It's a start.

Disch wrote:
- tracing program flow will be straightforward for the most part. The two things to watch for would be branches and jump tables. For branches you can dump the state of the tracer into a list, take one path of the branch, and when it ends, restore the state and trace the other path.

- a path ends when either 1) you run into code that's already been marked as code. Or 2) you run into something that obviously isn't code (like, say, an 'illegal' opcode). In the case of #2, I would undo all the marking the path did since it 'split' (ie -- undo up to the last branch or whatever).

I've got that working for the most part.

Disch wrote:
- jump tables can be very ugly, but most of them (99.99%) are stored one of two ways

I'm glad to get some outside confirmation that's the case, though I want to avoid making assumptions about how the data is structured. Tracking the upper and lower bytes of addresses in the jump tables is now on my to-do list.

Disch wrote:
- As for bankswitching -- unless you want to code individual mapper nonsense, you could treat any jump to the $6000-FFFF range as a jump to potentially any 8K bank in the ROM. So, like you would branches or jump tables, you could fork into several paths (one in each 8K portion of the ROM) and filter out paths which are 'obviously' not code.

According to the documentation I see, $6000-$7FFF is generally for SRAM. Hamtaro said it's used in a few specialized mappers; perhaps I should only allow code checks along this range in these specific cases?

Disch wrote:
- You could check for special case always-branch scenarios like "LDA #0, BEQ somewhere" or "SEC, BCS somewhere" to cut down on the number of paths you have to test.

Right now, I'm detecting the end of control flow with RTI, RTS, JMP, and JSR. When the number of branches left to check reaches zero, I'm done with the subroutine. These cases could very easily be obfuscated by separating them from following one another, and would really have to be tested in the CPU simulator. I still want to add branch destination labeling in some sort of assembly style, but it's low-priority right now. I'm still undecided on which to use. Maybe I'll support them all. *shrug*

Disch wrote:
Anyway those were my ideas. Of course none of it is fullproof, and it fails to properly assign labels to data blocks, so you'd have to have things like "LDA $8000" instead of things like "LDA bnk05_8000" or somesuch, where labels are assigned. I've tried to think of a practical way to assign this stuff but it does get crazy complicated with bankswitching, and it's next to impossible to get indirect reads (LDA (blah),Y) all handled well.

Yeah, if I don't wander down that garden path of implementing bankswitch detection (like I experimented with on MMC1 to very limited success), I'd have to check each PRG bank for subroutines at the given addy. Even then, I'd get false positives in the form of stray bytes interpreted as immediate returns. Or I could land in the middle of an unintended subroutine. I'm sure some games are designed with corresponding subroutines sharing addresses in different banks. Obvious targets: $8000 and $C000, depending on which bank is being switched.

by Disch on 2009-02-09 (#43137)

Cheesemeister wrote:
According to the documentation I see, $6000-$7FFF is generally for SRAM. Hamtaro said it's used in a few specialized mappers; perhaps I should only allow code checks along this range in these specific cases?

I suppose. I was thinking it couldn't hurt to treat it as if ROM was always there. Because if you see something like "JSR $6800" then it must be code, right?

But then that got me to thinking/remembering of games like Zelda1 and Battletoads which copy code to RAM and jump to it. That might be a huge pain to handle.

Disch wrote:
Right now, I'm detecting the end of control flow with RTI, RTS, JMP, and JSR.

JSR? That wouldn't mark the end of a subroutine in any situation I can think of.

by Cheesemeister on 2009-02-09 (#43138)

Disch wrote:
JSR? That wouldn't mark the end of a subroutine in any situation I can think of.

Ah, right. It's been a long day. I'm also debating whether to recognize illegal opcodes as undocumented, or more likely just flag them as invalid and mark the end of a subroutine when preceded by a valid end, and mark the subroutine invalid when occurring abruptly.

by Dwedit on 2009-02-09 (#43139)

Beware the dreaded Puzznic double nop.

by Cheesemeister on 2009-02-09 (#43145)

Dwedit wrote:
Beware the dreaded Puzznic double nop.

Heh, that looks like a cute pitfall. It's special-case stuff like this that makes me want to do an incremental disassembly. I'm really not a fan of special-casing. Patch one thing and ten others break.

So when the disassembler stops, it currently spits out a nice report showing where all of the unidentified bytes are, and the number of bytes in the gap.

C11D ~ C126 (0x0A)
CA5A ~ CAA8 (0x4F)
CDD7 ~ CE0D (0x37)
CF8F ~ CFA7 (0x19)
...
0x393D bytes identified (89.43481%)
0x6C3 bytes unidentified (10.56519%)

It'd be fairly simple to wrap a GUI around this type of info to click on the gap and jump there and see what it would look like in data or code. Some of the gaps, of course, will just be empty -- easily detected -- or possibly filled with garbage data. But even just disambiguating a subroutine symbol to the correct bank would let the disassembler analyze another big chunk of code.

Am I way off-base?

by tepples on 2009-02-09 (#43146)

Cheesemeister wrote:
Dwedit wrote:
Beware the dreaded Puzznic double nop.

Heh, that looks like a cute pitfall.

As does this, no?

Quote:
It'd be fairly simple to wrap a GUI around [address ranges that the disassembler didn't reach] to click on the gap and jump there and see what it would look like in data or code. Some of the gaps, of course, will just be empty -- easily detected -- or possibly filled with garbage data. But even just disambiguating a subroutine symbol to the correct bank would let the disassembler analyze another big chunk of code.

Or perhaps have the GUI app cross-correlate it with a log from FCEU*.