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 */ 103LZO_EXTERN(int) 104lzo1x_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 121static lzo_bytep 122code_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 280static lzo_bytep 281STORE_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 323static lzo_bytep 324code_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 349static lzo_uint 350len_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 390static lzo_uint 391min_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) 430static 431void 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 466static void 467better_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 535LZO_PUBLIC(int) 536lzo1x_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 771lazy_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 809LZO_PUBLIC(int) 810lzo1x_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 862LZO_PUBLIC(int) 863lzo1x_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 872LZO_PUBLIC(int) 873lzo1x_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/* 883vi:ts=4:et 884*/ 885 886