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