Link’s Awakening disassembly progress report – part 10

This article is part of an ongoing “Disassembling Link’s Awakening” series, where I attempt to gain some understanding on how special effects were implemented in this game.

Entities respawn mechanism

In a previous progress report, I wondered how Link’s Awakening respawn mechanism works.

Specifically, when destroying enemy entities on a specific area, moving out and back into this area doesn’t reload all the entities. Only the surviving enemies (if any) are visible. For a moment, at least. After a while, the enemies seems to respawn again.

A portion of gameplay showing how entities don’t respawn when leaving a room
Entities don’t respawn when returning to a previously visited area.

Eventually I found the piece of code responsible for this behavior. Turns out the implementation is cleverly simple.

It relies on two separate mechanisms: a recents rooms list, and flags depending on the entity load order.

Clearing rooms

The first mechanism used is a 16x16 array, wEntitiesClearedRooms. It contains one byte per area (or “room”). When all the enemy entities in a room are destroyed, this is recorded into this array.

When this room is visited later again, the game checks whether the room has been cleared or not before loading the entities. Simple enough.

But how do entities respawn again after a while? Well, because the wEntitiesClearedRooms also has companion variable: wRecentRooms.

wRecentRooms stores the six most recently visited rooms. At its core, it’s a simplified implementation of an LRU cache:

Clean and tight. But importantly, this means that new rooms will start overwriting older ones.

How does this relate to entities respawning again? Well, the single and unique purpose of wRecentRooms is actually not to store a list of recently visited rooms, but to detect when a room is evicted from this list. When a recent room is overwritten by a newer one, the byte corresponding to the evicted room in wEntitiesClearedRooms is reset to zero. Which means the entities of this room will start spawning again when the room is visited.

Entity flag

The game has actually a finer granularity than that. It’s not about whether then entire room is cleared or not: even destroying a single entity in a room will cause it not to respawn the next time (even if other entities in the room still do spawn). How does that work?

A portion of gameplay showing how only destroyed entities don’t respawn when leaving a room
Only destroyed entities don’t respawn. The others are still loaded when visiting the room again.

Turns out that the wEntitiesClearedRooms array doesn’t only tell if a room has been cleared or not, but also which entities have been destroyed in that room.

For this, entities are identified by their load order. Each entity has an index indicating in which order it was loaded into the room. So when an entity is destroyed, the game takes the entity load order, turns it into a bitmask, and stores it into wEntitiesClearedRooms.

A diagram of how the entities load order is encoded

Next time this room will be visited, when each entity is loaded, the game uses the load order to check if the entity has already been destroyed – and skip it if so.

Statistics

Knowing where we are and how much progress we made is instructing and motivating. For this purpose, similar to some of the pret projects, the LADX disassembly now has a script that can output various statistics about the overall completion state of the project.

Here is an example output:

$ tools/stats.sh
Number of remaining raw addresses:
   Referencing Home (0000-3FFF):
       0
   Referencing non-Home ROM banks (4000-7FFF):
    2551
   Referencing RAM (8000-FFFF):
    6478

Number of unlabeled functions:
    1033

Number of unlabeled jumps:
    7706

This should help to:

In the future, the script may present percentages instead of raw numbers; something like “Unlabeled functions: 1033 (34%)”.

Shiftable bank

Speaking of shiftable banks, work has begun towards making the disassembly shiftable!

But what’s a shiftable disassembly? When starting a disassembling project, the first step is often to run an automatic disassembler on the whole ROM binary. This automatic disassembler can only decode instructions, and add auto-generated-labels to the most obvious locations. But the output is quite limited: it will have data interpreted as code, no meaningful labels – and, crucially, many memory addresses will be left unresolved.

  ; Loading data from an unresolved `$4206` address.
  ld   hl, $4206
  ld   a, [hl]

What’s the problem with that? Well, if we start tweaking the original code (for instance to add a new feature that wasn’t present in the original game), the new code will slightly push the old code around. But places in the code using unresolved addresses won’t be updated, and will still point to the former location. This will lead to data-corruption and crashes very quickly.

How to avoid these corruptions? Either by:

In shiftable code, all unresolved raw addresses have been resolved to proper labels. Because of that, even if the data location is pushed around by new code, the code referencing this data location will also change – and the game will still work.

  ; Loading data from a labeled address.
  ld   hl, Data_004_4206
  ld   a, [hl]

Now, resolving data addresses in the whole reconstructed source code isn’t easy. There’s a reason disassemblers can’t do it automatically: the banks system.

When the disassembler sees, for instance, a pointer being created with the address $4206, it can’t know if this address means:

So cross-referencing these addresses has to be made manually. An human must understand what the code is actually trying to do, and replace the raw address with a label at the right location. And it takes time.

But already, as a first milestone, the main bank (bank 0) is now shiftable! That means new code can be added or removed from this bank, without breaking the game. As the bank 0 is always mapped into memory, this is already quite useful to insert some hooks for new features.

And meanwhile, the work to make the other banks shiftable continues. About half of it is now done, but it involves quite a bit of repetitive work (although some of it has been automated).

Want to give it some help, and contribute to make Link’s Awakening easier to mod than ever? Drop on the Discord channel!

Want to read more? Discover more of the code, or join the discussion on Discord.

Link’s Awakening disassembly progress report – part 9

This article is part of an ongoing “Disassembling Link’s Awakening” series, where I attempt to gain some understanding on how special effects were implemented in this game.

New contributors

Since the last report, the following people made first-time contributions to the disassembling project:

Super Game Boy frame

First, let’s expand a little on @marijnvdwerf’s improvements to the Super Game Boy code.

The Super Game Boy (a device that allowed to play Game Boy cartridges on a Super NES) has many features games could use – including custom color palettes, custom audio, or multiplayer support. But Zelda: Link’s Awakening included support only for the more prominent SGB feature: a custom border surrounding the display when playing the game.

Zelda Link’s Awakening being played on the Super Game Boy, including the SGB custom frame.

Sending the frame

Like all SNES or Game Boy graphics, the custom frame is made of tiles. Practically, this requires tiles data describing the tile graphics, a tilemap describing how the tiles are laid out, and some color palettes.

Now, as the Super GameBoy was created after the release of the original Game Boy, the Game Boy doesn’t know about this device. Specifically, it doesn’t have a specific communication channel with external hardware.

So, how can a Game Boy communicate with another device that was released as an afterthought? Well, the method eventually chosen was to abuse an existing hardware port. To communicate with a Super GameBoy, a game must write to the joypad registers. Of course, the joypad registers are usually read-only (a game can’t press a hardware button by itself). But when running on a Super GameBoy, the joypad hardware registers become also writable, and are used to send data to the device.

Using this communication method, uploading a custom frame involves a series of steps to communicate with the Super GameBoy:

  1. Send a MLT_REQ command to switch to 2-players mode (this will confirm the game is running on a Super GameBoy);
  2. Send a MASK_EN command to make the displayed screen black while the game will be messing with VRAM;
  3. Copy the tiles data for the custom frame from the ROM to the Game Boy VRAM;
  4. Send a CHR_TRN command to upload the VRAM content to the Super GameBoy;
  5. Upload the tilemap and palettes for the custom frame from the ROM to the Game Boy VRAM;
  6. Send a PCT_TRN command to upload the VRAM content to the Super GameBoy;
  7. Send a MASK_EN command to finally make the displayed screen visible again.

Timing the transfers

Each of these transfers takes some time. The usual way to wait for the transfers to be completed would be to sync on the v-blank intervals, occurring every 16,6 ms. But during these operations, the screen is off, so no v-blank occurs.

Instead, the code uses carefully crafted busy-loops to execute a specific number of instructions. Once all the instructions are executed, the game knows the right amount of time must have passed, and the transfer should be complete.

Extra background

While documenting the Super GameBoy code, data and commands, @marijnvdwerf found that the tilemap for the custom frame includes a bit of content that is never visible in-game.

Zelda Link’s Awakening Super GameBoy frame as coded in the ROM, with extra content visible
Only the content inside the red square is visible during normal gameplay; the rest of the frame is clipped.

Why this extra image section was left in the game is still to be discovered.

Using the Zelda III disassembly to fill out entities data

Game using an entity system tend to store entity attributes in a not-so-straightforward way. Instead of declaring an array of entities, game often use several arrays of attributes, indexed by entity.

// An array of entity structs would be the idiomatic way
// to declare entities in C.
struct entity = { int x, int y, int health /*, … */ };
struct entity entities[MAX_ENTITIES];

// But in games, entities are more often stored
// as arrays of entity attributes.
int entitiesX[MAX_ENTITIES];
int entitiesX[MAX_ENTITIES];
int entitiesHealth[MAX_ENTITIES];

When writing actual assembly code, it’s easy to see why.

To access an attribute of a single entity using the “one single array” variant, we need to perform one multiplication and two additions:

// Get the health of entity 5, using the "one single array" variant.
int entityIndex = 5;
int health = *(entities + sizeof(struct entity) * entityIndex + 3);

Whereas with the “several arrays of attributes” variant, accessing an attribute is only one single addition:

// Get the health of entity 5, using the "several arrays of attributes" variant.
int entityIndex = 5;
int health = *(entitiesHealth + entityIndex);

Link’s Awakening has about 35 of these entity attribute arrays. And the purpose and behavior of these attributes is often difficult to figure out.

After spending some time trying to make sense of some of the less-often used attributes, I eventually took another approach.

As the history records, Link’s Awakening was started right after the release “Zelda: A Link to the Past” release, by Nintendo employees working after-hours. Using a spare Game Boy development kit, they were trying to see if an ambitious Zelda game, similar to the SNES version, could run on the much-less-powerful Game Boy.

Given than the programmer team was partially made of the same programmers than “A Link to the Past”, could it be that they re-used some of the code structures? This was worth checking out.

Turns out that a fairly complete disassembly of Zelda SNES does actually exist. And indeed, some of the entities data structures look similar! This provided some hints to some of the less-used entities tables.

For instance one of these, wEntitiesPhysicsFlagsTable, exposes flags about the entity physics and rendering: whether it has a shadow, or if it reacts to projectiles, and so on. Another table figured out by looking at the Zelda SNES disassembly is wEntitiesFlashCountdownTable, which is used to make an entity flash for a while after it received a hit.

Generic trampoline

A while ago, user @spaceotter on Discord asked if a generic trampoline function was available in the game.

A what?

Remember how the game code has to be divided into different code sections, which mostly can’t be loaded at the same time? This creates an issue: in this configuration, how is it possible to call, from bank X, a function residing in bank Y? Bank X can’t directly call of jump to the function, because if bank X is loaded, then bank Y isn’t, and vice-versa.

The solution: a trampoline. It’s a small piece of code in bank 0 (the one that is always loaded) that allows to call a function from one bank to another.

The structure of a trampoline is almost always the same:

  1. Jump from bank X to bank 0 (which is always loaded);
  2. Switch to bank Y;
  3. Call the function in bank Y;
  4. Switch back to bank X;
  5. Return to the caller in bank X.

In Link’s Awakening, many trampolines are defined for specific uses: the target bank, function and return bank are hardcoded. As a trampoline is only a few instructions, hard-coding and duplication isn’t that bad. And if you have the original source code of the game, adding another ad-hoc trampoline when needed is easy.

But the ROM-hacking community usually doesn’t have the original source code of the same. And most of the ROM-hacking work is patching existing functions at specific places, to call newly-added code. It is quite useful for new code to call existing functions, but what if a trampoline for these functions doesn’t exist in the original game – or exists, but returns to the wrong bank?

This is where a generic trampoline function is really useful. Until a few days, I though developers never bothered to actually code one. But as I was randomly browsing some code in bank 0, I found this piece of code:

func_BD7:
    ld   a, [$DE01]
    ld   [MBC3SelectBank], a
    call label_BE7
    ld   a, [$DE04]
    ld   [MBC3SelectBank], a
    ret

When called, $DE01 and $DE04 are usually two different bank numbers, and the address of a function is also stored… Here we are: this is actually our generic trampoline!

Here is the documented version of it:

; Generic trampoline, for calling a function into another bank.
Farcall:
    ; Switch to bank wFarcallBank
    ld   a, [wFarcallBank]
    ld   [MBC3SelectBank], a
    ; Call the target function
    call Farcall_trampoline
    ; Switch back to bank wFarcallReturnBank
    ld   a, [wFarcallReturnBank]
    ld   [MBC3SelectBank], a
    ret

This function is only used in three different places: once in the credits, and twice in palette-related code. It was probably added to the code base while making the DX version – but wasn’t ever used a lot. Maybe because it doesn’t preserve some of the registers (making argument passing cumbersome), or because it is slower than a hardcoded trampoline for a specific use.

But ROM-hackers should enjoy this: hardcoded-trampolines cannot be easily patched into the original binary, so a generic function may prove useful to hook new code into the game.

What’s next?

Now that the disassembly is complete, and the entity system is getting in a decent shape, the next important milestone is to make the disassembly shiftable. Work has already begun – and we’ll see how and what does that mean for the project in the next progress report.

Want to read more? Discover more of the code, or join the discussion on Discord.

Quelles grèves pour l’informatique ?

Depuis le 5 décembre, je suis en grève contre la retraite individualiste dite « à points », et pour la mise en place d’un système de retraite solidaire.

Faire grève, dans l’informatique, c’est pas courant. Les informaticien·nes sont peu syndiqué·es, et ne participent que rarement à des mouvements sociaux. Moi-même, ce n’est que la troisième fois que je fais grève de toute ma carrière – et la première grève reconductible.

J’imagine qu’il y a des spécificités liées à l’informatique, qui font qu’on envisage moins la grève comme moyen d’action :

Dans ces conditions, quel sens peut avoir une grève dans l’informatique ?

La grève pour discuter

Depuis le début de la grève, et même un peu avant, on a beaucoup discuté avec des collègues. De la réforme à venir, de la grève, des moyens d’actions. Qui fera grève, quand, comment ? On partage des liens, on s’informe. On se retrouve en manifestation. Beaucoup de collègues ont écrit des articles pour parler de la réforme, et de la grève dans l’informatique.

De ce temps disponible sont nés par exemple :

Bref, la grève a libéré du temps pour s’informer, discuter, réfléchir. C’est déjà une belle réussite.

Visibiliser la grève

Comment rendre visible l’arrêt de travail alors que les systèmes que nous gérons sont largement automatisés ? Même si on est nombreux·ses à cesser le travail, les systèmes continueront à tourner pendant un moment : ça se remarquera à peine. Et l’enjeu d’une grève, c’est quand même que ça soit visible.

Avant la grève, on a joué avec quelques idées pour rendre notre arrêt de travail plus visible. Coder un fonctionnement où les systèmes se désactivent si on ne pointe pas le matin ? Faire la grève de résolution des soucis en production ?

Finalement on est un certain nombre à être partis sur une idée pas nouvelle, mais simple : mettre un bandeau en haut des sites web qu’on gère, qui explique qu’une partie de l’équipe est en grève. Le bandeau ne bloque pas l’accès au site, ni son fonctionnement.

Selon les sites et les contextes, la formulation peut être plus ou moins forte. Il y a par exemple le bandeau de grève de mon blog personnel, qui mentionne explicitement les revendications :

Bannière de grève sur mon blog personnel

En revanche, le site sur lequel je travaille comme indépendant fait partie du service public, et demande donc une formulation plus neutre :

Bannière de grève sur un site du service public

Si l’idée d’un bandeau n’est pas bien radicale, elle a tout de même fait débat. Certaines personnes s’interrogent sur la légitimité de ces bannières : n’est-ce pas utiliser une resource professionnelle pour faire passer un message personnel ?

Alors on en discute, on essaie de trouver des arguments. Une bannière sur un site, ce n’est sans doute pas différent d’une banderole devant une usine, ou une école. Et d’ailleurs, une banderole, ça ne signifie pas que toute l’équipe ou l’établissement derrière est d’accord avec le message – mais que personne ne va y opposer un veto fort, ou aller la décrocher.

Par ailleurs, ce genre de bannière existe sur de nombreux sites, y compris du service public : Radio-France, la RATP, la SNCF… L’enjeu, c’est sans doute plus la formulation du message, plus ou moins militante. Mais ce genre de question montre que la culture du mouvement social en informatique part de loin, et ne commence que tout doucement à se construire.

Et le blocage ?

Au bout de quelques jours de grève, on se rend compte que malgré la visibilité apportée, une bannière, ça ne dérange pas grand monde. Que le mouvement dure, et que la grève se fait longue.

Alors les discussions continuent. On se dit que probablement, la grève n’est efficace que lorsqu’elle dérange, qu’elle perturbe. Si la vie continue, si l’usine tourne malgré tout, si les systèmes ronronnent, rien ne se passe.

Et de fait, dans les mouvements sociaux, on a l’impression que des concessions sont obtenues par les actions qui ont un impact sur la vie quotidienne, moins que par le nombre de manifestants dans la rue. Blocages de la production (grève massive dans l’usine, piquets de grève, etc.) ou de la circulation (arrêt des transports, blocage des dépôts de bus ou de raffineries, opérations escargot sur les routes), tracteurs d’agriculteur·trices devant la préfecture, ordures qui s’accumulent.

Pour certaines professions, l’arrêt de travail est rapidement visible (chauffeurs, éboueurs, enseignants) ; d’autres où c’est moins le cas (argiculteurs, avocats, étudiants). Dans ce cas, les piquets de grève et les blocages sont régulièrement utilisés pour renforcer l’impact de la grève :

Dans tous ces cas, les blocages et les piquets de grève, s’ils sont techniquement illégaux, sont des outils très efficaces utilisés régulièrement dans le rapport de force.

Et justement, ces professions ont lancé il y a quelques jours un appel à leurs collègues informaticien·nes, les enjoignant à rejoindre la lutte avec leurs moyens.

Bloquer légitimement en informatique

Alors, comment transposer ces moyens d’action à l’informatique ?

Il faudrait sans doute déjà ne pas être seul·e. Bloquer une ressource sans subir de répression, ça fonctionne si on est nombreux·ses à le faire – que le cadre soit une équipe, un collectif informel ou un syndicat.

La légitimité du blocage se pose aussi. Idéalement, des blocages ciblés concerneraient au maximum les entreprises et le gouvernement – et au minimum les usagers ordinaires. Ou en tout cas aurait un effet insupportable mais ciblé, qui pousse au maximum à ce que les revendications de la grève soient satisfaite.

Par exemple, si des informaticien·nes décident de bloquer un service, il peut être intéressant de ne le rendre indisponible que la section utilisée par les administrateurs du site (le backoffice), et de laisser la partie utilisée par des utilisateurs externes disponible.

Avec tout ça, des idées émergent :

J’ai l’impression que ces réflexions n’en sont qu’au tout début. Et vous, qu’en pensez vous ?
Discutons-en sur Mastodon, ou sur le chat de onestla.tech.

Link’s Awakening disassembly progress report – part 8

This article is part of an ongoing “Disassembling Link’s Awakening” series, where I attempt to gain some understanding on how special effects were implemented in this game.

In the past weeks, a lot of work related to entities got made. The entities placement data was parsed, and the entities handlers were finally all figured out. Let’s dive in!

Entities placement data

First, what’s an entity? The “entity” term is vague, and may have several meanings. In this context, an entity represents a dynamic element in a room – such as an NPC, an enemy, an interactive device, and so on (as opposed to static room building blocks: walls, floor, pits, etc.).

A screenshot of Marin singing
Here’s how a room look like with only the static objects (but without entities).

A screenshot of Marin singing
And here’s how the room entities look like.

(Sidenote: you may ask, “So entities are simply sprites, right?” Well, not exactly. A sprite is a simple 8x16 pixels image displayed over the background. An entity will usually display itself by managing several independent sprites.

For instance, Bow-Wow is a single entity composed of several sprites: two for the head, one for the shadow, and four for the chain.)

Now, how are entities in a room defined? Very simply, each room has an associated list of entities, indexed by the room id. When loading a new room, the game only has to:

  1. Use the room index to find the address of the list for that room;
  2. Walk the entities list, and for each value create an entity at the given position.

But until now, these lists weren’t parsed: although strictly speaking the entities placement data had been dumped, only raw unstructured bytes were present.

; data/entities/entities.asm

; Entities placement data.
; Each entry places entities at a specific location in a room.
;
; TODO: write a proper Python script to generate the pointers tables
; and entities objects properly.

    db   $FF, $FF, $24, $39, $FF, $05, $42, $32, $2C, $55, $2C, $FF, $14, $17, $03, $42
    db   $FF, $13, $17, $66, $16, $15, $1C, $33, $1C, $FF, $23, $59, $FF, $31, $27, $45
    db   $19, $FF, $FF, $27, $20, $FF, $22, $90, $27, $90, $34, $90, $05, $42, $FF, $11
    db   $27, $18, $27, $61, $27, $68, $27, $FF, $FF, $24, $29, $FF, $35, $29, $14, $17
    db   $67, $16, $FF, $44, $1E, $26, $19, $35, $19, $FF, $67, $17, $55, $16, $23, $1E
    db   $FF, $34, $61, $38, $81, $36, $82, $FF, $34, $19, $35, $19, $44, $19, $45, $19
    db   $FF, $14, $20, $52, $1C, $57, $1C, $FF, $43, $1E, $46, $1E, $54, $19, $55, $19
    ; continued for 300 lines…

The raw bytes for entities lists are not very readable. Although if you squint, you can notice the list separator.

Writing a Python script to parse the entities was easier than parsing the room static objects: the entities lists data format is quite straightforward to parse, and some of the static objects code structure was reused.

Also, the static objects data format had a lot of quirks (unused labels, duplicated rooms, invalid pointers…). But for entities lists, the only intricacy was some lists being referenced by multiple rooms – which wasn’t hard to detect and handle properly.

In the end, it only took a couple of hours to generate a parsed version of the entities lists:

; data/entities/indoors_a.asm
; File generated automatically by `tools/generate_entities_data.py`

IndoorsA00Entities::
  entities_end

IndoorsA01Entities::
  entities_end

IndoorsA02Entities::
  entity $2, $4, ENTITY_INSTRUMENT_OF_THE_SIRENS
  entities_end

IndoorsA03Entities::
  entity $0, $5, ENTITY_OWL_STATUE
  entity $3, $2, ENTITY_SPIKED_BEETLE
  entity $5, $5, ENTITY_SPIKED_BEETLE
  entities_end

IndoorsA04Entities::
  entity $1, $4, ENTITY_SPARK_CLOCKWISE
  entity $0, $3, ENTITY_OWL_STATUE
  entities_end

IndoorsA05Entities::
  entity $1, $3, ENTITY_SPARK_CLOCKWISE
  entity $6, $6, ENTITY_SPARK_COUNTER_CLOCKWISE
  entity $1, $5, ENTITY_MINI_GEL
  entity $3, $3, ENTITY_MINI_GEL
  entities_end

; continued…

Easy enough: each list is associated to a room, and an entity is defined by its vertical position, horizontal position, and type. A nice, well-structured data format, without surprising behaviors. Thanks, original game developers.

Of course this nice readable list owes much to a couple of macros, that help to transform the readable values into a sequence of bytes:

; code/macros.asm

; Define an entity in an entities list
; Usage: entity <vertical-position>, <horizontal-position>, <type>
entity: macro
    db   \1 * $10 + \2, \3
endm

; Mark the end of an entities list
entities_end: macro
    db   $FF
endm

Entities handlers

Once entities are loaded in a room, they need to actually do something. For this, each entity has an associated entity handler. This piece of code is responsible for defining how the entity looks, how it is animated, and how the player can interact with it.

Entities handler are executed on every frame, for each entity. This is implemented by having a large table of function pointers to all entities handlers.

On each frame, the game will enumerate all entities, and:

  1. Load the current index of the entity,
  2. Lookup the address of the handler for this entity in the handlers table,
  3. Execute the entity handler.

Until know, although the code banks containing the entity handlers lookup table and code has been identified, the code fragments weren’t properly sorted out. All of this looked like a mess of instructions, dozens of thousands of them.

; Table of entities handlers
; First 2 bytes: memory address; third byte: bank id
EntityPointersTable::
._00 db $34, $6A, $03
._01 db $61, $44, $19
._02 db $96, $66, $03
._03 db $E3, $7B, $18
._04 db $B2, $69, $03
._05 db $28, $53, $03
._06 db $49, $52, $03
._07 db $DD, $7B, $07
._08 db $66, $79, $18
._09 db $E9, $57, $03
._0A db $26, $6A, $03
._0B db $27, $58, $03
; continued…

Cross-referencing all these function pointers to their respective location in the source code was tedious, and took several weeks.

But now, every handler has been labeled and cross-referenced in the handlers table. And again, a small entity_pointer macro even makes it easy to read:

; First 2 bytes: memory address; third byte: bank id
entity_pointer: macro
    db LOW(\1), HIGH(\1), BANK(\1)
endm

; Table of entities handlers
EntityPointersTable::
._00 entity_pointer ArrowEntityHandler
._01 entity_pointer BoomerangEntityHandler
._02 entity_pointer BombEntityHandler
._03 entity_pointer HookshotChainEntityHandler
._04 entity_pointer HookshotHitEntityHandler
._05 entity_pointer LiftableRockEntityHandler
._06 entity_pointer PushedBlockEntityHandler
._07 entity_pointer ChestWithItemEntityHandler
._08 entity_pointer MagicPowderSprinkleEntityHandler
._09 entity_pointer OctorockEntityHandler
._0A entity_pointer OctorockRockEntityHandler
._0B entity_pointer MoblinEntityHandler
; continued…

How useful is that?

Well, now it’s easy to know which section of code is responsible for the behavior of a specific entity. Are you interested by the exact behavior of arrows? Do you want to explore all the easter-egg messages Marin can tell to Link when following him? How are the several forms of the end-game boss implemented? You can just follow the handlers table, and start reading the code for these entities.

What’s next?

Of course, there is still a lot of work to be done regarding entities.

First, it would be nice to move all entities handler to their own files. Instead of having large files like entities/bank15.asm, they would be split into entities/arrow.asm, entities/marin.asm, and so on.

Also, the code for these entities is not documented yet: many helpers used to work with entities are not understood yet, which makes the code difficult to read. Documenting all these helpers would definitely help.

The way the game loads entities is not completely figured out yet. Notably, the behavior where entities cleared in a room do not immediately respawn when moving to another room is still mysterious to me: the game must have a way to keep track of which entities have been destroyed recently (in order not to respawn them), but how?

Last, we can see in the handlers table that several entities have been blanked out during the development of the game – but also that several entities have associated code, but never appear in the game. Analyzing the code to see what these entities were supposed to do could sure be interesting.

Want to read more? Discover more of the code, or join the discussion on Discord.

Link’s Awakening disassembly progress report – part 7

This article is part of an ongoing “Disassembling Link’s Awakening” series, where I attempt to gain some understanding on how special effects were implemented in this game.

The big news of this progress report is that the disassembly is finally standalone: it doesn’t require the original ROM anymore to fill out uncompleted sections. The project can now be built entirely only from its source code.

Why wasn’t that done before? After all mgbdis, the most-commonly used disassembler, can generate a valid disassembly of any Game Boy ROM in ten seconds.

So what took so long?

In the beginning

First, at the time this project begun, mgbdis didn’t exist. So the project started with a custom-made disassembler, written in C.

As a work-in-progress, support for less common special cases was added progressively to this disassembler. Which means it was tested first on a few sections of code – hoping that progressive improvements would allow it to generate the entire disassembly.

But instead, this custom disassembler slowly bitrot.

mgbdis

Enter mgbdis: a pretty nice generic disassembler, that guarantees it will always generates valid code that can be compiled back to the original ROM. Awesome! We can now apply it to our game, have it entirely disassembled, and commit the result to the project, right?

The problem is that some sections were already decompiled using the custom disassembler, which uses slightly different conventions. How to make these existing sections match the mgbdis output format? We won’t want to re-generate these sections from scratch: there are already heavily documented, with labels and annotations in comments.

In the end, the most sensible way to produce a good disassembly was to improve mgbdis itself, so that it would be useful even when working with an existing partial disassembly. This meant:

In the end, it was possible to generate the entire disassembly using mgbdis, while respecting the existing code, symbols and formatting conventions. Then it was just a matter of copying the code into our partial disassembly, section by section – having just to fix up a small number of remaining errors on the way.

Very good, but not entirely satisfying.

Code and data

You see, one of the initial tasks when working on a vintage game disassembly is separating code from data.

Most cartridge-based games of the early days don’t have a file system. Everything is compiled into a single binary file (usually called a ROM)1.

So when trying to figure out how the game work, there are no separate files in the ROM – and usually no metadata to tell us which parts of the binary are compiled code, 2D-textures, 3D-models, animations, maps, music… All we have is this large binary file, and we must try to sort out code from data.

A basic solution to this problem is to interpret everything as code. When generating a disassembly, let’s just consider every byte to be a valid code instruction. This is exactly the approach of mgbdis.

Every time a new section of code was copied from the mgbdis-generated disassembly, we knew that a large part of this code was probably actually data. And it felt inelegant to just insert these wrong segments of code into the project. Shouldn’t we sort out code from data before inserting them into the project; at least roughly?

This is why the integration of the mgbdis-disassembled sections was slow: before generating each section of code, it was manually scanned to guess which sections would actually be data. Many sections were integrated to the projects using this process, but it was tedious and slow.

Fortunately, some people tried to find solutions to automatically sort out code from data.

A tracing disassembler

A partial solution for sorting out code from data is to use a profile-guided disassembler. The idea is to play the game in a special emulator, which records every instruction executed to a game profile. Then a disassembler can use this profile to mark every executed instruction as code – and all the other as data.

The issue with this, of course, is that any missed code path will be interpreted as data. If during the profile-recording the player misses a gameplay branch, the code for this branch will never be marked as executed. And so this code will be turned into data by the disassembler.

If only we could know which code paths are executable, without having to play through every branch of the whole game…

That’s exactly the idea behind tracing disassemblers. Instead of being guided by the game being playing dynamically, a tracing disassembler will read the ROM statically, without actually executing it. But it will try to follow the flow of the instructions, one by one, and mark all the reachable bytes as code. In the end, all the possible branches should be traced – which means that all the remaining bytes are data.

Of course, this means a tracing disassembler must be good at following code paths. If some code path are missed, they will incorrectly appear as data instead. And following code paths can prove quite challenging.

Instructions

The easiest case, of course, is easy: start with the entry point of the ROM, and follow instructions from there. For instance, with simple instructions:

EntryPoint::
    ld   a, $30        ; $0100
    ld   [rP1], a      ; $0102
    ld   a, $01        ; $0104
    ld   [rKEY1], a    ; $0106

Great, so we know that bytes $0100 to $0108 of the ROM are actually code (and not data).

Jumps

When an unconditional jump occurs, we can simply mark the target address as being executable – and continue the tracing from here. For instance, continuing from the previous example:

    ld   [rKEY1], a    ; $0106
    jp   $0120         ; $0108

So we know that byte $0108 is really code – but also that the jump target address, $0120, also holds some executable code. And the tracing can continue from there.

And when the code reaches a conditional jump, then both the target address and the next instruction are marked as executable. The disassembler will then trace one of the code paths until the end, then remember to follow the other one later.

    ldh  a, [$FFF1]     ; $0120
    jp   z, $0200       ; $0121
    xor  a              ; $0124
    ldh  [$FFF1], a     ; $0125

In this case, when reaching the instruction jp z, $0200 (i.e. “jump to $0200 if the result of the previous operation is zero”), two addresses are marked as executable: the jump target address, $0200, and the next instruction taken if the branch is not taken, $0124.

Banking

Here start the issues.

Older consoles like the NES, Super NES and Game Boy have this concept of banks. Banks solve a problem that presents itself very quickly when programming a game on these consoles: the addressing space is too small. As pointers are only two-bytes long, the maximum length of ROM that can be addressed in 65 KB. And games can grow bigger than that pretty quickly. Although Super Mario Bros. 1, as a marvel of engineering, takes just under 32 KB, many games will need much more resources to display rich graphics, sounds and behavior. Link’s Awakening DX, for instance, is a 1 MB game.

Game Boy memory map – without bank switching

So how was this addressing problem solved? By allowing some of the address space to be swapped dynamically during gameplay. For instance, on the Game Boy, there are two code slots (a.k.a “banks”) of 16 KB: the first one, usually referred as bank 0, is always loaded into memory. But the second one is dynamic: the game can request for bank 3, 4 or 42 to be loaded into memory, and then copy data or execute code from this bank.

Game Boy memory map – using bank switching

Problem solved!2

So banks can be swapped in and out. When reading a game’s source code, it can for instance look like this:

    ; Load bank 2 into memory
    ld   a, $02                             ; $0200
    ld   [MBC3SelectBank], a                ; $0202
    ; Jump to the address $4020 in bank 2
    jp   $4020                              ; $0205

So, taken all by itself, the “jump at address $4020” is ambiguous: it could mean “the address $4020 in bank 1”, or “the address $4020 in bank 5”, or in bank 37 – it all depends on the bank currently loaded. Although here we know by reading the code that the loaded bank will be bank 2.

Which means that, in order to know what an address actually refers to, a tracing disassembler has to know which bank is loaded at the point an instruction is executed.

Fortunately, in the example above, the bank switch is relatively easy to figure out: the disassembler can track when a new value is written to the MBC3SelectBank memory address, and update it’s internal representation accordingly. Although, as you can see, the bank write always goes through an intermediate register (in the example above, a). So to know which value is written to MBC3SelectBank, the disassembler must also track the content of each register. Err, not so easy, but ok.

So now we can trace code jumping through different banks. Good.

Dynamic bank switching

Enter dynamic bank switching. Often, the bank number isn’t hardcoded in the ROM: it is figured out at runtime. For instance, some code could be written like this:

    ; If the player in currently indoors…
    ld   a, [hIsIndoor]
    and  a
    jp   z, .outdoor
    ; … use the bank $20
    ld   a, $20
    jp   .endIf
.outdoor
    ; … else use the bank $21.
    ld   a, $21
.endIf

    ; Load bank $20 or $21 into memory
    ld   [MBC3SelectBank], a
    ; Jump to address $4020 in bank $20 or $21
    jp   $4020

So the disassembler has to understand that, at the point the final jump is executed, the target bank can actually have several different values.

And this is the easiest case: the bank number can be further manipulated by a function–or even read at runtime from some sort of table. Great.

In this case, a tracing disassembler may try a combination of being smart (like storing the different possible values for the active bank), or starting to require human assistance. For instance, a human can read the code, and then tell the disassembler that at this specific location, a can only be $20 or $21 (instead of just any possible value).

Dynamic jumps

We’ve seen how the bank number can sometime by dynamically generated at runtime – but the jump address also can.

Often games will read the target address of a jump from an external array (which is sometime called a “jump table”). And sometime the address will even be computed entirely from code.

JumpTargetsArray:
    dw   $4000
    dw   $4100
    dw   $4200

JumpToTarget::
    ; Make `hl` the address of the jump targets array
    ld   hl, JumpTargetsTable
    ; Add the array index contained in `bc` to `hl`
    add  hl, bc
    ; Read the jump target address from the table
    ld   a, [hl]
    ; Jump to the address read from the table.
    ; (Can be either `$4000`, `$4100`, or `$4200`.)
    jp   hl

This is often the nail in the coffin for tracing disassemblers. It becomes very hard to figure out the jump target without executing the entire program. And if the tracing disassembler can’t figure out the target, then all the code accessible from this jump will be flagged as a blob of data, instead of code.

This is generally the moment when some per-game configuration has to be done by hand. Dynamic jumps are not that frequent in a game – and they usually follow a predictable pattern. So, by writing custom recognizers that can identify these formats, the disassembler can read the jump tables directly – and mark all the targets addresses as executable code.

Of course the recognizers to identify the jump table patterns are different for every game. And even in the same game, some dynamic jumps don’t obey to a specific pattern: they must be identified using a single-use recognizer, that will be applied only to a single code location.

So, while this is the end of our dream for a completely automated tracing disassembler, all of this is still useful. Even if some manual work is required, this is way better than manually going through lengthy sections of disassembled output, figuring out where the code stops and the data starts.

Making the disassembly standalone

Tracing disassemblers for the Game Boy are still experimental. But Discord user @featherless provided the output of a custom tracing disassembly which they are working on, applied to Link’s Awakening ROM.

And the results are stunning: in banks containing a lot of mingled code and data, the tracing disassembler can sort out executable code from other arrays, tables, and data with great accuracy.

So three months ago, when the final rush to finally add the remaining missing banks to the disassembly started, having this traced disassembly made adding the last banks much easier. Of course some manual work had to be performed to match the style of the existing disassembly – but it was way better than identifying data sections by hand.

Conclusion

So the disassembly is now standalone: it can compile back to the target ROM without needing external resources.

More important, the general purpose of each code section is roughly figured out. Instead of a long series of files named “bank35.asm”, “bank36.asm”, “bank37.asm”, most of the files are split and named according to the function of the role they contain (“entities.asm”, “super_gameboy.asm”, “photos_cutscenes.asm”, and so on).

Of cours most of this code is still generated by an automatic disassembler: there are no human-readable labels or documentation about the exact purpose of each function yet. All this work still has to be done. But it will be much easier to figure this out once the large pieces of the puzzle are identified.

For instance, good progress has been made recently on understanding the how entities system works. Hopefully this will be further expanded in the next progress report.

New contributors

Since the last report, the following people made first-time contributions to the project:

Want to read more? Discover more of the code, or join the discussion on Discord.

  1. This lasted more or less until the advent of CD-based games, which started to use file systems to package the various game assets. 

  2. Of course, for game developers, this “solution” of using banks quickly becomes a programming nightmare. Swappable banks mean, for instance, that code can’t jump from bank 2 to bank 3, as only a single non-0 bank can be loaded into memory at once. Writing a routine in bank 4 that copies data in bank 2? Also not possible: these two banks can’t be loaded at the same time.

    Every time an operation like this is needed, the code has to use a trampoline: a small piece of code in the bank 0 (which is always loaded) that will swap the banks, execute the target code, and then swap back to the original bank. So code has to be architected around this limitation, which this is usually one of the major hurdle to making ambitious games on these platforms.