Blame src/lzo1.c

Packit Service 5195f2
/* lzo1.c -- implementation of the LZO1 algorithm
Packit Service 5195f2
Packit Service 5195f2
   This file is part of the LZO real-time data compression library.
Packit Service 5195f2
Packit Service 5195f2
   Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer
Packit Service 5195f2
   All Rights Reserved.
Packit Service 5195f2
Packit Service 5195f2
   The LZO library is free software; you can redistribute it and/or
Packit Service 5195f2
   modify it under the terms of the GNU General Public License as
Packit Service 5195f2
   published by the Free Software Foundation; either version 2 of
Packit Service 5195f2
   the License, or (at your option) any later version.
Packit Service 5195f2
Packit Service 5195f2
   The LZO library is distributed in the hope that it will be useful,
Packit Service 5195f2
   but WITHOUT ANY WARRANTY; without even the implied warranty of
Packit Service 5195f2
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Packit Service 5195f2
   GNU General Public License for more details.
Packit Service 5195f2
Packit Service 5195f2
   You should have received a copy of the GNU General Public License
Packit Service 5195f2
   along with the LZO library; see the file COPYING.
Packit Service 5195f2
   If not, write to the Free Software Foundation, Inc.,
Packit Service 5195f2
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
Packit Service 5195f2
Packit Service 5195f2
   Markus F.X.J. Oberhumer
Packit Service 5195f2
   <markus@oberhumer.com>
Packit Service 5195f2
   http://www.oberhumer.com/opensource/lzo/
Packit Service 5195f2
 */
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
#include "lzo_conf.h"
Packit Service 5195f2
#include "lzo/lzo1.h"
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// The next two defines can be changed to customize LZO1.
Packit Service 5195f2
// The default version is LZO1-5/1.
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
/* run bits (3 - 5) - the compressor and the decompressor
Packit Service 5195f2
 * must use the same value. */
Packit Service 5195f2
#if !defined(RBITS)
Packit Service 5195f2
#  define RBITS     5
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
/* compression level (1 - 9) - this only affects the compressor.
Packit Service 5195f2
 * 1 is fastest, 9 is best compression ratio */
Packit Service 5195f2
#if !defined(CLEVEL)
Packit Service 5195f2
#  define CLEVEL    1           /* fastest by default */
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/* check configuration */
Packit Service 5195f2
#if (RBITS < 3 || RBITS > 5)
Packit Service 5195f2
#  error "invalid RBITS"
Packit Service 5195f2
#endif
Packit Service 5195f2
#if (CLEVEL < 1 || CLEVEL > 9)
Packit Service 5195f2
#  error "invalid CLEVEL"
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// You should not have to change anything below this line.
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
/*
Packit Service 5195f2
     Format of the marker byte
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
     76543210
Packit Service 5195f2
     --------
Packit Service 5195f2
     00000000   a long run (a 'R0' run) - there are short and long R0 runs
Packit Service 5195f2
     000rrrrr   a short run with len r
Packit Service 5195f2
     mmmooooo   a short match (len = 2+m, o = offset low bits)
Packit Service 5195f2
     111ooooo   a long match (o = offset low bits)
Packit Service 5195f2
*/
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
#define RSIZE   (1 << RBITS)
Packit Service 5195f2
#define RMASK   (RSIZE - 1)
Packit Service 5195f2
Packit Service 5195f2
#define OBITS   RBITS               /* offset and run-length use same bits */
Packit Service 5195f2
#define OSIZE   (1 << OBITS)
Packit Service 5195f2
#define OMASK   (OSIZE - 1)
Packit Service 5195f2
Packit Service 5195f2
#define MBITS   (8 - OBITS)
Packit Service 5195f2
#define MSIZE   (1 << MBITS)
Packit Service 5195f2
#define MMASK   (MSIZE - 1)
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/* sanity checks */
Packit Service 5195f2
#if (OBITS < 3 || OBITS > 5)
Packit Service 5195f2
#  error "invalid OBITS"
Packit Service 5195f2
#endif
Packit Service 5195f2
#if (MBITS < 3 || MBITS > 5)
Packit Service 5195f2
#  error "invalid MBITS"
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// some macros to improve readability
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
/* Minimum len of a match */
Packit Service 5195f2
#define MIN_MATCH           3
Packit Service 5195f2
#define THRESHOLD           (MIN_MATCH - 1)
Packit Service 5195f2
Packit Service 5195f2
/* Minimum len of match coded in 2 bytes */
Packit Service 5195f2
#define MIN_MATCH_SHORT     MIN_MATCH
Packit Service 5195f2
Packit Service 5195f2
/* Maximum len of match coded in 2 bytes */
Packit Service 5195f2
#define MAX_MATCH_SHORT     (THRESHOLD + (MSIZE - 2))
Packit Service 5195f2
/* MSIZE - 2: 0 is used to indicate runs,
Packit Service 5195f2
 *            MSIZE-1 is used to indicate a long match */
Packit Service 5195f2
Packit Service 5195f2
/* Minimum len of match coded in 3 bytes */
Packit Service 5195f2
#define MIN_MATCH_LONG      (MAX_MATCH_SHORT + 1)
Packit Service 5195f2
Packit Service 5195f2
/* Maximum len of match coded in 3 bytes */
Packit Service 5195f2
#define MAX_MATCH_LONG      (MIN_MATCH_LONG + 255)
Packit Service 5195f2
Packit Service 5195f2
/* Maximum offset of a match */
Packit Service 5195f2
#define MAX_OFFSET          (1 << (8 + OBITS))
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/*
Packit Service 5195f2
Packit Service 5195f2
RBITS | MBITS  MIN  THR.  MSIZE  MAXS  MINL  MAXL   MAXO  R0MAX R0FAST
Packit Service 5195f2
======+===============================================================
Packit Service 5195f2
  3   |   5      3    2     32    32    33    288   2048    263   256
Packit Service 5195f2
  4   |   4      3    2     16    16    17    272   4096    271   264
Packit Service 5195f2
  5   |   3      3    2      8     8     9    264   8192    287   280
Packit Service 5195f2
Packit Service 5195f2
 */
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// internal configuration
Packit Service 5195f2
// all of these affect compression only
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
/* choose the hashing strategy */
Packit Service 5195f2
#ifndef LZO_HASH
Packit Service 5195f2
#define LZO_HASH    LZO_HASH_LZO_INCREMENTAL_A
Packit Service 5195f2
#endif
Packit Service 5195f2
#define D_INDEX1(d,p)       d = DM(DMUL(0x21,DX2(p,5,5)) >> 5)
Packit Service 5195f2
#define D_INDEX2(d,p)       d = d ^ D_MASK
Packit Service 5195f2
Packit Service 5195f2
#define DBITS       (8 + RBITS)
Packit Service 5195f2
#include "lzo_dict.h"
Packit Service 5195f2
#define DVAL_LEN    DVAL_LOOKAHEAD
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// get algorithm info, return memory required for compression
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
LZO_EXTERN(lzo_uint) lzo1_info ( int *rbits, int *clevel );
Packit Service 5195f2
Packit Service 5195f2
LZO_PUBLIC(lzo_uint)
Packit Service 5195f2
lzo1_info ( int *rbits, int *clevel )
Packit Service 5195f2
{
Packit Service 5195f2
    if (rbits)
Packit Service 5195f2
        *rbits = RBITS;
Packit Service 5195f2
    if (clevel)
Packit Service 5195f2
        *clevel = CLEVEL;
Packit Service 5195f2
    return D_SIZE * lzo_sizeof(lzo_bytep);
Packit Service 5195f2
}
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// decode a R0 literal run (a long run)
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
#define R0MIN   (RSIZE)             /* Minimum len of R0 run of literals */
Packit Service 5195f2
#define R0MAX   (R0MIN + 255)       /* Maximum len of R0 run of literals */
Packit Service 5195f2
#define R0FAST  (R0MAX & ~7u)       /* R0MAX aligned to 8 byte boundary */
Packit Service 5195f2
Packit Service 5195f2
#if (R0MAX - R0FAST != 7) || ((R0FAST & 7) != 0)
Packit Service 5195f2
#  error "something went wrong"
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
/* 7 special codes from R0FAST+1 .. R0MAX
Packit Service 5195f2
 * these codes mean long R0 runs with lengths
Packit Service 5195f2
 * 512, 1024, 2048, 4096, 8192, 16384, 32768 */
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// LZO1 decompress a block of data.
Packit Service 5195f2
//
Packit Service 5195f2
// Could be easily translated into assembly code.
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
LZO_PUBLIC(int)
Packit Service 5195f2
lzo1_decompress  ( const lzo_bytep in , lzo_uint  in_len,
Packit Service 5195f2
                         lzo_bytep out, lzo_uintp out_len,
Packit Service 5195f2
                         lzo_voidp wrkmem )
Packit Service 5195f2
{
Packit Service 5195f2
    lzo_bytep op;
Packit Service 5195f2
    const lzo_bytep ip;
Packit Service 5195f2
    const lzo_bytep const ip_end = in + in_len;
Packit Service 5195f2
    lzo_uint t;
Packit Service 5195f2
Packit Service 5195f2
    LZO_UNUSED(wrkmem);
Packit Service 5195f2
Packit Service 5195f2
    op = out;
Packit Service 5195f2
    ip = in;
Packit Service 5195f2
    while (ip < ip_end)
Packit Service 5195f2
    {
Packit Service 5195f2
        t = *ip++;  /* get marker */
Packit Service 5195f2
Packit Service 5195f2
        if (t < R0MIN)          /* a literal run */
Packit Service 5195f2
        {
Packit Service 5195f2
            if (t == 0)             /* a R0 literal run */
Packit Service 5195f2
            {
Packit Service 5195f2
                t = *ip++;
Packit Service 5195f2
                if (t >= R0FAST - R0MIN)            /* a long R0 run */
Packit Service 5195f2
                {
Packit Service 5195f2
                    t -= R0FAST - R0MIN;
Packit Service 5195f2
                    if (t == 0)
Packit Service 5195f2
                        t = R0FAST;
Packit Service 5195f2
                    else
Packit Service 5195f2
                    {
Packit Service 5195f2
#if 0
Packit Service 5195f2
                        t = 256u << ((unsigned) t);
Packit Service 5195f2
#else
Packit Service 5195f2
                        /* help the optimizer */
Packit Service 5195f2
                        lzo_uint tt = 256;
Packit Service 5195f2
                        do tt <<= 1; while (--t > 0);
Packit Service 5195f2
                        t = tt;
Packit Service 5195f2
#endif
Packit Service 5195f2
                    }
Packit Service 5195f2
                    MEMCPY8_DS(op,ip,t);
Packit Service 5195f2
                    continue;
Packit Service 5195f2
                }
Packit Service 5195f2
                t += R0MIN;
Packit Service 5195f2
            }
Packit Service 5195f2
            MEMCPY_DS(op,ip,t);
Packit Service 5195f2
        }
Packit Service 5195f2
        else                    /* a match */
Packit Service 5195f2
        {
Packit Service 5195f2
            lzo_uint tt;
Packit Service 5195f2
            /* get match offset */
Packit Service 5195f2
            const lzo_bytep m_pos = op - 1;
Packit Service 5195f2
            m_pos -= (lzo_uint)(t & OMASK) | (((lzo_uint) *ip++) << OBITS);
Packit Service 5195f2
Packit Service 5195f2
            /* get match len */
Packit Service 5195f2
            if (t >= ((MSIZE - 1) << OBITS))                /* all m-bits set */
Packit Service 5195f2
                tt = (MIN_MATCH_LONG - THRESHOLD) + *ip++;  /* a long match */
Packit Service 5195f2
            else
Packit Service 5195f2
                tt = t >> OBITS;                            /* a short match */
Packit Service 5195f2
Packit Service 5195f2
            assert(m_pos >= out);
Packit Service 5195f2
            assert(m_pos <  op);
Packit Service 5195f2
            /* a half unrolled loop */
Packit Service 5195f2
            *op++ = *m_pos++;
Packit Service 5195f2
            *op++ = *m_pos++;
Packit Service 5195f2
            MEMCPY_DS(op,m_pos,tt);
Packit Service 5195f2
        }
Packit Service 5195f2
    }
Packit Service 5195f2
Packit Service 5195f2
    *out_len = pd(op, out);
Packit Service 5195f2
Packit Service 5195f2
    /* the next line is the only check in the decompressor ! */
Packit Service 5195f2
    return (ip == ip_end ? LZO_E_OK :
Packit Service 5195f2
           (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
Packit Service 5195f2
}
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// code a literal run
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
static
Packit Service 5195f2
#if LZO_ARCH_AVR
Packit Service 5195f2
__lzo_noinline
Packit Service 5195f2
#endif
Packit Service 5195f2
lzo_bytep
Packit Service 5195f2
store_run(lzo_bytep op, const lzo_bytep ii, lzo_uint r_len)
Packit Service 5195f2
{
Packit Service 5195f2
    assert(r_len > 0);
Packit Service 5195f2
Packit Service 5195f2
    /* code a long R0 run */
Packit Service 5195f2
    if (r_len >= 512)
Packit Service 5195f2
    {
Packit Service 5195f2
        unsigned r_bits = 7;        /* 256 << 7 == 32768 */
Packit Service 5195f2
        do {
Packit Service 5195f2
            while (r_len >= (256u << r_bits))
Packit Service 5195f2
            {
Packit Service 5195f2
                r_len -= (256u << r_bits);
Packit Service 5195f2
                *op++ = 0; *op++ = LZO_BYTE((R0FAST - R0MIN) + r_bits);
Packit Service 5195f2
                MEMCPY8_DS(op, ii, (256u << r_bits));
Packit Service 5195f2
            }
Packit Service 5195f2
        } while (--r_bits > 0);
Packit Service 5195f2
    }
Packit Service 5195f2
    while (r_len >= R0FAST)
Packit Service 5195f2
    {
Packit Service 5195f2
        r_len -= R0FAST;
Packit Service 5195f2
        *op++ = 0; *op++ = R0FAST - R0MIN;
Packit Service 5195f2
        MEMCPY8_DS(op, ii, R0FAST);
Packit Service 5195f2
    }
Packit Service 5195f2
Packit Service 5195f2
    if (r_len >= R0MIN)
Packit Service 5195f2
    {
Packit Service 5195f2
        /* code a short R0 run */
Packit Service 5195f2
        *op++ = 0; *op++ = LZO_BYTE(r_len - R0MIN);
Packit Service 5195f2
        MEMCPY_DS(op, ii, r_len);
Packit Service 5195f2
    }
Packit Service 5195f2
    else if (r_len > 0)
Packit Service 5195f2
    {
Packit Service 5195f2
        /* code a 'normal' run */
Packit Service 5195f2
        *op++ = LZO_BYTE(r_len);
Packit Service 5195f2
        MEMCPY_DS(op, ii, r_len);
Packit Service 5195f2
    }
Packit Service 5195f2
Packit Service 5195f2
    assert(r_len == 0);
Packit Service 5195f2
    return op;
Packit Service 5195f2
}
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// LZO1 compress a block of data.
Packit Service 5195f2
//
Packit Service 5195f2
// Could be translated into assembly code without too much effort.
Packit Service 5195f2
//
Packit Service 5195f2
// I apologize for the spaghetti code, but it really helps the optimizer.
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
static int
Packit Service 5195f2
do_compress    ( const lzo_bytep in , lzo_uint  in_len,
Packit Service 5195f2
                       lzo_bytep out, lzo_uintp out_len,
Packit Service 5195f2
                       lzo_voidp wrkmem )
Packit Service 5195f2
{
Packit Service 5195f2
    const lzo_bytep ip;
Packit Service 5195f2
#if defined(__LZO_HASH_INCREMENTAL)
Packit Service 5195f2
    lzo_xint dv;
Packit Service 5195f2
#endif
Packit Service 5195f2
    lzo_bytep op;
Packit Service 5195f2
    const lzo_bytep m_pos;
Packit Service 5195f2
    const lzo_bytep const ip_end = in+in_len - DVAL_LEN - MIN_MATCH_LONG;
Packit Service 5195f2
    const lzo_bytep const in_end = in+in_len - DVAL_LEN;
Packit Service 5195f2
    const lzo_bytep ii;
Packit Service 5195f2
    lzo_dict_p const dict = (lzo_dict_p) wrkmem;
Packit Service 5195f2
Packit Service 5195f2
#if !defined(NDEBUG)
Packit Service 5195f2
    const lzo_bytep m_pos_sav;
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
    op = out;
Packit Service 5195f2
    ip = in;
Packit Service 5195f2
    ii = ip;                /* point to start of literal run */
Packit Service 5195f2
    if (in_len <= MIN_MATCH_LONG + DVAL_LEN + 1)
Packit Service 5195f2
        goto the_end;
Packit Service 5195f2
Packit Service 5195f2
    /* init dictionary */
Packit Service 5195f2
#if (LZO_DETERMINISTIC)
Packit Service 5195f2
    BZERO8_PTR(wrkmem,sizeof(lzo_dict_t),D_SIZE);
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
    DVAL_FIRST(dv,ip);
Packit Service 5195f2
    UPDATE_D(dict,0,dv,ip,in);
Packit Service 5195f2
    ip++;
Packit Service 5195f2
    DVAL_NEXT(dv,ip);
Packit Service 5195f2
Packit Service 5195f2
    do {
Packit Service 5195f2
        LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, m_off, 0);
Packit Service 5195f2
        lzo_uint dindex;
Packit Service 5195f2
Packit Service 5195f2
        DINDEX1(dindex,ip);
Packit Service 5195f2
        GINDEX(m_pos,m_off,dict,dindex,in);
Packit Service 5195f2
        if (LZO_CHECK_MPOS(m_pos,m_off,in,ip,MAX_OFFSET))
Packit Service 5195f2
            goto literal;
Packit Service 5195f2
        if (m_pos[0] == ip[0] && m_pos[1] == ip[1] && m_pos[2] == ip[2])
Packit Service 5195f2
            goto match;
Packit Service 5195f2
        DINDEX2(dindex,ip);
Packit Service 5195f2
        GINDEX(m_pos,m_off,dict,dindex,in);
Packit Service 5195f2
        if (LZO_CHECK_MPOS(m_pos,m_off,in,ip,MAX_OFFSET))
Packit Service 5195f2
            goto literal;
Packit Service 5195f2
        if (m_pos[0] == ip[0] && m_pos[1] == ip[1] && m_pos[2] == ip[2])
Packit Service 5195f2
            goto match;
Packit Service 5195f2
        goto literal;
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
literal:
Packit Service 5195f2
        UPDATE_I(dict,0,dindex,ip,in);
Packit Service 5195f2
        if (++ip >= ip_end)
Packit Service 5195f2
            break;
Packit Service 5195f2
        continue;
Packit Service 5195f2
Packit Service 5195f2
match:
Packit Service 5195f2
        UPDATE_I(dict,0,dindex,ip,in);
Packit Service 5195f2
#if !defined(NDEBUG) && (LZO_DICT_USE_PTR)
Packit Service 5195f2
        m_pos_sav = m_pos;
Packit Service 5195f2
#endif
Packit Service 5195f2
        m_pos += 3;
Packit Service 5195f2
        {
Packit Service 5195f2
    /* we have found a match (of at least length 3) */
Packit Service 5195f2
#if !defined(NDEBUG) && !(LZO_DICT_USE_PTR)
Packit Service 5195f2
            assert((m_pos_sav = ip - m_off) == (m_pos - 3));
Packit Service 5195f2
#endif
Packit Service 5195f2
            /* 1) store the current literal run */
Packit Service 5195f2
            if (pd(ip,ii) > 0)
Packit Service 5195f2
            {
Packit Service 5195f2
                lzo_uint t = pd(ip,ii);
Packit Service 5195f2
#if 1
Packit Service 5195f2
                /* OPTIMIZED: inline the copying of a short run */
Packit Service 5195f2
                if (t < R0MIN)
Packit Service 5195f2
                {
Packit Service 5195f2
                    *op++ = LZO_BYTE(t);
Packit Service 5195f2
                    MEMCPY_DS(op, ii, t);
Packit Service 5195f2
                }
Packit Service 5195f2
                else
Packit Service 5195f2
#endif
Packit Service 5195f2
                    op = store_run(op,ii,t);
Packit Service 5195f2
            }
Packit Service 5195f2
Packit Service 5195f2
            /* 2a) compute match len */
Packit Service 5195f2
            ii = ip;        /* point to start of current match */
Packit Service 5195f2
Packit Service 5195f2
            /* we already matched MIN_MATCH bytes,
Packit Service 5195f2
             * m_pos also already advanced MIN_MATCH bytes */
Packit Service 5195f2
            ip += MIN_MATCH;
Packit Service 5195f2
            assert(m_pos < ip);
Packit Service 5195f2
Packit Service 5195f2
            /* try to match another MIN_MATCH_LONG - MIN_MATCH bytes
Packit Service 5195f2
             * to see if we get a long match */
Packit Service 5195f2
Packit Service 5195f2
#define PS  *m_pos++ != *ip++
Packit Service 5195f2
Packit Service 5195f2
#if (MIN_MATCH_LONG - MIN_MATCH == 2)                   /* MBITS == 2 */
Packit Service 5195f2
            if (PS || PS)
Packit Service 5195f2
#elif (MIN_MATCH_LONG - MIN_MATCH == 6)                 /* MBITS == 3 */
Packit Service 5195f2
            if (PS || PS || PS || PS || PS || PS)
Packit Service 5195f2
#elif (MIN_MATCH_LONG - MIN_MATCH == 14)                /* MBITS == 4 */
Packit Service 5195f2
            if (PS || PS || PS || PS || PS || PS || PS ||
Packit Service 5195f2
                PS || PS || PS || PS || PS || PS || PS)
Packit Service 5195f2
#elif (MIN_MATCH_LONG - MIN_MATCH == 30)                /* MBITS == 5 */
Packit Service 5195f2
            if (PS || PS || PS || PS || PS || PS || PS || PS ||
Packit Service 5195f2
                PS || PS || PS || PS || PS || PS || PS || PS ||
Packit Service 5195f2
                PS || PS || PS || PS || PS || PS || PS || PS ||
Packit Service 5195f2
                PS || PS || PS || PS || PS || PS)
Packit Service 5195f2
#else
Packit Service 5195f2
#  error "MBITS not yet implemented"
Packit Service 5195f2
#endif
Packit Service 5195f2
            {
Packit Service 5195f2
                lzo_uint m_len;
Packit Service 5195f2
Packit Service 5195f2
            /* 2b) code a short match */
Packit Service 5195f2
                    assert(pd(ip,m_pos) == m_off);
Packit Service 5195f2
                --ip;   /* ran one too far, point back to non-match */
Packit Service 5195f2
                m_len = pd(ip, ii);
Packit Service 5195f2
                    assert(m_len >= MIN_MATCH_SHORT);
Packit Service 5195f2
                    assert(m_len <= MAX_MATCH_SHORT);
Packit Service 5195f2
                    assert(m_off > 0);
Packit Service 5195f2
                    assert(m_off <= MAX_OFFSET);
Packit Service 5195f2
                    assert(ii-m_off == m_pos_sav);
Packit Service 5195f2
                    assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
Packit Service 5195f2
                --m_off;
Packit Service 5195f2
                /* code short match len + low offset bits */
Packit Service 5195f2
                *op++ = LZO_BYTE(((m_len - THRESHOLD) << OBITS) |
Packit Service 5195f2
                                 (m_off & OMASK));
Packit Service 5195f2
                /* code high offset bits */
Packit Service 5195f2
                *op++ = LZO_BYTE(m_off >> OBITS);
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
            /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
Packit Service 5195f2
Packit Service 5195f2
#define SI      /* nothing */
Packit Service 5195f2
#define DI      ++ii; DVAL_NEXT(dv,ii); UPDATE_D(dict,0,dv,ii,in);
Packit Service 5195f2
#define XI      assert(ii < ip); ii = ip; DVAL_FIRST(dv,(ip));
Packit Service 5195f2
Packit Service 5195f2
#if (CLEVEL == 9) || (CLEVEL >= 7 && MBITS <= 4) || (CLEVEL >= 5 && MBITS <= 3)
Packit Service 5195f2
            /* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
Packit Service 5195f2
                ++ii;
Packit Service 5195f2
                do {
Packit Service 5195f2
                    DVAL_NEXT(dv,ii);
Packit Service 5195f2
                    UPDATE_D(dict,0,dv,ii,in);
Packit Service 5195f2
                } while (++ii < ip);
Packit Service 5195f2
                DVAL_NEXT(dv,ii);
Packit Service 5195f2
                assert(ii == ip);
Packit Service 5195f2
                DVAL_ASSERT(dv,ip);
Packit Service 5195f2
#elif (CLEVEL >= 3)
Packit Service 5195f2
                SI   DI DI   XI
Packit Service 5195f2
#elif (CLEVEL >= 2)
Packit Service 5195f2
                SI   DI      XI
Packit Service 5195f2
#else
Packit Service 5195f2
                             XI
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
            }
Packit Service 5195f2
            else
Packit Service 5195f2
            {
Packit Service 5195f2
            /* we've found a long match - see how far we can still go */
Packit Service 5195f2
                const lzo_bytep end;
Packit Service 5195f2
                lzo_uint m_len;
Packit Service 5195f2
Packit Service 5195f2
                assert(ip <= in_end);
Packit Service 5195f2
                assert(ii == ip - MIN_MATCH_LONG);
Packit Service 5195f2
Packit Service 5195f2
                if (pd(in_end,ip) <= (MAX_MATCH_LONG - MIN_MATCH_LONG))
Packit Service 5195f2
                    end = in_end;
Packit Service 5195f2
                else
Packit Service 5195f2
                {
Packit Service 5195f2
                    end = ip + (MAX_MATCH_LONG - MIN_MATCH_LONG);
Packit Service 5195f2
                    assert(end < in_end);
Packit Service 5195f2
                }
Packit Service 5195f2
Packit Service 5195f2
                while (ip < end  &&  *m_pos == *ip)
Packit Service 5195f2
                    m_pos++, ip++;
Packit Service 5195f2
                assert(ip <= in_end);
Packit Service 5195f2
Packit Service 5195f2
            /* 2b) code the long match */
Packit Service 5195f2
                m_len = pd(ip, ii);
Packit Service 5195f2
                    assert(m_len >= MIN_MATCH_LONG);
Packit Service 5195f2
                    assert(m_len <= MAX_MATCH_LONG);
Packit Service 5195f2
                    assert(m_off > 0);
Packit Service 5195f2
                    assert(m_off <= MAX_OFFSET);
Packit Service 5195f2
                    assert(ii-m_off == m_pos_sav);
Packit Service 5195f2
                    assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
Packit Service 5195f2
                    assert(pd(ip,m_pos) == m_off);
Packit Service 5195f2
                --m_off;
Packit Service 5195f2
                /* code long match flag + low offset bits */
Packit Service 5195f2
                *op++ = LZO_BYTE(((MSIZE - 1) << OBITS) | (m_off & OMASK));
Packit Service 5195f2
                /* code high offset bits */
Packit Service 5195f2
                *op++ = LZO_BYTE(m_off >> OBITS);
Packit Service 5195f2
                /* code match len */
Packit Service 5195f2
                *op++ = LZO_BYTE(m_len - MIN_MATCH_LONG);
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
            /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
Packit Service 5195f2
#if (CLEVEL == 9)
Packit Service 5195f2
            /* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
Packit Service 5195f2
            /* This is not recommended because it is slow. */
Packit Service 5195f2
                ++ii;
Packit Service 5195f2
                do {
Packit Service 5195f2
                    DVAL_NEXT(dv,ii);
Packit Service 5195f2
                    UPDATE_D(dict,0,dv,ii,in);
Packit Service 5195f2
                } while (++ii < ip);
Packit Service 5195f2
                DVAL_NEXT(dv,ii);
Packit Service 5195f2
                assert(ii == ip);
Packit Service 5195f2
                DVAL_ASSERT(dv,ip);
Packit Service 5195f2
#elif (CLEVEL >= 8)
Packit Service 5195f2
                SI   DI DI DI DI DI DI DI DI   XI
Packit Service 5195f2
#elif (CLEVEL >= 7)
Packit Service 5195f2
                SI   DI DI DI DI DI DI DI      XI
Packit Service 5195f2
#elif (CLEVEL >= 6)
Packit Service 5195f2
                SI   DI DI DI DI DI DI         XI
Packit Service 5195f2
#elif (CLEVEL >= 5)
Packit Service 5195f2
                SI   DI DI DI DI               XI
Packit Service 5195f2
#elif (CLEVEL >= 4)
Packit Service 5195f2
                SI   DI DI DI                  XI
Packit Service 5195f2
#elif (CLEVEL >= 3)
Packit Service 5195f2
                SI   DI DI                     XI
Packit Service 5195f2
#elif (CLEVEL >= 2)
Packit Service 5195f2
                SI   DI                        XI
Packit Service 5195f2
#else
Packit Service 5195f2
                                               XI
Packit Service 5195f2
#endif
Packit Service 5195f2
            }
Packit Service 5195f2
Packit Service 5195f2
            /* ii now points to the start of next literal run */
Packit Service 5195f2
            assert(ii == ip);
Packit Service 5195f2
        }
Packit Service 5195f2
    } while (ip < ip_end);
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
the_end:
Packit Service 5195f2
    assert(ip <= in_end);
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
#if defined(LZO_RETURN_IF_NOT_COMPRESSIBLE)
Packit Service 5195f2
    /* return -1 if op == out to indicate that we
Packit Service 5195f2
     * couldn't compress and didn't copy anything.
Packit Service 5195f2
     */
Packit Service 5195f2
    if (op == out)
Packit Service 5195f2
    {
Packit Service 5195f2
        *out_len = 0;
Packit Service 5195f2
        return LZO_E_NOT_COMPRESSIBLE;
Packit Service 5195f2
    }
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
    /* store the final literal run */
Packit Service 5195f2
    if (pd(in_end+DVAL_LEN,ii) > 0)
Packit Service 5195f2
        op = store_run(op,ii,pd(in_end+DVAL_LEN,ii));
Packit Service 5195f2
Packit Service 5195f2
    *out_len = pd(op, out);
Packit Service 5195f2
    return 0;               /* compression went ok */
Packit Service 5195f2
}
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// compress public entry point.
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
LZO_PUBLIC(int)
Packit Service 5195f2
lzo1_compress ( const lzo_bytep in , lzo_uint  in_len,
Packit Service 5195f2
                      lzo_bytep out, lzo_uintp out_len,
Packit Service 5195f2
                      lzo_voidp wrkmem )
Packit Service 5195f2
{
Packit Service 5195f2
    int r = LZO_E_OK;
Packit Service 5195f2
Packit Service 5195f2
    /* don't try to compress a block that's too short */
Packit Service 5195f2
    if (in_len == 0)
Packit Service 5195f2
        *out_len = 0;
Packit Service 5195f2
    else if (in_len <= MIN_MATCH_LONG + DVAL_LEN + 1)
Packit Service 5195f2
    {
Packit Service 5195f2
#if defined(LZO_RETURN_IF_NOT_COMPRESSIBLE)
Packit Service 5195f2
        r = LZO_E_NOT_COMPRESSIBLE;
Packit Service 5195f2
#else
Packit Service 5195f2
        *out_len = pd(store_run(out,in,in_len), out);
Packit Service 5195f2
#endif
Packit Service 5195f2
    }
Packit Service 5195f2
    else
Packit Service 5195f2
        r = do_compress(in,in_len,out,out_len,wrkmem);
Packit Service 5195f2
Packit Service 5195f2
    return r;
Packit Service 5195f2
}
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/*
Packit Service 5195f2
vi:ts=4:et
Packit Service 5195f2
*/