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 (at) 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 871