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 #ifdef SWD_BEST_OFF
 470         if (s->use_best_off)
 471                 memset(s->best_pos, 0, sizeof(s->best_pos));
 472 #endif
 473         swd_findbest(s);
 474         c->m_len = s->m_len;
 475         c->m_off = s->m_off;
 476
 477         swd_getbyte(s);
 478
 479         if (s->b_char < 0) {
 480                 c->look = 0;
 481                 c->m_len = 0;
 482         } else {
 483                 c->look = s->look + 1;
 484         }
 485         c->bp = c->ip - c->look;
 486
 487         return LZO_E_OK;
 488 }
 489
 490 /* this is a public functions, but there is no prototype in a header file */
 491 static int lzo1x_999_compress_internal(const uint8_t *in , unsigned in_len,
 492                 uint8_t *out, unsigned *out_len,
 493                 void *wrkmem,
 494                 unsigned good_length,
 495                 unsigned max_lazy,
 496                 unsigned max_chain,
 497                 uint32_t use_best_off);
 498
 499
 500 /***********************************************************************
 501 //
 502 ************************************************************************/
 503 static uint8_t *code_match(lzo1x_999_t *c,
 504                 uint8_t *op, unsigned m_len, unsigned m_off)
 505 {
 506         assert(op > c->out);
 507         if (m_len == 2) {
 508                 assert(m_off <= M1_MAX_OFFSET);
 509                 assert(c->r1_lit > 0);
 510                 assert(c->r1_lit < 4);
 511                 m_off -= 1;
 512                 *op++ = M1_MARKER | ((m_off & 3) << 2);
 513                 *op++ = m_off >> 2;
 514         } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
 515                 assert(m_len >= 3);
 516                 m_off -= 1;
 517                 *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
 518                 *op++ = m_off >> 3;
 519                 assert(op[-2] >= M2_MARKER);
 520         } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
 521                 assert(m_len == 3);
 522                 assert(m_off > M2_MAX_OFFSET);
 523                 m_off -= 1 + M2_MAX_OFFSET;
 524                 *op++ = M1_MARKER | ((m_off & 3) << 2);
 525                 *op++ = m_off >> 2;
 526         } else if (m_off <= M3_MAX_OFFSET) {
 527                 assert(m_len >= 3);
 528                 m_off -= 1;
 529                 if (m_len <= M3_MAX_LEN)
 530                         *op++ = M3_MARKER | (m_len - 2);
 531                 else {
 532                         m_len -= M3_MAX_LEN;
 533                         *op++ = M3_MARKER | 0;
 534                         while (m_len > 255) {
 535                                 m_len -= 255;
 536                                 *op++ = 0;
 537                         }
 538                         assert(m_len > 0);
 539                         *op++ = m_len;
 540                 }
 541                 *op++ = m_off << 2;
 542                 *op++ = m_off >> 6;
 543         } else {
 544                 unsigned k;
 545
 546                 assert(m_len >= 3);
 547                 assert(m_off > 0x4000);
 548                 assert(m_off <= 0xbfff);
 549                 m_off -= 0x4000;
 550                 k = (m_off & 0x4000) >> 11;
 551                 if (m_len <= M4_MAX_LEN)
 552                         *op++ = M4_MARKER | k | (m_len - 2);
 553                 else {
 554                         m_len -= M4_MAX_LEN;
 555                         *op++ = M4_MARKER | k | 0;
 556                         while (m_len > 255) {
 557                                 m_len -= 255;
 558                                 *op++ = 0;
 559                         }
 560                         assert(m_len > 0);
 561                         *op++ = m_len;
 562                 }
 563                 *op++ = m_off << 2;
 564                 *op++ = m_off >> 6;
 565         }
 566
 567         return op;
 568 }
 569
 570
 571 static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op,
 572                 const uint8_t *ii, unsigned t)
 573 {
 574         if (op == c->out && t <= 238) {
 575                 *op++ = 17 + t;
 576         } else if (t <= 3) {
 577                 op[-2] |= t;
 578         } else if (t <= 18) {
 579                 *op++ = t - 3;
 580         } else {
 581                 unsigned tt = t - 18;
 582
 583                 *op++ = 0;
 584                 while (tt > 255) {
 585                         tt -= 255;
 586                         *op++ = 0;
 587                 }
 588                 assert(tt > 0);
 589                 *op++ = tt;
 590         }
 591         do *op++ = *ii++; while (--t > 0);
 592
 593         return op;
 594 }
 595
 596
 597 static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii,
 598                 unsigned lit)
 599 {
 600         if (lit > 0) {
 601                 assert(m_len >= 2);
 602                 op = STORE_RUN(c, op, ii, lit);
 603         } else {
 604                 assert(m_len >= 3);
 605         }
 606         c->r1_lit = lit;
 607
 608         return op;
 609 }
 610
 611
 612 /***********************************************************************
 613 //
 614 ************************************************************************/
 615 static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit)
 616 {
 617         int n = 4;
 618
 619         if (m_len < 2)
 620                 return -1;
 621         if (m_len == 2)
 622                 return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : -1;
 623         if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
 624                 return 2;
 625         if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
 626                 return 2;
 627         if (m_off <= M3_MAX_OFFSET) {
 628                 if (m_len <= M3_MAX_LEN)
 629                         return 3;
 630                 m_len -= M3_MAX_LEN;
 631         } else if (m_off <= M4_MAX_OFFSET) {
 632                 if (m_len <= M4_MAX_LEN)
 633                         return 3;
 634                 m_len -= M4_MAX_LEN;
 635         } else
 636                 return -1;
 637         while (m_len > 255) {
 638                 m_len -= 255;
 639                 n++;
 640         }
 641         return n;
 642 }
 643
 644
 645 static int min_gain(unsigned ahead, unsigned lit1,
 646                         unsigned lit2, int l1, int l2, int l3)
 647 {
 648         int lazy_match_min_gain = 0;
 649
 650         assert (ahead >= 1);
 651         lazy_match_min_gain += ahead;
 652
 653         if (lit1 <= 3)
 654                 lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
 655         else if (lit1 <= 18)
 656                 lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
 657
 658         lazy_match_min_gain += (l2 - l1) * 2;
 659         if (l3 > 0)
 660                 lazy_match_min_gain -= (ahead - l3) * 2;
 661
 662         if (lazy_match_min_gain < 0)
 663                 lazy_match_min_gain = 0;
 664
 665         return lazy_match_min_gain;
 666 }
 667
 668
 669 /***********************************************************************
 670 //
 671 ************************************************************************/
 672 #if defined(SWD_BEST_OFF)
 673
 674 static void better_match(const lzo_swd_p swd,
 675                         unsigned *m_len, unsigned *m_off)
 676 {
 677         if (*m_len <= M2_MIN_LEN)
 678                 return;
 679
 680         if (*m_off <= M2_MAX_OFFSET)
 681                 return;
 682
 683         /* M3/M4 -> M2 */
 684         if (*m_off > M2_MAX_OFFSET
 685          && *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1
 686          && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET
 687         ) {
 688                 *m_len = *m_len - 1;
 689                 *m_off = swd->best_off[*m_len];
 690                 return;
 691         }
 692
 693         /* M4 -> M2 */
 694         if (*m_off > M3_MAX_OFFSET
 695          && *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2
 696          && swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET
 697         ) {
 698                 *m_len = *m_len - 2;
 699                 *m_off = swd->best_off[*m_len];
 700                 return;
 701         }
 702         /* M4 -> M3 */
 703         if (*m_off > M3_MAX_OFFSET
 704          && *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1
 705          && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET
 706         ) {
 707                 *m_len = *m_len - 1;
 708                 *m_off = swd->best_off[*m_len];
 709         }
 710 }
 711
 712 #endif
 713
 714
 715 /***********************************************************************
 716 //
 717 ************************************************************************/
 718 static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
 719                 uint8_t *out, unsigned *out_len,
 720                 void *wrkmem,
 721                 unsigned good_length,
 722                 unsigned max_lazy,
 723                 unsigned max_chain,
 724                 uint32_t use_best_off)
 725 {
 726         uint8_t *op;
 727         const uint8_t *ii;
 728         unsigned lit;
 729         unsigned m_len, m_off;
 730         lzo1x_999_t cc;
 731         lzo1x_999_t *const c = &cc;
 732         const lzo_swd_p swd = (lzo_swd_p) wrkmem;
 733         int r;
 734
 735         c->init = 0;
 736         c->ip = c->in = in;
 737         c->in_end = in + in_len;
 738         c->out = out;
 739
 740         op = out;
 741         ii = c->ip;             /* point to start of literal run */
 742         lit = 0;
 743         c->r1_lit = 0;
 744
 745         r = init_match(c, swd, use_best_off);
 746         if (r != 0)
 747                 return r;
 748         swd->max_chain = max_chain;
 749
 750         r = find_match(c, swd, 0, 0);
 751         if (r != 0)
 752                 return r;
 753
 754         while (c->look > 0) {
 755                 unsigned ahead;
 756                 unsigned max_ahead;
 757                 int l1, l2, l3;
 758
 759                 m_len = c->m_len;
 760                 m_off = c->m_off;
 761
 762                 assert(c->bp == c->ip - c->look);
 763                 assert(c->bp >= in);
 764                 if (lit == 0)
 765                         ii = c->bp;
 766                 assert(ii + lit == c->bp);
 767                 assert(swd->b_char == *(c->bp));
 768
 769                 if (m_len < 2
 770                  || (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4))
 771                     /* Do not accept this match for compressed-data compatibility
 772                      * with LZO v1.01 and before
 773                      * [ might be a problem for decompress() and optimize() ]
 774                      */
 775                  || (m_len == 2 && op == out)
 776                  || (op == out && lit == 0)
 777                 ) {
 778                         /* a literal */
 779                         m_len = 0;
 780                 }
 781                 else if (m_len == M2_MIN_LEN) {
 782                         /* compression ratio improves if we code a literal in some cases */
 783                         if (m_off > MX_MAX_OFFSET && lit >= 4)
 784                                 m_len = 0;
 785                 }
 786
 787                 if (m_len == 0) {
 788                         /* a literal */
 789                         lit++;
 790                         swd->max_chain = max_chain;
 791                         r = find_match(c, swd, 1, 0);
 792                         assert(r == 0);
 793                         continue;
 794                 }
 795
 796                 /* a match */
 797 #if defined(SWD_BEST_OFF)
 798                 if (swd->use_best_off)
 799                         better_match(swd, &m_len, &m_off);
 800 #endif
 801
 802                 /* shall we try a lazy match ? */
 803                 ahead = 0;
 804                 if (m_len >= max_lazy) {
 805                         /* no */
 806                         l1 = 0;
 807                         max_ahead = 0;
 808                 } else {
 809                         /* yes, try a lazy match */
 810                         l1 = len_of_coded_match(m_len, m_off, lit);
 811                         assert(l1 > 0);
 812                         max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
 813                 }
 814
 815
 816                 while (ahead < max_ahead && c->look > m_len) {
 817                         int lazy_match_min_gain;
 818
 819                         if (m_len >= good_length)
 820                                 swd->max_chain = max_chain >> 2;
 821                         else
 822                                 swd->max_chain = max_chain;
 823                         r = find_match(c, swd, 1, 0);
 824                         ahead++;
 825
 826                         assert(r == 0);
 827                         assert(c->look > 0);
 828                         assert(ii + lit + ahead == c->bp);
 829
 830                         if (c->m_len < m_len)
 831                                 continue;
 832                         if (c->m_len == m_len && c->m_off >= m_off)
 833                                 continue;
 834 #if defined(SWD_BEST_OFF)
 835                         if (swd->use_best_off)
 836                                 better_match(swd, &c->m_len, &c->m_off);
 837 #endif
 838                         l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead);
 839                         if (l2 < 0)
 840                                 continue;
 841
 842                         /* compressed-data compatibility [see above] */
 843                         l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit);
 844
 845                         lazy_match_min_gain = min_gain(ahead, lit, lit+ahead, l1, l2, l3);
 846                         if (c->m_len >= m_len + lazy_match_min_gain) {
 847                                 if (l3 > 0) {
 848                                         /* code previous run */
 849                                         op = code_run(c, op, ii, lit);
 850                                         lit = 0;
 851                                         /* code shortened match */
 852                                         op = code_match(c, op, ahead, m_off);
 853                                 } else {
 854                                         lit += ahead;
 855                                         assert(ii + lit == c->bp);
 856                                 }
 857                                 goto lazy_match_done;
 858                         }
 859                 }
 860
 861                 assert(ii + lit + ahead == c->bp);
 862
 863                 /* 1 - code run */
 864                 op = code_run(c, op, ii, lit);
 865                 lit = 0;
 866
 867                 /* 2 - code match */
 868                 op = code_match(c, op, m_len, m_off);
 869                 swd->max_chain = max_chain;
 870                 r = find_match(c, swd, m_len, 1+ahead);
 871                 assert(r == 0);
 872
 873  lazy_match_done: ;
 874         }
 875
 876         /* store final run */
 877         if (lit > 0)
 878                 op = STORE_RUN(c, op, ii, lit);
 879
 880 #if defined(LZO_EOF_CODE)
 881         *op++ = M4_MARKER | 1;
 882         *op++ = 0;
 883         *op++ = 0;
 884 #endif
 885
 886         *out_len = op - out;
 887
 888         return LZO_E_OK;
 889 }
 890
 891
 892 /***********************************************************************
 893 //
 894 ************************************************************************/
 895 int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
 896                 uint8_t *out, unsigned *out_len,
 897                 void *wrkmem,
 898                 int compression_level)
 899 {
 900         static const struct {
 901                 uint16_t good_length;
 902                 uint16_t max_lazy;
 903                 uint16_t max_chain;
 904                 uint16_t use_best_off;
 905         } c[3] = {
 906                 {     8,    32,  256,   0 },
 907                 {    32,   128, 2048,   1 },
 908                 { SWD_F, SWD_F, 4096,   1 }       /* max. compression */
 909         };
 910
 911         if (compression_level < 7 || compression_level > 9)
 912                 return LZO_E_ERROR;
 913
 914         compression_level -= 7;
 915         return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
 916                                         c[compression_level].good_length,
 917                                         c[compression_level].max_lazy,
 918                                         c[compression_level].max_chain,
 919                                         c[compression_level].use_best_off);
 920 }