|
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 |
*/
|