1 /* lzo1b_sm.ch -- implementation of the LZO1B compression algorithm
3 This file is part of the LZO real-time data compression library.
5 Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
6 Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
7 Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
8 Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
9 Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
10 Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
11 Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
12 Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
13 Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
14 Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
15 Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
16 Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
17 Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
20 The LZO library is free software; you can redistribute it and/or
21 modify it under the terms of the GNU General Public License as
22 published by the Free Software Foundation; either version 2 of
23 the License, or (at your option) any later version.
25 The LZO library is distributed in the hope that it will be useful,
26 but WITHOUT ANY WARRANTY; without even the implied warranty of
27 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28 GNU General Public License for more details.
30 You should have received a copy of the GNU General Public License
31 along with the LZO library; see the file COPYING.
32 If not, write to the Free Software Foundation, Inc.,
33 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
35 Markus F.X.J. Oberhumer
36 <markus@oberhumer.com>
37 http://www.oberhumer.com/opensource/lzo/
41 /* WARNING: this file should *not* be used by applications. It is
42 part of the implementation of the library and is subject
48 /***********************************************************************
50 ************************************************************************/
54 /* search ip in the dictionary */
56 GINDEX(m_pos,m_off,dict,dindex,in);
57 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET))
60 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
64 GINDEX(m_pos,m_off,dict,dindex,in);
65 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET))
67 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
72 #else /* (DD_BITS == 0) */
76 /* search ip in the deepened dictionary */
78 lzo_dict_p d = &dict [ DINDEX(dv,ip) ];
79 const lzo_bytep ip_sav;
90 const lzo_bytep z_pos = NULL;
92 #if defined(LZO_DICT_USE_PTR)
94 assert((z_pos = m_pos) == *d);
95 #if defined(LZO_DETERMINISTIC)
96 assert(m_pos == NULL || m_pos >= in);
97 assert(m_pos == NULL || m_pos < ip);
102 assert(ip == ip_sav);
104 if (LZO_CHECK_MPOS(m_pos,x_off,in,ip,MAX_OFFSET))
110 else if (m_pos[m_len] != ip[m_len])
112 else if (*m_pos++ == *ip++ && *m_pos++ == *ip++ && *m_pos++ == *ip++)
114 #if !defined(LZO_DICT_USE_PTR)
115 assert((z_pos = ip - 3 - x_off) == (m_pos - 3));
120 x_len = pd((ip - 1), ip_sav);
125 assert((m_pos_sav = z_pos) != NULL);
128 /* try to find a closer match */
129 else if (x_len == m_len && x_off < m_off)
132 assert((m_pos_sav = z_pos) != NULL);
138 assert((ip - ip_sav) == M2_MAX_LEN + 1);
140 #if defined(MATCH_IP_END)
144 while (ip < end && *m_pos == *ip)
146 assert(ip <= in_end);
147 x_len = pd(ip, ip_sav);
153 assert((m_pos_sav = z_pos) != NULL);
154 if (ip >= MATCH_IP_END)
158 /* not needed - we are at the end */
160 assert(d == &dict [ DINDEX(dv,ip) ]);
161 UPDATE_P(d,drun,ip,in);
166 else if (x_len == m_len && x_off < m_off)
169 assert((m_pos_sav = z_pos) != NULL);
172 /* try to find a closer match */
173 if (m_len < M2_MAX_LEN + 1 || x_off < m_off)
175 m_len = M2_MAX_LEN + 1;
177 assert((m_pos_sav = z_pos) != NULL);
181 /* don't search for a longer/closer match */
182 m_len = M2_MAX_LEN + 1;
184 assert((m_pos_sav = z_pos) != NULL);
187 assert(d == &dict [ DINDEX(dv,ip) ]);
188 UPDATE_P(d,drun,ip,in);
198 assert(ip == ip_sav);
201 assert(d == &dict [ DINDEX(dv,ip) ]);
202 UPDATE_P(d,drun,ip,in);
205 #endif /* (DD_BITS == 0) */