LCOV - code coverage report
Current view: top level - lunchbox/compressor/liblzf - lzf_c.c (source / functions) Hit Total Coverage
Test: lcov2.info Lines: 78 83 94.0 %
Date: 2014-10-01 Functions: 1 1 100.0 %

          Line data    Source code
       1             : /*
       2             :  * Copyright (c) 2000-2010 Marc Alexander Lehmann <schmorp@schmorp.de>
       3             :  * 
       4             :  * Redistribution and use in source and binary forms, with or without modifica-
       5             :  * tion, are permitted provided that the following conditions are met:
       6             :  * 
       7             :  *   1.  Redistributions of source code must retain the above copyright notice,
       8             :  *       this list of conditions and the following disclaimer.
       9             :  * 
      10             :  *   2.  Redistributions in binary form must reproduce the above copyright
      11             :  *       notice, this list of conditions and the following disclaimer in the
      12             :  *       documentation and/or other materials provided with the distribution.
      13             :  * 
      14             :  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
      15             :  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
      16             :  * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO
      17             :  * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
      18             :  * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
      19             :  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
      20             :  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
      21             :  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
      22             :  * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
      23             :  * OF THE POSSIBILITY OF SUCH DAMAGE.
      24             :  *
      25             :  * Alternatively, the contents of this file may be used under the terms of
      26             :  * the GNU General Public License ("GPL") version 2 or any later version,
      27             :  * in which case the provisions of the GPL are applicable instead of
      28             :  * the above. If you wish to allow the use of your version of this file
      29             :  * only under the terms of the GPL and not to allow others to use your
      30             :  * version of this file under the BSD license, indicate your decision
      31             :  * by deleting the provisions above and replace them with the notice
      32             :  * and other provisions required by the GPL. If you do not delete the
      33             :  * provisions above, a recipient may use your version of this file under
      34             :  * either the BSD or the GPL.
      35             :  */
      36             : 
      37             : #include "lzfP.h"
      38             : 
      39             : #define HSIZE (1 << (HLOG))
      40             : 
      41             : /*
      42             :  * don't play with this unless you benchmark!
      43             :  * the data format is not dependent on the hash function.
      44             :  * the hash function might seem strange, just believe me,
      45             :  * it works ;)
      46             :  */
      47             : #ifndef FRST
      48             : # define FRST(p) (((p[0]) << 8) | p[1])
      49             : # define NEXT(v,p) (((v) << 8) | p[2])
      50             : # if ULTRA_FAST
      51             : #  define IDX(h) ((( h             >> (3*8 - HLOG)) - h  ) & (HSIZE - 1))
      52             : # elif VERY_FAST
      53             : #  define IDX(h) ((( h             >> (3*8 - HLOG)) - h*5) & (HSIZE - 1))
      54             : # else
      55             : #  define IDX(h) ((((h ^ (h << 5)) >> (3*8 - HLOG)) - h*5) & (HSIZE - 1))
      56             : # endif
      57             : #endif
      58             : /*
      59             :  * IDX works because it is very similar to a multiplicative hash, e.g.
      60             :  * ((h * 57321 >> (3*8 - HLOG)) & (HSIZE - 1))
      61             :  * the latter is also quite fast on newer CPUs, and compresses similarly.
      62             :  *
      63             :  * the next one is also quite good, albeit slow ;)
      64             :  * (int)(cos(h & 0xffffff) * 1e6)
      65             :  */
      66             : 
      67             : #if 0
      68             : /* original lzv-like hash function, much worse and thus slower */
      69             : # define FRST(p) (p[0] << 5) ^ p[1]
      70             : # define NEXT(v,p) ((v) << 5) ^ p[2]
      71             : # define IDX(h) ((h) & (HSIZE - 1))
      72             : #endif
      73             : 
      74             : #define        MAX_LIT        (1 <<  5)
      75             : #define        MAX_OFF        (1 << 13)
      76             : #define        MAX_REF        ((1 << 8) + (1 << 3))
      77             : 
      78             : #if __GNUC__ >= 3
      79             : # define expect(expr,value)         __builtin_expect ((expr),(value))
      80             : # define inline                     inline
      81             : #else
      82             : # define expect(expr,value)         (expr)
      83             : # define inline                     static
      84             : #endif
      85             : 
      86             : #define expect_false(expr) expect ((expr) != 0, 0)
      87             : #define expect_true(expr)  expect ((expr) != 0, 1)
      88             : 
      89             : /*
      90             :  * compressed format
      91             :  *
      92             :  * 000LLLLL <L+1>    ; literal, L+1=1..33 octets
      93             :  * LLLooooo oooooooo ; backref L+1=1..7 octets, o+1=1..4096 offset
      94             :  * 111ooooo LLLLLLLL oooooooo ; backref L+8 octets, o+1=1..4096 offset
      95             :  *
      96             :  */
      97             : 
      98             : unsigned int
      99          76 : lzf_compress (const void *const in_data, unsigned int in_len,
     100             :               void *out_data, unsigned int out_len
     101             : #if LZF_STATE_ARG
     102             :               , LZF_STATE htab
     103             : #endif
     104             :               )
     105             : {
     106             : #if !LZF_STATE_ARG
     107             :   LZF_STATE htab;
     108             : #endif
     109          76 :   const u8 *ip = (const u8 *)in_data;
     110          76 :         u8 *op = (u8 *)out_data;
     111          76 :   const u8 *in_end  = ip + in_len;
     112          76 :         u8 *out_end = op + out_len;
     113             :   const u8 *ref;
     114             : 
     115             :   /* off requires a type wide enough to hold a general pointer difference.
     116             :    * ISO C doesn't have that (size_t might not be enough and ptrdiff_t only
     117             :    * works for differences within a single object). We also assume that no
     118             :    * no bit pattern traps. Since the only platform that is both non-POSIX
     119             :    * and fails to support both assumptions is windows 64 bit, we make a
     120             :    * special workaround for it.
     121             :    */
     122             : #if defined (WIN32) && defined (_M_X64)
     123             :   unsigned long long off; /* workaround for missing POSIX compliance */
     124             : #else
     125             :   unsigned long off;
     126             : #endif
     127             :   unsigned int hval;
     128             :   int lit;
     129             : 
     130          76 :   if (!in_len || !out_len)
     131           0 :     return 0;
     132             : 
     133             : #if INIT_HTAB
     134             :   memset (htab, 0, sizeof (htab));
     135             : #endif
     136             : 
     137          76 :   lit = 0; op++; /* start run */
     138             : 
     139          76 :   hval = FRST (ip);
     140   237372174 :   while (ip < in_end - 2)
     141             :     {
     142             :       LZF_HSLOT *hslot;
     143             : 
     144   237372078 :       hval = NEXT (hval, ip);
     145   237372078 :       hslot = htab + IDX (hval);
     146   237372078 :       ref = *hslot + LZF_HSLOT_BIAS; *hslot = ip - LZF_HSLOT_BIAS;
     147             : 
     148   237372078 :       if (1
     149             : #if INIT_HTAB
     150             :           && ref < ip /* the next test will actually take care of this, but this is faster */
     151             : #endif
     152   237372078 :           && (off = ip - ref - 1) < MAX_OFF
     153    43775836 :           && ref > (u8 *)in_data
     154    43774058 :           && ref[2] == ip[2]
     155             : #if STRICT_ALIGN
     156             :           && ((ref[1] << 8) | ref[0]) == ((ip[1] << 8) | ip[0])
     157             : #else
     158    20177627 :           && *(u16 *)ref == *(u16 *)ip
     159             : #endif
     160             :         )
     161    20176986 :         {
     162             :           /* match found at *ref++ */
     163    20177042 :           unsigned int len = 2;
     164    20177042 :           unsigned int maxlen = in_end - ip - len;
     165    20177042 :           maxlen = maxlen > MAX_REF ? MAX_REF : maxlen;
     166             : 
     167    20177042 :           if (expect_false (op + 3 + 1 >= out_end)) /* first a faster conservative test */
     168           0 :             if (op - !lit + 3 + 1 >= out_end) /* second the exact but rare test */
     169           0 :               return 0;
     170             : 
     171    20177042 :           op [- lit - 1] = lit - 1; /* stop run */
     172    20177042 :           op -= !lit; /* undo run if length is zero */
     173             : 
     174             :           for (;;)
     175             :             {
     176    20177042 :               if (expect_true (maxlen > 16))
     177             :                 {
     178    20176922 :                   len++; if (ref [len] != ip [len]) break;
     179    12656884 :                   len++; if (ref [len] != ip [len]) break;
     180     9147566 :                   len++; if (ref [len] != ip [len]) break;
     181     6914404 :                   len++; if (ref [len] != ip [len]) break;
     182             : 
     183     5099844 :                   len++; if (ref [len] != ip [len]) break;
     184     3512972 :                   len++; if (ref [len] != ip [len]) break;
     185     2665092 :                   len++; if (ref [len] != ip [len]) break;
     186     2333354 :                   len++; if (ref [len] != ip [len]) break;
     187             : 
     188     2015942 :                   len++; if (ref [len] != ip [len]) break;
     189     1669926 :                   len++; if (ref [len] != ip [len]) break;
     190     1486542 :                   len++; if (ref [len] != ip [len]) break;
     191     1349782 :                   len++; if (ref [len] != ip [len]) break;
     192             : 
     193     1225720 :                   len++; if (ref [len] != ip [len]) break;
     194     1049746 :                   len++; if (ref [len] != ip [len]) break;
     195      896366 :                   len++; if (ref [len] != ip [len]) break;
     196      811482 :                   len++; if (ref [len] != ip [len]) break;
     197             :                 }
     198             : 
     199             :               do
     200    14935992 :                 len++;
     201    14935992 :               while (len < maxlen && ref[len] == ip[len]);
     202             : 
     203      750276 :               break;
     204             :             }
     205             : 
     206    20177042 :           len -= 2; /* len is now #octets - 1 */
     207    20177042 :           ip++;
     208             : 
     209    20177042 :           if (len < 7)
     210             :             {
     211    17511932 :               *op++ = (off >> 8) + (len << 5);
     212             :             }
     213             :           else
     214             :             {
     215     2665110 :               *op++ = (off >> 8) + (  7 << 5);
     216     2665110 :               *op++ = len - 7;
     217             :             }
     218             : 
     219    20177042 :           *op++ = off;
     220             : 
     221    20177042 :           lit = 0; op++; /* start run */
     222             : 
     223    20177042 :           ip += len + 1;
     224             : 
     225    20177042 :           if (expect_false (ip >= in_end - 2))
     226          56 :             break;
     227             : 
     228             : #if ULTRA_FAST || VERY_FAST
     229    20176986 :           --ip;
     230             : # if VERY_FAST && !ULTRA_FAST
     231    20176986 :           --ip;
     232             : # endif
     233    20176986 :           hval = FRST (ip);
     234             : 
     235    20176986 :           hval = NEXT (hval, ip);
     236    20176986 :           htab[IDX (hval)] = ip - LZF_HSLOT_BIAS;
     237    20176986 :           ip++;
     238             : 
     239             : # if VERY_FAST && !ULTRA_FAST
     240    20176986 :           hval = NEXT (hval, ip);
     241    20176986 :           htab[IDX (hval)] = ip - LZF_HSLOT_BIAS;
     242    20176986 :           ip++;
     243             : # endif
     244             : #else
     245             :           ip -= len + 1;
     246             : 
     247             :           do
     248             :             {
     249             :               hval = NEXT (hval, ip);
     250             :               htab[IDX (hval)] = ip - LZF_HSLOT_BIAS;
     251             :               ip++;
     252             :             }
     253             :           while (len--);
     254             : #endif
     255             :         }
     256             :       else
     257             :         {
     258             :           /* one more literal byte we must copy */
     259   217195036 :           if (expect_false (op >= out_end))
     260           0 :             return 0;
     261             : 
     262   217195036 :           lit++; *op++ = *ip++;
     263             : 
     264   217195036 :           if (expect_false (lit == MAX_LIT))
     265             :             {
     266     5990030 :               op [- lit - 1] = lit - 1; /* stop run */
     267     5990030 :               lit = 0; op++; /* start run */
     268             :             }
     269             :         }
     270             :     }
     271             : 
     272          76 :   if (op + 3 > out_end) /* at most 3 bytes can be missing here */
     273           0 :     return 0;
     274             : 
     275         270 :   while (ip < in_end)
     276             :     {
     277         118 :       lit++; *op++ = *ip++;
     278             : 
     279         118 :       if (expect_false (lit == MAX_LIT))
     280             :         {
     281           4 :           op [- lit - 1] = lit - 1; /* stop run */
     282           4 :           lit = 0; op++; /* start run */
     283             :         }
     284             :     }
     285             : 
     286          76 :   op [- lit - 1] = lit - 1; /* end run */
     287          76 :   op -= !lit; /* undo run if length is zero */
     288             : 
     289          76 :   return op - (u8 *)out_data;
     290             : }
     291             : 

Generated by: LCOV version 1.10