kusano 7d535a
/* lzo1b_9x.c -- implementation of the LZO1B-999 compression algorithm
kusano 7d535a
kusano 7d535a
   This file is part of the LZO real-time data compression library.
kusano 7d535a
kusano 7d535a
   Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   All Rights Reserved.
kusano 7d535a
kusano 7d535a
   The LZO library is free software; you can redistribute it and/or
kusano 7d535a
   modify it under the terms of the GNU General Public License as
kusano 7d535a
   published by the Free Software Foundation; either version 2 of
kusano 7d535a
   the License, or (at your option) any later version.
kusano 7d535a
kusano 7d535a
   The LZO library is distributed in the hope that it will be useful,
kusano 7d535a
   but WITHOUT ANY WARRANTY; without even the implied warranty of
kusano 7d535a
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
kusano 7d535a
   GNU General Public License for more details.
kusano 7d535a
kusano 7d535a
   You should have received a copy of the GNU General Public License
kusano 7d535a
   along with the LZO library; see the file COPYING.
kusano 7d535a
   If not, write to the Free Software Foundation, Inc.,
kusano 7d535a
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
kusano 7d535a
kusano 7d535a
   Markus F.X.J. Oberhumer
kusano 7d535a
   <markus@oberhumer.com></markus@oberhumer.com>
kusano 7d535a
   http://www.oberhumer.com/opensource/lzo/
kusano 7d535a
 */
kusano 7d535a
kusano 7d535a
kusano 7d535a
#include "config1b.h"
kusano 7d535a
kusano 7d535a
kusano 7d535a
/***********************************************************************
kusano 7d535a
//
kusano 7d535a
************************************************************************/
kusano 7d535a
kusano 7d535a
#define N          0xffffL          /* size of ring buffer */
kusano 7d535a
#define THRESHOLD       2           /* lower limit for match length */
kusano 7d535a
#define F            2048           /* upper limit for match length */
kusano 7d535a
kusano 7d535a
kusano 7d535a
#define LZO1B
kusano 7d535a
#define LZO_COMPRESS_T  lzo1b_999_t
kusano 7d535a
#define lzo_swd_t       lzo1b_999_swd_t
kusano 7d535a
#include "lzo_mchw.ch"
kusano 7d535a
kusano 7d535a
kusano 7d535a
kusano 7d535a
/***********************************************************************
kusano 7d535a
//
kusano 7d535a
************************************************************************/
kusano 7d535a
kusano 7d535a
static lzo_bytep
kusano 7d535a
code_match ( LZO_COMPRESS_T *c, lzo_bytep op, lzo_uint m_len, lzo_uint m_off )
kusano 7d535a
{
kusano 7d535a
    if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
kusano 7d535a
    {
kusano 7d535a
        assert(m_len >= M2_MIN_LEN);
kusano 7d535a
        assert(m_off >= M2_MIN_OFFSET);
kusano 7d535a
kusano 7d535a
        m_off -= M2_MIN_OFFSET;
kusano 7d535a
        /* code match len + low offset bits */
kusano 7d535a
        *op++ = LZO_BYTE(((m_len - (M2_MIN_LEN - 2)) << M2O_BITS) |
kusano 7d535a
                          (m_off & M2O_MASK));
kusano 7d535a
        /* code high offset bits */
kusano 7d535a
        *op++ = LZO_BYTE(m_off >> M2O_BITS);
kusano 7d535a
        c->m2_m++;
kusano 7d535a
    }
kusano 7d535a
    else
kusano 7d535a
    {
kusano 7d535a
        assert(m_len >= M3_MIN_LEN);
kusano 7d535a
        assert(m_off <= M3_MAX_OFFSET);
kusano 7d535a
kusano 7d535a
        m_off -= M3_MIN_OFFSET - M3_EOF_OFFSET;
kusano 7d535a
        /* code match len */
kusano 7d535a
        if (m_len <= M3_MAX_LEN)
kusano 7d535a
            *op++ = LZO_BYTE(M3_MARKER | (m_len - (M3_MIN_LEN - 1)));
kusano 7d535a
        else
kusano 7d535a
        {
kusano 7d535a
            assert(m_len >= M4_MIN_LEN);
kusano 7d535a
            /* code M4 match len flag */
kusano 7d535a
            *op++ = M4_MARKER;
kusano 7d535a
            /* code match len */
kusano 7d535a
            m_len -= M4_MIN_LEN - 1;
kusano 7d535a
            while (m_len > 255)
kusano 7d535a
            {
kusano 7d535a
                m_len -= 255;
kusano 7d535a
                *op++ = 0;
kusano 7d535a
            }
kusano 7d535a
            assert(m_len > 0);
kusano 7d535a
            *op++ = LZO_BYTE(m_len);
kusano 7d535a
        }
kusano 7d535a
        /* code low offset bits */
kusano 7d535a
        *op++ = LZO_BYTE(m_off & M3O_MASK);
kusano 7d535a
        /* code high offset bits */
kusano 7d535a
        *op++ = LZO_BYTE(m_off >> M3O_BITS);
kusano 7d535a
kusano 7d535a
        c->r1_m_len = 0;
kusano 7d535a
        c->m3_m++;
kusano 7d535a
    }
kusano 7d535a
    return op;
kusano 7d535a
}
kusano 7d535a
kusano 7d535a
kusano 7d535a
/***********************************************************************
kusano 7d535a
// this is a public function, but there is no prototype in a header file
kusano 7d535a
************************************************************************/
kusano 7d535a
kusano 7d535a
LZO_EXTERN(int)
kusano 7d535a
lzo1b_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
kusano 7d535a
                                    lzo_bytep out, lzo_uintp out_len,
kusano 7d535a
                                    lzo_voidp wrkmem,
kusano 7d535a
                                    lzo_callback_p cb,
kusano 7d535a
                                    lzo_uint max_chain );
kusano 7d535a
kusano 7d535a
LZO_PUBLIC(int)
kusano 7d535a
lzo1b_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
kusano 7d535a
                                    lzo_bytep out, lzo_uintp out_len,
kusano 7d535a
                                    lzo_voidp wrkmem,
kusano 7d535a
                                    lzo_callback_p cb,
kusano 7d535a
                                    lzo_uint max_chain )
kusano 7d535a
{
kusano 7d535a
    lzo_bytep op;
kusano 7d535a
    const lzo_bytep ii;
kusano 7d535a
    lzo_uint lit;
kusano 7d535a
    lzo_uint m_len, m_off;
kusano 7d535a
    LZO_COMPRESS_T cc;
kusano 7d535a
    LZO_COMPRESS_T * const c = &cc;
kusano 7d535a
    lzo_swd_p const swd = (lzo_swd_p) wrkmem;
kusano 7d535a
    int r;
kusano 7d535a
kusano 7d535a
    /* sanity check */
kusano 7d535a
    LZO_COMPILE_TIME_ASSERT(LZO1B_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
kusano 7d535a
kusano 7d535a
    c->init = 0;
kusano 7d535a
    c->ip = c->in = in;
kusano 7d535a
    c->in_end = in + in_len;
kusano 7d535a
    c->cb = cb;
kusano 7d535a
    c->r1_r = c->m3_r = c->m2_m = c->m3_m = 0;
kusano 7d535a
kusano 7d535a
    op = out;
kusano 7d535a
    ii = c->ip;             /* point to start of literal run */
kusano 7d535a
    lit = 0;
kusano 7d535a
    c->r1_m_len = 0;
kusano 7d535a
kusano 7d535a
    r = init_match(c,swd,NULL,0,0);
kusano 7d535a
    if (r != 0)
kusano 7d535a
        return r;
kusano 7d535a
    if (max_chain > 0)
kusano 7d535a
        swd->max_chain = max_chain;
kusano 7d535a
kusano 7d535a
    r = find_match(c,swd,0,0);
kusano 7d535a
    if (r != 0)
kusano 7d535a
        return r;
kusano 7d535a
    while (c->look > 0)
kusano 7d535a
    {
kusano 7d535a
        int lazy_match_min_gain = -1;
kusano 7d535a
        lzo_uint ahead = 0;
kusano 7d535a
kusano 7d535a
        m_len = c->m_len;
kusano 7d535a
        m_off = c->m_off;
kusano 7d535a
kusano 7d535a
#if 0
kusano 7d535a
        printf("%5ld: %5d len:%3d off:%5d\n", (c->ip-c->look)-in, c->look,
kusano 7d535a
                m_len, m_off);
kusano 7d535a
#endif
kusano 7d535a
kusano 7d535a
        assert(c->ip - c->look >= in);
kusano 7d535a
        if (lit == 0)
kusano 7d535a
            ii = c->ip - c->look;
kusano 7d535a
        assert(ii + lit == c->ip - c->look);
kusano 7d535a
        assert(swd->b_char == *(c->ip - c->look));
kusano 7d535a
kusano 7d535a
        if ((m_len < M2_MIN_LEN) ||
kusano 7d535a
            (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET))
kusano 7d535a
        {
kusano 7d535a
            m_len = 0;
kusano 7d535a
        }
kusano 7d535a
        else
kusano 7d535a
        {
kusano 7d535a
            assert(c->ip - c->look - m_off >= in);
kusano 7d535a
            assert(c->ip - c->look - m_off + m_len < c->ip);
kusano 7d535a
            assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
kusano 7d535a
                              m_len) == 0);
kusano 7d535a
kusano 7d535a
            if (lit > 0)
kusano 7d535a
            {
kusano 7d535a
                /* we have a current literal run: do not try a lazy match,
kusano 7d535a
                   if the literal could be coded into a r1 match */
kusano 7d535a
                if (lit == 1 && c->r1_m_len == M2_MIN_LEN)
kusano 7d535a
                    lazy_match_min_gain = -1;
kusano 7d535a
                else
kusano 7d535a
                    lazy_match_min_gain = 1;
kusano 7d535a
kusano 7d535a
#if (M2_MIN_LEN == 2)
kusano 7d535a
                if (m_len == 2)
kusano 7d535a
                {
kusano 7d535a
                    /* don't code a match of len 2 if we have to
kusano 7d535a
                       code a literal run. Code a literal instead. */
kusano 7d535a
                    m_len = 0;
kusano 7d535a
                }
kusano 7d535a
#endif
kusano 7d535a
#if (M2_MIN_LEN == M3_MIN_LEN)
kusano 7d535a
                if (m_len == M2_MIN_LEN && m_off > M2_MAX_OFFSET)
kusano 7d535a
                {
kusano 7d535a
                    /* don't code a M3 match of len 3 if we have to
kusano 7d535a
                       code a literal run. Code a literal instead. */
kusano 7d535a
                    m_len = 0;
kusano 7d535a
                }
kusano 7d535a
#endif
kusano 7d535a
            }
kusano 7d535a
            else
kusano 7d535a
            {
kusano 7d535a
                /* no current literal run: only try a lazy match,
kusano 7d535a
                   if the literal could be coded into a r1 match */
kusano 7d535a
                if (c->r1_m_len == M2_MIN_LEN)
kusano 7d535a
                    lazy_match_min_gain = 0;
kusano 7d535a
                else
kusano 7d535a
                    lazy_match_min_gain = -1;
kusano 7d535a
            }
kusano 7d535a
        }
kusano 7d535a
kusano 7d535a
kusano 7d535a
        /* try a lazy match */
kusano 7d535a
        if (m_len == 0)
kusano 7d535a
            lazy_match_min_gain = -1;
kusano 7d535a
        if (lazy_match_min_gain >= 0 && c->look > m_len)
kusano 7d535a
        {
kusano 7d535a
            assert(m_len > 0);
kusano 7d535a
kusano 7d535a
            r = find_match(c,swd,1,0);
kusano 7d535a
            assert(r == 0);
kusano 7d535a
            assert(c->look > 0);
kusano 7d535a
kusano 7d535a
            if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET &&
kusano 7d535a
                c->m_off > M2_MAX_OFFSET)
kusano 7d535a
                lazy_match_min_gain += 1;
kusano 7d535a
kusano 7d535a
            if (c->m_len >= m_len + lazy_match_min_gain)
kusano 7d535a
            {
kusano 7d535a
                c->lazy++;
kusano 7d535a
#if !defined(NDEBUG)
kusano 7d535a
                m_len = c->m_len;
kusano 7d535a
                m_off = c->m_off;
kusano 7d535a
                assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
kusano 7d535a
                                  m_len) == 0);
kusano 7d535a
#endif
kusano 7d535a
                lit++;
kusano 7d535a
                assert(ii + lit == c->ip - c->look);
kusano 7d535a
                continue;
kusano 7d535a
            }
kusano 7d535a
            else
kusano 7d535a
            {
kusano 7d535a
                ahead = 1;
kusano 7d535a
                assert(ii + lit + 1 == c->ip - c->look);
kusano 7d535a
            }
kusano 7d535a
            assert(m_len > 0);
kusano 7d535a
        }
kusano 7d535a
        assert(ii + lit + ahead == c->ip - c->look);
kusano 7d535a
kusano 7d535a
kusano 7d535a
        if (m_len == 0)
kusano 7d535a
        {
kusano 7d535a
            /* a literal */
kusano 7d535a
            lit++;
kusano 7d535a
            r = find_match(c,swd,1,0);
kusano 7d535a
            assert(r == 0);
kusano 7d535a
        }
kusano 7d535a
        else
kusano 7d535a
        {
kusano 7d535a
            /* 1 - store run */
kusano 7d535a
            if (lit > 0)
kusano 7d535a
            {
kusano 7d535a
                /* code current literal run */
kusano 7d535a
                if (lit == 1 && c->r1_m_len == M2_MIN_LEN)
kusano 7d535a
                {
kusano 7d535a
                    /* Code a context sensitive R1 match. */
kusano 7d535a
                    assert((op[-2] >> M2O_BITS) == (M2_MARKER >> M2O_BITS));
kusano 7d535a
                    op[-2] &= M2O_MASK;
kusano 7d535a
                    assert((op[-2] >> M2O_BITS) == 0);
kusano 7d535a
                    /* copy 1 literal */
kusano 7d535a
                    *op++ = *ii++;
kusano 7d535a
                    assert(ii + ahead == c->ip - c->look);
kusano 7d535a
                    c->r1_r++;
kusano 7d535a
                }
kusano 7d535a
                else
kusano 7d535a
                {
kusano 7d535a
                    op = STORE_RUN(op,ii,lit);
kusano 7d535a
                }
kusano 7d535a
                if (lit < R0FAST)
kusano 7d535a
                    c->r1_m_len = m_len;
kusano 7d535a
                else
kusano 7d535a
                    c->r1_m_len = 0;
kusano 7d535a
                lit = 0;
kusano 7d535a
            }
kusano 7d535a
            else
kusano 7d535a
                c->r1_m_len = 0;
kusano 7d535a
kusano 7d535a
            /* 2 - code match */
kusano 7d535a
            op = code_match(c,op,m_len,m_off);
kusano 7d535a
            r = find_match(c,swd,m_len,1+ahead);
kusano 7d535a
            assert(r == 0);
kusano 7d535a
        }
kusano 7d535a
kusano 7d535a
        c->codesize = pd(op, out);
kusano 7d535a
    }
kusano 7d535a
kusano 7d535a
kusano 7d535a
    /* store final run */
kusano 7d535a
    if (lit > 0)
kusano 7d535a
        op = STORE_RUN(op,ii,lit);
kusano 7d535a
kusano 7d535a
#if defined(LZO_EOF_CODE)
kusano 7d535a
    *op++ = M3_MARKER | 1;
kusano 7d535a
    *op++ = 0;
kusano 7d535a
    *op++ = 0;
kusano 7d535a
#endif
kusano 7d535a
kusano 7d535a
    c->codesize = pd(op, out);
kusano 7d535a
    assert(c->textsize == in_len);
kusano 7d535a
kusano 7d535a
    *out_len = pd(op, out);
kusano 7d535a
kusano 7d535a
    if (c->cb && c->cb->nprogress)
kusano 7d535a
        (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
kusano 7d535a
kusano 7d535a
#if 0
kusano 7d535a
    printf("%ld %ld -> %ld: %ld %ld %ld %ld %ld\n",
kusano 7d535a
        (long) c->textsize, (long)in_len, (long) c->codesize,
kusano 7d535a
        c->r1_r, c->m3_r, c->m2_m, c->m3_m, c->lazy);
kusano 7d535a
#endif
kusano 7d535a
    return LZO_E_OK;
kusano 7d535a
}
kusano 7d535a
kusano 7d535a
kusano 7d535a
kusano 7d535a
/***********************************************************************
kusano 7d535a
//
kusano 7d535a
************************************************************************/
kusano 7d535a
kusano 7d535a
LZO_PUBLIC(int)
kusano 7d535a
lzo1b_999_compress  ( const lzo_bytep in , lzo_uint  in_len,
kusano 7d535a
                            lzo_bytep out, lzo_uintp out_len,
kusano 7d535a
                            lzo_voidp wrkmem )
kusano 7d535a
{
kusano 7d535a
    return lzo1b_999_compress_callback(in,in_len,out,out_len,wrkmem,
kusano 7d535a
                                       (lzo_callback_p) 0, 0);
kusano 7d535a
}
kusano 7d535a
kusano 7d535a
kusano 7d535a
/*
kusano 7d535a
vi:ts=4:et
kusano 7d535a
*/
kusano 7d535a