diff options
Diffstat (limited to 'src/lzo1b_sm.ch')
| -rw-r--r-- | src/lzo1b_sm.ch | 213 |
1 files changed, 213 insertions, 0 deletions
diff --git a/src/lzo1b_sm.ch b/src/lzo1b_sm.ch new file mode 100644 index 0000000..89ba3a7 --- /dev/null +++ b/src/lzo1b_sm.ch @@ -0,0 +1,213 @@ +/* lzo1b_sm.ch -- implementation of the LZO1B compression algorithm + + This file is part of the LZO real-time data compression library. + + Copyright (C) 2011 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2010 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2009 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1996 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 +*/ |