1 /* lzo1b_c.ch -- implementation of the LZO1B compression algorithm
3 This file is part of the LZO real-time data compression library.
5 Copyright (C) 2011 Markus Franz Xaver Johannes Oberhumer
6 Copyright (C) 2010 Markus Franz Xaver Johannes Oberhumer
7 Copyright (C) 2009 Markus Franz Xaver Johannes Oberhumer
8 Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
9 Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
10 Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
11 Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
12 Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
13 Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
14 Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
15 Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
16 Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
17 Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
18 Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
19 Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
20 Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
23 The LZO library is free software; you can redistribute it and/or
24 modify it under the terms of the GNU General Public License as
25 published by the Free Software Foundation; either version 2 of
26 the License, or (at your option) any later version.
28 The LZO library is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU General Public License for more details.
33 You should have received a copy of the GNU General Public License
34 along with the LZO library; see the file COPYING.
35 If not, write to the Free Software Foundation, Inc.,
36 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
38 Markus F.X.J. Oberhumer
39 <markus@oberhumer.com>
40 http://www.oberhumer.com/opensource/lzo/
45 /***********************************************************************
47 ************************************************************************/
49 #if !defined(LZO_HAVE_R1) && !defined(LZO_NO_R1)
50 # define LZO_HAVE_R1 1
53 #if !defined(LZO_HAVE_M3) && !defined(LZO_NO_M3)
55 # define LZO_HAVE_M3 1
63 #define DI ++ii; DVAL_NEXT(dv,ii); UPDATE_D(dict,drun,dv,ii,in); MI
64 #define XI assert(ii < ip); ii = ip; DVAL_FIRST(dv,(ip));
66 #define DI ++ii; DINDEX1(dindex,ii); UPDATE_I(dict,0,dindex,ii,in); MI
67 #define XI assert(ii < ip); ii = ip;
71 /***********************************************************************
72 // compress a block of data.
74 // I really apologize for this spaghetti code.
75 ************************************************************************/
78 do_compress ( const lzo_bytep in , lzo_uint in_len,
79 lzo_bytep out, lzo_uintp out_len,
82 register const lzo_bytep ip;
84 #if defined(__LZO_HASH_INCREMENTAL)
90 const lzo_bytep const in_end = in + in_len;
91 const lzo_bytep const ip_end = in + in_len - MIN_LOOKAHEAD;
93 #if defined(LZO_HAVE_R1)
94 const lzo_bytep r1 = ip_end; /* pointer for R1 match (none yet) */
96 #if defined(LZO_HAVE_M3)
97 lzo_bytep m3 = out + 1; /* pointer after last m3/m4 match */
100 lzo_dict_p const dict = (lzo_dict_p) wrkmem;
103 #if (LZO_COLLECT_STATS)
104 lzo_stats->r_bits = R_BITS;
105 lzo_stats->m3o_bits = M3O_BITS;
106 lzo_stats->dd_bits = DD_BITS;
107 lzo_stats->clevel = CLEVEL;
108 lzo_stats->d_bits = D_BITS;
109 lzo_stats->min_lookahead = MIN_LOOKAHEAD;
110 lzo_stats->max_lookbehind = MAX_LOOKBEHIND;
111 lzo_stats->compress_id = LZO_CPP_MACRO_EXPAND(COMPRESS_ID);
114 /* init dictionary */
115 #if (LZO_DETERMINISTIC)
116 BZERO8_PTR(wrkmem,sizeof(lzo_dict_t),D_SIZE);
122 ii = ip; /* point to start of current literal run */
127 UPDATE_D(dict,drun,dv,ip,in);
137 const lzo_bytep m_pos;
139 const lzo_bytep m_pos_sav = NULL;
141 LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, m_off, 0);
148 /***********************************************************************
149 // search for a match
150 ************************************************************************/
152 #if !defined(LZO_SEARCH_MATCH_INCLUDE_FILE)
153 # define LZO_SEARCH_MATCH_INCLUDE_FILE "lzo1b_sm.ch"
156 #include LZO_SEARCH_MATCH_INCLUDE_FILE
159 #if !defined(LZO_TEST_MATCH_INCLUDE_FILE)
160 # define LZO_TEST_MATCH_INCLUDE_FILE "lzo1b_tm.ch"
163 #include LZO_TEST_MATCH_INCLUDE_FILE
167 /***********************************************************************
169 ************************************************************************/
175 UPDATE_I(dict,0,dindex,ip,in);
186 /***********************************************************************
188 ************************************************************************/
192 UPDATE_I(dict,0,dindex,ip,in);
194 /* we have found a match of at least M2_MIN_LEN */
197 #if !defined(LZO_CODE_RUN_INCLUDE_FILE)
198 # define LZO_CODE_RUN_INCLUDE_FILE "lzo1b_cr.ch"
201 #include LZO_CODE_RUN_INCLUDE_FILE
204 /* ii now points to the start of the current match */
208 /***********************************************************************
210 ************************************************************************/
212 #if !defined(LZO_CODE_MATCH_INCLUDE_FILE)
213 # define LZO_CODE_MATCH_INCLUDE_FILE "lzo1b_cm.ch"
216 #include LZO_CODE_MATCH_INCLUDE_FILE
219 /* ii now points to the start of the next literal run */
225 /***********************************************************************
227 ************************************************************************/
229 assert(ip <= in_end);
231 #if (LZO_COLLECT_STATS)
236 for (i = 0; i < D_SIZE; i++)
239 if (BOUNDS_CHECKING_OFF_IN_EXPR(p == NULL || p < in || p > in_end))
240 lzo_stats->unused_dict_entries++;
242 lzo_stats->unused_dict_entries_percent =
243 100.0 * lzo_stats->unused_dict_entries / D_SIZE;
248 #if defined(LZO_RETURN_IF_NOT_COMPRESSIBLE)
249 /* return if op == out to indicate that we
250 * couldn't compress and didn't copy anything.
255 return LZO_E_NOT_COMPRESSIBLE;
259 /* store the final literal run */
260 if (pd(in_end,ii) > 0)
262 lzo_uint t = pd(in_end,ii);
263 op = STORE_RUN(op,ii,t);
266 *out_len = pd(op, out);
267 return LZO_E_OK; /* compression went ok */