MKLOADOB (the Echidna Data Linker)


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.

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.

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.

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:

mylevel.lbi the name of the file we are going to create
-duperr if two sections have the same name print an error
-sectorsize 2048 one sector of the disk is 2048 bytes so our filesize will be padded to a multiple of 2048 bytes
-chunksize $2800000 chunks are probably not something you will use.  In this case we just want one big chunk so we set the chunksize to some giant size
-nopad normally all chucks would get filled out to be chunksize big but in this case we don't want that since there is only one chunk.
-nosort don't sort any binary included files.  Normally they get sorted so that they can be squeezed into the various chunks but since we are only going to have one chunk there is no point.
-fixupmode 2 put the pointer fixup table at the end of the file.  Because it's at the end, once the pointers have been fixed up you can free that part of memory if you want to
-padsize 4 is the alignment for sections.  All sections and files will start at a 4 byte boundary by default

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:

#include "filename" includes another linker file
#define var value defines a var that can be referenced as %var%
#if value 0 = ignore lines until #elif, #else, or #endif
#elif value 0 = ignore lines until #elif, #else, or #endif
#else ignore lines if a previous #if, #elif area was not ignored
#endif marks the end of the current #if group
#error msg generates an error

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
[secname] start a section

You can set the alignment for a section as follows

[mysection,align=16]

Mysection will start at a 16 byte boundary

NOTE: the alignment is relative to the address of the particular block this section ends up being placed in. The alignment of block is up to the loader in the program you are using this data.

file= pointer to a file : quotes are optional

You can also optionally specify an alignment for the file like this

file=myfile.bin,align=16

alignment is relative to the address of the particular block this files ends up being placed in. The alignment of block is up to the loader in the program you are using this data.

You can also optionally allow a file to not exist like this

file=myfile.bin,nullok=true

In this case if the file does not exist a NULL pointer will be inserted.  Normally the linker would print an error.

To understand the file= command, the long hand way of writing this would be as follows

...
pntr=myfile.bin.section
...

[myfile.bin.section]
binc=myfile.bin
data= pointer to a file (same as file=) : quotes are optional
load= pointer to a file loaded at runtime : quotes are optional

note: this will actually start as a pointer to a filename with with the POSITIONFLAG_ISFILE set to tell your loader that you need to load the file

since mkloadob excepts variables both as environment vars and as #define var value, the expected usage of load= is as follows

#define objectload=load
;#define objectload=file
#define weaponsload=load
;#define weaponsload=file

%objectload%="myobject1.ob"
%objectload%="myobject2.ob"
%weaponload%="myweapon1.foo"
%weaponload%="myweapon2.foo"

this way you can comment turn on/off individual files or file types throughout.

pntr= pointer to another section

You can also optionally allow the section to not exist like this

pntr=mysection,nullok=true

In this case if the section does not exist a NULL pointer will be inserted.  Normally the linker would print an error.

level= pointer to another section (same as pntr=)
long= longs (4 bytes each)
int32= longs (4 bytes each)
uint32= longs (4 bytes each)
word= words (2 bytes each)
short= words (2 bytes each)
int16= words (2 bytes each)
uint16= words (2 bytes each)
byte= bytes (1 byte each)
char= bytes (1 byte each)
int8= bytes (1 byte each)
uint8= bytes (1 byte each)
float= floats (4 bytes each)
string= string, note: NO NULL IS INSERTED!!!
string=ABC
inserts ABC
string="ABC"
inserts "ABC" (including the quotes!!!)
binc= binary file to include here, quotes are optional
align= boundary to align to (no arg or 0 = default)

NOTE: THIS ALIGNS BASED ON THE START OF THE SECTION,  NOT MEMORY.

In other words, if you have section like this

[mysection]
byte=1
align=4
long=$12345678

You will get 3 bytes of padding after the first byte BUT the section will be placed based on the -PADSIZE option. If -PADSIZE is set to a non multiple of 4 in the example above it's possible the section will not start at a 4 byte boundary and therefore neither will the long

pad= pad with N bytes
pad=24

insert 24 bytes (value 0)

path= set the path for loading binary files. Files encountered after this line will be loaded from here

 NOTE: Files are parsed from the TOP section to each connecting section  so for example

[start]
pntr=section1
file=file3.bin ; load dir\subdir\file2.bin

[section1]
path=dir\subdir
file=file1.bin ; loads dir\subdir\file1.bin

Also note that by default, files are loaded relative to the file they are referenced from first.  In other words if a file= statement is found in c:\mydir\myfile.dlink the file will be looked for in c:\mydir

insert= inserts another section here.  Not a pointer, the actual section so for example this:
[start]
byte=1 2 3
insert=othersection
byte=7 8 9

[othersection]
byte=4
byte=5 6

is the same as this

[start]
byte=1 2 3
byte=4
byte=5 6
byte=7 8 9

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...]

OUTFILE Output filename
SPECFILES Linker files.  Note it says FILES.  As in PLURAL.  You can use include statements and/or you can specify as many files as you need right here.  Files are parsed from the [start] section so the order sections appear in the files and the order they are included is not relevant (*)
-VERBOSE Verbose (print too much info)
-NOOUTPUT Don't write output file
-DUPERR To sections with the same name cause an error (default, ignore duplicates)
-NOPACK Don't Pack.  Don't check the contents of each binary file to see if it match another binary file
-BIGENDIAN Big Endian, default is little endian.
-PADSIZE <bytes> Padsize Size (Def. 4). This is the default alignment for the start of sections
-CHUNKSIZE <bytes> Chunk Size (Def. 2048).  This is the size of one chuck.  See Chunkifying your data.  Most likely you'll want to set this to something like $7F000000
-SECTORSIZE <bytes> Hardware Sector Size (Def. 1).  If you set this to any size larger then 1 your file will be padded to be a multiple of this number.
-FIXUPMODE <mode> Fixup mode.  This specifies the the method used to save the optional pointer fixup table

0 = none (def)
1 = at beginning of the file
2 = at end (this is probably the most common setting)

-NOPAD Don't pad end of file to Chunk size.  You will probably want to set this option, otherwise if you set the chunksize above to some very large size you'll get a gigantic file
-TOP <top> Top Section (Def. 'START').  By default the linker will look for a section called [start] for where it should start parsing.  You can change that with this option
-WRITEPRE <prefile> Write Preload file
-WRITEKEY<prekey> Write Preload key file
-NOSORT Do NOT sort binary files.  The point of this is supposed to be that if not sorted, "file=" files will generally get loaded in memory consecutively as they are found in the linker file. Of course they will be no where near the non-file data
-READPRE <prefile> Read preload file
-INCLUDE <incpath> Add an include pat

(*) 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

%fnop (...)anything inside the parentheses is ignored.  Kind of a way to comment something out.
%fset (var,value)set the variable called var to value
%fadd (value1,value2,...)add value1 to value2 (then add value3, ... etc)
%fsubtract,%fsub (value1,value2,...)sub value2 from value1 (then subtract value3, ...etc)
%fdivide,%fdiv (value1,value2,...)divide value1 by value2 (then divide by value3, ...etc)
%fmultiply,%fmul,%fmult (value1,value2,...)multiply value1 by value2 (then multiply by value3, ..etc)
%fmodulo,%fmod (value1,value2,...)return the remainder when dividing value1 by value2
%fconcatenate,%fconcate,%fcat (str1, str2, ...)concatenate str2 on the end of str1 (then str3 on the end of that etc)
%fsubstr (str,index[,len])return the substring of str.  If just index is specified then you get the substring from index to the end of the string.  If len is specified then you get len characters after index
%fleft(str,count)return the left count characters of str
%fright(str,count)return the right count characters of str
%fstrlen (str1,...)return the length the str1 (plus str2, etc...)
%fif (value,truecase[,falsecase])if value is true return truecase, else, if there is a falsecase return it
%fequal,%feq (value1,value2)return 1 if value1 is equal to value2 (integer compare)
%fgreaterthan,%fgt (value,value)return 1 if value1 is greater than to value2 (integer compare)
%fgreaterthanequal,%fge (value,value)return 1 if value1 is greater than or equal to value2 (integer compare)
%flessthan,%flt (value,value)return 1 if value1 is less than to value2 (integer compare)
%flessthanequal,%fle (value,value)return 1 if value1 is less than or equal to value2 (integer compare)
%fnotequal,%fne, (value,value)return 1 if value1 is not equal to value2 (integer compare)
%for (value,value,...)return 1 if value1 is OR value2 is not zero (or value3,... etc) (integer compare)
%fand (value,value,...)return 1 if value1 is AND value2 is not zero (and value3,... etc) (integer compare)
%fnot(value)return 1 if value is zero, else return 0
%frand(range) ... (min,max)return a random number.  If one argument is specified the returned value will be from 0 to 1 - that number.  If two numbers are specified the number returned will be from min to max-1
%fstrcmp(str1,str2)compare str1 to str2.  Return -1 if str1 is asciibetically lower than str2, 0 if they are equal, 1 if str1 is asciibetically higher than str2
%fstricmp(value,value)compare str1 to str2 case insensitive (using stricmp).  Return -1 if str1 is asciibetically lower than str2, 0 if they are equal, 1 if str1 is asciibetically higher than str2
%fascii(str)return the ascii value of the first character of str
%fquote(str)quote something, don't interpret it
%fsearch(string1,string2)find string2 in string1, if found return the index to the first character found or -1 if not found
%fint(value)convert an float to an int.  27.9 becomes 27
%fexists(filename) returns 1 if the file exists, 0 if it does not
%ffilelength(filename) returns the length of a file in bytes
%fformat(string,arg)format arg using string like printf from C/C++

fformat only does one value at a time. The first argument is the formatting specification. The second is the value to format. A formatting specification starts with % although it will get addedt of you forget. It ends with one of the these letters

Character Type Output format
c integer specifies a single-byte character
C integer specifies a single-byte character.
d integer Signed decimal integer.
i integer Signed decimal integer.
o integer Unsigned octal integer.
u integer Unsigned decimal integer.
x integer Unsigned hexadecimal integer, using "abcdef."
X integer Unsigned hexadecimal integer, using "ABCDEF."
e float Signed value having the form [ E]d.dddd e [sign]ddd where d is a single decimal digit, dddd is one or more decimal digits, ddd is exactly three decimal digits, and sign is + or E
E float Identical to the e format except that E rather than e introduces the exponent.
f float Signed value having the form [ E]dddd.dddd, where dddd is one or more decimal digits. The number of digits before the decimal point depends on the magnitude of the number, and the number of digits after the decimal point depends on the requested precision.
g float Signed value printed in f or e format, whichever is more compact for the given value and precision. The e format is used only when the exponent of the value is less than E or greater than or equal to the precision argument. Trailing zeros are truncated, and the decimal point appears only if one or more digits follow it.
G float Identical to the g format, except that E, rather than e, introduces the exponent (where appropriate).
s String specifies a string; Characters are printed up to the first null character or until the precision value is reached.

 

If you know C or C++ it is just using printf.  If not you can read about how the formatting works here

example:

    fformat(%1.1f,27.4699)

the %1.1f above says; Print at least 1 character and print one and only one after the decimal so in the example above you'd get "27.5".

%5.3 would print at least five characters with 3 after the decimal point so "2.54" would become "2.540".

%09.4f would make it "0002.5400".

%9.4f would make it "     2.5400"

Note the the last example of "    2.5400" would not work in HTML because HTML usually converts a bunch of spaces to one space.  Only inside a <pre> </pre> section are spaces not ignored. (pre = preformatted).  If you need things to be right aligned use HTML's align property instead of spaces.

Tips / Suggestions

// 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.

// 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
[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.

#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?

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:

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