release/src/router/lzo/src/lzo2a_9x.c

   1 /* lzo2a_9x.c -- implementation of the LZO2A-999 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 #include "config2a.h"
  46
  47
  48 /***********************************************************************
  49 //
  50 ************************************************************************/
  51
  52 #define SWD_THRESHOLD       1           /* lower limit for match length */
  53 #define SWD_F            2048           /* upper limit for match length */
  54
  55
  56 #define LZO2A 1
  57 #define LZO_COMPRESS_T  lzo2a_999_t
  58 #define lzo_swd_t       lzo2a_999_swd_t
  59 #include "lzo_mchw.ch"
  60
  61
  62 #if (LZO_CC_BORLANDC && LZO_MM_FLAT)
  63 #  if ((__BORLANDC__) >= 0x0450 && (__BORLANDC__) < 0x0460)
  64      /* avoid internal compiler error */
  65 #    pragma option -Od
  66 #  endif
  67 #endif
  68
  69
  70 /***********************************************************************
  71 //
  72 ************************************************************************/
  73
  74 #define putbyte(x)      *op++ = LZO_BYTE(x)
  75
  76 #define putbits(j,x) \
  77     if (k == 0) bitp = op++; \
  78     SETBITS(j,x); \
  79     if (k >= 8) { *bitp = LZO_BYTE(MASKBITS(8)); DUMPBITS(8); \
  80                     if (k > 0) bitp = op++; }
  81
  82 #define putbit(x)       putbits(1,x)
  83
  84
  85 /***********************************************************************
  86 // this is a public function, but there is no prototype in a header file
  87 ************************************************************************/
  88
  89 LZO_EXTERN(int)
  90 lzo2a_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
  91                                     lzo_bytep out, lzo_uintp out_len,
  92                                     lzo_voidp wrkmem,
  93                                     lzo_callback_p cb,
  94                                     lzo_uint max_chain );
  95
  96 LZO_PUBLIC(int)
  97 lzo2a_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
  98                                     lzo_bytep out, lzo_uintp out_len,
  99                                     lzo_voidp wrkmem,
 100                                     lzo_callback_p cb,
 101                                     lzo_uint max_chain )
 102 {
 103     lzo_bytep op;
 104     lzo_bytep bitp = 0;
 105     lzo_uint m_len, m_off;
 106     LZO_COMPRESS_T cc;
 107     LZO_COMPRESS_T * const c = &cc;
 108     lzo_swd_p const swd = (lzo_swd_p) wrkmem;
 109     int r;
 110
 111     lzo_uint32 b = 0;       /* bit buffer */
 112     unsigned k = 0;         /* bits in bit buffer */
 113
 114     /* sanity check */
 115     LZO_COMPILE_TIME_ASSERT(LZO2A_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
 116
 117     c->init = 0;
 118     c->ip = c->in = in;
 119     c->in_end = in + in_len;
 120     c->cb = cb;
 121     c->m1 = c->m2 = c->m3 = c->m4 = 0;
 122
 123     op = out;
 124
 125     r = init_match(c,swd,NULL,0,0);
 126     if (r != 0)
 127         return r;
 128     if (max_chain > 0)
 129         swd->max_chain = max_chain;
 130
 131     r = find_match(c,swd,0,0);
 132     if (r != 0)
 133         return r;
 134     while (c->look > 0)
 135     {
 136         lzo_uint lazy_match_min_gain = 0;
 137 #if (SWD_N >= 8192)
 138         lzo_uint extra1 = 0;
 139 #endif
 140         lzo_uint extra2 = 0;
 141         lzo_uint ahead = 0;
 142
 143         m_len = c->m_len;
 144         m_off = c->m_off;
 145
 146 #if (SWD_N >= 8192)
 147         if (m_off >= 8192)
 148         {
 149             if (m_len < M3_MIN_LEN)
 150                 m_len = 0;
 151             else
 152                 lazy_match_min_gain = 1;
 153         }
 154         else
 155 #endif
 156         if (m_len >= M1_MIN_LEN && m_len <= M1_MAX_LEN && m_off <= 256)
 157         {
 158             lazy_match_min_gain = 2;
 159 #if (SWD_N >= 8192)
 160             extra1 = 3;
 161 #endif
 162             extra2 = 2;
 163         }
 164         else if (m_len >= 10)
 165             lazy_match_min_gain = 1;
 166         else if (m_len >= 3)
 167         {
 168             lazy_match_min_gain = 1;
 169 #if (SWD_N >= 8192)
 170             extra1 = 1;
 171 #endif
 172         }
 173         else
 174             m_len = 0;
 175
 176
 177         /* try a lazy match */
 178         if (lazy_match_min_gain > 0 && c->look > m_len)
 179         {
 180             unsigned char lit = LZO_BYTE(swd->b_char);
 181
 182             r = find_match(c,swd,1,0);
 183             assert(r == 0); LZO_UNUSED(r);
 184             assert(c->look > 0);
 185
 186 #if (SWD_N >= 8192)
 187             if (m_off < 8192 && c->m_off >= 8192)
 188                 lazy_match_min_gain += extra1;
 189             else
 190 #endif
 191             if (m_len >= M1_MIN_LEN && m_len <= M1_MAX_LEN && m_off <= 256)
 192             {
 193                 if (!(c->m_len >= M1_MIN_LEN &&
 194                       c->m_len <= M1_MAX_LEN && c->m_off <= 256))
 195                     lazy_match_min_gain += extra2;
 196             }
 197             if (c->m_len >= M1_MIN_LEN &&
 198                 c->m_len <= M1_MAX_LEN && c->m_off <= 256)
 199             {
 200                     lazy_match_min_gain -= 1;
 201             }
 202
 203             if ((lzo_int) lazy_match_min_gain < 1)
 204                 lazy_match_min_gain = 1;
 205
 206             if (c->m_len >= m_len + lazy_match_min_gain)
 207             {
 208                 c->lazy++;
 209 #if !defined(NDEBUG)
 210                 m_len = c->m_len;
 211                 m_off = c->m_off;
 212                 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
 213                                   m_len) == 0);
 214                 assert(m_len >= 3 || (m_len >= 2 && m_off <= 256));
 215 #endif
 216                 /* code literal */
 217                 putbit(0);
 218                 putbyte(lit);
 219                 c->lit_bytes++;
 220                 continue;
 221             }
 222             else
 223                 ahead = 1;
 224             assert(m_len > 0);
 225         }
 226
 227
 228         if (m_len == 0)
 229         {
 230             /* a literal */
 231             putbit(0);
 232             putbyte(swd->b_char);
 233             c->lit_bytes++;
 234             r = find_match(c,swd,1,0);
 235             assert(r == 0); LZO_UNUSED(r);
 236         }
 237         else
 238         {
 239             assert(m_len >= M1_MIN_LEN);
 240             assert(m_off > 0);
 241             assert(m_off <= SWD_N);
 242
 243             /* 2 - code match */
 244             if (m_len >= M1_MIN_LEN && m_len <= M1_MAX_LEN && m_off <= 256)
 245             {
 246                 putbit(1);
 247                 putbit(0);
 248                 putbits(2,m_len - M1_MIN_LEN);
 249                 putbyte(m_off - 1);
 250                 c->m1++;
 251             }
 252 #if (SWD_N >= 8192)
 253             else if (m_off >= 8192)
 254             {
 255                 unsigned len = m_len;
 256                 assert(m_len >= M3_MIN_LEN);
 257                 putbit(1);
 258                 putbit(1);
 259                 putbyte(m_off & 31);
 260                 putbyte(m_off >> 5);
 261                 putbit(1);
 262                 len -= M3_MIN_LEN - 1;
 263                 while (len > 255)
 264                 {
 265                     len -= 255;
 266                     putbyte(0);
 267                 }
 268                 putbyte(len);
 269                 c->m4++;
 270             }
 271 #endif
 272             else
 273             {
 274                 assert(m_len >= 3);
 275
 276                 putbit(1);
 277                 putbit(1);
 278                 if (m_len <= 9)
 279                 {
 280                     putbyte(((m_len - 2) << 5) | (m_off & 31));
 281                     putbyte(m_off >> 5);
 282                     c->m2++;
 283                 }
 284                 else
 285                 {
 286                     lzo_uint len = m_len;
 287                     putbyte(m_off & 31);
 288                     putbyte(m_off >> 5);
 289 #if (SWD_N >= 8192)
 290                     putbit(0);
 291 #endif
 292                     len -= 10 - 1;
 293                     while (len > 255)
 294                     {
 295                         len -= 255;
 296                         putbyte(0);
 297                     }
 298                     putbyte(len);
 299                     c->m3++;
 300                 }
 301             }
 302             r = find_match(c,swd,m_len,1+ahead);
 303             assert(r == 0); LZO_UNUSED(r);
 304         }
 305
 306         c->codesize = pd(op, out);
 307     }
 308
 309 #if defined(LZO_EOF_CODE)
 310     /* code EOF code */
 311     putbit(1);
 312     putbit(1);
 313     putbyte(1 << 5);
 314     putbyte(0);
 315 #endif
 316
 317     /* flush remaining bits */
 318     assert(k < CHAR_BIT);
 319     if (k > 0)
 320     {
 321         assert(b == MASKBITS(k));
 322         assert(op - bitp > 1);
 323         *bitp = LZO_BYTE(MASKBITS(k));
 324         DUMPBITS(k);
 325         assert(b == 0);
 326         assert(k == 0);
 327     }
 328
 329     assert(c->textsize == in_len);
 330     c->codesize = pd(op, out);
 331
 332     *out_len = pd(op, out);
 333
 334     if (c->cb && c->cb->nprogress)
 335         (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
 336
 337 #if 0
 338     printf("%ld -> %ld: %ld %ld %ld %ld %ld %ld\n",
 339         (long) c->textsize, (long) c->codesize,
 340         c->lit_bytes, c->m1, c->m2, c->m3, c->m4, c->lazy);
 341 #endif
 342     return LZO_E_OK;
 343 }
 344
 345
 346
 347 /***********************************************************************
 348 //
 349 ************************************************************************/
 350
 351 LZO_PUBLIC(int)
 352 lzo2a_999_compress  ( const lzo_bytep in , lzo_uint  in_len,
 353                             lzo_bytep out, lzo_uintp out_len,
 354                             lzo_voidp wrkmem )
 355 {
 356     return lzo2a_999_compress_callback(in,in_len,out,out_len,wrkmem,
 357                                        (lzo_callback_p) 0, 0);
 358 }
 359
 360
 361 /*
 362 vi:ts=4:et
 363 */
 364