In my last post we left of having successfully decoded the PAK and EGA image formats used by Electronic Arts with 688 Attack Sub. In this post we will reverse the process allowing us to convert an input image into the format. This post will mostly concentrate on the EGA image format, as there really isn’t anything to do with the PAK image format as it was just raw image data. The EGA format is more interesting in that it uses a form of RLE compression we had not seen until this point with the formats we’ve looked at so far.
I’ve published my code related to the PAK image format as well as the code discussed here related to the EGA image format to my github profile and have released it under the MIT license. Do what you will with it, just give credit if you use it in your own code.
As we discovered last time the PAK file format was simply a pair of files, one holding the raw pixel data, and the other holding the palette data. As there is nothing to encode or decode here really it’s just copying data around. Also the format can be read and written directly using GIMP and it’s raw image data import/export feature. So I won’t discuss it further here, but I have included some code in my github repo to convert to/from the PAK file format and the Windows BMP format for those interested.
The EGA format is far more interesting to look at. In my last post we learned that the EGA format uses a different from of RLE compression than those we’ve previously encountered. This form of RLE poses some extra challenges when encoding as we are not only concerned with lengths for runs of data, but also lengths for raw pass-through data. These length values are then encoded with a flag bit to establish if it is a run or copied data. The data is also packed 2 pixels per byte, and encoded in reverse scanline order. One of the first things we need to determine before we can write the compressor/encoder is if the encoding is done on the raw pixel stream, or on a per scanline basis. One thing to note, as our code is converting to/from the Windows BMP format. We could optimize the code to not unpack the pixels, or translate the scanline order, as BMP also stores in reverse scanline order, and 4 bit images are packed. However this would have been a purpose built decoder/encoder and not fully demonstrated the decoding and encoding of the format for application elsewhere.
Determining the RLE bounds
In order to determine if the RLE encoding is done on a per line basis, or on the raw stream, we can add some debug prints to our decoder to log the path through the compressed stream. Then if we can see that an encoding (run or copy) is cut short at a line boundary and then restarted on the next line, we know that it is a line based encoding. If it spans the line boundary then we know it is a stream based encoding. This knowledge will drive how we structure our encoder.
while(src.pos < src.len) {
uint8_t tc = src.data[src.pos++];
if(tc >= 128) {
tc = (tc & 0x7f) + 3;
uint8_t tv = src.data[src.pos++];
printf("%d (%02x)\n", tc, tv);
for(int i = 0; i< tc; i++) {
*dst++ = (tv >> 4) & 0x0f;
*dst++ = tv & 0x0f;
x += 2;
}
} else {
tc += 1;
printf("%d [", tc);
for(int i = 0; i< tc; i++) {
uint8_t tv = src.data[src.pos++];
printf(" %02x", tv);
*dst++ = (tv >> 4) & 0x0f;
*dst++ = tv & 0x0f;
x += 2;
}
printf(" ]\n");
}
if(x >= width) {
x = 0;
dst -= (2 * width);
}
}
Running the above code against our reference image produces the following stream.
Electronic Arts EGA image format to BMP image converter
Opening EGA File: 'MAIN.EGA' File Size: 5807
Resolution: 320 x 199
26 (00)
8 [ 0c c0 cc 00 c0 00 0c 00 ]
3 (c0)
20 [ 0c c0 0c 0c 00 c0 00 0c 00 0c 0c cc 00 0c 00 00 cc c0 cc 00 ]
3 (c0)
2 [ 0c 00 ]
3 (0c)
7 [ 00 c0 0c 00 0c c0 cc ]
3 (c0)
22 [ 00 c0 00 00 c0 0c 0c 00 c0 cc 00 00 0c cc 0c cc 0c cc 00 cc 00 c0 ]
3 (0c)
10 [ c0 0c 00 c0 c0 0c c0 00 0c 00 ]
3 (c0)
3 [ 0c 00 cc ]
5 (00)
5 (cc)
1 [ 0c ]
7 (cc)
1 [ c0 ]
25 (00)
26 (00)As we can see from the highlighted lines There is an unusual double run encoding back to back of the same data value. Neither encoding is at the maximum encodable length value of 130. This strongly suggests line based encoding. Summing up the length values we get to 160 at the point where the first run is terminated early, as we are packed 2 pixels to a byte this is exactly the end of a line. This confirms for us that the RLE compression is performed on a scanline basis. With that established we can now start to write the encoder itself.
Packing the pixels
Since the RLE compression is done on a packed pixel stream, the first thing we want to do is take our unpacked pixel stream and pack it. This will make our RLE compression process much easier as we won’t have to pack on the fly, which we would have to do several times per pixel, once per scan, and once when we consume/output the byte to the compressed stream. Luckily we can do this packing in-place as the result is guaranteed to be ½ the size of the unpacked source. Since our source pointer will move at twice the rate of our destination pointer we can safely overwrite the source as we go.
// pack the source pixels
uint8_t *sp, *dp; // source and destination pointers
sp = img.data; // point to start of pixel buffer
dp = img.data;
// loop through all the pixel data, consuming 2 per iteration
for(size_t i = 0; i < img.len; i+=2) {
uint8_t px = *sp++;
px <<= 4;
px |= ((*sp++) & 0x0f);
*dp++ = px;
}
// our width, and size, are 1/2 because we are packed 2 pixels per byte now
width /= 2;
img.len /= 2;
Finding the runs
To make our life easier we’ll want a helper function here that will scan a input line buffer (or part of), and have it return the position and length of the first run that it finds. Consequently this also gives us the length of bytes to copy before we have our run, as any non-zero return position is the copy-length.
int find_run(uint8_t *buf, uint8_t len, int *rpos) {
uint8_t lc = *buf++; // last char to compare to
int lp = 0; // position of "last char"
int count = 1; // length of run
int pos = 1; // current position in buffer
while(pos < len) {
uint8_t cc = *buf++; // current char for comparison
// run has ended (or hasn't started yet)
if(lc != cc) {
// valid runs are >= 3
if(3 <= count) {
*rpos = lp; // return the start position of the run
return count; // return the length of the run
}
// wasn't a valid run, so restart from current position
lp = pos;
count = 1;
lc = cc;
} else { // in a run
count++; // count it
}
pos++; // advance
}
// return our stop position if we didn't find any runs >= 3
if(3 > count) {
*rpos = pos; // return our end position
return 0; // return a length of 0 as we don't have a valid run
}
// return last start position
*rpos = lp; // return the start position of the run
return count; // return the length of the run
}
We could have not set the return position, or set it to -1 here when a run isn’t found, but by returning the stop position we can use that value to determine the copy length in our main loop, and simplify our logic there.
The compression loop
Now that we have our helper function to find runs, we can write our main compression loop. One thing we have to keep in mind is that the helper function can return lengths that are greater than the maximum encodable amount, as such we will need to break those up into multiple encodings. We also will need to track our start position, and length, as we consume bytes of the input with each encoding.
// image is stored from bottom scanline to top
// so start by pointing to the beginning of the last line.
uint8_t *src = &img.data[(height-1) * width];
for(int y = 0; y < height; y++) {
for(int x = 0; x < width;) {
int rpos = 0;
int len = find_run(src, width - x, &rpos);
if(rpos) { // we have bytes to copy before the found run (or we have no run)
int clen = rpos;
while(clen > 128) { // copy length is longer than the maximal encode length
dst.data[dst.pos++] = 127; // max copy length (encoded as len-1)
for(int i = 0; i < 128; i++) { // copy the data
dst.data[dst.pos++] = *src++; // copy and consume the byte
}
clen -= 128;
}
dst.data[dst.pos++] = clen - 1; // copy length (encoded as len-1)
for(int i = 0; i < clen; i++) { // copy the data
dst.data[dst.pos++] = *src++; // copy & consume the byte
}
x += rpos; // adjust our position in the line
}
if(len) { // we found a run-length to encode
int rlen = len;
while(rlen > 130) { // run is longer than the maximal encode length
dst.data[dst.pos++] = 127 + 0x80; // max encoded run length + flag
dst.data[dst.pos++] = *src; // value of byte to be replicated
rlen -= 130;
}
rlen -= 3; // length encoded as length-3
dst.data[dst.pos++] = (rlen - 3) + 0x80; // run length + flag
dst.data[dst.pos++] = *src; // value of byte to be replicated
x += len; // adjust our position in the line
src += len; // consume the bytes
}
}
src -= (2 * width); // advance to the start of the previous scanline
}
And that is pretty much it. Let’s give it a go and see what we get.
Validating the encoder
Electronic Arts EGA image format to BMP image converter
Opening EGA File: 'MAIN.EGA' File Size: 5807
Resolution: 320 x 199
Creating BMP 'MAIN2.BMP'
Done
BMP image to Electronic Arts EGA image format converter
Reading BMP 'MAIN2.BMP'
Creating EGA File: 'MAIN2.EGA'
Done
MD5 (MAIN.EGA) = 74e5a0c47a80abd54fb66cb430112337
MD5 (MAIN2.EGA) = 74e5a0c47a80abd54fb66cb430112337We have a perfect match, so we managed to get the encoding correct on the first try this time. Unfortunately we have only the one EGA file at the moment to work with, so we can’t be sure that there aren’t some edge cases out there.With that said the format seems pretty straight forward, so I’m fairly confidant we have our bases covered here.
I’ve posted the code for the EGA format, as well as the code for the PAK format over on my github. Hopefully someone out there finds it useful. Regardless, it’s been a fun exercise and a fun distraction as I’ve been going through the process of recovering my data on my RAID.
Ouch my eye! 
Leave a comment