release/src/router/lzo/src/lzo_mchw.ch

   1 /* lzo_mchw.ch -- matching functions using a window
   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 typedef struct
  49 {
  50     unsigned init;
  51
  52     lzo_uint look;          /* bytes in lookahead buffer */
  53
  54     lzo_uint m_len;
  55     lzo_uint m_off;
  56
  57     lzo_uint last_m_len;
  58     lzo_uint last_m_off;
  59
  60     const lzo_bytep bp;
  61     const lzo_bytep ip;
  62     const lzo_bytep in;
  63     const lzo_bytep in_end;
  64     lzo_bytep out;
  65
  66     lzo_callback_p cb;
  67
  68     lzo_uint textsize;      /* text size counter */
  69     lzo_uint codesize;      /* code size counter */
  70     lzo_uint printcount;    /* counter for reporting progress every 1K bytes */
  71
  72     /* some stats */
  73     unsigned long lit_bytes;
  74     unsigned long match_bytes;
  75     unsigned long rep_bytes;
  76     unsigned long lazy;
  77
  78 #if defined(LZO1B)
  79     lzo_uint r1_m_len;
  80
  81     /* some stats */
  82     unsigned long r1_r, m3_r, m2_m, m3_m;
  83 #endif
  84
  85 #if defined(LZO1C)
  86     lzo_uint r1_m_len;
  87     lzo_bytep m3;
  88
  89     /* some stats */
  90     unsigned long r1_r, m3_r, m2_m, m3_m;
  91 #endif
  92
  93 #if defined(LZO1F)
  94     lzo_uint r1_lit;
  95     lzo_uint r1_m_len;
  96
  97     /* some stats */
  98     unsigned long r1_r, m2_m, m3_m;
  99 #endif
 100
 101 #if defined(LZO1X) || defined(LZO1Y) || defined(LZO1Z)
 102     lzo_uint r1_lit;
 103     lzo_uint r1_m_len;
 104
 105     /* some stats */
 106     unsigned long m1a_m, m1b_m, m2_m, m3_m, m4_m;
 107     unsigned long lit1_r, lit2_r, lit3_r;
 108 #endif
 109
 110 #if defined(LZO2A)
 111     /* some stats */
 112     unsigned long m1, m2, m3, m4;
 113 #endif
 114 }
 115 LZO_COMPRESS_T;
 116
 117
 118 #if (LZO_CC_BORLANDC && LZO_ARCH_I086) && (__BORLANDC__ < 0x0450)
 119    /* work around a Borland C 3.1 bug */
 120 #  define getbyte(c)  ((c).ip < (c).in_end ? (c).ip +=1, (c).ip[-1] : (-1))
 121 #elif (LZO_OS_TOS && (LZO_CC_PUREC || LZO_CC_TURBOC))
 122    /* work around a code generation bug in Turbo C / Pure C (Atari ST) */
 123 #  define getbyte(c)  ((c).ip < (c).in_end ? (int) (unsigned) *((c).ip)++ : (-1))
 124 #else
 125 #  define getbyte(c)  ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
 126 #endif
 127
 128 #include "lzo_swd.ch"
 129
 130
 131 /***********************************************************************
 132 //
 133 ************************************************************************/
 134
 135 static int
 136 init_match ( LZO_COMPRESS_T *c, lzo_swd_p s,
 137              const lzo_bytep dict, lzo_uint dict_len,
 138              lzo_uint32 flags )
 139 {
 140     int r;
 141
 142     assert(!c->init);
 143     c->init = 1;
 144
 145     s->c = c;
 146
 147     c->last_m_len = c->last_m_off = 0;
 148
 149     c->textsize = c->codesize = c->printcount = 0;
 150     c->lit_bytes = c->match_bytes = c->rep_bytes = 0;
 151     c->lazy = 0;
 152
 153     r = swd_init(s,dict,dict_len);
 154     if (r != LZO_E_OK)
 155     {
 156         swd_exit(s);
 157         return r;
 158     }
 159
 160     s->use_best_off = (flags & 1) ? 1 : 0;
 161     return LZO_E_OK;
 162 }
 163
 164
 165 /***********************************************************************
 166 //
 167 ************************************************************************/
 168
 169 static int
 170 find_match ( LZO_COMPRESS_T *c, lzo_swd_p s,
 171              lzo_uint this_len, lzo_uint skip )
 172 {
 173     assert(c->init);
 174
 175     if (skip > 0)
 176     {
 177         assert(this_len >= skip);
 178         swd_accept(s, this_len - skip);
 179         c->textsize += this_len - skip + 1;
 180     }
 181     else
 182     {
 183         assert(this_len <= 1);
 184         c->textsize += this_len - skip;
 185     }
 186
 187     s->m_len = SWD_THRESHOLD;
 188     s->m_off = 0;
 189 #ifdef SWD_BEST_OFF
 190     if (s->use_best_off)
 191         lzo_memset(s->best_pos,0,sizeof(s->best_pos));
 192 #endif
 193     swd_findbest(s);
 194     c->m_len = s->m_len;
 195     c->m_off = s->m_off;
 196
 197     swd_getbyte(s);
 198
 199     if (s->b_char < 0)
 200     {
 201         c->look = 0;
 202         c->m_len = 0;
 203         swd_exit(s);
 204     }
 205     else
 206     {
 207         c->look = s->look + 1;
 208     }
 209     c->bp = c->ip - c->look;
 210
 211 #if 0
 212     /* brute force match search */
 213     if (c->m_len > SWD_THRESHOLD && c->m_len + 1 <= c->look)
 214     {
 215         const lzo_bytep ip = c->bp;
 216         const lzo_bytep m  = c->bp - c->m_off;
 217         const lzo_bytep in = c->in;
 218
 219         if (ip - in > s->swd_n)
 220             in = ip - s->swd_n;
 221         for (;;)
 222         {
 223             while (*in != *ip)
 224                 in++;
 225             if (in == ip)
 226                 break;
 227             if (in != m)
 228                 if (lzo_memcmp(in,ip,c->m_len+1) == 0)
 229                     printf("%p %p %p %5d\n",in,ip,m,c->m_len);
 230             in++;
 231         }
 232     }
 233 #endif
 234
 235     if (c->cb && c->cb->nprogress && c->textsize > c->printcount)
 236     {
 237         (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
 238         c->printcount += 1024;
 239     }
 240
 241     return LZO_E_OK;
 242 }
 243
 244
 245 /*
 246 vi:ts=4:et
 247 */
 248