gbdk-2020 | GameBoy Development Kit |
| download: https://git.y1.nz/archives/gbdk.tar.gz | |
| README | Files | Log | Refs | LICENSE |
commit 0350ee2bdc5897d692bda99d714544cbd366bbe9 parent 159abbcdbaa25a09a6c876b0b5f80fb3cc9bfa68 Author: Toxa <56631470+untoxa@users.noreply.github.com> Date: Thu, 11 Feb 2021 11:53:31 +0300 Merge pull request #132 from bbbbbr/develop_gbcompress Grow output buffers if needed, better input buffer overrun checking Diffstat:
| M | gbdk-support/gbcompress/Makefile | 4 | ++++ |
| M | gbdk-support/gbcompress/gbcompress.c | 263 | ++++++++++++++++++++++++++++++++++++++++++------------------------------------- |
| M | gbdk-support/gbcompress/gbcompress.h | 4 | ++-- |
| M | gbdk-support/gbcompress/main.c | 37 | ++++++++++++++++++++----------------- |
4 files changed, 165 insertions(+), 143 deletions(-)
diff --git a/gbdk-support/gbcompress/Makefile b/gbdk-support/gbcompress/Makefile @@ -15,3 +15,7 @@ $(BIN): $(OBJ) clean: rm -f *.o $(BIN) *~ + rm tmp.* +# round trip the executable through compression and de-compression as a brief test +test: + cp $(BIN) tmp.in; ./gbcompress -v tmp.in tmp.cmp; ./gbcompress -v -d tmp.cmp tmp.dcmp; diff -s tmp.in tmp.dcmp diff --git a/gbdk-support/gbcompress/gbcompress.c b/gbdk-support/gbcompress/gbcompress.c @@ -19,17 +19,34 @@ const uint8_t token_trash = 0xC0; const uint8_t EOFMarker = 0x00; -uint8_t * FinBuf = 0; -uint8_t * FoutBuf = 0; -uint32_t Fsize_in = 0; -uint32_t FOutIndex = 0; -uint32_t Fsize_max = 0; +uint8_t * FinBuf = NULL; +uint32_t Fsize_in = 0; +uint32_t FinIndex = 0; + +uint8_t ** pp_FoutBuf = NULL; +uint8_t * FoutBuf = NULL; +uint32_t Fsize_out = 0; +uint32_t FoutIndex = 0; + static void check_write_size(uint8_t len) { - if ((FOutIndex + len) >= Fsize_max) { - printf("Error: OutBuf too small"); - exit(EXIT_FAILURE); + // Grow output buffer if needed + if ((FoutIndex + len) >= Fsize_out) { + uint8_t * p_tmp = *pp_FoutBuf; + + // Reallocate to twice as larege + Fsize_out = Fsize_out * 2; + *pp_FoutBuf = (void *)realloc(*pp_FoutBuf, Fsize_out); + + // If realloc failed, free original buffer before quitting + if (!(*pp_FoutBuf)) { + printf("Error: Failed to grow memory for output buffer!\n"); + if (p_tmp) free(p_tmp); + p_tmp = NULL; + exit(EXIT_FAILURE); + } else + FoutBuf = *pp_FoutBuf; // Update working pointer } } @@ -38,8 +55,8 @@ static void write_byte(uint8_t len, uint8_t data) { check_write_size(2); // writing 2 bytes - FoutBuf[FOutIndex++] = ((len - 1) & len_mask); - FoutBuf[FOutIndex++] = data; + FoutBuf[FoutIndex++] = ((len - 1) & len_mask); + FoutBuf[FoutIndex++] = data; } @@ -47,9 +64,9 @@ static void write_word( uint8_t len, uint16_t data ) { check_write_size(3); // writing 3 bytes - FoutBuf[FOutIndex++] = (((len - 1) & len_mask) | token_word); - FoutBuf[FOutIndex++] = (uint8_t)((data >> 8) & 0xFF); - FoutBuf[FOutIndex++] = (uint8_t)(data & 0xFF); + FoutBuf[FoutIndex++] = (((len - 1) & len_mask) | token_word); + FoutBuf[FoutIndex++] = (uint8_t)((data >> 8) & 0xFF); + FoutBuf[FoutIndex++] = (uint8_t)(data & 0xFF); } @@ -60,9 +77,9 @@ static void write_string( uint8_t len, uint16_t data) { // conver's complement does not give the negation, see § Most negative number below. t back-ref offset from positive unsigned to negative signed data = (data ^ 0xFFFF) + 1; - FoutBuf[FOutIndex++] = (((len - 1) & len_mask) | token_str); - FoutBuf[FOutIndex++] = (uint8_t)(data & 0xFF); - FoutBuf[FOutIndex++] = (uint8_t)((data >> 8) & 0xFF); + FoutBuf[FoutIndex++] = (((len - 1) & len_mask) | token_str); + FoutBuf[FoutIndex++] = (uint8_t)(data & 0xFF); + FoutBuf[FoutIndex++] = (uint8_t)((data >> 8) & 0xFF); } @@ -72,9 +89,9 @@ static void write_trash( uint8_t len, uint8_t * pos) { check_write_size(len); // writing len bytes - FoutBuf[FOutIndex++] = (((len-1) & len_mask) | token_trash); + FoutBuf[FoutIndex++] = (((len-1) & len_mask) | token_trash); for (i=0; i < len; i++) - FoutBuf[FOutIndex++] = pos[i]; + FoutBuf[FoutIndex++] = pos[i]; } @@ -82,14 +99,14 @@ static void write_end(void) { check_write_size(1); // writing 1 byte - FoutBuf[FOutIndex++] = EOFMarker; + FoutBuf[FoutIndex++] = EOFMarker; } static int read_uint16_t(uint16_t byte_pos, uint16_t * out_data) { if ((byte_pos + 2) < Fsize_in) { - *out_data = (uint16_t)((FinBuf[byte_pos] << 8) + (uint32_t)FinBuf[byte_pos+1]); + *out_data = (uint16_t)((FinBuf[byte_pos] << 8) + (uint16_t)FinBuf[byte_pos+1]); return true; } else return false; @@ -108,9 +125,7 @@ static void flush_trash(uint32_t * byte_pos, uint32_t * trash_len) { // Convert buffer inBuf to gbcompress rle encoding and write out to outBuf // Returns converted length -uint32_t gbcompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t * outBuf, uint32_t size_max) { - - uint32_t byte_pos = 0; // bp +uint32_t gbcompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t ** pp_outBuf, uint32_t size_out) { uint8_t rle_u8_match; // x uint16_t rle_u16_match; // y @@ -124,23 +139,25 @@ uint32_t gbcompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t * outBuf, uin uint32_t rle_str_back_offset; // sr (this is signed in original code, handled differently to be unsigned now) uint32_t rle_str_len_work; // rl - FinBuf = inBuf; - FoutBuf = outBuf; - Fsize_in = size_in; - Fsize_max = size_max; + FinBuf = inBuf; + Fsize_in = size_in; + FinIndex = 0; // bp + + pp_FoutBuf = pp_outBuf; + FoutBuf = *pp_outBuf; + Fsize_out = size_out; + FoutIndex = 0; - byte_pos = 0; trash_len = 0; - FOutIndex = 0; - while (byte_pos < Fsize_in) { + while (FinIndex < Fsize_in) { // Check for u8 RLE run up to 63 bytes max - rle_u8_match = FinBuf[byte_pos]; + rle_u8_match = FinBuf[FinIndex]; rle_u8_len = 1; - while ((byte_pos + rle_u8_len) < Fsize_in) { + while ((FinIndex + rle_u8_len) < Fsize_in) { // If the current u8 matches, increment the length - if ((FinBuf[byte_pos + rle_u8_len] == rle_u8_match) && + if ((FinBuf[FinIndex + rle_u8_len] == rle_u8_match) && (rle_u8_len < 64)) { rle_u8_len++; } @@ -149,11 +166,11 @@ uint32_t gbcompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t * outBuf, uin // Check for overlapping uint16_t RLE run up to 63 bytes max // Read in initial u16 to match against - if (read_uint16_t(byte_pos, &rle_u16_match)) { + if (read_uint16_t(FinIndex, &rle_u16_match)) { uint16_t temp_u16; rle_u16_len = 1; // If the current u16 matches, increment the length - while (read_uint16_t(byte_pos + (rle_u16_len * 2), &temp_u16)) { + while (read_uint16_t(FinIndex + (rle_u16_len * 2), &temp_u16)) { if ((temp_u16 == rle_u16_match) && (rle_u16_len < 64)) { rle_u16_len++; @@ -168,17 +185,17 @@ uint32_t gbcompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t * outBuf, uin rle_str_start = 0; // rle_str_back_offset = 0; rle_str_len = 0; - while (rle_str_start < byte_pos) { + while (rle_str_start < FinIndex) { rle_str_len_work = 0; - // Check for a matching run at rle_str_start against byte_pos + // Check for a matching run at rle_str_start against FinIndex // and save length to rle_str_len_work - while ((byte_pos + rle_str_len_work) < Fsize_in) { + while ((FinIndex + rle_str_len_work) < Fsize_in) { // Test to see if u8 in current sequence matches the u8 for a previous sequence // Break out of the current sequence if it would reach 64 bytes // or it would reach the current byte pos (and cause an overlap) - if ((FinBuf[rle_str_start + rle_str_len_work] == FinBuf[byte_pos + rle_str_len_work]) && - ((rle_str_start + rle_str_len_work) < byte_pos) && + if ((FinBuf[rle_str_start + rle_str_len_work] == FinBuf[FinIndex + rle_str_len_work]) && + ((rle_str_start + rle_str_len_work) < FinIndex) && (rle_str_len_work < 64)) { rle_str_len_work++; @@ -189,7 +206,7 @@ uint32_t gbcompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t * outBuf, uin // If the newly tested sequence length is greater than the previous length // then save the length and store an negative offset to it in rle_str_back_offset if (rle_str_len_work > rle_str_len) { - rle_str_back_offset = byte_pos - rle_str_start; // Changed this from neg offset to pos, and gets flipped to negative on writing it out + rle_str_back_offset = FinIndex - rle_str_start; // Changed this from neg offset to pos, and gets flipped to negative on writing it out rle_str_len = rle_str_len_work; } @@ -201,162 +218,160 @@ uint32_t gbcompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t * outBuf, uin if ((rle_u8_len > 2) && (rle_u8_len > rle_u16_len) && (rle_u8_len > rle_str_len)) { - flush_trash(&byte_pos, &trash_len); + flush_trash(&FinIndex, &trash_len); write_byte(rle_u8_len, rle_u8_match); - byte_pos = byte_pos + rle_u8_len; + FinIndex = FinIndex + rle_u8_len; } else if ((rle_u16_len > 2) && ((rle_u16_len*2) > rle_str_len)) { - flush_trash(&byte_pos, &trash_len); + flush_trash(&FinIndex, &trash_len); write_word(rle_u16_len, rle_u16_match); - byte_pos = byte_pos + rle_u16_len*2; + FinIndex = FinIndex + rle_u16_len*2; } else if (rle_str_len > 3) { - flush_trash(&byte_pos, &trash_len); + flush_trash(&FinIndex, &trash_len); write_string(rle_str_len, rle_str_back_offset); - byte_pos = byte_pos + rle_str_len; + FinIndex = FinIndex + rle_str_len; } else if (trash_len >= 64) { - write_trash(trash_len, &FinBuf[byte_pos-trash_len]); + write_trash(trash_len, &FinBuf[FinIndex-trash_len]); trash_len = 0; } else { trash_len++; - byte_pos++; + FinIndex++; } } // Flush any remaining "trash" bytes - flush_trash(&byte_pos, &trash_len); + flush_trash(&FinIndex, &trash_len); write_end(); - return FOutIndex; + return FoutIndex; } +static void write_single_byte(uint8_t data) { + + check_write_size(1); + + FoutBuf[FoutIndex++] = data; +} + + +static uint8_t read_single_byte(void) { + + if (FinIndex >= Fsize_in) { + printf("Error: Read past end of input buffer!\n"); + exit(EXIT_FAILURE); + } + + return (FinBuf[FinIndex++]); +} + + // Decompress buffer inBuf from gbcompress rle encoding and write to outBuf // Returns converted length -uint32_t gbdecompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t * outBuf, uint32_t size_max) { +uint32_t gbdecompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t ** pp_outBuf, uint32_t size_out) { uint8_t rle_val[2]; uint8_t token; uint8_t rle_toggle; - uint8_t * p_rle_backref; uint8_t * inBuf_end = inBuf + size_in - 1; - uint32_t rle_len; - uint32_t rle_offset; - uint32_t size_out; + uint32_t backref_index; - size_out = 0; - rle_len = 0; + FinBuf = inBuf; + Fsize_in = size_in; + FinIndex = 0; - while (inBuf <= inBuf_end) { + pp_FoutBuf = pp_outBuf; + FoutBuf = *pp_outBuf; + Fsize_out = size_out; + FoutIndex = 0; - // Check for EOF token - if (*inBuf == EOFMarker) - break; - // Load the next RLE token if needed - if (rle_len == 0) { - // Read a RLE token - // First byte should always be a token - token = (*inBuf) & token_mask; - rle_len = ((*inBuf) & len_mask) + 1; + while (FinIndex < size_in) { - inBuf++; // Move to next ENCODED byte + token = read_single_byte(); - rle_toggle = 0; // Reset RLE decoded byte flipflop + // Check for EOF token, exit if encountered + if (token == EOFMarker) + break; + + // Read a RLE token + // First byte should always be a token + rle_len = (token & len_mask) + 1; + token = token & token_mask; - // Reading a RLE Length zero = END of encoded data - // Then break out of loop and quit - if (rle_len == 0) { + // Read how to handle ENCODED RLE Value + switch (token) { + case token_byte: + // Load only one byte + rle_val[0] = read_single_byte(); break; - } - // Read how to handle ENCODED RLE Value - switch (token) { - case token_byte: - // Load only one byte - rle_val[0] = *inBuf; - inBuf++; - break; + case token_word: + // If token is Word double the RLE decode length + rle_len *= 2; + rle_toggle = 0; // Reset RLE decoded word/byte flipflop - case token_word: - // If token is Word double the RLE decode length - rle_len *= 2; - - // Load LS byte then MS Byte - rle_val[0] = *inBuf; - inBuf++; - rle_val[1] = *inBuf; - inBuf++; - break; + // Load LS byte then MS Byte + rle_val[0] = read_single_byte(); + rle_val[1] = read_single_byte(); + break; - case token_str: - // This token: copy N bytes from negative offset of current - // DECODED memory location (back reference) - rle_offset = (uint16_t)(*inBuf); - inBuf++; - rle_offset |= (uint16_t)((*inBuf)<<8); - inBuf++; - // Convert input from from Signed to Unsigned - rle_offset = (rle_offset ^ 0xFFFF) + 1; - - // Assign the string back reference relative to the current buffer pointer - p_rle_backref = outBuf - rle_offset; - break; + case token_str: + // This token: copy N bytes from negative offset of current + // DECODED memory location (back reference) + backref_index = (uint16_t)(read_single_byte()); + backref_index |= (uint16_t)((read_single_byte())<<8); + // Convert input from from Signed to Unsigned + backref_index = (backref_index ^ 0xFFFF) + 1; - case token_trash: // AKA "Trash Bytes" in GBTD - // This token : copy next N bytes directly from ENCODED input - break; - } - } + // Assign the string back reference relative to the current buffer pointer + backref_index = FoutIndex - backref_index; + break; + case token_trash: // AKA "Trash Bytes" in GBTD + // This token : copy next N bytes directly from ENCODED input + break; + } + while (rle_len) { - // Abort if decompressed output exceeds output buffer size - if (size_out >= size_max) { - printf("Error: OutBuf too small"); - exit(EXIT_FAILURE); - } - // Copy the decoded byte into VRAM switch (token) { case token_byte: // Copy from cached repeating RLE value - *outBuf = rle_val[0]; + write_single_byte(rle_val[0]); break; case token_word: // Copy from cached repeating RLE value // Toggle between MS/LS bytes input values - *outBuf = rle_val[rle_toggle]; + write_single_byte(rle_val[rle_toggle]); rle_toggle ^= 0x01; break; case token_str: // Copy byte from the backreferenced VRAM address // Then increment backreference to next VRAM byte - *outBuf = *p_rle_backref; - p_rle_backref++; + write_single_byte(FoutBuf[backref_index++]); break; case token_trash: // Copy directly from encoded input - *outBuf = *inBuf; - inBuf++; + write_single_byte(read_single_byte()); break; } - outBuf++; // Move to next VRAM byte - size_out++; rle_len--; // Decrement number of RLE bytes remaining } } - return size_out; + return FoutIndex; } diff --git a/gbdk-support/gbcompress/gbcompress.h b/gbdk-support/gbcompress/gbcompress.h @@ -5,7 +5,7 @@ #ifndef _GBCOMPRESS_H #define _GBCOMPRESS_H -uint32_t gbcompress_buf(uint8_t * inBuf, uint32_t InSize, uint8_t * outBuf, uint32_t MaxSize); -uint32_t gbdecompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t * outBuf, uint32_t size_max); +uint32_t gbcompress_buf(uint8_t * inBuf, uint32_t InSize, uint8_t ** pp_outBuf, uint32_t size_out); +uint32_t gbdecompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t ** pp_outBuf, uint32_t size_out); #endif // _GBCOMPRESS_H diff --git a/gbdk-support/gbcompress/main.c b/gbdk-support/gbcompress/main.c @@ -101,21 +101,24 @@ void cleanup(void) { static int compress() { - uint32_t buf_size = 0; + uint32_t buf_size_in = 0; + uint32_t buf_size_out = 0; uint32_t out_len = 0; - p_buf_in = file_read_into_buffer(filename_in, &buf_size); + p_buf_in = file_read_into_buffer(filename_in, &buf_size_in); - // Allocate buffer of same size for rle output - p_buf_out = malloc(buf_size); + // Allocate buffer output buffer same size as input + // It can grow more in gbdecompress_buf() + buf_size_out = buf_size_in; + p_buf_out = malloc(buf_size_out); - if ((p_buf_out) && (buf_size > 0)) { - out_len = gbcompress_buf(p_buf_in, buf_size, - p_buf_out, buf_size); + if ((p_buf_out) && (buf_size_in > 0)) { + out_len = gbcompress_buf(p_buf_in, buf_size_in, + &p_buf_out, buf_size_out); if (out_len > 0) if (file_write_from_buffer(filename_out, p_buf_out, out_len)) { if (opt_verbose) - printf("Compressed: %d bytes -> %d bytes (%%%.2f)\n", buf_size, out_len, ((double)out_len / (double)buf_size) * 100); + printf("Compressed: %d bytes -> %d bytes (%%%.2f)\n", buf_size_in, out_len, ((double)out_len / (double)buf_size_in) * 100); return EXIT_SUCCESS; } } @@ -126,24 +129,24 @@ static int compress() { static int decompress() { - uint32_t buf_size = 0; + uint32_t buf_size_in = 0; uint32_t buf_size_out = 0; uint32_t out_len = 0; - p_buf_in = file_read_into_buffer(filename_in, &buf_size); + p_buf_in = file_read_into_buffer(filename_in, &buf_size_in); - // Allocate buffer of same size for rle output - // Todo: replace static buffer allocation with one that grows using realloc - buf_size_out = buf_size * 10; + // Allocate buffer output buffer 3x size of input + // It can grow more in gbdecompress_buf() + buf_size_out = buf_size_in * 3; p_buf_out = malloc(buf_size_out); - if ((p_buf_out) && (buf_size > 0)) { - out_len = gbdecompress_buf(p_buf_in, buf_size, - p_buf_out, buf_size_out); + if ((p_buf_out) && (buf_size_in > 0)) { + out_len = gbdecompress_buf(p_buf_in, buf_size_in, + &p_buf_out, buf_size_out); if (out_len > 0) if (file_write_from_buffer(filename_out, p_buf_out, out_len)) { if (opt_verbose) - printf("Decompressed: %d bytes -> %d bytes (compression was %%%.2f)\n", buf_size, out_len, ((double)buf_size / (double)out_len) * 100); + printf("Decompressed: %d bytes -> %d bytes (compression was %%%.2f)\n", buf_size_in, out_len, ((double)buf_size_in / (double)out_len) * 100); return EXIT_SUCCESS; } }
This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.