busybox/archival/libarchive/lzo1x_9x.c
<<
>>
Prefs
   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
  59typedef 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
 102typedef 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
 158static 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************************************************************************/
 201static 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************************************************************************/
 225static 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************************************************************************/
 248static 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************************************************************************/
 279static 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
 341static 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************************************************************************/
 370static 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************************************************************************/
 434static 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************************************************************************/
 455static 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 */
 490static 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************************************************************************/
 502static 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
 570static 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
 596static 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************************************************************************/
 614static 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
 644static 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
 673static 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************************************************************************/
 717static 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************************************************************************/
 894int 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}
 920