Sonic CD decompilation

Aw. I hope the technical details were at least an interesting read.

 

The following technical explanation is an attempt at demonstrating how close the decompiled C code is to the original, but that assumptions still had to be made because there is often more than one way to write something in C. Those assumptions were based on the debug information that we do have, but the assumption was also made that the programmers' code style was at least consistent within the same C source code file. This was not necessarily the case.

First, a quick summary of the debug information that each ELF file contains:

• Symbol Table (.symtab). Contains an index of function names and global variables. Ghidra can read this.
• DWARF Information (.debug). An index of all functions, global variables, local variables, and user-defined types. It even records the full path of the source code files (they're all under C:\project\GEMS\application\SonicCD\src\ps2\main\).
• DWARF Line Table (.line). If you've looked at the decompiled source code, you must have noticed that each line has a comment with the original line number and its associated memory address. Those were generated from this table, which contains the address of each function and an offset for each line of code. Essentially, this links chunks of ASM to lines.

Next, I'm going to explain how I could use the debug information to figure out what was originally written. I've tried to explain things clearly, but I'm not used to making detailed explanations like this.

Assignments

There's only one way to assign a value to a variable in C, so there's no ambiguity there. But when you do multiple assignments on one line, there is [ambiguity]. The most straight-forward way is to group multiple statements:

Code (C):

1. scrflaga.w = 0; scrflagb.w = 0; scrflagc.w = 0; scrflagz.w = 0;

Or you can make it one statement by replacing end statements ( ; ) with the comma operator:

Code (C):

1. scrflaga.w = 0, scrflagb.w = 0, scrflagc.w = 0, scrflagz.w = 0;

Or, if you're assigning the same value to all of them, you can chain them:

Code (C):

1. scrflaga.w = scrflagb.w = scrflagc.w = scrflagz.w = 0;

It is not possible to distinguish between the first two ways. Both will generate ASM like this:

Code (ASM):

1. lui          v0,hi(scrflaga)
2. sh           $0,lo(scrflaga)(v0)
3. lui          v0,hi(scrflagb)
4. sh           $0,lo(scrflagb)(v0)
5. lui          v0,hi(scrflagc)
6. sh           $0,lo(scrflagc)(v0)
7. lui          v0,hi(scrflagz)
8. sh           $0,lo(scrflagz)(v0)

However, chaining assignments generates distinct ASM:

Code (ASM):

1. lui          v0,hi(scrflagz)
2. sh           $0,lo(scrflagz)(v0)
3. andi         v1,$0,0xffff
4. lui          v0,hi(scrflagc)
5. sh           v1,lo(scrflagc)(v0)
6. andi         v1,v1,0xffff
7. lui          v0,hi(scrflagb)
8. sh           v1,lo(scrflagb)(v0)
9. andi         v1,v1,0xffff
10. lui          v0,hi(scrflaga)
11. sh           v1,lo(scrflaga)(v0)

The value is put into a register once, then the value is loaded from that register each time. (Note: MIPS has a dedicated register for the value zero, which is why it's not explicitly loaded into a register on the first assignment)

if statements

You can use the if statement in three ways for program flow. The most commonly used case is as follows:

Code (C):

1. if (d0 < 0) {
2.   d0 *= -1;
3. }

However, you can achieve the same result and ASM by inverting the condition and pairing it with a goto statement:

Code (C):

1. if (d0 >= 0) goto label1;
2. d0 *= -1;
3.  
4. label1:

If the if statement causes execution to jump to the end of the function if the condition is evaluated to false, you can also just return:

Code (C):

1. if (d0 >= 0) return;

As all of these result in the same ASM, I could only guess as to which was used.

As C is a structured programming language, I always tried the first approach first. Then I'd see if everything fit into the space reserved for the function (as I know exactly on which line its closing brace is).

For example, if there is only room for two lines, I can't do this:

Code (C):

1. function hello() {
2.   if (plflag != 0) {
3.     plflag = 0;
4.   }
5. }

I have to write it like this:

Code (C):

1. function hello() {
2.   if (plflag != 0)
3.     plflag = 0;
4. }

Of course, that's assuming they didn't do it like this:

Code (C):

1. function hello() {
2.   if (plflag != 0)
3.   { plflag = 0; }
4. }

In large functions, it happens that there's no room for the first if statement's closing brace. In that case, I have to invert the condition and return. This is the case in patset():

Code (C):

1. void patset() {
2.   /* LOCAL VARIABLES */
3.  
4.   if (lpKeepWork->GamePass != 0) return;
5.  
6.   linkdata = 0;
7.   for (i = 0; i < 8; ++i) {
8.  
9.     /* SNIP */
10.   }
11.  
12.   for (i = (unsigned short)linkdata; i < 80; ++i) {
13.     EAsprset(0, 0, 0, i, 0);
14.   }
15. }

The goto statement is used as a last resort, when I can't match the control flow using structured programming. The speedset function is a great example of this:

Code (C):

1. void speedset(sprite_status* pActwk) {
2.   int_union xpos, ypos;
3.   short_union spd;
4.  
5.   xpos.l = pActwk->xposi.l;
6.   ypos.l = pActwk->yposi.l;
7.   spd.w = pActwk->xspeed.w;
8.   xpos.l += spd.w << 8;
9.   spd.w = pActwk->yspeed.w;
10.   if (pActwk->actfree[2] & 8) goto label2;
11.   if (spd.w >= 0) goto label1;
12.   if (!(pActwk->actfree[2] & 2)) goto label1;
13.   if (pActwk->yspeed.w < -2048) goto label2;
14. label1:
15.   if (pActwk->actfree[2] & 4) goto label2;
16.   pActwk->yspeed.w += 56;
17. label2:
18.   if (pActwk->yspeed.w < 0) goto label3;
19.   if (pActwk->yspeed.w < 4096) goto label3;
20.   pActwk->yspeed.w = 4096;
21. label3:
22.   ypos.l += spd.w << 8;
23.   pActwk->xposi.l = xpos.l;
24.   pActwk->yposi.l = ypos.l;
25. }

As you can see, there are lots of if statements that redirect execution to the same locations, and there's no room for closing braces. And even if there was, I don't think you can reproduce the same flow using nested if ... else blocks. Speaking of those...

if ... else statements

Yes, I'm going to talk about this compound statement separately, because different forms lead to different ASM and line numbers.

Let's look at an example of the most common form:

Code (C):

1. if (pActwk->actfree[5] == knum) {
2.  
3.   pNewact->patno = 1;
4. }
5. else {
6.   pNewact->patno = 2;
7. }

Thanks to the debug info, I know the if statement made use of braces. This is because the closing brace is associated with a branch instruction that jumps execution to after the else block.

If you rewrite it like this:

Code (C):

1.  
2. if (pActwk->actfree[5] == knum)
3.   pNewact->patno = 1;
4.  
5. else {
6.   pNewact->patno = 2;
7. }
8.  

Then the branch instruction will be part of the "pNewact->patno = 1;" line.

There's no ASM associated with the closing brace of the else statement. So in the case that the block contained only one statement, I tried to be consistent with the if statement, if there was space.

Sometimes I had to squish things together like in the following example:

Code (C):

1. if (lenwk >= 0) {
2.   actwk[0].actfree[1] = 0;
3. } else {
4.   actwk[0].actfree[1] = 128;
5.   lenwk = -lenwk;
6. }

This is because there was no room to put the else statement on its own line, below the brace. If the else block had only one statement, I'd have been able to get away with this:

Code (C):

1. if (lenwk >= 0) {
2.   actwk[0].actfree[1] = 0;
3. }
4. else actwk[0].actfree[1] = 128;

Other flow control statements

The principle of having ASM associated with the closing brace applies to other control statements as well, like for loops and while loops.

Here's an example of a for loop:

Code (C):

1. for (i = 0; i < 128; ++i, ++pActwk) {
2.   if (pActwk->actno) {
3.  
4.     act_tbl[pActwk->actno - 1](pActwk);
5.   }
6.  
7. }

If there was a brace originally, there will be ASM associated with a line below the last statement of the for loop's body. This ASM will contain the instructions for the increment step of the loop, then the instructions for the condition step, with the destination of the branch being the first statement of the body.

If no brace was present, similar to the braceless if statement, this ASM will be associated with the sole line of the loop.

The while loop works the same, except that it has no increment step.

Finally, in most cases you can distinguish between for loops, while loops, and do while loops.

• The first line of a for loop will execute the init step, then branch to the condition step.
• A while loop will typically immediately branch to its condition logic, which is placed after the loop's body. However, it could be a for loop with an empty init step. In that case, you can recognise that it's a for loop when the closing brace is associated not only with a condition step, but an increment step as well.
• A do while loop does not branch to its condition logic. You could be decompiling a do while loop and not notice until you come across a condition that branches back to its start. Careful, though, because in some rare cases that doesn't mean there's a loop, and what you found was a goto statement that jumps back to an earlier point in the function.

Indentation style (braces)

Many a holy war has been fought over where to put opening braces. Do you put them on the same line as the opening statement (K&R), or by its own on the next line (Allman)?

As the K&R style is my preference, that's what I started out using. It also has the advantage of taking up less lines, meaning I didn't need to worry about needing a free line for the opening brace. However, there are plenty of places where there are blank lines after flow control statements that provide room for the Allman style opening brace. Opening braces never have ASM associated with them, so they could be placed wherever.

I decided that if the Allman style could be applied to all the code in the file, that's what it would use. As a result, there are plenty of files that use the Allman style, but they are still a minority. I know it's not consistent, but multiple programmers worked on the original code, and there's no guarantee that they were consistent themselves.

I'd also like to mention that, despite the K&R style being my preference, I preferred decompiling code that used the Allman style. Because consistent gaps in those files would tell me with some certainty where a flow control statement was used, and where an else statement was used.

Let me show you an example from the code for the boss of Palmtree Panic:

Code (C):

1. int egg1_01(sprite_status* pActwk) {
2.   scralim_right = 2752;
3.   scralim_n_right = 2752;
4.  
5.   if (actwk[0].xposi.w.h < 2666) return 1;
6.   if (actwk[0].xposi.w.h - 160 < scralim_left) return 1;
7.  
8.   if (actwk[0].xposi.w.h >= 2912)
9.   {
10.     pActwk->r_no0 = 12;
11.     scralim_right = 2752;
12.     scralim_n_right = 2752;
13.     scralim_left = 2752;
14.     scralim_n_left = 2752;
15.   }
16.   else
17.   {
18.     scralim_left = actwk[0].xposi.w.h - 160;
19.     scralim_n_left = actwk[0].xposi.w.h - 160;
20.   }
21.   return 1;
22. }

The first if statement doesn't have a gap after it, and the code that executes if the condition evaluates to true fills in a return value, so I knew for certain this wasn't the start of a block. The second if statement does have a gap after it, but as the following code also fills in a return value, there's no block here either.

What I really want to show is the third if statement and its accompanying else statement. Debug information shows where the statements making up the blocks are located, so there's no question about those. The closing brace of the if statement has a branch instruction associated to it, so we know it is there.

After the closing brace, however, there are two blank lines, which perfectly fit the start of an Allman style else block, where the else keyword is on its own line, and the opening brace is on its own line.

Conclusion

The debug information contained in the ELF files is so detailed that it made it possible to recreate the original source code with a high degree of accuracy, but in many parts it's only an approximation.

 

I've put what I've decompiled of the Windows PC version's executable so far in the WINEXE folder of the Git repo. I'm also attaching an export of all the labeling I've done. (Note: I don't know the proper way to mark functions in an export, so I've left those as "Function")

It's getting increasingly hard to move forward without introducing even more unknowns, so if you can help, it'd be appreciated.

 

NotABug.org is regularly unavailable for a short time. I shrugged it off because, hey, you get what you pay for, right? However, until a couple hours ago it was unavailable for at least a full day, preventing me from pushing my changes. That's not acceptable, and honestly I've had enough of the frequent downtime.

Moving forward, the Git repository will be hosted at sourcehut. You're expected to pay, but as it's officially still in alpha (but according to them already very stable and reliable) they tolerate free use. I'm going to use it for a bit first as an evaluation and then pay the very reasonable fee of 2 bucks a month.

I've already saved the useful wiki pages and will be hosting them at my personal website after translating them to clean HTML.

 

I've finally made time to create a page for the project at my personal website. Aside from a short description and the current status, it has the information that used to be featured on the wiki, with some changes:

• For the information on types, instead of listing which names were made up, I listed which were recorded in the debug information, as that list is much shorter.
  
• The missing symbols were condensed where appropriate, as there was a lot of duplication.

I didn't mention my decompilation of the Windows EXE because it's technically another project.

While making the page I discovered that there was one data file for R3 that wasn't filled in. That has been remedied.

 

Great to see someone else make an attempt at getting this to run!

Flexible array members are legal as of C99 by not specifying an array size, yet for some reason neither MinGW nor MWCC accept that for the array containing the list of objects for edit/debug mode.

As for static versus global, my understanding is that you can have one static and one global function with the same name, as they're in different scopes. Has that changed?

Finally, it is definitely possible that the decompilation has some inaccuracies left. Barring four inconsequential differences, the code compiles to the same MIPS assembly, but I was not able to match global variable addresses. Which means some writes or reads could be incorrect.

 

I'm back to decompiling SONICCD.EXE! So what if I don't understand the DINO2D graphics calls? There's still everything else to uncover!

Currently decompiling the function that's responsible for reading player input. It seems to build a bitfield variable of the same format as the Sonic games. Interestingly, despite only having one button (jump) in the game, it reads input for both A and B buttons.

 

With help from Chippy, a fellow reverse engineer, I've started properly decompiling SONICCD.EXE. You can follow the progress on decomp.me.

The program seems to have been compiled using Microsoft Visual Studio C++ 4.2. What I didn't expect was that the length of local variable names affects where they are put on the stack. It makes it a challenge to match the original assembly at times.

The first part of the executable contains functions related to CD audio playback, followed by some dummy assembly, so I've taken that to mean it's the end of a source file, put it all in CDAUDIO.C.

 

Decompilation is still on-going. A lot of graphics-related functions have been decompiled, and some global variables have been documented.

I've also had to look a bit more into both RDX/DINO DLLs, and can now confirm that DirectX is used. It looks like instead of converting Sonic CD to use DirectX directly, they still use the RDX libraries, which have been upgraded to use DirectX under the hood instead of DINO's own routines.

 

I've now decompiled all the code related to graphics operations. However, there are more than 10 functions where I wasn't able to match the original assembly exactly. I also have to wonder why some variables are a union type that allows them to be used either like a 4-byte integer or a 2-byte short.

Needless to say, without symbols or RDX documentation, the bulk of the code is a big question mark.

 

WINMAIN.C is now available! This houses the program's entrypoint (WinMain), the windows procedure (WndProc), and core logic.

 

Turns out the next file was a short one! Say hello to DECOMPRESS.C.

It has three functions: LZ decompression (using the Windows API), 4-bit bitmap conversion, and some other conversion that's done after the previous one that I haven't figured out yet.