LCOV - code coverage report
Current view: top level - lunchbox/compressor/fastlz - fastlz.c (source / functions) Hit Total Coverage
Test: lcov2.info Lines: 178 197 90.4 %
Date: 2014-10-01 Functions: 6 7 85.7 %

          Line data    Source code
       1             : /*  
       2             :   FastLZ - lightning-fast lossless compression library
       3             : 
       4             :   Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
       5             :   Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
       6             :   Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
       7             : 
       8             :   Permission is hereby granted, free of charge, to any person obtaining a copy
       9             :   of this software and associated documentation files (the "Software"), to deal
      10             :   in the Software without restriction, including without limitation the rights
      11             :   to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
      12             :   copies of the Software, and to permit persons to whom the Software is
      13             :   furnished to do so, subject to the following conditions:
      14             : 
      15             :   The above copyright notice and this permission notice shall be included in
      16             :   all copies or substantial portions of the Software.
      17             : 
      18             :   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      19             :   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      20             :   FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
      21             :   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      22             :   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
      23             :   OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
      24             :   THE SOFTWARE.
      25             : */
      26             : 
      27             : #if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
      28             : 
      29             : /*
      30             :  * Always check for bound when decompressing.
      31             :  * Generally it is best to leave it defined.
      32             :  */
      33             : #define FASTLZ_SAFE
      34             : 
      35             : /*
      36             :  * Give hints to the compiler for branch prediction optimization.
      37             :  */
      38             : #if defined(__GNUC__) && (__GNUC__ > 2)
      39             : #define FASTLZ_EXPECT_CONDITIONAL(c)    (__builtin_expect((c), 1))
      40             : #define FASTLZ_UNEXPECT_CONDITIONAL(c)  (__builtin_expect((c), 0))
      41             : #else
      42             : #define FASTLZ_EXPECT_CONDITIONAL(c)    (c)
      43             : #define FASTLZ_UNEXPECT_CONDITIONAL(c)  (c)
      44             : #endif
      45             : 
      46             : /*
      47             :  * Use inlined functions for supported systems.
      48             :  */
      49             : #if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
      50             : #define FASTLZ_INLINE inline
      51             : #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
      52             : #define FASTLZ_INLINE __inline
      53             : #else 
      54             : #define FASTLZ_INLINE
      55             : #endif
      56             : 
      57             : /*
      58             :  * Prevent accessing more than 8-bit at once, except on x86 architectures.
      59             :  */
      60             : #if !defined(FASTLZ_STRICT_ALIGN)
      61             : #define FASTLZ_STRICT_ALIGN
      62             : #if defined(__i386__) || defined(__386)  /* GNU C, Sun Studio */
      63             : #undef FASTLZ_STRICT_ALIGN
      64             : #elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
      65             : #undef FASTLZ_STRICT_ALIGN
      66             : #elif defined(_M_IX86) /* Intel, MSVC */
      67             : #undef FASTLZ_STRICT_ALIGN
      68             : #elif defined(__386)
      69             : #undef FASTLZ_STRICT_ALIGN
      70             : #elif defined(_X86_) /* MinGW */
      71             : #undef FASTLZ_STRICT_ALIGN
      72             : #elif defined(__I86__) /* Digital Mars */
      73             : #undef FASTLZ_STRICT_ALIGN
      74             : #endif
      75             : #endif
      76             : 
      77             : /*
      78             :  * FIXME: use preprocessor magic to set this on different platforms!
      79             :  */
      80             : typedef unsigned char  flzuint8;
      81             : typedef unsigned short flzuint16;
      82             : typedef unsigned int   flzuint32;
      83             : 
      84             : /* prototypes */
      85             : int fastlz_compress(const void* input, int length, void* output);
      86             : int fastlz_compress_level(int level, const void* input, int length, void* output);
      87             : int fastlz_decompress(const void* input, int length, void* output, int maxout);
      88             : 
      89             : #define MAX_COPY       32
      90             : #define MAX_LEN       264  /* 256 + 8 */
      91             : #define MAX_DISTANCE 8192
      92             : 
      93             : #if !defined(FASTLZ_STRICT_ALIGN)
      94             : #define FASTLZ_READU16(p) *((const flzuint16*)(p)) 
      95             : #else
      96             : #define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
      97             : #endif
      98             : 
      99             : #define HASH_LOG  13
     100             : #define HASH_SIZE (1<< HASH_LOG)
     101             : #define HASH_MASK  (HASH_SIZE-1)
     102             : #define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
     103             : 
     104             : #undef FASTLZ_LEVEL
     105             : #define FASTLZ_LEVEL 1
     106             : 
     107             : #undef FASTLZ_COMPRESSOR
     108             : #undef FASTLZ_DECOMPRESSOR
     109             : #define FASTLZ_COMPRESSOR fastlz1_compress
     110             : #define FASTLZ_DECOMPRESSOR fastlz1_decompress
     111             : static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
     112             : static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
     113             : #include "fastlz.c"
     114             : 
     115             : #undef FASTLZ_LEVEL
     116             : #define FASTLZ_LEVEL 2
     117             : 
     118             : #undef MAX_DISTANCE
     119             : #define MAX_DISTANCE 8191
     120             : #define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
     121             : 
     122             : #undef FASTLZ_COMPRESSOR
     123             : #undef FASTLZ_DECOMPRESSOR
     124             : #define FASTLZ_COMPRESSOR fastlz2_compress
     125             : #define FASTLZ_DECOMPRESSOR fastlz2_decompress
     126             : static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
     127             : static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
     128             : #include "fastlz.c"
     129             : 
     130          76 : int fastlz_compress(const void* input, int length, void* output)
     131             : {
     132             :   /* for short block, choose fastlz1 */
     133          76 :   if(length < 65536)
     134           2 :     return fastlz1_compress(input, length, output);
     135             : 
     136             :   /* else... */
     137          74 :   return fastlz2_compress(input, length, output);
     138             : }
     139             : 
     140          76 : int fastlz_decompress(const void* input, int length, void* output, int maxout)
     141             : {
     142             :   /* magic identifier for compression level */
     143          76 :   int level = ((*(const flzuint8*)input) >> 5) + 1;
     144             : 
     145          76 :   if(level == 1)
     146           2 :     return fastlz1_decompress(input, length, output, maxout);
     147          74 :   if(level == 2)
     148          74 :     return fastlz2_decompress(input, length, output, maxout);
     149             : 
     150             :   /* unknown level, trigger error */
     151           0 :   return 0;
     152             : }
     153             : 
     154           0 : int fastlz_compress_level(int level, const void* input, int length, void* output)
     155             : {
     156           0 :   if(level == 1)
     157           0 :     return fastlz1_compress(input, length, output);
     158           0 :   if(level == 2)
     159           0 :     return fastlz2_compress(input, length, output);
     160             : 
     161           0 :   return 0;
     162             : }
     163             : 
     164             : #else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
     165             : 
     166          76 : static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
     167             : {
     168          76 :   const flzuint8* ip = (const flzuint8*) input;
     169          76 :   const flzuint8* ip_bound = ip + length - 2;
     170          76 :   const flzuint8* ip_limit = ip + length - 12;
     171          76 :   flzuint8* op = (flzuint8*) output;
     172             : 
     173             :   const flzuint8* htab[HASH_SIZE];
     174             :   const flzuint8** hslot;
     175             :   flzuint32 hval;
     176             : 
     177             :   flzuint32 copy;
     178             : 
     179             :   /* sanity check */
     180          76 :   if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
     181             :   {
     182           0 :     if(length)
     183             :     {
     184             :       /* create literal copy only */
     185           0 :       *op++ = length-1;
     186           0 :       ip_bound++;
     187           0 :       while(ip <= ip_bound)
     188           0 :         *op++ = *ip++;
     189           0 :       return length+1;
     190             :     }
     191             :     else
     192           0 :       return 0;
     193             :   }
     194             : 
     195             :   /* initializes hash table */
     196      622668 :   for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
     197      622592 :     *hslot = ip;
     198             : 
     199             :   /* we start with literal copy */
     200          76 :   copy = 2;
     201          76 :   *op++ = MAX_COPY-1;
     202          76 :   *op++ = *ip++;
     203          76 :   *op++ = *ip++;
     204             : 
     205             :   /* main loop */
     206   235404546 :   while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
     207             :   {
     208             :     const flzuint8* ref;
     209             :     flzuint32 distance;
     210             : 
     211             :     /* minimum match length */
     212   235404394 :     flzuint32 len = 3;
     213             : 
     214             :     /* comparison starting-point */
     215   235404394 :     const flzuint8* anchor = ip;
     216             : 
     217             :     /* check for a run */
     218             : #if FASTLZ_LEVEL==2
     219   235382904 :     if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
     220             :     {
     221      541240 :       distance = 1;
     222      541240 :       ip += 3;
     223      541240 :       ref = anchor - 1 + 3;
     224      541240 :       goto match;
     225             :     }
     226             : #endif
     227             : 
     228             :     /* find potential match */
     229   234863154 :     HASH_FUNCTION(hval,ip);
     230   234863154 :     hslot = htab + hval;
     231   234863154 :     ref = htab[hval];
     232             : 
     233             :     /* calculate distance to the match */
     234   234863154 :     distance = anchor - ref;
     235             : 
     236             :     /* update hash table */
     237   234863154 :     *hslot = anchor;
     238             : 
     239             :     /* is this a match? check the first 3 bytes */
     240   234863154 :     if(distance==0 || 
     241             : #if FASTLZ_LEVEL==1
     242       14228 :     (distance >= MAX_DISTANCE) ||
     243             : #else
     244   232768670 :     (distance >= MAX_FARDISTANCE) ||
     245             : #endif
     246   254838734 :     *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
     247             :       goto literal;
     248             : 
     249             : #if FASTLZ_LEVEL==2
     250             :     /* far, needs at least 5-byte match */
     251    18965220 :     if(distance >= MAX_DISTANCE)
     252             :     {
     253     2218332 :       if(*ip++ != *ref++ || *ip++!= *ref++) 
     254             :         goto literal;
     255      933050 :       len += 2;
     256             :     }
     257             :     
     258             :     match:
     259             : #endif
     260             : 
     261             :     /* last matched byte */
     262    18229608 :     ip = anchor + len;
     263             : 
     264             :     /* distance is biased */
     265    18229608 :     distance--;
     266             : 
     267    18229608 :     if(!distance)
     268             :     {
     269             :       /* zero distance means a run */
     270      541646 :       flzuint8 x = ip[-1];
     271     2723766 :       while(ip < ip_bound)
     272     2182120 :         if(*ref++ != x) break; else ip++;
     273             :     }
     274             :     else
     275             :     for(;;)
     276             :     {
     277             :       /* safe because the outer check against ip limit */
     278    17687962 :       if(*ref++ != *ip++) break;
     279    11535022 :       if(*ref++ != *ip++) break;
     280     8562518 :       if(*ref++ != *ip++) break;
     281     6540330 :       if(*ref++ != *ip++) break;
     282     4854360 :       if(*ref++ != *ip++) break;
     283     3408208 :       if(*ref++ != *ip++) break;
     284     2651104 :       if(*ref++ != *ip++) break;
     285     2329690 :       if(*ref++ != *ip++) break;
     286    32826422 :       while(ip < ip_bound)
     287    30787200 :         if(*ref++ != *ip++) break;
     288     2039214 :       break;
     289             :     }
     290             : 
     291             :     /* if we have copied something, adjust the copy count */
     292    18229608 :     if(copy)
     293             :       /* copy is biased, '0' means 1 byte copy */
     294    10018162 :       *(op-copy-1) = copy-1;
     295             :     else
     296             :       /* back, to overwrite the copy count */
     297     8211446 :       op--;
     298             : 
     299             :     /* reset literal counter */
     300    18229608 :     copy = 0;
     301             : 
     302             :     /* length is biased, '1' means a match of 3 bytes */
     303    18229608 :     ip -= 3;
     304    18229608 :     len = ip - anchor;
     305             : 
     306             :     /* encode the match */
     307             : #if FASTLZ_LEVEL==2
     308    18221178 :     if(distance < MAX_DISTANCE)
     309             :     {
     310    17288190 :       if(len < 7)
     311             :       {
     312    14904768 :         *op++ = (len << 5) + (distance >> 8);
     313    14904768 :         *op++ = (distance & 255);
     314             :       }
     315             :       else
     316             :       {
     317     2383422 :         *op++ = (7 << 5) + (distance >> 8);
     318     2390290 :         for(len-=7; len >= 255; len-= 255)
     319        6868 :           *op++ = 255;
     320     2383422 :         *op++ = len;
     321     2383422 :         *op++ = (distance & 255);
     322             :       }
     323             :     }
     324             :     else
     325             :     {
     326             :       /* far away, but not yet in the another galaxy... */
     327      932988 :       if(len < 7)
     328             :       {
     329      554264 :         distance -= MAX_DISTANCE;
     330      554264 :         *op++ = (len << 5) + 31;
     331      554264 :         *op++ = 255;
     332      554264 :         *op++ = distance >> 8;
     333      554264 :         *op++ = distance & 255;
     334             :       }
     335             :       else
     336             :       {
     337      378724 :         distance -= MAX_DISTANCE;
     338      378724 :         *op++ = (7 << 5) + 31;
     339      394076 :         for(len-=7; len >= 255; len-= 255)
     340       15352 :           *op++ = 255;
     341      378724 :         *op++ = len;
     342      378724 :         *op++ = 255;
     343      378724 :         *op++ = distance >> 8;
     344      378724 :         *op++ = distance & 255;
     345             :       }
     346             :     }
     347             : #else
     348             : 
     349        8430 :     if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
     350          26 :       while(len > MAX_LEN-2)
     351             :       {
     352          22 :         *op++ = (7 << 5) + (distance >> 8);
     353          22 :         *op++ = MAX_LEN - 2 - 7 -2; 
     354          22 :         *op++ = (distance & 255);
     355          22 :         len -= MAX_LEN-2;
     356             :       }
     357             : 
     358        8430 :     if(len < 7)
     359             :     {
     360        7422 :       *op++ = (len << 5) + (distance >> 8);
     361        7422 :       *op++ = (distance & 255);
     362             :     }
     363             :     else
     364             :     {
     365        1008 :       *op++ = (7 << 5) + (distance >> 8);
     366        1008 :       *op++ = len - 7;
     367        1008 :       *op++ = (distance & 255);
     368             :     }
     369             : #endif
     370             : 
     371             :     /* update the hash at match boundary */
     372    18229608 :     HASH_FUNCTION(hval,ip);
     373    18229608 :     htab[hval] = ip++;
     374    18229608 :     HASH_FUNCTION(hval,ip);
     375    18229608 :     htab[hval] = ip++;
     376             : 
     377             :     /* assuming literal copy */
     378    18229608 :     *op++ = MAX_COPY-1;
     379             : 
     380    18229608 :     continue;
     381             : 
     382             :     literal:
     383   217174786 :       *op++ = *anchor++;
     384   217174786 :       ip = anchor;
     385   217174786 :       copy++;
     386   217174786 :       if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
     387             :       {
     388     6019500 :         copy = 0;
     389     6019500 :         *op++ = MAX_COPY-1;
     390             :       }
     391             :   }
     392             : 
     393             :   /* left-over as literal copy */
     394          76 :   ip_bound++;
     395         804 :   while(ip <= ip_bound)
     396             :   {
     397         652 :     *op++ = *ip++;
     398         652 :     copy++;
     399         652 :     if(copy == MAX_COPY)
     400             :     {
     401          10 :       copy = 0;
     402          10 :       *op++ = MAX_COPY-1;
     403             :     }
     404             :   }
     405             : 
     406             :   /* if we have copied something, adjust the copy length */
     407          76 :   if(copy)
     408          74 :     *(op-copy-1) = copy-1;
     409             :   else
     410           2 :     op--;
     411             : 
     412             : #if FASTLZ_LEVEL==2
     413             :   /* marker for fastlz2 */
     414          74 :   *(flzuint8*)output |= (1 << 5);
     415             : #endif
     416             : 
     417          76 :   return op - (flzuint8*)output;
     418             : }
     419             : 
     420          76 : static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
     421             : {
     422          76 :   const flzuint8* ip = (const flzuint8*) input;
     423          76 :   const flzuint8* ip_limit  = ip + length;
     424          76 :   flzuint8* op = (flzuint8*) output;
     425          76 :   flzuint8* op_limit = op + maxout;
     426          76 :   flzuint32 ctrl = (*ip++) & 31;
     427          76 :   int loop = 1;
     428             : 
     429             :   do
     430             :   {
     431    34267376 :     const flzuint8* ref = op;
     432    34267376 :     flzuint32 len = ctrl >> 5;
     433    34267376 :     flzuint32 ofs = (ctrl & 31) << 8;
     434             : 
     435    34267376 :     if(ctrl >= 32)
     436             :     {
     437             : #if FASTLZ_LEVEL==2
     438             :       flzuint8 code;
     439             : #endif
     440    18229630 :       len--;
     441    18229630 :       ref -= ofs;
     442    18229630 :       if (len == 7-1)
     443             : #if FASTLZ_LEVEL==1
     444        1030 :         len += *ip++;
     445        8452 :       ref -= *ip++;
     446             : #else
     447             :         do
     448             :         {
     449     2784366 :           code = *ip++;
     450     2784366 :           len += code;
     451     2784366 :         } while (code==255);
     452    18221178 :       code = *ip++;
     453    18221178 :       ref -= code;
     454             : 
     455             :       /* match from 16-bit distance */
     456    18221178 :       if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
     457     1153186 :       if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
     458             :       {
     459      932988 :         ofs = (*ip++) << 8;
     460      932988 :         ofs += *ip++;
     461      932988 :         ref = op - ofs - MAX_DISTANCE;
     462             :       }
     463             : #endif
     464             :       
     465             : #ifdef FASTLZ_SAFE
     466    18229630 :       if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
     467           0 :         return 0;
     468             : 
     469    18229630 :       if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
     470           0 :         return 0;
     471             : #endif
     472             : 
     473    18229630 :       if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
     474    18229630 :         ctrl = *ip++;
     475             :       else
     476           0 :         loop = 0;
     477             : 
     478    18229630 :       if(ref == op)
     479             :       {
     480             :         /* optimize copy for a run */
     481      541668 :         flzuint8 b = ref[-1];
     482      541668 :         *op++ = b;
     483      541668 :         *op++ = b;
     484      541668 :         *op++ = b;
     485     1640430 :         for(; len; --len)
     486     1098762 :           *op++ = b;
     487             :       }
     488             :       else
     489             :       {
     490             : #if !defined(FASTLZ_STRICT_ALIGN)
     491             :         const flzuint16* p;
     492             :         flzuint16* q;
     493             : #endif
     494             :         /* copy from reference */
     495    17687962 :         ref--;
     496    17687962 :         *op++ = *ref++;
     497    17687962 :         *op++ = *ref++;
     498    17687962 :         *op++ = *ref++;
     499             : 
     500             : #if !defined(FASTLZ_STRICT_ALIGN)
     501             :         /* copy a byte, so that now it's word aligned */
     502             :         if(len & 1)
     503             :         {
     504             :           *op++ = *ref++;
     505             :           len--;
     506             :         }
     507             : 
     508             :         /* copy 16-bit at once */
     509             :         q = (flzuint16*) op;
     510             :         op += len;
     511             :         p = (const flzuint16*) ref;
     512             :         for(len>>=1; len > 4; len-=4)
     513             :         {
     514             :           *q++ = *p++;
     515             :           *q++ = *p++;
     516             :           *q++ = *p++;
     517             :           *q++ = *p++;
     518             :         }
     519             :         for(; len; --len)
     520             :           *q++ = *p++;
     521             : #else
     522    90222494 :         for(; len; --len)
     523    72534532 :           *op++ = *ref++;
     524             : #endif
     525             :       }
     526             :     }
     527             :     else
     528             :     {
     529    16037746 :       ctrl++;
     530             : #ifdef FASTLZ_SAFE
     531    16037746 :       if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
     532           0 :         return 0;
     533    16037746 :       if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
     534           0 :         return 0;
     535             : #endif
     536             : 
     537    16037746 :       *op++ = *ip++; 
     538   217175590 :       for(--ctrl; ctrl; ctrl--)
     539   201137844 :         *op++ = *ip++;
     540             : 
     541    16037746 :       loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
     542    16037746 :       if(loop)
     543    16037670 :         ctrl = *ip++;
     544             :     }
     545             :   }
     546    34267376 :   while(FASTLZ_EXPECT_CONDITIONAL(loop));
     547             : 
     548          76 :   return op - (flzuint8*)output;
     549             : }
     550             : 
     551             : #endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */

Generated by: LCOV version 1.10