MKLOADOB (the Echidna Data Linker)

• Why, What, Where
• Introduction and example
• Running the linker
• Loading your data
• Download
• Data Linker input file format
• Numeric Formats
• Command line arguments
• Macro Language
• Tips and Suggestions
• Chunkifying your data

Back in the early 90s as soon as CD based game systems came out it became clear that one of the big problems with CD based games was they took forever to load!  Those problems were mostly solved by several companies back in the early 90s but it seems like almost no one noticed because we still get crap like Crash Bandicoot: Wrath of Cortex with atrocious load times.  Pick a level, wait 90 seconds, take a few steps, die, wait 90 seconds for the hub level to load so you can immediately jump back into the level and have to wait another 90 seconds!!

How do you get around these problems?  The biggest step is realizing that A CONSOLE IS NOT A PC!!!!  Burn that into your brain!!!

It's not uncommon for PC games to just put each texture, each model, each sound in a separate file.  When you install the game all of them get copied to your hard drive and when you start the game they load them up, one at a time.  The only thing that makes this possibly acceptable on a PC is you are loading them off the hard drive or a 40x CD/DVD drive with disk caching built into the OS.  Good consoles don't have an OS and to keep costs down they don't have 40x CD/DVD drives.

The other excuse is nobody knows what kind of PC the game will run on.  Will it be a 512meg Pentium 4 with 128Meg of Video RAM or a 300mhz Celeron and a 4Meg RIVA 128 card?  In that case sometimes there might be different versions of each model, texture, sound etc.  Consoles don't have this problem.  There is only one type.  If you are making a PS2 game you know exactly what hardware the user will have.

Basically here is what you need to do to get your load times to be as fast as possible.

• Load all your data from ONE FILE!!!

There are two steps to this.  One, for a single stage/level, attempt to load all the data for that stage from one file directly into memory.  No loading one model from one file and a different model from a different file.  Even if that means putting some of the same models, textures or sounds on the DVD more than once, do it!  You've got a friggin DVD worth of space.  Use it!

Note! I do not mean a WAD files, PAK files or CAB file likes are used in many PC games.  Although those are better than separate files they will not speed up your load times much at all because you are still treating them as separate files.

The second step is putting all the files in your game (the one file for each stage) all together into one BIG file that contains all the data for your entire game.  This is not a hard thing to do and it will remove even more overhead for your game.

• Load your data in chucks no smaller than 1 DVD hardware sector.  In other words, if on your platform a DVD hardware sector holds 2048 bytes of data then ALWAYS LOAD A MULTIPLE OF 2048 bytes.  Never load less even if you have to pad the file.

The reason is on some systems data can be DMAed directly into memory but this is only true if you are DMAing a whole sector.  Anything less than a sector and it first has to be read into some buffer in the OS and then copied to your memory.  That also means you cannot read a few bytes from the file and then start reading multiples of sector size chucks of data.  You have to start right from the beginning going at full speed.

• Finally, load your data in as close to an image of memory as possible.  You should NOT have to parse your data while your are loading it or after.  With very few exceptions you should NOT have to copy things around.  I've seen many schemes that make some file format where there are "chunks".  A chunk is usually some kind of ID followed by the length of the chunk after which follows the next chunk.  That is NOT a good format for a game.  That's a great format for a tool or an application but not for a game because parsing takes time, code and memory.  More time, more code and more memory than not parsing.  In a game, anything which takes more time or memory or code is BAD.  Don't do it!

It's this last step that I'm here to help you with.  In the early 1990s my friends and I wrote a tool to deal with this.  Since about 1997 we have made it freely available but without docs it's been unlikely that anybody has used it let alone even found it, until now!

The Echidna Data Linker

It's what we call a Data Linker because it takes a bunch of data an links it together.  It's called MKLOADOB.  Lame name I know but hey, it's old, starting back from the days of DOS.  If you are curious, MKLOADOB stands for MaKe LOAD OBject.

It takes a bunch of spec files of the form below and generates a hierarchical binary file with pointers.

Example:

Here's a short example.  Let's say you want to have level structure that is an array of instances where an instance is a model pointer, a position and a y rotation.  Here's the C/C++ structure for what I'm talking about

// level.h
//
struct Instance
{
    float   transx;
    float   transy;
    float   transz;
    float   rotationy;
    Model*  pModel;
};

struct Level
{
    int       numInstances;
    Instance* pInstances;
};

Now lets make a small level with a ground model, a house model and 2 trees of the same model using the data linker

// linker file
//
[start]
long=4  ; number of models
pntr=modeltable

[modeltable]
float=0.0 0.0 0.0   ; translation for ground
float=0.0           ; rotation for ground
file=ground.3d      ; model file for ground

float=5.0 0.0 3.0   ; translation for house
float=45.0          ; rotation for house
file=house.3d       ; model file for house

float=-4.0 0.0 -2.0 ; translation for tree1
float=30.0          ; rotation for tree1
file=tree.3d        ; model file for tree

float=-2.0 0.0 -4.0 ; translation for tree2
float=225.0     ; rotation for tree2
file=tree.3d        ; model file for tree

You pass this file to the data linker and you'll get a binary file that you can load directly into memory and with only a few lines of code all your pointers will already be pointing at your data.

Above notice the third line that says "pntr=".  This line generates a pointer to a section that matches the name after the '='.  You can have as many pointers as you need/want.  They can be nested to any level and they can be circular.  Also, notice that the file tree.3d is referenced twice.  In this case the file tree.3d would be stored only once inside the binary file that the data linker creates but there would be two pointers pointing to that data.

For a real game, most of the time we would not write data linker files by hand.  We would make our tools generate data linker files and then let the data linker pull it all together.  There's no need to hand load and hand parse stuff which is another huge advantage.  Most games that use individual files or chunky formats end up reading a few bytes at a time and *parsing* the data, reading the size of this or that, allocating bits of memory at time etc..  That's a lot of work.  Many loaders are hundreds of lines long.  Using the a data linker removes all that code.  Less code = faster development, faster loading, more memory, less bugs.

Running the Data Linker

A typical command line might look like this

mkloadob mylevel.lbi -duperr -sectorsize 2048 -chunksize $2800000
         -nopad -nosort -fixupmode 2 -padsize 4 linkerfile.dlk

Those options say:

Loading Your Data

In the case of a one chunk file, loading your data is pretty straight forward.  Here's some sample code:

#include "link.h"

struct Level* pLevel;  // the level structure from above

pLevel = LINK_QuickLoadBlockFile ("mylevel.lbi");

As you can tell that was extremely difficult! :-p  Your level is now loaded and all your pointers are correct.

The example loading and pointer fixup files are in the same folder as mkloadob in the CVS repository.  See Quickload.cpp, Quickload.h, Link.cpp and Link.h

Downloading

The Echidna Data Linker is one of the tools in the Echidna Libraries which can be accessed through github.com here.

Data Linker File Format

The format of the data linker files is as follows

Preprocessor commands:

Commands:

IMPORTANT!!!

data fields are not automatically aligned. In other words

[mysection]
byte=1
long=2

Will result in a long starting at a 1 byte offset from the start of mysection.  The reason is this allows you to use the data linker to make unaligned data. If you want aligned data you need to use the align= option as in

[mysection]
byte=1
align=4
long=2

string=ABC

string="ABC"

Numeric Format

You can specify integer based numbers as follows

1234	= decimal 1234
$1234	= hexadecimal 0x1234
0x1234	= hexadecimal 0x1234
1234h	= hexadecimal 0x1234
!12.34	= fixed point 16.16 fraction

Command Line Arguments

Usage: MKLOADOB OUTFILE SPECFILES [switches...]

(*) Never relevant is an over statement.  Of course if you have an include in the middle of a section then it does matter but there is no reason to do that.  Use the insert= statement instead.

Macro Language

There is a small macro language built in.  It works on a line by line basis.  In other words, macros can NOT span more than one line.  Variables and macros are referenced with %.  Example

#define file myfile
#define extension .bin
load=%file%%extension%

would be the same as

load=myfile.bin

Note: The format is %blah%.  Notice the ending %.  This is so you can put two variables directly next to each other like in the example above.  It is optional only when the next thing following is not a macro/variable.  This has the following consequence.  If you follow a macro with a variable or another macro be sure to remember the trailing %.  For example

%fadd(2,3)%fadd(4,5)

That is most likely a bug.  It reads as %fadd(2,3)% followed by fadd(4,5).  The second fadd is not preceded by a % and is therefore not a macro call.  The correct way is

%fadd(2,3)%%fadd(4,5)

Macro commands

Tips / Suggestions

• Given the above example I generally put a version number inside the top structure of the file

// level.h
struct Level
{
    int       versionNumber;
    int       numInstances;
    Instance* pInstances;
};

// linker file
[start]
long=1  ; version number
long=4  ; number of models
pntr=modeltable

This way, anytime I change the format of the data I change the version number.  The loader in the game can check the version number and print an error message.  That way I won't spend hours debugging something just because I'm using old data with a new version of the code or visa versa.

• Since the #define format is the same a C/C++ you can use the same header file for both the data linker and your code.  For example

// objectdefs.h
//
#define OBJECTID_PLAYER 1
#define OBJECTID_ZOMBIE 2
#define OBJECTID_CHEST  3

// linker file
//
[object_instance_array]
long=%OBJECTID_PLAYER% ; object type
pntr=instance_data_player
long=%OBJECTID_ZOMBIE%
pntr=instance_data_zombie_1
long=%OBJECTID_ZOMBIE%
pntr=instance_data_zombie_2
long=%OBJECTID_ZOMBIE%
pntr=instance_data_zombie_3
long=%OBJECTID_CHEST%
pntr=instance_data_chest_1
long=%OBJECTID_CHEST%
pntr=instance_data_chest_2

• You can use the nullok=true options to make it possible to optionally connect data to some structure before you know if it will exist or not.  For example, assume you have a program the generates a 3D joint hierarchy from a Maya or 3DSMax file.

[chest_bone]
float=0.1 2.3 4.5 ; translation
long=2    ; num children
pntr=chest_children;
pntr=chest_attachments,nullok=true

[chest_children]
pntr=left_forearm_bone
pntr=right_forearm_bone

[left_forearm_bone]
float=0.1 2.3 4.5 ; translation
long=0    ; num children
long=0    ; (null), no children
pntr=left_forearm_attachments,nullok=true

[right_forearm_bone]
float=0.1 2.3 4.5 ; translation
long=2    ; num children
long=0    ; (null), no children
pntr=right_forearm_attachments,nullok=true

That program does not need to be aware of IF you are going to later attach something to the joints.  Each joint has an *optional* pointer.  If you happen to supply it in another file for example it will get connected, otherwise you'll get null.

• Use the macro language with #if / #elif. For example:

#if %fexists(myfolder/myfile.dlk)
  #include "myfolder/myfile.dlk"
#endif

#if %fnot(%fstricmp(%username,"gregg"))
  ...
#endif

Chunkifying Your Data

MKLOADOB can separate data into chucks of a specified size. If you don't need chucks specify a really large size and you'll get just one chunk! Note: no piece of data or any sections can be larger than a single chunk.

What's the point to chunks?

• You want to spool music from the CD and STILL be able to load in real time. Load one chuck at a time (giving the machine time to grab more music between chucks
   
• You want to be able to LOAD and later FREE multiple levels in the same memory space without having to worry about garbage collection and fragmentation. You do this by storing the level in chunks using this program.

At runtime you allocation say 200 chunks of memory. You can then load each chunk from one of these files into any of those 200 chunks in any order since all pointers are chuck relative.

The first chunk of the file contains a pointer field for each chunk that ends in NULL. So if there are 4 chunks the start of the very first chunk would be

$FFFFFFFF ; space for pointer for chunk 0
$FFFFFFFF ; space for pointer for chunk 1
$FFFFFFFF ; space for pointer for chunk 2
$FFFFFFFF ; space for pointer for chunk 3
$00000000 ; end marker
$???????? ; pointer to start of data

As you load each chunk you can record it's address in memory in that table.

When you are finish you can go and fix up all the pointers in your data something like this

long* chunktable; ; address of first chunk
long relpntr;     ; a pointer you've gotten out of the data
void* pntr;       ; actuall address in memory

pntr = chunktable[relpntr & (LOAD_CHUNK_MASK >> LOAD_CHUNK_SHIFT)]
            + (relpntr & LOAD_CHUCK_OFFSET_MASK)

It is assumed that no pointer may be at an ODD address therefore all pointers in the file have their low bit set (0x00000001). This is so as you fix up the pointers you know if the pointer has already been fixed up. This is important because if you are fixing up the pointers by walking the data yourself.

So for example if you have this

[start]
pntr=section1
pntr=section1

[section1]
file=myfile.bin

As you walk your data you will encounter 2 pointers to section1. When you find the first one you would go fix up section1. When you find the second one you would go to fix up section1 again and if you didn't know the pointers were already fixed up you'd fix them again and mess them up.

Optionally you can write out a fixup table. This is a list of relative pointers to ALL other pointers in the file followed by a null.  The issue here is currently all fixup pointers must all fit in the first chunk.  If you are not using chunks this is not an issue.  If you are and you run out of room then it would be relatively easy to come up with a format that allowed the fixup table to span chunks.  Last time we used chunks we were not using a fixup table.

When using the multiple chunk method each chunk is padded to be one full chunk long. If you are only using one chunk you probably want to use -NOPAD option to not pad since you will specify an arbitrarily large chunk.

BUT, at the same time you probably want your in game loader to be as simple as possible like for example never having to load less than a full sector of data from the CD/DVD. In that case use the -SECTORSIZE option to specify the size of a sector on the CD/DVD. This is pretty much only useful if you are using ONE chunk.

Why is that important? Because many DVD/CD libraries will read directly to user memory if they can read an entire sector but if they have to read less than an entire sector they must first load it to their own buffer then copy the part you wanted to user memory. That's clearly slower than directly reading it.

Loading a multi-chunk file would look something like this:

• Get length of entire file and divide by the chunk size to get the number of chunks
• for each chunk
  • Load a chunk
  • record the address of the loaded chunk in the corresponding long word in the first chunk.
• end for

now all the blocks are loaded and you know where the data offset starts, the first pointer after the chunk table so:

• for each non-zero data offset
  • look up the correct block address
  • add the block offset
  • or in the data offset
• endfor