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