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