1/*
2 FastLZ - Byte-aligned LZ77 compression library
3 Copyright (C) 2005-2020 Ariya Hidayat <ariya.hidayat@gmail.com>
4
5 Permission is hereby granted, free of charge, to any person obtaining a copy
6 of this software and associated documentation files (the "Software"), to deal
7 in the Software without restriction, including without limitation the rights
8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 copies of the Software, and to permit persons to whom the Software is
10 furnished to do so, subject to the following conditions:
11
12 The above copyright notice and this permission notice shall be included in
13 all copies or substantial portions of the Software.
14
15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 THE SOFTWARE.
22*/
23
24#include "fastlz.h"
25
26#include <stdint.h>
27
28/*
29 * Always check for bound when decompressing.
30 * Generally it is best to leave it defined.
31 */
32#define FASTLZ_SAFE
33#if defined(FASTLZ_USE_SAFE_DECOMPRESSOR) && (FASTLZ_USE_SAFE_DECOMPRESSOR == 0)
34#undef FASTLZ_SAFE
35#endif
36
37/*
38 * Give hints to the compiler for branch prediction optimization.
39 */
40#if defined(__clang__) || (defined(__GNUC__) && (__GNUC__ > 2))
41#define FASTLZ_LIKELY(c) (__builtin_expect(!!(c), 1))
42#define FASTLZ_UNLIKELY(c) (__builtin_expect(!!(c), 0))
43#else
44#define FASTLZ_LIKELY(c) (c)
45#define FASTLZ_UNLIKELY(c) (c)
46#endif
47
48#if defined(FASTLZ_SAFE)
49#define FASTLZ_BOUND_CHECK(cond) \
50 if (FASTLZ_UNLIKELY(!(cond))) return 0;
51#else
52#define FASTLZ_BOUND_CHECK(cond) \
53 do { \
54 } while (0)
55#endif
56
57#define MAX_COPY 32
58#define MAX_LEN 264 /* 256 + 8 */
59#define MAX_L1_DISTANCE 8192
60#define MAX_L2_DISTANCE 8191
61#define MAX_FARDISTANCE (65535 + MAX_L2_DISTANCE - 1)
62
63#define FASTLZ_READU16(p) ((p)[0] | (p)[1] << 8)
64
65#define HASH_LOG 13
66#define HASH_SIZE (1 << HASH_LOG)
67#define HASH_MASK (HASH_SIZE - 1)
68#define HASH_FUNCTION(v, p) \
69 { \
70 v = FASTLZ_READU16(p); \
71 v ^= FASTLZ_READU16(p + 1) ^ (v >> (16 - HASH_LOG)); \
72 v &= HASH_MASK; \
73 }
74
75int fastlz1_compress(const void* input, int length, void* output) {
76 const uint8_t* ip = (const uint8_t*)input;
77 const uint8_t* ip_bound = ip + length - 2;
78 const uint8_t* ip_limit = ip + length - 12 - 1;
79 uint8_t* op = (uint8_t*)output;
80
81 const uint8_t* htab[HASH_SIZE];
82 uint32_t hval;
83
84 uint32_t copy;
85
86 /* sanity check */
87 if (FASTLZ_UNLIKELY(length < 4)) {
88 if (length) {
89 /* create literal copy only */
90 *op++ = length - 1;
91 ip_bound++;
92 while (ip <= ip_bound) *op++ = *ip++;
93 return length + 1;
94 } else
95 return 0;
96 }
97
98 /* initializes hash table */
99 for (hval = 0; hval < HASH_SIZE; ++hval) htab[hval] = ip;
100
101 /* we start with literal copy */
102 copy = 2;
103 *op++ = MAX_COPY - 1;
104 *op++ = *ip++;
105 *op++ = *ip++;
106
107 /* main loop */
108 while (FASTLZ_LIKELY(ip < ip_limit)) {
109 const uint8_t* ref;
110 uint32_t distance;
111
112 /* minimum match length */
113 uint32_t len = 3;
114
115 /* comparison starting-point */
116 const uint8_t* anchor = ip;
117
118 /* find potential match */
119 HASH_FUNCTION(hval, ip);
120 ref = htab[hval];
121
122 /* update hash table */
123 htab[hval] = anchor;
124
125 /* calculate distance to the match */
126 distance = anchor - ref;
127
128 /* is this a match? check the first 3 bytes */
129 if (distance == 0 || (distance >= MAX_L1_DISTANCE) || *ref++ != *ip++ ||
130 *ref++ != *ip++ || *ref++ != *ip++)
131 goto literal;
132
133 /* last matched byte */
134 ip = anchor + len;
135
136 /* distance is biased */
137 distance--;
138
139 if (!distance) {
140 /* zero distance means a run */
141 uint8_t x = ip[-1];
142 while (ip < ip_bound)
143 if (*ref++ != x)
144 break;
145 else
146 ip++;
147 } else
148 for (;;) {
149 /* safe because the outer check against ip limit */
150 if (*ref++ != *ip++) break;
151 if (*ref++ != *ip++) break;
152 if (*ref++ != *ip++) break;
153 if (*ref++ != *ip++) break;
154 if (*ref++ != *ip++) break;
155 if (*ref++ != *ip++) break;
156 if (*ref++ != *ip++) break;
157 if (*ref++ != *ip++) break;
158 while (ip < ip_bound)
159 if (*ref++ != *ip++) break;
160 break;
161 }
162
163 /* if we have copied something, adjust the copy count */
164 if (copy) /* copy is biased, '0' means 1 byte copy */
165 *(op - copy - 1) = copy - 1;
166 else
167 /* back, to overwrite the copy count */
168 op--;
169
170 /* reset literal counter */
171 copy = 0;
172
173 /* length is biased, '1' means a match of 3 bytes */
174 ip -= 3;
175 len = ip - anchor;
176
177 /* encode the match */
178 if (FASTLZ_UNLIKELY(len > MAX_LEN - 2))
179 while (len > MAX_LEN - 2) {
180 *op++ = (7 << 5) + (distance >> 8);
181 *op++ = MAX_LEN - 2 - 7 - 2;
182 *op++ = (distance & 255);
183 len -= MAX_LEN - 2;
184 }
185
186 if (len < 7) {
187 *op++ = (len << 5) + (distance >> 8);
188 *op++ = (distance & 255);
189 } else {
190 *op++ = (7 << 5) + (distance >> 8);
191 *op++ = len - 7;
192 *op++ = (distance & 255);
193 }
194
195 /* update the hash at match boundary */
196 HASH_FUNCTION(hval, ip);
197 htab[hval] = ip++;
198 HASH_FUNCTION(hval, ip);
199 htab[hval] = ip++;
200
201 /* assuming literal copy */
202 *op++ = MAX_COPY - 1;
203
204 continue;
205
206 literal:
207 *op++ = *anchor++;
208 ip = anchor;
209 copy++;
210 if (FASTLZ_UNLIKELY(copy == MAX_COPY)) {
211 copy = 0;
212 *op++ = MAX_COPY - 1;
213 }
214 }
215
216 /* left-over as literal copy */
217 ip_bound++;
218 while (ip <= ip_bound) {
219 *op++ = *ip++;
220 copy++;
221 if (copy == MAX_COPY) {
222 copy = 0;
223 *op++ = MAX_COPY - 1;
224 }
225 }
226
227 /* if we have copied something, adjust the copy length */
228 if (copy)
229 *(op - copy - 1) = copy - 1;
230 else
231 op--;
232
233 return op - (uint8_t*)output;
234}
235
236#if defined(FASTLZ_USE_MEMMOVE) && (FASTLZ_USE_MEMMOVE == 0)
237
238static void fastlz_memmove(uint8_t* dest, const uint8_t* src, uint32_t count) {
239 do {
240 *dest++ = *src++;
241 } while (--count);
242}
243
244static void fastlz_memcpy(uint8_t* dest, const uint8_t* src, uint32_t count) {
245 return fastlz_memmove(dest, src, count);
246}
247
248#else
249
250#include <string.h>
251
252static void fastlz_memmove(uint8_t* dest, const uint8_t* src, uint32_t count) {
253 if ((count > 4) && (dest >= src + count)) {
254 memmove(dest, src, count);
255 } else {
256 switch (count) {
257 default:
258 do {
259 *dest++ = *src++;
260 } while (--count);
261 break;
262 case 3:
263 *dest++ = *src++;
264 case 2:
265 *dest++ = *src++;
266 case 1:
267 *dest++ = *src++;
268 case 0:
269 break;
270 }
271 }
272}
273
274static void fastlz_memcpy(uint8_t* dest, const uint8_t* src, uint32_t count) {
275 memcpy(dest, src, count);
276}
277
278#endif
279
280int fastlz1_decompress(const void* input, int length, void* output,
281 int maxout) {
282 const uint8_t* ip = (const uint8_t*)input;
283 const uint8_t* ip_limit = ip + length;
284 const uint8_t* ip_bound = ip_limit - 2;
285 uint8_t* op = (uint8_t*)output;
286 uint8_t* op_limit = op + maxout;
287 uint32_t ctrl = (*ip++) & 31;
288
289 while (1) {
290 if (ctrl >= 32) {
291 uint32_t len = (ctrl >> 5) - 1;
292 uint32_t ofs = (ctrl & 31) << 8;
293 const uint8_t* ref = op - ofs - 1;
294 if (len == 7 - 1) {
295 FASTLZ_BOUND_CHECK(ip <= ip_bound);
296 len += *ip++;
297 }
298 ref -= *ip++;
299 len += 3;
300 FASTLZ_BOUND_CHECK(op + len <= op_limit);
301 FASTLZ_BOUND_CHECK(ref >= (uint8_t*)output);
302 fastlz_memmove(op, ref, len);
303 op += len;
304 } else {
305 ctrl++;
306 FASTLZ_BOUND_CHECK(op + ctrl <= op_limit);
307 FASTLZ_BOUND_CHECK(ip + ctrl <= ip_limit);
308 fastlz_memcpy(op, ip, ctrl);
309 ip += ctrl;
310 op += ctrl;
311 }
312
313 if (FASTLZ_UNLIKELY(ip > ip_bound)) break;
314 ctrl = *ip++;
315 }
316
317 return op - (uint8_t*)output;
318}
319
320int fastlz2_compress(const void* input, int length, void* output) {
321 const uint8_t* ip = (const uint8_t*)input;
322 const uint8_t* ip_bound = ip + length - 2;
323 const uint8_t* ip_limit = ip + length - 12 - 1;
324 uint8_t* op = (uint8_t*)output;
325
326 const uint8_t* htab[HASH_SIZE];
327 uint32_t hval;
328
329 uint32_t copy;
330
331 /* sanity check */
332 if (FASTLZ_UNLIKELY(length < 4)) {
333 if (length) {
334 /* create literal copy only */
335 *op++ = length - 1;
336 ip_bound++;
337 while (ip <= ip_bound) *op++ = *ip++;
338 return length + 1;
339 } else
340 return 0;
341 }
342
343 /* initializes hash table */
344 for (hval = 0; hval < HASH_SIZE; ++hval) htab[hval] = ip;
345
346 /* we start with literal copy */
347 copy = 2;
348 *op++ = MAX_COPY - 1;
349 *op++ = *ip++;
350 *op++ = *ip++;
351
352 /* main loop */
353 while (FASTLZ_LIKELY(ip < ip_limit)) {
354 const uint8_t* ref;
355 uint32_t distance;
356
357 /* minimum match length */
358 uint32_t len = 3;
359
360 /* comparison starting-point */
361 const uint8_t* anchor = ip;
362
363 /* check for a run */
364 if (ip[0] == ip[-1] && ip[0] == ip[1] && ip[1] == ip[2]) {
365 distance = 1;
366 ip += 3;
367 ref = anchor - 1 + 3;
368 goto match;
369 }
370
371 /* find potential match */
372 HASH_FUNCTION(hval, ip);
373 ref = htab[hval];
374
375 /* update hash table */
376 htab[hval] = anchor;
377
378 /* calculate distance to the match */
379 distance = anchor - ref;
380
381 /* is this a match? check the first 3 bytes */
382 if (distance == 0 || (distance >= MAX_FARDISTANCE) || *ref++ != *ip++ ||
383 *ref++ != *ip++ || *ref++ != *ip++)
384 goto literal;
385
386 /* far, needs at least 5-byte match */
387 if (distance >= MAX_L2_DISTANCE) {
388 if (*ip++ != *ref++ || *ip++ != *ref++) goto literal;
389 len += 2;
390 }
391
392 match:
393
394 /* last matched byte */
395 ip = anchor + len;
396
397 /* distance is biased */
398 distance--;
399
400 if (!distance) {
401 /* zero distance means a run */
402 uint8_t x = ip[-1];
403 while (ip < ip_bound)
404 if (*ref++ != x)
405 break;
406 else
407 ip++;
408 } else
409 for (;;) {
410 /* safe because the outer check against ip limit */
411 if (*ref++ != *ip++) break;
412 if (*ref++ != *ip++) break;
413 if (*ref++ != *ip++) break;
414 if (*ref++ != *ip++) break;
415 if (*ref++ != *ip++) break;
416 if (*ref++ != *ip++) break;
417 if (*ref++ != *ip++) break;
418 if (*ref++ != *ip++) break;
419 while (ip < ip_bound)
420 if (*ref++ != *ip++) break;
421 break;
422 }
423
424 /* if we have copied something, adjust the copy count */
425 if (copy) /* copy is biased, '0' means 1 byte copy */
426 *(op - copy - 1) = copy - 1;
427 else
428 /* back, to overwrite the copy count */
429 op--;
430
431 /* reset literal counter */
432 copy = 0;
433
434 /* length is biased, '1' means a match of 3 bytes */
435 ip -= 3;
436 len = ip - anchor;
437
438 /* encode the match */
439 if (distance < MAX_L2_DISTANCE) {
440 if (len < 7) {
441 *op++ = (len << 5) + (distance >> 8);
442 *op++ = (distance & 255);
443 } else {
444 *op++ = (7 << 5) + (distance >> 8);
445 for (len -= 7; len >= 255; len -= 255) *op++ = 255;
446 *op++ = len;
447 *op++ = (distance & 255);
448 }
449 } else {
450 /* far away, but not yet in the another galaxy... */
451 if (len < 7) {
452 distance -= MAX_L2_DISTANCE;
453 *op++ = (len << 5) + 31;
454 *op++ = 255;
455 *op++ = distance >> 8;
456 *op++ = distance & 255;
457 } else {
458 distance -= MAX_L2_DISTANCE;
459 *op++ = (7 << 5) + 31;
460 for (len -= 7; len >= 255; len -= 255) *op++ = 255;
461 *op++ = len;
462 *op++ = 255;
463 *op++ = distance >> 8;
464 *op++ = distance & 255;
465 }
466 }
467
468 /* update the hash at match boundary */
469 HASH_FUNCTION(hval, ip);
470 htab[hval] = ip++;
471 HASH_FUNCTION(hval, ip);
472 htab[hval] = ip++;
473
474 /* assuming literal copy */
475 *op++ = MAX_COPY - 1;
476
477 continue;
478
479 literal:
480 *op++ = *anchor++;
481 ip = anchor;
482 copy++;
483 if (FASTLZ_UNLIKELY(copy == MAX_COPY)) {
484 copy = 0;
485 *op++ = MAX_COPY - 1;
486 }
487 }
488
489 /* left-over as literal copy */
490 ip_bound++;
491 while (ip <= ip_bound) {
492 *op++ = *ip++;
493 copy++;
494 if (copy == MAX_COPY) {
495 copy = 0;
496 *op++ = MAX_COPY - 1;
497 }
498 }
499
500 /* if we have copied something, adjust the copy length */
501 if (copy)
502 *(op - copy - 1) = copy - 1;
503 else
504 op--;
505
506 /* marker for fastlz2 */
507 *(uint8_t*)output |= (1 << 5);
508
509 return op - (uint8_t*)output;
510}
511
512int fastlz2_decompress(const void* input, int length, void* output,
513 int maxout) {
514 const uint8_t* ip = (const uint8_t*)input;
515 const uint8_t* ip_limit = ip + length;
516 const uint8_t* ip_bound = ip_limit - 2;
517 uint8_t* op = (uint8_t*)output;
518 uint8_t* op_limit = op + maxout;
519 uint32_t ctrl = (*ip++) & 31;
520
521 while (1) {
522 if (ctrl >= 32) {
523 uint32_t len = (ctrl >> 5) - 1;
524 uint32_t ofs = (ctrl & 31) << 8;
525 const uint8_t* ref = op - ofs - 1;
526
527 uint8_t code;
528 if (len == 7 - 1) do {
529 FASTLZ_BOUND_CHECK(ip <= ip_bound);
530 code = *ip++;
531 len += code;
532 } while (code == 255);
533 code = *ip++;
534 ref -= code;
535 len += 3;
536
537 /* match from 16-bit distance */
538 if (FASTLZ_UNLIKELY(code == 255))
539 if (FASTLZ_LIKELY(ofs == (31 << 8))) {
540 FASTLZ_BOUND_CHECK(ip < ip_bound);
541 ofs = (*ip++) << 8;
542 ofs += *ip++;
543 ref = op - ofs - MAX_L2_DISTANCE - 1;
544 }
545
546 FASTLZ_BOUND_CHECK(op + len <= op_limit);
547 FASTLZ_BOUND_CHECK(ref >= (uint8_t*)output);
548 fastlz_memmove(op, ref, len);
549 op += len;
550 } else {
551 ctrl++;
552 FASTLZ_BOUND_CHECK(op + ctrl <= op_limit);
553 FASTLZ_BOUND_CHECK(ip + ctrl <= ip_limit);
554 fastlz_memcpy(op, ip, ctrl);
555 ip += ctrl;
556 op += ctrl;
557 }
558
559 if (FASTLZ_UNLIKELY(ip >= ip_limit)) break;
560 ctrl = *ip++;
561 }
562
563 return op - (uint8_t*)output;
564}
565
566int fastlz_compress(const void* input, int length, void* output) {
567 /* for short block, choose fastlz1 */
568 if (length < 65536) return fastlz1_compress(input, length, output);
569
570 /* else... */
571 return fastlz2_compress(input, length, output);
572}
573
574int fastlz_decompress(const void* input, int length, void* output, int maxout) {
575 /* magic identifier for compression level */
576 int level = ((*(const uint8_t*)input) >> 5) + 1;
577
578 if (level == 1) return fastlz1_decompress(input, length, output, maxout);
579 if (level == 2) return fastlz2_decompress(input, length, output, maxout);
580
581 /* unknown level, trigger error */
582 return 0;
583}
584
585int fastlz_compress_level(int level, const void* input, int length,
586 void* output) {
587 if (level == 1) return fastlz1_compress(input, length, output);
588 if (level == 2) return fastlz2_compress(input, length, output);
589
590 return 0;
591}
592