summaryrefslogtreecommitdiff
path: root/thirdparty/misc/fastlz.c
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty/misc/fastlz.c')
-rw-r--r--thirdparty/misc/fastlz.c796
1 files changed, 418 insertions, 378 deletions
diff --git a/thirdparty/misc/fastlz.c b/thirdparty/misc/fastlz.c
index 508f6ea2ae..b4d2dd3c29 100644
--- a/thirdparty/misc/fastlz.c
+++ b/thirdparty/misc/fastlz.c
@@ -1,9 +1,6 @@
- /*
- FastLZ - lightning-fast lossless compression library
-
- Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
- Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
- Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+/*
+ FastLZ - Byte-aligned LZ77 compression library
+ Copyright (C) 2005-2020 Ariya Hidayat <ariya.hidayat@gmail.com>
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
@@ -24,239 +21,375 @@
THE SOFTWARE.
*/
-#if !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
+#include "fastlz.h"
+
+#include <stdint.h>
/*
* Always check for bound when decompressing.
* Generally it is best to leave it defined.
*/
#define FASTLZ_SAFE
+#if defined(FASTLZ_USE_SAFE_DECOMPRESSOR) && (FASTLZ_USE_SAFE_DECOMPRESSOR == 0)
+#undef FASTLZ_SAFE
+#endif
/*
* Give hints to the compiler for branch prediction optimization.
*/
-#if defined(__GNUC__) && (__GNUC__ > 2)
-#define FASTLZ_EXPECT_CONDITIONAL(c) (__builtin_expect((c), 1))
-#define FASTLZ_UNEXPECT_CONDITIONAL(c) (__builtin_expect((c), 0))
+#if defined(__clang__) || (defined(__GNUC__) && (__GNUC__ > 2))
+#define FASTLZ_LIKELY(c) (__builtin_expect(!!(c), 1))
+#define FASTLZ_UNLIKELY(c) (__builtin_expect(!!(c), 0))
#else
-#define FASTLZ_EXPECT_CONDITIONAL(c) (c)
-#define FASTLZ_UNEXPECT_CONDITIONAL(c) (c)
+#define FASTLZ_LIKELY(c) (c)
+#define FASTLZ_UNLIKELY(c) (c)
#endif
-/*
- * Use inlined functions for supported systems.
- */
-#if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
-#define FASTLZ_INLINE inline
-#elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
-#define FASTLZ_INLINE __inline
-#else
-#define FASTLZ_INLINE
+#if defined(FASTLZ_SAFE)
+#define FASTLZ_BOUND_CHECK(cond) \
+ if (FASTLZ_UNLIKELY(!(cond))) return 0;
+#else
+#define FASTLZ_BOUND_CHECK(cond) \
+ do { \
+ } while (0)
#endif
-/*
- * Prevent accessing more than 8-bit at once, except on x86 architectures.
- */
-#if !defined(FASTLZ_STRICT_ALIGN)
-#define FASTLZ_STRICT_ALIGN
-#if defined(__i386__) || defined(__386) /* GNU C, Sun Studio */
-#undef FASTLZ_STRICT_ALIGN
-#elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
-#undef FASTLZ_STRICT_ALIGN
-#elif defined(_M_IX86) /* Intel, MSVC */
-#undef FASTLZ_STRICT_ALIGN
-#elif defined(__386)
-#undef FASTLZ_STRICT_ALIGN
-#elif defined(_X86_) /* MinGW */
-#undef FASTLZ_STRICT_ALIGN
-#elif defined(__I86__) /* Digital Mars */
-#undef FASTLZ_STRICT_ALIGN
-#endif
-#endif
+#define MAX_COPY 32
+#define MAX_LEN 264 /* 256 + 8 */
+#define MAX_L1_DISTANCE 8192
+#define MAX_L2_DISTANCE 8191
+#define MAX_FARDISTANCE (65535 + MAX_L2_DISTANCE - 1)
+
+#define FASTLZ_READU16(p) ((p)[0] | (p)[1] << 8)
+
+#define HASH_LOG 13
+#define HASH_SIZE (1 << HASH_LOG)
+#define HASH_MASK (HASH_SIZE - 1)
+#define HASH_FUNCTION(v, p) \
+ { \
+ v = FASTLZ_READU16(p); \
+ v ^= FASTLZ_READU16(p + 1) ^ (v >> (16 - HASH_LOG)); \
+ v &= HASH_MASK; \
+ }
-/*
- * FIXME: use preprocessor magic to set this on different platforms!
- */
-typedef unsigned char flzuint8;
-typedef unsigned short flzuint16;
-typedef unsigned int flzuint32;
+int fastlz1_compress(const void* input, int length, void* output) {
+ const uint8_t* ip = (const uint8_t*)input;
+ const uint8_t* ip_bound = ip + length - 2;
+ const uint8_t* ip_limit = ip + length - 12 - 1;
+ uint8_t* op = (uint8_t*)output;
-/* prototypes */
-int fastlz_compress(const void* input, int length, void* output);
-int fastlz_compress_level(int level, const void* input, int length, void* output);
-int fastlz_decompress(const void* input, int length, void* output, int maxout);
+ const uint8_t* htab[HASH_SIZE];
+ uint32_t hval;
-#define MAX_COPY 32
-#define MAX_LEN 264 /* 256 + 8 */
-#define MAX_DISTANCE 8192
+ uint32_t copy;
-#if !defined(FASTLZ_STRICT_ALIGN)
-#define FASTLZ_READU16(p) *((const flzuint16*)(p))
-#else
-#define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
-#endif
+ /* sanity check */
+ if (FASTLZ_UNLIKELY(length < 4)) {
+ if (length) {
+ /* create literal copy only */
+ *op++ = length - 1;
+ ip_bound++;
+ while (ip <= ip_bound) *op++ = *ip++;
+ return length + 1;
+ } else
+ return 0;
+ }
-#define HASH_LOG 13
-#define HASH_SIZE (1<< HASH_LOG)
-#define HASH_MASK (HASH_SIZE-1)
-#define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
-
-#undef FASTLZ_LEVEL
-#define FASTLZ_LEVEL 1
-
-#undef FASTLZ_COMPRESSOR
-#undef FASTLZ_DECOMPRESSOR
-#define FASTLZ_COMPRESSOR fastlz1_compress
-#define FASTLZ_DECOMPRESSOR fastlz1_decompress
-static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
-static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
-#include "fastlz.c"
-
-#undef FASTLZ_LEVEL
-#define FASTLZ_LEVEL 2
-
-#undef MAX_DISTANCE
-#define MAX_DISTANCE 8191
-#define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
-
-#undef FASTLZ_COMPRESSOR
-#undef FASTLZ_DECOMPRESSOR
-#define FASTLZ_COMPRESSOR fastlz2_compress
-#define FASTLZ_DECOMPRESSOR fastlz2_decompress
-static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
-static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
-#include "fastlz.c"
-
-int fastlz_compress(const void* input, int length, void* output)
-{
- /* for short block, choose fastlz1 */
- if(length < 65536)
- return fastlz1_compress(input, length, output);
+ /* initializes hash table */
+ for (hval = 0; hval < HASH_SIZE; ++hval) htab[hval] = ip;
- /* else... */
- return fastlz2_compress(input, length, output);
+ /* we start with literal copy */
+ copy = 2;
+ *op++ = MAX_COPY - 1;
+ *op++ = *ip++;
+ *op++ = *ip++;
+
+ /* main loop */
+ while (FASTLZ_LIKELY(ip < ip_limit)) {
+ const uint8_t* ref;
+ uint32_t distance;
+
+ /* minimum match length */
+ uint32_t len = 3;
+
+ /* comparison starting-point */
+ const uint8_t* anchor = ip;
+
+ /* find potential match */
+ HASH_FUNCTION(hval, ip);
+ ref = htab[hval];
+
+ /* update hash table */
+ htab[hval] = anchor;
+
+ /* calculate distance to the match */
+ distance = anchor - ref;
+
+ /* is this a match? check the first 3 bytes */
+ if (distance == 0 || (distance >= MAX_L1_DISTANCE) || *ref++ != *ip++ ||
+ *ref++ != *ip++ || *ref++ != *ip++)
+ goto literal;
+
+ /* last matched byte */
+ ip = anchor + len;
+
+ /* distance is biased */
+ distance--;
+
+ if (!distance) {
+ /* zero distance means a run */
+ uint8_t x = ip[-1];
+ while (ip < ip_bound)
+ if (*ref++ != x)
+ break;
+ else
+ ip++;
+ } else
+ for (;;) {
+ /* safe because the outer check against ip limit */
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ while (ip < ip_bound)
+ if (*ref++ != *ip++) break;
+ break;
+ }
+
+ /* if we have copied something, adjust the copy count */
+ if (copy) /* copy is biased, '0' means 1 byte copy */
+ *(op - copy - 1) = copy - 1;
+ else
+ /* back, to overwrite the copy count */
+ op--;
+
+ /* reset literal counter */
+ copy = 0;
+
+ /* length is biased, '1' means a match of 3 bytes */
+ ip -= 3;
+ len = ip - anchor;
+
+ /* encode the match */
+ if (FASTLZ_UNLIKELY(len > MAX_LEN - 2))
+ while (len > MAX_LEN - 2) {
+ *op++ = (7 << 5) + (distance >> 8);
+ *op++ = MAX_LEN - 2 - 7 - 2;
+ *op++ = (distance & 255);
+ len -= MAX_LEN - 2;
+ }
+
+ if (len < 7) {
+ *op++ = (len << 5) + (distance >> 8);
+ *op++ = (distance & 255);
+ } else {
+ *op++ = (7 << 5) + (distance >> 8);
+ *op++ = len - 7;
+ *op++ = (distance & 255);
+ }
+
+ /* update the hash at match boundary */
+ HASH_FUNCTION(hval, ip);
+ htab[hval] = ip++;
+ HASH_FUNCTION(hval, ip);
+ htab[hval] = ip++;
+
+ /* assuming literal copy */
+ *op++ = MAX_COPY - 1;
+
+ continue;
+
+ literal:
+ *op++ = *anchor++;
+ ip = anchor;
+ copy++;
+ if (FASTLZ_UNLIKELY(copy == MAX_COPY)) {
+ copy = 0;
+ *op++ = MAX_COPY - 1;
+ }
+ }
+
+ /* left-over as literal copy */
+ ip_bound++;
+ while (ip <= ip_bound) {
+ *op++ = *ip++;
+ copy++;
+ if (copy == MAX_COPY) {
+ copy = 0;
+ *op++ = MAX_COPY - 1;
+ }
+ }
+
+ /* if we have copied something, adjust the copy length */
+ if (copy)
+ *(op - copy - 1) = copy - 1;
+ else
+ op--;
+
+ return op - (uint8_t*)output;
}
-int fastlz_decompress(const void* input, int length, void* output, int maxout)
-{
- /* magic identifier for compression level */
- int level = ((*(const flzuint8*)input) >> 5) + 1;
+#if defined(FASTLZ_USE_MEMMOVE) && (FASTLZ_USE_MEMMOVE == 0)
- if(level == 1)
- return fastlz1_decompress(input, length, output, maxout);
- if(level == 2)
- return fastlz2_decompress(input, length, output, maxout);
+static void fastlz_memmove(uint8_t* dest, const uint8_t* src, uint32_t count) {
+ do {
+ *dest++ = *src++;
+ } while (--count);
+}
- /* unknown level, trigger error */
- return 0;
+static void fastlz_memcpy(uint8_t* dest, const uint8_t* src, uint32_t count) {
+ return fastlz_memmove(dest, src, count);
}
-int fastlz_compress_level(int level, const void* input, int length, void* output)
-{
- if(level == 1)
- return fastlz1_compress(input, length, output);
- if(level == 2)
- return fastlz2_compress(input, length, output);
+#else
- return 0;
+#include <string.h>
+
+static void fastlz_memmove(uint8_t* dest, const uint8_t* src, uint32_t count) {
+ if ((count > 4) && (dest >= src + count)) {
+ memmove(dest, src, count);
+ } else {
+ switch (count) {
+ default:
+ do {
+ *dest++ = *src++;
+ } while (--count);
+ break;
+ case 3:
+ *dest++ = *src++;
+ case 2:
+ *dest++ = *src++;
+ case 1:
+ *dest++ = *src++;
+ case 0:
+ break;
+ }
+ }
+}
+
+static void fastlz_memcpy(uint8_t* dest, const uint8_t* src, uint32_t count) {
+ memcpy(dest, src, count);
}
-#else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
+#endif
-static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
-{
- const flzuint8* ip = (const flzuint8*) input;
- const flzuint8* ip_bound = ip + length - 2;
- const flzuint8* ip_limit = ip + length - 12;
- flzuint8* op = (flzuint8*) output;
+int fastlz1_decompress(const void* input, int length, void* output,
+ int maxout) {
+ const uint8_t* ip = (const uint8_t*)input;
+ const uint8_t* ip_limit = ip + length;
+ const uint8_t* ip_bound = ip_limit - 2;
+ uint8_t* op = (uint8_t*)output;
+ uint8_t* op_limit = op + maxout;
+ uint32_t ctrl = (*ip++) & 31;
+
+ while (1) {
+ if (ctrl >= 32) {
+ uint32_t len = (ctrl >> 5) - 1;
+ uint32_t ofs = (ctrl & 31) << 8;
+ const uint8_t* ref = op - ofs - 1;
+ if (len == 7 - 1) {
+ FASTLZ_BOUND_CHECK(ip <= ip_bound);
+ len += *ip++;
+ }
+ ref -= *ip++;
+ len += 3;
+ FASTLZ_BOUND_CHECK(op + len <= op_limit);
+ FASTLZ_BOUND_CHECK(ref >= (uint8_t*)output);
+ fastlz_memmove(op, ref, len);
+ op += len;
+ } else {
+ ctrl++;
+ FASTLZ_BOUND_CHECK(op + ctrl <= op_limit);
+ FASTLZ_BOUND_CHECK(ip + ctrl <= ip_limit);
+ fastlz_memcpy(op, ip, ctrl);
+ ip += ctrl;
+ op += ctrl;
+ }
- const flzuint8* htab[HASH_SIZE];
- const flzuint8** hslot;
- flzuint32 hval;
+ if (FASTLZ_UNLIKELY(ip > ip_bound)) break;
+ ctrl = *ip++;
+ }
+
+ return op - (uint8_t*)output;
+}
- flzuint32 copy;
+int fastlz2_compress(const void* input, int length, void* output) {
+ const uint8_t* ip = (const uint8_t*)input;
+ const uint8_t* ip_bound = ip + length - 2;
+ const uint8_t* ip_limit = ip + length - 12 - 1;
+ uint8_t* op = (uint8_t*)output;
+
+ const uint8_t* htab[HASH_SIZE];
+ uint32_t hval;
+
+ uint32_t copy;
/* sanity check */
- if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
- {
- if(length)
- {
+ if (FASTLZ_UNLIKELY(length < 4)) {
+ if (length) {
/* create literal copy only */
- *op++ = length-1;
+ *op++ = length - 1;
ip_bound++;
- while(ip <= ip_bound)
- *op++ = *ip++;
- return length+1;
- }
- else
+ while (ip <= ip_bound) *op++ = *ip++;
+ return length + 1;
+ } else
return 0;
}
/* initializes hash table */
- for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
- *hslot = ip;
+ for (hval = 0; hval < HASH_SIZE; ++hval) htab[hval] = ip;
/* we start with literal copy */
copy = 2;
- *op++ = MAX_COPY-1;
+ *op++ = MAX_COPY - 1;
*op++ = *ip++;
*op++ = *ip++;
/* main loop */
- while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
- {
- const flzuint8* ref;
- flzuint32 distance;
+ while (FASTLZ_LIKELY(ip < ip_limit)) {
+ const uint8_t* ref;
+ uint32_t distance;
/* minimum match length */
- flzuint32 len = 3;
+ uint32_t len = 3;
/* comparison starting-point */
- const flzuint8* anchor = ip;
+ const uint8_t* anchor = ip;
/* check for a run */
-#if FASTLZ_LEVEL==2
- if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
- {
+ if (ip[0] == ip[-1] && ip[0] == ip[1] && ip[1] == ip[2]) {
distance = 1;
ip += 3;
ref = anchor - 1 + 3;
goto match;
}
-#endif
/* find potential match */
- HASH_FUNCTION(hval,ip);
- hslot = htab + hval;
+ HASH_FUNCTION(hval, ip);
ref = htab[hval];
+ /* update hash table */
+ htab[hval] = anchor;
+
/* calculate distance to the match */
distance = anchor - ref;
- /* update hash table */
- *hslot = anchor;
-
/* is this a match? check the first 3 bytes */
- if(distance==0 ||
-#if FASTLZ_LEVEL==1
- (distance >= MAX_DISTANCE) ||
-#else
- (distance >= MAX_FARDISTANCE) ||
-#endif
- *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
+ if (distance == 0 || (distance >= MAX_FARDISTANCE) || *ref++ != *ip++ ||
+ *ref++ != *ip++ || *ref++ != *ip++)
goto literal;
-#if FASTLZ_LEVEL==2
/* far, needs at least 5-byte match */
- if(distance >= MAX_DISTANCE)
- {
- if(*ip++ != *ref++ || *ip++!= *ref++)
- goto literal;
+ if (distance >= MAX_L2_DISTANCE) {
+ if (*ip++ != *ref++ || *ip++ != *ref++) goto literal;
len += 2;
}
-
- match:
-#endif
+
+ match:
/* last matched byte */
ip = anchor + len;
@@ -264,34 +397,33 @@ static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void*
/* distance is biased */
distance--;
- if(!distance)
- {
+ if (!distance) {
/* zero distance means a run */
- flzuint8 x = ip[-1];
- while(ip < ip_bound)
- if(*ref++ != x) break; else ip++;
- }
- else
- for(;;)
- {
- /* safe because the outer check against ip limit */
- if(*ref++ != *ip++) break;
- if(*ref++ != *ip++) break;
- if(*ref++ != *ip++) break;
- if(*ref++ != *ip++) break;
- if(*ref++ != *ip++) break;
- if(*ref++ != *ip++) break;
- if(*ref++ != *ip++) break;
- if(*ref++ != *ip++) break;
- while(ip < ip_bound)
- if(*ref++ != *ip++) break;
- break;
- }
+ uint8_t x = ip[-1];
+ while (ip < ip_bound)
+ if (*ref++ != x)
+ break;
+ else
+ ip++;
+ } else
+ for (;;) {
+ /* safe because the outer check against ip limit */
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ while (ip < ip_bound)
+ if (*ref++ != *ip++) break;
+ break;
+ }
/* if we have copied something, adjust the copy count */
- if(copy)
- /* copy is biased, '0' means 1 byte copy */
- *(op-copy-1) = copy-1;
+ if (copy) /* copy is biased, '0' means 1 byte copy */
+ *(op - copy - 1) = copy - 1;
else
/* back, to overwrite the copy count */
op--;
@@ -304,248 +436,156 @@ static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void*
len = ip - anchor;
/* encode the match */
-#if FASTLZ_LEVEL==2
- if(distance < MAX_DISTANCE)
- {
- if(len < 7)
- {
+ if (distance < MAX_L2_DISTANCE) {
+ if (len < 7) {
*op++ = (len << 5) + (distance >> 8);
*op++ = (distance & 255);
- }
- else
- {
+ } else {
*op++ = (7 << 5) + (distance >> 8);
- for(len-=7; len >= 255; len-= 255)
- *op++ = 255;
+ for (len -= 7; len >= 255; len -= 255) *op++ = 255;
*op++ = len;
*op++ = (distance & 255);
}
- }
- else
- {
+ } else {
/* far away, but not yet in the another galaxy... */
- if(len < 7)
- {
- distance -= MAX_DISTANCE;
+ if (len < 7) {
+ distance -= MAX_L2_DISTANCE;
*op++ = (len << 5) + 31;
*op++ = 255;
*op++ = distance >> 8;
*op++ = distance & 255;
- }
- else
- {
- distance -= MAX_DISTANCE;
+ } else {
+ distance -= MAX_L2_DISTANCE;
*op++ = (7 << 5) + 31;
- for(len-=7; len >= 255; len-= 255)
- *op++ = 255;
+ for (len -= 7; len >= 255; len -= 255) *op++ = 255;
*op++ = len;
*op++ = 255;
*op++ = distance >> 8;
*op++ = distance & 255;
}
}
-#else
-
- if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
- while(len > MAX_LEN-2)
- {
- *op++ = (7 << 5) + (distance >> 8);
- *op++ = MAX_LEN - 2 - 7 -2;
- *op++ = (distance & 255);
- len -= MAX_LEN-2;
- }
-
- if(len < 7)
- {
- *op++ = (len << 5) + (distance >> 8);
- *op++ = (distance & 255);
- }
- else
- {
- *op++ = (7 << 5) + (distance >> 8);
- *op++ = len - 7;
- *op++ = (distance & 255);
- }
-#endif
/* update the hash at match boundary */
- HASH_FUNCTION(hval,ip);
+ HASH_FUNCTION(hval, ip);
htab[hval] = ip++;
- HASH_FUNCTION(hval,ip);
+ HASH_FUNCTION(hval, ip);
htab[hval] = ip++;
/* assuming literal copy */
- *op++ = MAX_COPY-1;
+ *op++ = MAX_COPY - 1;
continue;
- literal:
- *op++ = *anchor++;
- ip = anchor;
- copy++;
- if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
- {
- copy = 0;
- *op++ = MAX_COPY-1;
- }
+ literal:
+ *op++ = *anchor++;
+ ip = anchor;
+ copy++;
+ if (FASTLZ_UNLIKELY(copy == MAX_COPY)) {
+ copy = 0;
+ *op++ = MAX_COPY - 1;
+ }
}
/* left-over as literal copy */
ip_bound++;
- while(ip <= ip_bound)
- {
+ while (ip <= ip_bound) {
*op++ = *ip++;
copy++;
- if(copy == MAX_COPY)
- {
+ if (copy == MAX_COPY) {
copy = 0;
- *op++ = MAX_COPY-1;
+ *op++ = MAX_COPY - 1;
}
}
/* if we have copied something, adjust the copy length */
- if(copy)
- *(op-copy-1) = copy-1;
+ if (copy)
+ *(op - copy - 1) = copy - 1;
else
op--;
-#if FASTLZ_LEVEL==2
/* marker for fastlz2 */
- *(flzuint8*)output |= (1 << 5);
-#endif
+ *(uint8_t*)output |= (1 << 5);
- return op - (flzuint8*)output;
+ return op - (uint8_t*)output;
}
-static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
-{
- const flzuint8* ip = (const flzuint8*) input;
- const flzuint8* ip_limit = ip + length;
- flzuint8* op = (flzuint8*) output;
- flzuint8* op_limit = op + maxout;
- flzuint32 ctrl = (*ip++) & 31;
- int loop = 1;
-
- do
- {
- const flzuint8* ref = op;
- flzuint32 len = ctrl >> 5;
- flzuint32 ofs = (ctrl & 31) << 8;
-
- if(ctrl >= 32)
- {
-#if FASTLZ_LEVEL==2
- flzuint8 code;
-#endif
- len--;
- ref -= ofs;
- if (len == 7-1)
-#if FASTLZ_LEVEL==1
- len += *ip++;
- ref -= *ip++;
-#else
- do
- {
+int fastlz2_decompress(const void* input, int length, void* output,
+ int maxout) {
+ const uint8_t* ip = (const uint8_t*)input;
+ const uint8_t* ip_limit = ip + length;
+ const uint8_t* ip_bound = ip_limit - 2;
+ uint8_t* op = (uint8_t*)output;
+ uint8_t* op_limit = op + maxout;
+ uint32_t ctrl = (*ip++) & 31;
+
+ while (1) {
+ if (ctrl >= 32) {
+ uint32_t len = (ctrl >> 5) - 1;
+ uint32_t ofs = (ctrl & 31) << 8;
+ const uint8_t* ref = op - ofs - 1;
+
+ uint8_t code;
+ if (len == 7 - 1) do {
+ FASTLZ_BOUND_CHECK(ip <= ip_bound);
code = *ip++;
len += code;
- } while (code==255);
+ } while (code == 255);
code = *ip++;
ref -= code;
+ len += 3;
/* match from 16-bit distance */
- if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
- if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
- {
- ofs = (*ip++) << 8;
- ofs += *ip++;
- ref = op - ofs - MAX_DISTANCE;
- }
-#endif
-
-#ifdef FASTLZ_SAFE
- if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
- return 0;
-
- if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
- return 0;
-#endif
-
- if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
- ctrl = *ip++;
- else
- loop = 0;
-
- if(ref == op)
- {
- /* optimize copy for a run */
- flzuint8 b = ref[-1];
- *op++ = b;
- *op++ = b;
- *op++ = b;
- for(; len; --len)
- *op++ = b;
- }
- else
- {
-#if !defined(FASTLZ_STRICT_ALIGN)
- const flzuint16* p;
- flzuint16* q;
-#endif
- /* copy from reference */
- ref--;
- *op++ = *ref++;
- *op++ = *ref++;
- *op++ = *ref++;
-
-#if !defined(FASTLZ_STRICT_ALIGN)
- /* copy a byte, so that now it's word aligned */
- if(len & 1)
- {
- *op++ = *ref++;
- len--;
+ if (FASTLZ_UNLIKELY(code == 255))
+ if (FASTLZ_LIKELY(ofs == (31 << 8))) {
+ FASTLZ_BOUND_CHECK(ip < ip_bound);
+ ofs = (*ip++) << 8;
+ ofs += *ip++;
+ ref = op - ofs - MAX_L2_DISTANCE - 1;
}
- /* copy 16-bit at once */
- q = (flzuint16*) op;
- op += len;
- p = (const flzuint16*) ref;
- for(len>>=1; len > 4; len-=4)
- {
- *q++ = *p++;
- *q++ = *p++;
- *q++ = *p++;
- *q++ = *p++;
- }
- for(; len; --len)
- *q++ = *p++;
-#else
- for(; len; --len)
- *op++ = *ref++;
-#endif
- }
- }
- else
- {
+ FASTLZ_BOUND_CHECK(op + len <= op_limit);
+ FASTLZ_BOUND_CHECK(ref >= (uint8_t*)output);
+ fastlz_memmove(op, ref, len);
+ op += len;
+ } else {
ctrl++;
-#ifdef FASTLZ_SAFE
- if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
- return 0;
- if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
- return 0;
-#endif
-
- *op++ = *ip++;
- for(--ctrl; ctrl; ctrl--)
- *op++ = *ip++;
-
- loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
- if(loop)
- ctrl = *ip++;
+ FASTLZ_BOUND_CHECK(op + ctrl <= op_limit);
+ FASTLZ_BOUND_CHECK(ip + ctrl <= ip_limit);
+ fastlz_memcpy(op, ip, ctrl);
+ ip += ctrl;
+ op += ctrl;
}
+
+ if (FASTLZ_UNLIKELY(ip >= ip_limit)) break;
+ ctrl = *ip++;
}
- while(FASTLZ_EXPECT_CONDITIONAL(loop));
- return op - (flzuint8*)output;
+ return op - (uint8_t*)output;
}
-#endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
+int fastlz_compress(const void* input, int length, void* output) {
+ /* for short block, choose fastlz1 */
+ if (length < 65536) return fastlz1_compress(input, length, output);
+
+ /* else... */
+ return fastlz2_compress(input, length, output);
+}
+
+int fastlz_decompress(const void* input, int length, void* output, int maxout) {
+ /* magic identifier for compression level */
+ int level = ((*(const uint8_t*)input) >> 5) + 1;
+
+ if (level == 1) return fastlz1_decompress(input, length, output, maxout);
+ if (level == 2) return fastlz2_decompress(input, length, output, maxout);
+
+ /* unknown level, trigger error */
+ return 0;
+}
+
+int fastlz_compress_level(int level, const void* input, int length,
+ void* output) {
+ if (level == 1) return fastlz1_compress(input, length, output);
+ if (level == 2) return fastlz2_compress(input, length, output);
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-15 23:29:18 +0000