“One person's data is another person's noise.”

I know it's been forever since I've done a post and I'm really sorry. I got caught up in the sound issues and panorama issues. I'm going to talk about sound in this post and then make another post about panoramas. So here we go!

“One person's data is another person's noise.”  ― K.C. Cole

This quote pretty much sums up my experiences with the sound decoding. I was somewhat lucky in that Marisa Chan's source code had an implementation of sound decoding that I could model off of, but at the same time, the whole function was quite cryptic. This is mostly due to the variable "naming". And I say "naming" in the loosest sense of the word, because most were single letters:

void adpcm8_decode(void *in, void *out, int8_t stereo, int32_t n)
{
    uint8_t *m1;
    uint16_t *m2;
    m1 = (uint8_t *)in;
    m2 = (uint16_t *)out;
    uint32_t a, x, j = 0;
    int32_t b, i, t[4] = {0, 0, 0, 0};

    while (n)
    {
        a = *m1;
        i = t[j+2];
        x = t2[i];
        b = 0;

        if(a & 0x40)
            b += x;
        if(a & 0x20)
            b += x >> 1;
        if(a & 0x10)
            b += x >> 2;
        if(a & 8)
            b += x >> 3;
        if(a & 4)
            b += x >> 4;
        if(a & 2)
            b += x >> 5;
        if(a & 1)
            b += x >> 6;

        if(a & 0x80)
            b = -b;

        b += t[j];

        if(b > 32767)
            b = 32767;
        else if(b < -32768)
            b = -32768;

        i += t1[(a >> 4) & 7];

        if(i < 0)
            i = 0;
        else if(i > 88)
            i = 88;

        t[j] = b;
        t[j+2] = i;
        j = (j + 1) & stereo;
        *m2 = b;

        m1++;
        m2++;
        n--;
    }
}

No offense intended towards Marisa Chan, but that makes my eyes hurt. It made understanding the algorithm that much harder. But after talking to a couple people at ScummVM and Wikipedia-ing general sound decoding, I figured out the sound is encoded using a modified Microsoft Adaptive PCM. I'll go ahead and post my implementation and then describe the process:

const int16 RawZorkStream::_stepAdjustmentTable[8] = {-1, -1, -1, 1, 4, 7, 10, 12};

const int32 RawZorkStream::_amplitudeLookupTable[89] = {0x0007, 0x0008, 0x0009, 0x000A, 0x000B, 0x000C, 0x000D, 0x000E,
                                                        0x0010, 0x0011, 0x0013, 0x0015, 0x0017, 0x0019, 0x001C, 0x001F,
                                                        0x0022, 0x0025, 0x0029, 0x002D, 0x0032, 0x0037, 0x003C, 0x0042,
                                                        0x0049, 0x0050, 0x0058, 0x0061, 0x006B, 0x0076, 0x0082, 0x008F,
                                                        0x009D, 0x00AD, 0x00BE, 0x00D1, 0x00E6, 0x00FD, 0x0117, 0x0133, 
                                                        0x0151, 0x0173, 0x0198, 0x01C1, 0x01EE, 0x0220, 0x0256, 0x0292,
                                                        0x02D4, 0x031C, 0x036C, 0x03C3, 0x0424, 0x048E, 0x0502, 0x0583, 
                                                        0x0610, 0x06AB, 0x0756, 0x0812, 0x08E0, 0x09C3, 0x0ABD, 0x0BD0,
                                                        0x0CFF, 0x0E4C, 0x0FBA, 0x114C, 0x1307, 0x14EE, 0x1706, 0x1954, 
                                                        0x1BDC, 0x1EA5, 0x21B6, 0x2515, 0x28CA, 0x2CDF, 0x315B, 0x364B,
                                                        0x3BB9, 0x41B2, 0x4844, 0x4F7E, 0x5771, 0x602F, 0x69CE, 0x7462, 0x7FFF};

int RawZorkStream::readBuffer(int16 *buffer, const int numSamples) {
    uint32 bytesRead = 0;

    // 0: Left, 1: Right
    byte channel = 0;

    while (bytesRead < numSamples) {
        byte encodedSample = _stream->readByte();
        if (_stream->eos()) {
            _endOfData = true;
            return bytesRead;
        }
        bytesRead++;

        int16 index = _lastSample[channel].index;
        uint32 lookUpSample = _amplitudeLookupTable[index];

        int32 sample = 0;

        if (encodedSample & 0x40)
            sample += lookUpSample;
        if (encodedSample & 0x20)
            sample += lookUpSample >> 1;
        if (encodedSample & 0x10)
            sample += lookUpSample >> 2;
        if (encodedSample & 8)
            sample += lookUpSample >> 3;
        if (encodedSample & 4)
            sample += lookUpSample >> 4;
        if (encodedSample & 2)
            sample += lookUpSample >> 5;
        if (encodedSample & 1)
            sample += lookUpSample >> 6;
        if (encodedSample & 0x80)
            sample = -sample;

        sample += _lastSample[channel].sample;
        sample = CLIP(sample, -32768, 32767);

        buffer[bytesRead - 1] = (int16)sample;

        index += _stepAdjustmentTable[(encodedSample >> 4) & 7];
        index = CLIP<int16>(index, 0, 88);

        _lastSample[channel].sample = sample;
        _lastSample[channel].index = index;

        // Increment and wrap the channel
        channel = (channel + 1) & _stereo;
    }

    return bytesRead;
}

Each sample is encoded into 8 bits. The actual sound sample is read from the bits using a lookup table and an index from the previous 'frame'. This is then added to the sample from last 'frame'. Finally, the 4 high bits are used to set the index for the next 'frame'.

The biggest problem I ran into for sound was actually a typo on my part. The template argument for CLIP was accidentally set to a uint16 instead of a int16. This caused distortions at the extremely high and low ranges of the sound. But, this usually only occurred at the beginning and end of a sound clip. I spent days trying to figure out if I had set the initial lastSample correctly, or other random ideas. After pounding my head into the desk for 3 days, the glorious wjp came along and found my typo. After which, the sound worked perfectly. Shout out to wjp!!!!!!!!!

There is one other bug with sound and that's in videos. The sound has a slight 'ticking'. However, clone2727 identified it potentially as a problem with the AVI decoder. In the current state, the AVI decoder puts each sound 'chunk' into its own AudioStream, and then puts all the streams into a queue to be played. We're thinking the lastSample needs to persist from chunk to chunk. However, solving this problem would take either a gross hack, or a redesign of the AVI decoder. clone2727 has taken on the task, so I'm going to leave it to him and get back to the video audio later in the project.

Well, that's it for this post. Sound was pretty straightforward. I was only bogged down due to some really bad typos on my part. As always, feel free to comment or ask questions.

-RichieSams

The Engine Skeleton Gains Some Tendons - Part 2

Part 2!! As a recap from last post, I started out last week by implementing image handling, video handling, and a text debug console.

I started with the console as it allows me to to map typed commands to functions. (IE. 'loadimage zassets/castle/cae4d311.tga' calls loadImageToScreen() on that file) This is extremely useful in that I can load an image multiple times or I can load different images all without having to re-run the engine or recompile.

Creating the text console was actually extremely easy because it was already written. I just to inherit from the base class:

class Console : public GUI::Debugger {
public:
    Console(ZEngine *engine);
    virtual ~Console() {}

private:
    ZEngine *_engine;

    bool cmdLoadImage(int argc, const char **argv);
    bool cmdLoadVideo(int argc, const char **argv);
    bool cmdLoadSound(int argc, const char **argv);
};

In the constructor, I just registered the various commands:

Console::Console(ZEngine *engine) : GUI::Debugger(), _engine(engine) {
    DCmd_Register("loadimage", WRAP_METHOD(Console, cmdLoadImage));
    DCmd_Register("loadvideo", WRAP_METHOD(Console, cmdLoadVideo));
    DCmd_Register("loadsound", WRAP_METHOD(Console, cmdLoadSound));
}

And then, in ZEngine::initialize() I created an instance of my custom class:

void ZEngine::initialize() {
        .
        .
        .

    _console = new Console(this);
}

And lastly, I registered a key press combination to bring up the debug console

void ZEngine::processEvents() {
    while (_eventMan->pollEvent(_event)) {
        switch (_event.type) {
        case Common::EVENT_KEYDOWN:
            switch (_event.kbd.keycode) {
            case Common::KEYCODE_d:
                if (_event.kbd.hasFlags(Common::KBD_CTRL)) {
                    // Start the debugger
                    _console->attach();
                    _console->onFrame();
                }
                break;
            }
            break;
        }
    }
}

With that done, I can press ctrl+d, and this is what pops up:

Awesome! With that done, I could move on to images. All the images in ZNem and ZGI are .tga files, but don't be fooled; the vast majority of them aren't actually TGA. They're actually TGZ, a custom image format. The format itself isn't too difficult, and I give all the credit to Mr. Mouse on Xentax.

Byte[4] "TGZ\0"
uint32 Original size of bitmap data
uint32 Width of image
uint32 Heigth of image
Byte[n] Bitmap data (LZSS compressed)

I could have created a class for decoding TGZ, but with it being that simple, I just chose to integrate the decoding in the renderImageToScreen method:

void ZEngine::renderImageToScreen(const Common::String &fileName, uint32 x, uint32 y) {
    Common::File file;

    if (!file.open(fileName)) {
        error("Could not open file %s", fileName.c_str());
        return;
    }

    // Read the magic number
    // Some files are true TGA, while others are TGZ
    char fileType[4];
    file.read(fileType, 4);

    // Check for TGZ files
    if (fileType[0] == 'T' && fileType[1] == 'G' && fileType[2] == 'Z' && fileType[3] == '\0') {
        // TGZ files have a header and then Bitmap data that is compressed with LZSS
        uint32 decompressedSize = file.readSint32LE();
        uint32 width = file.readSint32LE();
        uint32 height = file.readSint32LE();

        LzssReadStream stream(&file);
        byte *buffer = new byte[decompressedSize];
        stream.read(buffer, decompressedSize);

        _system->copyRectToScreen(buffer, width * 2, x, y, width, height);
    } else {
        // Reset the cursor
        file.seek(0);

        // Decode
        Graphics::TGADecoder tga;
        if (!tga.loadStream(file)) {
            error("Error while reading TGA image");
            return;
        }

        const Graphics::Surface *tgaSurface = tga.getSurface();
        _system->copyRectToScreen(tgaSurface->pixels, tgaSurface->pitch, x, y, tgaSurface->w, tgaSurface->h);

        tga.destroy();
    }

    _needsScreenUpdate = true;
}

So after using the loadimage command in the console, we get a wonderful picture on the screen:

Video!! Implementing the image aspect of video was rather trivial, as ZEngine uses a standard AVI format. The only 'wrinkle' was that the videos used a different PixelFormat. Every other part of the engine uses RGB 555, but videos use RGB 565. However, when a video is playing, it's only thing going on. So, I can reinitialize the graphics to RGB 565 before playing a video, and reset it back to RGB 555 when the video finishes:

void ZEngine::startVideo(Video::VideoDecoder *videoDecoder) {
    if (!videoDecoder)
        return;

    _currentVideo = videoDecoder;

    Common::List formats;
    formats.push_back(videoDecoder->getPixelFormat());
    initGraphics(_width, _height, true, formats);
           .
           .
           .
}

void ZEngine::continueVideo() {
           .
           .
           .

    if (!_currentVideo->endOfVideo()) {
        // Code to render the current frame
    } else {
        initGraphics(_width, _height, true, &_pixelFormat);
        delete _currentVideo;
        _currentVideo = 0;
        delete _scaledVideoFrameBuffer;
        _scaledVideoFrameBuffer = 0;
    }
}

Where _pixelFormat is a const PixelFormat member variable of the ZEngine class.

One other slight wrinkle is that the video is at a resolution of 256 x 160, which is quite small if I do say so myself. To fix that, I used a linear 2x scaler that [md5] wrote and scaled every frame. Using the opening cinematic as an example, we get this:

However, the sound in video is messed up, and it's actually been what I've been working on this week, but I'll save that for another post.

I'm now two steps closer to getting all the parts of the engine implemented and somewhat tied together. As always, if you have an suggestions or comments, feel free to comment below.

-RichieSams

The Engine Skeleton Gains Some Tendons - Part 1

Being a little tired of the script system, I started last week by adding image handling, video handling and a text debug console to the engine. With that done, I tried piecing together how the script system worked as a whole. After a long talk with Fuzzie, we figured out the majority of the system worked and I've spent the beginning of this week putting it into code.

I'll start with the script system since it's fresh in my mind. Rather than try to explain what I learned, I'll just explain my current understanding of the system and it's behavior.

The system is governed by five main containers:

Common::HashMap<uint32, byte> _globalState;

Common::List<ActionNode *> _activeNodes;

Common::HashMap<uint32, Common::Array<Puzzle *>> _referenceTable;

Common::Stack<Puzzle *> _puzzlesToCheck;

Common::List<Puzzle> _activePuzzles;

Common::List<Control> _activeControls;

_globalState holds the state of the entire game. Each key is a hash that can represent anything from a timer to whether a certain puzzle has been solved. The value depends on the what the key is, however, the vast majority are boolean states (0 or 1).

_activeNodes holds... wait for it... the active ActionNodes. Imagine that! Nodes are anything that needs to be processed over time. For example, a timer, an animation, etc. I'll explain further later in the post.

_referenceTable stores references to the Puzzles that certain globalState keys have. This can be thought of as a reverse of the Puzzle struct. A Puzzle stores a list of globalState keys to be checked. _referenceTable stores which Puzzles reference certain globalState keys. Why would we want to do this? It means that any puzzles loaded into the _reference table only have to be checked once, instead of every frame. When a value in _globalState is changed, it adds the referenced Puzzle to _puzzlesToCheck

_puzzlesToCheck holds the Puzzles whose Criteria we want to check against _globalState. This stack is exhausted every frame. It is filled either by _referenceTable or when we enter a new room.

_activePuzzles is where the room's Puzzles are stored. The Puzzle pointers in _referenceTable and _puzzlesToCheck point to here.

I realize that the descriptions are still a bit vague, so I figured I would go through an example of sorts and how the containers behave.

Every time we change rooms:

1. Clear _referenceTable, _puzzlesToCheck, and _activePuzzles
2. Open and parse the corresponding .scr file into Puzzle structs and store them in _activePuzzles. (See last three blog posts)
3. Iterate through all the Puzzles and their Criteria and create references from a globalState key to the Puzzle. (See createReferenceTable below)
4. Add all Puzzles to _puzzlesToCheck

void ScriptManager::createReferenceTable() {
    // Iterate through each Puzzle
    for (Common::List<Puzzle>::iterator activePuzzleIter = _activePuzzles.begin(); activePuzzleIter != _activePuzzles.end(); activePuzzleIter++) {
        Puzzle *puzzlePtr = &(*activePuzzleIter);

        // Iterate through each Criteria and add a reference from the criteria key to the Puzzle
        for (Common::List<Criteria>::iterator criteriaIter = activePuzzleIter->criteriaList.begin(); criteriaIter != (*activePuzzleIter).criteriaList.end(); criteriaIter++) {
            _referenceTable[criteriaIter->key].push_back(puzzlePtr);

            // If the argument is a key, add a reference to it as well
            if (criteriaIter->argument)
                _referenceTable[criteriaIter->argument].push_back(puzzlePtr);
        }
    }

    // Remove duplicate entries
    for (Common::HashMap<uint32, Common::Array<Puzzle *>>::iterator referenceTableIter; referenceTableIter != _referenceTable.end(); referenceTableIter++) {
        removeDuplicateEntries(&(referenceTableIter->_value));
    }
}

Every frame:

1. Iterate through each ActionNode in _activeNodes and call process() on them
2. If process() returns true, remove and delete the ActionNode

void ScriptManager::updateNodes(uint32 deltaTimeMillis) {
    // If process() returns true, it means the node can be deleted
    for (Common::List<ActionNode *>::iterator iter = _activeNodes.begin(); iter != _activeNodes.end();) {
        if ((*iter)->process(_engine, deltaTimeMillis)) {
            // Remove the node from _activeNodes, then delete it
            ActionNode *node = *iter;
            iter = _activeNodes.erase(iter);
            delete node;
        } else {
            iter++;
        }
    }
}

bool NodeTimer::process(ZEngine *engine, uint32 deltaTimeInMillis) {
    _timeLeft -= deltaTimeInMillis;

    if (_timeLeft <= 0) {
        engine->getScriptManager()->setStateValue(_key, 0);
        return true;
    }

    return false;
}

1. While _puzzlesToCheck is not empty, pop a Puzzle off the stack and check its Criteria against _globalState
2. If any of the Criteria pass, call execute() on the corresponding ResultAction.
• Some ResultAction's might create ActionNode's and add them to _activeNodes. IE ActionTimer

void ScriptManager::checkPuzzleCriteria() {
    while (!_puzzlesToCheck.empty()) {
        Puzzle *puzzle = _puzzlesToCheck.pop();
        // Check each Criteria
        for (Common::List<Criteria>::iterator iter = puzzle->criteriaList.begin(); iter != puzzle->criteriaList.end(); iter++) {
            bool criteriaMet = false;

            // Get the value to compare against
            byte argumentValue;
            if ((*iter).argument)
                argumentValue = getStateValue(iter->argument);
            else
                argumentValue = iter->argument;

            // Do the comparison
            switch ((*iter).criteriaOperator) {
            case EQUAL_TO:
                criteriaMet = getStateValue(iter->key) == argumentValue;
                break;
            case NOT_EQUAL_TO:
                criteriaMet = getStateValue(iter->key) != argumentValue;
                break;
            case GREATER_THAN:
                criteriaMet = getStateValue(iter->key) > argumentValue;
                break;
            case LESS_THAN:
                criteriaMet = getStateValue(iter->key) < argumentValue;
                break;
            }

            // TODO: Add logic for the different Flags (aka, ONCE_PER_INST)
            if (criteriaMet) {
                for (Common::List<ResultAction *>::iterator resultIter = puzzle->resultActions.begin(); resultIter != puzzle->resultActions.end(); resultIter++) {
                    (*resultIter)->execute(_engine);
                }
            }
        }
    }
}

bool ActionTimer::execute(ZEngine *zEngine) {
    zEngine->getScriptManager()->addActionNode(new NodeTimer(_key, _time));
    return true;
}

So that's the script system. I've tried to explain it in the best way possible, but if you guys have any questions or suggestions for my implementation, as always, feel free to comment.

Details on the image handling, video handling and the text debug console will be in Part 2, which should be up some time tomorrow. As always, thanks for reading. :)

-RichieSams

Improving the 'Object' class (including renaming it) and using classes for ResultActions

Last week, I posted about using an 'Object' class to encapsulate the variable-typed arguments for ResultActions. You guys posted some awesome feedback and I used it to improve the class. First, I renamed the class to 'SingleValueContainer' so users have a better sense of what it is. Second, following Fuzzie's advice, I put all the values except for String, directly in the union. It's the same or less memory cost and results in less heap allocations.

union {
    bool boolVal;
    byte byteVal;
    int16 int16Val;
    uint16 uint16Val;
    int32 int32Val;
    uint32 uint32Val;
    float floatVal;
    double doubleVal;
    char *stringVal;
} _value;

You'll notice that the stringVal isn't actually a Common::String object, but rather a pointer to a char array. This saves a bit of memory at the cost of a couple strlen(), memcpy(), and String object assigment.

SingleValueContainer::SingleValueContainer(Common::String value) : _objectType(BYTE) {
    _value.stringVal = new char[value.size() + 1];
    memcpy(_value.stringVal, value.c_str(), value.size() + 1);
}

SingleValueContainer &SingleValueContainer::operator=(const Common::String &rhs) {
    if (_objectType != STRING) {
        _objectType = STRING;
        _value.stringVal = new char[rhs.size() + 1];
        memcpy(_value.stringVal, rhs.c_str(), rhs.size() + 1);

        return *this;
    }

    uint32 length = strlen(_value.stringVal);
    if (length <= rhs.size() + 1) {
        memcpy(_value.stringVal, rhs.c_str(), rhs.size() + 1);
    } else {
        delete[] _value.stringVal;
        _value.stringVal = new char[rhs.size() + 1];
        memcpy(_value.stringVal, rhs.c_str(), rhs.size() + 1);
    }

    return *this;
}

bool SingleValueContainer::getStringValue(Common::String *returnValue) const {
    if (_objectType !=  STRING)
        warning("'Object' is not storing a Common::String.");

    *returnValue = _value.stringVal;
    return true;
}

With those changes the class seems quite solid. (The full source can be found here and here). However, after seeing Zidane Sama's comment, I realized that there was a better way to tackle the problem than variant objects. Instead of trying to generalize the action types and arguments and storing them in structs, a better approach is to create a class for each action type with a common, "execute()" method that will be called by the scriptManager when the Criteria are met for an ResultAction.

I first created an interface base class that all the different types would inherit from:

class ResultAction {
public:
    virtual ~ResultAction() {}
    virtual bool execute(ZEngine *zEngine) = 0;
};

Next, I created the individual classes for each type of ResultAction:

class ActionAdd : public ResultAction {
public:
    ActionAdd(Common::String line);
    bool execute(ZEngine *zEngine);

private:
    uint32 _key;
    byte _value;
};

The individual classes parse out any arguments in their constructor and store them in member variables. In execute(), they execute the logic pertaining to their action. A pointer to ZEngine is passed in order to give the method access to all the necessary tools (modifying graphics, scriptManager states, sounds, etc.)

class ResultAction {
ActionAdd::ActionAdd(Common::String line) {
    sscanf(line.c_str(), ":add(%u,%hhu)", &_key, &_value);
}

bool ActionAdd::execute(ZEngine *zEngine) {
    zEngine->getScriptManager()->addToStateValue(_key, _value);
    return true;
}

Thus, in the script file parser I can just look for the action type and then pass create an action type, passing the constructor the whole line:

while (!line.contains('}')) {
    // Parse for the action type
    if (line.matchString("*:add*", true)) {
        actionList.push_back(ActionAdd(line));
    } else if (line.matchString("*:animplay*", true)) {
        actionList.push_back(ActionAnimPlay(line));
    } else if (.....)
         .
         .
         .
}

While this means I have to create 20+ classes for all the different types of actions, I think this method nicely encapsulates and abstracts both the parsing and the action of the result.

I'm a bit sad that I'm not going to be using the 'SingleValueContainer' class, but if nothing else, I learned quite a bit while creating it. Plus, I won't be getting rid of it, so it might have a use somewhere else.

This coming week I need to finish creating all the classes and then try to finish the rest of the engine skeleton. As always, feel free to comment / ask questions.

-RichieSams

Implementing a generic single value container in c++

In my previous post I explained the format of the script system for ZEngine. Each Puzzle has a Results section which essentially stores function names and their arguments:

results {
    action:assign(5985, 0)
    background:timer:7336(60)
    event:change_location(C,B,C0,1073)
    background:music:5252(1 a000h1tc.raw 1)    
}

I wanted to be able to store each action inside a struct, and then have a linked list of all the structs. However, the problem is that both the number of arguments and the size of the arguments are variable. Marisa Chan's solution was to store all the arguments in a space delimited char array. IE:

char arguments[25] = "1 a00h1tc.raw 1";

Simple, but not without it's problems.

1. Since the char array is in a struct, the size is fixed. In order to make sure we never overflow, we have to allocate a fairly large array. That said, in this particular case, each 'large' array in this case would only be ~30 bytes per struct.
2. By storing everything as strings, we put off parsing till the action function is actually called. At first glace, this doesn't seem too bad, since the data will have to be parsed anyway. However, this method forces it to be parsed at every call to that action function.

Another option was to have everything stored in a linked list of void pointers. However, I don't think I need to convince anyone that void pointers are just gross and using them would be just asking for problems.

What I really wanted was a typed way to store a variably typed (and sized) value. Therefore I created what I'm calling the "Object" class. (I'm up for suggestions for a better name)

The heart of the class is a union that stores a variety of pointers to different types and an enum that defines what type is being stored:

class Object {
public:
    enum ObjectType : byte {
        BOOL,
        BYTE,
        INT16,
        UINT16,
        INT32,
        UINT32,
        FLOAT,
        DOUBLE,
        STRING,
    };

private:
    ObjectType _objectType;

    union {
        bool *boolVal;
        byte *byteVal;
        int16 *int16Val;
        uint16 *uint16Val;
        int32 *int32Val;
        uint32 *uint32Val;
        float *floatVal;
        double *doubleVal;
        Common::String *stringVal;
    } _value;
}

_objectType keeps track of what type of data the object is storing and _value points to the actual data. If _value were instead to hold the actual data value, the union would be forced to sizeof(Common::String), which is quite large (~34 bytes), due to internal caching. Then we're back to the argument of storing things in containers much larger than what they need. By putting the data on the heap and only storing pointers to the data, we save the wasted space, but at the CPU cost of heap allocation.

Now that the data is stored, how do we get it back? My original idea was to have implicit cast operators:

operator bool();
operator byte();
operator int16();
      .
      .
      .

However, LordHoto, one of the GSoC mentors and ScummVM developers, brought my attention to the problems that can arise when using implicit casting. For example, a user could try to cast the data to a type that wasn't stored in the Object and the cast would work, but the data would be completely corrupted. Also, from a user point of view, it wasn't intuitive.

Therefore, I removed the cast operators and created accessor methods:

bool getBoolValue(bool *returnValue) const;
bool getByteValue(byte *returnValue) const;
bool getInt16Value(int16 *returnValue) const;
           .
           .
           .

bool Object::getBoolValue(bool *returnValue) const {
    if (_objectType !=  BOOL) {
        warning("'Object' not of type bool.");
        return false;
    }

    *returnValue = *_value.boolVal;
    return true;
}

This adds a layer of type semi-protection to the class.

Lastly, I added assigment operators to the class, but rather than making this post even longer, I'll just link the full source here and here.


Advantages of 'Object' class

• Can store relatively 'any' type of data. (Any type not currently supported could be trivially added)
• Only uses as much space as needed.
• Transforms dynamically typed data into a statically typed 'box' that can be stored in arrays, linked lists, hashmaps, etc. and can be iterated upon

Disadvantages of 'Object' class

• Adds a small memory overhead per object. ( 1 byte + sizeof(Operating System pointer) )
• Adds one heap memory allocation per object

So is it better than Marisa Chan's implementation? It really depends on what you define as better. While it does save memory, only requires data to be parsed once, and, in my opinion, adds a great deal of elegance to handling the Results arguments, it does so at the cost of heap storage. Not only the cost of the initial allocation, but the cost of potential defragmentation runs. But then again, is the cost of heap storage really that big, especially since the data should have a relatively long life? (On average, the time an end user spends in a room in the game) That I don't know, since it all depends on the memory allocator implementation.

In the end, I believe both methods perform well, and as such I choose the eloquence of using the 'Object' class. I am very much open to your thoughts on both the class as a whole or on your take of the problem. Also, if I misspoke about something please, please, please let me know.

Thanks for reading and have fun coding,
-RichieSams


Edit: Upon further inspection I noticed that by using Common::String I'm not only negating any memory size benefits from using 'Object', but potentially even using more memory, since Common::String has such a huge size.

Marisa Chan:
char arguments[25] = "1 a00h1tc.raw 1";
size = 25;

Object:
Object arg1 = 1;
Object arg2 = "a00h1tc.raw";
Object arg3 = 1;

size = (3 *sizeof(Object)) + sizeof(byte) + sizeof(Common::String) + sizeof(byte);
size = 15 + 1 + 34 + 1;
size = 51;

I could instead store the data in a char array, but it would mean that the Object class would need a stringLength member, which adds another 1 - 4 bytes on every instance of the class. Even with this new insight, I think I will continue to use 'Object', again for the added eloquence it adds. The memory difference is still rather small.

Scripting!!!!!!

I just realized that I forgot to do a post last week! I was being so productive, time just flew by.

Last week and the beginning of this week I've been working on the script management system for ZEngine. Well, before I get into that, let me go back a little further. According to my original timeline, the next milestone was creating a skeleton engine that could do basic rendering, sounds, and events. So, last Monday, I started by cleaning up the main game loop and splitting everything into separate methods and classes. With that, the run loop looks like this:

Common::Error ZEngine::run() {
    initialize();
    
    // Main loop
    uint32 currentTime = _system->getMillis();
    uint32 lastTime = currentTime;
    const uint32 desiredFrameTime = 33; // ~30 fps
    
    while (!shouldQuit()) {
        processEvents();
        
        currentTime = _system->getMillis();
        uint32 deltaTime = currentTime - lastTime;
        lastTime = currentTime;
        
        updateScripts();
        updateAnimations(deltaTime);
        
        if (_needsScreenUpdate)
        {
            _system->updateScreen();
        }
        
        // Calculate the frame delay based off a desired frame rate
        int delay = desiredFrameTime - (currentTime - _system->getMillis());
        // Ensure non-negative
        delay = delay < 0 ? 0 : delay;
        _system->delayMillis(delay);
    }
    
    return Common::kNoError;
}

No bad, if I do say so myself. :)

That done, I started implementing the various method shells, such as processEvents(). It was about that time that I realized the the structure of the scripting system had a huge impact on the structure of the engine as a whole. For example, should the event system call methods directly, or should it just register key presses, etc. and let the script system handle the calls? I had a basic understanding of how it probably worked, knowing the history of adventure games, but it was clear I needed to understand the script system before I could go any further.

The .scr files themselves are rather simple; they're text-based if-then statements. Here's an example of a puzzle and a control:

puzzle:5251 {
    criteria { 
        [4188] = 1
        [4209] ! 5
        [7347] = 1
        [67] = 0
    }
    criteria { 
        [4209] > 1
        [7347] = 1
        [67] = 1
        [4188] = [6584]
    }
    results {
        action:assign(5985, 0)
        background:timer:7336(60)
        event:change_location(C,B,C0,1073)
        background:music:5252(1 a000h1tc.raw 1)    
    }
    flags {
        ONCE_PER_INST
    }
}

control:8454 push_toggle {
    flat_hotspot(0,265,511,54)
    cursor(backward)
}

Puzzles:

• Criteria are a set of comparisons. If ANY of the criteria are satisfied, the results are called.
• The number in square brackets is the key in a 'global' variable hashmap. (The hashmap isn't actually global in my implementation but rather a member variable in the ScriptManager class) 
• Next is a simplified form of the standard comparison operators ( ==, !=, <, > ). 
• The last number can either be a constant or a key to another global variable. 
• Results are what happens when one of the criteria is met. The first part defines a function, and the remaining parts are the arguments.
• I haven't fully figured out flags, but from what I can see it's a bitwise OR of when results can be called. For example, only once per room.

For those of you that understand code better than words:

if (criteriaOne || criteriaTwo) {
    assign(5985, 0);
    timer(7336, 60);
    change_location('C', 'B', "C0", 1073);
    music(5252, 1, "a000h1tc.raw", 1);
}

Controls:

• I haven't done much work on controls yet, but from what I have done, they look to be similar to results and are just called whenever interacted with. For example, a lever being toggled.

The majority of the week was spent working on the best way to store this information so all the conditions could be readily tested and actions fired. The best way I've come up with so far, is to have a Criteria struct and a Results struct as follows:

/** Criteria for a Puzzle result to be fired */
struct Criteria {
    /** The id of a global state */
    uint32 id;
    /**  
     * What we're comparing the value of the global state against
     * This can either be a pure value or it can be the id of another global state
     */
    uint32 argument;
    /** How to do the comparison */
    CriteriaOperator criteriaOperator;
    /** Is 'argument' the id of a global state or a pure value */
    bool argumentIsAnId;
};

/** What happens when Puzzle criteria are met */
struct Result {
    ResultAction action;
    Common::List<Object> arguments;
};

CriteriaOperator is an enum of the operators and ResultAction is an enum of all the possible actions. The other variables are pretty self explanatory.

Using the Criteria and Result structs, the Puzzle struct is:

struct Puzzle {
    uint32 id;
    Common::List<criteria> criteriaList;
    Common::List<result> resultList;
    byte flags;
};

Thus, the process is: read a script file, parse the puzzles into structs and load the structs into a linked list representing all the currently active puzzles. Elegant and exceedingly fast to iterate for criteria comparison checking. Now, some of you may have noticed the 'Object' class and are probably thinking to yourselves, "I thought this was c++, not c# or <insert terrible coffee-named language here>." It is, but that is a whole post to itself, which I will be writing after this one.

So, a couple hundred words in, what have I said? Well, over this past week I discovered how the script system determines what events to fire. This has helped me not only to design the script system code, but also has given me insight into how to design the other systems in the engine. For example, I now know that mouse and keyboard events will just translate to setting global state variables.

What I have left to do in the ScriptManager:

• Figure out what CriteriaFlags are used for
• Create shell methods for all the Result 'actions'
• Write the parser and storage for control and figure out how they are called

Well that's about it for this post, so until next time,
-RichieSams

ZFS File format

Over the years I've reverse engineered quite a few file formats, but I've never really sat down and picked apart why a format was designed the way it was. With that said, I wanted to show the ZFS archive file format and highlight some of the peculiarities I saw and perhaps you guys can answer some of my questions.

For some context, Z-engine was created around 1995 and was used on Macintosh, MS-DOS, and Windows 95.

Format

The main file header is defined as:

struct ZfsHeader {
    uint32 magic;
    uint32 unknown1;
    uint32 maxNameLength;
    uint32 filesPerBlock;
    uint32 fileCount;
    byte xorKey[4];
    uint32 fileSectionOffset;
};

• magic and unknown1 are self explanatory
• maxNameLength refers to the length of the block that stores a file's name. Any extra spaces are null.
• The archive is split into 'pages' or 'blocks'. Each 'page' contains, at max, filesPerBlock files
• fileCount is total number of files the archive contains
• xorKey is the XOR cipher used for encryption of the files
• fileSectionOffset is the offset of the main data section, aka fileLength - mainHeaderLength

The file entry header is defined as:

struct ZfsEntryHeader {
    char name[16];
    uint32 offset;
    uint32 id;
    uint32 size;
    uint32 time;
    uint32 unknown;
};

• name is the file name right-padded with null characters
• offset is the offset to the actual file data
• id is a the numeric id of the file. The id's increment from 0 to fileCount
• size is the length of the file
• unknown is self explanatory

Therefore, the entire file structure is as follows:

[Main Header]
 
[uint32 offsetToPage2]
[Page 1 File Entry Headers]
[Page 1 File Data]
 
[uint32 offsetToPage3]
[Page 2 File Entry Headers]
[Page 2 File Data]
 
etc.

Questions and Observations

maxNameLength
Why have a fixed size name block vs. null terminated or [size][string]? Was that just the popular thing to do back then so the entire header to could be cast directly to a struct?

filesPerBlock
What is the benefit to pagination? The only explanation I can see atm is that it was some artifact of their asset compiler max memory. Maybe I'm missing something since I've never programmed for that type of hardware.

fileSectionOffset
I've seen things like this a lot in my reverse engineering; they give the offset to a section that's literally just after the header. Even if they were doing straight casting instead of incremental reading, a simple sizeof(mainHeader) would give them the offset to the next section. Again, if I'm missing something, please let me know.


Well that's it for now,
-RichieSams