6502.org Forum  Projects  Code  Documents  Tools  Forum
It is currently Fri Mar 29, 2024 10:06 am

All times are UTC




Post new topic Reply to topic  [ 98 posts ]  Go to page 1, 2, 3, 4, 5 ... 7  Next
Author Message
PostPosted: Tue Feb 26, 2019 10:40 am 
Offline
User avatar

Joined: Sat Feb 23, 2019 9:11 am
Posts: 38
With the proliferation of really good emulators for the Apple II, I have recently been re-introduced to the games I played decades ago. Then, in school, there were 6502 wizards who not only cracked the copy protection on those games but were actually able to understand and change them. Awesome! Since then it has always bugged me that I shied away from learning 6502 and diving into 8bit game design. I don't know why I have finally decided to try this myself, maybe it was just a critical mass thing. Anyways, here I am, all set.

I chose Robotron 2084 as a target for reverse engineering because I play it reasonably well and have very fond memories. An added advantage which might come in handy at a later point in the project is that Robotron is a well-researched game. There is 6502 source code available for the Williams coin-op system (where the game was officially launched) as well as for the Atari7400 and other platforms - - but not the Apple II.

From reverse engineering projects in other domains I know that it is never recommended to try to understand a target system completely. This rule certainly applies here, because
a) I basically don't know anything about the 6502
b) I owned an Apple II in the 80s but never understood the hardware.
c) I don't have a clue about game design

Apart from those pretty damning constraints, Robotron is a pretty big game, with a lot of stuff happening on screen. I have to be prepared that the inner workings of the software are pretty arcane and convoluted.

The starting point for the project was James Tauber's Apple II emulator (http://jtauber.com/applepy), written in Python. At this point I should add another one:
d) I am a Python newbie

Python knowledge is needed for a different project, expected to start towards the end of 2019. I think it is easier to learn a language with a good project and right now I can't think of any project being a better one than reverse engineering a 6502 game! :)

Reverse engineering generates a lot of data which has to be collected and correlated as easily as possible, which maybe makes the choice of using Python a bit more sensible. Note that I am not interested in a high fidelity recreation of Apple II artefacts, nor execution speed - - to achieve both I use the excellent https://en.wikipedia.org/wiki/AppleWin.

I had to port ApplyPy to Python 3, but else nothing else was needed to do a "first light" with running Robotron from the ram image.

The last couple of days I did the following:
    * read relevant sections of the Apple II Reference Manual (Woz, 1979)
    * understand 6502 opcodes and addressing modes
    * collect execution traces
    * collect info on memory locations (leap from/to info, touch counts etc.)
    * disassemble code with automatic labels and other leap info (who calls what)
    * intercept self-modifying code
    * link the emulator to Excel (via https://www.xlwings.org/
    * save/load complete state of 6502, memory, as well as Apple II display and softswitches

For now I focus exclusively on the splash screen part of the intro section of the game, that's difficult enough for its 600 lines of disassembled 6502 code.

The immediate goal is to map the execution flow for this very first part of the game. So far that has turned out considerably more difficult than expected, mainly because of "subroutines" PLA'ing the return addresses from the stack (i.e. mixing JSR and JMP), also PHA'ing different addresses and doing RTS more as a jump than as a return from subroutine. The whole idea of statically analysing the 6502 code seems a bit flawed, or it has to be at least complemented with runtime info.

Still, it has been possible to identify a bunch of "compact" subroutines: a contiguous stretche of executable 6502 code, leaped into the top by 1 or more JSRs, exit via normal RTS, no jumps from anywhere else into the middle of the stretches - - what I would call a "subroutine" in the normal sense. Call trees from those compact subroutines are directed acyclic graphs, which in turn will help me understand the execution flow.

The next step will be to establish which stretch of the code reads and writes certain memory locations, together with the particular addressing modes. Currently I am far too weak in 6502 to try to understand the code itself, just by reading it. I need more hints on what a stretch of instructions does. Of particular interest are the indirect-index / index-indirect instructions, because they shed light not only on the organisation of the overall memory but also on the meaning of zeropage addresses.

At this point I am looking for general advice on reverse engineering 6502 code.
    * How to generate sensible call trees for code which uses RTS as tabled jump facility?
    * Are there reverse engineering tools for 6502 code?
    * Are there any good books or other documention about reverse engineering 6502 out there?
    * What are common pitfalls when analysing 6502 code?
    * What are structures to look out for?
    * Is there value in trying to identify blocks of instructions and grouping them into macros, to speed up the understanding?

Thanks in advance for any pointers!

I intend to come back to this forum topic from time to time and add info on my progress. The project could very well be too ambitious for me, but I am looking forward to the challenges on the way.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 10:51 am 
Offline
User avatar

Joined: Sat Feb 23, 2019 9:11 am
Posts: 38
Here 2 images, one from AppleWin, showing the very first part of the Robotron intro, the other one a view on the Excel workbench - - just to give you an idea about what I am working with right now.


Attachments:
Splash1 (Workbench).jpg
Splash1 (Workbench).jpg [ 154.61 KiB | Viewed 3294 times ]
Splash1 (AppleWin).jpg
Splash1 (AppleWin).jpg [ 60.79 KiB | Viewed 3294 times ]
Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 12:24 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10760
Location: England
A grand adventure, and some interesting techniques. You've already met with the creative use of the stack: pushing and RTS is often used for a table-driven dispatch.

The only thing I can think of to look for is that sometimes conditional branches can be proved to be always taken, so they become branch-always - an opcode found on the 65C02 but not the 6502.

It's unusual to see more than one TXS in a program. I suppose that can work as a setjmp/longjmp, or a cold vs warm restart.

Very rarely you will see a tactic of arriving mid-way through a multi-byte instruction, such that the operand becomes an opcode. It can save a cycle, or a byte, or something, because it gives two paths to the code beyond it.

I think you're right to try to see how zero page is used - you'll find single bytes as values, pairs of bytes as values, and also find pairs of bytes acting as pointers.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 1:09 pm 
Offline
User avatar

Joined: Sat Feb 23, 2019 9:11 am
Posts: 38
That's interesting - - there are 4 TXS occuring in the Robotron code, 3 of visible in the screenshot, i.e. right at the beginning of the program. The code modifies itself by overwriting the initial part w/ NOP (not shown, I intercept this), so that's in line with your remarks on cold vs warm restart. In all 4 cases the stack pointer is set to #$3F, so it could be a protection scheme for variables on the stack page. Thanks for the hint.

Quote:
Very rarely you will see a tactic of arriving mid-way through a multi-byte instruction,

I've added a check to the emulator right away, to get a warning when the pc is set to a byte which I know served as operand for a previous operation. So far it looks like Robotron's developer has not used this trick. Unbelievable what you can do with the 6502 :)


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 1:19 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10760
Location: England
Oh, yes, self-modifying code - that can happen! Including the case of copying some code to zero-page and executing it, where it can self-modify itself even more efficiently.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 4:28 pm 
Offline

Joined: Sat Dec 13, 2003 3:37 pm
Posts: 1004
fschuhi wrote:
There is 6502 source code available for the Williams coin-op system

That's a real trick, being as Williams uses the 6809.
Quote:
Python knowledge is needed for a different project, expected to start towards the end of 2019. I think it is easier to learn a language with a good project and right now I can't think of any project being a better one than reverse engineering a 6502 game! :)

Personally, I learn a language by writing code, not reading it.

What are your overall goals from this project? What are you trying to learn, and what are you expecting this to teach you?
Quote:
At this point I am looking for general advice on reverse engineering 6502 code.
    * How to generate sensible call trees for code which uses RTS as tabled jump facility?
    * Are there reverse engineering tools for 6502 code?
    * Are there any good books or other documention about reverse engineering 6502 out there?
    * What are common pitfalls when analysing 6502 code?
    * What are structures to look out for?
    * Is there value in trying to identify blocks of instructions and grouping them into macros, to speed up the understanding?

Doesn't White Flame have a tracing disassembler on the web? That might be a start.

Before understanding the robotron code, you best understand the architecture of the Apple II. Notably things like the video hardware, the hows and whys of VBLANK, and screen syncing.

At a basic level games are broken in to two phases. The "doing" code, and the "drawing" code. "Doing" is the reading of controls, moving objects, checking for collisions, etc.

"Drawing" is rendering the graphics on the screen.

VBLANK is when the TV beam is moving from the bottom of the display back up to the top of the display. Many games do the bulk of the their drawing code during this time, because the developers know that whatever changes they make won't be visible. Otherwise, they are "racing the beam". Simply, there's an intimate relationship between what the electron beam of the monitor is doing and what the game is doing, so it's best to understand how that relationship is manifest on an Apple II (I have no idea), because then you can see how the code interacts with it. Many simple games did ALL of their work during VBLANK. But Robotron won't be simple.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 4:50 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10760
Location: England
> * Is there value in trying to identify blocks of instructions and grouping them into macros, to speed up the understanding?

I'd suspect not. Good names for routines and for locations will be a big help, and note that you might need to rename them too, as you figure things out. It's also possible that locations will be time-multiplexed so one location serves several temporary purposes.

The Apple II is relatively simple though, which will help. No interrupts, no custom chips with autonomous behaviour. The layout of video memory is non-obvious, and so any high-performance routines to update video memory may be quite clever.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 5:33 pm 
Offline

Joined: Mon May 21, 2018 8:09 pm
Posts: 1462
From a structural point of view, you may find that classifying subroutines into four classes will aid understanding:

1: Where there is no stack manipulation (PHA/PLA/PHP/PLP/TXS) between entry and RTS. You've already done this, I think. (In 65C02 code, you'd also look for PHX/PHY/PLX/PLY.)

2: Where there are pushes balanced by pops later in the same routine, and no manipulation of the stack beyond the level at entry.

3: Where there are pushes *not* fully balanced by pops before RTS, or return is via an RTI instead of RTS. This is one sign of "clever code" which will need deeper analysis.

4: Where there are pops of the return address *from* the stack. This is normally done to access "inline data" placed immediately after the entry JSR. Expect the address to be transferred to zero-page, incremented during access, and then used in an indirect-JMP for return. You should be able to decipher (or use trace data to observe) where the return actually ends up. The gap between there and the JSR will contain inline data which may be revealing (it may be ASCII text).

One good use of the fourth category is in Woz' Sweet16 bytecode interpreter, which I understand was included in the Apple ][ ROMs. There are listings and a discussion of Sweet16 in our documentation archives. If you encounter a call to Sweet16, you can decode the opcodes directly instead of puzzling over the interpreter itself.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 5:39 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10760
Location: England
Another thought, although I'm not sure what Apple II offers by way of a BRK handler, but it's possible you'll see the BRK opcode used as a software interrupt.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 7:33 pm 
Offline
User avatar

Joined: Sat Feb 23, 2019 9:11 am
Posts: 38
whartung wrote:
fschuhi wrote:
There is 6502 source code available for the Williams coin-op system

That's a real trick, being as Williams uses the 6809.


Just checked again, and of course you are right, that doesn't look like 6502 at all. The Atari code does, though, so at least that one might come handy. I wouldn't be surprised if it doesn't. The Apple II port was obviously done by Atari (at least it says so in the intro), so I might get something out of it when I try to understand certain parts of the Apple code.

Quote:
Personally, I learn a language by writing code, not reading it.

Yes, me too. Still, I like the idea of combining learning Python and learning about the 6502, plus learning about game design, using one of my favorite games from ages ago.

Quote:
What are your overall goals from this project? What are you trying to learn, and what are you expecting this to teach you?

I chose the "Nostalgia" board for a reason. It's a bit about revisiting the past and doing something I did not do then. The overall goal is therefore a bit fuzzy, and that's ok for now. At the same time I am really at awe when I see what developers are able to cram into, well, about 13k in the case of Robotron. There are a lot of lessons to learn, I'm sure.

Quote:
Doesn't White Flame have a tracing disassembler on the web? That might be a start.

I checked that out today, did also some reading in the WFDis thread on this board (thanks to White Flame pointing this out to me). That's for sure a great piece of software.

I'm working from a different position, though. WFDis is doing static analysis of the code, guided by manually hinting to where the code might be. I have it easier: I run the code with an emulator, so I know with certainty where the opcodes and their operands are. I am also able to resolve a lot of cases which are difficult (if not impossible) to infer from the code alone, e.g. detecting RTS jump tables and other stack-based wizardry. Because I know everything about the execution flow it is easy to annotate the assembly listing.

From one post from White Flame I have gleaned a nice idea, though. WFDis uses a "flooding" algorithm to try to detect the instructions to disassemble. This idea can be used to detect relocatable code, or what I called "compact subroutines" in the OP. Those are important building blocks and it's good to pinpoint them as early as possible.

I will have to dive deeper into WFDis, though, thanks for bringing this up.

Quote:
Before understanding the robotron code, you best understand the architecture of the Apple II. Notably things like the video hardware, the hows and whys of VBLANK, and screen syncing.

Great feedback! I have already downloaded a number of books on Apple II hardware and software. Particularly the display is a bit messy, due to weird addressing schemes of the colored hires pixels. Operating on sprite data directly in the display memory would be an algorithmic nightmare. But for the purpose of reverse engineering that's actually quite nice - - It's a certainly a bet, but I think the odds are in my favour that the developer of Robotron stored the sprite data somewhere else, in a more legible format. I already know the parts of the code which are responsible to throwing the stuff onto the screen, by watching which parts of the code STA to pages $20 and following. I don't know but I would guess that I'll find the LDA to the sprite tables in the vicinity.

It is certainly not the normal way to understand a target platform, you are right, but it might turn out to be a fun excercise. And don't get me wrong, it's certainly going to be much harder than I just outlined! :)

At least it looks like Robotron doesn't make use of VBLANK info, as it doesn't access the byte which indicates that the Apple II is in the vertical retrace region. Maybe I don't have to count cycles then.

Quote:
But Robotron won't be simple.

Yeah, thanks for reminding me ;)


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 7:39 pm 
Offline
User avatar

Joined: Sat Feb 23, 2019 9:11 am
Posts: 38
BigEd wrote:
Another thought, although I'm not sure what Apple II offers by way of a BRK handler, but it's possible you'll see the BRK opcode used as a software interrupt.

Thanks for making me aware about that. I think BRK on an Apple II does a hard reset - - it's of limited value on that platform. The Robotron code only uses BRK in one place: To close the door at the beginning of the code, so that the original init section is definitely never executed twice (i.e. overwrites the JMP at the top of the loaded image w/ a BRK).


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 7:56 pm 
Offline
User avatar

Joined: Sat Feb 23, 2019 9:11 am
Posts: 38
Chromatix wrote:
From a structural point of view, you may find that classifying subroutines into four classes will aid understanding:

Thank you, Chromatix, that's really good food for thought. I've actually identified your first 3 cases in the code, by checking the pairings between JSR'd stack addresses and what the next RTS finds on the stack. It is most often what can be expected from a "compact" subroutine. But not always:

Quote:
This is one sign of "clever code" which will need deeper analysis.

I'm a bit torn: should I focus on pulling the clever code apart, or focus on the easier (i.e. more "compact") code first? Right from the start, just in the first couple of dozen instructions there is some cleverness going on in the execution trace, obviously some initialisation code. I would like to have a organised approach for such sections, but that might not be possible. There will be code where I will have to decipher the execution flow manually.

Quote:
4: Where there are pops of the return address *from* the stack. This is normally done to access "inline data" placed immediately after the entry JSR. Expect the address to be transferred to zero-page, incremented during access, and then used in an indirect-JMP for return. You should be able to decipher (or use trace data to observe) where the return actually ends up. The gap between there and the JSR will contain inline data which may be revealing (it may be ASCII text).

That's exciting! Looking at the disassembly, it seems there are a number of candidate cases where something like this might be happening. The Robotron code does not contain any indirect JMPs, so I should expect RTS doing the trick. I'll keep this in mind.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 8:07 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10760
Location: England
I think for the most part you'll be able to understand the clever code so long as you can zoom out far enough to see the whole picture of what it's doing. If you do find anything you can't get your head around, I'm sure there are many here who would be more than pleased to have a 6502 puzzle to solve.

BTW, you might like this diagram of the 6502's architecture and instruction set:
viewtopic.php?p=42766#p42766


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 8:08 pm 
Offline
User avatar

Joined: Sat Feb 23, 2019 9:11 am
Posts: 38
BigEd wrote:
> * Is there value in trying to identify blocks of instructions and grouping them into macros, to speed up the understanding?

I'd suspect not. Good names for routines and for locations will be a big help, and note that you might need to rename them too, as you figure things out. It's also possible that locations will be time-multiplexed so one location serves several temporary purposes.

Well, I am usually tempted to turn everything into a domain-specific language. I should put more thought into a good annotation system, to mix automatically generated disassembly (containing trace / watch info) w/ my notes and comments. Thanks for your advice.

Quote:
The layout of video memory is non-obvious, and so any high-performance routines to update video memory may be quite clever.

I fear there will be a rude awakening from the current honeymoon period. Trying to understand what's happening in those video memory update routines might actually be too difficult for me, but it's worth a try.


Top
 Profile  
Reply with quote  
PostPosted: Tue Feb 26, 2019 8:20 pm 
Offline
User avatar

Joined: Sat Feb 23, 2019 9:11 am
Posts: 38
Quote:
BTW, you might like this diagram of the 6502's architecture and instruction set:

This site and this forum contains so much info, I'd like to drop out of work (and life in general) for a while and just read! :)

Is there a consensus on which 6502 book is the best? In school we were pointed to Zaks' "Programming the 6502", but it's quite verbose. Any love for Scanlon's "6502 Software Design"?

... Probably not the right place to ask this question. Which board should I check?


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 98 posts ]  Go to page 1, 2, 3, 4, 5 ... 7  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron