busybox/archival/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
 679        if (*m_len <= M2_MIN_LEN)
 680                return;
 681
 682        if (*m_off <= M2_MAX_OFFSET)
 683                return;
 684
 685        /* M3/M4 -> M2 */
 686        if (*m_off > M2_MAX_OFFSET
 687         && *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1
 688         && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET
 689        ) {
 690                *m_len = *m_len - 1;
 691                *m_off = swd->best_off[*m_len];
 692                return;
 693        }
 694
 695        /* M4 -> M2 */
 696        if (*m_off > M3_MAX_OFFSET
 697         && *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2
 698         && swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET
 699        ) {
 700                *m_len = *m_len - 2;
 701                *m_off = swd->best_off[*m_len];
 702                return;
 703        }
 704        /* M4 -> M3 */
 705        if (*m_off > M3_MAX_OFFSET
 706         && *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1
 707         && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET
 708        ) {
 709                *m_len = *m_len - 1;
 710                *m_off = swd->best_off[*m_len];
 711        }
 712}
 713
 714#endif
 715
 716
 717/***********************************************************************
 718//
 719************************************************************************/
 720static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
 721                uint8_t *out, unsigned *out_len,
 722                void *wrkmem,
 723                unsigned good_length,
 724                unsigned max_lazy,
 725                unsigned max_chain,
 726                uint32_t use_best_off)
 727{
 728        uint8_t *op;
 729        const uint8_t *ii;
 730        unsigned lit;
 731        unsigned m_len, m_off;
 732        lzo1x_999_t cc;
 733        lzo1x_999_t *const c = &cc;
 734        const lzo_swd_p swd = (lzo_swd_p) wrkmem;
 735        int r;
 736
 737        c->init = 0;
 738        c->ip = c->in = in;
 739        c->in_end = in + in_len;
 740        c->out = out;
 741
 742        op = out;
 743        ii = c->ip;             /* point to start of literal run */
 744        lit = 0;
 745        c->r1_lit = 0;
 746
 747        r = init_match(c, swd, use_best_off);
 748        if (r != 0)
 749                return r;
 750        swd->max_chain = max_chain;
 751
 752        r = find_match(c, swd, 0, 0);
 753        if (r != 0)
 754                return r;
 755
 756        while (c->look > 0) {
 757                unsigned ahead;
 758                unsigned max_ahead;
 759                int l1, l2, l3;
 760
 761                m_len = c->m_len;
 762                m_off = c->m_off;
 763
 764                assert(c->bp == c->ip - c->look);
 765                assert(c->bp >= in);
 766                if (lit == 0)
 767                        ii = c->bp;
 768                assert(ii + lit == c->bp);
 769                assert(swd->b_char == *(c->bp));
 770
 771                if (m_len < 2
 772                 || (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4))
 773                    /* Do not accept this match for compressed-data compatibility
 774                     * with LZO v1.01 and before
 775                     * [ might be a problem for decompress() and optimize() ]
 776                     */
 777                 || (m_len == 2 && op == out)
 778                 || (op == out && lit == 0)
 779                ) {
 780                        /* a literal */
 781                        m_len = 0;
 782                }
 783                else if (m_len == M2_MIN_LEN) {
 784                        /* compression ratio improves if we code a literal in some cases */
 785                        if (m_off > MX_MAX_OFFSET && lit >= 4)
 786                                m_len = 0;
 787                }
 788
 789                if (m_len == 0) {
 790                        /* a literal */
 791                        lit++;
 792                        swd->max_chain = max_chain;
 793                        r = find_match(c, swd, 1, 0);
 794                        assert(r == 0);
 795                        continue;
 796                }
 797
 798                /* a match */
 799#if defined(SWD_BEST_OFF)
 800                if (swd->use_best_off)
 801                        better_match(swd, &m_len, &m_off);
 802#endif
 803
 804                /* shall we try a lazy match ? */
 805                ahead = 0;
 806                if (m_len >= max_lazy) {
 807                        /* no */
 808                        l1 = 0;
 809                        max_ahead = 0;
 810                } else {
 811                        /* yes, try a lazy match */
 812                        l1 = len_of_coded_match(m_len, m_off, lit);
 813                        assert(l1 > 0);
 814                        max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
 815                }
 816
 817
 818                while (ahead < max_ahead && c->look > m_len) {
 819                        int lazy_match_min_gain;
 820
 821                        if (m_len >= good_length)
 822                                swd->max_chain = max_chain >> 2;
 823                        else
 824                                swd->max_chain = max_chain;
 825                        r = find_match(c, swd, 1, 0);
 826                        ahead++;
 827
 828                        assert(r == 0);
 829                        assert(c->look > 0);
 830                        assert(ii + lit + ahead == c->bp);
 831
 832                        if (c->m_len < m_len)
 833                                continue;
 834                        if (c->m_len == m_len && c->m_off >= m_off)
 835                                continue;
 836#if defined(SWD_BEST_OFF)
 837                        if (swd->use_best_off)
 838                                better_match(swd, &c->m_len, &c->m_off);
 839#endif
 840                        l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead);
 841                        if (l2 < 0)
 842                                continue;
 843
 844                        /* compressed-data compatibility [see above] */
 845                        l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit);
 846
 847                        lazy_match_min_gain = min_gain(ahead, lit, lit+ahead, l1, l2, l3);
 848                        if (c->m_len >= m_len + lazy_match_min_gain) {
 849                                if (l3 > 0) {
 850                                        /* code previous run */
 851                                        op = code_run(c, op, ii, lit);
 852                                        lit = 0;
 853                                        /* code shortened match */
 854                                        op = code_match(c, op, ahead, m_off);
 855                                } else {
 856                                        lit += ahead;
 857                                        assert(ii + lit == c->bp);
 858                                }
 859                                goto lazy_match_done;
 860                        }
 861                }
 862
 863                assert(ii + lit + ahead == c->bp);
 864
 865                /* 1 - code run */
 866                op = code_run(c, op, ii, lit);
 867                lit = 0;
 868
 869                /* 2 - code match */
 870                op = code_match(c, op, m_len, m_off);
 871                swd->max_chain = max_chain;
 872                r = find_match(c, swd, m_len, 1+ahead);
 873                assert(r == 0);
 874
 875 lazy_match_done: ;
 876        }
 877
 878        /* store final run */
 879        if (lit > 0)
 880                op = STORE_RUN(c, op, ii, lit);
 881
 882#if defined(LZO_EOF_CODE)
 883        *op++ = M4_MARKER | 1;
 884        *op++ = 0;
 885        *op++ = 0;
 886#endif
 887
 888        *out_len = op - out;
 889
 890        return LZO_E_OK;
 891}
 892
 893
 894/***********************************************************************
 895//
 896************************************************************************/
 897int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
 898                uint8_t *out, unsigned *out_len,
 899                void *wrkmem,
 900                int compression_level)
 901{
 902        static const struct {
 903                uint16_t good_length;
 904                uint16_t max_lazy;
 905                uint16_t max_chain;
 906                uint16_t use_best_off;
 907        } c[3] = {
 908                {     8,    32,  256,   0 },
 909                {    32,   128, 2048,   1 },
 910                { SWD_F, SWD_F, 4096,   1 }       /* max. compression */
 911        };
 912
 913        if (compression_level < 7 || compression_level > 9)
 914                return LZO_E_ERROR;
 915
 916        compression_level -= 7;
 917        return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
 918                                           c[compression_level].good_length,
 919                                           c[compression_level].max_lazy,
 920                                           c[compression_level].max_chain,
 921                                           c[compression_level].use_best_off);
 922}
 923