/* lzo1b_sm.ch -- implementation of the LZO1B compression algorithm

   This file is part of the LZO real-time data compression library.

   Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer
   All Rights Reserved.

   The LZO library is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of
   the License, or (at your option) any later version.

   The LZO library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with the LZO library; see the file COPYING.
   If not, write to the Free Software Foundation, Inc.,
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

   Markus F.X.J. Oberhumer
   <markus@oberhumer.com>
   http://www.oberhumer.com/opensource/lzo/
 */


/* WARNING: this file should *not* be used by applications. It is
   part of the implementation of the library and is subject
   to change.
 */



/***********************************************************************
// search for a match
************************************************************************/

#if (DD_BITS == 0)

        /* search ip in the dictionary */
        DINDEX1(dindex,ip);
        GINDEX(m_pos,m_off,dict,dindex,in);
        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET))
            goto literal;
#if 1
        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
            goto try_match;
        DINDEX2(dindex,ip);
#endif
        GINDEX(m_pos,m_off,dict,dindex,in);
        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET))
            goto literal;
        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
            goto try_match;
        goto literal;


#else /* (DD_BITS == 0) */



        /* search ip in the deepened dictionary */
        {
            lzo_dict_p d = &dict [ DINDEX(dv,ip) ];
            const lzo_bytep ip_sav;
            unsigned j = DD_SIZE;
            lzo_uint x_len;
            LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, x_off, 0);

            DVAL_ASSERT(dv,ip);

            ip_sav = ip;
            m_len = 0;
            do {
#if !defined(NDEBUG)
                const lzo_bytep z_pos = NULL;
#endif
#if (LZO_DICT_USE_PTR)
                m_pos = *d;
                assert((z_pos = m_pos) == *d);
#if (LZO_DETERMINISTIC)
                assert(m_pos == NULL || m_pos >= in);
                assert(m_pos == NULL || m_pos < ip);
#endif
#else
                x_off = *d;
#endif
                assert(ip == ip_sav);

                if (LZO_CHECK_MPOS(m_pos,x_off,in,ip,MAX_OFFSET))
#if (CLEVEL == 9)
                    *d = DENTRY(ip,in);
#else
                    ((void)(0));
#endif
                else if (m_pos[m_len] != ip[m_len])
                    ((void)(0));
                else if (*m_pos++ == *ip++ && *m_pos++ == *ip++ && *m_pos++ == *ip++)
                {
#if !(LZO_DICT_USE_PTR)
                    assert((z_pos = ip - 3 - x_off) == (m_pos - 3));
#endif
                    /* a match */
                    if (MATCH_M2)
                    {
                        x_len = pd((ip - 1), ip_sav);
                        if (x_len > m_len)
                        {
                            m_len = x_len;
                            m_off = x_off;
                            assert((m_pos_sav = z_pos) != NULL);
                        }
#if (CLEVEL == 9)
                        /* try to find a closer match */
                        else if (x_len == m_len && x_off < m_off)
                        {
                            m_off = x_off;
                            assert((m_pos_sav = z_pos) != NULL);
                        }
#endif
                    }
                    else
                    {
                        assert((ip - ip_sav) == M2_MAX_LEN + 1);
#if (CLEVEL == 9)
#if defined(MATCH_IP_END)
                        {
                            const lzo_bytep end;
                            end = MATCH_IP_END;
                            while (ip < end  &&  *m_pos == *ip)
                                m_pos++, ip++;
                            assert(ip <= in_end);
                            x_len = pd(ip, ip_sav);
                        }
                        if (x_len > m_len)
                        {
                            m_len = x_len;
                            m_off = x_off;
                            assert((m_pos_sav = z_pos) != NULL);
                            if (ip >= MATCH_IP_END)
                            {
                                ip = ip_sav;
#if 0
                                /* not needed - we are at the end */
                                d -= DD_SIZE - j;
                                assert(d == &dict [ DINDEX(dv,ip) ]);
                                UPDATE_P(d,drun,ip,in);
#endif
                                goto match;
                            }
                        }
                        else if (x_len == m_len && x_off < m_off)
                        {
                            m_off = x_off;
                            assert((m_pos_sav = z_pos) != NULL);
                        }
#else
                        /* try to find a closer match */
                        if (m_len < M2_MAX_LEN + 1 || x_off < m_off)
                        {
                            m_len = M2_MAX_LEN + 1;
                            m_off = x_off;
                            assert((m_pos_sav = z_pos) != NULL);
                        }
#endif
#else
                        /* don't search for a longer/closer match */
                        m_len = M2_MAX_LEN + 1;
                        m_off = x_off;
                        assert((m_pos_sav = z_pos) != NULL);
                        ip = ip_sav;
                        d -= DD_SIZE - j;
                        assert(d == &dict [ DINDEX(dv,ip) ]);
                        UPDATE_P(d,drun,ip,in);
                        goto match;
#endif
                    }
                    ip = ip_sav;
                }
                else
                    ip = ip_sav;
                d++;
            } while (--j > 0);
            assert(ip == ip_sav);

            d -= DD_SIZE;
            assert(d == &dict [ DINDEX(dv,ip) ]);
            UPDATE_P(d,drun,ip,in);
        }

#endif /* (DD_BITS == 0) */


/*
vi:ts=4:et
*/