Ouch my eye!

In my last post we took the first steps towards writing an PIC encoder by implementing the necessary pixel packing and RLE encoding schemes. All that is left is writing the LZW compressor, and that is the subject for this post. While I had hoped that by the end of this post we will have all the parts necessary to make a fully functional encoder for MicroProse PIC files., the Fates had another path in mind…

Back in my third post in this series we covered off on the LZW basics and started implementing the decompression code, with the final debugging a few posts later. If you haven’t read those posts, I suggest going back and reading them first, as we will rely a lot on what was established there. My third post also contains some links to some good external references for more background on LZW compression, if you need a background refresher. As with the decompressor, I’m primarily following the path as set out by Mark Nelson in his Dr Dobb’s article from 1989. So with that laid down, let’s get down to business.

Writing the LZW compressor

As a base I’m going to start with the code and structures we have with the decompressor. One of the first things we will need is some sort of database or lookup table so we can quickly find strings already created. To do that we will use a simple hash table. The hash table will just be a series of 16 bit indices into our already existing dictionary. For the hash table to work its size needs to be relatively prime to the index key and stride values, and to keep collisions to minimum so we will use a value of 3079, which is the smallest prime number larger than 1.5 * 2¹¹ which is 150% our max number of entries. I chose 150% to try and reduce collisions and thus search time, though the choice here is somewhat arbitrary. We could just as easily use 2053 (smallest prime greater than 2048) to save memory, at the cost of potentially longer search times. We will also need a couple of more variables to hold the state of the compression code from call to call. Unlike the decompressor we wrote, the compressor will need to be called repeatedly as bytes are encoded since we are at the tail-end of the stack instead of the head now.

typedef struct {
    uint8_t     bit_count;   // count of bits currently loaded in bit_buffer
    uint32_t    bit_buffer;  // small working buffer for the input stream

    uint8_t     code_bits;   // current code width in bits
    uint32_t    code_mask;   // current bitmask for the code
    uint32_t    resize_code; // current code to force a width increase or reset

    uint16_t    next_code;   // value of next available code

    // compression vars
    uint16_t    chain_code;  // value of last found code for current string
    uint16_t    hash_point;  // hash table insertion point

    // our tables
    lzw_dictionary_t dictionary[LZW_TABLE_SIZE]; // table containing the chaining codes (compression+decompression)
    uint8_t symbol_stack[LZW_SYMBOL_LIMIT]; // used for constructing the stream of bits to output during expansion (decompression only)
    uint16_t hash_table[LZW_HASH_TABLE_SIZE]; // hash table containing the chaining codes (compression only)
} lzw_state_t;

With the new vars we need to update the initialization routines, specifically the reset routine. And unlike the decompression routine we need to clear the tables, to ensure we don’t get a false match.

void lzw_reset(lzw_state_t *ctx) {
    ctx->code_bits = LZW_MIN_CODE_WIDTH;
    ctx->resize_code = (1 << LZW_MIN_CODE_WIDTH);
    ctx->code_mask = ((1 << LZW_MIN_CODE_WIDTH) - 1);
    ctx->next_code = (1 << SYMBOL_WIDTH);
     // clear the table, preserving the first 256 entries 
    memset(&ctx->dictionary[256], 0, (LZW_TABLE_SIZE-256) * sizeof(lzw_dictionary_t));
    ctx->chain_code = LZW_EOC;
    // clear the table to 0xFFFF (LZW_EMPTY)
    memset(ctx->hash_table, 0xff, LZW_HASH_TABLE_SIZE * sizeof(uint16_t));

}

That covers off on the changes to the existing structures. Next we will need a way to write our variable width codes out to the file. This will essentially be an inversion of our read_code() routine from the compressor, and we will re-use the bit_buffer and related context vars here.

// write the bits out to the file
void write_code(FILE *dst, uint16_t code, lzw_state_t *ctx) {
    uint32_t new_bits = 0;

    if(LZW_EOF != code) {
        new_bits = code;
        new_bits &= ctx->code_mask;
        ctx->bit_buffer |= (new_bits << ctx->bit_count);
        ctx->bit_count += ctx->code_bits;
    } else {
        // special case for when we are passed EOF to flush the buffer, pad with 0 bits
        // one less than the output width to ensure the last byte written contains at
        // least one bit of the final code
        ctx->bit_count += (SYMBOL_WIDTH-1); 
    }
    
    while(SYMBOL_WIDTH <= ctx->bit_count) {
        uint8_t out_bits = ctx->bit_buffer;
        fputc(out_bits, dst);
        ctx->bit_buffer >>= SYMBOL_WIDTH;
        ctx->bit_count -= SYMBOL_WIDTH;
    }
}

Next we need to implement our hash lookup code. Note the highlighted lines, I embarrassingly forgot that on my first pass… oops!

// look to see if we already have a string in the form of prefix:symbol
uint16_t seek_chain(uint16_t prefix, uint8_t symbol, lzw_state_t *ctx) {
    // create the hash by combining the prefix with symbol
    uint32_t hash = prefix;
    hash <<= SYMBOL_WIDTH;
    hash |= symbol;
    hash <<= (SYMBOL_WIDTH / 2); // this will spread the key and stride values
    // by dividing SYMBOL_WIDTH by 2 in the final shift we can guarantee 
    // stride is always less than hash table size
    // at this point HASH is 21 - 27 bits for 8 bit symbols (9-15 bit codes)

    // generate our key and stride values from the hash
    uint32_t key = hash % LZW_HASH_TABLE_SIZE;
    uint16_t stride = hash / LZW_HASH_TABLE_SIZE;
    // make sure we never have a stride of 0!
    if(stride==0) stride = (LZW_HASH_TABLE_SIZE / 4);

    uint16_t index = LZW_NO_CODE;

    uint16_t start_key = key;
    do {
        index = ctx->hash_table[key];
        if(LZW_EMPTY != index) { // we have an index
            // if it's a match, return the index
            if( (ctx->dictionary[index].prefix == prefix) && 
                (ctx->dictionary[index].symbol == symbol)) {
                return index;
            }

            // if we got here, we had a collision
            // step by stride to try and find it a the next location
            key += stride; 
            if (key > LZW_HASH_TABLE_SIZE) {
                key -= LZW_HASH_TABLE_SIZE;
            }
        }
    } while(LZW_EMPTY != index);

    // if we got here, we didn't find a match and are pointing to the
    // the first available slot where the new entry can go based on key:stride

    // save the place where the entry should be, so we can insert it there
    ctx->hash_point = key;

    // return no match found
    return LZW_NO_CODE;
}

Now all that’s left is to write the core compression routine itself. First as we are repeatedly calling this function to compress the input stream as it is passed in, we need a mechanism to signal the end of the stream so that we can process out any data we may still be holding onto.

int lzw_compress(FILE *dst, int symbol, lzw_state_t *ctx) {

    // passing EOF triggers a flushing of the output
    if(EOF == symbol) {
        write_code(dst, ctx->chain_code, ctx); // write the final string code
        write_code(dst, LZW_EOF, ctx); // flush the bit buffer
        return LZW_NOERROR; // nothing more to do
    }

Next we need to handle the start-up condition, where we don’t have any previous data to have a prefix:symbol pair.

    // startup condition
    if(LZW_EOC == ctx->chain_code) {
        // no need to look it up, all single character codes are guarnateed to 
        // be in the dictionary
        ctx->chain_code = symbol; 
        return LZW_NOERROR; // nothing more to do
    }

Now that we’ve covered off on our special cases, we need to look up the current string, if it exists save the code to our state, and exit. If it doesn’t exist, we need to output the previous string code, and then create a new one code for the new string, adding it to the tables.

    // see if chain_code + symbol exists already
    uint16_t new_code = seek_chain(ctx->chain_code, symbol, ctx); 

    if(LZW_NO_CODE != new_code) { // match found, keep extending
        ctx->chain_code = new_code;
        return LZW_NOERROR;
    }

    if(LZW_LIMIT <= ctx->next_code) { // table is full!
        return LZW_STRING_TABLE_FULL;
    }

    // write out the old code
    write_code(dst, ctx->chain_code, ctx);

    // create a new code for the current string
    new_code = ctx->next_code;
    lzw_add_code(ctx->chain_code, symbol, ctx); // add it to the dictionary
    ctx->hash_table[ctx->hash_point] = new_code; // and the hash table

Finally we need to expand or reset the table, and set-up for the next pass.

    // start the next string with the current symbol
    ctx->chain_code = symbol;

    // handle table expansion and reset
    if(ctx->next_code >= ctx->resize_code) {
        // check if we are at max bits, if so reset instead of resize
        if(LZW_MAX_CODE_WIDTH > ctx->code_bits) {
            lzw_resize(ctx);
        } else {
            lzw_reset(ctx);
        }
    }
    return LZW_NOERROR;
}

And that should be it. Time to give it a go and see what we get.

PIC LZW Compressor
Opening RLE Image: 'TITLE16.RLE'	File Size: 14826
Creating PIC Image: 'TITLE16.PIC2'
Compression Complete

MD5 (TITLE16.PIC) = bd7a9c10dcd06fec62af1071a678ad7f
MD5 (TITLE16.PIC2) = 2113c51d9dd68496dc99274a5b922705

Well that’s not good.

PIC to PPM image converter
Resolution: 320 x 200
Using Packed Pixel Arrangement
Opening PIC Image: 'TITLE16.PIC2'	File Size: 7524
Warning: Decompression returned code: PIC_BUFFER_OVERFLOW
Decompressed: 64000 bytes
Creating PPM Image: 'TITLE16.PPM'
Writing PPM Image

Dang-it, not even close! I guess it was too much to ask for it to work first-try.

Debugging the compressor

Let’s dig in and see where we went wrong. We seem to be off right out of the gate.

Reference TITLE16.PIC
File: TITLE16.PIC  [7529 bytes]  Skipped Prefix Bytes: 1  Symbol: 9 bits LE
Offset     00  01  02  03  04  05  06  07  08  09  0A  0B  0C  0D  0E  0F  10  11  
00000000: 000 090 044 088 008 088 000 105 090 007 008 080 10B 000 080 000 104 105 
00000012: 088 088 080 10F 114 106 090 013 10C 101 05A 10B 008 101 00A 0DD 090 024 
00000024: 101 013 11F 090 05B 11F 118 00A 04D 044 090 022 0D4 125 127 05E 127 008 
00000036: 0D0 12E 024 00D 101 07A 137 123 08D 101 011 10F 127 066 12D 123 131 090 

Generated TITLE16.PIC2
File: TITLE16.PIC2  [7554 bytes]  Skipped Prefix Bytes: 1  Symbol: 9 bits LE
Offset     00  01  02  03  04  05  06  07  08  09  0A  0B  0C  0D  0E  0F  10  11  
00000000: 000 090 044 088 008 088 000 104 090 007 008 080 10A 000 080 000 103 104 
00000012: 088 088 080 10E 113 105 090 013 10B 100 05A 10A 008 100 00A 0DD 090 024 
00000024: 100 013 11E 090 05B 11E 117 00A 04D 044 090 022 0D4 124 126 05E 126 008 
00000036: 0D0 12D 024 00D 100 07A 136 122 08D 100 011 10E 126 066 12C 122 130 090 

Well that’s interesting, things actually appear to be closer than the image would lead us to believe. Seems all our generated codes (codes >= 0x100) are off by 1, we are always one lower. Then I remembered that during our debugging of the decompressor we discovered that the LZW stream doesn’t have a typical startup, it seems to start assuming a zero already in the queue (value probably isn’t actually important, I don’t think, as code 128 never seems to be emitted). We can quickly test that by feeding in a dummy byte of zero.

Generated TITLE16.PIC2
File: TITLE16.PIC2  [7524 bytes]  Skipped Prefix Bytes: 1  Symbol: 9 bits LE
Offset     00  01  02  03  04  05  06  07  08  09  0A  0B  0C  0D  0E  0F  10  11   
00000000: 000 000 090 044 088 008 088 000 105 090 007 008 080 10B 000 080 000 104 

Hmm, that fixed our one off problem, but now we have a new problem of having the extra byte. Perhaps my initial belief that the compressor started off with a “previous value” of zero was incorrect… maybe code 128 is reserved, it is after all traditionally used for in-band signalling. We never actually see code 128, at least not with 9 bit code widths, or before the first reset that I’ve seen. Let’s change the init value for the first available code to be 129 instead of 128. This could be a problem with resets, but we’ll deal with that later.

Generated TITLE16.PIC2
File: TITLE16.PIC2  [7520 bytes]  Skipped Prefix Bytes: 1  Symbol: 9 bits LE
Offset     00  01  02  03  04  05  06  07  08  09  0A  0B  0C  0D  0E  0F  10  11  
00000000: 000 090 044 088 008 088 000 105 090 007 008 080 10B 000 080 000 104 105 

That’s much better. Will have to make a note of this and possibly update the decompression code. The size is still off, so obviously there is more to do still. However, let’s take a look and see how the image looks, we should at least see part of what we expect now.

PIC to PPM image converter
Resolution: 320 x 200
Using Packed Pixel Arrangement
Opening PIC Image: 'TITLE16.PIC2'	File Size: 7520
Warning: Decompression returned code: PIC_CORRUPT_STREAM
Decompressed: 6244 bytes
Creating PPM Image: 'TITLE16.PPM'

Well that’s a start. The decompression error suggests an invalid/unexpected code. So we must be resetting or resizing incorrectly. So let’s temporarily abort compression at the first resize and see how much image we get, this should help us see if the problem is a resize, or a reset.

Failure point looks to be the same, so we must be filing at the resize. Thinking about it, we are resizing the code width, but still have a pending code to be emitted. Let’s force outputting the code before the resize.

Nope, that wasn’t it. I now suspect we have some re-arranging to do, as the compressor is one step ahead of the decompressor. We need to make sure we resize at the same point as the decompressor would. Let’s move the resize code to just after where we write out the current code.

Progress! I suspect now we are running up against the table reset. My first suspect is that start value of code 129. We are not doing that in the decompressor, though it is naturally happening before the first reset, because of how we are doing it, and the codes we see in the file. Let’s try making it so that on initialization the first code is 129, but it goes back to 128 after a reset.

MD5 (TITLE16.PIC) = bd7a9c10dcd06fec62af1071a678ad7f
MD5 (TITLE16.PIC2) = bd7a9c10dcd06fec62af1071a678ad7f

Looks like we have a winner! It’s been a struggle to get this far, took quite a bit longer than I had planned, but feels good to have it done, and working.

WTF? How? This makes no sense to me! This is the same file that gave us problems with RLE. But it makes no sense here that we resize and reset just fine on the other files, but not this one. F#@K!

This post is part of a series of posts surrounding my reverse engineering efforts of the PIC file format that MicroProse used with their games. Specifically F-15 Strike Eagle II (Though I plan to trace the format through other titles to see if and how it changes). To read my other posts on this topic you can use this link to my archive page for the PIC File Format which will contain all my posts to date on the subject.