Thursday, September 20, 2018

On the subject of bitwise operators in C#

This subject is a bit off-band for the blog, but I figured it could also double as a status update. The first draft of the object definitions is almost complete; only Death Egg Zone remains at the time of writing. After that, I'll probably go over the entire set and make everything a little bit more consistent, add a few more overlays here and there, etc. I'm currently aiming to get everything done early next month, so we'll see how that goes.

I've also made up my mind about what the focus of my hack will be, so I can't wait to jump on that as well. It's going to be a lot of work up front, but I'm hoping the payoff is worth it. Anyway, time for a rant.


As you may or may not be aware, SonLVL is programmed in C#. Due to this, the most powerful way of writing SonLVL object definitions is to just roll your own C# code against SonLVL's public API, which SonLVL then compiles on the fly by calling up the C# compiler at runtime.

This is good! C# is a great programming language, and one which I regularly work with in my day job, so being able to transfer my existing skill set certainly makes it easier on both sides.

Now, the greatest complexity in writing object definitions comes from wrangling subtypes. Apart from the X/Y flip flags, the subtype is the only way of instructing objects to serve up a different appearance or behavior. As such, more often than not, several different properties are packed into the individual bits of the subtype byte. And therein lies the rub: performing bitwise operations in C# is just sad.


Let's take, for example, the Automatic Tunnel object. These are the high speed chutes found in Launch Base Zone and Lava Reef Zone. They have three properties, which are encoded into the subtype as follows:

  • Bits 0-4 are the Path ID, which defines the set of waypoints the player will be sent through.
  • Bit 6 is the Launch flag; if set, the player will keep their momentum at the end of the tunnel.
  • Bit 7 is the Reverse flag; if set, the player will go through the waypoints in reverse order.
  • Bit 5 is unused.

Here's the above information in graphical form, because humans love graphics:
     0  0  0  0  0  0  0  0 

   Reverse     Launch     Path ID
Alright, so now let's say I want to have a property box where the user can change the path ID, without affecting the other flags. Sounds easy enough. Just blank out the path ID bits already in the subtype, truncate the user value to five bits, and join the two together. So let's write that.
    subtype = (subtype & 0xE0) | (value & 0x1F);
Hit compile and... compilation error. An expression of type int cannot be assigned to the variable subtype, which is of type byte. Oh right, the literals 0xE0 and 0x1F are of type int, so the AND operations are lifted to int: both subtype and value get promoted from byte to int and operator &(int a, int b) is called, which itself returns int. The two resulting ints are then ORed together, so the entire expression is of type int, which cannot be assigned to a variable of type byte.

There's actually no way to write a byte literal in C#; you are expected to cast the int literal to byte. The compiler will do the right thing and not insert a conversion operation, but work with byte from the start. So let's write that.
    subtype = (subtype & (byte)0xE0) | (value & (byte)0x1F);
Hit compile, same error. As it turns out...

Pain point #1: There are no bitwise operators defined on byte


It's not the literals, it's the operators! There actually isn't such a thing as byte operator &(byte a, byte b) in C#; they go down to int and that's it. So when we write subtype & (byte)0xE0, the compiler promotes both bytes to int and then calls int operator &(int a, int b), once again resulting in a subexpression of type int.

The same thing goes for the OR operator, so no matter how we slice it, the whole expression will always evaluate to int. So the correct solution is to cast that instead:
    subtype = (byte)((subtype & 0xE0) | (value & 0x1F));
It's already getting hard to read through all the parentheses, but it's only going to get worse.

Pain point #2: Bitwise operations do not return bool


Let's turn our attention to the flags. In the case of the Reverse flag, I want the user value to be a yes/no toggle, so value is a bool. Then, depending on whether the bool is true or not, we set the relevant bit to 1 or 0. Let's write that.
    subtype = (byte)((subtype & 0x7F) | (value ? 0x80 : 0x00));
Alright, relatively painless. But what about the reverse operation, where we look up the current subtype and figure out the current state of the Launch flag? This time we're assigning to value, which is of type bool. So we write
    value = subtype & 0x80;
which again results in a compilation error, this time stating that an expression of type int cannot be assigned to a variable of type bool.

This is because in C#, unlike C and C++ before it, bools are strongly typed. They can only hold the values true and false, which alleviates the situation where 1 and 2 both mean true, but compare differently to one another. But that means there's no quick way to write a bit test in C#; one must append either != 0 or == 0x80, the former a tautology, the latter a repetition.

Now, since the Reverse flag happens to be the most significant bit, we can sidestep the issue by instead writing:
    value = subtype >= 0x80;
But in the case of the Launch flag, imagine my surprise when I write
    value = subtype & 0x40 != 0;
and I get yet another compilation error: operator & cannot be applied to operands of type byte and bool.

Pain point #3: Bitwise operators are also logical operators


If the previous point was to get rid of legacy C bullcrap, then this one enshrines it. Early versions of C did not have the logical operators && and ||, so to combine two or more equality comparisons into a single conditional expression, you would use the bitwise operators & and |, like so:
    if (day == 25 & month == 12) printf("It's Christmas!\n");
In order for this kind of expression to evaluate correctly, bitwise operations were given lower precedence than equality comparisons, so that the program would first check that the day is 25, then that the month is December, before it combines the results and decides whether it's Christmas or not. When bitwise operators were added to the C# specification, their precedence was kept the same, presumably in order to avoid "gotcha" scenarios when porting over legacy C and C++ code.

So above, when we wrote
    value = subtype & 0x40 != 0;
what the compiler actually does is check 0x40 and 0 for equality, and then attempt to combine the result with the value of subtype, which is the complete opposite of what we were trying to accomplish!

The solution is, again, to add more parentheses to the expression:
    value = (subtype & 0x40) != 0;
But here's the kicker: since in C#, equality comparisons result in bool, not int, they had to introduce separate, eager logical operators &(bool a, bool b) and |(bool a, bool b) to go along with the to the existing short-circuiting logical operators &&(bool a, bool b) and ||(bool a, bool b). So they could have avoided this whole disaster by simply giving the eager logical operators a different notation from the bitwise operators! Grrr.

With all that parenthesizing, it's no surprise that we end up with code that looks a little something like this:
properties[2] = new PropertySpec("Launch", typeof(bool), "Extended",
    "If set, the player will launch off at the end of the path.", null,
    (obj) => (obj.SubType & 0x40) != 0,
    (obj, value) => obj.SubType = (byte)((obj.SubType & 0xBF) | ((bool)value ? 0x40 : 0)));

And that's just a little bit sad.

Update 27/02/2020: Eric Lippert expands on the last point over at his own blog. This post was mostly inspired by Eric's writings there and elsewhere on the the Internet, so being able to finally link back is incredibly delightful to me.

Monday, July 9, 2018

An overview of the new API features in SonLVL

Okay, here we go. As promised in my previous post, here's a rundown of all the features MainMemory has graciously added to SonLVL's API in order to support my ongoing object definition adventure.

Debug overlays: Like I hinted at in last week's post, objects now have the option of drawing a secondary sprite, which is rendered with high priority above all regular sprites and level blocks. The most basic use of this feature is to plot out the movement patterns of continuously moving objects, such as floating platforms.


Beyond that, I also made it so that objects which are configured to move to a predetermined position will plot out the location of their collision box at the end of their movement pattern.


Streamlined sprites: Under the hood, the sprite rendering code has been greatly improved, resulting in faster load times and smoother scrolling when compared to previous versions of SonLVL. Sprites are also refreshed more often now, allowing me to do crazy stuff such as have crushing objects automatically detect the floors and ceilings as you drag them around the level.


Depth and priority: SonLVL now considers VDP priority information when rendering the main level view: high priority level blocks will hide any overlapping sprites, unless they are also set to high priority. Objects can now also optionally report the sprite's SST priority value, known here as depth, for proper sorting between sprites.


Extra colors: Four additional color palettes are now available in each level. These are hidden in the editor, but can be used by sprites in order to render objects which normally overwrite one of the palette lines, such as bosses, as well as grant the Knuckles player start its proper coloring.


XML player starts: Player start markers can now be defined using a limited subset of the XML syntax for regular object defintions, allowing for custom poses in each level, as well as composite sprites where necessary.


Layout swap option: This is a big one. It allows level configurations to define a set of layout copy areas in its level layout, and then swap them into the main layout through a menu option. This is absolutely vital while editing LBZ1, but also quite useful in FBZ, and to a lesser extent AIZ1, LBZ2 and SOZ2.


Animated PLC support: Levels can now optionally load blocks of uncompressed art, which are then rendered in place of the placeholder blocks in the main level view, allowing for a level's animated tiles to be rendered as they appear in-game. This is a really big one because it's not useful for just Sonic 3; MainMemory has already gone ahead and added animated tiles to the Sonic 1 and 2 level configurations.


So that's where we stand. The whole thing is still a work in progress -- only the S3 levels are done at the moment. If you're feeling intrepid enough, you can always grab the current stuff from my personal Git repo; constructive feedback is highly appreciated if you have any.

Monday, July 2, 2018

What I've been up to this whole time

It's been a while, huh?

You may be wondering where the hell I've been. Unfortunately, progress on the hack is pretty much where I left it four months ago -- I've produced a couple of assets and had a couple new ideas, no doubt in part due to all the crazy Mania Plus stuff just around the corner -- but I seem to have a knack for getting into digressions which soon become much more work than anyone could have reasonably anticipated.

Case in point: right now, here's what your average Sonic 3 stage looks like when opened up in the SonLVL level editor:


Urgh. A bunch of floating question marks, the actual level layout covered by a brick wall, and to round it out, a couple of placeholder numerals hanging around near the corner.

Now, let's check out what the same section looks like when using my work-in-progress SonLVL configuration files:


OMG there's so much stuff to talk about in this screenshot.

What you're seeing here is the result of a semi-joint venture between the author of SonLVL, MainMemory and myself, with the goal of providing a complete set of SonLVL object definitions for Sonic 3 & Knuckles. Essentially, what that entails is reverse-engineering the original 68k code, and producing accurate representations of all the objects within the level editor.

This process can be further boiled down into three core points:
  1. Identify every object ID used in a given stage, and give each of them human-readable names;
  2. Document the effects of the subtype byte and the X/Y flip flags on the object's behavior and appearance, and provide a reasonable way for the user to view and modify these properties;
  3. Render a visual representation of the object, which should first and foremost be accurate to the object's in-game appearance, and if possible, illustrate the object's movement pattern as defined by its properties.

Let's focus on that last point. SonLVL already has a definition for Sonic 2's invisible block object, which highlights the object's actual size by drawing a yellow box around the rather unhelpful Tails block that appears in-game.


Upon porting this object to the Sonic 3 side of things, I quickly realized that a similar concept could be used to illustrate the alternating movement pattern of objects such as retracting spikes, thus making them stand out from their stationary brethren. Just draw the spikes at their "on" position, and the box at the "off" position!


There were two problems with this idea. Since the box was logically part of the object's sprite, you couldn't draw the spikes without the box, which ruined the map export feature. This wasn't an issue with the invisible block object, since its status as a "debug object" meant it didn't appear in the exported map anyway.

The other problem was that because the sprite was now twice as tall, so were the object's selection bounds!


Yuck!

No, if I was doing this, I was doing it right, which meant that somehow, I had to make SonLVL draw an optional "debug overlay" on top of an object's regular sprite. Luckily, I was already in talks with MainMemory at this point, and little did she know, I was about to make her work on SonLVL more than she had during the entire preceding year.

Next time, I'll go over all of the new features, and how I'm currently using them to make the Sonic 3 object definitions vastly superior to the ones available for previous titles.

Sunday, April 1, 2018

The many tendrils of a Sonic 3 level, part 3: hiding in plain sight

Have you ever been on an egg hunt, and ended up walking past the damn things multiple times without actually seeing them?

Shortly after the code for the animal object, at $2CA7C we run across the code for the title card object. The first thing it does in its init routine is check if the current zone is one of the Competition levels, and if so set byte $44 of its own SST.
Obj_TitleCardInit:
        cmpi.b  #$E,(Current_zone).w
        bcs.s   loc_2CA96
        cmpi.b  #$12,(Current_zone).w
        bhi.s   loc_2CA96
        st      $44(a0)
        jmp     (Delete_Current_Sprite).l
When this flag is set, various aspects of the object's behavior are changed in order to display a unique set of title cards in Competition mode. However, these are ultimately never shown, because the object calls the Delete_Current_Sprite function immediately after setting the flag.
loc_2CA96:
        ...
        lea     TitleCard_LevelGfx,a1
        moveq   #0,d0
        move.b  (Apparent_zone).w,d0
        lsl.w   #2,d0
        movea.l (a1,d0.w),a1
        move.w  #$A9A0,d2
        jsr     (Queue_Kos_Module).l
Shortly after, we find the code which loads the title card graphics. It uses the value of the apparent zone as an index to the TitleCard_LevelGfx array, which is a list of pointers to KosM-compressed archives containing the letters that spell out each zone's name:
TitleCard_LevelGfx:     dc.l ArtKosM_AIZTitleCard
                        dc.l ArtKosM_HCZTitleCard
                        dc.l ArtKosM_MGZTitleCard
                        dc.l ArtKosM_CNZTitleCard
                        dc.l ArtKosM_FBZTitleCard
                        dc.l ArtKosM_ICZTitleCard
                        dc.l ArtKosM_LBZTitleCard
                        dc.l ArtKosM_AIZTitleCard       ; MHZ
                        dc.l ArtKosM_AIZTitleCard       ; SOZ
                        dc.l ArtKosM_AIZTitleCard       ; LRZ
                        dc.l ArtKosM_AIZTitleCard       ; SSZ
                        dc.l ArtKosM_AIZTitleCard       ; DEZ
                        dc.l ArtKosM_AIZTitleCard       ; DDZ
                        dc.l ArtKosM_AIZTitleCard       ; HPZ
                        dc.l ArtKosM_ALZTitleCard
                        dc.l ArtKosM_BPZTitleCard
                        dc.l ArtKosM_DPZTitleCard
                        dc.l ArtKosM_CGZTitleCard
                        dc.l ArtKosM_EMZTitleCard
                        dc.l ArtKosM_BonusTitleCard
                        dc.l ArtKosM_BonusTitleCard
                        dc.l ArtKosM_BonusTitleCard
Then, at $2CC62, the apparent zone is used again, this time to inform the mapping frame used by the "name" portion of the title card:
Obj_TitleCardName:
        move.b  (Apparent_zone).w,d0
        add.b   d0,$22(a0)
The sprite mappings used by the title card object can be found at $2D90C. These mappings have the same layout as their Sonic & Knuckles counterparts, except the S&K stages all point at a blank mapping frame, and there's a mapping frame for the Competition mode title cards which was removed in Sonic & Knuckles.
Map_TitleCard:  dc.w Map_TitleCard_Blank-Map_TitleCard
                dc.w Map_TitleCard_Banner-Map_TitleCard
                dc.w Map_TitleCard_Act-Map_TitleCard
                dc.w Map_TitleCard_Zone-Map_TitleCard
                dc.w Map_TitleCard_AIZ-Map_TitleCard
                dc.w Map_TitleCard_HCZ-Map_TitleCard
                dc.w Map_TitleCard_MGZ-Map_TitleCard
                dc.w Map_TitleCard_CNZ-Map_TitleCard
                dc.w Map_TitleCard_FBZ-Map_TitleCard
                dc.w Map_TitleCard_ICZ-Map_TitleCard
                dc.w Map_TitleCard_LBZ-Map_TitleCard
                dc.w Map_TitleCard_Blank-Map_TitleCard  ; MHZ
                dc.w Map_TitleCard_Blank-Map_TitleCard  ; SOZ
                dc.w Map_TitleCard_Blank-Map_TitleCard  ; LRZ
                dc.w Map_TitleCard_Blank-Map_TitleCard  ; SSZ
                dc.w Map_TitleCard_Blank-Map_TitleCard  ; DEZ
                dc.w Map_TitleCard_Blank-Map_TitleCard  ; DDZ
                dc.w Map_TitleCard_Blank-Map_TitleCard  ; HPZ
                dc.w Map_TitleCard_2PMode-Map_TitleCard
                dc.w Map_TitleCard_Bonus-Map_TitleCard
                dc.w Map_TitleCard_Stage-Map_TitleCard
Note that both TitleCard_LevelGfx and Map_TitleCard contain valid entries for Flying Battery Zone, which is why we can get as far as displaying its title card in Sonic 3.

That's not why we're here, though. At $2CC08, right before being dismissed, the title card is responsible for loading the current level's KosM PLCs. It does this by calling the rather appropriately named LoadEnemyArt function:
LoadEnemyArt:
        lea     off_2DF60,a6
        move.w  (Apparent_zone_and_act).w,d0
        ror.b   #1,d0
        lsr.w   #6,d0
        adda.w  (a6,d0.w),a6
        move.w  (a6)+,d6
        bmi.s   locret_2DF5E

loc_2DF50:
        movea.l (a6)+,a1
        move.w  (a6)+,d2
        jsr     (Queue_Kos_Module).l
        dbf     d6,loc_2DF50

locret_2DF5E:
        rts
Once again, it uses the value of the apparent zone (and act) as an index to a pointer array, this time containing pointers to the KosM PLCs for each act in the game.

The thing is, much like TitleCard_LevelGfx and Map_TitleCard before it, this pointer array also contains valid entries for Flying Battery Zone:
off_2DF60:      dc.w PLCKosM_AIZ-off_2DF60
                dc.w PLCKosM_AIZ-off_2DF60
                dc.w PLCKosM_HCZ1-off_2DF60
                dc.w PLCKosM_HCZ2-off_2DF60
                dc.w PLCKosM_MGZ1-off_2DF60
                dc.w PLCKosM_MGZ2-off_2DF60
                dc.w PLCKosM_CNZ-off_2DF60
                dc.w PLCKosM_CNZ-off_2DF60
                dc.w PLCKosM_FBZ-off_2DF60
                dc.w PLCKosM_FBZ-off_2DF60
                dc.w PLCKosM_ICZ-off_2DF60
                dc.w PLCKosM_ICZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
                dc.w PLCKosM_LBZ-off_2DF60
Remember when I said the graphics for Flying Battery's enemies went out the door with the rest of the level load block?
PLCKosM_FBZ:    dc.w 1
                dc.l ArtKosM_Blaster
                dc.w $A000
                dc.l ArtKosM_Technosqueek
                dc.w $A500
Uh... April Fools!

The PAR code 02DF46:7010 will force every level to load Flying Battery Zone's KosM PLC. You can use this alongside the codes 05B58C:7010 and 05B5C2:7010 from my previous post in order to place the FBZ enemies in any level using debug mode. FBZ's palette is long gone (I checked), but luckily Carnival Night Zone's is a suitable replacement.

Friday, March 23, 2018

The many tendrils of a Sonic 3 level, part 2.5

Before we proceed any further in our analysis, a brief digression. On the subject of the Animate_Tiles function, reader Silver Sonic 1992 commented:
Lava Reef zone has some type of dynamically reloading tiles. Is it just garbage data?
I completely missed this the first time around. Amidst all the pointers to null routines, the Offs_AniFunc table actually contains a pointer to a properly-defined animation routine for Lava Reef Zone 1:
                 dc.w AnimateTiles_NULL-Offs_AniFunc
                 dc.w AniPLC_ALZ-Offs_AniFunc
                 dc.w AnimateTiles_LRZ1-Offs_AniFunc
                 dc.w AniPLC_ALZ-Offs_AniFunc
                 dc.w AnimateTiles_NULL-Offs_AniFunc
                 dc.w AniPLC_ALZ-Offs_AniFunc
Notably, apart from some tweaks to the target VRAM offsets to make the routine work also for act 2, as well as the fact that ArtUnc_AniLRZ__BG2 seemingly grew to 1.5x its size sometime after Sonic 3's release, the bulk of the routine is quite similar to the code found in Sonic & Knuckles:
AnimateTiles_LRZ1:                              AnimateTiles_LRZ1:
                                                    move.w  #$6400,d4
                                                    move.w  #$6880,d6
                                                    bra.s   loc_282D0
                                                ; ---------------------------------------------

                                                AnimateTiles_LRZ2:
                                                    move.w  #$6400,d4
                                                    move.w  #$6880,d6

                                                loc_282D0:
    lea     (Anim_Counters).w,a3                    lea     (Anim_Counters).w,a3
    moveq   #0,d0                                   moveq   #0,d0
    move.w  ($FFFFEEE4).w,d0                        move.w  ($FFFFEEE4).w,d0
    sub.w   (Camera_X_pos_BG_copy).w,d0             sub.w   (Camera_X_pos_BG_copy).w,d0
                                                    subq.w  #1,d0
    divu.w  #$30,d0                                 divu.w  #$30,d0
    swap    d0                                      swap    d0
    cmp.b   1(a3),d0                                cmp.b   1(a3),d0
    beq.s   loc_27440                               beq.s   loc_2833C
    move.b  d0,1(a3)                                move.b  d0,1(a3)
    moveq   #0,d1                                   moveq   #0,d1
    move.w  d0,d2                                   move.w  d0,d2
    andi.w  #7,d0                                   andi.w  #7,d0
    lsl.w   #7,d0                                   lsl.w   #7,d0
    move.w  d0,d1                                   move.w  d0,d1
    lsl.w   #3,d0                                   lsl.w   #3,d0
    add.w   d0,d1                                   add.w   d0,d1
    move.l  d1,d5                                   move.l  d1,d5
    andi.w  #$38,d2                                 andi.w  #$38,d2
    move.w  d2,d0                                   move.w  d2,d0
    lsl.w   #3,d2                                   lsl.w   #3,d2
    add.w   d2,d1                                   add.w   d2,d1
    add.w   d2,d2                                   add.w   d2,d2
    add.w   d2,d1                                   add.w   d2,d1
    lsr.w   #1,d0                                   lsr.w   #1,d0
    lea     word_27446(pc,d0.w),a4                  lea     word_2834C(pc,d0.w),a4
    lea     (ArtUnc_AniALZ).l,a0                    lea     (ArtUnc_AniLRZ__BG).l,a0
    move.w  #$6020,d4
    add.l   a0,d1                                   add.l   a0,d1
    move.w  d4,d2                                   move.w  d4,d2
    move.w  (a4)+,d3                                move.w  (a4)+,d3
    add.w   d3,d4                                   add.w   d3,d4
    add.w   d3,d4                                   add.w   d3,d4
    jsr     (Add_To_DMA_Queue).l                    jsr     (Add_To_DMA_Queue).l
    move.l  d5,d1                                   move.l  d5,d1
    add.l   a0,d1                                   add.l   a0,d1
    move.w  d4,d2                                   move.w  d4,d2
    move.w  (a4)+,d3                                move.w  (a4)+,d3
    beq.s   loc_27440                               beq.s   loc_2833C
    jsr     (Add_To_DMA_Queue).l                    jsr     (Add_To_DMA_Queue).l

loc_27440:                                      loc_2833C:
                                                    cmpi.b  #$16,(Current_zone).w
                                                    beq.s   locret_2834A
    addq.w  #2,a3                                   addq.w  #2,a3
    bra.w   loc_2745E                               bra.w   loc_28364
; --------------------------------------------- ; ---------------------------------------------

                                                locret_2834A:
                                                    rts
                                                ; ---------------------------------------------
word_27446:                                     word_2834C:
    dc.w  $240,     0                               dc.w  $240,     0
    dc.w  $1E0,   $60                               dc.w  $1E0,   $60
    dc.w  $180,   $C0                               dc.w  $180,   $C0
    dc.w  $120,  $120                               dc.w  $120,  $120
    dc.w   $C0,  $180                               dc.w   $C0,  $180
    dc.w   $60,  $1E0                               dc.w   $60,  $1E0
; --------------------------------------------- ; ---------------------------------------------

loc_2745E:                                      loc_28364:
    moveq   #0,d0                                   moveq   #0,d0
    move.w  ($FFFFEEE2).w,d0                        move.w  ($FFFFEEE2).w,d0
    sub.w   (Camera_X_pos_BG_copy).w,d0             sub.w   (Camera_X_pos_BG_copy).w,d0
    andi.w  #$1F,d0                                 andi.w  #$1F,d0
    cmp.b   1(a3),d0                                cmp.b   1(a3),d0
    beq.s   locret_274BE                            beq.s   loc_283CC
    move.b  d0,1(a3)                                move.b  d0,1(a3)
    moveq   #0,d1                                   moveq   #0,d1
    move.w  d0,d2                                   move.w  d0,d2
    andi.w  #7,d0                                   andi.w  #7,d0
    lsl.w   #8,d0                                   lsl.w   #7,d0
                                                    move.w  d0,d1
                                                    add.w   d0,d0
                                                    add.w   d1,d0
    move.w  d0,d1                                   move.w  d0,d1
    move.l  d1,d5                                   move.l  d1,d5
    andi.w  #$18,d2                                 andi.w  #$18,d2
    move.w  d2,d0                                   move.w  d2,d0
    lsl.w   #3,d2                                   lsl.w   #2,d2
                                                    add.w   d2,d1
                                                    add.w   d2,d2
    add.w   d2,d1                                   add.w   d2,d1
    lsr.w   #1,d0                                   lsr.w   #1,d0
    lea     word_274C0(pc,d0.w),a4                  lea     word_283D2(pc,d0.w),a4
    lea     (ArtUnc_AniALZ).l,a0                    lea     (ArtUnc_AniLRZ__BG2).l,a0
    move.w  #$64A0,d4                               move.w  d6,d4
    add.l   a0,d1                                   add.l   a0,d1
    move.w  d4,d2                                   move.w  d4,d2
    move.w  (a4)+,d3                                move.w  (a4)+,d3
    add.w   d3,d4                                   add.w   d3,d4
    add.w   d3,d4                                   add.w   d3,d4
    jsr     (Add_To_DMA_Queue).l                    jsr     (Add_To_DMA_Queue).l
    move.l  d5,d1                                   move.l  d5,d1
    add.l   a0,d1                                   add.l   a0,d1
    move.w  d4,d2                                   move.w  d4,d2
    move.w  (a4)+,d3                                move.w  (a4)+,d3
    beq.s   locret_274BE                            beq.s   loc_283CC
    jsr     (Add_To_DMA_Queue).l                    jsr     (Add_To_DMA_Queue).l

locret_274BE:                                   loc_283CC:
                                                    addq.w  #2,a3
    rts                                             bra.w   loc_286E8
; --------------------------------------------- ; ---------------------------------------------
word_274C0:                                     word_283D2:
    dc.w   $80,     0                               dc.w   $C0,     0
    dc.w   $60,   $20                               dc.w   $90,   $30
    dc.w   $40,   $40                               dc.w   $60,   $60
    dc.w   $20,   $60                               dc.w   $30,   $90
; --------------------------------------------- ; ---------------------------------------------
Much like what happened with the level load block though, the uncompressed art used by this routine was completely wiped from the Sonic 3 ROM, leaving the code pointing at whatever data came next. In this case it's ArtUnc_AniALZ, which is uncompressed art normally used by Azure Lake's animation routine.

Friday, March 16, 2018

The many tendrils of a Sonic 3 level, part 2: the animal exchange

Picking up from where we left off, at $2BD98 we come across the Obj_Animal object, which as we learned before, is the small animal that spawns both from a defeated enemy and from an act 2 end capsule. And right at the start of its code, we find this seemingly innocuous byte array:
byte_2BDDA: dc.b 5, 1
            dc.b 0, 3
            dc.b 5, 1
            dc.b 0, 5
            dc.b 6, 5
            dc.b 2, 3
            dc.b 6, 1
            dc.b 6, 5
            dc.b 6, 5
            dc.b 6, 5
            dc.b 6, 5
            dc.b 6, 5
            dc.b 6, 5
This is actually a very dangerous byte array! When the animal object is first initialized, it uses the value of the current zone, plus the value in register d0 (which is randomly set to either 0 or 1), to index the byte_2BDDA array, and put the resulting byte into offset $30 of its own SST:
loc_2BF4A:
    moveq   #0,d1
    move.b  (Current_zone).w,d1
    add.w   d1,d1
    add.w   d0,d1
    lea     byte_2BDDA,a1
    move.b  (a1,d1.w),d0
    move.b  d0,$30(a0)
Then at loc_2BFEA, after the animal first lands on the floor, it feeds this value into the routine counter at offset 5 of its own SST, in order to determine whether it should hop or fly away:
    move.b  $30(a0),d0
    add.b   d0,d0
    addq.b  #4,d0
    move.b  d0,5(a0)
It is therefore vital that the byte_2BDDA array contain two entries for each level in the game, as these determine which two animals may spawn in any given stage. With Sonic 3 in particular, every stage past Launch Base Zone reuses the same animal combination as Flying Battery Zone. In Sonic & Knuckles, only Doomsday Zone retains this property.
byte_2BDDA: dc.b 5, 1  ; AIZ                    byte_2C7BA: dc.b 5, 1  ; AIZ
            dc.b 0, 3  ; HCZ                                dc.b 0, 3  ; HCZ
            dc.b 5, 1  ; MGZ                                dc.b 5, 1  ; MGZ
            dc.b 0, 5  ; CNZ                                dc.b 0, 5  ; CNZ
            dc.b 6, 5  ; FBZ                                dc.b 6, 5  ; FBZ
            dc.b 2, 3  ; ICZ                                dc.b 2, 3  ; ICZ
            dc.b 6, 1  ; LBZ                                dc.b 5, 1  ; LBZ
            dc.b 6, 5  ; MHZ                                dc.b 6, 1  ; MHZ
            dc.b 6, 5  ; SOZ                                dc.b 0, 1  ; SOZ
            dc.b 6, 5  ; LRZ                                dc.b 5, 1  ; LRZ
            dc.b 6, 5  ; SSZ                                dc.b 0, 5  ; SSZ
            dc.b 6, 5  ; DEZ                                dc.b 6, 1  ; DEZ
            dc.b 6, 5  ; DDZ                                dc.b 6, 5  ; DDZ
                                                            dc.b 5, 1  ; Ending
                                                            dc.b 5, 1  ; ALZ
                                                            dc.b 5, 1  ; BPZ
                                                            dc.b 5, 1  ; DPZ
                                                            dc.b 5, 1  ; CGZ
                                                            dc.b 5, 1  ; EMZ
                                                            dc.b 5, 1  ; Gumball
                                                            dc.b 5, 1  ; Pachinko
                                                            dc.b 5, 1  ; Slots
                                                            dc.b 5, 1  ; LRZ Boss
                                                            dc.b 5, 1  ; DEZ Boss
Interestingly, in Sonic & Knuckles, the array was extended to cover every level slot, rather than stopping at Doomsday Zone. This was probably done for the sake of the Lava Reef Zone boss act, in which animals spawn from the capsule at the very end of the stage. Indeed, if we look at the numbers, all of the new entries in the array use the same animal combination as Lava Reef Zone.

The length of this array in Sonic 3 suggests that attempting to load any level slot beyond Doomsday Zone is inherently dangerous. But in reality, it only becomes a problem if an animal is spawned while playing the stage; it shouldn't affect whether the stage can load or not.

What does affect it are the animals' graphics, which are loaded by the PLCLoad_AnimalsAndExplosion function at $543F4 when the level starts. Much like the animal object, it uses the value of the current zone as an offset to an array, which contains pointers to the PLCs for each stage's combination of animals.

And therein lies the rub, because in Sonic 3, this array only goes up to Launch Base Zone:
off_54414:  dc.w PLC_54422-off_54414  ; AIZ     off_85FFE:  dc.w PLC_8602E-off_85FFE  ; AIZ
            dc.w PLC_54430-off_54414  ; HCZ                 dc.w PLC_8603C-off_85FFE  ; HCZ
            dc.w PLC_5443E-off_54414  ; MGZ                 dc.w PLC_8604A-off_85FFE  ; MGZ
            dc.w PLC_5444C-off_54414  ; CNZ                 dc.w PLC_86058-off_85FFE  ; CNZ
            dc.w PLC_5445A-off_54414  ; FBZ                 dc.w PLC_86066-off_85FFE  ; FBZ
            dc.w PLC_54468-off_54414  ; ICZ                 dc.w PLC_86074-off_85FFE  ; ICZ
            dc.w PLC_54476-off_54414  ; LBZ                 dc.w PLC_86082-off_85FFE  ; LBZ
                                                            dc.w PLC_86090-off_85FFE  ; MHZ
                                                            dc.w PLC_8609E-off_85FFE  ; SOZ
                                                            dc.w PLC_860AC-off_85FFE  ; LRZ
                                                            dc.w PLC_860BA-off_85FFE  ; SSZ
                                                            dc.w PLC_860C8-off_85FFE  ; DEZ
                                                            dc.w PLC_860D6-off_85FFE  ; DDZ
                                                            dc.w PLC_860E4-off_85FFE  ; Ending
                                                            dc.w PLC_860E4-off_85FFE  ; ALZ
                                                            dc.w PLC_860E4-off_85FFE  ; BPZ
                                                            dc.w PLC_860E4-off_85FFE  ; DPZ
                                                            dc.w PLC_860E4-off_85FFE  ; CGZ
                                                            dc.w PLC_860E4-off_85FFE  ; EMZ
                                                            dc.w PLC_860E4-off_85FFE  ; Gumball
                                                            dc.w PLC_860E4-off_85FFE  ; Pachinko
                                                            dc.w PLC_860E4-off_85FFE  ; Slots
                                                            dc.w PLC_860E4-off_85FFE  ; LRZ Boss
                                                            dc.w PLC_860E4-off_85FFE  ; DEZ Boss
PLC_54422:  dc.w 1                              PLC_8602E:  dc.w 1
            dc.l ArtNem_BlueFlicky                          dc.l ArtNem_BlueFlicky
            dc.w $B000                                      dc.w $B000
            dc.l ArtNem_Chicken                             dc.l ArtNem_Chicken
            dc.w $B240                                      dc.w $B240
PLC_54430:  dc.w 1                              PLC_8603C:  dc.w 1
            dc.l ArtNem_Rabbit                              dc.l ArtNem_Rabbit
            dc.w $B000                                      dc.w $B000
            dc.l ArtNem_Seal                                dc.l ArtNem_Seal
            dc.w $B240                                      dc.w $B240
PLC_5443E:  dc.w 1                              PLC_8604A:  dc.w 1
            dc.l ArtNem_BlueFlicky                          dc.l ArtNem_BlueFlicky
            dc.w $B000                                      dc.w $B000
            dc.l ArtNem_Chicken                             dc.l ArtNem_Chicken
            dc.w $B240                                      dc.w $B240
PLC_5444C:  dc.w 1                              PLC_86058:  dc.w 1
            dc.l ArtNem_Rabbit                              dc.l ArtNem_Rabbit
            dc.w $B000                                      dc.w $B000
            dc.l ArtNem_BlueFlicky                          dc.l ArtNem_BlueFlicky
            dc.w $B240                                      dc.w $B240
PLC_5445A:  dc.w 1                              PLC_86066:  dc.w 1
            dc.l ArtNem_Squirrel                            dc.l ArtNem_Squirrel
            dc.w $B000                                      dc.w $B000
            dc.l ArtNem_BlueFlicky                          dc.l ArtNem_BlueFlicky
            dc.w $B240                                      dc.w $B240
PLC_54468:  dc.w 1                              PLC_86074:  dc.w 1
            dc.l ArtNem_Penguin                             dc.l ArtNem_Penguin
            dc.w $B000                                      dc.w $B000
            dc.l ArtNem_Seal                                dc.l ArtNem_Seal
            dc.w $B240                                      dc.w $B240
PLC_54476:  dc.w 1                              PLC_86082:  dc.w 1
            dc.l ArtNem_Squirrel                            dc.l ArtNem_BlueFlicky
            dc.w $B000                                      dc.w $B000
            dc.l ArtNem_Chicken                             dc.l ArtNem_Chicken
            dc.w $B240                                      dc.w $B240
                                                PLC_86090:  dc.w 1
                                                            dc.l ArtNem_Squirrel
                                                            dc.w $B000
                                                            dc.l ArtNem_Chicken
                                                            dc.w $B240
                                                PLC_8609E:  dc.w 1
                                                            dc.l ArtNem_Rabbit
                                                            dc.w $B000
                                                            dc.l ArtNem_Chicken
                                                            dc.w $B240
                                                PLC_860AC:  dc.w 1
                                                            dc.l ArtNem_BlueFlicky
                                                            dc.w $B000
                                                            dc.l ArtNem_Chicken
                                                            dc.w $B240
                                                PLC_860BA:  dc.w 1
                                                            dc.l ArtNem_Rabbit
                                                            dc.w $B000
                                                            dc.l ArtNem_Chicken
                                                            dc.w $B240
                                                PLC_860C8:  dc.w 1
                                                            dc.l ArtNem_Squirrel
                                                            dc.w $B000
                                                            dc.l ArtNem_Chicken
                                                            dc.w $B240
                                                PLC_860D6:  dc.w 1
                                                            dc.l ArtNem_Squirrel
                                                            dc.w $B000
                                                            dc.l ArtNem_Chicken
                                                            dc.w $B240
                                                PLC_860E4:  dc.w 1
                                                            dc.l ArtNem_BlueFlicky
                                                            dc.w $B000
                                                            dc.l ArtNem_Chicken
                                                            dc.w $B240
So even if we were to fix up the level load block for the Sonic & Knuckles stages, the PLCLoad_AnimalsAndExplosion function would then take the value of the current zone, go past the end of the pointer array straight into the actual PLC definitions, and eventually attempt to load a nonsensical PLC, which would most definitely crash the game. Huzzah!
PLC_54476:  dc.w 1                              PLC_86082:  dc.w 1
            dc.l ArtNem_Squirrel                            dc.l ArtNem_BlueFlicky
            dc.w $B000                                      dc.w $B000
            dc.l ArtNem_Chicken                             dc.l ArtNem_Chicken
            dc.w $B240                                      dc.w $B240
It was only by looking at the animal data side-by-side like this that I stumbled upon one of the most obscure differences between Sonic 3 and Sonic & Knuckles that I know of. In Sonic 3, the animals which appear in Launch Base Zone are Ricky (the squirrel) and Cucky (the chicken). In Sonic & Knuckles however, Ricky was replaced by Flicky (the flicky).

This wasn't an accident; if you check the byte_2BDDA array at the top of this post, you'll see that the animal type was changed from 6 to 5 there, too.


Finally, on the subject of animal types, here's something that always bugged me. In Sonic 1, there were seven different animals. From left to right, they are: Pocky, Cucky, Pecky, Rocky, Picky, Flicky and Ricky.


Sonic 2 then added five more, whose names I can't find a source for: an eagle, a mouse, a monkey, a turtle and a bear.


When it came time to make Sonic 3, the developers decided to scale back to the original cast of animals. Indeed, if you look at the byte_2BDDA array, you'll find that they're numbered 0 through 6... but animal 4 is nowhere to be seen.


Picky appears to have disappeared; not even his graphics can be found within the ROM. Maybe he's still hiding in the Casino Night Zone?

Sunday, March 11, 2018

The many tendrils of a Sonic 3 level, part 1

Apologies for the radio silence during the past month; I've been absolutely swamped with work and haven't had time for either the blog or the hack.

On the subject of loading Sonic & Knuckles stages in Sonic 3, an anonymous commenter wondered whether the bogus entries in the S3A level load block are enough to make the game crash while loading those levels, to which I answered that yes, that should be quite enough.

However, are they the sole cause of errors in this scenario? Assuming we patch up the level load block to point at valid Kosinski data where appropriate, would those stages then boot up properly? Not necessarily.

First off, as we saw before, the level load block itself contains byte pointers which are used as an index to the PalPoint and Offs_PLC arrays. Obviously, these bytes must correspond to valid entries within those arrays, otherwise we'll once again be attempting to decompress garbage data, or trying to copy nonsensical color values to a random location in the Mega Drive's address space.

Beyond this though, there are several other points in the game where code is executed and data is loaded conditionally depending on which level is being played. These points are scattered throughout the ROM without any structure, which is partially why Sonic 3 has a reputation of being a harder game to hack than previous Sonic titles.

Let's start from the top. At $23CA, we have the AnPal_Load function, which is called once every frame in order to run all of the animated palettes within a stage. To accomplish this, it takes the value of the current zone and act and uses it as an index to the OffsAnPal array, which is itself a list of pointers to smaller routines that then handle all the palette animations specific to that stage:
OffsAnPal:      dc.w AnPal_AIZ1-OffsAnPal
                dc.w AnPal_AIZ2-OffsAnPal
                dc.w AnPal_HCZ1-OffsAnPal
                dc.w AnPal_HCZ2-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_CNZ-OffsAnPal
                dc.w AnPal_CNZ-OffsAnPal
                dc.w AnPal_FBZ-OffsAnPal
                dc.w AnPal_FBZ-OffsAnPal
                dc.w AnPal_ICZ-OffsAnPal
                dc.w AnPal_ICZ-OffsAnPal
                dc.w AnPal_LBZ1-OffsAnPal
                dc.w AnPal_LBZ2-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_LRZ1-OffsAnPal
                dc.w AnPal_LRZ2-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_BPZ-OffsAnPal
                dc.w AnPal_BPZ-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_CGZ-OffsAnPal
                dc.w AnPal_CGZ-OffsAnPal
                dc.w AnPal_EMZ-OffsAnPal
                dc.w AnPal_EMZ-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
                dc.w AnPal_None-OffsAnPal
Interestingly, Flying Battery Zone has its own routine just like in Sonic & Knuckles, except that here it does absolutely nothing. More interestingly, there are also routines defined for both acts of Lava Reef Zone, and although the routine for act 2 is blank, the routine for act 1 is fully functional, and even references some otherwise unused palette data!


The presence of this data, which is identical to the corresponding data in the Sonic & Knuckles ROM, ties squarely into the notion that Lava Reef Zone had already entered production by the time of Sonic 3's release.

Moving right along, at $4680 we have the LevelMusic_Playlist, which as we saw before, dictates which track is played at level load based on the current zone and act. Sonic 3's version of the playlist is identical to the one found in Sonic & Knuckles, except for the following points:

  • The Rolling Jump bonus stage reuses the track for the Gumball bonus stage.
  • Both the ending level slot and the four acts at the end of the level list make use of the special stage track.
  • Sky Sanctuary Zone and Death Egg Zone are bugged. Instead of using the same song for both acts, act 2 of Sky Sanctuary Zone uses the song meant for Death Egg Zone 1, and then both acts of Death Egg Zone use the song meant for Death Egg Zone 2.

At $1A1F4, we find the LevelSizes structure. All of the levels unused in Sonic 3 have the default size of $1000 pixels down and $6000 pixels across. Shortly after, at $1A8A8 we find the LevelResizeArray. Like in Sonic & Knuckles, every stage past Launch Base Zone 2 points at an empty dynamic resize routine.

Then at $26A92, we find the Animate_Tiles function, which is also called once every frame in order to process all the animated elements within a level. Much like the AnPal_Load function, it uses the current zone and act as an index to an array of pointers to smaller routines, which then handle the tile-based animations specific to that level. Interleaved with this array however, is another array containing pointers to the level's "animated PLC", which consists of the ROM address of the uncompressed art, the destination VRAM address, and the duration of each frame of animation.
Offs_AniFunc:   dc.w AnimateTiles_AIZ1-Offs_AniFunc
Offs_AniPLC:    dc.w AniPLC_AIZ1-Offs_AniFunc
                dc.w AnimateTiles_AIZ2-Offs_AniFunc
                dc.w AniPLC_AIZ2-Offs_AniFunc
                dc.w AnimateTiles_HCZ1-Offs_AniFunc
                dc.w AniPLC_HCZ1-Offs_AniFunc
                dc.w AnimateTiles_HCZ2-Offs_AniFunc
                dc.w AniPLC_HCZ2-Offs_AniFunc
                dc.w AnimateTiles_MGZ-Offs_AniFunc
                dc.w AniPLC_MGZ-Offs_AniFunc
                dc.w AnimateTiles_MGZ-Offs_AniFunc
                dc.w AniPLC_MGZ-Offs_AniFunc
                dc.w AnimateTiles_CNZ-Offs_AniFunc
                dc.w AniPLC_CNZ-Offs_AniFunc
                dc.w AnimateTiles_CNZ-Offs_AniFunc
                dc.w AniPLC_CNZ-Offs_AniFunc
                dc.w AnimateTiles_NULL-Offs_AniFunc
                dc.w AniPLC_ICZ-Offs_AniFunc
                dc.w AnimateTiles_NULL-Offs_AniFunc
                dc.w AniPLC_ICZ-Offs_AniFunc
                dc.w AnimateTiles_ICZ-Offs_AniFunc
                dc.w AniPLC_ICZ-Offs_AniFunc
                dc.w AnimateTiles_ICZ-Offs_AniFunc
                dc.w AniPLC_ICZ-Offs_AniFunc
                dc.w AnimateTiles_LBZ1-Offs_AniFunc
                dc.w AniPLC_LBZ1-Offs_AniFunc
                dc.w AnimateTiles_LBZ2-Offs_AniFunc
                dc.w AniPLC_LBZ2-Offs_AniFunc
                dc.w AnimateTiles_NULL-Offs_AniFunc
                dc.w AniPLC_ALZ-Offs_AniFunc
                dc.w AnimateTiles_NULL-Offs_AniFunc
                dc.w AniPLC_ALZ-Offs_AniFunc
                dc.w AnimateTiles_NULL-Offs_AniFunc
                dc.w AniPLC_ALZ-Offs_AniFunc
                dc.w AnimateTiles_NULL-Offs_AniFunc
                dc.w AniPLC_ALZ-Offs_AniFunc
                ...
As with the OffsAnPal array, all of the empty slots in the Offs_AniFunc array point to blank, "null" routines. However, much like the level load block, empty slots in the Offs_AniPLC array are filled with pointers to whatever data follows the previous PLC entry. As a result, Flying Battery Zone points to the PLC for Icecap Zone, all of the Sonic & Knuckles levels point to the PLC for Azure Lake, and every level past Desert Palace (the last stage with animated PLCs) points at the end of the animated PLC block.

Okay, but unlike the data mismatch in the level load block, the Azure Lake PLC is obviously valid PLC data, so loading Sonic & Knuckles levels shouldn't cause the game to crash. And even if the PLC data is invalid, such as with the levels that point at the end of the animated PLC block, the fact that the animation routine is blank means the game doesn't do anything with the invalid PLC data.

So far we haven't found anything that might crash the game. In the next post, we'll look at one aspect which could, and in the process, stumble upon an obscure version difference.

Monday, February 12, 2018

How many did I say? Sorry, I meant half that.

As I begin development of the yet unnamed hack, my first order of business is to free up as much space on the ROM as possible. We saw before how the Mega Drive has a 32 megabit, or 4 MB ROM address space, and when Sonic 3 is locked on to Sonic & Knuckles, they take up the entirety of this space.

However, as I also mentioned, the public disassembly contains a special build flag, the Sonic3_Complete flag, which according to the disassembly's README file...
[...] will change the assembly process, incorporating all necessary Sonic 3 data split from the original rom to create a complete Sonic 3 and Knuckles rom without filler.
Indeed, setting this flag causes all Sonic 3 data that isn't referenced by Sonic & Knuckles to be trimmed off, producing a lean, 3.23 MB ROM. Can we get it even smaller, though?

As an initial approach, I tried repacking all of the compressed assets in the game using flamewing's optimized suite of compressors. These are able to output smaller versions of the same files, but which the game's Kosinski and Nemesis decompressors can unpack all the same. Doing so brings the ROM size down to 3.16 MB.

We can do better, though. As you may recall, the Sonic 3 cartridge contains a small subset of Knuckles' sprites that are used during his cutscene appearances. In Sonic 3 & Knuckles, these sprites are still used for the cutscenes which take place in Sonic 3 stages, so the Sonic3_Complete flag includes the cutscene art block in the ROM.


Much like the player object, cutscene Knuckles uses DPLCs to ensure that only one of its sprites needs to be loaded to VRAM at a time. This requires that all of his sprites be stored uncompressed in the ROM, which takes up a significant amount of space. All told, Knuckles takes up about 19.7 KB of the Sonic 3 cartridge.

However, since player sprites are also uncompressed, this presents an opportunity. If we take a close look at the above sprites, we can see that most of them are identical to sprites which can be found in the main Knuckles art block. In fact, only nine sprites along the bottom row are unique to the cutscene art block.


Once isolated, these sprites only take up about 4.3 KB. If we add them to the main Knuckles art block, and then simply edit cutscene Knuckles' DPLC scripts to point at the identical sprites in the main art block, we can lose the cutscene art block entirely and save about 15.4 KB.

The main art block is exactly 130,944 bytes. Adding the sprites above makes it 135,360 bytes. That's just over 132 KB.

Uh-oh.

To understand why this is a problem, let's look at the documentation for the DPLC format over at the Sonic Retro wiki:
Sonic 3 & Knuckles uses the same DPLC format as Sonic 2 for the main characters: the first word is the number of DPLC requests to make, and each successive word (up to the value of the first word) is split up so that the first nybble is the number of tiles to load minus one, and the last three nybbles are the offset (in tiles, i.e. multiples of $20 bytes) of the art to load from the beginning of the object's specified art offset in ROM.
To put it differently, each DPLC entry is a word in the format $NAAA, in which N is the number of tiles to copy to VRAM (minus one), and AAA is the the number of the tile to start copying from. So for instance, if we wanted to queue up tiles $3E2 through $3E7, that's six tiles starting from $3E2, so we would write down $53E2.

This format can only index up to $1000 tiles, and because each tile is $20 bytes long, that means the art block can't be larger than $1000 × $20 = $20000 bytes, or 128 KB.

So now we have to go into the art block and somehow save up 4 KB of tiles in order to add in the 4.3 KB of sprites from the cutscene block. Thankfully, there are a lot of poorly optimized sprites to aid us in our task.


For instance, in the teetering sprites above, there's a lot of empty space, and the shoe on the floor appears three times despite being identical in each frame. By nudging Knuckles around slightly, we can reduce the size of the sprite pieces and reuse the shoe for every frame, saving about a dozen tiles. Rinse and repeat for all 252 of Knuckles' frames.

You do the impossible and fit everything into 128 KB. That should work, right? Just build the ROM and-- oh, bloody hell.



Assuming you actually followed that link to the Sonic Retro wiki, you may have noticed that the DPLC format is different between Player Characters and Other Objects. Here's what it says in the latter case:
For other objects, the first word is the number of DPLC requests to make minus one, and each successive word (up to the value of the first word plus one) is split up so that the last nybble is the number of tiles to load minus one, and the first three nybbles are the offset (in tiles, i.e. multiples of $20 bytes) of the art to load from the beginning of the object's specified art offset in ROM.
Cutscene Knuckles isn't a player character, so by exclusion, he must be an "other object". So what, that just means the DPLC entry format is $AAAN rather than $NAAA, right?

Not so fast. In order to calculate the ROM offset for the DMA transfer, the DPLC code must take the starting tile number AAA and multiply it by $20, the size of each tile. Let's look at how the code in Knuckles_Load_PLC does it:
                andi.w  #$FFF,d1
                lsl.l   #5,d1
Pretty straightforward. The bottom 24 bits are isolated, and then promoted to a longword as the value is shifted left five times, multiplying it by $20. Now let's look at the general purpose code in Perform_DPLC:
                andi.w  #$FFF0,d1               ; Isolate all but lower 4 bits
                add.w   d1,d1
This time around, the tile number is in the top 24 bits, so it is already multiplied by $10 and only needs to be multiplied by two in order to calculate the offset. This is done by adding by adding the contents of the d1 register back onto itself, without promoting the value to a longword.

There are two consequences to this. One is that the d1 register does not have to be cleared before loading each new DPLC entry. The other is that tiles past the 64 KB boundary are inaccessible: since the topmost bit is always truncated, a request for tile $9B9 results in tile $1B9 being loaded instead.

At this point I just shrugged, moved all the cutscene sprites to the first half of the art block, and called it a day.

Friday, February 2, 2018

End of part one

On this day 24 years ago, Sonic the Hedgehog 3 was released for the Sega Genesis in North America. Happy birthday!


Coincidentally, today also marks my 200th post on this blog. Holy goodness, I swear I did not plan this far ahead when I started the blog nine months ago. It's been a lot of work writing a post every weekday, but also a lot of fun, especially when I was able to answer your questions. Doing so has made me learn a lot of things I previously did not know.

To all of my readers, especially those who have contributed to the discussion in the comments: thank you so much.


I would like to take this opportunity to make a couple of announcements. At various times, people have approached me on Twitter, YouTube, and even the Sonic Retro forums, asking me to work on a new version of Sonic 3 Complete, or to release my work in some other form. I'm not really interested in the former, because if I had my way, half of the stuff in that ROM hack would be thrown out, which would be a tremendous disservice to everyone who's ever contributed to it, as well as everyone who had played the previous versions.

I've also been reluctant on pursuing the latter, because "Sonic 3 Complete except with a lot less features" is a hard sell, both to the developer and the consumer. However, over the past few months I've been doing a lot of brainstorming, and I feel that I now have enough original ideas and a sufficiently unique direction to warrant pursuing them.

I'm excited to announce that starting today, I will begin development of my own Sonic 3 hack.


Which brings me to my second announcement. Like I've said, writing this blog has been very fun, but it has also been a challenge, and I have learned the hard way that I am not good with deadlines, even when it's doing something which I enjoy. Combined with the time I'll need to work on the hack, I am hereby suspending regular updates to this blog.

Let me make that perfectly clear: the blog isn't going anywhere. I still have more than 100 potential blog posts in my bag, and they will materialize sooner or later. Plus, working on a hack is bound to give me even more subject matter to work with. I just won't be posting regularly for the time being, that's all.

To that effect, I would advise you to follow me on Twitter, since I'll tweet out each new blog post. I'll probably also post some hack updates on there, and I promise I'll try to cut down on the memes.


I've gone back and tidied up the formatting on the older blog posts, and over the coming weeks I'd like to make the tags more helpful, as well as optimize the first animated GIFs I made, because they weigh a ton. Next thing I'll probably do however is write an updated about page to reflect the current nature of the blog, as well as the hack.

Again, thank you so much for reading this far, and I hope you'll stick around -- this ride ain't over by a long shot.

Thursday, February 1, 2018

Trouble at the border

A while ago, we saw how in Sonic 3, Knuckles' boss area in Launch Base Zone 1 was originally a bit different, and that Sonic 3 & Knuckles modifies it by altering the level layout directly in RAM. Logically, the same changes are also applied to the matching area at the start of act 2, except that this time, the twin boxes are already open.


Interestingly, in Sonic 3 the checkered tube is still present in the act 2 layout, despite normally being removed when the boss is defeated. It's possible that the act transition was originally planned to happen up there, and the tube would only explode at the start of act 2.

However, this theory is challenged by the presence of hidden monitors, buried in the floor at the bottom of the room, as early as the Sonic 3 object layout.


On the other hand, assuming the tube was meant to explode in act 1, it would then suddenly reappear upon loading the act 2 layout, which wcould lead to this curious scenario.

This isn't the only level layout adjustment performed in Launch Base Zone 2, though: directly after Knuckles' act 2 boss area, the Sonic 3 layout cuts off rather abruptly. In Sonic 3 & Knuckles, a couple of extra chunks were added to end the pipe floor more naturally.


This change is purely cosmetic however, because Knuckles' end of level cutscene forces him to jump at the exact point where the floor would cut off, regardless.


If it's weird you're looking for, though, look no further than Angel Island Zone 2. For whatever reason, there are actually hidden monitors buried in the floor of Knuckles' boss area. In act 2.


What on earth could the developers have been planning here?

Wednesday, January 31, 2018

The unused boss

A while ago, I noted how Knuckles' route at the end of Marble Garden Zone 2 is pretty much complete all the way up to the boss area, including the entire rising floor section. There are considerable differences in the object layout that allow you to quickly reach the end of the section and be left with nothing to do, which is probably why it got changed.


Once you reach the boss area, you may be disappointed (though not particularly surprised) that the boss doesn't show up regardless of character, as it does in Sonic 3 & Knuckles. In fact, there are no objects placed in the boss area at all.

As it turns out however, Knuckles' boss is actually present within the game's code in a half-finished state. The following PAR codes will add the boss to Marble Garden Zone 2's object layout at its usual coordinates from Sonic 3 & Knuckles, overwriting the last starpost in Sonic and Tails' route:
063822:3E78
063824:0000
063826:B100
When the boss spawns now, though, you'll find that the screen locks itself at an earlier part of the level, and the boss is moving around far below the usual boss area. It would seem the level layout was quite different at one point.


The screen lock can be modified using the code 04A490:3D78, but since the object has several hardcoded coordinates in its movement routines, it will quickly jump outside the screen and never return. This is fixed with the following codes:
04A572:3E18
04A578:FFA8
04B0C6:0038
04B0CE:3E18
04B176:00F8
Of course, now that we've done this, the boss is actually at a negative Y coordinate when it begins coiling its drill, which the spike chain objects interpret as a large positive value, causing the first row of spikes to be deleted prematurely. The final object fixes this by performing a signed comparison, which can be replicated using the code 04AA66:6D1A.

For convenience's sake, we can push up the bottom screen boundary by setting the Camera_target_max_Y_pos RAM variable to $28, which is achieved with the following codes:
FFEE12:0000
FFEE13:0028
We can now finally check out the boss in action, which as commenter Silver Sonic 1992 points out, correctly plays the act 2 boss music unlike in Sonic 3 & Knuckles.


As we can see, the behavior of the object is very similar to that of the final version, except for being displayed in front of the level blocks, and not producing any debris when passing through them. And although the player can damage it, the boss doesn't have a death handler, so it can't actually be defeated.

Tuesday, January 30, 2018

S3A harder bosses flag

Did you know? Some of the boss objects in S3A actually contain prototype versions of the harder attack patterns which are encountered when playing the final game as Knuckles. These patterns are enabled when the RAM flag at $FA81 is set, which can be done manually using the PAR code FFFA81:0001.

If this flag is set, the boss of Angel Island Zone 1 will launch the customary three bombs before flying overhead across the arena. The difference with these bombs is that rather than self-destructing when the boss is defeated, they fall back down where they stand, which is a problem because their graphics might get overwritten in the meantime.


Two bosses exhibit behavior indistinguishable from the final game: the Hydrocity Zone 2 boss produces a spout without descending into the water, while the Marble Garden Zone 1 boss introduces the usual spiked cylinder object, as well as the slightly altered movement that goes along with it.


The final boss affected by the flag is the Launch Base Zone 2 boss, Beam Rocket. When this boss is defeated, a sprite with broken mappings suddenly attaches itself to the Egg Mobile, and as the ship flies horizontally across the screen, it leaves behind an invisible object which produces a bunch of explosions.

If any of this sounds familiar, that's because this is a very early version of Knuckles' end of level cutscene. The invisible exploding object is the bomb, and the sprite with the broken mappings is the bomb chute!


Unfortunately, no more of the cutscene seems to be implemented. The player will still remain in control, and the screen lock just won't vanish. You'll just be trapped, forever.

Monday, January 29, 2018

Drowning during bosses

An anonymous reader asks:
I don't think you've talked about it yet so I'd like to ask a few things related to the Hydrocity Act 1 boss in S3A.
Sure, go ahead.
Why does it use the Act 2 boss BGM instead?
loc_47DBA:                                      loc_69F64:
    move.l  #Obj_HCZ_MinibossLoop,(a0)              move.l  #Obj_HCZ_MinibossLoop,(a0)
    moveq   #$19,d0                                 moveq   #$2E,d0
    jsr     (Play_Sound).l                          jsr     (Play_Sound).l
                                                    move.b  #$2E,($FFFFFF91).w

locret_47DC8:                                   locret_69F78:
    rts                                             rts
Because for some reason, in S3A the act 1 boss requests the act 2 boss music.
Why, if you let the air countdown start and then get out of the water, does the S&K Act 1 boss BGM start to play? It's seems to be the only time where track 18 (I think it's 18) is used. (Apparently this glitch also happens in Act 2 but I haven't tried)
Because, to put it mildly, the code that's responsible for resuming a level's music after having previously switched to the drowning theme is a brittle piece of crap:
Player_ResetAirTimer:
    cmpi.b  #$C,$2C(a1)
    bhi.s   loc_1744C
    cmpa.w  #Player_1,a1
    bne.s   loc_1744C
    move.w  (Level_music).w,d0
    btst    #1,$2B(a1)
    beq.s   loc_17430
    move.w  #$2C,d0

loc_17430:
    tst.b   (Super_Sonic_Knux_flag).w
    beq.w   loc_1743C
    move.w  #$2C,d0

loc_1743C:
    tst.b   (Boss_flag).w
    beq.s   loc_17446
    move.w  #$18,d0

loc_17446:
    jsr     (Play_Sound).l

loc_1744C:
    move.b  #$1E,$2C(a1)
    rts
Let's go over what this code does. First, the current level's music is loaded from the Level_music RAM variable, which as we saw before, is pulled from the master playlist, based on the current zone and act. This value is then stored in the d0 register, from which it will eventually be read by the Play_Sound function called at loc_17446.

Before it can reach loc_17446 though, the value must survive a gauntlet, which begins by checking bit 1 of the player's status_secondary bitfield, which is set when the player is invincible. If the player is currently invincible, the contents of the d0 register are replaced with the value $2C, which is the ID for the invincibility music track.

Next, if the Super_Sonic_Knux_flag is set, the value of the d0 register is once again replaced with $2C, the ID for the invincibility music track. Note that this check is redundant: the player is always invincible when in their Super form.

Finally, the Boss_flag is checked. If the player is currently fighting a boss, then the game should continue playing boss music, and therefore the d0 register is overwritten with the value $18, which as the commenter duly notes, is the theme used by act 1 bosses in Sonic & Knuckles. No effort is made to pick specific themes for each boss, despite the fact that there are only two bosses in the entire game where the player can trigger the countdown music.

This is annoying for several reasons. In Sonic 3, both bosses play the act 2 boss theme, so they could've just made the code set d0 to $19 and be done with it: at least it would always resume the right track! Meanwhile, as we can see from the code near the start of this post, Sonic & Knuckles actually saves the current boss track to RAM address $FF91, but nothing in the game ever makes use of this value.

Why complicate matters, though? Just check the current act and use that information to pick one song or the other.
It's possible to drown during the score tally but in S3&K this was apparently fixed. Why does it happen and how it was fixed?
The question presupposes a falsehood: the only way to drown during the level results is by running out of air just as the results object slides into view, which works equally well in both Sonic 3 and Sonic & Knuckles.


In practice, however, the level results object prevents this by restoring both player objects' air reserves (at offset $2C of their SSTs) right as the stage clear theme begins playing:
Obj_LevelResultsWait:
    tst.w   $2E(a0)
    beq.s   loc_2CF4C
    subq.w  #1,$2E(a0)
    cmpi.w  #$121,$2E(a0)
    bne.s   locret_2CF8E                        ; Play after eh, a second or so
    move.b  #$1E,($FFFFB02C).w                  ; Reset air for Hydrocity
    move.b  #$1E,($FFFFB076).w
    moveq   #$29,d0
    jmp     (Play_Sound).l                      ; Play level complete theme
The title card object then repeats the process, ensuring the player always begins the second act with a full set of lungs.
Thanks in advance.
Thank you for the questions!