Forum > Research & Development
SGS Compression Algorithm
(1/1)
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: ---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--; }
--- End code ---
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: ---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;
--- End code ---
If this works as expected, I can recode PackSGS/UnpackSGS/MakeSGS to handle the compression and decompression algorithms.
Navigation
[0] Message Index
|