kusano 7d535a
/* lzo1a_cm.ch -- implementation of the LZO1A 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
/* WARNING: this file should *not* be used by applications. It is
kusano 7d535a
   part of the implementation of the library and is subject
kusano 7d535a
   to change.
kusano 7d535a
 */
kusano 7d535a
kusano 7d535a
kusano 7d535a
kusano 7d535a
/***********************************************************************
kusano 7d535a
// code the match in LZO1 compatible format
kusano 7d535a
************************************************************************/
kusano 7d535a
kusano 7d535a
#define THRESHOLD   (M2_MIN_LEN - 1)
kusano 7d535a
#define MSIZE       LZO_SIZE(M2L_BITS)
kusano 7d535a
kusano 7d535a
kusano 7d535a
/***********************************************************************
kusano 7d535a
//
kusano 7d535a
************************************************************************/
kusano 7d535a
kusano 7d535a
#if (DD_BITS == 0)
kusano 7d535a
kusano 7d535a
        /* we already matched M2_MIN_LEN bytes,
kusano 7d535a
         * m_pos also already advanced M2_MIN_LEN bytes */
kusano 7d535a
        ip += M2_MIN_LEN;
kusano 7d535a
        assert(m_pos < ip);
kusano 7d535a
kusano 7d535a
        /* try to match another M2_MAX_LEN + 1 - M2_MIN_LEN bytes
kusano 7d535a
         * to see if we get more than a M2 match */
kusano 7d535a
#define M2_OR_M3    (MATCH_M2)
kusano 7d535a
kusano 7d535a
#else /* (DD_BITS == 0) */
kusano 7d535a
kusano 7d535a
        /* we already matched m_len bytes */
kusano 7d535a
        assert(m_len >= M2_MIN_LEN);
kusano 7d535a
        ip += m_len;
kusano 7d535a
        assert(ip <= in_end);
kusano 7d535a
kusano 7d535a
#define M2_OR_M3    (m_len <= M2_MAX_LEN)
kusano 7d535a
kusano 7d535a
#endif /* (DD_BITS == 0) */
kusano 7d535a
kusano 7d535a
kusano 7d535a
        if (M2_OR_M3)
kusano 7d535a
        {
kusano 7d535a
        /* we've found a short match */
kusano 7d535a
            assert(ip <= in_end);
kusano 7d535a
kusano 7d535a
        /* 2a) compute match parameters */
kusano 7d535a
#if (DD_BITS == 0)
kusano 7d535a
                assert(pd(ip,m_pos) == m_off);
kusano 7d535a
            --ip;   /* ran one too far, point back to non-match */
kusano 7d535a
            m_len = ip - ii;
kusano 7d535a
#endif
kusano 7d535a
                assert(m_len >= M2_MIN_LEN);
kusano 7d535a
                assert(m_len <= M2_MAX_LEN);
kusano 7d535a
kusano 7d535a
                assert(m_off >= M2_MIN_OFFSET);
kusano 7d535a
                assert(m_off <= M2_MAX_OFFSET);
kusano 7d535a
                assert(ii-m_off == m_pos_sav);
kusano 7d535a
                assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
kusano 7d535a
kusano 7d535a
        /* 2b) code the match */
kusano 7d535a
            m_off -= M2_MIN_OFFSET;
kusano 7d535a
            /* code short match len + low offset bits */
kusano 7d535a
            *op++ = LZO_BYTE(((m_len - THRESHOLD) << 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
kusano 7d535a
kusano 7d535a
            if (ip >= ip_end)
kusano 7d535a
            {
kusano 7d535a
                ii = ip;
kusano 7d535a
                break;
kusano 7d535a
            }
kusano 7d535a
kusano 7d535a
kusano 7d535a
        /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
kusano 7d535a
kusano 7d535a
#if (CLEVEL == 9) || (CLEVEL >= 7 && M2L_BITS <= 4) || (CLEVEL >= 5 && M2L_BITS <= 3)
kusano 7d535a
        /* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
kusano 7d535a
            ++ii;
kusano 7d535a
            do {
kusano 7d535a
                DVAL_NEXT(dv,ii);
kusano 7d535a
#if 0
kusano 7d535a
                UPDATE_D(dict,drun,dv,ii,in);
kusano 7d535a
#else
kusano 7d535a
                dict[ DINDEX(dv,ii) ] = DENTRY(ii,in);
kusano 7d535a
#endif
kusano 7d535a
                MI
kusano 7d535a
            } while (++ii < ip);
kusano 7d535a
            DVAL_NEXT(dv,ii);
kusano 7d535a
            assert(ii == ip);
kusano 7d535a
            DVAL_ASSERT(dv,ip);
kusano 7d535a
#elif (CLEVEL >= 3)
kusano 7d535a
            SI   DI DI   XI
kusano 7d535a
#elif (CLEVEL >= 2)
kusano 7d535a
            SI   DI      XI
kusano 7d535a
#else
kusano 7d535a
                         XI
kusano 7d535a
#endif
kusano 7d535a
        }
kusano 7d535a
kusano 7d535a
        else
kusano 7d535a
kusano 7d535a
        {
kusano 7d535a
        /* we've found a long match - see how far we can still go */
kusano 7d535a
            const lzo_bytep end;
kusano 7d535a
kusano 7d535a
            assert(ip <= in_end);
kusano 7d535a
            assert(ii == ip - (M2_MAX_LEN + 1));
kusano 7d535a
            assert(lzo_memcmp(m_pos_sav,ii,(lzo_uint)(ip-ii)) == 0);
kusano 7d535a
kusano 7d535a
#if (DD_BITS > 0)
kusano 7d535a
            assert(m_len == (lzo_uint)(ip-ii));
kusano 7d535a
            m_pos = ip - m_off;
kusano 7d535a
            assert(m_pos == m_pos_sav + m_len);
kusano 7d535a
#endif
kusano 7d535a
kusano 7d535a
            if (pd(in_end,ip) <= (M3_MAX_LEN - M3_MIN_LEN))
kusano 7d535a
                end = in_end;
kusano 7d535a
            else
kusano 7d535a
            {
kusano 7d535a
                end = ip + (M3_MAX_LEN - M3_MIN_LEN);
kusano 7d535a
                assert(end < in_end);
kusano 7d535a
            }
kusano 7d535a
kusano 7d535a
            while (ip < end  &&  *m_pos == *ip)
kusano 7d535a
                m_pos++, ip++;
kusano 7d535a
            assert(ip <= in_end);
kusano 7d535a
kusano 7d535a
            /* 2a) compute match parameters */
kusano 7d535a
            m_len = pd(ip, ii);
kusano 7d535a
                assert(m_len >= M3_MIN_LEN);
kusano 7d535a
                assert(m_len <= M3_MAX_LEN);
kusano 7d535a
kusano 7d535a
                assert(m_off >= M3_MIN_OFFSET);
kusano 7d535a
                assert(m_off <= M3_MAX_OFFSET);
kusano 7d535a
                assert(ii-m_off == m_pos_sav);
kusano 7d535a
                assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
kusano 7d535a
                assert(pd(ip,m_pos) == m_off);
kusano 7d535a
kusano 7d535a
        /* 2b) code the match */
kusano 7d535a
            m_off -= M3_MIN_OFFSET - M3_EOF_OFFSET;
kusano 7d535a
            /* code long match flag + low offset bits */
kusano 7d535a
            *op++ = LZO_BYTE(((MSIZE - 1) << M3O_BITS) | (m_off & M3O_MASK));
kusano 7d535a
            /* code high offset bits */
kusano 7d535a
            *op++ = LZO_BYTE(m_off >> M3O_BITS);
kusano 7d535a
            /* code match len */
kusano 7d535a
            *op++ = LZO_BYTE(m_len - M3_MIN_LEN);
kusano 7d535a
kusano 7d535a
kusano 7d535a
            if (ip >= ip_end)
kusano 7d535a
            {
kusano 7d535a
                ii = ip;
kusano 7d535a
                break;
kusano 7d535a
            }
kusano 7d535a
kusano 7d535a
kusano 7d535a
        /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
kusano 7d535a
#if (CLEVEL == 9)
kusano 7d535a
        /* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
kusano 7d535a
        /* This is not recommended because it can be slow. */
kusano 7d535a
            ++ii;
kusano 7d535a
            do {
kusano 7d535a
                DVAL_NEXT(dv,ii);
kusano 7d535a
#if 0
kusano 7d535a
                UPDATE_D(dict,drun,dv,ii,in);
kusano 7d535a
#else
kusano 7d535a
                dict[ DINDEX(dv,ii) ] = DENTRY(ii,in);
kusano 7d535a
#endif
kusano 7d535a
                MI
kusano 7d535a
            } while (++ii < ip);
kusano 7d535a
            DVAL_NEXT(dv,ii);
kusano 7d535a
            assert(ii == ip);
kusano 7d535a
            DVAL_ASSERT(dv,ip);
kusano 7d535a
#elif (CLEVEL >= 8)
kusano 7d535a
            SI   DI DI DI DI DI DI DI DI   XI
kusano 7d535a
#elif (CLEVEL >= 7)
kusano 7d535a
            SI   DI DI DI DI DI DI DI      XI
kusano 7d535a
#elif (CLEVEL >= 6)
kusano 7d535a
            SI   DI DI DI DI DI DI         XI
kusano 7d535a
#elif (CLEVEL >= 5)
kusano 7d535a
            SI   DI DI DI DI               XI
kusano 7d535a
#elif (CLEVEL >= 4)
kusano 7d535a
            SI   DI DI DI                  XI
kusano 7d535a
#elif (CLEVEL >= 3)
kusano 7d535a
            SI   DI DI                     XI
kusano 7d535a
#elif (CLEVEL >= 2)
kusano 7d535a
            SI   DI                        XI
kusano 7d535a
#else
kusano 7d535a
                                           XI
kusano 7d535a
#endif
kusano 7d535a
        }
kusano 7d535a
kusano 7d535a
        /* ii now points to the start of the next literal run */
kusano 7d535a
        assert(ii == ip);
kusano 7d535a
kusano 7d535a
kusano 7d535a
/*
kusano 7d535a
vi:ts=4:et
kusano 7d535a
*/