archival/libarchive/lzo1x_9x.c

   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
  59 typedef 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)      (* (bb__aliased_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
 103 typedef 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
 159 static 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 ************************************************************************/
 202 static 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 ************************************************************************/
 226 static 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 ************************************************************************/
 249 static 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 ************************************************************************/
 280 static 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
 342 static 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 ************************************************************************/
 371 static 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 ************************************************************************/
 435 static 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 ************************************************************************/
 456 static 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 */
 492 static 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 ************************************************************************/
 504 static 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
 572 static 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
 598 static 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 ************************************************************************/
 616 static 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
 646 static 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
 675 static void better_match(const lzo_swd_p swd,
 676                         unsigned *m_len, unsigned *m_off)
 677 {
 678         if (*m_len <= M2_MIN_LEN)
 679                 return;
 680
 681         if (*m_off <= M2_MAX_OFFSET)
 682                 return;
 683
 684         /* M3/M4 -> M2 */
 685         if (*m_off > M2_MAX_OFFSET
 686          && *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1
 687          && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET
 688         ) {
 689                 *m_len = *m_len - 1;
 690                 *m_off = swd->best_off[*m_len];
 691                 return;
 692         }
 693
 694         /* M4 -> M2 */
 695         if (*m_off > M3_MAX_OFFSET
 696          && *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2
 697          && swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET
 698         ) {
 699                 *m_len = *m_len - 2;
 700                 *m_off = swd->best_off[*m_len];
 701                 return;
 702         }
 703         /* M4 -> M3 */
 704         if (*m_off > M3_MAX_OFFSET
 705          && *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1
 706          && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET
 707         ) {
 708                 *m_len = *m_len - 1;
 709                 *m_off = swd->best_off[*m_len];
 710         }
 711 }
 712
 713 #endif
 714
 715
 716 /***********************************************************************
 717 //
 718 ************************************************************************/
 719 static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
 720                 uint8_t *out, unsigned *out_len,
 721                 void *wrkmem,
 722                 unsigned good_length,
 723                 unsigned max_lazy,
 724                 unsigned max_chain,
 725                 uint32_t use_best_off)
 726 {
 727         uint8_t *op;
 728         const uint8_t *ii;
 729         unsigned lit;
 730         unsigned m_len, m_off;
 731         lzo1x_999_t cc;
 732         lzo1x_999_t *const c = &cc;
 733         const lzo_swd_p swd = (lzo_swd_p) wrkmem;
 734         int r;
 735
 736         c->init = 0;
 737         c->ip = c->in = in;
 738         c->in_end = in + in_len;
 739         c->out = out;
 740
 741         op = out;
 742         ii = c->ip;             /* point to start of literal run */
 743         lit = 0;
 744         c->r1_lit = 0;
 745
 746         r = init_match(c, swd, use_best_off);
 747         if (r != 0)
 748                 return r;
 749         swd->max_chain = max_chain;
 750
 751         r = find_match(c, swd, 0, 0);
 752         if (r != 0)
 753                 return r;
 754
 755         while (c->look > 0) {
 756                 unsigned ahead;
 757                 unsigned max_ahead;
 758                 int l1, l2, l3;
 759
 760                 m_len = c->m_len;
 761                 m_off = c->m_off;
 762
 763                 assert(c->bp == c->ip - c->look);
 764                 assert(c->bp >= in);
 765                 if (lit == 0)
 766                         ii = c->bp;
 767                 assert(ii + lit == c->bp);
 768                 assert(swd->b_char == *(c->bp));
 769
 770                 if (m_len < 2
 771                  || (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4))
 772                     /* Do not accept this match for compressed-data compatibility
 773                      * with LZO v1.01 and before
 774                      * [ might be a problem for decompress() and optimize() ]
 775                      */
 776                  || (m_len == 2 && op == out)
 777                  || (op == out && lit == 0)
 778                 ) {
 779                         /* a literal */
 780                         m_len = 0;
 781                 }
 782                 else if (m_len == M2_MIN_LEN) {
 783                         /* compression ratio improves if we code a literal in some cases */
 784                         if (m_off > MX_MAX_OFFSET && lit >= 4)
 785                                 m_len = 0;
 786                 }
 787
 788                 if (m_len == 0) {
 789                         /* a literal */
 790                         lit++;
 791                         swd->max_chain = max_chain;
 792                         r = find_match(c, swd, 1, 0);
 793                         assert(r == 0);
 794                         continue;
 795                 }
 796
 797                 /* a match */
 798 #if defined(SWD_BEST_OFF)
 799                 if (swd->use_best_off)
 800                         better_match(swd, &m_len, &m_off);
 801 #endif
 802
 803                 /* shall we try a lazy match ? */
 804                 ahead = 0;
 805                 if (m_len >= max_lazy) {
 806                         /* no */
 807                         l1 = 0;
 808                         max_ahead = 0;
 809                 } else {
 810                         /* yes, try a lazy match */
 811                         l1 = len_of_coded_match(m_len, m_off, lit);
 812                         assert(l1 > 0);
 813                         max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
 814                 }
 815
 816
 817                 while (ahead < max_ahead && c->look > m_len) {
 818                         int lazy_match_min_gain;
 819
 820                         if (m_len >= good_length)
 821                                 swd->max_chain = max_chain >> 2;
 822                         else
 823                                 swd->max_chain = max_chain;
 824                         r = find_match(c, swd, 1, 0);
 825                         ahead++;
 826
 827                         assert(r == 0);
 828                         assert(c->look > 0);
 829                         assert(ii + lit + ahead == c->bp);
 830
 831                         if (c->m_len < m_len)
 832                                 continue;
 833                         if (c->m_len == m_len && c->m_off >= m_off)
 834                                 continue;
 835 #if defined(SWD_BEST_OFF)
 836                         if (swd->use_best_off)
 837                                 better_match(swd, &c->m_len, &c->m_off);
 838 #endif
 839                         l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead);
 840                         if (l2 < 0)
 841                                 continue;
 842
 843                         /* compressed-data compatibility [see above] */
 844                         l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit);
 845
 846                         lazy_match_min_gain = min_gain(ahead, lit, lit+ahead, l1, l2, l3);
 847                         if (c->m_len >= m_len + lazy_match_min_gain) {
 848                                 if (l3 > 0) {
 849                                         /* code previous run */
 850                                         op = code_run(c, op, ii, lit);
 851                                         lit = 0;
 852                                         /* code shortened match */
 853                                         op = code_match(c, op, ahead, m_off);
 854                                 } else {
 855                                         lit += ahead;
 856                                         assert(ii + lit == c->bp);
 857                                 }
 858                                 goto lazy_match_done;
 859                         }
 860                 }
 861
 862                 assert(ii + lit + ahead == c->bp);
 863
 864                 /* 1 - code run */
 865                 op = code_run(c, op, ii, lit);
 866                 lit = 0;
 867
 868                 /* 2 - code match */
 869                 op = code_match(c, op, m_len, m_off);
 870                 swd->max_chain = max_chain;
 871                 r = find_match(c, swd, m_len, 1+ahead);
 872                 assert(r == 0);
 873
 874  lazy_match_done: ;
 875         }
 876
 877         /* store final run */
 878         if (lit > 0)
 879                 op = STORE_RUN(c, op, ii, lit);
 880
 881 #if defined(LZO_EOF_CODE)
 882         *op++ = M4_MARKER | 1;
 883         *op++ = 0;
 884         *op++ = 0;
 885 #endif
 886
 887         *out_len = op - out;
 888
 889         return LZO_E_OK;
 890 }
 891
 892
 893 /***********************************************************************
 894 //
 895 ************************************************************************/
 896 int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
 897                 uint8_t *out, unsigned *out_len,
 898                 void *wrkmem,
 899                 int compression_level)
 900 {
 901         static const struct {
 902                 uint16_t good_length;
 903                 uint16_t max_lazy;
 904                 uint16_t max_chain;
 905                 uint16_t use_best_off;
 906         } c[3] = {
 907                 {     8,    32,  256,   0 },
 908                 {    32,   128, 2048,   1 },
 909                 { SWD_F, SWD_F, 4096,   1 }       /* max. compression */
 910         };
 911
 912         if (compression_level < 7 || compression_level > 9)
 913                 return LZO_E_ERROR;
 914
 915         compression_level -= 7;
 916         return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
 917                                         c[compression_level].good_length,
 918                                         c[compression_level].max_lazy,
 919                                         c[compression_level].max_chain,
 920                                         c[compression_level].use_best_off);
 921 }