World Builder Formats

 The following is documentation that I've created as a result of reverse engineering the various file formats used by World Builder games.

NOTE: All types are big-endian unless otherwise specified.

Overview

It is assumed that you can read HFS disk images. As a part of being able to read HFS disk images, you can also parse a file's resource fork.   All of this is well-documented on the internet.  The formats for standard resources (such as DLOG or MENU) are also well-documented and outside the scope of this blog post.

Main Resource Fork

The main executable contains a resource fork which holds nearly all of the assets and UI for the game. It can be identified by the filetype APPL and the creator WEDT.

Common Structures

The following structures are commonly used by the various data formats:

struct Rect {

    int16 top;     // 00

    int16 left;    // 02

    int16 bottom;  // 04

    int16 right;   // 06

}

struct String {

    uint8 length;  // 00

    uint8 data[];  // 01

}

ACHR

This contains the graphics and information on various characters in the game.  This includes the main player, or players if there are more than one.

All strings, except for initial_scene can be blank.

struct ACHR {

    uint16   offset_to_bounds;   // 00

    Graphics graphics[];         // 02

    Rect     bounds;             // offset_to_bounds

    uint8    physical_strength;  // +08

    uint8    physical_hp;        // +09

    uint8    physical_armor;     // +0a

    uint8    physical_accuracy;  // +0b

    uint8    spiritual_strength; // +0c

    uint8    spiritual_hp;       // +0d

    uint8    magic_resistance;   // +0e

    uint8    spiritual_accuracy; // +0f

    uint8    running_speed;      // +10

    uint8    reject_offers;      // +11

    uint8    follows_opponent;   // +12

    uint8    unknown;            // +13

    uint32   unknown;            // +14

    uint8    weapon1_damage;     // +18

    uint8    weapon2_damage;     // +19

    uint8    unknown;            // +1a

    uint8    is_player;          // +1b

    uint8    carry_amount;       // +1c

    uint8    return_to;          // +1d

    uint8    winning_weapon;     // +1e

    uint8    winning_magic;      // +1f

    uint8    winning_run;        // +20

    uint8    winning_offer;      // +21

    uint8    losing_weapon;      // +22

    uint8    losing_magic;       // +23

    uint8    losing_run;         // +24

    uint8    losing_offer;       // +25

    uint8    gender;             // +26

    uint8    proper_noun;        // +27

    String   initial_scene;      // +28

    String   weapon1_name;

    String   weapon1_verb;

    String   weapon2_name;

    String   weapon2_verb;

    String   initial_comment;

    String   score_hit;

    String   receive_hit;

    String   make_offer;

    String   reject_offer;

    String   accept_offer;

    String   die;

    String   initial_sound;

    String   score_hit_sound;

    String   receive_hit_sound;

    String   die_sound;

    String   weapon1_sound;

    String   weapon2_sound;

}

offset_to_bounds

    Byte offset to beginning of bounds rectangle. If there are no graphics, this will be 2.

graphics

    Visual representation of this character.  The format is documented in the Graphics section.

bounds

    The bounding box for the character's graphics.

physical_strength

    Determines damage done with physical weapons.

physical_hp

    The character's hit points.

physical_armor

    Reduces damage taken from physical attacks.

physical_accuracy

    Chances of missing a physical attack.

spiritual_strength

    Determines damage done with magic

spiritual_hp

    The character's mental hit points.

magic_resistance

    Reduces damage taken from magical attacks.

spiritual_accuracy

    Chances of missing a magical attack.

running_speed

    Used to check if you can flee an enemy, or chase one down.

reject_offers

    Maximum price of offers to reject.  Offers above this will be accepted.

follows_opponent

    Chance of following you if you run.

weapon1_damage

    Damage caused by first innate weapon (punches or claws, etc).

weapon2_damage

    Damage caused by second innate weapon (kicks or fire breath, etc)

is_player

    There can be multiple players.  In that case, the game will chose a random character marked with is_player as the main player character.

    0: enemy

    1: player

carry_amount

    Number of items you can have in your inventory.

return_to

    Scene to teleport the character to when it dies.

    0: STORAGE@

    1: RANDOM@

    otherwise: use initial_scene

winning_weapon

    Odds of using a weapon if the mob has more HP than you.

winning_magic

    Odds of using magic when winning.

winning_run

    Odds of fleeing when winning

winning_offer

    Odds of making an offer when winning.

losing_weapon

    Odds of using a weapon if mob has less HP than you.

losing_magic

    Odds of using magic when losing

losing_run

    Odds of fleeing when losing

losing_offer

    Odds of making an offer when losing.

gender

    0: male

    1: female

    2: it

proper_noun

    Whether or not a character's name is a proper noun.  "A robot attacks" vs "Robot attacks".

initial_scene

    The name of the initial scene for this character. Can also be STORAGE@ or RANDOM@.

    If so, then return_to should be set accordingly.

weapon1_name

    The name of the first innate weapon. (Claws, fire, etc).

weapon1_verb

    The verb to use for that weapon. ("breathe" fire, etc.)

weapon2_name

    The name of the second innate weapon.

weapon2_verb

    The verb to use for that weapon.

initial_comment

    Message to print when mob first appears.

score_hit

    Message to print when mob scores a hit.

receive_hit

    Message to print when mob gets hit.

make_offer

    Message to print when mob makes an offer.

reject_offer

    Message to print when mob rejects your offer.

accept_offer

    Message to print when mob accepts your offer.

die

    Message to print when mob dies.

initial_sound

    Sound to play when mob first appears.

score_hit_sound

    Sound to play when mob scores a hit

receive_hit_sound

    Sound to play when mob gets hit.

die_sound

    Sound to play when mob dies

weapon1_sound

    Sound to play when mob uses first innate weapon.

weapon2_sound

    Sound to play when mob uses second innate weapon.

AOBJ

This contains the graphics and information for various objects in the game.

struct AOBJ {

    uint16   offset_to_bounds;  // 00

    Graphics graphics[];        // 02

    Rect     bounds;            // offset_to_bounds

    uint8    plural;            // +08

    uint32   unknown;           // +09

    uint8    accuracy;          // +0d

    uint8    value;             // +0e

    uint8    type;              // +0f

    uint8    damage;            // +10

    uint8    effect;            // +11

    int16    uses;              // +12

    uint8    return_to;         // +14

    uint8    unknown;           // +15

    String   owner;             // +16

    String   pickup_message;

    String   operative_verb;

    String   failure_message;

    String   successful_use;

    String   operative_sound;

}

enum Types {

    unknown         = 0,

    regular_weapon  = 1,

    thrown_weapon   = 2,

    magical_object  = 3,

    helmet          = 4,

    shield          = 5,

    chest_armor     = 6,

    spiritual_armor = 7,

    mobile_object   = 8,

    immobile_object = 9,

}

enum Effects {

    cause_physical_damage  = 0,

    cause_spiritual_damage = 1,

    cause_both_damage      = 2,

    heal_physical_damage   = 3,

    heal_spiritual_damage  = 4,

    heal_both_damage       = 5,

    freeze_opponent        = 6,

}

offset_to_bounds

    Byte offset to beginning of bounds rectangle. If there are no graphics, this will be 2.

graphics

    Visual representation of this object. The format is described in the Graphics section.

bounds

    Bounding box for the object's graphics.

plural

    Whether or not this object is plural.  "You see an arrow" vs "You see some arrows".

accuracy

    Accuracy modifier if this is a weapon.

value

    Price of this object, for making offers.

type

    Type of object, Immobile_objects cannot be moved, they're used to decorate a scene.

damage

    If this is a weapon, this is the damage it causes. If this is armor, then this is the amount of protection in provides.  If this is a magical object, then this is the spell armor.

effect

    If this is a magical device, this determines what it does.

uses

    Number of times this object can be used before it breaks. -1 : indestructible.

return_to

    Where to respawn this object when it breaks.

    0: STORAGE@

    otherwise: Spawn in a random scene.

owner

    Initial owner of this object. Might be the name of a scene or a character. Can also be STORAGE@ or RANDOM@. If random, that means a random scene, not a random character.

pickup_message

    Message to print if the item is picked up

operative_verb

    Verb to use for this object. "Eat" a cake, for example.

failure_message

    Message to print if item breaks.

successful_use

    Message to print if item is used successfully.

operative_sound

    Sound to play when item is used.

ASCN

This contains the graphics and information for every room or "scene" in the game. It also determines the size and location of the graphics window.

struct ASCN {

    uint16   offset_to_bounds;    // 00

    Graphics graphics[];          // 02

    Rect     bounds;              // offset_to_bounds

    uint16   map_y;               // +08

    uint16   map_x;               // +0a

    uint8    blocked_north;       // +0c

    uint8    blocked_south;       // +0d

    uint8    blocked_east;        // +0e

    uint8    blocked_west;        // +0f

    uint16   frequency;           // +10

    uint16   loop_type;           // +12

    String   north_text;          // +14

    String   south_text;

    String   east_text;

    String   west_text;

    String   ambient_sound;

}

offset_to_bounds

    Byte offset to beginning of bounding box. If there are no graphics, this will be 2.

graphics

    Visual representation of this scene. The format is documented in the Graphics section.

bounds

    Bounding box for the main graphics window.

map_y

    Y coordinate (0-49) of this scene in the world map.

map_x

    X coordinate (0-49) of this scene in the world map.

blocked_north

    Whether or not the north exit is blocked

blocked_south

    Whether or not the south exit is blocked.

blocked_east

    Whether or not the east exit is blocked.

blocked_west

    Whether or not the west exit is blocked.

frequency

    How often to play the ambient sound while in this scene. The actual meaning of the value depends on loop_type.

loop_type

    How to loop the ambient sound. 0 means play the sound frequency times per hour, with the first time being when you enter the room. Otherwise, play the ambient sound randomly.  In that case, there is a frequency out of 3,000 chance of playing for every second you remain in the room.

north_text

    Message to print if you try to go north while it is blocked.

south_text

    Message to print if you try to go south while it is blocked.

east_text

    Message to print if you try to go east while it is blocked.

west_text

    Message to print if you try to go west while it is blocked.

ambient_sound

    Sound to play as ambient noise.  See frequency and loop_type for how to play this.

ATXT

This contains the intro text for a room or scene, as well as information on the text window's location and font.  There is one ATXT for every ASCN.

struct ATXT {

    Rect    bounds;  // 00

    uint16  fontid;  // 08

    uint16  size;    // 0a

    char    text[];  // 0c

}

bounds

    The bounding box for the text window

fontid

    The Macintosh font ID for the font to use

size

    Font size (in points) to use

text

    Text to show. This just runs until the end of the resource.

ASND

This contains a single digitized sound.

struct ASND {

    uint16  channels;    // 00

    uint16  loops;       // 02

    int8    deltas[16];  // 04

    uint8   data[];      // 14

}

channels

    I believe this is the number of channels. Every sound I've found is always 1 (mono) however.

loops

    The number of times to loop this sound.

deltas

    A 16-byte array of deltas to use when parsing the sample data.

data

    Each byte represents 2 samples.  The high nibble is the first sample, the low nibble is the second. You use each nibble to look up a delta in the deltas array, and add it to the current sample value. The resulting byte is the next sample.  The sample value starts at $80.

The final sample is an 8-bit unsigned PCM array.  The sound is always played back at 22.2545 kHz, but stored at half that.  The way the engine compensates for this is to store last + delta in buffer[i + 1] and last + delta / 2 in buffer[i], essentially interpolating the audio.

ACOD / GCOD

This contains the code for the scene or global context.  There is an ACOD for every ASCN in the game, and a single GCOD resource.  The GCOD resource is only run when the ACOD resource for the scene exits without hitting an EXIT opcode.

These code resources are run whenever the user does something, like clicking on an object or typing a command.  Whenever a user changes scenes, a fake LOOK command is issued.

struct ACOD {

    Rect    bounds;  // 00

    uint16  fontid;  // 02

    uint16  size;    // 0a

    char    code[];  // 0c
}

bounds

    Bounding box for the script window.  Only used in the world editor, since the script window isn't visible in game.

fontid

    Macintosh font ID for the script window.

size

    Font size (in points) for the script window.

code

    The code to run for this script, see the section below on Code format.

Code Format

The code format is basically just a tokenized scripting language. You can translate the tokens back into their original instructions for displaying the scripting window.  The tokens are listed below, along with how each instruction changes the tab depth (which is used both visually, as well as to determine execution flow).

$80    "IF ("      depth++

$81    "="

$82    "<"

$83    ">"

$84    ") AND ("

$85    ") OR ("

$87    "EXIT\n"    --depth

$88    "END\n"     --depth

$89    "MOVE ("

$8a    ") TO ("

$8b    "PRINT("

$8c    "SOUND("

$8e    "LET("

$8f    "+"

$90    "-"

$91    "*"

$92    "/"

$93    "="

$94    "!"

$95    "MENU("

$a0    "TEXT$"

$a1    "CLICK$"

$b0    "VISITS#"

$b1    "RANDOM#"

$b2    "LOOP#"
$b3    "VICTORY#"

$b4    "BADCOPY#"

$c0    "STORAGE@"

$c1    "SCENE@"

$c2    "PLAYER@"
$c3    "MONSTER@"

$c4    "RANDOMSCN@"

$c5    "RANDOMCHR@"

$c6    "RANDOMOBJ@"

$d0    "PHYS.STR.BAS#"

$d1    "PHYS.HIT.BAS#"

$d2    "PHYS.ARM.BAS#"

$d3    "PHYS.ACC.BAS#"

$d4    "SPIR.STR.BAS#"

$d5    "SPIR.HIT.BAS#"

$d6    "SPIR.ARM.BAS#"

$d7    "SPIR.ACC.BAS#"

$d8    "PHYS.SPE.BAS#"

$e0    "PHYS.STR.CUR#"

$e1    "PHYS.HIT.CUR#"

$e2    "PHYS.ARM.CUR#"

$e3    "PHYS.ACC.CUR#"

$e4    "SPIR.STR.CUR#"

$e5    "SPIR.HIT.CUR#"

$e6    "SPIR.ARM.CUR#"

$e7    "SPIR.ACC.CUR#"

$e8    "PHYS.SPE.CUR#"

$fd    ")\n"

$fe    ") THEN\n"        depth++

$ff    global

Globals are stored in a single byte that follows the $ff opcode.  The names of the globals are represented as A0-A9, B0-B9, C0-C9, and so on.  Thus, globals can only be from $00 to $ea, since $ea is Z9.

Any character in the script without the high-bit set represents itself.  So strings and such are just stored in plaintext.

NOTE: This also includes any constant numbers.  42 is stored as the string "42".

Graphics Data Format

The graphics data found in various assets, including the background, all follow the same format.  It is comprised of a list of shapes, with their corresponding patterns and pens.  The patterns are indices into the PAT# resource, with the first pattern identified with the index 1.

You will need to use the quickdraw routines to accurately draw these shapes.

There is no END code, so just keep parsing and drawing shapes until you hit the end of the graphics section.

Each shape begins with the same header:

struct Shape {

    uint8  fillPattern;  // 00

    uint8  penSize;      // 01

    uint8  penPattern;   // 02

    uint8  shapeType;    // 03

}

enum ShapeType {

    rectangle   = 4,

    roundedRect = 8,

    oval        = 0xc,

    polygon     = 0x10,

    freeHand    = 0x14,

    bitmap      = 0x18,

}

fillPattern

    This is the pattern to use as a fill for the shape.  $1e is reserved to represent no fill at all.

penSize

    This is the size (in pixels) of the pen to use as a stroke for the shape.  $00 is reserved to represent no stroke.

penPattern

    This is the pattern to use for the stroke, $1e is reserved to represent no stroke.

shapeType

    This indentifies which shape to draw.  The shape-specific data follows the header.

Rectangle ($04)

Draws a rectangle at the provided coordinates.  These may be partially or even entirely offscreen.

struct Rectangle {

    Shape header;  // 00

    Rect  bounds;  // 04

}

Rounded Rectangle ($08)

Draws a rounded rectangle with the provided coordinates and corner radius.  This may be partially or entirely offscreen.

struct RoundedRect {
    Shape  header;  // 00

    Rect   bounds;  // 04

    uint16 radius;  // 0c

}

Oval ($0c)

Draws an oval in the provided bounds.  This may be partially or entirely offscreen.

struct Oval {

    Shape header;  // 00

    Rect  bounds;  // 04

}

Polygon ($10)

Draw a polygon

struct Polygon {

    Shape  header;     // 00

    uint16 smoothness; // 04

    uint16 length;     // 06

    Rect   bounds;     // 08

    int16  start_y;    // 10

    int16  start_x;    // 12

    int8   data[];     // 14

}

The bounds aren't used for drawing, but for highlighting the shape in the world editor.  The length determines the size of all the data following the length field, including the length field.

Smoothness determines how many times to subdivide the polygon before drawing it.

The polygon data itself uses a light compression algorithm.  The starting point for the polygon is given in start_x and start_y.  Loop through the data, and if the value is -128, then the next int16 is a new Y coordinate.  Otherwise, add the value to the current Y coordinate.  The next value is for the X coordinate, and so on until the end of the array.

FreeHand ($14)

This shape was actually created using a different drawing tool in the editor, but the storage and appearance is identical to the Polygon.

Bitmap ($18)

Draws a bitmap in the viewport.

struct Bitmap {

    Shape  header;    // 00

    uint16 length;    // 04

    Rect   bounds;    // 06

    uint8  packed[];  // 0a

}

The width of the bitmap is always a multiple of 8.  To unpack the data, you must calculate how many bytes each expanded row will be.  You can simply divide the width by 8 for this.

Next, you will run the algorithm below for each scanline.  Run until you've expanded the correct number of bytes.

The algorithm is a simple RLE format.  The first byte is the opcode.  If it is $80, do nothing and move onto the next opcode.  Otherwise, if the high bit is set, copy the next byte into the output -opcode + 1 times.  If the high bit is not set, copy opcode + 1 bytes from the input into the output.

This is widely known as the PackBits algorithm,  You'll see it referenced as the TIFF or PICT PackBits algorithm.

And that's everything I know about the World Builder file formats.

Self-Modifying Code

When you read about programming in the 80s, often there is a discussion about how common assembly was.  You'll hear about all sorts of mystic tricks and tips that programmers back then used.  You might have also heard reference to "self-modifying code".

When I was younger, "self-modifying code" always sounded so advanced.  It was something that only the very brightest people did, and they surely must've done it to prevent people from disassembling their code.

The reality is much more mundane.  I'll show you a real example of self-modifying code from a piece of commercial software from the 80s.  I'll walk you through it, and explain why it was written this way.

The code in question is from an Apple IIgs game (the CPU is a 65816, which is a 16-bit variant of the classic 6502).

00/0e4e: a9 00 60    lda #$6000     ; A = $6000

00/0e51: 8d 6d 0e    sta $0e6d      ; mem[$0e6d] = A

...

00/0e65: e2 30       sep #$30       ; 8-bit registers

00/0e67: a2 00       ldx #$00       ; X = 0

00/0e69: bd 00 0a    lda $0a00, x   ; A = mem[$0a00 + X]

00/0e6c: 8d ff ff    sta $ffff      ; mem[$ffff] = A  !!!

00/0e6f: ee 6d 0e    inc $0e6d      ; mem[$0e6d]++

00/0e72: d0 03       bne $00/0e77   ; is result != 0?

00/0e74: ee 6e 0e    inc $0e6e      ; no, mem[$0e6e]++

00/0e77: e8          inx            ; X++

00/0e78: d0 ef       bne $00/0e69   ; is result != 0?

That's a chunk of real self-modifying code, let's go through it.   Notice the references to memory at addresses $0e6d and $0e6e.  If you look at the address labels on the side, you'll see those addresses point to the operand of the instruction I've marked with "!!!".  By modifying the values at those addresses, we cause the "sta" instruction to point to arbitrary 16-bit addresses.  That's the only part of this code that gets modified.  Mundane, right?

I put pseudocode over on the right so you can see what each instruction does even if you don't know 65816 assembly.  Basically the code does this:

uint8_t *ptr = &memAt6000;

...

   for (x = 0; x < 0x100; x++) {

     *ptr++ = memAtA00[x];

   }

The observant among you will wonder why we go through all this hassle when you could instead do: sta $6000, x.  (which is basically the same as ptr[x] = memAtA00[x])

There are several reasons.  One is the result isn't quite identical.  In the original, when the loop is finished, the pointer points to the end of the array, not the beginning. This is important in the original code because this is actually an inner loop that gets run multiple times by an outer loop, which leads us to two, because it gets run multiple times, the array grows beyond the bounds of an 8-bit index register.

Why not just use a variable elsewhere in memory to store the pointer then?  Surely this doesn't need to be self-modifying.

Well, actually it does.  It has to do with the addressing modes available, or not available as it were.

You see, the 65816 only allows indirect addressing on the direct page (known as the zero page on the 6502).  Absolute addressing doesn't offer any indirect modes.  Needless to say, the direct page gets a bit crowded, and programmers have just decided that its far more elegant to use self-modifying code to "fake" indirect absolute addressing.. which is why this technique is rampant on the Apple IIgs.

It's also less confusing in practice.  The direct page can move around, so you either keep track of it by hand (setting it to the appropriate place upon entering a routine, adding mental and real overhead) or you leave it in a single place the entire time (limiting you to less than 128 pointers for your entire program).  It becomes clear that this particular style of self-modifying code is an elegant solution to the problem.

This isn't the only use-case of self-modifying code, of course, but it is one of the most common, especially on machines with limited addressing modes.

A Word Search Generator

A while ago I needed to generate a daily word search using a word list that was unique for each day.  I didn't find anything online so I invented my own algorithm.  It is designed to encourage words to overlap as much as possible.

The setup for the algorithm is very simple and a bit boring, so I'll just cover the basics here.  The two things we need before we begin is a list of words to put in the word search, as well as the dimensions of the letter grid.  For my implementation, the dimensions and a file containing a whitespace-separated list of words were passed in as arguments.

The word list also needs one other, non-obvious thing.  You need to make sure that none of the words in the word list are substrings of any other words in the word list.  Be sure to check for reverse matches as well.  For example, "times" and "emit" would be very confusing to search for.

Then before we hit the main algorithm, we sort the word list by length, with the longest words first.  We then loop through all the words in the word list and attempt to insert them into the grid.  If we succeed, we mark the word as used so we can later print it out as part of the clue list.

for (word : words) {

  if (addWord(grid, word)) {

    word.wasUsed = true;

  }

}

To add a word to the grid, we first loop through every cell in the grid.  We check to see if the cell is blank or if the cell matches the first letter of our given word.  If either of these are true, we measure the score for that position.  Then we move onto the next cell.

addWord(grid: Grid, word: Word): bool {

  bestScore = 0;

  for (y := 0..grid.height) {

    for (x := 0..grid.width) {

      if (grid.cell(x, y) == Blank || grid.cell(x, y) == word[0]) {

        measure(grid, word, x, y);

      }

    }

  }

  // random best fit goes here

  ...

}

To measure the score, we try to place the word in the grid at that location in all directions.  We then calculate a score based on the number of intersections for a given direction.

measure(grid: Grid, word: Word, x: int, y: int) {

  for (dy : [-1, 0, 1]) {

    for (dx : [-1, 0, 1]) {

      if (dx == 0 && dy == 0) {  // no direction

        continue;

      }

      ex := x + word.length * dx;

      ey := y + word.length * dy;

      if (ex < 0 || ex >= grid.width ||

          ey < 0 || ey >= grid.height) {  // word doesn't fit

        continue;

      }

      int score = 1;

      for (i := 0..word.length) {

        cell := grid.cell(x + i * dx, y + i * dy);  // next cell

        if (cell == word[i]) {  // matches word

          score++;

        } else if (cell != Blank) {  // word doesn't fit here at all

          score = 0;

          break;

        }

      }

      if (score >= bestScore) {  // are we among the best matches?

        if (score > bestScore) {

          bestScore = score;

          matches.clear();  // new tier of best scoring matches

        }

        matches.add(Match(x, y, dx, dy));

        if (dx && dy) {  // we want diagonals, so add twice

          matches.add(new Match(x, y, dx, dy));

        }

      }

    }

  }

}

This is the core of the algorithm, so we should look at it at little closer.  We loop through all the directions, which is where dx and dy are one of -1, 0, 1.  If both dx and dy are 0, then that doesn't point in any direction, so we skip that case.  We calculate the end position of the word for the current direction and check to see if it fits on the grid.  If not, we skip that direction.

Next we calculate the score for that direction.  Encountering a cell already containing a matching letter is worth 1 point.  This encourages intersecting words.  If we encounter a cell with a different letter, we reset the score to zero and move on since the word doesn't actually fit there.

If the score is among the best scores, we add our current orientation to the list of matches.

What we end up with is a list of all the highest scoring orientations.  Given the choice between a horizontal or vertical match and a diagonal match, we would prefer the diagonal match.  Thus, we've added any diagonal matches to the high-score list twice.

Note that we haven't actually placed the word on the grid yet.. we've just calculated a list of best places to put it.

After we have tested every cell in the grid, we now have a list of possible places to put that word.  If we don't have any, that means the word doesn't fit anywhere in the grid and we should abandon that word and move onto the next.

If we do have a list of possibilities, we should pick a random one and then place the word into the grid.  Then move onto the next word.

Finally, after we have added all possible words to the grid, we loop through the grid and fill out any blanks with random letters.

Then you can output the grid and marked words.

Possible improvements could be the inclusion of red herrings.  When filling in the blanks with random letters, you could use letters from the word list to make "almost" matches.  It's also trivial to make the grid a random shape.  Just take the grid and before you do anything, fill in any blank spaces with a special character.  Then replace the special character with a blank on the final grid.

Oldschool planar graphics and why they were a good idea

Oldschool planar graphics

If you ever work with old hardware, like writing an NES emulator or reverse engineering an old Amiga game, you will inevitably come across planar graphics modes.

These days, with loads of memory and huge color depths, graphics are stored sequentially.  It makes the most logical sense.  The red, green, and blue values for each pixel are just stored in an array, in some predefined order (RGB, BGR, whatever).  There may even be an alpha channel.

Video cards of yesteryear didn't have access to that much ram, so direct color, requiring 3 or 4 bytes of ram per pixel, was out of the question. 

Those old video cards used a palette-based system instead.  There's a palette with the red, green, and blue values of each color.  Then the image data itself is just an array of indices into the palette.  With 256 colors, we can use a single byte per pixel.

This is all very straight forward so far.  However, even 256 colors was extravagant for some older hardware.

What if you only had 16 colors?

With 16 colors, we only need 4 bits per pixel for the indices.  That means that a single byte can modify 2 pixels on the screen.  This works out rather well, since the width of each video mode is always going to be an even number.  With 16 colors, images take up exactly half the amount of space as if we had 256 colors.  The only thing you'd really need to worry about is whether the low nibble (4 bits) is drawn first, or the high nibble?  That of course would be up to the hardware to decide.  Regardless, the sequential palette based system still works.

32-colors - the problem child!

With 32 colors, things get difficult.  We technically only need 5 bits per pixel for the indices, but you cannot really cut up an array of bytes into 5-bit chunks easily.  You could pad it, so that each byte contains the index, but now you're wasting 3 bits per pixel.  That's a lot of space to be wasting.

You could try to cram it all together, so the first 5 bits of the first byte represent the first pixel, and the top 3 bits represent the bottom 3 bits of the second pixel, and the bottom 2 bits of the second byte represent the top 2 bits of the second pixel, and so on.  This is a disaster.  Addressing individual pixels is now a total nightmare.

So our options are waste space, or make addressing suck.

Planes to the rescue!

This is where planar graphics come in to save the day.  Instead of trying to pack all the bits of the indices together, we spread them out across planes. 

A plane is a 1 bit per pixel array.  So any byte of a plane controls 8 pixels.  For 32-colors, we need 5 bits per pixel, so we need 5 planes.

The first plane contains the lowest bits of all pixels.  The second plane contains the second lowest bits of all pixels, and so on.  So to modify the 3rd pixel on the screen, you would modify bit 3 of the first byte of every plane.

It's a bit more complicated than sequential storage, but it's still easy to address a specific pixel (byte = position / 8, bit = position & 7), and it saves a ton of RAM.  Imagine a 320x200 screen with 32 colors.  If we had padded each pixel out, it would require 64,000 bytes.  With planes, we only need (320 * 200 / 8) bytes per plane, with 5 planes, comes to just 40,000 bytes.

Another reason for planes

While planes were super useful for odd bit-length palette sizes like 32 colors, they were also used for expansion reasons.  Let's say we made a system with 16 colors, but intended to upgrade the system later on to 32 colors.

If we made the 16-color system use planar graphics instead of storing the indices in the low and high nibble of each byte, then going to 32-colors only requires adding a new plane somewhere in RAM. The older 16-color games would still work, they just wouldn't ever reference the 16 newer colors in the palette (assuming the new plane was initialized to 0 by the system).

With systems like the Amiga, software could even specify how many planes it wanted to use, and the hardware addressing doesn't even have to change to accommodate it.

Understanding larger disassembly

This past weekend I was disassembling something and it struck me how few people knew how to do what I was doing.

So I figured I would quickly document the process of taking a chunk of disassembled code and putting it into a format that's easier to understand.

The disassembly I'm going to use for my examples is the same disassembly I was working on this weekend.  It is the music playing routines from some Apple IIgs software.

There is some knowledge that you should have before attempting to parse disassembly on any platform.

You should be familiar with the assembly language for your target platform.

Since this code ran on an Apple IIgs, that means you should know 65816 assembly.  If you know 6502 assembly, you're more than halfway there.  The 65816 is a 16-bit successor to the 6502, and is backwards compatible.  There's just a few more opcodes and addressing modes, as well as some additional flags for switching between 8-bit and 16-bit registers.

You should understand how hardware is used on your target platform.

For example, if you're disassembling software that draws to the screen, you should know how the various video modes work and how video memory is laid out.  Since we're disassembling a music player, we should know how the sound card works.

I'm not going to cover how the IIgs sound card works here, if you care, the Apple IIgs Technical Reference covers it.

Locate the code you're interested in.

This is one of the more difficult things to do.  You can't just disassemble an entire executable and hope to parse it all at once, it's far too big.  Instead you need to use some techniques to narrow down your search.

For example, if you're trying to figure out a file format for some file the program uses, you should search the disassembly for OS file calls and then work your way backwards from those calls.

If you're trying to find out how a program does some special graphical effect, then maybe check for code attached to the video blank interrupt (if it has one, again, know your platform).

For our example, we want to find the routine that's tied to the sound interrupt. This interrupt is fired whenever one of the soundcard's channels stops playing a note.  This is the natural place where you would advance the song and set up the soundcard to play the next note.  (Again, know your platform).

Searching through the disassembly I find the following:

00/3b84: a9 5c 98    lda  #$985c
00/3b87: 8f 2c 00 e1 sta  $e1/002c   ; Sound interrupt
00/3b8b: a9 3c 00    lda  #$003c
00/3b8e: 8f 2e 00 e1 sta  $e1/002e

This installs the sound interrupt routine.  It actually stores 5c 98 3c 00 into that memory location.  This is machine code that translates into the assembly "jmp $00/3c98".  So we now know that $3c98 in bank $00 is the sound interrupt routine that we want to understand.

The code next to where the sound interrupt is installed also loads the music into a specific location in RAM, loads all the sample data into the sound RAM, and sets some variables.  You would want to disassemble this routine as well as it paints a clearer picture of what's happening with everything sound-related.  I won't do that here, but this is how I was able to better understand the sound interrupt routine.

Isolate the code you care about, once you've found it.

So now we know the function we care about, we're going to isolate it and any small functions that the code calls.  This helps get rid of noise.

I've got the code we care about uploaded here.  It's 528 lines of assembly.  That's a pretty healthy sized routine.

One thing I'll point out before we get into it.  There are two small routines at $3cd4 and $3cd9 that seem to be redundant and return the value in a table located at $00:0000 (which is a total red flag that something is horribly wrong).  That's not correct.  The function that sets up the sound interrupt routine also replaces those zeroed addresses with calculated addresses into the music data.

That's another lesson.  Assembly programmers will modify program code instead of setting a variable, all just to save a memory access later on.

So how do we begin?  Do we just step through the assembly and see what it's doing?  Well, that's certainly an option, and for smaller routines, I have no problem doing this.  However, with longer routines, you'll want to do what you can to see the structure of the routine.

Visualize the structure of the routine.

I mean that literally.  The best way I've found to do this is to break the assembly up into what's known as "basic blocks".  A basic block is a chunk of contiguous assembly with only a single entry point (at the head), and exit point (at the tail).  You then draw connections between chunks.

There is software that will automatically do this.  It's the first step in a higher-level decompiler.  However, that software is either specific to an architecture, or expensive, or both.  Luckily, it's rather easy to do it by hand.

I like to use GraphViz for this.  It's a simple command-line tool that takes a text file and generates a directed graph from it.

Here's the first two basic blocks from our assembly plotted:

digraph {
  node[shape="record" fontname="helvetica"];
  edge[fontname="helvetica" fontsize=9];
  m3c98 [label="$3c98|$3c9c"];
  m3c98 -> m3c9d;
  m3c9d [label="$3c9d|$3ca0"];
  m3c9d -> m3c9d [label="bmi"];
  m3c9d -> m3ca2;  
}

We start with a node called "m3c98".  This is the very first address in the routine.  It's prefixed with "m" just because node names cannot start with a number.  The node has a label that has 2 records, these records are the entry and exit addresses of the basic block.  This is immediately followed by a connection from this basic block to the next basic block.

You can see how I've also added a label to one of the edges.  If a jump between basic blocks is caused by a branch instruction, I'll put a label on it.  Unlabeled edges are implicit connections (m3c98 will automatically go to m3c9d without any branching).

Doing it this way is quick and easy, you can build the graph progressively as you go through the assembly looking for branches.  If you jump backwards into the middle of a basic block, it's trivial to split that basic block into two blocks and reassign the edges coming from original block to come from the new block instead.

The end result is this graph:

Full function graph

You can view the full size graph here.

This graph is useful, but it's a bit noisy.  Our next step is to clean up the graph.  We do this in several ways.  The first is to remove any useless blocks.  It's very common to find a branch that leads directly to a jump.  This creates a useless block.  So you can go through the graph, looking for any blocks that do this, and remove them.  Replace any edges pointing to that node to the target node of the removed block.

Another common thing, at least with this CPU architecture, is there are branches that lead to a basic block that does nothing but change between 8 bit and 16 bit mode, and then jump to another block.  Since we don't really care about this too much (the disassembler cared more), we can treat these as empty blocks and remove them as well.

Finally, you'll find nodes that do nothing but clean up the stack and then RET.  Instead of jumping to these blocks, we should go through and replace them with unique RET blocks.  That way you don't have all of these exit points all routed to couple of blocks, looking like part of the structure.

After you make these cleanups, you'll have a graph that looks like this:

Cleaned up graph

See the full size graph here.

This is much cleaner and easier to follow.

Analyze the structure of the routine.

There are patterns in this graph that correspond to programming structures that you are familiar with.

For example, this pattern is an IF statement.

IF statement

At the end of the block at $3e11, there is some comparison done.  The bpl tells us that we skipped a block if the result of some comparison was positive.

This can be structured as follows:

// at the end of the $3e11 block
if (result < 0) {
  // do $3e24 block
}
// do $3e27 block

The IF/ELSE statement is also easy to spot:

IF/ELSE statement

The beq tells us that if some result is zero, then we do the $40db block, otherwise we do the $40a9 block.

This can be structured as follows:

// at the end of the $40a5 block
if (result == 0) {
  // do $40db block
} else {
  // do $40a9 block
}
// do $40e7 block

Finally, loops (for loops, while loops, do/while loops) look like this:

WHILE loop

This is a case where a block points back at a previous block.  That's how you know it's a loop.  This particular one looks like a WHILE loop because the comparison happens in $3ec7 (i.e. first).  The bcs tells us there was most likely a comparison between two variables.

The structure then would be:

// $3ec7 block
while (something < somethingelse) {
  // 3ed3 block
}
// 3eda block

Using these simple patterns, it becomes rather easy to see the structure of the routine.

Convert disassembly into pseudocode

Now we begin the process of converting the disassembly into pseudocode.  This is a step-by-step process, and we use the basic block graph to help us organize the large structures.

For example, when you get to a basic block that has multiple other blocks from below pointing back up to it, you know it's the top of a loop.  You should open up a new block and mark it.  As you go along, you'll discover what type of loop it is and you can go back and clarify.

When you get to an IF/ELSE statement, you can scan through the tree and see where it will converge (of if it will converge).

 You may end up with criss-crossed blocks, which cannot be represented cleanly without GOTOs.  This is especially true of older programs that were likely written in assembly in the first place.  I would recommend using GOTOs in your pseudocode, and only after you grasp what is happening, refactor it into a structured routine.. duplicating code if necessary.

As you practice, you'll get better at spotting patterns in the structure.  Without much thought at all, I can see that the block at $3d67 is probably the same as the block at $4013.  They're likely both the bottom of the same FOR loop, and they're likely just duplicated because assembly programmers would do that.  At the very least, block $3d67 is a "continue" statement if block $4013 is indeed the bottom of a FOR loop.

The way I convert disassembly into pseudocode, is at the top of the file I keep a list of the globals.

They start out looking something like:

uint8_t d_4356;  // 4356

Then as I figure out what d_4356 is, based on usage, I'll go rename it:

uint8_t numInst;  // 4356

Whenever I come across a new memory address, I'll search for it, if it exists, I use its name, if it doesn't, I add it to the list.

For the opcodes themselves, I tend to build them out piece by piece.

Let's look at the beginning of the assembly.

It starts with a spinlock on the soundCtl.  I'll look up what the high-bit is and note it in a comment.

while (soundCtl & 0x80) {}  // wait for DOC to finish

Then it takes the result of soundCtl and ANDs it with $9f and stores it back into soundCtl.  Again, I'll look up what those bits do and comment it.

soundCtl &= 0x9f;  // DOC mode, no autoinc

and so on.  I'll have temporary variables for the accumulator and x and y indices, which will eventually get replaced with more complicated expressions to make them easier to follow.

And that's it.  The final pseudocode (basically C) for the sound interrupt routine is here.

Found Data

I'm always interested in found data. Little notes buried in executables and other strange places. These are usually intended to be seen only by those curious enough to fire up a hex editor, or do a little reverse engineering.

Here's an example. On the 68k Macintosh, executables usually only have a resource fork. All the code is stored in CODE blocks in the resource fork. So I was curious when I found that the 68k mac version of Shadowgate had a data fork. The data fork contained the following message:

Welcome to TMON!
TMON was written in the summer of 1984 by Waldemar Horwat when he was still 15 years old. Initially TMON didn't have the heap and file windows; these were added later. TMON was very valuable in debugging itself. The biggest problem in writing TMON was making sure that it will not affect the Macintosh system in undesirable ways. Although some side effects couldn't be avoided, most have been eliminated. How are you able to read this message, anyway? Do you have a disk sector reader?

It's interesting to note that Waldemar Horwat did some programming on Shadowgate. So my guess is that this is evidence that he used his TMON debugger on Shadowgate. Later revisions of Shadowgate have had this data fork removed. I also found it in Uninvited, which is another ICOM game. No sign of it in Deja Vu 1 or 2, but I haven't been able to find anything but the 1992 reissues of those games.