Skip to content
Permalink
master
Switch branches/tags
Go to file
 
 
Cannot retrieve contributors at this time
808 lines (663 sloc) 24.7 KB
/*
exhal / inhal (de)compression routines
This code is released under the terms of the MIT license.
See COPYING.txt for details.
Copyright (c) 2013-2018 Devin Acker
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
#include <stdio.h>
#include <string.h>
#include "compress.h"
#include "uthash.h"
// memmem.c
void *memmem(const void *h0, size_t k, const void *n0, size_t l);
#ifdef DEBUG_OUT
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...)
#endif
#define RUN_SIZE 32
#define LONG_RUN_SIZE 1024
// compression method values for backref_t and rle_t
typedef enum {
rle_8 = 0,
rle_16 = 1,
rle_seq = 2,
lz_norm = 0,
lz_rot = 1,
lz_rev = 2
} method_e;
// used to store and compare backref candidates
typedef struct {
uint16_t offset, size;
method_e method;
} backref_t;
// used to store RLE candidates
typedef struct {
uint16_t size, data;
method_e method;
} rle_t;
// used to hash and index byte tuples
typedef struct {
int bytes;
uint16_t offset;
UT_hash_handle hh;
} tuple_t;
// turn 4 bytes into a single integer for quicker hashing/searching
#define COMBINE(w, x, y, z) ((w << 24) | (x << 16) | (y << 8) | z)
typedef struct {
uint8_t *unpacked;
size_t inputsize;
uint8_t *packed;
// current input/output positions
uint32_t inpos;
uint32_t outpos;
// used to collect data which should be written uncompressed
uint8_t dontpack[LONG_RUN_SIZE];
uint16_t dontpacksize;
// index of first locations of byte-tuples used to speed up LZ string search
tuple_t *offsets;
} pack_context_t;
// ------------------------------------------------------------------------------------------------
static pack_context_t* pack_context_alloc(uint8_t *unpacked, size_t inputsize, uint8_t *packed) {
pack_context_t *this;
if (inputsize > DATA_SIZE) return 0;
if (!(this = calloc(1, sizeof(*this)))) return 0;
this->unpacked = unpacked;
this->inputsize = inputsize;
this->packed = packed;
// index locations of all 4-byte sequences occurring in the input
for (uint16_t i = 0; inputsize >= 4 && i < inputsize - 4; i++) {
tuple_t *tuple;
int currbytes = COMBINE(unpacked[i], unpacked[i+1], unpacked[i+2], unpacked[i+3]);
// has this one been indexed already
HASH_FIND_INT(this->offsets, &currbytes, tuple);
if (!tuple) {
tuple = (tuple_t*)malloc(sizeof(tuple_t));
tuple->bytes = currbytes;
tuple->offset = i;
HASH_ADD_INT(this->offsets, bytes, tuple);
}
}
return this;
}
// ------------------------------------------------------------------------------------------------
static void pack_context_free(pack_context_t* this) {
tuple_t *curr, *temp;
HASH_ITER(hh, this->offsets, curr, temp) {
HASH_DEL(this->offsets, curr);
free(curr);
}
free(this);
}
// ------------------------------------------------------------------------------------------------
static inline size_t input_bytes_left(const pack_context_t* this) {
return this->inputsize - this->inpos;
}
// ------------------------------------------------------------------------------------------------
// Reverses the order of bits in a byte.
// One of the back reference methods does this. As far as game data goes, it seems to be
// pretty useful for compressing graphics.
static inline uint8_t rotate (uint8_t i) {
uint8_t j = 0;
if (i & 0x01) j |= 0x80;
if (i & 0x02) j |= 0x40;
if (i & 0x04) j |= 0x20;
if (i & 0x08) j |= 0x10;
if (i & 0x10) j |= 0x08;
if (i & 0x20) j |= 0x04;
if (i & 0x40) j |= 0x02;
if (i & 0x80) j |= 0x01;
return j;
}
// ------------------------------------------------------------------------------------------------
static inline void rle_candidate(rle_t *candidate, size_t size, uint16_t data, method_e method) {
// if this is better than the current candidate, use it
if (method == rle_16 && size >= 2*LONG_RUN_SIZE)
size = 2*LONG_RUN_SIZE;
else if (size > LONG_RUN_SIZE)
size = LONG_RUN_SIZE;
if (size > 2 && size > candidate->size) {
candidate->size = size;
candidate->data = data;
candidate->method = method;
debug("\trle_check: found new candidate (size = %d, method = %d)\n", size, method);
}
}
// ------------------------------------------------------------------------------------------------
// Searches for possible RLE compressed data.
// start and current are positions within the uncompressed input stream.
// fast enables faster compression by ignoring sequence RLE.
static void rle_check(const pack_context_t *this, rle_t *candidate, int fast) {
uint8_t *start = this->unpacked;
uint8_t *current = start + this->inpos;
size_t insize = this->inputsize;
size_t size;
candidate->size = 0;
candidate->data = 0;
candidate->method = 0;
// check for possible 8-bit RLE
for (size = 0; size <= LONG_RUN_SIZE && current + size < start + insize; size++) {
if (current[size] != current[0]) break;
}
rle_candidate(candidate, size, current[0], rle_8);
// check for possible 16-bit RLE
uint16_t first = current[0] | (current[1] << 8);
for (size = 0; size <= 2*LONG_RUN_SIZE && current + size < start + insize - 1; size += 2) {
uint16_t next = current[size] | (current[size + 1] << 8);
if (next != first) break;
}
rle_candidate(candidate, size, first, rle_16);
// fast mode: don't use sequence RLE
if (fast) return;
// check for possible sequence RLE
for (size = 0; size <= LONG_RUN_SIZE && current + size < start + insize; size++) {
if (current[size] != (current[0] + size)) break;
}
rle_candidate(candidate, size, current[0], rle_seq);
}
// ------------------------------------------------------------------------------------------------
static inline void backref_candidate(backref_t *candidate, size_t offset, size_t size, method_e method) {
// if this is better than the current candidate, use it
if (size > LONG_RUN_SIZE) size = LONG_RUN_SIZE;
if (size >= 4 && size > candidate->size) {
candidate->size = size;
candidate->offset = offset;
candidate->method = method;
debug("\tref_search: found new candidate (offset: %4x, size: %d, method = %d)\n", offset, size, method);
}
}
// ------------------------------------------------------------------------------------------------
// Searches for the best possible back reference.
// start and current are positions within the uncompressed input stream.
// fast enables fast mode which only uses regular forward references
static void ref_search (const pack_context_t *this, backref_t *candidate, int fast) {
uint8_t *start = this->unpacked;
uint8_t *current = start + this->inpos;
size_t insize = this->inputsize;
tuple_t *offsets = this->offsets;
uint16_t size;
int currbytes;
tuple_t *tuple;
candidate->size = 0;
candidate->offset = 0;
candidate->method = 0;
// references to previous data which goes in the same direction
// see if this byte sequence exists elsewhere, then start searching.
currbytes = COMBINE(current[0], current[1], current[2], current[3]);
size = 4;
HASH_FIND_INT(offsets, &currbytes, tuple);
if (tuple) for (uint8_t *pos = start + tuple->offset; pos && pos < current;) {
// see how many bytes in a row are the same between the current uncompressed data
// and the data at the position being searched
for (; size <= LONG_RUN_SIZE && current + size < start + insize; size++) {
if (pos[size] != current[size]) break;
}
backref_candidate(candidate, pos - start, size, lz_norm);
// find another instance of the current data to see if it can be a better candidate
pos = memmem(pos + 1, insize - (pos - start) - 1, pos, size);
}
// fast mode: forward references only
if (fast) return;
// references to data where the bits are rotated
currbytes = COMBINE(rotate(current[0]), rotate(current[1]), rotate(current[2]), rotate(current[3]));
size = 4;
HASH_FIND_INT(offsets, &currbytes, tuple);
if (tuple) for (uint8_t *pos = start + tuple->offset; pos && pos < current;) {
// now repeat the check with the bit rotation method
for (; size <= LONG_RUN_SIZE && current + size < start + insize; size++) {
if (pos[size] != rotate(current[size])) break;
}
backref_candidate(candidate, pos - start, size, lz_rot);
// find another instance of the current data to see if it can be a better candidate
pos = memmem(pos + 1, insize - (pos - start) - 1, pos, size);
}
// references to data which goes backwards
currbytes = COMBINE(current[3], current[2], current[1], current[0]);
size = 4;
HASH_FIND_INT(offsets, &currbytes, tuple);
if (tuple) for (uint8_t *pos = start + tuple->offset + 3; pos && pos < current; pos++) {
// now repeat the check but go backwards
// TODO: possibly use memmem to speed up this one a bit also,
// though we'd then basically be searching both backwards and forwards,
// which would be a bit weird to manage correctly...
for (size = 0; size <= LONG_RUN_SIZE && start + size <= pos
&& current + size < start + insize; size++) {
if (start[pos - start - size] != current[size]) break;
}
backref_candidate(candidate, pos - start, size, lz_rev);
}
}
// ------------------------------------------------------------------------------------------------
static inline int write_check_size(const pack_context_t *this, size_t size) {
return this->outpos + this->dontpacksize + size < DATA_SIZE;
}
// ------------------------------------------------------------------------------------------------
// Write uncompressed data to the output stream.
// Returns number of bytes written.
static uint16_t write_raw (pack_context_t *this) {
uint8_t *out = this->packed;
uint16_t insize = this->dontpacksize;
if (!insize) return 0;
debug("%04x %04x write_raw: writing %d bytes unpacked data\n",
this->inpos - insize, this->outpos, insize);
uint16_t size = insize - 1;
int outsize;
if (size >= RUN_SIZE) {
// write_check_size already accounts for size of raw data,
// but also check the size of the command/size byte(s)
outsize = 2;
if (!write_check_size(this, outsize)) return 0;
// write command byte + MSB of size
out[this->outpos++] = 0xE0 + (size >> 8);
// write LSB of size
out[this->outpos++] = size & 0xFF;
}
// normal size run
else {
outsize = 1;
if (!write_check_size(this, outsize)) return 0;
// write command byte / size
out[this->outpos++] = size;
}
// write data
memcpy(&out[this->outpos], this->dontpack, insize);
this->outpos += insize;
this->dontpacksize = 0;
// total size written is the command + size + all data
return outsize + insize;
}
// ------------------------------------------------------------------------------------------------
static inline uint16_t backref_outsize(const backref_t *backref) {
return (backref->size - 1 >= RUN_SIZE) ? 4 : 3;
}
// ------------------------------------------------------------------------------------------------
// Writes a back reference to the compressed output stream.
// Returns number of bytes written
static uint16_t write_backref (pack_context_t *this, const backref_t *backref) {
uint16_t size = backref->size - 1;
uint8_t *out = this->packed;
uint16_t outsize = backref_outsize(backref);
if (!write_check_size(this, outsize)) return 0;
// flush the raw data buffer first
write_raw(this);
debug("%04x %04x write_backref: writing backref to %4x, size %d (method %d)\n",
this->inpos, this->outpos, backref->offset, backref->size, backref->method);
// long run
if (size >= RUN_SIZE) {
// write command byte / MSB of size
out[this->outpos++] = (0xF0 + (backref->method << 2)) | (size >> 8);
// write LSB of size
out[this->outpos++] = size & 0xFF;
}
// normal size run
else {
// write command byte / size
out[this->outpos++] = (0x80 + (backref->method << 5)) | size;
}
// write MSB of offset
out[this->outpos++] = backref->offset >> 8;
// write LSB of offset
out[this->outpos++] = backref->offset & 0xFF;
this->inpos += backref->size;
return outsize;
}
// ------------------------------------------------------------------------------------------------
static inline uint16_t rle_outsize(const rle_t *rle) {
uint16_t size = (rle->size - 1 >= RUN_SIZE) ? 3 : 2;
if (rle->method == rle_16) size++; // account for extra byte of value
return size;
}
// ------------------------------------------------------------------------------------------------
// Writes RLE data to the compressed output stream.
// Returns number of bytes written
static uint16_t write_rle (pack_context_t *this, const rle_t *rle) {
uint16_t size;
uint8_t *out = this->packed;
uint16_t outsize = rle_outsize(rle);
if (!write_check_size(this, outsize)) return 0;
if (rle->method == rle_16) {
size = (rle->size / 2) - 1;
} else {
size = rle->size - 1;
}
// flush the raw data buffer first
write_raw(this);
debug("%04x %04x write_rle: writing %d bytes of data 0x%02x (method %d)\n",
this->inpos, this->outpos, rle->size, rle->data, rle->method);
// long run
if (size >= RUN_SIZE) {
// write command byte / MSB of size
out[this->outpos++] = (0xE4 + (rle->method << 2)) | (size >> 8);
// write LSB of size
out[this->outpos++] = size & 0xFF;
}
// normal size run
else {
// write command byte / size
out[this->outpos++] = (0x20 + (rle->method << 5)) | size;
}
out[this->outpos++] = rle->data;
// write upper byte of 16-bit RLE (and adjust written data size)
if (rle->method == rle_16) {
out[this->outpos++] = rle->data >> 8;
}
this->inpos += rle->size;
return outsize;
}
// ------------------------------------------------------------------------------------------------
// Writes a single byte of raw (literal) data from the input.
// Returns number of bytes written
static uint16_t write_next_byte(pack_context_t *this) {
if (!write_check_size(this, 1)) return 0;
this->dontpack[this->dontpacksize++] = this->unpacked[this->inpos++];
// if the raw data buffer is full, flush it
if (this->dontpacksize == LONG_RUN_SIZE) {
write_raw(this);
}
return 1;
}
// ------------------------------------------------------------------------------------------------
// Writes a single byte to terminate the compressed data.
// Returns number of bytes written
static uint16_t write_trailer(pack_context_t *this) {
if (!write_check_size(this, 1)) return 0;
write_raw(this);
//add the terminating byte
this->packed[this->outpos++] = 0xFF;
return 1;
}
// ------------------------------------------------------------------------------------------------
static void pack_normal(pack_context_t *this, int fast) {
size_t inputsize = this->inputsize;
// backref and RLE compression candidates
backref_t backref = {0};
rle_t rle = {0};
while (inputsize > 0) {
// check for a potential RLE
rle_check(this, &rle, fast);
// check for a potential back reference
if (rle.size < LONG_RUN_SIZE && inputsize >= 4)
ref_search(this, &backref, fast);
else backref.size = 0;
// if the backref is a better candidate, use it
if (backref.size > rle.size) {
if (!write_backref(this, &backref)) break;
}
// or if the RLE is a better candidate, use it instead
else if (rle.size >= 2) {
if (!write_rle(this, &rle)) break;
}
// otherwise, write this byte uncompressed
else {
if (!write_next_byte(this)) break;
}
inputsize = input_bytes_left(this);
}
}
// ------------------------------------------------------------------------------------------------
static void pack_optimal(pack_context_t *this, int fast) {
size_t inputsize = this->inputsize;
// backref and RLE compression candidates
backref_t backref = {0};
rle_t rle = {0};
// test - just go through entire input and score each byte
typedef struct node_s {
// previous and next nodes in directed graph
// (populated when doing shortest-path search)
struct node_s *next, *prev;
// distance to second neighboring node (first is n+1)
size_t neighbor;
// graph edge length between this and neighbor (i.e. size of compressed data)
size_t length;
// distance to start of data
size_t distance;
// backref used for compression (else RLE if neighbor > 0)
int backref;
// RLE data or backref offset
uint16_t data;
// RLE/backref method used
method_e method;
} node_t;
node_t *nodes = calloc(inputsize+1, sizeof(node_t));
node_t *node, *other;
for (this->inpos = 0; this->inpos < inputsize; this->inpos++) {
node = nodes+this->inpos;
node->distance = 1<<16;
// check for a potential RLE
rle_check(this, &rle, fast);
// check for a potential back reference
if (rle.size < LONG_RUN_SIZE && inputsize >= 4)
ref_search(this, &backref, fast);
else backref.size = 0;
// if the backref is a better candidate, use it
if (backref.size > rle.size) {
node->neighbor = backref.size;
node->length = backref_outsize(&backref);
node->method = backref.method;
node->data = backref.offset;
node->backref = 1;
}
// or if the RLE is a better candidate, use it instead
else if (rle.size >= 2) {
node->neighbor = rle.size;
node->length = rle_outsize(&rle);
node->method = rle.method;
node->data = rle.data;
}
}
// find shortest path through input
nodes[0].distance = 0;
nodes[inputsize].distance = 1<<16;
for (size_t i = 0; i < inputsize; i++) {
node = nodes+i;
size_t newdist;
// check first neighbor (next byte)
other = node+1;
newdist = node->distance + 2; // at least 1 literal byte + 1 control byte
if (newdist < other->distance) {
other->distance = newdist;
other->prev = node;
}
// check second neighbor (next byte after compression, if possible)
if (!node->neighbor) continue;
other = node+node->neighbor;
newdist = node->distance + node->length;
if (newdist < other->distance) {
other->distance = newdist;
other->prev = node;
}
}
debug("final distance = %u prev = %04x\n", nodes[inputsize].distance, nodes[inputsize].prev);
// create path back from end to start of data
for (node = nodes+inputsize; node->prev; node = node->prev) {
debug("node = %u prev = %u\n", node-nodes, node->prev-nodes);
node->prev->next = node;
}
// compress data based on shortest path
this->inpos = 0;
for (node = nodes; node->next; node = node->next) {
debug("node = %u next = %u\n", node-nodes, node->next-nodes);
if (node->next == node+1) {
if (!write_next_byte(this)) break;
} else if (node->backref) {
backref.size = node->neighbor;
backref.method = node->method;
backref.offset = node->data;
if (!write_backref(this, &backref)) break;
} else {
rle.size = node->neighbor;
rle.method = node->method;
rle.data = node->data;
if (!write_rle(this, &rle)) break;
}
}
free(nodes);
}
// ------------------------------------------------------------------------------------------------
// Compresses a file of up to 64 kb.
// unpacked/packed are 65536 byte buffers to read/from write to,
// inputsize is the length of the uncompressed data.
// Returns the size of the compressed data in bytes, or 0 if compression failed.
size_t exhal_pack2(uint8_t *unpacked, size_t inputsize, uint8_t *packed, const pack_options_t *options) {
size_t outpos = 0;
debug("inputsize = %d\n", inputsize);
pack_context_t *ctx = pack_context_alloc(unpacked, inputsize, packed);
if (!ctx) return 0;
if (inputsize > 0) {
if (options && options->optimal)
pack_optimal(ctx, options ? options->fast : 0);
else
pack_normal(ctx, options ? options->fast : 0);
}
if (write_trailer(ctx)) {
// compressed data was written successfully
outpos = (size_t)ctx->outpos;
}
pack_context_free(ctx);
return outpos;
}
// ------------------------------------------------------------------------------------------------
size_t exhal_pack(uint8_t *unpacked, size_t inputsize, uint8_t *packed, int fast) {
pack_options_t options = {
.fast = fast,
};
return exhal_pack2(unpacked, inputsize, packed, &options);
}
// ------------------------------------------------------------------------------------------------
// Decompresses a file of up to 64 kb.
// unpacked/packed are 65536 byte buffers to read/from write to,
// Returns the size of the uncompressed data in bytes or 0 if decompression failed.
size_t exhal_unpack(uint8_t *packed, uint8_t *unpacked, unpack_stats_t *stats) {
// current input/output positions
uint32_t inpos = 0;
uint32_t outpos = 0;
uint8_t input;
uint16_t command, length, offset;
if (stats) memset(stats, 0, sizeof(*stats));
while (1) {
int32_t insize = DATA_SIZE - inpos;
// read command byte from input
if (insize < 1) return 0;
input = packed[inpos++];
// command 0xff = end of data
if (input == 0xFF)
break;
// check if it is a long or regular command, get the command no. and size
if ((input & 0xE0) == 0xE0) {
if (insize < 1) return 0;
command = (input >> 2) & 0x07;
// get LSB of length from next byte
length = (((input & 0x03) << 8) | packed[inpos++]) + 1;
} else {
command = input >> 5;
length = (input & 0x1F) + 1;
}
// don't try to decompress > 64kb
if (((command == 2) && (outpos + 2*length > DATA_SIZE))
|| (outpos + length > DATA_SIZE)) {
return 0;
}
switch (command) {
// write uncompressed bytes
case 0:
if (insize < length) return 0;
debug("%06x: writing %u raw bytes\n", inpos, length);
memcpy(&unpacked[outpos], &packed[inpos], length);
outpos += length;
inpos += length;
break;
// 8-bit RLE
case 1:
if (insize < 1) return 0;
debug("%06x: writing %u bytes RLE, value %02x\n", inpos, length, packed[inpos]);
for (int i = 0; i < length; i++)
unpacked[outpos++] = packed[inpos];
inpos++;
break;
// 16-bit RLE
case 2:
if (insize < 2) return 0;
debug("%06x: writing %u words RLE, value %02x%02x\n", inpos, length, packed[inpos], packed[inpos+1]);
for (int i = 0; i < length; i++) {
unpacked[outpos++] = packed[inpos];
unpacked[outpos++] = packed[inpos+1];
}
inpos += 2;
break;
// 8-bit increasing sequence
case 3:
if (insize < 1) return 0;
debug("%06x: writing %u bytes sequence RLE, value %02x\n", inpos, length, packed[inpos]);
for (int i = 0; i < length; i++)
unpacked[outpos++] = packed[inpos] + i;
inpos++;
break;
// regular backref
// (offset is big-endian)
case 4:
case 7:
// 7 isn't a real method number, but it behaves the same as 4 due to a quirk in how
// the original decompression routine is programmed. (one of Parasyte's docs confirms
// this for GB games as well). let's handle it anyway
command = 4;
if (insize < 2) return 0;
offset = (packed[inpos] << 8) | packed[inpos+1];
debug("%06x: writing %u byte forward ref to %x\n", inpos, length, offset);
if (offset + length > DATA_SIZE) return 0;
for (int i = 0; i < length; i++)
unpacked[outpos++] = unpacked[offset + i];
inpos += 2;
break;
// backref with bit rotation
// (offset is big-endian)
case 5:
if (insize < 2) return 0;
offset = (packed[inpos] << 8) | packed[inpos+1];
debug("%06x: writing %u byte rotated ref to %x\n", inpos, length, offset);
if (offset + length > DATA_SIZE) return 0;
for (int i = 0; i < length; i++)
unpacked[outpos++] = rotate(unpacked[offset + i]);
inpos += 2;
break;
// backwards backref
// (offset is big-endian)
case 6:
if (insize < 2) return 0;
offset = (packed[inpos] << 8) | packed[inpos+1];
debug("%06x: writing %u byte backward ref to %x\n", inpos, length, offset);
if (offset < length - 1) return 0;
for (int i = 0; i < length; i++)
unpacked[outpos++] = unpacked[offset - i];
inpos += 2;
}
// keep track of how many times each compression method is used
if (stats) stats->methoduse[command]++;
}
if (stats) stats->inputsize = (size_t)inpos;
return (size_t)outpos;
}
// ------------------------------------------------------------------------------------------------
// Decompress data from an offset into a file
size_t exhal_unpack_from_file(FILE *file, size_t offset, uint8_t *unpacked, unpack_stats_t *stats) {
uint8_t packed[DATA_SIZE] = {0};
fseek(file, offset, SEEK_SET);
fread((void*)packed, DATA_SIZE, 1, file);
if (!ferror(file))
return exhal_unpack(packed, unpacked, stats);
return 0;
}