From 7fe60435bce6595a9c58a9bfd8244d74b5320e96 Mon Sep 17 00:00:00 2001 From: Benjamin Franzke Date: Tue, 15 Jan 2013 08:46:13 +0100 Subject: Import DirectFB141_2k11R3_beta5 --- Source/DirectFB/lib/direct/flz.c | 555 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 555 insertions(+) create mode 100755 Source/DirectFB/lib/direct/flz.c (limited to 'Source/DirectFB/lib/direct/flz.c') diff --git a/Source/DirectFB/lib/direct/flz.c b/Source/DirectFB/lib/direct/flz.c new file mode 100755 index 0000000..070bbe2 --- /dev/null +++ b/Source/DirectFB/lib/direct/flz.c @@ -0,0 +1,555 @@ +/* + 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) + + Permission is hereby granted, free of charge, to any person obtaining a copy + of this software and associated documentation files (the "Software"), to deal + in the Software without restriction, including without limitation the rights + to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + copies of the Software, and to permit persons to whom the Software is + furnished to do so, subject to the following conditions: + + The above copyright notice and this permission notice shall be included in + all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + THE SOFTWARE. +*/ + +#if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) + +/* + * Always check for bound when decompressing. + * Generally it is best to leave it defined. + */ +#define FASTLZ_SAFE + +/* + * 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)) +#else +#define FASTLZ_EXPECT_CONDITIONAL(c) (c) +#define FASTLZ_UNEXPECT_CONDITIONAL(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 +#endif + +/* + * Prevent accessing more than 8-bit at once, except on x86 architectures. + */ +#if !defined(FASTLZ_STRICT_ALIGN) +#define FASTLZ_STRICT_ALIGN + +#if 0 +#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 + +#endif + +/* + * FIXME: use preprocessor magic to set this on different platforms! + */ +typedef unsigned char flzuint8; +typedef unsigned short flzuint16; +typedef unsigned int flzuint32; + +/* 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); + +#define MAX_COPY 32 +#define MAX_LEN 264 /* 256 + 8 */ +#define MAX_DISTANCE 8192 + +#if !defined(FASTLZ_STRICT_ALIGN) +#define FASTLZ_READU16(p) *((const flzuint16*)(p)) +#else +#define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8) +#endif + +#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 "flz.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 "flz.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); + + /* 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 flzuint8*)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; +} + +#else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */ + +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; + + const flzuint8* htab[HASH_SIZE]; + const flzuint8** hslot; + flzuint32 hval; + + flzuint32 copy; + + /* sanity check */ + if(FASTLZ_UNEXPECT_CONDITIONAL(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; + } + + /* initializes hash table */ + for (hslot = htab; hslot < htab + HASH_SIZE; hslot++) + *hslot = ip; + + /* we start with literal copy */ + copy = 2; + *op++ = MAX_COPY-1; + *op++ = *ip++; + *op++ = *ip++; + + /* main loop */ + while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit)) + { + const flzuint8* ref; + flzuint32 distance; + + /* minimum match length */ + flzuint32 len = 3; + + /* comparison starting-point */ + const flzuint8* anchor = ip; + + /* check for a run */ +#if FASTLZ_LEVEL==2 + if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1)) + { + distance = 1; + ip += 3; + ref = anchor - 1 + 3; + goto match; + } +#endif + + /* find potential match */ + HASH_FUNCTION(hval,ip); + hslot = htab + hval; + ref = htab[hval]; + + /* 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++) + goto literal; + +#if FASTLZ_LEVEL==2 + /* far, needs at least 5-byte match */ + if(distance >= MAX_DISTANCE) + { + if(*ip++ != *ref++ || *ip++!= *ref++) + goto literal; + len += 2; + } + + match: +#endif + + /* last matched byte */ + ip = anchor + len; + + /* distance is biased */ + 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; + } + + /* 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_LEVEL==2 + if(distance < MAX_DISTANCE) + { + if(len < 7) + { + *op++ = (len << 5) + (distance >> 8); + *op++ = (distance & 255); + } + else + { + *op++ = (7 << 5) + (distance >> 8); + for(len-=7; len >= 255; len-= 255) + *op++ = 255; + *op++ = len; + *op++ = (distance & 255); + } + } + else + { + /* far away, but not yet in the another galaxy... */ + if(len < 7) + { + distance -= MAX_DISTANCE; + *op++ = (len << 5) + 31; + *op++ = 255; + *op++ = distance >> 8; + *op++ = distance & 255; + } + else + { + distance -= MAX_DISTANCE; + *op++ = (7 << 5) + 31; + 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); + 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_UNEXPECT_CONDITIONAL(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--; + +#if FASTLZ_LEVEL==2 + /* marker for fastlz2 */ + *(flzuint8*)output |= (1 << 5); +#endif + + return op - (flzuint8*)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 + { + code = *ip++; + len += code; + } while (code==255); + code = *ip++; + ref -= code; + + /* 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--; + } + + /* 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 + { + 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++; + } + } + while(FASTLZ_EXPECT_CONDITIONAL(loop)); + + return op - (flzuint8*)output; +} + +#endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */ -- cgit