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