gbdk-2020 | GameBoy Development Kit |
| download: https://git.y1.nz/archives/gbdk.tar.gz | |
| README | Files | Log | Refs | LICENSE |
gbdk-support/gbcompress/rlecompress.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 "rlecompress.h"
11
12
13 static uint8_t * FinBuf = NULL;
14 static uint32_t Fsize_in = 0;
15 static uint32_t FinIndex = 0;
16
17 static uint8_t ** pp_FoutBuf = NULL;
18 static uint8_t * FoutBuf = NULL;
19 static uint32_t Fsize_out = 0;
20 static uint32_t FoutIndex = 0;
21
22
23 #define RLE_MASK_LEN 0x7F
24 #define RLE_MASK_TYPE 0x80
25 #define RLE_TYPE_RAND 0x00
26 #define RLE_TYPE_REPEAT 0x80
27 #define RLE_MAX_LEN 127
28 #define RLE_CTRL_END 0x00
29 #define RLE_MAX_BLOCK 127
30 #define RLE_CHANGE_COST 2
31
32
33 static uint8_t rle_queued[128];
34 static int rle_queue_idx = 0;
35 static int run_len = 0;
36
37
38 // Initialize the buffer vars
39 static void initbufs(uint8_t * inBuf, uint32_t size_in, uint8_t ** pp_outBuf, uint32_t size_out) {
40
41 FinBuf = inBuf;
42 Fsize_in = size_in;
43 FinIndex = 0;
44
45 pp_FoutBuf = pp_outBuf;
46 FoutBuf = *pp_outBuf;
47 Fsize_out = size_out;
48 FoutIndex = 0;
49 }
50
51
52 static void check_write_size(int len) {
53
54 // Grow output buffer if needed
55 if ((FoutIndex + len) >= Fsize_out) {
56 uint8_t * p_tmp = *pp_FoutBuf;
57
58 // Reallocate to twice as large
59 Fsize_out = Fsize_out * 2;
60 *pp_FoutBuf = (void *)realloc(*pp_FoutBuf, Fsize_out);
61
62 // If realloc failed, free original buffer before quitting
63 if (!(*pp_FoutBuf)) {
64 printf("Error: Failed to grow memory for output buffer!\n");
65 if (p_tmp) free(p_tmp);
66 p_tmp = NULL;
67 exit(EXIT_FAILURE);
68 } else
69 FoutBuf = *pp_FoutBuf; // Update working pointer
70 }
71 }
72
73
74
75 static void write_end_of_data(void) {
76
77 check_write_size(1); // writing 1 control byte
78 FoutBuf[FoutIndex++] = RLE_CTRL_END; // Write sequence control byte
79 }
80
81
82 static void write_run_repeat(int len, uint8_t value) {
83
84 if (len) {
85 check_write_size(2); // writing 1 repeated value bytes + 1 control byte
86 // Write sequence control byte (length + type)
87 // Convert length to twos complement to identify it as repeat run
88 FoutBuf[FoutIndex++] = ((len & RLE_MASK_LEN) ^ 0xFFu) + 1u;
89 FoutBuf[FoutIndex++] = value;
90 }
91 }
92
93
94 static void rle_commit() {
95
96 int idx = 0;
97
98 if (rle_queue_idx > 0) {
99 check_write_size(rle_queue_idx + 1); // writing len bytes + 1 control byte
100 // Write sequence control byte (length + type)
101 FoutBuf[FoutIndex++] = (rle_queue_idx & RLE_MASK_LEN) | RLE_TYPE_RAND;
102 while (rle_queue_idx > 0) {
103 FoutBuf[FoutIndex++] = rle_queued[idx++];
104 rle_queue_idx--;
105 }
106 }
107 rle_queue_idx = 0; // redundant
108 }
109
110
111
112 // Convert buffer inBuf to rlecompress rle encoding and write out to outBuf
113 // Returns converted length
114 uint32_t rlecompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t ** pp_outBuf, uint32_t size_out) {
115
116 uint8_t last, current;
117 initbufs(inBuf, size_in, pp_outBuf, size_out);
118
119 last = 0;
120 run_len = 0;
121 rle_queue_idx = 0;
122
123 while (FinIndex < Fsize_in) {
124
125 current = FinBuf[FinIndex++];
126
127 if (current != last) {
128 // The run stopped, if switching to repeat is worthwhile then
129 // flush preceding random data
130 if (run_len > RLE_CHANGE_COST) {
131 rle_commit();
132 write_run_repeat(run_len, last);
133 } else {
134 // Otherwise treat repeat data as random and queue it
135 // with flushing as needed
136 while(run_len--) {
137 if (rle_queue_idx >= RLE_MAX_BLOCK) {
138 rle_commit();
139 }
140 rle_queued[rle_queue_idx++] = last;
141 }
142 }
143 run_len = 1;
144 last = current;
145 }
146 else {
147 // Flush pending repeat if max length is encountered
148 if (run_len >= RLE_MAX_BLOCK) {
149 rle_commit();
150 write_run_repeat(run_len, last);
151 run_len = 0;
152 }
153 run_len++;
154 }
155
156 }
157
158 // If switching to repeat is worthwhile then flush preceding random data
159 if (run_len > RLE_CHANGE_COST) {
160 rle_commit();
161 write_run_repeat(run_len, last);
162 } else {
163 // Otherwise treat repeat data as random and queue it
164 // with flushing as needed
165 while(run_len--) {
166 if (rle_queue_idx >= RLE_MAX_BLOCK) {
167 rle_commit();
168 }
169 rle_queued[rle_queue_idx++] = last;
170 }
171 }
172
173 // Flush any trailing data
174 rle_commit();
175 write_end_of_data();
176
177 return FoutIndex;
178
179 }
180
181
182
183 static void write_single_byte(uint8_t data) {
184
185 check_write_size(1);
186
187 FoutBuf[FoutIndex++] = data;
188 }
189
190
191 static uint8_t read_single_byte(void) {
192
193 if (FinIndex >= Fsize_in) {
194 printf("Error: Read past end of input buffer!\n");
195 exit(EXIT_FAILURE);
196 }
197
198 return (FinBuf[FinIndex++]);
199 }
200
201
202
203 // Decompress buffer inBuf from gbcompress rle encoding and write to outBuf
204 // Returns converted length
205 uint32_t rledecompress_buf(uint8_t * inBuf, uint32_t size_in, uint8_t ** pp_outBuf, uint32_t size_out) {
206
207 initbufs(inBuf, size_in, pp_outBuf, size_out);
208
209 uint8_t token, rle_len, value;
210
211 while (FinIndex < size_in) {
212
213 token = read_single_byte();
214
215 // Check for EOF token, exit if encountered
216 if (token == RLE_CTRL_END)
217 break;
218 else if ((token & RLE_MASK_TYPE) == RLE_TYPE_RAND) {
219 rle_len = token & RLE_MASK_LEN;
220 while (rle_len--)
221 write_single_byte(read_single_byte());
222 }
223 else { // if ((token & RLE_MASK_TYPE) == RLE_TYPE_REPEAT) {
224 rle_len = ((token ^ 0xFF) + 1) & RLE_MASK_LEN; // length is two's complement
225 value = read_single_byte();
226 while (rle_len--)
227 write_single_byte(value);
228 }
229 }
230
231 return FoutIndex;
232 }
This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.