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 */ 100LZO_EXTERN(int) 101lzo1x_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 118static lzo_bytep 119code_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 277static lzo_bytep 278STORE_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 320static lzo_bytep 321code_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 346static int 347len_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 387static lzo_int 388min_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) 427static 428void 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 463static void 464better_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 532LZO_PUBLIC(int) 533lzo1x_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 767lazy_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 805LZO_PUBLIC(int) 806lzo1x_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 858LZO_PUBLIC(int) 859lzo1x_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 868LZO_PUBLIC(int) 869lzo1x_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/* 879vi:ts=4:et 880*/ 881 882