gbdk-2020 | GameBoy Development Kit |
| download: https://git.y1.nz/archives/gbdk.tar.gz | |
| README | Files | Log | Refs | LICENSE |
gbdk-support/gbcompress/gbcompress.c
1 // This is free and unencumbered software released into the public domain.
2 // For more information, please refer to <https://unlicense.org>
3 // bbbbbr 2020
4
5 #include <stdio.h>
6 //#include <string.h>
7 #include <stdlib.h>
8 #include <stdbool.h>
9 #include <stdint.h>
10 #include "gbcompress.h"
11
12 const uint8_t len_mask = 0x3F;
13 const uint8_t token_mask = 0xC0;
14
15 #define token_byte 0x00
16 #define token_word 0x40
17 #define token_str 0x80
18 #define token_trash 0xC0
19
20 const uint8_t EOFMarker = 0x00;
21
22 uint8_t * FinBuf = NULL;
23 uint32_t Fsize_in = 0;
24 uint32_t FinIndex = 0;
25
26 uint8_t ** pp_FoutBuf = NULL;
27 uint8_t * FoutBuf = NULL;
28 uint32_t Fsize_out = 0;
29 uint32_t FoutIndex = 0;
30
31
32 static void check_write_size(uint8_t len) {
33
34 // Grow output buffer if needed
35 if ((FoutIndex + len) >= Fsize_out) {
36 uint8_t * p_tmp = *pp_FoutBuf;
37
38 // Reallocate to twice as large
39 Fsize_out = Fsize_out * 2;
40 *pp_FoutBuf = (void *)realloc(*pp_FoutBuf, Fsize_out);
41
42 // If realloc failed, free original buffer before quitting
43 if (!(*pp_FoutBuf)) {
44 printf("Error: Failed to grow memory for output buffer!\n");
45 if (p_tmp) free(p_tmp);
46 p_tmp = NULL;
47 exit(EXIT_FAILURE);
48 } else
49 FoutBuf = *pp_FoutBuf; // Update working pointer
50 }
51 }
52
53
54 static void write_byte(uint8_t len, uint8_t data) {
55
56 check_write_size(2); // writing 2 bytes
57 // printf("* write_byte len: %2d , data: %02x \n", len, data);
58
59 FoutBuf[FoutIndex++] = ((len - 1) & len_mask);
60 FoutBuf[FoutIndex++] = data;
61 }
62
63
64 static void write_word( uint8_t len, uint16_t data ) {
65
66 check_write_size(3); // writing 3 bytes
67 // printf("* write_word len: %2d , data: %02x, %02x \n", len, (uint8_t)((data >> 8) & 0xFF), (uint8_t)(data & 0xFF));
68
69 FoutBuf[FoutIndex++] = (((len - 1) & len_mask) | token_word);
70 FoutBuf[FoutIndex++] = (uint8_t)((data >> 8) & 0xFF);
71 FoutBuf[FoutIndex++] = (uint8_t)(data & 0xFF);
72 }
73
74
75 static void write_string( uint8_t len, uint16_t data) {
76
77 check_write_size(3); // writing 3 bytes
78
79 // Convert back-ref offset from positive unsigned to negative signed to match format
80 data = (data ^ 0xFFFF) + 1;
81 // printf("* write_string len: %2d , data: %02x, %02x \n", len, (uint8_t)((data >> 8) & 0xFF), (uint8_t)(data & 0xFF));
82
83 FoutBuf[FoutIndex++] = (((len - 1) & len_mask) | token_str);
84 FoutBuf[FoutIndex++] = (uint8_t)(data & 0xFF);
85 FoutBuf[FoutIndex++] = (uint8_t)((data >> 8) & 0xFF);
86 }
87
88
89 static void write_trash( uint8_t len, uint8_t * pos) {
90
91 uint8_t i;
92
93 check_write_size(len); // writing len bytes
94 // printf("* write_string len: %2d , data: ", len);
95 // for (i=0; i < len; i++)
96 // printf("%02x, ", pos[i]);
97 // printf("\n");
98
99 FoutBuf[FoutIndex++] = (((len-1) & len_mask) | token_trash);
100 for (i=0; i < len; i++)
101 FoutBuf[FoutIndex++] = pos[i];
102 }
103
104
105 static void write_end(void) {
106
107 check_write_size(1); // writing 1 byte
108
109 FoutBuf[FoutIndex++] = EOFMarker;
110 }
111
112
113 static int read_uint16_t(uint32_t byte_pos, uint16_t * out_data) {
114
115 if ((byte_pos + 2) < Fsize_in) {
116 *out_data = (uint16_t)((FinBuf[byte_pos] << 8) + (uint16_t)FinBuf[byte_pos+1]);
117 return true;
118 }
119 else return false;
120 }
121
122
123 // Writes out any pending "trash" (non-rle sequence) and resets the counter
124 static void flush_trash(uint32_t * byte_pos, uint32_t * trash_len) {
125
126 if (*trash_len > 0) {
127 write_trash(*trash_len, &FinBuf[*byte_pos - *trash_len]);
128 *trash_len = 0;
129 }
130 }
131
132
133 // Convert buffer inBuf to gbcompress rle encoding and write out to outBuf
134 // Returns converted length
135 uint32_t gbcompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t ** pp_outBuf, uint32_t size_out) {
136
137 uint8_t rle_u8_match; // x
138 uint16_t rle_u16_match; // y
139
140 uint32_t rle_u8_len = 0; // r_rb
141 uint32_t rle_u16_len = 0; // r_rw
142 uint32_t rle_str_len = 0; // r_rs
143 uint32_t trash_len = 0; // tb (by "trash" the original author meant, "non-rle sequence of bytes")
144
145 uint32_t rle_str_start; // rr
146 uint32_t rle_str_back_offset; // sr (this is signed in original code, handled differently to be unsigned now)
147 uint32_t rle_str_len_work; // rl
148
149 FinBuf = inBuf;
150 Fsize_in = size_in;
151 FinIndex = 0; // bp
152
153 pp_FoutBuf = pp_outBuf;
154 FoutBuf = *pp_outBuf;
155 Fsize_out = size_out;
156 FoutIndex = 0;
157
158 while (FinIndex < Fsize_in) {
159
160 // printf("@%3d / %3d = %02x\n", FinIndex, Fsize_in, FinBuf[FinIndex]);
161
162 // Check for u8 RLE run up to 63 bytes max
163 rle_u8_match = FinBuf[FinIndex];
164 rle_u8_len = 1;
165 while ((FinIndex + rle_u8_len) < Fsize_in) {
166 // If the current u8 matches, increment the length
167 if ((FinBuf[FinIndex + rle_u8_len] == rle_u8_match) &&
168 (rle_u8_len < 64)) {
169 rle_u8_len++;
170 }
171 else break;
172 }
173
174 // Check for overlapping uint16_t RLE run up to 63 bytes max
175 // Read in initial u16 to match against
176 if (read_uint16_t(FinIndex, &rle_u16_match)) {
177 uint16_t temp_u16;
178 rle_u16_len = 1;
179 // If the current u16 matches, increment the length
180 while (read_uint16_t(FinIndex + (rle_u16_len * 2), &temp_u16)) {
181 if ((temp_u16 == rle_u16_match) &&
182 (rle_u16_len < 64)) {
183 rle_u16_len++;
184 }
185 else break;
186 }
187 } else {
188 // If failed to read a u16 worth of data reset u16 token length
189 // (meaning: near end of buffer and only 1 byte was available)
190 rle_u16_len = 0;
191 }
192
193 // Check for matching sequences starting at current position
194 // against all previous data beginning at start up to 63 bytes max
195 // (back reference "strings")
196 rle_str_back_offset = 0;
197 rle_str_len = 0;
198 // Max string backreference length is 16 bits unsigned
199 // adjust search start accordingly
200 if (FinIndex > 0xFFFF)
201 rle_str_start = FinIndex - 0xFFFF;
202 else
203 rle_str_start = 0;
204
205 while (rle_str_start < FinIndex) {
206 rle_str_len_work = 0;
207
208 // Check for a matching run at rle_str_start against FinIndex
209 // and save length to rle_str_len_work
210 while ((FinIndex + rle_str_len_work) < Fsize_in) {
211 // Test to see if u8 in current sequence matches the u8 for a previous sequence
212 // Break out of the current sequence if it would reach 64 bytes
213 // or it would reach the current byte pos (and cause an overlap)
214 if ((FinBuf[rle_str_start + rle_str_len_work] == FinBuf[FinIndex + rle_str_len_work]) &&
215 ((rle_str_start + rle_str_len_work) < FinIndex) &&
216 (rle_str_len_work < 64)) {
217
218 rle_str_len_work++;
219 }
220 else break;
221 }
222
223 // If the newly tested sequence length is greater than the previous length
224 // then save the length and store an negative offset to it in rle_str_back_offset
225 if (rle_str_len_work > rle_str_len) {
226 rle_str_back_offset = FinIndex - rle_str_start; // Changed this from neg offset to pos, and gets flipped to negative on writing it out
227 rle_str_len = rle_str_len_work;
228 }
229
230 rle_str_start++;
231 }
232
233
234 // Write out any rle data if it's ready
235 if ((rle_u8_len > 2) &&
236 (rle_u8_len > rle_u16_len) &&
237 (rle_u8_len > rle_str_len)) {
238
239 flush_trash(&FinIndex, &trash_len);
240 write_byte(rle_u8_len, rle_u8_match);
241 FinIndex = FinIndex + rle_u8_len;
242 }
243 else if ((rle_u16_len > 2) &&
244 ((rle_u16_len*2) > rle_str_len)) {
245
246 flush_trash(&FinIndex, &trash_len);
247 write_word(rle_u16_len, rle_u16_match);
248 FinIndex = FinIndex + rle_u16_len*2;
249 }
250 else if (rle_str_len > 3) {
251
252 flush_trash(&FinIndex, &trash_len);
253 write_string(rle_str_len, rle_str_back_offset);
254 FinIndex = FinIndex + rle_str_len;
255 }
256 else if (trash_len >= 64) {
257
258 write_trash(trash_len, &FinBuf[FinIndex-trash_len]);
259 trash_len = 0;
260 }
261 else {
262 trash_len++;
263 FinIndex++;
264 }
265
266 }
267
268 // printf("End of compression, flushing unwritten bytes\n");
269
270 // Flush any remaining "trash" bytes
271 flush_trash(&FinIndex, &trash_len);
272
273 write_end();
274
275 return FoutIndex;
276 }
277
278
279
280 static void write_single_byte(uint8_t data) {
281
282 check_write_size(1);
283
284 FoutBuf[FoutIndex++] = data;
285 }
286
287
288 static uint8_t read_single_byte(void) {
289
290 if (FinIndex >= Fsize_in) {
291 printf("Error: Read past end of input buffer!\n");
292 exit(EXIT_FAILURE);
293 }
294
295 return (FinBuf[FinIndex++]);
296 }
297
298
299 // Decompress buffer inBuf from gbcompress rle encoding and write to outBuf
300 // Returns converted length
301 uint32_t gbdecompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t ** pp_outBuf, uint32_t size_out) {
302
303 uint8_t rle_val[2];
304 uint8_t token;
305 uint8_t rle_toggle;
306 uint8_t * inBuf_end = inBuf + size_in - 1;
307 uint32_t rle_len;
308 uint32_t backref_index;
309
310 FinBuf = inBuf;
311 Fsize_in = size_in;
312 FinIndex = 0;
313
314 pp_FoutBuf = pp_outBuf;
315 FoutBuf = *pp_outBuf;
316 Fsize_out = size_out;
317 FoutIndex = 0;
318
319
320 while (FinIndex < size_in) {
321
322 token = read_single_byte();
323
324 // Check for EOF token, exit if encountered
325 if (token == EOFMarker)
326 break;
327
328 // Read a RLE token
329 // First byte should always be a token
330 rle_len = (token & len_mask) + 1;
331 token = token & token_mask;
332
333 // Read how to handle ENCODED RLE Value
334 switch (token) {
335 case token_byte:
336 // Load only one byte
337 rle_val[0] = read_single_byte();
338 break;
339
340 case token_word:
341 // If token is Word double the RLE decode length
342 rle_len *= 2;
343 rle_toggle = 0; // Reset RLE decoded word/byte flipflop
344
345 // Load LS byte then MS Byte
346 rle_val[0] = read_single_byte();
347 rle_val[1] = read_single_byte();
348 break;
349
350 case token_str:
351 // This token: copy N bytes from negative offset of current
352 // DECODED memory location (back reference)
353 backref_index = ((uint16_t)read_single_byte() | (( (uint16_t)read_single_byte() ) << 8));
354 // Convert input from from Signed to Unsigned
355 backref_index = (backref_index ^ 0xFFFF) + 1;
356
357 // Assign the string back reference relative to the current buffer pointer
358 backref_index = (FoutIndex - (uint32_t)backref_index);
359 break;
360
361 case token_trash: // AKA "Trash Bytes" in GBTD
362 // This token : copy next N bytes directly from ENCODED input
363 break;
364 }
365
366 while (rle_len) {
367
368 // Copy the decoded byte into VRAM
369 switch (token) {
370 case token_byte:
371 // Copy from cached repeating RLE value
372 write_single_byte(rle_val[0]);
373 break;
374
375 case token_word:
376 // Copy from cached repeating RLE value
377 // Toggle between MS/LS bytes input values
378 write_single_byte(rle_val[rle_toggle]);
379 rle_toggle ^= 0x01;
380 break;
381
382 case token_str:
383 // Copy byte from the backreferenced VRAM address
384 // Then increment backreference to next VRAM byte
385 write_single_byte(FoutBuf[backref_index++]);
386 break;
387
388 case token_trash:
389 // Copy directly from encoded input
390 write_single_byte(read_single_byte());
391 break;
392 }
393
394 rle_len--; // Decrement number of RLE bytes remaining
395 }
396 }
397
398 return FoutIndex;
399 }
This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.