release/src/router/lzo/src/lzo1x_9x.c

   1 /* lzo1x_9x.c -- implementation of the LZO1X-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 #if !defined(LZO1X) && !defined(LZO1Y) && !defined(LZO1Z)
  45 #  define LZO1X 1
  46 #endif
  47
  48 #if defined(LZO1X)
  49 #  include "config1x.h"
  50 #elif defined(LZO1Y)
  51 #  include "config1y.h"
  52 #elif defined(LZO1Z)
  53 #  include "config1z.h"
  54 #else
  55 #  error
  56 #endif
  57
  58
  59 /***********************************************************************
  60 //
  61 ************************************************************************/
  62
  63 #define SWD_N           M4_MAX_OFFSET   /* size of ring buffer */
  64 #define SWD_THRESHOLD       1           /* lower limit for match length */
  65 #define SWD_F            2048           /* upper limit for match length */
  66
  67 #define SWD_BEST_OFF    (LZO_MAX3( M2_MAX_LEN, M3_MAX_LEN, M4_MAX_LEN ) + 1)
  68
  69 #if defined(LZO1X)
  70 #  define LZO_COMPRESS_T                lzo1x_999_t
  71 #  define lzo_swd_t                     lzo1x_999_swd_t
  72 #elif defined(LZO1Y)
  73 #  define LZO_COMPRESS_T                lzo1y_999_t
  74 #  define lzo_swd_t                     lzo1y_999_swd_t
  75 #  define lzo1x_999_compress_internal   lzo1y_999_compress_internal
  76 #  define lzo1x_999_compress_dict       lzo1y_999_compress_dict
  77 #  define lzo1x_999_compress_level      lzo1y_999_compress_level
  78 #  define lzo1x_999_compress            lzo1y_999_compress
  79 #elif defined(LZO1Z)
  80 #  define LZO_COMPRESS_T                lzo1z_999_t
  81 #  define lzo_swd_t                     lzo1z_999_swd_t
  82 #  define lzo1x_999_compress_internal   lzo1z_999_compress_internal
  83 #  define lzo1x_999_compress_dict       lzo1z_999_compress_dict
  84 #  define lzo1x_999_compress_level      lzo1z_999_compress_level
  85 #  define lzo1x_999_compress            lzo1z_999_compress
  86 #else
  87 #  error
  88 #endif
  89
  90 #if 0
  91 #  define HEAD3(b,p) \
  92     ((((((lzo_xint)b[p]<<3)^b[p+1])<<3)^b[p+2]) & (SWD_HSIZE-1))
  93 #endif
  94 #if 0 && defined(LZO_UNALIGNED_OK_4) && defined(LZO_ABI_LITTLE_ENDIAN)
  95 #  define HEAD3(b,p) \
  96     (((* (lzo_uint32p) &b[p]) ^ ((* (lzo_uint32p) &b[p])>>10)) & (SWD_HSIZE-1))
  97 #endif
  98
  99 #include "lzo_mchw.ch"
 100
 101
 102 /* this is a public functions, but there is no prototype in a header file */
 103 LZO_EXTERN(int)
 104 lzo1x_999_compress_internal ( const lzo_bytep in , lzo_uint  in_len,
 105                                     lzo_bytep out, lzo_uintp out_len,
 106                                     lzo_voidp wrkmem,
 107                               const lzo_bytep dict, lzo_uint dict_len,
 108                                     lzo_callback_p cb,
 109                                     int try_lazy_parm,
 110                                     lzo_uint good_length,
 111                                     lzo_uint max_lazy,
 112                                     lzo_uint nice_length,
 113                                     lzo_uint max_chain,
 114                                     lzo_uint32 flags );
 115
 116
 117 /***********************************************************************
 118 //
 119 ************************************************************************/
 120
 121 static lzo_bytep
 122 code_match ( LZO_COMPRESS_T *c, lzo_bytep op, lzo_uint m_len, lzo_uint m_off )
 123 {
 124     lzo_uint x_len = m_len;
 125     lzo_uint x_off = m_off;
 126
 127     c->match_bytes += (unsigned long) m_len;
 128
 129 #if 0
 130 /*
 131     static lzo_uint last_m_len = 0, last_m_off = 0;
 132     static lzo_uint prev_m_off[4];
 133     static unsigned prev_m_off_ptr = 0;
 134     unsigned i;
 135
 136     //if (m_len >= 3 && m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
 137     if (m_len >= 3 && m_len <= M2_MAX_LEN)
 138     {
 139     //if (m_len == last_m_len && m_off == last_m_off)
 140         //printf("last_m_len + last_m_off\n");
 141     //else
 142     if (m_off == last_m_off)
 143         printf("last_m_off\n");
 144     else
 145     {
 146         for (i = 0; i < 4; i++)
 147             if (m_off == prev_m_off[i])
 148                 printf("prev_m_off %u: %5ld\n",i,(long)m_off);
 149     }
 150     }
 151     last_m_len = m_len;
 152     last_m_off = prev_m_off[prev_m_off_ptr] = m_off;
 153     prev_m_off_ptr = (prev_m_off_ptr + 1) & 3;
 154 */
 155 #endif
 156
 157     assert(op > c->out);
 158     if (m_len == 2)
 159     {
 160         assert(m_off <= M1_MAX_OFFSET);
 161         assert(c->r1_lit > 0); assert(c->r1_lit < 4);
 162         m_off -= 1;
 163 #if defined(LZO1Z)
 164         *op++ = LZO_BYTE(M1_MARKER | (m_off >> 6));
 165         *op++ = LZO_BYTE(m_off << 2);
 166 #else
 167         *op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
 168         *op++ = LZO_BYTE(m_off >> 2);
 169 #endif
 170         c->m1a_m++;
 171     }
 172 #if defined(LZO1Z)
 173     else if (m_len <= M2_MAX_LEN && (m_off <= M2_MAX_OFFSET || m_off == c->last_m_off))
 174 #else
 175     else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
 176 #endif
 177     {
 178         assert(m_len >= 3);
 179 #if defined(LZO1X)
 180         m_off -= 1;
 181         *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
 182         *op++ = LZO_BYTE(m_off >> 3);
 183         assert(op[-2] >= M2_MARKER);
 184 #elif defined(LZO1Y)
 185         m_off -= 1;
 186         *op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2));
 187         *op++ = LZO_BYTE(m_off >> 2);
 188         assert(op[-2] >= M2_MARKER);
 189 #elif defined(LZO1Z)
 190         if (m_off == c->last_m_off)
 191             *op++ = LZO_BYTE(((m_len - 1) << 5) | (0x700 >> 6));
 192         else
 193         {
 194             m_off -= 1;
 195             *op++ = LZO_BYTE(((m_len - 1) << 5) | (m_off >> 6));
 196             *op++ = LZO_BYTE(m_off << 2);
 197         }
 198 #endif
 199         c->m2_m++;
 200     }
 201     else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4)
 202     {
 203         assert(m_len == 3);
 204         assert(m_off > M2_MAX_OFFSET);
 205         m_off -= 1 + M2_MAX_OFFSET;
 206 #if defined(LZO1Z)
 207         *op++ = LZO_BYTE(M1_MARKER | (m_off >> 6));
 208         *op++ = LZO_BYTE(m_off << 2);
 209 #else
 210         *op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
 211         *op++ = LZO_BYTE(m_off >> 2);
 212 #endif
 213         c->m1b_m++;
 214     }
 215     else if (m_off <= M3_MAX_OFFSET)
 216     {
 217         assert(m_len >= 3);
 218         m_off -= 1;
 219         if (m_len <= M3_MAX_LEN)
 220             *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
 221         else
 222         {
 223             m_len -= M3_MAX_LEN;
 224             *op++ = M3_MARKER | 0;
 225             while (m_len > 255)
 226             {
 227                 m_len -= 255;
 228                 *op++ = 0;
 229             }
 230             assert(m_len > 0);
 231             *op++ = LZO_BYTE(m_len);
 232         }
 233 #if defined(LZO1Z)
 234         *op++ = LZO_BYTE(m_off >> 6);
 235         *op++ = LZO_BYTE(m_off << 2);
 236 #else
 237         *op++ = LZO_BYTE(m_off << 2);
 238         *op++ = LZO_BYTE(m_off >> 6);
 239 #endif
 240         c->m3_m++;
 241     }
 242     else
 243     {
 244         lzo_uint k;
 245
 246         assert(m_len >= 3);
 247         assert(m_off > 0x4000); assert(m_off <= 0xbfff);
 248         m_off -= 0x4000;
 249         k = (m_off & 0x4000) >> 11;
 250         if (m_len <= M4_MAX_LEN)
 251             *op++ = LZO_BYTE(M4_MARKER | k | (m_len - 2));
 252         else
 253         {
 254             m_len -= M4_MAX_LEN;
 255             *op++ = LZO_BYTE(M4_MARKER | k | 0);
 256             while (m_len > 255)
 257             {
 258                 m_len -= 255;
 259                 *op++ = 0;
 260             }
 261             assert(m_len > 0);
 262             *op++ = LZO_BYTE(m_len);
 263         }
 264 #if defined(LZO1Z)
 265         *op++ = LZO_BYTE(m_off >> 6);
 266         *op++ = LZO_BYTE(m_off << 2);
 267 #else
 268         *op++ = LZO_BYTE(m_off << 2);
 269         *op++ = LZO_BYTE(m_off >> 6);
 270 #endif
 271         c->m4_m++;
 272     }
 273
 274     c->last_m_len = x_len;
 275     c->last_m_off = x_off;
 276     return op;
 277 }
 278
 279
 280 static lzo_bytep
 281 STORE_RUN ( LZO_COMPRESS_T *c, lzo_bytep op, const lzo_bytep ii, lzo_uint t )
 282 {
 283     c->lit_bytes += (unsigned long) t;
 284
 285     if (op == c->out && t <= 238)
 286     {
 287         *op++ = LZO_BYTE(17 + t);
 288     }
 289     else if (t <= 3)
 290     {
 291 #if defined(LZO1Z)
 292         op[-1] |= LZO_BYTE(t);
 293 #else
 294         op[-2] |= LZO_BYTE(t);
 295 #endif
 296         c->lit1_r++;
 297     }
 298     else if (t <= 18)
 299     {
 300         *op++ = LZO_BYTE(t - 3);
 301         c->lit2_r++;
 302     }
 303     else
 304     {
 305         lzo_uint tt = t - 18;
 306
 307         *op++ = 0;
 308         while (tt > 255)
 309         {
 310             tt -= 255;
 311             *op++ = 0;
 312         }
 313         assert(tt > 0);
 314         *op++ = LZO_BYTE(tt);
 315         c->lit3_r++;
 316     }
 317     do *op++ = *ii++; while (--t > 0);
 318
 319     return op;
 320 }
 321
 322
 323 static lzo_bytep
 324 code_run ( LZO_COMPRESS_T *c, lzo_bytep op, const lzo_bytep ii,
 325            lzo_uint lit, lzo_uint m_len )
 326 {
 327     if (lit > 0)
 328     {
 329         assert(m_len >= 2);
 330         op = STORE_RUN(c,op,ii,lit);
 331         c->r1_m_len = m_len;
 332         c->r1_lit = lit;
 333     }
 334     else
 335     {
 336         assert(m_len >= 3);
 337         c->r1_m_len = 0;
 338         c->r1_lit = 0;
 339     }
 340
 341     return op;
 342 }
 343
 344
 345 /***********************************************************************
 346 //
 347 ************************************************************************/
 348
 349 static lzo_uint
 350 len_of_coded_match ( lzo_uint m_len, lzo_uint m_off, lzo_uint lit )
 351 {
 352     lzo_uint n = 4;
 353
 354     if (m_len < 2)
 355         return 0;
 356     if (m_len == 2)
 357         return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : 0;
 358     if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
 359         return 2;
 360     if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
 361         return 2;
 362     if (m_off <= M3_MAX_OFFSET)
 363     {
 364         if (m_len <= M3_MAX_LEN)
 365             return 3;
 366         m_len -= M3_MAX_LEN;
 367         while (m_len > 255)
 368         {
 369             m_len -= 255;
 370             n++;
 371         }
 372         return n;
 373     }
 374     if (m_off <= M4_MAX_OFFSET)
 375     {
 376         if (m_len <= M4_MAX_LEN)
 377             return 3;
 378         m_len -= M4_MAX_LEN;
 379         while (m_len > 255)
 380         {
 381             m_len -= 255;
 382             n++;
 383         }
 384         return n;
 385     }
 386     return 0;
 387 }
 388
 389
 390 static lzo_uint
 391 min_gain(lzo_uint ahead, lzo_uint lit1, lzo_uint lit2, lzo_uint l1, lzo_uint l2, lzo_uint l3)
 392 {
 393     lzo_uint lazy_match_min_gain;
 394
 395     assert (ahead >= 1);
 396     lazy_match_min_gain = ahead;
 397
 398 #if 0
 399     if (l3)
 400         lit2 -= ahead;
 401 #endif
 402
 403     if (lit1 <= 3)
 404         lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
 405     else if (lit1 <= 18)
 406         lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
 407
 408     lazy_match_min_gain += (l2 - l1) * 2;
 409     if (l3)
 410         lazy_match_min_gain -= (ahead - l3) * 2;
 411
 412     if ((lzo_int) lazy_match_min_gain < 0)
 413         lazy_match_min_gain = 0;
 414
 415 #if 0
 416     if (l1 == 2)
 417         if (lazy_match_min_gain == 0)
 418             lazy_match_min_gain = 1;
 419 #endif
 420
 421     return lazy_match_min_gain;
 422 }
 423
 424
 425 /***********************************************************************
 426 //
 427 ************************************************************************/
 428
 429 #if !defined(NDEBUG)
 430 static
 431 void assert_match( const lzo_swd_p swd, lzo_uint m_len, lzo_uint m_off )
 432 {
 433     const LZO_COMPRESS_T *c = swd->c;
 434     lzo_uint d_off;
 435
 436     assert(m_len >= 2);
 437     if (m_off <= (lzo_uint) (c->bp - c->in))
 438     {
 439         assert(c->bp - m_off + m_len < c->ip);
 440         assert(lzo_memcmp(c->bp, c->bp - m_off, m_len) == 0);
 441     }
 442     else
 443     {
 444         assert(swd->dict != NULL);
 445         d_off = m_off - (lzo_uint) (c->bp - c->in);
 446         assert(d_off <= swd->dict_len);
 447         if (m_len > d_off)
 448         {
 449             assert(lzo_memcmp(c->bp, swd->dict_end - d_off, d_off) == 0);
 450             assert(c->in + m_len - d_off < c->ip);
 451             assert(lzo_memcmp(c->bp + d_off, c->in, m_len - d_off) == 0);
 452         }
 453         else
 454         {
 455             assert(lzo_memcmp(c->bp, swd->dict_end - d_off, m_len) == 0);
 456         }
 457     }
 458 }
 459 #else
 460 #  define assert_match(a,b,c)   ((void)0)
 461 #endif
 462
 463
 464 #if defined(SWD_BEST_OFF)
 465
 466 static void
 467 better_match ( const lzo_swd_p swd, lzo_uint *m_len, lzo_uint *m_off )
 468 {
 469 #if defined(LZO1Z)
 470     const LZO_COMPRESS_T *c = swd->c;
 471 #endif
 472
 473     if (*m_len <= M2_MIN_LEN)
 474         return;
 475 #if defined(LZO1Z)
 476     if (*m_off == c->last_m_off && *m_len <= M2_MAX_LEN)
 477         return;
 478 #if 1
 479     if (*m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1 &&
 480         c->last_m_off && swd->best_off[*m_len-1] == c->last_m_off)
 481     {
 482         *m_len = *m_len - 1;
 483         *m_off = swd->best_off[*m_len];
 484         return;
 485     }
 486 #endif
 487 #endif
 488
 489     if (*m_off <= M2_MAX_OFFSET)
 490         return;
 491
 492 #if 1
 493     /* M3/M4 -> M2 */
 494     if (*m_off > M2_MAX_OFFSET &&
 495         *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1 &&
 496         swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET)
 497     {
 498         *m_len = *m_len - 1;
 499         *m_off = swd->best_off[*m_len];
 500         return;
 501     }
 502 #endif
 503
 504 #if 1
 505     /* M4 -> M2 */
 506     if (*m_off > M3_MAX_OFFSET &&
 507         *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2 &&
 508         swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET)
 509     {
 510         *m_len = *m_len - 2;
 511         *m_off = swd->best_off[*m_len];
 512         return;
 513     }
 514 #endif
 515
 516 #if 1
 517     /* M4 -> M3 */
 518     if (*m_off > M3_MAX_OFFSET &&
 519         *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1 &&
 520         swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET)
 521     {
 522         *m_len = *m_len - 1;
 523         *m_off = swd->best_off[*m_len];
 524     }
 525 #endif
 526 }
 527
 528 #endif
 529
 530
 531 /***********************************************************************
 532 //
 533 ************************************************************************/
 534
 535 LZO_PUBLIC(int)
 536 lzo1x_999_compress_internal ( const lzo_bytep in , lzo_uint  in_len,
 537                                     lzo_bytep out, lzo_uintp out_len,
 538                                     lzo_voidp wrkmem,
 539                               const lzo_bytep dict, lzo_uint dict_len,
 540                                     lzo_callback_p cb,
 541                                     int try_lazy_parm,
 542                                     lzo_uint good_length,
 543                                     lzo_uint max_lazy,
 544                                     lzo_uint nice_length,
 545                                     lzo_uint max_chain,
 546                                     lzo_uint32 flags )
 547 {
 548     lzo_bytep op;
 549     const lzo_bytep ii;
 550     lzo_uint lit;
 551     lzo_uint m_len, m_off;
 552     LZO_COMPRESS_T cc;
 553     LZO_COMPRESS_T * const c = &cc;
 554     lzo_swd_p const swd = (lzo_swd_p) wrkmem;
 555     lzo_uint try_lazy;
 556     int r;
 557
 558     /* sanity check */
 559 #if defined(LZO1X)
 560     LZO_COMPILE_TIME_ASSERT(LZO1X_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
 561 #elif defined(LZO1Y)
 562     LZO_COMPILE_TIME_ASSERT(LZO1Y_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
 563 #elif defined(LZO1Z)
 564     LZO_COMPILE_TIME_ASSERT(LZO1Z_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
 565 #else
 566 #  error
 567 #endif
 568
 569 /* setup parameter defaults */
 570     /* number of lazy match tries */
 571     try_lazy = (lzo_uint) try_lazy_parm;
 572     if (try_lazy_parm < 0)
 573         try_lazy = 1;
 574     /* reduce lazy match search if we already have a match with this length */
 575     if (good_length == 0)
 576         good_length = 32;
 577     /* do not try a lazy match if we already have a match with this length */
 578     if (max_lazy == 0)
 579         max_lazy = 32;
 580     /* stop searching for longer matches than this one */
 581     if (nice_length == 0)
 582         nice_length = 0;
 583     /* don't search more positions than this */
 584     if (max_chain == 0)
 585         max_chain = SWD_MAX_CHAIN;
 586
 587     c->init = 0;
 588     c->ip = c->in = in;
 589     c->in_end = in + in_len;
 590     c->out = out;
 591     c->cb = cb;
 592     c->m1a_m = c->m1b_m = c->m2_m = c->m3_m = c->m4_m = 0;
 593     c->lit1_r = c->lit2_r = c->lit3_r = 0;
 594
 595     op = out;
 596     ii = c->ip;             /* point to start of literal run */
 597     lit = 0;
 598     c->r1_lit = c->r1_m_len = 0;
 599
 600     r = init_match(c,swd,dict,dict_len,flags);
 601     if (r != 0)
 602         return r;
 603     if (max_chain > 0)
 604         swd->max_chain = max_chain;
 605     if (nice_length > 0)
 606         swd->nice_length = nice_length;
 607
 608     r = find_match(c,swd,0,0);
 609     if (r != 0)
 610         return r;
 611     while (c->look > 0)
 612     {
 613         lzo_uint ahead;
 614         lzo_uint max_ahead;
 615         lzo_uint l1, l2, l3;
 616
 617         c->codesize = pd(op, out);
 618
 619         m_len = c->m_len;
 620         m_off = c->m_off;
 621
 622         assert(c->bp == c->ip - c->look);
 623         assert(c->bp >= in);
 624         if (lit == 0)
 625             ii = c->bp;
 626         assert(ii + lit == c->bp);
 627         assert(swd->b_char == *(c->bp));
 628
 629         if ( m_len < 2 ||
 630             (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4)) ||
 631 #if 1
 632             /* Do not accept this match for compressed-data compatibility
 633              * with LZO v1.01 and before
 634              * [ might be a problem for decompress() and optimize() ]
 635              */
 636             (m_len == 2 && op == out) ||
 637 #endif
 638             (op == out && lit == 0))
 639         {
 640             /* a literal */
 641             m_len = 0;
 642         }
 643         else if (m_len == M2_MIN_LEN)
 644         {
 645             /* compression ratio improves if we code a literal in some cases */
 646             if (m_off > MX_MAX_OFFSET && lit >= 4)
 647                 m_len = 0;
 648         }
 649
 650         if (m_len == 0)
 651         {
 652     /* a literal */
 653             lit++;
 654             swd->max_chain = max_chain;
 655             r = find_match(c,swd,1,0);
 656             assert(r == 0); LZO_UNUSED(r);
 657             continue;
 658         }
 659
 660     /* a match */
 661 #if defined(SWD_BEST_OFF)
 662         if (swd->use_best_off)
 663             better_match(swd,&m_len,&m_off);
 664 #endif
 665         assert_match(swd,m_len,m_off);
 666
 667
 668         /* shall we try a lazy match ? */
 669         ahead = 0;
 670         if (try_lazy == 0 || m_len >= max_lazy)
 671         {
 672             /* no */
 673             l1 = 0;
 674             max_ahead = 0;
 675         }
 676         else
 677         {
 678             /* yes, try a lazy match */
 679             l1 = len_of_coded_match(m_len,m_off,lit);
 680             assert(l1 > 0);
 681 #if 1
 682             max_ahead = LZO_MIN(try_lazy, l1 - 1);
 683 #else
 684             max_ahead = LZO_MIN3(try_lazy, l1, m_len - 1);
 685 #endif
 686         }
 687
 688
 689         while (ahead < max_ahead && c->look > m_len)
 690         {
 691             lzo_uint lazy_match_min_gain;
 692
 693             if (m_len >= good_length)
 694                 swd->max_chain = max_chain >> 2;
 695             else
 696                 swd->max_chain = max_chain;
 697             r = find_match(c,swd,1,0);
 698             ahead++;
 699
 700             assert(r == 0); LZO_UNUSED(r);
 701             assert(c->look > 0);
 702             assert(ii + lit + ahead == c->bp);
 703
 704 #if defined(LZO1Z)
 705             if (m_off == c->last_m_off && c->m_off != c->last_m_off)
 706                 if (m_len >= M2_MIN_LEN && m_len <= M2_MAX_LEN)
 707                     c->m_len = 0;
 708 #endif
 709             if (c->m_len < m_len)
 710                 continue;
 711 #if 1
 712             if (c->m_len == m_len && c->m_off >= m_off)
 713                 continue;
 714 #endif
 715 #if defined(SWD_BEST_OFF)
 716             if (swd->use_best_off)
 717                 better_match(swd,&c->m_len,&c->m_off);
 718 #endif
 719             l2 = len_of_coded_match(c->m_len,c->m_off,lit+ahead);
 720             if (l2 == 0)
 721                 continue;
 722 #if 0
 723             if (c->m_len == m_len && l2 >= l1)
 724                 continue;
 725 #endif
 726
 727
 728 #if 1
 729             /* compressed-data compatibility [see above] */
 730             l3 = (op == out) ? 0 : len_of_coded_match(ahead,m_off,lit);
 731 #else
 732             l3 = len_of_coded_match(ahead,m_off,lit);
 733 #endif
 734
 735             lazy_match_min_gain = min_gain(ahead,lit,lit+ahead,l1,l2,l3);
 736             if (c->m_len >= m_len + lazy_match_min_gain)
 737             {
 738                 c->lazy++;
 739                 assert_match(swd,c->m_len,c->m_off);
 740
 741                 if (l3)
 742                 {
 743                     /* code previous run */
 744                     op = code_run(c,op,ii,lit,ahead);
 745                     lit = 0;
 746                     /* code shortened match */
 747                     op = code_match(c,op,ahead,m_off);
 748                 }
 749                 else
 750                 {
 751                     lit += ahead;
 752                     assert(ii + lit == c->bp);
 753                 }
 754                 goto lazy_match_done;
 755             }
 756         }
 757
 758
 759         assert(ii + lit + ahead == c->bp);
 760
 761         /* 1 - code run */
 762         op = code_run(c,op,ii,lit,m_len);
 763         lit = 0;
 764
 765         /* 2 - code match */
 766         op = code_match(c,op,m_len,m_off);
 767         swd->max_chain = max_chain;
 768         r = find_match(c,swd,m_len,1+ahead);
 769         assert(r == 0); LZO_UNUSED(r);
 770
 771 lazy_match_done: ;
 772     }
 773
 774
 775     /* store final run */
 776     if (lit > 0)
 777         op = STORE_RUN(c,op,ii,lit);
 778
 779 #if defined(LZO_EOF_CODE)
 780     *op++ = M4_MARKER | 1;
 781     *op++ = 0;
 782     *op++ = 0;
 783 #endif
 784
 785     c->codesize = pd(op, out);
 786     assert(c->textsize == in_len);
 787
 788     *out_len = pd(op, out);
 789
 790     if (c->cb && c->cb->nprogress)
 791         (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
 792
 793 #if 0
 794     printf("%ld %ld -> %ld  %ld: %ld %ld %ld %ld %ld  %ld: %ld %ld %ld  %ld\n",
 795         (long) c->textsize, (long) in_len, (long) c->codesize,
 796         c->match_bytes, c->m1a_m, c->m1b_m, c->m2_m, c->m3_m, c->m4_m,
 797         c->lit_bytes, c->lit1_r, c->lit2_r, c->lit3_r, c->lazy);
 798 #endif
 799     assert(c->lit_bytes + c->match_bytes == in_len);
 800
 801     return LZO_E_OK;
 802 }
 803
 804
 805 /***********************************************************************
 806 //
 807 ************************************************************************/
 808
 809 LZO_PUBLIC(int)
 810 lzo1x_999_compress_level    ( const lzo_bytep in , lzo_uint  in_len,
 811                                     lzo_bytep out, lzo_uintp out_len,
 812                                     lzo_voidp wrkmem,
 813                               const lzo_bytep dict, lzo_uint dict_len,
 814                                     lzo_callback_p cb,
 815                                     int compression_level )
 816 {
 817     static const struct
 818     {
 819         int try_lazy_parm;
 820         lzo_uint good_length;
 821         lzo_uint max_lazy;
 822         lzo_uint nice_length;
 823         lzo_uint max_chain;
 824         lzo_uint32 flags;
 825     } c[9] = {
 826         /* faster compression */
 827         {   0,     0,     0,     8,    4,   0 },
 828         {   0,     0,     0,    16,    8,   0 },
 829         {   0,     0,     0,    32,   16,   0 },
 830         {   1,     4,     4,    16,   16,   0 },
 831         {   1,     8,    16,    32,   32,   0 },
 832         {   1,     8,    16,   128,  128,   0 },
 833         {   2,     8,    32,   128,  256,   0 },
 834         {   2,    32,   128, SWD_F, 2048,   1 },
 835         {   2, SWD_F, SWD_F, SWD_F, 4096,   1 }
 836         /* max. compression */
 837     };
 838
 839     if (compression_level < 1 || compression_level > 9)
 840         return LZO_E_ERROR;
 841
 842     compression_level -= 1;
 843     return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
 844                                        dict, dict_len, cb,
 845                                        c[compression_level].try_lazy_parm,
 846                                        c[compression_level].good_length,
 847                                        c[compression_level].max_lazy,
 848 #if 0
 849                                        c[compression_level].nice_length,
 850 #else
 851                                        0,
 852 #endif
 853                                        c[compression_level].max_chain,
 854                                        c[compression_level].flags);
 855 }
 856
 857
 858 /***********************************************************************
 859 //
 860 ************************************************************************/
 861
 862 LZO_PUBLIC(int)
 863 lzo1x_999_compress_dict     ( const lzo_bytep in , lzo_uint  in_len,
 864                                     lzo_bytep out, lzo_uintp out_len,
 865                                     lzo_voidp wrkmem,
 866                               const lzo_bytep dict, lzo_uint dict_len )
 867 {
 868     return lzo1x_999_compress_level(in, in_len, out, out_len, wrkmem,
 869                                     dict, dict_len, 0, 8);
 870 }
 871
 872 LZO_PUBLIC(int)
 873 lzo1x_999_compress  ( const lzo_bytep in , lzo_uint  in_len,
 874                             lzo_bytep out, lzo_uintp out_len,
 875                             lzo_voidp wrkmem )
 876 {
 877     return lzo1x_999_compress_level(in, in_len, out, out_len, wrkmem,
 878                                     NULL, 0, (lzo_callback_p) 0, 8);
 879 }
 880
 881
 882 /*
 883 vi:ts=4:et
 884 */
 885