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) 1996-2015 Markus Franz Xaver Johannes Oberhumer
   6    All Rights Reserved.
   7
   8    The LZO library is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2 of
  11    the License, or (at your option) any later version.
  12
  13    The LZO library is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with the LZO library; see the file COPYING.
  20    If not, write to the Free Software Foundation, Inc.,
  21    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  22
  23    Markus F.X.J. Oberhumer
  24    <markus@oberhumer.com>
  25    http://www.oberhumer.com/opensource/lzo/
  26  */
  27
  28
  29
  30 #include "config2a.h"
  31
  32
  33 /***********************************************************************
  34 //
  35 ************************************************************************/
  36
  37 #define SWD_THRESHOLD       1           /* lower limit for match length */
  38 #define SWD_F            2048           /* upper limit for match length */
  39
  40
  41 #define LZO2A 1
  42 #define LZO_COMPRESS_T  lzo2a_999_t
  43 #define lzo_swd_t       lzo2a_999_swd_t
  44 #include "lzo_mchw.ch"
  45
  46
  47 #if (LZO_CC_BORLANDC && LZO_MM_FLAT)
  48 #  if ((__BORLANDC__) >= 0x0450 && (__BORLANDC__) < 0x0460)
  49      /* avoid internal compiler error */
  50 #    pragma option -Od
  51 #  endif
  52 #endif
  53
  54
  55 /***********************************************************************
  56 //
  57 ************************************************************************/
  58
  59 #define putbyte(x)      *op++ = LZO_BYTE(x)
  60
  61 #define putbits(j,x) \
  62     if (k == 0) bitp = op++; \
  63     SETBITS(j,x); \
  64     if (k >= 8) { *bitp = LZO_BYTE(MASKBITS(8)); DUMPBITS(8); \
  65                     if (k > 0) bitp = op++; }
  66
  67 #define putbit(x)       putbits(1,x)
  68
  69
  70 /***********************************************************************
  71 // this is a public function, but there is no prototype in a header file
  72 ************************************************************************/
  73
  74 LZO_EXTERN(int)
  75 lzo2a_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
  76                                     lzo_bytep out, lzo_uintp out_len,
  77                                     lzo_voidp wrkmem,
  78                                     lzo_callback_p cb,
  79                                     lzo_uint max_chain );
  80
  81 LZO_PUBLIC(int)
  82 lzo2a_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
  83                                     lzo_bytep out, lzo_uintp out_len,
  84                                     lzo_voidp wrkmem,
  85                                     lzo_callback_p cb,
  86                                     lzo_uint max_chain )
  87 {
  88     lzo_bytep op;
  89     lzo_bytep bitp = 0;
  90     lzo_uint m_len, m_off;
  91     LZO_COMPRESS_T cc;
  92     LZO_COMPRESS_T * const c = &cc;
  93     lzo_swd_p const swd = (lzo_swd_p) wrkmem;
  94     int r;
  95
  96     lzo_uint32_t b = 0;     /* bit buffer */
  97     unsigned k = 0;         /* bits in bit buffer */
  98
  99     /* sanity check */
 100     LZO_COMPILE_TIME_ASSERT(LZO2A_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
 101
 102     c->init = 0;
 103     c->ip = c->in = in;
 104     c->in_end = in + in_len;
 105     c->cb = cb;
 106     c->m1 = c->m2 = c->m3 = c->m4 = 0;
 107
 108     op = out;
 109
 110     r = init_match(c,swd,NULL,0,0);
 111     if (r != 0)
 112         return r;
 113     if (max_chain > 0)
 114         swd->max_chain = max_chain;
 115
 116     r = find_match(c,swd,0,0);
 117     if (r != 0)
 118         return r;
 119     while (c->look > 0)
 120     {
 121         lzo_uint lazy_match_min_gain = 0;
 122 #if (SWD_N >= 8192)
 123         lzo_uint extra1 = 0;
 124 #endif
 125         lzo_uint extra2 = 0;
 126         lzo_uint ahead = 0;
 127
 128         m_len = c->m_len;
 129         m_off = c->m_off;
 130
 131 #if (SWD_N >= 8192)
 132         if (m_off >= 8192)
 133         {
 134             if (m_len < M3_MIN_LEN)
 135                 m_len = 0;
 136             else
 137                 lazy_match_min_gain = 1;
 138         }
 139         else
 140 #endif
 141         if (m_len >= M1_MIN_LEN && m_len <= M1_MAX_LEN && m_off <= 256)
 142         {
 143             lazy_match_min_gain = 2;
 144 #if (SWD_N >= 8192)
 145             extra1 = 3;
 146 #endif
 147             extra2 = 2;
 148         }
 149         else if (m_len >= 10)
 150             lazy_match_min_gain = 1;
 151         else if (m_len >= 3)
 152         {
 153             lazy_match_min_gain = 1;
 154 #if (SWD_N >= 8192)
 155             extra1 = 1;
 156 #endif
 157         }
 158         else
 159             m_len = 0;
 160
 161
 162         /* try a lazy match */
 163         if (lazy_match_min_gain > 0 && c->look > m_len)
 164         {
 165             unsigned char lit = LZO_BYTE(swd->b_char);
 166
 167             r = find_match(c,swd,1,0);
 168             assert(r == 0); LZO_UNUSED(r);
 169             assert(c->look > 0);
 170
 171 #if (SWD_N >= 8192)
 172             if (m_off < 8192 && c->m_off >= 8192)
 173                 lazy_match_min_gain += extra1;
 174             else
 175 #endif
 176             if (m_len >= M1_MIN_LEN && m_len <= M1_MAX_LEN && m_off <= 256)
 177             {
 178                 if (!(c->m_len >= M1_MIN_LEN &&
 179                       c->m_len <= M1_MAX_LEN && c->m_off <= 256))
 180                     lazy_match_min_gain += extra2;
 181             }
 182             if (c->m_len >= M1_MIN_LEN &&
 183                 c->m_len <= M1_MAX_LEN && c->m_off <= 256)
 184             {
 185                     lazy_match_min_gain -= 1;
 186             }
 187
 188             if ((lzo_int) lazy_match_min_gain < 1)
 189                 lazy_match_min_gain = 1;
 190
 191             if (c->m_len >= m_len + lazy_match_min_gain)
 192             {
 193                 c->lazy++;
 194 #if !defined(NDEBUG)
 195                 m_len = c->m_len;
 196                 m_off = c->m_off;
 197                 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
 198                                   m_len) == 0);
 199                 assert(m_len >= 3 || (m_len >= 2 && m_off <= 256));
 200 #endif
 201                 /* code literal */
 202                 putbit(0);
 203                 putbyte(lit);
 204                 c->lit_bytes++;
 205                 continue;
 206             }
 207             else
 208                 ahead = 1;
 209             assert(m_len > 0);
 210         }
 211
 212
 213         if (m_len == 0)
 214         {
 215             /* a literal */
 216             putbit(0);
 217             putbyte(swd->b_char);
 218             c->lit_bytes++;
 219             r = find_match(c,swd,1,0);
 220             assert(r == 0); LZO_UNUSED(r);
 221         }
 222         else
 223         {
 224             assert(m_len >= M1_MIN_LEN);
 225             assert(m_off > 0);
 226             assert(m_off <= SWD_N);
 227
 228             /* 2 - code match */
 229             if (m_len >= M1_MIN_LEN && m_len <= M1_MAX_LEN && m_off <= 256)
 230             {
 231                 putbit(1);
 232                 putbit(0);
 233                 putbits(2,m_len - M1_MIN_LEN);
 234                 putbyte(m_off - 1);
 235                 c->m1++;
 236             }
 237 #if (SWD_N >= 8192)
 238             else if (m_off >= 8192)
 239             {
 240                 unsigned len = m_len;
 241                 assert(m_len >= M3_MIN_LEN);
 242                 putbit(1);
 243                 putbit(1);
 244                 putbyte(m_off & 31);
 245                 putbyte(m_off >> 5);
 246                 putbit(1);
 247                 len -= M3_MIN_LEN - 1;
 248                 while (len > 255)
 249                 {
 250                     len -= 255;
 251                     putbyte(0);
 252                 }
 253                 putbyte(len);
 254                 c->m4++;
 255             }
 256 #endif
 257             else
 258             {
 259                 assert(m_len >= 3);
 260
 261                 putbit(1);
 262                 putbit(1);
 263                 if (m_len <= 9)
 264                 {
 265                     putbyte(((m_len - 2) << 5) | (m_off & 31));
 266                     putbyte(m_off >> 5);
 267                     c->m2++;
 268                 }
 269                 else
 270                 {
 271                     lzo_uint len = m_len;
 272                     putbyte(m_off & 31);
 273                     putbyte(m_off >> 5);
 274 #if (SWD_N >= 8192)
 275                     putbit(0);
 276 #endif
 277                     len -= 10 - 1;
 278                     while (len > 255)
 279                     {
 280                         len -= 255;
 281                         putbyte(0);
 282                     }
 283                     putbyte(len);
 284                     c->m3++;
 285                 }
 286             }
 287             r = find_match(c,swd,m_len,1+ahead);
 288             assert(r == 0); LZO_UNUSED(r);
 289         }
 290
 291         c->codesize = pd(op, out);
 292     }
 293
 294 #if defined(LZO_EOF_CODE)
 295     /* code EOF code */
 296     putbit(1);
 297     putbit(1);
 298     putbyte(1 << 5);
 299     putbyte(0);
 300 #endif
 301
 302     /* flush remaining bits */
 303     assert(k < CHAR_BIT);
 304     if (k > 0)
 305     {
 306         assert(b == MASKBITS(k));
 307         assert(op - bitp > 1);
 308         *bitp = LZO_BYTE(MASKBITS(k));
 309         DUMPBITS(k);
 310         assert(b == 0);
 311         assert(k == 0);
 312     }
 313
 314     assert(c->textsize == in_len);
 315     c->codesize = pd(op, out);
 316
 317     *out_len = pd(op, out);
 318
 319     if (c->cb && c->cb->nprogress)
 320         (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
 321
 322 #if 0
 323     printf("%ld -> %ld: %ld %ld %ld %ld %ld %ld\n",
 324         (long) c->textsize, (long) c->codesize,
 325         c->lit_bytes, c->m1, c->m2, c->m3, c->m4, c->lazy);
 326 #endif
 327     return LZO_E_OK;
 328 }
 329
 330
 331
 332 /***********************************************************************
 333 //
 334 ************************************************************************/
 335
 336 LZO_PUBLIC(int)
 337 lzo2a_999_compress  ( const lzo_bytep in , lzo_uint  in_len,
 338                             lzo_bytep out, lzo_uintp out_len,
 339                             lzo_voidp wrkmem )
 340 {
 341     return lzo2a_999_compress_callback(in,in_len,out,out_len,wrkmem,
 342                                        (lzo_callback_p) 0, 0);
 343 }
 344
 345
 346 /* vim:set ts=4 sw=4 et: */