/src/lzo-2.10/src/lzo1c_9x.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* lzo1c_9x.c -- implementation of the LZO1C-999 compression algorithm |
2 | | |
3 | | This file is part of the LZO real-time data compression library. |
4 | | |
5 | | Copyright (C) 1996-2017 Markus Franz Xaver Johannes Oberhumer |
6 | | All Rights Reserved. |
7 | | |
8 | | The LZO library is free software; you can redistribute it and/or |
9 | | modify it under the terms of the GNU General Public License as |
10 | | published by the Free Software Foundation; either version 2 of |
11 | | the License, or (at your option) any later version. |
12 | | |
13 | | The LZO library is distributed in the hope that it will be useful, |
14 | | but WITHOUT ANY WARRANTY; without even the implied warranty of |
15 | | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
16 | | GNU General Public License for more details. |
17 | | |
18 | | You should have received a copy of the GNU General Public License |
19 | | along with the LZO library; see the file COPYING. |
20 | | If not, write to the Free Software Foundation, Inc., |
21 | | 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. |
22 | | |
23 | | Markus F.X.J. Oberhumer |
24 | | <markus@oberhumer.com> |
25 | | http://www.oberhumer.com/opensource/lzo/ |
26 | | */ |
27 | | |
28 | | |
29 | | #include "config1c.h" |
30 | | |
31 | | |
32 | | /*********************************************************************** |
33 | | // |
34 | | ************************************************************************/ |
35 | | |
36 | 628 | #define SWD_N 16383 /* size of ring buffer */ |
37 | 4.09M | #define SWD_THRESHOLD 2 /* lower limit for match length */ |
38 | 628 | #define SWD_F 2048 /* upper limit for match length */ |
39 | | |
40 | | |
41 | | #define LZO1C 1 |
42 | 1.25k | #define LZO_COMPRESS_T lzo1c_999_t |
43 | 628 | #define lzo_swd_t lzo1c_999_swd_t |
44 | | #include "lzo_mchw.ch" |
45 | | |
46 | | |
47 | | |
48 | | /*********************************************************************** |
49 | | // |
50 | | ************************************************************************/ |
51 | | |
52 | | static lzo_bytep |
53 | | code_match ( LZO_COMPRESS_T *c, lzo_bytep op, lzo_uint m_len, lzo_uint m_off ) |
54 | 158k | { |
55 | 158k | if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) |
56 | 100k | { |
57 | 100k | assert(m_len >= M2_MIN_LEN); |
58 | 100k | assert(m_off >= M2_MIN_OFFSET); |
59 | | |
60 | 100k | m_off -= M2_MIN_OFFSET; |
61 | | /* code match len + low offset bits */ |
62 | 100k | *op++ = LZO_BYTE(((m_len - (M2_MIN_LEN - 2)) << M2O_BITS) | |
63 | 100k | (m_off & M2O_MASK)); |
64 | | /* code high offset bits */ |
65 | 100k | *op++ = LZO_BYTE(m_off >> M2O_BITS); |
66 | 100k | c->m2_m++; |
67 | 100k | } |
68 | 58.3k | else |
69 | 58.3k | { |
70 | 58.3k | assert(m_len >= M3_MIN_LEN); |
71 | 58.3k | assert(m_off <= M3_MAX_OFFSET); |
72 | | |
73 | 58.3k | m_off -= M3_MIN_OFFSET - M3_EOF_OFFSET; |
74 | | /* code match len */ |
75 | 58.3k | if (m_len <= M3_MAX_LEN) |
76 | 43.7k | *op++ = LZO_BYTE(M3_MARKER | (m_len - (M3_MIN_LEN - 1))); |
77 | 14.5k | else |
78 | 14.5k | { |
79 | 14.5k | assert(m_len >= M4_MIN_LEN); |
80 | | /* code M4 match len flag */ |
81 | 14.5k | *op++ = M4_MARKER; |
82 | | /* code match len */ |
83 | 14.5k | m_len -= M4_MIN_LEN - 1; |
84 | 25.1k | while (m_len > 255) |
85 | 10.6k | { |
86 | 10.6k | m_len -= 255; |
87 | 10.6k | *op++ = 0; |
88 | 10.6k | } |
89 | 14.5k | assert(m_len > 0); |
90 | 14.5k | *op++ = LZO_BYTE(m_len); |
91 | 14.5k | } |
92 | | /* code low offset bits */ |
93 | 58.3k | *op++ = LZO_BYTE(m_off & M3O_MASK); |
94 | | /* code high offset bits */ |
95 | 58.3k | *op++ = LZO_BYTE(m_off >> M3O_BITS); |
96 | | |
97 | 58.3k | c->r1_m_len = 0; |
98 | 58.3k | c->m3 = op; |
99 | 58.3k | c->m3_m++; |
100 | 58.3k | } |
101 | 158k | return op; |
102 | 158k | } |
103 | | |
104 | | |
105 | | /*********************************************************************** |
106 | | // this is a public function, but there is no prototype in a header file |
107 | | ************************************************************************/ |
108 | | |
109 | | LZO_EXTERN(int) |
110 | | lzo1c_999_compress_callback ( const lzo_bytep in , lzo_uint in_len, |
111 | | lzo_bytep out, lzo_uintp out_len, |
112 | | lzo_voidp wrkmem, |
113 | | lzo_callback_p cb, |
114 | | lzo_uint max_chain ); |
115 | | |
116 | | LZO_PUBLIC(int) |
117 | | lzo1c_999_compress_callback ( const lzo_bytep in , lzo_uint in_len, |
118 | | lzo_bytep out, lzo_uintp out_len, |
119 | | lzo_voidp wrkmem, |
120 | | lzo_callback_p cb, |
121 | | lzo_uint max_chain ) |
122 | 628 | { |
123 | 628 | lzo_bytep op; |
124 | 628 | const lzo_bytep ii; |
125 | 628 | lzo_uint lit; |
126 | 628 | lzo_uint m_len, m_off; |
127 | 628 | LZO_COMPRESS_T cc; |
128 | 628 | LZO_COMPRESS_T * const c = &cc; |
129 | 628 | lzo_swd_p const swd = (lzo_swd_p) wrkmem; |
130 | 628 | int r; |
131 | | |
132 | | /* sanity check */ |
133 | 628 | LZO_COMPILE_TIME_ASSERT(LZO1C_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T) |
134 | | |
135 | 628 | c->init = 0; |
136 | 628 | c->ip = c->in = in; |
137 | 628 | c->in_end = in + in_len; |
138 | 628 | c->cb = cb; |
139 | 628 | c->r1_r = c->m3_r = c->m2_m = c->m3_m = 0; |
140 | | |
141 | 628 | op = out; |
142 | 628 | ii = c->ip; /* point to start of literal run */ |
143 | 628 | lit = 0; |
144 | 628 | c->r1_m_len = 0; |
145 | 628 | c->m3 = out + 1; /* pointer after last m3/m4 match */ |
146 | | |
147 | 628 | r = init_match(c,swd,NULL,0,0); |
148 | 628 | if (r != 0) |
149 | 0 | return r; |
150 | 628 | if (max_chain > 0) |
151 | 0 | swd->max_chain = max_chain; |
152 | | |
153 | 628 | r = find_match(c,swd,0,0); |
154 | 628 | if (r != 0) |
155 | 0 | return r; |
156 | 3.98M | while (c->look > 0) |
157 | 3.98M | { |
158 | 3.98M | int lazy_match_min_gain = -1; |
159 | 3.98M | lzo_uint ahead = 0; |
160 | | |
161 | 3.98M | m_len = c->m_len; |
162 | 3.98M | m_off = c->m_off; |
163 | | |
164 | | #if 0 |
165 | | printf("%5ld: %5d len:%3d off:%5d\n", (c->ip-c->look)-in, c->look, |
166 | | m_len, m_off); |
167 | | #endif |
168 | | |
169 | 3.98M | assert(c->ip - c->look >= in); |
170 | 3.98M | if (lit == 0) |
171 | 158k | ii = c->ip - c->look; |
172 | 3.98M | assert(ii + lit == c->ip - c->look); |
173 | 3.98M | assert(swd->b_char == *(c->ip - c->look)); |
174 | | |
175 | 3.98M | if ((m_len < M2_MIN_LEN) || |
176 | 3.98M | (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET)) |
177 | 3.79M | { |
178 | 3.79M | m_len = 0; |
179 | 3.79M | } |
180 | 182k | else |
181 | 182k | { |
182 | 182k | assert(c->ip - c->look - m_off >= in); |
183 | 182k | assert(c->ip - c->look - m_off + m_len < c->ip); |
184 | 182k | assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off, |
185 | 182k | m_len) == 0); |
186 | | |
187 | 182k | if (lit > 0) |
188 | 102k | { |
189 | | /* we have a current literal run: do not try a lazy match, |
190 | | if the literal could be coded into a r1 or m3 match */ |
191 | 102k | if (lit == 1 && c->r1_m_len == M2_MIN_LEN) |
192 | 6.96k | lazy_match_min_gain = -1; |
193 | 95.4k | else if (lit == 3 && op == c->m3) |
194 | 3.77k | lazy_match_min_gain = -1; |
195 | 91.6k | else if (lit < 3 && op == c->m3) |
196 | 27.7k | lazy_match_min_gain = 0; |
197 | 63.9k | else |
198 | 63.9k | lazy_match_min_gain = 1; |
199 | | |
200 | | #if (M2_MIN_LEN == 2) |
201 | | if (m_len == 2) |
202 | | { |
203 | | /* don't code a match of len 2 if we have to |
204 | | code a literal run. Code a literal instead. */ |
205 | | m_len = 0; |
206 | | } |
207 | | #endif |
208 | | #if (M2_MIN_LEN == M3_MIN_LEN) |
209 | | if (m_len == M2_MIN_LEN && m_off > M2_MAX_OFFSET) |
210 | | { |
211 | | /* don't code a M3 match of len 3 if we have to |
212 | | code a literal run. Code a literal instead. */ |
213 | | m_len = 0; |
214 | | } |
215 | | #endif |
216 | 102k | } |
217 | 80.5k | else |
218 | 80.5k | { |
219 | | /* no current literal run: only try a lazy match, |
220 | | if the literal could be coded into a r1 or m3 match */ |
221 | 80.5k | if (c->r1_m_len == M2_MIN_LEN || op == c->m3) |
222 | 41.2k | lazy_match_min_gain = 0; |
223 | 39.2k | else |
224 | 39.2k | lazy_match_min_gain = -1; |
225 | 80.5k | } |
226 | 182k | } |
227 | | |
228 | | |
229 | | /* try a lazy match */ |
230 | 3.98M | if (m_len == 0) |
231 | 3.79M | lazy_match_min_gain = -1; |
232 | 3.98M | if (lazy_match_min_gain >= 0 && c->look > m_len) |
233 | 132k | { |
234 | 132k | assert(m_len > 0); |
235 | | |
236 | 132k | r = find_match(c,swd,1,0); |
237 | 132k | assert(r == 0); LZO_UNUSED(r); |
238 | 132k | assert(c->look > 0); |
239 | | |
240 | 132k | if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET && |
241 | 132k | c->m_off > M2_MAX_OFFSET) |
242 | 2.23k | lazy_match_min_gain += 1; |
243 | | |
244 | 132k | if (c->m_len >= m_len + lazy_match_min_gain) |
245 | 24.4k | { |
246 | 24.4k | c->lazy++; |
247 | | #if !defined(NDEBUG) |
248 | | m_len = c->m_len; |
249 | | m_off = c->m_off; |
250 | | assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off, |
251 | | m_len) == 0); |
252 | | #endif |
253 | 24.4k | lit++; |
254 | 24.4k | assert(ii + lit == c->ip - c->look); |
255 | 24.4k | continue; |
256 | 24.4k | } |
257 | 108k | else |
258 | 108k | { |
259 | 108k | ahead = 1; |
260 | 108k | assert(ii + lit + 1 == c->ip - c->look); |
261 | 108k | } |
262 | 108k | assert(m_len > 0); |
263 | 108k | } |
264 | 3.95M | assert(ii + lit + ahead == c->ip - c->look); |
265 | | |
266 | | |
267 | 3.95M | if (m_len == 0) |
268 | 3.79M | { |
269 | | /* a literal */ |
270 | 3.79M | lit++; |
271 | 3.79M | r = find_match(c,swd,1,0); |
272 | 3.79M | assert(r == 0); LZO_UNUSED(r); |
273 | 3.79M | } |
274 | 158k | else |
275 | 158k | { |
276 | | /* 1 - store run */ |
277 | 158k | if (lit > 0) |
278 | 88.5k | { |
279 | | /* code current literal run */ |
280 | 88.5k | if (lit == 1 && c->r1_m_len == M2_MIN_LEN) |
281 | 6.96k | { |
282 | | /* Code a context sensitive R1 match. */ |
283 | 6.96k | assert((op[-2] >> M2O_BITS) == (M2_MARKER >> M2O_BITS)); |
284 | 6.96k | op[-2] &= M2O_MASK; |
285 | 6.96k | assert((op[-2] >> M2O_BITS) == 0); |
286 | | /* copy 1 literal */ |
287 | 6.96k | *op++ = *ii++; |
288 | 6.96k | assert(ii + ahead == c->ip - c->look); |
289 | 6.96k | c->r1_r++; |
290 | 6.96k | } |
291 | 81.5k | else if (lit < 4 && op == c->m3) |
292 | 25.6k | { |
293 | 25.6k | assert((c->m3[-2] >> M3O_BITS) == 0); |
294 | 25.6k | c->m3[-2] = LZO_BYTE(c->m3[-2] | (lit << M3O_BITS)); |
295 | 25.6k | MEMCPY_DS(op, ii, lit); |
296 | 25.6k | assert(ii + ahead == c->ip - c->look); |
297 | 25.6k | c->m3_r++; |
298 | 25.6k | } |
299 | 55.9k | else |
300 | 55.9k | { |
301 | 55.9k | op = STORE_RUN(op,ii,lit); |
302 | 55.9k | } |
303 | 88.5k | if (lit < R0FAST) |
304 | 86.6k | c->r1_m_len = m_len; |
305 | 1.94k | else |
306 | 1.94k | c->r1_m_len = 0; |
307 | 88.5k | lit = 0; |
308 | 88.5k | } |
309 | 69.9k | else |
310 | 69.9k | c->r1_m_len = 0; |
311 | | |
312 | | /* 2 - code match */ |
313 | 158k | op = code_match(c,op,m_len,m_off); |
314 | 158k | r = find_match(c,swd,m_len,1+ahead); |
315 | 158k | assert(r == 0); LZO_UNUSED(r); |
316 | 158k | } |
317 | | |
318 | 3.95M | c->codesize = pd(op, out); |
319 | 3.95M | } |
320 | | |
321 | | |
322 | | /* store final run */ |
323 | 628 | if (lit > 0) |
324 | 404 | op = STORE_RUN(op,ii,lit); |
325 | | |
326 | 628 | #if defined(LZO_EOF_CODE) |
327 | 628 | *op++ = M3_MARKER | 1; |
328 | 628 | *op++ = 0; |
329 | 628 | *op++ = 0; |
330 | 628 | #endif |
331 | | |
332 | 628 | c->codesize = pd(op, out); |
333 | 628 | assert(c->textsize == in_len); |
334 | | |
335 | 628 | *out_len = pd(op, out); |
336 | | |
337 | 628 | if (c->cb && c->cb->nprogress) |
338 | 0 | (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0); |
339 | | |
340 | | #if 0 |
341 | | printf("%ld %ld -> %ld: %ld %ld %ld %ld %ld\n", |
342 | | (long) c->textsize, (long)in_len, (long) c->codesize, |
343 | | c->r1_r, c->m3_r, c->m2_m, c->m3_m, c->lazy); |
344 | | #endif |
345 | 628 | return LZO_E_OK; |
346 | 628 | } |
347 | | |
348 | | |
349 | | |
350 | | /*********************************************************************** |
351 | | // |
352 | | ************************************************************************/ |
353 | | |
354 | | LZO_PUBLIC(int) |
355 | | lzo1c_999_compress ( const lzo_bytep in , lzo_uint in_len, |
356 | | lzo_bytep out, lzo_uintp out_len, |
357 | | lzo_voidp wrkmem ) |
358 | 628 | { |
359 | 628 | return lzo1c_999_compress_callback(in,in_len,out,out_len,wrkmem, |
360 | 628 | (lzo_callback_p) 0, 0); |
361 | 628 | } |
362 | | |
363 | | |
364 | | /* vim:set ts=4 sw=4 et: */ |