gbdk-2020 | GameBoy Development Kit |
| download: https://git.y1.nz/archives/gbdk.tar.gz | |
| README | Files | Log | Refs | LICENSE |
gbdk-support/gbcompress/zx0/zx0_expand.c
1 /*
2 * expand.c - decompressor implementation
3 *
4 * Copyright (C) 2021 Emmanuel Marty
5 *
6 * This software is provided 'as-is', without any express or implied
7 * warranty. In no event will the authors be held liable for any damages
8 * arising from the use of this software.
9 *
10 * Permission is granted to anyone to use this software for any purpose,
11 * including commercial applications, and to alter it and redistribute it
12 * freely, subject to the following restrictions:
13 *
14 * 1. The origin of this software must not be misrepresented; you must not
15 * claim that you wrote the original software. If you use this software
16 * in a product, an acknowledgment in the product documentation would be
17 * appreciated but is not required.
18 * 2. Altered source versions must be plainly marked as such, and must not be
19 * misrepresented as being the original software.
20 * 3. This notice may not be removed or altered from any source distribution.
21 */
22
23 /*
24 * Uses the libdivsufsort library Copyright (c) 2003-2008 Yuta Mori
25 *
26 * Implements the ZX0 encoding designed by Einar Saukas. https://github.com/einar-saukas/ZX0
27 * Also inspired by Charles Bloom's compression blog. http://cbloomrants.blogspot.com/
28 *
29 */
30
31 #include <stdlib.h>
32 #include <string.h>
33 #include "zx0_format.h"
34 #include "zx0_expand.h"
35 #include "zx0_libsalvador.h"
36
37 #ifdef _MSC_VER
38 #define FORCE_INLINE __forceinline
39 #else /* _MSC_VER */
40 #define FORCE_INLINE __attribute__((always_inline))
41 #endif /* _MSC_VER */
42
43 static inline FORCE_INLINE int salvador_read_bit(const unsigned char **ppInBlock, const unsigned char *pDataEnd, int *nCurBitMask, unsigned char *bits) {
44 int nBit;
45
46 const unsigned char* pInBlock = *ppInBlock;
47
48 if ((*nCurBitMask) == 0) {
49 if (pInBlock >= pDataEnd) return -1;
50 (*bits) = *pInBlock++;
51 (*nCurBitMask) = 128;
52 }
53
54 nBit = ((*bits) & 128) ? 1 : 0;
55
56 (*bits) <<= 1;
57 (*nCurBitMask) >>= 1;
58
59 *ppInBlock = pInBlock;
60 return nBit;
61 }
62
63 static inline FORCE_INLINE int salvador_read_elias(const unsigned char** ppInBlock, const unsigned char* pDataEnd, const int nInitialValue, const int nIsBackward, int* nCurBitMask, unsigned char* bits) {
64 int nValue = nInitialValue;
65
66 if (nIsBackward) {
67 while (salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits) == 1) {
68 nValue = (nValue << 1) | salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits);
69 }
70 }
71 else {
72 while (!salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits)) {
73 nValue = (nValue << 1) | salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits);
74 }
75 }
76
77 return nValue;
78 }
79
80 static inline FORCE_INLINE int salvador_read_elias_inverted(const unsigned char** ppInBlock, const unsigned char* pDataEnd, const int nInitialValue, int* nCurBitMask, unsigned char* bits) {
81 int nValue = nInitialValue;
82
83 while (!salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits)) {
84 nValue = (nValue << 1) | (salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits) ^ 1);
85 }
86
87 return nValue;
88 }
89
90 static inline FORCE_INLINE int salvador_read_elias_prefix(const unsigned char** ppInBlock, const unsigned char* pDataEnd, const int nInitialValue, const int nIsBackward, int* nCurBitMask, unsigned char* bits, unsigned int nFirstBit) {
91 int nValue = nInitialValue;
92
93 if (nIsBackward) {
94 if (nFirstBit) {
95 nValue = (nValue << 1) | salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits);
96 while (salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits) == 1) {
97 nValue = (nValue << 1) | salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits);
98 }
99 }
100 }
101 else {
102 if (!nFirstBit) {
103 nValue = (nValue << 1) | salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits);
104 while (!salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits)) {
105 nValue = (nValue << 1) | salvador_read_bit(ppInBlock, pDataEnd, nCurBitMask, bits);
106 }
107 }
108 }
109
110 return nValue;
111 }
112
113 /**
114 * Get maximum decompressed size of compressed data
115 *
116 * @param pInputData compressed data
117 * @param nInputSize compressed size in bytes
118 * @param nFlags compression flags (set to FLG_IS_INVERTED)
119 *
120 * @return maximum decompressed size
121 */
122 size_t salvador_get_max_decompressed_size(const unsigned char *pInputData, size_t nInputSize, const unsigned int nFlags) {
123 const unsigned char* pInputDataEnd = pInputData + nInputSize;
124 int nCurBitMask = 0;
125 unsigned char bits = 0;
126 int nIsFirstCommand = 1;
127 const int nIsInverted = (nFlags & FLG_IS_INVERTED) && !(nFlags & FLG_IS_BACKWARD);
128 const int nIsBackward = (nFlags & FLG_IS_BACKWARD) ? 1 : 0;
129 int nDecompressedSize = 0;
130
131 if (pInputData >= pInputDataEnd)
132 return -1;
133
134 while (1) {
135 unsigned int nIsMatchWithOffset;
136
137 if (nIsFirstCommand) {
138 /* The first command is always literals */
139 nIsFirstCommand = 0;
140 nIsMatchWithOffset = 0;
141 }
142 else {
143 /* Read match with offset / literals bit */
144 nIsMatchWithOffset = salvador_read_bit(&pInputData, pInputDataEnd, &nCurBitMask, &bits);
145 if (nIsMatchWithOffset == -1)
146 return -1;
147 }
148
149 if (nIsMatchWithOffset == 0) {
150 unsigned int nLiterals = salvador_read_elias(&pInputData, pInputDataEnd, 1, nIsBackward, &nCurBitMask, &bits);
151
152 /* Count literals */
153
154 if ((pInputData + nLiterals) <= pInputDataEnd) {
155 pInputData += nLiterals;
156 nDecompressedSize += nLiterals;
157 }
158 else {
159 return -1;
160 }
161
162 /* Read match with offset / rep match bit */
163
164 nIsMatchWithOffset = salvador_read_bit(&pInputData, pInputDataEnd, &nCurBitMask, &bits);
165 if (nIsMatchWithOffset == -1)
166 return -1;
167 }
168
169 unsigned int nMatchLen;
170
171 if (nIsMatchWithOffset) {
172 /* Match with offset */
173
174 unsigned int nMatchOffsetHighByte;
175
176 if (nIsInverted)
177 nMatchOffsetHighByte = salvador_read_elias_inverted(&pInputData, pInputDataEnd, 1, &nCurBitMask, &bits);
178 else
179 nMatchOffsetHighByte = salvador_read_elias(&pInputData, pInputDataEnd, 1, nIsBackward, &nCurBitMask, &bits);
180
181 if (nMatchOffsetHighByte == 256)
182 break;
183
184 if (pInputData >= pInputDataEnd)
185 return -1;
186
187 unsigned int nMatchOffsetLowByte = (unsigned int)(*pInputData++);
188
189 nMatchLen = salvador_read_elias_prefix(&pInputData, pInputDataEnd, 1, nIsBackward, &nCurBitMask, &bits, nMatchOffsetLowByte & 1);
190
191 nMatchLen += (2 - 1);
192 }
193 else {
194 /* Rep-match */
195
196 nMatchLen = salvador_read_elias(&pInputData, pInputDataEnd, 1, nIsBackward, &nCurBitMask, &bits);
197 }
198
199 /* Count matched bytes */
200 nDecompressedSize += nMatchLen;
201 }
202
203 return nDecompressedSize;
204 }
205
206 /**
207 * Decompress data in memory
208 *
209 * @param pInputData compressed data
210 * @param pOutData buffer for decompressed data
211 * @param nInputSize compressed size in bytes
212 * @param nMaxOutBufferSize maximum capacity of decompression buffer
213 * @param nDictionarySize size of dictionary in front of input data (0 for none)
214 * @param nFlags compression flags (set to FLG_IS_INVERTED)
215 *
216 * @return actual decompressed size, or -1 for error
217 */
218 size_t salvador_decompress(const unsigned char *pInputData, unsigned char *pOutData, size_t nInputSize, size_t nMaxOutBufferSize, size_t nDictionarySize, const unsigned int nFlags) {
219 const unsigned char *pInputDataEnd = pInputData + nInputSize;
220 unsigned char *pCurOutData = pOutData + nDictionarySize;
221 const unsigned char *pOutDataEnd = pCurOutData + nMaxOutBufferSize;
222 int nCurBitMask = 0;
223 unsigned char bits = 0;
224 int nMatchOffset = 1;
225 int nIsFirstCommand = 1;
226 const int nIsInverted = (nFlags & FLG_IS_INVERTED) && !(nFlags & FLG_IS_BACKWARD);
227 const int nIsBackward = (nFlags & FLG_IS_BACKWARD) ? 1 : 0;
228
229 if (pInputData >= pInputDataEnd && pCurOutData < pOutDataEnd)
230 return -1;
231
232 while (1) {
233 unsigned int nIsMatchWithOffset;
234
235 if (nIsFirstCommand) {
236 /* The first command is always literals */
237 nIsFirstCommand = 0;
238 nIsMatchWithOffset = 0;
239 }
240 else {
241 /* Read match with offset / literals bit */
242 nIsMatchWithOffset = salvador_read_bit(&pInputData, pInputDataEnd, &nCurBitMask, &bits);
243 if (nIsMatchWithOffset == -1)
244 return -1;
245 }
246
247 if (nIsMatchWithOffset == 0) {
248 unsigned int nLiterals = salvador_read_elias(&pInputData, pInputDataEnd, 1, nIsBackward, &nCurBitMask, &bits);
249
250 /* Copy literals */
251
252 if ((pInputData + nLiterals) <= pInputDataEnd &&
253 (pCurOutData + nLiterals) <= pOutDataEnd) {
254 memcpy(pCurOutData, pInputData, nLiterals);
255 pInputData += nLiterals;
256 pCurOutData += nLiterals;
257 }
258 else {
259 return -1;
260 }
261
262 /* Read match with offset / rep match bit */
263
264 nIsMatchWithOffset = salvador_read_bit(&pInputData, pInputDataEnd, &nCurBitMask, &bits);
265 if (nIsMatchWithOffset == -1)
266 return -1;
267 }
268
269 unsigned int nMatchLen;
270
271 if (nIsMatchWithOffset) {
272 /* Match with offset */
273
274 unsigned int nMatchOffsetHighByte;
275
276 if (nIsInverted)
277 nMatchOffsetHighByte = salvador_read_elias_inverted(&pInputData, pInputDataEnd, 1, &nCurBitMask, &bits);
278 else
279 nMatchOffsetHighByte = salvador_read_elias(&pInputData, pInputDataEnd, 1, nIsBackward, &nCurBitMask, &bits);
280
281 if (nMatchOffsetHighByte == 256)
282 break;
283 nMatchOffsetHighByte--;
284
285 if (pInputData >= pInputDataEnd)
286 return -1;
287
288 unsigned int nMatchOffsetLowByte = (unsigned int)(*pInputData++);
289 if (nIsBackward)
290 nMatchOffset = (nMatchOffsetHighByte << 7) | (nMatchOffsetLowByte >> 1);
291 else
292 nMatchOffset = (nMatchOffsetHighByte << 7) | (127 - (nMatchOffsetLowByte >> 1));
293 nMatchOffset++;
294
295 nMatchLen = salvador_read_elias_prefix(&pInputData, pInputDataEnd, 1, nIsBackward, &nCurBitMask, &bits, nMatchOffsetLowByte & 1);
296
297 nMatchLen += (2 - 1);
298 }
299 else {
300 /* Rep-match */
301
302 nMatchLen = salvador_read_elias(&pInputData, pInputDataEnd, 1, nIsBackward, &nCurBitMask, &bits);
303 }
304
305 /* Copy matched bytes */
306 const unsigned char* pSrc = pCurOutData - nMatchOffset;
307 if (pSrc >= pOutData) {
308 if ((pSrc + nMatchLen) <= pOutDataEnd) {
309 if ((pCurOutData + nMatchLen) <= pOutDataEnd) {
310 while (nMatchLen) {
311 *pCurOutData++ = *pSrc++;
312 nMatchLen--;
313 }
314 }
315 else {
316 return -1;
317 }
318 }
319 else {
320 return -1;
321 }
322 }
323 else {
324 return -1;
325 }
326 }
327
328 return (size_t)(pCurOutData - pOutData) - nDictionarySize;
329 }
This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.