Blame src/lzo1b_sm.ch

Packit Service 5195f2
/* lzo1b_sm.ch -- implementation of the LZO1B compression 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
/* WARNING: this file should *not* be used by applications. It is
Packit Service 5195f2
   part of the implementation of the library and is subject
Packit Service 5195f2
   to change.
Packit Service 5195f2
 */
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// search for a match
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
#if (DD_BITS == 0)
Packit Service 5195f2
Packit Service 5195f2
        /* search ip in the dictionary */
Packit Service 5195f2
        DINDEX1(dindex,ip);
Packit Service 5195f2
        GINDEX(m_pos,m_off,dict,dindex,in);
Packit Service 5195f2
        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET))
Packit Service 5195f2
            goto literal;
Packit Service 5195f2
#if 1
Packit Service 5195f2
        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
Packit Service 5195f2
            goto try_match;
Packit Service 5195f2
        DINDEX2(dindex,ip);
Packit Service 5195f2
#endif
Packit Service 5195f2
        GINDEX(m_pos,m_off,dict,dindex,in);
Packit Service 5195f2
        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET))
Packit Service 5195f2
            goto literal;
Packit Service 5195f2
        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
Packit Service 5195f2
            goto try_match;
Packit Service 5195f2
        goto literal;
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
#else /* (DD_BITS == 0) */
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
        /* search ip in the deepened dictionary */
Packit Service 5195f2
        {
Packit Service 5195f2
            lzo_dict_p d = &dict [ DINDEX(dv,ip) ];
Packit Service 5195f2
            const lzo_bytep ip_sav;
Packit Service 5195f2
            unsigned j = DD_SIZE;
Packit Service 5195f2
            lzo_uint x_len;
Packit Service 5195f2
            LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, x_off, 0);
Packit Service 5195f2
Packit Service 5195f2
            DVAL_ASSERT(dv,ip);
Packit Service 5195f2
Packit Service 5195f2
            ip_sav = ip;
Packit Service 5195f2
            m_len = 0;
Packit Service 5195f2
            do {
Packit Service 5195f2
#if !defined(NDEBUG)
Packit Service 5195f2
                const lzo_bytep z_pos = NULL;
Packit Service 5195f2
#endif
Packit Service 5195f2
#if (LZO_DICT_USE_PTR)
Packit Service 5195f2
                m_pos = *d;
Packit Service 5195f2
                assert((z_pos = m_pos) == *d);
Packit Service 5195f2
#if (LZO_DETERMINISTIC)
Packit Service 5195f2
                assert(m_pos == NULL || m_pos >= in);
Packit Service 5195f2
                assert(m_pos == NULL || m_pos < ip);
Packit Service 5195f2
#endif
Packit Service 5195f2
#else
Packit Service 5195f2
                x_off = *d;
Packit Service 5195f2
#endif
Packit Service 5195f2
                assert(ip == ip_sav);
Packit Service 5195f2
Packit Service 5195f2
                if (LZO_CHECK_MPOS(m_pos,x_off,in,ip,MAX_OFFSET))
Packit Service 5195f2
#if (CLEVEL == 9)
Packit Service 5195f2
                    *d = DENTRY(ip,in);
Packit Service 5195f2
#else
Packit Service 5195f2
                    ((void)(0));
Packit Service 5195f2
#endif
Packit Service 5195f2
                else if (m_pos[m_len] != ip[m_len])
Packit Service 5195f2
                    ((void)(0));
Packit Service 5195f2
                else if (*m_pos++ == *ip++ && *m_pos++ == *ip++ && *m_pos++ == *ip++)
Packit Service 5195f2
                {
Packit Service 5195f2
#if !(LZO_DICT_USE_PTR)
Packit Service 5195f2
                    assert((z_pos = ip - 3 - x_off) == (m_pos - 3));
Packit Service 5195f2
#endif
Packit Service 5195f2
                    /* a match */
Packit Service 5195f2
                    if (MATCH_M2)
Packit Service 5195f2
                    {
Packit Service 5195f2
                        x_len = pd((ip - 1), ip_sav);
Packit Service 5195f2
                        if (x_len > m_len)
Packit Service 5195f2
                        {
Packit Service 5195f2
                            m_len = x_len;
Packit Service 5195f2
                            m_off = x_off;
Packit Service 5195f2
                            assert((m_pos_sav = z_pos) != NULL);
Packit Service 5195f2
                        }
Packit Service 5195f2
#if (CLEVEL == 9)
Packit Service 5195f2
                        /* try to find a closer match */
Packit Service 5195f2
                        else if (x_len == m_len && x_off < m_off)
Packit Service 5195f2
                        {
Packit Service 5195f2
                            m_off = x_off;
Packit Service 5195f2
                            assert((m_pos_sav = z_pos) != NULL);
Packit Service 5195f2
                        }
Packit Service 5195f2
#endif
Packit Service 5195f2
                    }
Packit Service 5195f2
                    else
Packit Service 5195f2
                    {
Packit Service 5195f2
                        assert((ip - ip_sav) == M2_MAX_LEN + 1);
Packit Service 5195f2
#if (CLEVEL == 9)
Packit Service 5195f2
#if defined(MATCH_IP_END)
Packit Service 5195f2
                        {
Packit Service 5195f2
                            const lzo_bytep end;
Packit Service 5195f2
                            end = MATCH_IP_END;
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
                            x_len = pd(ip, ip_sav);
Packit Service 5195f2
                        }
Packit Service 5195f2
                        if (x_len > m_len)
Packit Service 5195f2
                        {
Packit Service 5195f2
                            m_len = x_len;
Packit Service 5195f2
                            m_off = x_off;
Packit Service 5195f2
                            assert((m_pos_sav = z_pos) != NULL);
Packit Service 5195f2
                            if (ip >= MATCH_IP_END)
Packit Service 5195f2
                            {
Packit Service 5195f2
                                ip = ip_sav;
Packit Service 5195f2
#if 0
Packit Service 5195f2
                                /* not needed - we are at the end */
Packit Service 5195f2
                                d -= DD_SIZE - j;
Packit Service 5195f2
                                assert(d == &dict [ DINDEX(dv,ip) ]);
Packit Service 5195f2
                                UPDATE_P(d,drun,ip,in);
Packit Service 5195f2
#endif
Packit Service 5195f2
                                goto match;
Packit Service 5195f2
                            }
Packit Service 5195f2
                        }
Packit Service 5195f2
                        else if (x_len == m_len && x_off < m_off)
Packit Service 5195f2
                        {
Packit Service 5195f2
                            m_off = x_off;
Packit Service 5195f2
                            assert((m_pos_sav = z_pos) != NULL);
Packit Service 5195f2
                        }
Packit Service 5195f2
#else
Packit Service 5195f2
                        /* try to find a closer match */
Packit Service 5195f2
                        if (m_len < M2_MAX_LEN + 1 || x_off < m_off)
Packit Service 5195f2
                        {
Packit Service 5195f2
                            m_len = M2_MAX_LEN + 1;
Packit Service 5195f2
                            m_off = x_off;
Packit Service 5195f2
                            assert((m_pos_sav = z_pos) != NULL);
Packit Service 5195f2
                        }
Packit Service 5195f2
#endif
Packit Service 5195f2
#else
Packit Service 5195f2
                        /* don't search for a longer/closer match */
Packit Service 5195f2
                        m_len = M2_MAX_LEN + 1;
Packit Service 5195f2
                        m_off = x_off;
Packit Service 5195f2
                        assert((m_pos_sav = z_pos) != NULL);
Packit Service 5195f2
                        ip = ip_sav;
Packit Service 5195f2
                        d -= DD_SIZE - j;
Packit Service 5195f2
                        assert(d == &dict [ DINDEX(dv,ip) ]);
Packit Service 5195f2
                        UPDATE_P(d,drun,ip,in);
Packit Service 5195f2
                        goto match;
Packit Service 5195f2
#endif
Packit Service 5195f2
                    }
Packit Service 5195f2
                    ip = ip_sav;
Packit Service 5195f2
                }
Packit Service 5195f2
                else
Packit Service 5195f2
                    ip = ip_sav;
Packit Service 5195f2
                d++;
Packit Service 5195f2
            } while (--j > 0);
Packit Service 5195f2
            assert(ip == ip_sav);
Packit Service 5195f2
Packit Service 5195f2
            d -= DD_SIZE;
Packit Service 5195f2
            assert(d == &dict [ DINDEX(dv,ip) ]);
Packit Service 5195f2
            UPDATE_P(d,drun,ip,in);
Packit Service 5195f2
        }
Packit Service 5195f2
Packit Service 5195f2
#endif /* (DD_BITS == 0) */
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/*
Packit Service 5195f2
vi:ts=4:et
Packit Service 5195f2
*/