1/* lzo1a.c -- implementation of the LZO1A 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#include "lzo_conf.h" 42#include "lzo/lzo1a.h" 43 44 45/*********************************************************************** 46// The next two defines can be changed to customize LZO1A. 47// The default version is LZO1A-5/1. 48************************************************************************/ 49 50/* run bits (3 - 5) - the compressor and the decompressor 51 * must use the same value. */ 52#if !defined(RBITS) 53# define RBITS 5 54#endif 55 56/* compression level (1 - 9) - this only affects the compressor. 57 * 1 is fastest, 9 is best compression ratio 58 */ 59#if !defined(CLEVEL) 60# define CLEVEL 1 /* fastest by default */ 61#endif 62 63 64/* Collect statistics */ 65#if 0 && !defined(LZO_COLLECT_STATS) 66# define LZO_COLLECT_STATS 67#endif 68 69 70/*********************************************************************** 71// You should not have to change anything below this line. 72************************************************************************/ 73 74/* check configuration */ 75#if (RBITS < 3 || RBITS > 5) 76# error "invalid RBITS" 77#endif 78#if (CLEVEL < 1 || CLEVEL > 9) 79# error "invalid CLEVEL" 80#endif 81 82 83/*********************************************************************** 84// internal configuration 85// all of these affect compression only 86************************************************************************/ 87 88/* choose the hashing strategy */ 89#ifndef LZO_HASH 90#define LZO_HASH LZO_HASH_LZO_INCREMENTAL_A 91#endif 92#define D_INDEX1(d,p) d = DM(DMUL(0x21,DX2(p,5,5)) >> 5) 93#define D_INDEX2(d,p) d = d ^ D_MASK 94 95#include "lzo1a_de.h" 96#include "stats1a.h" 97 98 99/* check other constants */ 100#if (LBITS < 5 || LBITS > 8) 101# error "invalid LBITS" 102#endif 103 104 105#if defined(LZO_COLLECT_STATS) 106 static lzo1a_stats_t lzo_statistics; 107 lzo1a_stats_t *lzo1a_stats = &lzo_statistics; 108# define lzo_stats lzo1a_stats 109#endif 110 111 112/*********************************************************************** 113// get algorithm info, return memory required for compression 114************************************************************************/ 115 116LZO_EXTERN(lzo_uint) lzo1a_info ( int *rbits, int *clevel ); 117 118LZO_PUBLIC(lzo_uint) 119lzo1a_info ( int *rbits, int *clevel ) 120{ 121 if (rbits) 122 *rbits = RBITS; 123 if (clevel) 124 *clevel = CLEVEL; 125 return D_SIZE * lzo_sizeof(lzo_bytep); 126} 127 128 129/*********************************************************************** 130// LZO1A decompress a block of data. 131// 132// Could be easily translated into assembly code. 133************************************************************************/ 134 135LZO_PUBLIC(int) 136lzo1a_decompress ( const lzo_bytep in , lzo_uint in_len, 137 lzo_bytep out, lzo_uintp out_len, 138 lzo_voidp wrkmem ) 139{ 140 register lzo_bytep op; 141 register const lzo_bytep ip; 142 register lzo_uint t; 143 register const lzo_bytep m_pos; 144 const lzo_bytep const ip_end = in + in_len; 145 146 LZO_UNUSED(wrkmem); 147 148 op = out; 149 ip = in; 150 while (ip < ip_end) 151 { 152 t = *ip++; /* get marker */ 153 LZO_STATS(lzo_stats->marker[t]++); 154 155 if (t == 0) /* a R0 literal run */ 156 { 157 t = *ip++; 158 if (t >= R0FAST - R0MIN) /* a long R0 run */ 159 { 160 t -= R0FAST - R0MIN; 161 if (t == 0) 162 t = R0FAST; 163 else 164 { 165#if 0 166 t = 256u << ((unsigned) t); 167#else 168 /* help the optimizer */ 169 lzo_uint tt = 256; 170 do tt <<= 1; while (--t > 0); 171 t = tt; 172#endif 173 } 174 MEMCPY8_DS(op,ip,t); 175 continue; 176 } 177 t += R0MIN; 178 goto literal; 179 } 180 else if (t < R0MIN) /* a short literal run */ 181 { 182literal: 183 MEMCPY_DS(op,ip,t); 184 185 /* after a literal a match must follow */ 186 while (ip < ip_end) 187 { 188 t = *ip++; /* get R1 marker */ 189 if (t >= R0MIN) 190 goto match; 191 192 /* R1 match - a context sensitive 3 byte match + 1 byte literal */ 193 assert((t & OMASK) == t); 194 m_pos = op - MIN_OFFSET; 195 m_pos -= t | (((lzo_uint) *ip++) << OBITS); 196 assert(m_pos >= out); assert(m_pos < op); 197 *op++ = *m_pos++; 198 *op++ = *m_pos++; 199 *op++ = *m_pos++; 200 *op++ = *ip++; 201 } 202 } 203 else /* a match */ 204 { 205match: 206 /* get match offset */ 207 m_pos = op - MIN_OFFSET; 208 m_pos -= (t & OMASK) | (((lzo_uint) *ip++) << OBITS); 209 assert(m_pos >= out); assert(m_pos < op); 210 211 /* get match len */ 212 if (t < ((MSIZE - 1) << OBITS)) /* a short match */ 213 { 214 t >>= OBITS; 215 *op++ = *m_pos++; 216 *op++ = *m_pos++; 217 MEMCPY_DS(op,m_pos,t); 218 } 219 else /* a long match */ 220 { 221#if (LBITS < 8) 222 t = (MIN_MATCH_LONG - THRESHOLD) + ((lzo_uint)(*ip++) & LMASK); 223#else 224 t = (MIN_MATCH_LONG - THRESHOLD) + (lzo_uint)(*ip++); 225#endif 226 *op++ = *m_pos++; 227 *op++ = *m_pos++; 228 MEMCPY_DS(op,m_pos,t); 229#if (LBITS < 8) 230 /* a very short literal following a long match */ 231 t = ip[-1] >> LBITS; 232 if (t) do 233 *op++ = *ip++; 234 while (--t); 235#endif 236 } 237 } 238 } 239 240 *out_len = pd(op, out); 241 242 /* the next line is the only check in the decompressor */ 243 return (ip == ip_end ? LZO_E_OK : 244 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN)); 245} 246 247 248 249/*********************************************************************** 250// LZO1A compress a block of data. 251// 252// I apologize for the spaghetti code, but it really helps the optimizer. 253************************************************************************/ 254 255#include "lzo1a_cr.ch" 256 257static int 258do_compress ( const lzo_bytep in , lzo_uint in_len, 259 lzo_bytep out, lzo_uintp out_len, 260 lzo_voidp wrkmem ) 261{ 262 register const lzo_bytep ip; 263#if defined(__LZO_HASH_INCREMENTAL) 264 lzo_xint dv; 265#endif 266 const lzo_bytep m_pos; 267 lzo_bytep op; 268 const lzo_bytep const ip_end = in+in_len - DVAL_LEN - MIN_MATCH_LONG; 269 const lzo_bytep const in_end = in+in_len - DVAL_LEN; 270 const lzo_bytep ii; 271 lzo_dict_p const dict = (lzo_dict_p) wrkmem; 272 const lzo_bytep r1 = ip_end; /* pointer for R1 match (none yet) */ 273#if (LBITS < 8) 274 const lzo_bytep im = ip_end; /* pointer to last match start */ 275#endif 276 277#if !defined(NDEBUG) 278 const lzo_bytep m_pos_sav; 279#endif 280 281 op = out; 282 ip = in; 283 ii = ip; /* point to start of current literal run */ 284 285 /* init dictionary */ 286#if defined(LZO_DETERMINISTIC) 287 BZERO8_PTR(wrkmem,sizeof(lzo_dict_t),D_SIZE); 288#endif 289 290 DVAL_FIRST(dv,ip); UPDATE_D(dict,0,dv,ip,in); ip++; 291 DVAL_NEXT(dv,ip); 292 293 do { 294 lzo_uint m_off; 295 lzo_uint dindex; 296 297 DINDEX1(dindex,ip); 298 GINDEX(m_pos,m_off,dict,dindex,in); 299 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,MAX_OFFSET)) 300 goto literal; 301 if (m_pos[0] == ip[0] && m_pos[1] == ip[1] && m_pos[2] == ip[2]) 302 goto match; 303 DINDEX2(dindex,ip); 304 GINDEX(m_pos,m_off,dict,dindex,in); 305 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,MAX_OFFSET)) 306 goto literal; 307 if (m_pos[0] == ip[0] && m_pos[1] == ip[1] && m_pos[2] == ip[2]) 308 goto match; 309 goto literal; 310 311literal: 312 UPDATE_I(dict,0,dindex,ip,in); 313 if (++ip >= ip_end) 314 break; 315 continue; 316 317match: 318 UPDATE_I(dict,0,dindex,ip,in); 319#if !defined(NDEBUG) && defined(LZO_DICT_USE_PTR) 320 assert(m_pos == NULL || m_pos >= in); 321 m_pos_sav = m_pos; 322#endif 323 m_pos += 3; 324 { 325 /* we have found a match (of at least length 3) */ 326 327#if !defined(NDEBUG) && !defined(LZO_DICT_USE_PTR) 328 assert((m_pos_sav = ip - m_off) == (m_pos - 3)); 329#endif 330 331 assert(m_pos >= in); 332 assert(ip < ip_end); 333 334 /* 1) store the current literal run */ 335 if (pd(ip,ii) > 0) 336 { 337 lzo_uint t = pd(ip,ii); 338 339 if (ip - r1 == MIN_MATCH + 1) 340 { 341 /* Code a context sensitive R1 match. 342 * This is tricky and somewhat difficult to explain: 343 * multiplex a literal run of length 1 into the previous 344 * short match of length MIN_MATCH. 345 * The key idea is: 346 * - after a short run a match MUST follow 347 * - therefore the value m = 000 in the mmmooooo marker is free 348 * - use 000ooooo to indicate a MIN_MATCH match (this 349 * is already coded) plus a 1 byte literal 350 */ 351 assert(t == 1); 352 /* modify marker byte */ 353 assert((op[-2] >> OBITS) == (MIN_MATCH - THRESHOLD)); 354 op[-2] &= OMASK; 355 assert((op[-2] >> OBITS) == 0); 356 /* copy 1 literal */ 357 *op++ = *ii; 358 LZO_STATS(lzo_stats->r1_matches++); 359 r1 = ip; /* set new R1 pointer */ 360 } 361 else if (t < R0MIN) 362 { 363 /* inline the copying of a short run */ 364#if (LBITS < 8) 365 if (t < (1 << (8-LBITS)) && ii - im >= MIN_MATCH_LONG) 366 { 367 /* Code a very short literal run into the 368 * previous long match length byte. 369 */ 370 LZO_STATS(lzo_stats->lit_runs_after_long_match++); 371 LZO_STATS(lzo_stats->lit_run_after_long_match[t]++); 372 assert(ii - im <= MAX_MATCH_LONG); 373 assert((op[-1] >> LBITS) == 0); 374 op[-1] |= t << LBITS; 375 MEMCPY_DS(op, ii, t); 376 } 377 else 378#endif 379 { 380 LZO_STATS(lzo_stats->lit_runs++); 381 LZO_STATS(lzo_stats->lit_run[t]++); 382 *op++ = LZO_BYTE(t); 383 MEMCPY_DS(op, ii, t); 384 r1 = ip; /* set new R1 pointer */ 385 } 386 } 387 else if (t < R0FAST) 388 { 389 /* inline the copying of a short R0 run */ 390 LZO_STATS(lzo_stats->r0short_runs++); 391 *op++ = 0; *op++ = LZO_BYTE(t - R0MIN); 392 MEMCPY_DS(op, ii, t); 393 r1 = ip; /* set new R1 pointer */ 394 } 395 else 396 op = store_run(op,ii,t); 397 } 398#if (LBITS < 8) 399 im = ip; 400#endif 401 402 403 /* 2) compute match len */ 404 ii = ip; /* point to start of current match */ 405 406 /* we already matched MIN_MATCH bytes, 407 * m_pos also already advanced MIN_MATCH bytes */ 408 ip += MIN_MATCH; 409 assert(m_pos < ip); 410 411 /* try to match another MIN_MATCH_LONG - MIN_MATCH bytes 412 * to see if we get a long match */ 413 414#define PS *m_pos++ != *ip++ 415 416#if (MIN_MATCH_LONG - MIN_MATCH == 2) /* MBITS == 2 */ 417 if (PS || PS) 418#elif (MIN_MATCH_LONG - MIN_MATCH == 6) /* MBITS == 3 */ 419 if (PS || PS || PS || PS || PS || PS) 420#elif (MIN_MATCH_LONG - MIN_MATCH == 14) /* MBITS == 4 */ 421 if (PS || PS || PS || PS || PS || PS || PS || 422 PS || PS || PS || PS || PS || PS || PS) 423#elif (MIN_MATCH_LONG - MIN_MATCH == 30) /* MBITS == 5 */ 424 if (PS || PS || PS || PS || PS || PS || PS || PS || 425 PS || PS || PS || PS || PS || PS || PS || PS || 426 PS || PS || PS || PS || PS || PS || PS || PS || 427 PS || PS || PS || PS || PS || PS) 428#else 429# error "MBITS not yet implemented" 430#endif 431 { 432 /* we've found a short match */ 433 lzo_uint m_len; 434 435 /* 2a) compute match parameters */ 436 assert(ip-m_pos == (int)m_off); 437 --ip; /* ran one too far, point back to non-match */ 438 m_len = pd(ip, ii); 439 assert(m_len >= MIN_MATCH_SHORT); 440 assert(m_len <= MAX_MATCH_SHORT); 441 assert(m_off >= MIN_OFFSET); 442 assert(m_off <= MAX_OFFSET); 443 assert(ii-m_off == m_pos_sav); 444 assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0); 445 m_off -= MIN_OFFSET; 446 447 /* 2b) code a short match */ 448 /* code short match len + low offset bits */ 449 *op++ = LZO_BYTE(((m_len - THRESHOLD) << OBITS) | 450 (m_off & OMASK)); 451 /* code high offset bits */ 452 *op++ = LZO_BYTE(m_off >> OBITS); 453 454 455#if defined(LZO_COLLECT_STATS) 456 lzo_stats->short_matches++; 457 lzo_stats->short_match[m_len]++; 458 if (m_off < OSIZE) 459 lzo_stats->short_match_offset_osize[m_len]++; 460 if (m_off < 256) 461 lzo_stats->short_match_offset_256[m_len]++; 462 if (m_off < 1024) 463 lzo_stats->short_match_offset_1024[m_len]++; 464#endif 465 466 467 /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */ 468 469#define SI /* nothing */ 470#define DI ++ii; DVAL_NEXT(dv,ii); UPDATE_D(dict,0,dv,ii,in); 471#define XI assert(ii < ip); ii = ip; DVAL_FIRST(dv,(ip)); 472 473#if (CLEVEL == 9) || (CLEVEL >= 7 && MBITS <= 4) || (CLEVEL >= 5 && MBITS <= 3) 474 /* Insert the whole match (ii+1)..(ip-1) into dictionary. */ 475 ++ii; 476 do { 477 DVAL_NEXT(dv,ii); 478 UPDATE_D(dict,0,dv,ii,in); 479 } while (++ii < ip); 480 DVAL_NEXT(dv,ii); 481 assert(ii == ip); 482 DVAL_ASSERT(dv,ip); 483#elif (CLEVEL >= 3) 484 SI DI DI XI 485#elif (CLEVEL >= 2) 486 SI DI XI 487#else 488 XI 489#endif 490 491 } 492 else 493 { 494 /* we've found a long match - see how far we can still go */ 495 const lzo_bytep end; 496 lzo_uint m_len; 497 498 assert(ip <= in_end); 499 assert(ii == ip - MIN_MATCH_LONG); 500 501 if (pd(in_end,ip) <= (MAX_MATCH_LONG - MIN_MATCH_LONG)) 502 end = in_end; 503 else 504 { 505 end = ip + (MAX_MATCH_LONG - MIN_MATCH_LONG); 506 assert(end < in_end); 507 } 508 509 while (ip < end && *m_pos == *ip) 510 m_pos++, ip++; 511 assert(ip <= in_end); 512 513 /* 2a) compute match parameters */ 514 m_len = pd(ip, ii); 515 assert(m_len >= MIN_MATCH_LONG); 516 assert(m_len <= MAX_MATCH_LONG); 517 assert(m_off >= MIN_OFFSET); 518 assert(m_off <= MAX_OFFSET); 519 assert(ii-m_off == m_pos_sav); 520 assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0); 521 assert(pd(ip,m_pos) == m_off); 522 m_off -= MIN_OFFSET; 523 524 /* 2b) code the long match */ 525 /* code long match flag + low offset bits */ 526 *op++ = LZO_BYTE(((MSIZE - 1) << OBITS) | (m_off & OMASK)); 527 /* code high offset bits */ 528 *op++ = LZO_BYTE(m_off >> OBITS); 529 /* code match len */ 530 *op++ = LZO_BYTE(m_len - MIN_MATCH_LONG); 531 532 533#if defined(LZO_COLLECT_STATS) 534 lzo_stats->long_matches++; 535 lzo_stats->long_match[m_len]++; 536#endif 537 538 539 /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */ 540#if (CLEVEL == 9) 541 /* Insert the whole match (ii+1)..(ip-1) into dictionary. */ 542 /* This is not recommended because it is slow. */ 543 ++ii; 544 do { 545 DVAL_NEXT(dv,ii); 546 UPDATE_D(dict,0,dv,ii,in); 547 } while (++ii < ip); 548 DVAL_NEXT(dv,ii); 549 assert(ii == ip); 550 DVAL_ASSERT(dv,ip); 551#elif (CLEVEL >= 8) 552 SI DI DI DI DI DI DI DI DI XI 553#elif (CLEVEL >= 7) 554 SI DI DI DI DI DI DI DI XI 555#elif (CLEVEL >= 6) 556 SI DI DI DI DI DI DI XI 557#elif (CLEVEL >= 5) 558 SI DI DI DI DI XI 559#elif (CLEVEL >= 4) 560 SI DI DI DI XI 561#elif (CLEVEL >= 3) 562 SI DI DI XI 563#elif (CLEVEL >= 2) 564 SI DI XI 565#else 566 XI 567#endif 568 } 569 570 /* ii now points to the start of the next literal run */ 571 assert(ii == ip); 572 } 573 574 } while (ip < ip_end); 575 576 assert(ip <= in_end); 577 578 579#if defined(LZO_RETURN_IF_NOT_COMPRESSIBLE) 580 /* return -1 if op == out to indicate that we 581 * couldn't compress and didn't copy anything. 582 */ 583 if (op == out) 584 { 585 *out_len = 0; 586 return LZO_E_NOT_COMPRESSIBLE; 587 } 588#endif 589 590 /* store the final literal run */ 591 if (pd(in_end+DVAL_LEN,ii) > 0) 592 op = store_run(op,ii,pd(in_end+DVAL_LEN,ii)); 593 594 *out_len = pd(op, out); 595 return 0; /* compression went ok */ 596} 597 598 599/*********************************************************************** 600// LZO1A compress public entry point. 601************************************************************************/ 602 603LZO_PUBLIC(int) 604lzo1a_compress ( const lzo_bytep in , lzo_uint in_len, 605 lzo_bytep out, lzo_uintp out_len, 606 lzo_voidp wrkmem ) 607{ 608 int r = LZO_E_OK; 609 610 611#if defined(LZO_COLLECT_STATS) 612 lzo_memset(lzo_stats,0,sizeof(*lzo_stats)); 613 lzo_stats->rbits = RBITS; 614 lzo_stats->clevel = CLEVEL; 615 lzo_stats->dbits = DBITS; 616 lzo_stats->lbits = LBITS; 617 lzo_stats->min_match_short = MIN_MATCH_SHORT; 618 lzo_stats->max_match_short = MAX_MATCH_SHORT; 619 lzo_stats->min_match_long = MIN_MATCH_LONG; 620 lzo_stats->max_match_long = MAX_MATCH_LONG; 621 lzo_stats->min_offset = MIN_OFFSET; 622 lzo_stats->max_offset = MAX_OFFSET; 623 lzo_stats->r0min = R0MIN; 624 lzo_stats->r0fast = R0FAST; 625 lzo_stats->r0max = R0MAX; 626 lzo_stats->in_len = in_len; 627#endif 628 629 630 /* don't try to compress a block that's too short */ 631 if (in_len <= 0) 632 *out_len = 0; 633 else if (in_len <= MIN_MATCH_LONG + DVAL_LEN + 1) 634 { 635#if defined(LZO_RETURN_IF_NOT_COMPRESSIBLE) 636 r = LZO_E_NOT_COMPRESSIBLE; 637#else 638 *out_len = pd(store_run(out,in,in_len), out); 639#endif 640 } 641 else 642 r = do_compress(in,in_len,out,out_len,wrkmem); 643 644 645#if defined(LZO_COLLECT_STATS) 646 lzo_stats->short_matches -= lzo_stats->r1_matches; 647 lzo_stats->short_match[MIN_MATCH] -= lzo_stats->r1_matches; 648 lzo_stats->out_len = *out_len; 649#endif 650 651 return r; 652} 653 654 655/* 656vi:ts=4:et 657*/ 658