archival/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)      (* (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                         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 #endif
 414         }
 415
 416         swd_remove_node(s,s->rp);
 417
 418 #ifdef HEAD2
 419         /* add bp into HEAD2 */
 420         key = HEAD2(s->b,s->bp);
 421         s->head2[key] = s->bp;
 422 #endif
 423 }
 424
 425 #undef HEAD3
 426 #undef HEAD2
 427 #undef s_get_head3
 428
 429
 430 /***********************************************************************
 431 //
 432 ************************************************************************/
 433 static int init_match(lzo1x_999_t *c, lzo_swd_p s, uint32_t use_best_off)
 434 {
 435         int r;
 436
 437         assert(!c->init);
 438         c->init = 1;
 439
 440         s->c = c;
 441
 442         r = swd_init(s);
 443         if (r != 0)
 444                 return r;
 445
 446         s->use_best_off = use_best_off;
 447         return r;
 448 }
 449
 450
 451 /***********************************************************************
 452 //
 453 ************************************************************************/
 454 static int find_match(lzo1x_999_t *c, lzo_swd_p s,
 455                 unsigned this_len, unsigned skip)
 456 {
 457         assert(c->init);
 458
 459         if (skip > 0) {
 460                 assert(this_len >= skip);
 461                 swd_accept(s, this_len - skip);
 462         } else {
 463                 assert(this_len <= 1);
 464         }
 465
 466         s->m_len = 1;
 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); assert(c->r1_lit < 4);
 509                 m_off -= 1;
 510                 *op++ = M1_MARKER | ((m_off & 3) << 2);
 511                 *op++ = m_off >> 2;
 512         } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
 513                 assert(m_len >= 3);
 514                 m_off -= 1;
 515                 *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
 516                 *op++ = m_off >> 3;
 517                 assert(op[-2] >= M2_MARKER);
 518         } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
 519                 assert(m_len == 3);
 520                 assert(m_off > M2_MAX_OFFSET);
 521                 m_off -= 1 + M2_MAX_OFFSET;
 522                 *op++ = M1_MARKER | ((m_off & 3) << 2);
 523                 *op++ = m_off >> 2;
 524         } else if (m_off <= M3_MAX_OFFSET) {
 525                 assert(m_len >= 3);
 526                 m_off -= 1;
 527                 if (m_len <= M3_MAX_LEN)
 528                         *op++ = M3_MARKER | (m_len - 2);
 529                 else {
 530                         m_len -= M3_MAX_LEN;
 531                         *op++ = M3_MARKER | 0;
 532                         while (m_len > 255)
 533                                 {
 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); assert(m_off <= 0xbfff);
 547                 m_off -= 0x4000;
 548                 k = (m_off & 0x4000) >> 11;
 549                 if (m_len <= M4_MAX_LEN)
 550                         *op++ = M4_MARKER | k | (m_len - 2);
 551                 else {
 552                         m_len -= M4_MAX_LEN;
 553                         *op++ = M4_MARKER | k | 0;
 554                         while (m_len > 255)
 555                                 {
 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
 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         lzo_swd_p const 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 }