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
  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
 103typedef 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
 159static 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************************************************************************/
 202static 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************************************************************************/
 226static 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************************************************************************/
 249static 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************************************************************************/
 280static void swd_search(lzo_swd_p s, unsigned node, unsigned cnt)
 281{
 282        const uint8_t *p1;
 283        const uint8_t *p2;
 284        const uint8_t *px;
 285        unsigned m_len = s->m_len;
 286        const uint8_t *b  = s->b;
 287        const uint8_t *bp = s->b + s->bp;
 288        const uint8_t *bx = s->b + s->bp + s->look;
 289        unsigned char scan_end1;
 290
 291        assert(s->m_len > 0);
 292
 293        scan_end1 = bp[m_len - 1];
 294        for ( ; cnt-- > 0; node = s->succ3[node]) {
 295                p1 = bp;
 296                p2 = b + node;
 297                px = bx;
 298
 299                assert(m_len < s->look);
 300
 301                if (p2[m_len - 1] == scan_end1
 302                 && p2[m_len] == p1[m_len]
 303                 && p2[0] == p1[0]
 304                 && p2[1] == p1[1]
 305                ) {
 306                        unsigned i;
 307                        assert(lzo_memcmp(bp, &b[node], 3) == 0);
 308
 309                        p1 += 2; p2 += 2;
 310                        do {} while (++p1 < px && *p1 == *++p2);
 311                        i = p1-bp;
 312
 313                        assert(lzo_memcmp(bp, &b[node], i) == 0);
 314
 315#if defined(SWD_BEST_OFF)
 316                        if (i < SWD_BEST_OFF) {
 317                                if (s->best_pos[i] == 0)
 318                                        s->best_pos[i] = node + 1;
 319                        }
 320#endif
 321                        if (i > m_len) {
 322                                s->m_len = m_len = i;
 323                                s->m_pos = node;
 324                                if (m_len == s->look)
 325                                        return;
 326                                if (m_len >= SWD_F)
 327                                        return;
 328                                if (m_len > (unsigned) s->best3[node])
 329                                        return;
 330                                scan_end1 = bp[m_len - 1];
 331                        }
 332                }
 333        }
 334}
 335
 336
 337/***********************************************************************
 338//
 339************************************************************************/
 340#ifdef HEAD2
 341
 342static int swd_search2(lzo_swd_p s)
 343{
 344        unsigned key;
 345
 346        assert(s->look >= 2);
 347        assert(s->m_len > 0);
 348
 349        key = s->head2[HEAD2(s->b, s->bp)];
 350        if (key == NIL2)
 351                return 0;
 352        assert(lzo_memcmp(&s->b[s->bp], &s->b[key], 2) == 0);
 353#if defined(SWD_BEST_OFF)
 354        if (s->best_pos[2] == 0)
 355                s->best_pos[2] = key + 1;
 356#endif
 357
 358        if (s->m_len < 2) {
 359                s->m_len = 2;
 360                s->m_pos = key;
 361        }
 362        return 1;
 363}
 364
 365#endif
 366
 367
 368/***********************************************************************
 369//
 370************************************************************************/
 371static void swd_findbest(lzo_swd_p s)
 372{
 373        unsigned key;
 374        unsigned cnt, node;
 375        unsigned len;
 376
 377        assert(s->m_len > 0);
 378
 379        /* get current head, add bp into HEAD3 */
 380        key = HEAD3(s->b,s->bp);
 381        node = s->succ3[s->bp] = s_get_head3(s, key);
 382        cnt = s->llen3[key]++;
 383        assert(s->llen3[key] <= SWD_N + SWD_F);
 384        if (cnt > s->max_chain)
 385                cnt = s->max_chain;
 386        s->head3[key] = s->bp;
 387
 388        s->b_char = s->b[s->bp];
 389        len = s->m_len;
 390        if (s->m_len >= s->look) {
 391                if (s->look == 0)
 392                        s->b_char = -1;
 393                s->m_off = 0;
 394                s->best3[s->bp] = SWD_F + 1;
 395        } else {
 396#ifdef HEAD2
 397                if (swd_search2(s))
 398#endif
 399                        if (s->look >= 3)
 400                                swd_search(s, node, cnt);
 401                if (s->m_len > len)
 402                        s->m_off = swd_pos2off(s,s->m_pos);
 403                s->best3[s->bp] = s->m_len;
 404
 405#if defined(SWD_BEST_OFF)
 406                if (s->use_best_off) {
 407                        int i;
 408                        for (i = 2; i < SWD_BEST_OFF; i++) {
 409                                if (s->best_pos[i] > 0)
 410                                        s->best_off[i] = swd_pos2off(s, s->best_pos[i]-1);
 411                                else
 412                                        s->best_off[i] = 0;
 413                        }
 414                }
 415#endif
 416        }
 417
 418        swd_remove_node(s,s->rp);
 419
 420#ifdef HEAD2
 421        /* add bp into HEAD2 */
 422        key = HEAD2(s->b, s->bp);
 423        s->head2[key] = s->bp;
 424#endif
 425}
 426
 427#undef HEAD3
 428#undef HEAD2
 429#undef s_get_head3
 430
 431
 432/***********************************************************************
 433//
 434************************************************************************/
 435static int init_match(lzo1x_999_t *c, lzo_swd_p s, uint32_t use_best_off)
 436{
 437        int r;
 438
 439        assert(!c->init);
 440        c->init = 1;
 441
 442        s->c = c;
 443
 444        r = swd_init(s);
 445        if (r != 0)
 446                return r;
 447
 448        s->use_best_off = use_best_off;
 449        return r;
 450}
 451
 452
 453/***********************************************************************
 454//
 455************************************************************************/
 456static int find_match(lzo1x_999_t *c, lzo_swd_p s,
 457                unsigned this_len, unsigned skip)
 458{
 459        assert(c->init);
 460
 461        if (skip > 0) {
 462                assert(this_len >= skip);
 463                swd_accept(s, this_len - skip);
 464        } else {
 465                assert(this_len <= 1);
 466        }
 467
 468        s->m_len = 1;
 469        s->m_len = 1;
 470#ifdef SWD_BEST_OFF
 471        if (s->use_best_off)
 472                memset(s->best_pos, 0, sizeof(s->best_pos));
 473#endif
 474        swd_findbest(s);
 475        c->m_len = s->m_len;
 476        c->m_off = s->m_off;
 477
 478        swd_getbyte(s);
 479
 480        if (s->b_char < 0) {
 481                c->look = 0;
 482                c->m_len = 0;
 483        } else {
 484                c->look = s->look + 1;
 485        }
 486        c->bp = c->ip - c->look;
 487
 488        return LZO_E_OK;
 489}
 490
 491/* this is a public functions, but there is no prototype in a header file */
 492static int lzo1x_999_compress_internal(const uint8_t *in , unsigned in_len,
 493                uint8_t *out, unsigned *out_len,
 494                void *wrkmem,
 495                unsigned good_length,
 496                unsigned max_lazy,
 497                unsigned max_chain,
 498                uint32_t use_best_off);
 499
 500
 501/***********************************************************************
 502//
 503************************************************************************/
 504static uint8_t *code_match(lzo1x_999_t *c,
 505                uint8_t *op, unsigned m_len, unsigned m_off)
 506{
 507        assert(op > c->out);
 508        if (m_len == 2) {
 509                assert(m_off <= M1_MAX_OFFSET);
 510                assert(c->r1_lit > 0);
 511                assert(c->r1_lit < 4);
 512                m_off -= 1;
 513                *op++ = M1_MARKER | ((m_off & 3) << 2);
 514                *op++ = m_off >> 2;
 515        } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
 516                assert(m_len >= 3);
 517                m_off -= 1;
 518                *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
 519                *op++ = m_off >> 3;
 520                assert(op[-2] >= M2_MARKER);
 521        } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
 522                assert(m_len == 3);
 523                assert(m_off > M2_MAX_OFFSET);
 524                m_off -= 1 + M2_MAX_OFFSET;
 525                *op++ = M1_MARKER | ((m_off & 3) << 2);
 526                *op++ = m_off >> 2;
 527        } else if (m_off <= M3_MAX_OFFSET) {
 528                assert(m_len >= 3);
 529                m_off -= 1;
 530                if (m_len <= M3_MAX_LEN)
 531                        *op++ = M3_MARKER | (m_len - 2);
 532                else {
 533                        m_len -= M3_MAX_LEN;
 534                        *op++ = M3_MARKER | 0;
 535                        while (m_len > 255) {
 536                                m_len -= 255;
 537                                *op++ = 0;
 538                        }
 539                        assert(m_len > 0);
 540                        *op++ = m_len;
 541                }
 542                *op++ = m_off << 2;
 543                *op++ = m_off >> 6;
 544        } else {
 545                unsigned k;
 546
 547                assert(m_len >= 3);
 548                assert(m_off > 0x4000);
 549                assert(m_off <= 0xbfff);
 550                m_off -= 0x4000;
 551                k = (m_off & 0x4000) >> 11;
 552                if (m_len <= M4_MAX_LEN)
 553                        *op++ = M4_MARKER | k | (m_len - 2);
 554                else {
 555                        m_len -= M4_MAX_LEN;
 556                        *op++ = M4_MARKER | k | 0;
 557                        while (m_len > 255) {
 558                                m_len -= 255;
 559                                *op++ = 0;
 560                        }
 561                        assert(m_len > 0);
 562                        *op++ = m_len;
 563                }
 564                *op++ = m_off << 2;
 565                *op++ = m_off >> 6;
 566        }
 567
 568        return op;
 569}
 570
 571
 572static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op,
 573                const uint8_t *ii, unsigned t)
 574{
 575        if (op == c->out && t <= 238) {
 576                *op++ = 17 + t;
 577        } else if (t <= 3) {
 578                op[-2] |= t;
 579        } else if (t <= 18) {
 580                *op++ = t - 3;
 581        } else {
 582                unsigned tt = t - 18;
 583
 584                *op++ = 0;
 585                while (tt > 255) {
 586                        tt -= 255;
 587                        *op++ = 0;
 588                }
 589                assert(tt > 0);
 590                *op++ = tt;
 591        }
 592        do *op++ = *ii++; while (--t > 0);
 593
 594        return op;
 595}
 596
 597
 598static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii,
 599                unsigned lit)
 600{
 601        if (lit > 0) {
 602                assert(m_len >= 2);
 603                op = STORE_RUN(c, op, ii, lit);
 604        } else {
 605                assert(m_len >= 3);
 606        }
 607        c->r1_lit = lit;
 608
 609        return op;
 610}
 611
 612
 613/***********************************************************************
 614//
 615************************************************************************/
 616static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit)
 617{
 618        int n = 4;
 619
 620        if (m_len < 2)
 621                return -1;
 622        if (m_len == 2)
 623                return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : -1;
 624        if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
 625                return 2;
 626        if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
 627                return 2;
 628        if (m_off <= M3_MAX_OFFSET) {
 629                if (m_len <= M3_MAX_LEN)
 630                        return 3;
 631                m_len -= M3_MAX_LEN;
 632        } else if (m_off <= M4_MAX_OFFSET) {
 633                if (m_len <= M4_MAX_LEN)
 634                        return 3;
 635                m_len -= M4_MAX_LEN;
 636        } else
 637                return -1;
 638        while (m_len > 255) {
 639                m_len -= 255;
 640                n++;
 641        }
 642        return n;
 643}
 644
 645
 646static int min_gain(unsigned ahead, unsigned lit1,
 647                    unsigned lit2, int l1, int l2, int l3)
 648{
 649        int lazy_match_min_gain = 0;
 650
 651        assert (ahead >= 1);
 652        lazy_match_min_gain += ahead;
 653
 654        if (lit1 <= 3)
 655                lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
 656        else if (lit1 <= 18)
 657                lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
 658
 659        lazy_match_min_gain += (l2 - l1) * 2;
 660        if (l3 > 0)
 661                lazy_match_min_gain -= (ahead - l3) * 2;
 662
 663        if (lazy_match_min_gain < 0)
 664                lazy_match_min_gain = 0;
 665
 666        return lazy_match_min_gain;
 667}
 668
 669
 670/***********************************************************************
 671//
 672************************************************************************/
 673#if defined(SWD_BEST_OFF)
 674
 675static void better_match(const lzo_swd_p swd,
 676                           unsigned *m_len, unsigned *m_off)
 677{
 678        if (*m_len <= M2_MIN_LEN)
 679                return;
 680
 681        if (*m_off <= M2_MAX_OFFSET)
 682                return;
 683
 684        /* M3/M4 -> M2 */
 685        if (*m_off > M2_MAX_OFFSET
 686         && *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1
 687         && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET
 688        ) {
 689                *m_len = *m_len - 1;
 690                *m_off = swd->best_off[*m_len];
 691                return;
 692        }
 693
 694        /* M4 -> M2 */
 695        if (*m_off > M3_MAX_OFFSET
 696         && *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2
 697         && swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET
 698        ) {
 699                *m_len = *m_len - 2;
 700                *m_off = swd->best_off[*m_len];
 701                return;
 702        }
 703        /* M4 -> M3 */
 704        if (*m_off > M3_MAX_OFFSET
 705         && *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1
 706         && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET
 707        ) {
 708                *m_len = *m_len - 1;
 709                *m_off = swd->best_off[*m_len];
 710        }
 711}
 712
 713#endif
 714
 715
 716/***********************************************************************
 717//
 718************************************************************************/
 719static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
 720                uint8_t *out, unsigned *out_len,
 721                void *wrkmem,
 722                unsigned good_length,
 723                unsigned max_lazy,
 724                unsigned max_chain,
 725                uint32_t use_best_off)
 726{
 727        uint8_t *op;
 728        const uint8_t *ii;
 729        unsigned lit;
 730        unsigned m_len, m_off;
 731        lzo1x_999_t cc;
 732        lzo1x_999_t *const c = &cc;
 733        const lzo_swd_p swd = (lzo_swd_p) wrkmem;
 734        int r;
 735
 736        c->init = 0;
 737        c->ip = c->in = in;
 738        c->in_end = in + in_len;
 739        c->out = out;
 740
 741        op = out;
 742        ii = c->ip;             /* point to start of literal run */
 743        lit = 0;
 744        c->r1_lit = 0;
 745
 746        r = init_match(c, swd, use_best_off);
 747        if (r != 0)
 748                return r;
 749        swd->max_chain = max_chain;
 750
 751        r = find_match(c, swd, 0, 0);
 752        if (r != 0)
 753                return r;
 754
 755        while (c->look > 0) {
 756                unsigned ahead;
 757                unsigned max_ahead;
 758                int l1, l2, l3;
 759
 760                m_len = c->m_len;
 761                m_off = c->m_off;
 762
 763                assert(c->bp == c->ip - c->look);
 764                assert(c->bp >= in);
 765                if (lit == 0)
 766                        ii = c->bp;
 767                assert(ii + lit == c->bp);
 768                assert(swd->b_char == *(c->bp));
 769
 770                if (m_len < 2
 771                 || (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4))
 772                    /* Do not accept this match for compressed-data compatibility
 773                     * with LZO v1.01 and before
 774                     * [ might be a problem for decompress() and optimize() ]
 775                     */
 776                 || (m_len == 2 && op == out)
 777                 || (op == out && lit == 0)
 778                ) {
 779                        /* a literal */
 780                        m_len = 0;
 781                }
 782                else if (m_len == M2_MIN_LEN) {
 783                        /* compression ratio improves if we code a literal in some cases */
 784                        if (m_off > MX_MAX_OFFSET && lit >= 4)
 785                                m_len = 0;
 786                }
 787
 788                if (m_len == 0) {
 789                        /* a literal */
 790                        lit++;
 791                        swd->max_chain = max_chain;
 792                        r = find_match(c, swd, 1, 0);
 793                        assert(r == 0);
 794                        continue;
 795                }
 796
 797                /* a match */
 798#if defined(SWD_BEST_OFF)
 799                if (swd->use_best_off)
 800                        better_match(swd, &m_len, &m_off);
 801#endif
 802
 803                /* shall we try a lazy match ? */
 804                ahead = 0;
 805                if (m_len >= max_lazy) {
 806                        /* no */
 807                        l1 = 0;
 808                        max_ahead = 0;
 809                } else {
 810                        /* yes, try a lazy match */
 811                        l1 = len_of_coded_match(m_len, m_off, lit);
 812                        assert(l1 > 0);
 813                        max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
 814                }
 815
 816
 817                while (ahead < max_ahead && c->look > m_len) {
 818                        int lazy_match_min_gain;
 819
 820                        if (m_len >= good_length)
 821                                swd->max_chain = max_chain >> 2;
 822                        else
 823                                swd->max_chain = max_chain;
 824                        r = find_match(c, swd, 1, 0);
 825                        ahead++;
 826
 827                        assert(r == 0);
 828                        assert(c->look > 0);
 829                        assert(ii + lit + ahead == c->bp);
 830
 831                        if (c->m_len < m_len)
 832                                continue;
 833                        if (c->m_len == m_len && c->m_off >= m_off)
 834                                continue;
 835#if defined(SWD_BEST_OFF)
 836                        if (swd->use_best_off)
 837                                better_match(swd, &c->m_len, &c->m_off);
 838#endif
 839                        l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead);
 840                        if (l2 < 0)
 841                                continue;
 842
 843                        /* compressed-data compatibility [see above] */
 844                        l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit);
 845
 846                        lazy_match_min_gain = min_gain(ahead, lit, lit+ahead, l1, l2, l3);
 847                        if (c->m_len >= m_len + lazy_match_min_gain) {
 848                                if (l3 > 0) {
 849                                        /* code previous run */
 850                                        op = code_run(c, op, ii, lit);
 851                                        lit = 0;
 852                                        /* code shortened match */
 853                                        op = code_match(c, op, ahead, m_off);
 854                                } else {
 855                                        lit += ahead;
 856                                        assert(ii + lit == c->bp);
 857                                }
 858                                goto lazy_match_done;
 859                        }
 860                }
 861
 862                assert(ii + lit + ahead == c->bp);
 863
 864                /* 1 - code run */
 865                op = code_run(c, op, ii, lit);
 866                lit = 0;
 867
 868                /* 2 - code match */
 869                op = code_match(c, op, m_len, m_off);
 870                swd->max_chain = max_chain;
 871                r = find_match(c, swd, m_len, 1+ahead);
 872                assert(r == 0);
 873
 874 lazy_match_done: ;
 875        }
 876
 877        /* store final run */
 878        if (lit > 0)
 879                op = STORE_RUN(c, op, ii, lit);
 880
 881#if defined(LZO_EOF_CODE)
 882        *op++ = M4_MARKER | 1;
 883        *op++ = 0;
 884        *op++ = 0;
 885#endif
 886
 887        *out_len = op - out;
 888
 889        return LZO_E_OK;
 890}
 891
 892
 893/***********************************************************************
 894//
 895************************************************************************/
 896int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
 897                uint8_t *out, unsigned *out_len,
 898                void *wrkmem,
 899                int compression_level)
 900{
 901        static const struct {
 902                uint16_t good_length;
 903                uint16_t max_lazy;
 904                uint16_t max_chain;
 905                uint16_t use_best_off;
 906        } c[3] = {
 907                {     8,    32,  256,   0 },
 908                {    32,   128, 2048,   1 },
 909                { SWD_F, SWD_F, 4096,   1 }       /* max. compression */
 910        };
 911
 912        if (compression_level < 7 || compression_level > 9)
 913                return LZO_E_ERROR;
 914
 915        compression_level -= 7;
 916        return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
 917                                           c[compression_level].good_length,
 918                                           c[compression_level].max_lazy,
 919                                           c[compression_level].max_chain,
 920                                           c[compression_level].use_best_off);
 921}
 922