release/src/router/lzo/src/lzo1b_c.ch

   1 /* lzo1b_c.ch -- implementation of the LZO1B compression algorithm
   2
   3    This file is part of the LZO real-time data compression library.
   4
   5    Copyright (C) 2011 Markus Franz Xaver Johannes Oberhumer
   6    Copyright (C) 2010 Markus Franz Xaver Johannes Oberhumer
   7    Copyright (C) 2009 Markus Franz Xaver Johannes Oberhumer
   8    Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
   9    Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
  10    Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
  11    Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
  12    Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
  13    Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
  14    Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
  15    Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
  16    Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
  17    Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
  18    Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
  19    Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
  20    Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
  21    All Rights Reserved.
  22
  23    The LZO library is free software; you can redistribute it and/or
  24    modify it under the terms of the GNU General Public License as
  25    published by the Free Software Foundation; either version 2 of
  26    the License, or (at your option) any later version.
  27
  28    The LZO library is distributed in the hope that it will be useful,
  29    but WITHOUT ANY WARRANTY; without even the implied warranty of
  30    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31    GNU General Public License for more details.
  32
  33    You should have received a copy of the GNU General Public License
  34    along with the LZO library; see the file COPYING.
  35    If not, write to the Free Software Foundation, Inc.,
  36    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  37
  38    Markus F.X.J. Oberhumer
  39    <markus@oberhumer.com>
  40    http://www.oberhumer.com/opensource/lzo/
  41  */
  42
  43
  44
  45 /***********************************************************************
  46 //
  47 ************************************************************************/
  48
  49 #if !defined(LZO_HAVE_R1) && !defined(LZO_NO_R1)
  50 #  define LZO_HAVE_R1 1
  51 #endif
  52
  53 #if !defined(LZO_HAVE_M3) && !defined(LZO_NO_M3)
  54 #  if (M3O_BITS < 8)
  55 #    define LZO_HAVE_M3 1
  56 #  endif
  57 #endif
  58
  59
  60 #define MI      /*empty*/
  61 #define SI      MI
  62 #if (DD_BITS > 0)
  63 #define DI      ++ii; DVAL_NEXT(dv,ii); UPDATE_D(dict,drun,dv,ii,in); MI
  64 #define XI      assert(ii < ip); ii = ip; DVAL_FIRST(dv,(ip));
  65 #else
  66 #define DI      ++ii; DINDEX1(dindex,ii); UPDATE_I(dict,0,dindex,ii,in); MI
  67 #define XI      assert(ii < ip); ii = ip;
  68 #endif
  69
  70
  71 /***********************************************************************
  72 // compress a block of data.
  73 //
  74 // I really apologize for this spaghetti code.
  75 ************************************************************************/
  76
  77 LZO_PRIVATE(int)
  78 do_compress    ( const lzo_bytep in , lzo_uint  in_len,
  79                        lzo_bytep out, lzo_uintp out_len,
  80                        lzo_voidp wrkmem )
  81 {
  82     register const lzo_bytep ip;
  83 #if (DD_BITS > 0)
  84 #if defined(__LZO_HASH_INCREMENTAL)
  85     lzo_xint dv;
  86 #endif
  87     unsigned drun = 0;
  88 #endif
  89     lzo_bytep op;
  90     const lzo_bytep const in_end = in + in_len;
  91     const lzo_bytep const ip_end = in + in_len - MIN_LOOKAHEAD;
  92     const lzo_bytep ii;
  93 #if defined(LZO_HAVE_R1)
  94     const lzo_bytep r1 = ip_end;    /* pointer for R1 match (none yet) */
  95 #endif
  96 #if defined(LZO_HAVE_M3)
  97     lzo_bytep m3 = out + 1;         /* pointer after last m3/m4 match */
  98 #endif
  99
 100     lzo_dict_p const dict = (lzo_dict_p) wrkmem;
 101
 102
 103 #if (LZO_COLLECT_STATS)
 104     lzo_stats->r_bits   = R_BITS;
 105     lzo_stats->m3o_bits = M3O_BITS;
 106     lzo_stats->dd_bits  = DD_BITS;
 107     lzo_stats->clevel   = CLEVEL;
 108     lzo_stats->d_bits   = D_BITS;
 109     lzo_stats->min_lookahead  = MIN_LOOKAHEAD;
 110     lzo_stats->max_lookbehind = MAX_LOOKBEHIND;
 111     lzo_stats->compress_id    = LZO_CPP_MACRO_EXPAND(COMPRESS_ID);
 112 #endif
 113
 114     /* init dictionary */
 115 #if (LZO_DETERMINISTIC)
 116     BZERO8_PTR(wrkmem,sizeof(lzo_dict_t),D_SIZE);
 117 #endif
 118
 119
 120     op = out;
 121     ip = in;
 122     ii = ip;            /* point to start of current literal run */
 123
 124
 125 #if (DD_BITS > 0)
 126     DVAL_FIRST(dv,ip);
 127     UPDATE_D(dict,drun,dv,ip,in);
 128     ip++;
 129     DVAL_NEXT(dv,ip);
 130 #else
 131     ip++;
 132 #endif
 133
 134     assert(ip < ip_end);
 135     for (;;)
 136     {
 137         const lzo_bytep m_pos;
 138 #if !defined(NDEBUG)
 139         const lzo_bytep m_pos_sav = NULL;
 140 #endif
 141         LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, m_off, 0);
 142 #if (DD_BITS == 0)
 143         lzo_uint dindex;
 144 #endif
 145         lzo_uint m_len;
 146
 147
 148 /***********************************************************************
 149 // search for a match
 150 ************************************************************************/
 151
 152 #if !defined(LZO_SEARCH_MATCH_INCLUDE_FILE)
 153 #  define LZO_SEARCH_MATCH_INCLUDE_FILE     "lzo1b_sm.ch"
 154 #endif
 155
 156 #include LZO_SEARCH_MATCH_INCLUDE_FILE
 157
 158
 159 #if !defined(LZO_TEST_MATCH_INCLUDE_FILE)
 160 #  define LZO_TEST_MATCH_INCLUDE_FILE       "lzo1b_tm.ch"
 161 #endif
 162
 163 #include LZO_TEST_MATCH_INCLUDE_FILE
 164
 165
 166
 167 /***********************************************************************
 168 // found a literal
 169 ************************************************************************/
 170
 171
 172     /* a literal */
 173 literal:
 174 #if (DD_BITS == 0)
 175         UPDATE_I(dict,0,dindex,ip,in);
 176 #endif
 177         if (++ip >= ip_end)
 178             break;
 179 #if (DD_BITS > 0)
 180         DVAL_NEXT(dv,ip);
 181 #endif
 182         continue;
 183
 184
 185
 186 /***********************************************************************
 187 // found a match
 188 ************************************************************************/
 189
 190 match:
 191 #if (DD_BITS == 0)
 192         UPDATE_I(dict,0,dindex,ip,in);
 193 #endif
 194         /* we have found a match of at least M2_MIN_LEN */
 195
 196
 197 #if !defined(LZO_CODE_RUN_INCLUDE_FILE)
 198 #  define LZO_CODE_RUN_INCLUDE_FILE     "lzo1b_cr.ch"
 199 #endif
 200
 201 #include LZO_CODE_RUN_INCLUDE_FILE
 202
 203
 204         /* ii now points to the start of the current match */
 205         assert(ii == ip);
 206
 207
 208 /***********************************************************************
 209 // code the match
 210 ************************************************************************/
 211
 212 #if !defined(LZO_CODE_MATCH_INCLUDE_FILE)
 213 #  define LZO_CODE_MATCH_INCLUDE_FILE   "lzo1b_cm.ch"
 214 #endif
 215
 216 #include LZO_CODE_MATCH_INCLUDE_FILE
 217
 218
 219         /* ii now points to the start of the next literal run */
 220         assert(ii == ip);
 221
 222     }
 223
 224
 225 /***********************************************************************
 226 // end of block
 227 ************************************************************************/
 228
 229     assert(ip <= in_end);
 230
 231 #if (LZO_COLLECT_STATS)
 232     {
 233         lzo_uint i;
 234         const lzo_bytep p;
 235
 236         for (i = 0; i < D_SIZE; i++)
 237         {
 238             p = dict[i];
 239             if (BOUNDS_CHECKING_OFF_IN_EXPR(p == NULL || p < in || p > in_end))
 240                 lzo_stats->unused_dict_entries++;
 241         }
 242         lzo_stats->unused_dict_entries_percent =
 243             100.0 * lzo_stats->unused_dict_entries / D_SIZE;
 244     }
 245 #endif
 246
 247
 248 #if defined(LZO_RETURN_IF_NOT_COMPRESSIBLE)
 249     /* return if op == out to indicate that we
 250      * couldn't compress and didn't copy anything.
 251      */
 252     if (op == out)
 253     {
 254         *out_len = 0;
 255         return LZO_E_NOT_COMPRESSIBLE;
 256     }
 257 #endif
 258
 259     /* store the final literal run */
 260     if (pd(in_end,ii) > 0)
 261     {
 262         lzo_uint t = pd(in_end,ii);
 263         op = STORE_RUN(op,ii,t);
 264     }
 265
 266     *out_len = pd(op, out);
 267     return LZO_E_OK;                /* compression went ok */
 268 }
 269
 270
 271 /*
 272 vi:ts=4:et
 273 */