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