SGS Compression Algorithm

[JG]

Eureka!  After much trial and error and reworking of the assembly code, I've finally cracked the SGS decompression algorithm.

Here it is for you coders.

Code: [Select]

int input_position = 0;
int output_position = 0;
int shift_byte = 0x00;
int shift_cycle = 0;
while (input_position < input_bytes_length) {
    if (shift_cycle == 0) {
shift_byte = input_bytes[input_position++];
shift_cycle = 8;
    }
    if ((shift_byte & 0x80) == 0x00) {
output_bytes[output_position++] = input_bytes[input_position++];
    }
    else {
int low_byte = input_bytes[input_position++];
int high_byte = input_bytes[input_position++];
int dx_word = (high_byte << 8) + low_byte;
int num_bytes_to_copy = (dx_word >> 12) + 1;
int lookback = dx_word & 0x0FFF;
for (int i = 0; i < num_bytes_to_copy; i++) {
    output_bytes[output_position] = output_bytes[output_position - lookback];
    output_position++;
}
    }
    shift_byte <<= 1;
    shift_cycle--;
}


Now to turn this around into the more difficult compression algorithm...

[黒い灯影]

AWESOME!!

[JG]

Thank goodness the compression algorithm isn't absurdly complex (like say, LZW)

I haven't tested it fully, but I think I've got it.  I need to try it on a larger PCM file - seems to work fine on the smaller WINs I'm testing with.

Code: [Select]

int input_position = 0;
int output_position = 0;
int previous_shift_byte_position = 0;
int shift_byte_position = output_position;
int shift_cycle = 0;
byte shift_byte = 0x00;
while (input_position < input_bytes_length) {
    if (shift_cycle == 0) {
        // write previous cycle shift byte
        previous_shift_byte_position = shift_byte_position;
        output_bytes[shift_byte_position] = shift_byte;

        // start new cycle
        shift_byte_position = output_position;
        output_position++; //skip over shift byte
        shift_cycle = 8;
    }
    shift_cycle--;
    shift_byte <<= 1;

    // determine optimal lookback
    int optimal_lookback_start = 0;
    int optimal_lookback_length = 0;
    int max_lookback = (input_position < 4096) ? input_position : 4096;
    for (int test_start = max_lookback; test_start > 1; test_start--) {
        int test_length = 0;
        while ((test_length < 16) && (input_position + test_length < input_bytes_length) && (input_bytes[input_position + test_length - test_start] == input_bytes[input_position + test_length])) {
        test_length++;
        }
        if ((test_length > optimal_lookback_length) && (test_length > 2)) {
        optimal_lookback_start = test_start;
        optimal_lookback_length = test_length;
        }
    }

    if ((optimal_lookback_length > 2) && ((output_position - optimal_lookback_start) >= 0) && ((output_position - optimal_lookback_start + optimal_lookback_length) < previous_shift_byte_position)) {
        int lookback_start = optimal_lookback_start;
        int compressionWord = lookback_start + ((optimal_lookback_length - 1) << 12);
        output_bytes[output_position++] = (byte)(compressionWord & 0xFF);
        output_bytes[output_position++] = (byte)(compressionWord >> 8);
        input_position += optimal_lookback_length;
       
        // set lowest bit in shift_byte to indicating encoding
        shift_byte |= 0x01;
    }
    else {
        output_bytes[output_position++] = input_bytes[input_position++];
    }
}

// simulate cycles so that shift byte is rolled left properly
while (shift_cycle > 0) {
    shift_cycle--;
    shift_byte <<= 1;
}

// write final shift byte
output_bytes[shift_byte_position] = shift_byte;


If this works as expected, I can recode PackSGS/UnpackSGS/MakeSGS to handle the compression and decompression algorithms.