1 /* lzo1b_9x.c -- implementation of the LZO1B-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 "config1b.h"
30
31
32 /***********************************************************************
33 //
34 ************************************************************************/
35
36 #define SWD_N 0xffffL /* size of ring buffer */
37 #define SWD_THRESHOLD 2 /* lower limit for match length */
38 #define SWD_F 2048 /* upper limit for match length */
39
40
41 #define LZO1B 1
42 #define LZO_COMPRESS_T lzo1b_999_t
43 #define lzo_swd_t lzo1b_999_swd_t
44 #include "lzo_mchw.ch"
45
46
47
48 /***********************************************************************
49 //
50 ************************************************************************/
51
52 static lzo_bytep
code_match(LZO_COMPRESS_T * c,lzo_bytep op,lzo_uint m_len,lzo_uint m_off)53 code_match ( LZO_COMPRESS_T *c, lzo_bytep op, lzo_uint m_len, lzo_uint m_off )
54 {
55 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
56 {
57 assert(m_len >= M2_MIN_LEN);
58 assert(m_off >= M2_MIN_OFFSET);
59
60 m_off -= M2_MIN_OFFSET;
61 /* code match len + low offset bits */
62 *op++ = LZO_BYTE(((m_len - (M2_MIN_LEN - 2)) << M2O_BITS) |
63 (m_off & M2O_MASK));
64 /* code high offset bits */
65 *op++ = LZO_BYTE(m_off >> M2O_BITS);
66 c->m2_m++;
67 }
68 else
69 {
70 assert(m_len >= M3_MIN_LEN);
71 assert(m_off <= M3_MAX_OFFSET);
72
73 m_off -= M3_MIN_OFFSET - M3_EOF_OFFSET;
74 /* code match len */
75 if (m_len <= M3_MAX_LEN)
76 *op++ = LZO_BYTE(M3_MARKER | (m_len - (M3_MIN_LEN - 1)));
77 else
78 {
79 assert(m_len >= M4_MIN_LEN);
80 /* code M4 match len flag */
81 *op++ = M4_MARKER;
82 /* code match len */
83 m_len -= M4_MIN_LEN - 1;
84 while (m_len > 255)
85 {
86 m_len -= 255;
87 *op++ = 0;
88 }
89 assert(m_len > 0);
90 *op++ = LZO_BYTE(m_len);
91 }
92 /* code low offset bits */
93 *op++ = LZO_BYTE(m_off & M3O_MASK);
94 /* code high offset bits */
95 *op++ = LZO_BYTE(m_off >> M3O_BITS);
96
97 c->r1_m_len = 0;
98 c->m3_m++;
99 }
100 return op;
101 }
102
103
104 /***********************************************************************
105 // this is a public function, but there is no prototype in a header file
106 ************************************************************************/
107
108 LZO_EXTERN(int)
109 lzo1b_999_compress_callback ( const lzo_bytep in , lzo_uint in_len,
110 lzo_bytep out, lzo_uintp out_len,
111 lzo_voidp wrkmem,
112 lzo_callback_p cb,
113 lzo_uint max_chain );
114
115 LZO_PUBLIC(int)
lzo1b_999_compress_callback(const lzo_bytep in,lzo_uint in_len,lzo_bytep out,lzo_uintp out_len,lzo_voidp wrkmem,lzo_callback_p cb,lzo_uint max_chain)116 lzo1b_999_compress_callback ( const lzo_bytep in , lzo_uint in_len,
117 lzo_bytep out, lzo_uintp out_len,
118 lzo_voidp wrkmem,
119 lzo_callback_p cb,
120 lzo_uint max_chain )
121 {
122 lzo_bytep op;
123 const lzo_bytep ii;
124 lzo_uint lit;
125 lzo_uint m_len, m_off;
126 LZO_COMPRESS_T cc;
127 LZO_COMPRESS_T * const c = &cc;
128 lzo_swd_p const swd = (lzo_swd_p) wrkmem;
129 int r;
130
131 /* sanity check */
132 LZO_COMPILE_TIME_ASSERT(LZO1B_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
133
134 c->init = 0;
135 c->ip = c->in = in;
136 c->in_end = in + in_len;
137 c->cb = cb;
138 c->r1_r = c->m3_r = c->m2_m = c->m3_m = 0;
139
140 op = out;
141 ii = c->ip; /* point to start of literal run */
142 lit = 0;
143 c->r1_m_len = 0;
144
145 r = init_match(c,swd,NULL,0,0);
146 if (r != 0)
147 return r;
148 if (max_chain > 0)
149 swd->max_chain = max_chain;
150
151 r = find_match(c,swd,0,0);
152 if (r != 0)
153 return r;
154 while (c->look > 0)
155 {
156 int lazy_match_min_gain = -1;
157 lzo_uint ahead = 0;
158
159 m_len = c->m_len;
160 m_off = c->m_off;
161
162 #if 0
163 printf("%5ld: %5d len:%3d off:%5d\n", (c->ip-c->look)-in, c->look,
164 m_len, m_off);
165 #endif
166
167 assert(c->ip - c->look >= in);
168 if (lit == 0)
169 ii = c->ip - c->look;
170 assert(ii + lit == c->ip - c->look);
171 assert(swd->b_char == *(c->ip - c->look));
172
173 if ((m_len < M2_MIN_LEN) ||
174 (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET))
175 {
176 m_len = 0;
177 }
178 else
179 {
180 assert(c->ip - c->look - m_off >= in);
181 assert(c->ip - c->look - m_off + m_len < c->ip);
182 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
183 m_len) == 0);
184
185 if (lit > 0)
186 {
187 /* we have a current literal run: do not try a lazy match,
188 if the literal could be coded into a r1 match */
189 if (lit == 1 && c->r1_m_len == M2_MIN_LEN)
190 lazy_match_min_gain = -1;
191 else
192 lazy_match_min_gain = 1;
193
194 #if (M2_MIN_LEN == 2)
195 if (m_len == 2)
196 {
197 /* don't code a match of len 2 if we have to
198 code a literal run. Code a literal instead. */
199 m_len = 0;
200 }
201 #endif
202 #if (M2_MIN_LEN == M3_MIN_LEN)
203 if (m_len == M2_MIN_LEN && m_off > M2_MAX_OFFSET)
204 {
205 /* don't code a M3 match of len 3 if we have to
206 code a literal run. Code a literal instead. */
207 m_len = 0;
208 }
209 #endif
210 }
211 else
212 {
213 /* no current literal run: only try a lazy match,
214 if the literal could be coded into a r1 match */
215 if (c->r1_m_len == M2_MIN_LEN)
216 lazy_match_min_gain = 0;
217 else
218 lazy_match_min_gain = -1;
219 }
220 }
221
222
223 /* try a lazy match */
224 if (m_len == 0)
225 lazy_match_min_gain = -1;
226 if (lazy_match_min_gain >= 0 && c->look > m_len)
227 {
228 assert(m_len > 0);
229
230 r = find_match(c,swd,1,0);
231 assert(r == 0); LZO_UNUSED(r);
232 assert(c->look > 0);
233
234 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET &&
235 c->m_off > M2_MAX_OFFSET)
236 lazy_match_min_gain += 1;
237
238 if (c->m_len >= m_len + lazy_match_min_gain)
239 {
240 c->lazy++;
241 #if !defined(NDEBUG)
242 m_len = c->m_len;
243 m_off = c->m_off;
244 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
245 m_len) == 0);
246 #endif
247 lit++;
248 assert(ii + lit == c->ip - c->look);
249 continue;
250 }
251 else
252 {
253 ahead = 1;
254 assert(ii + lit + 1 == c->ip - c->look);
255 }
256 assert(m_len > 0);
257 }
258 assert(ii + lit + ahead == c->ip - c->look);
259
260
261 if (m_len == 0)
262 {
263 /* a literal */
264 lit++;
265 r = find_match(c,swd,1,0);
266 assert(r == 0); LZO_UNUSED(r);
267 }
268 else
269 {
270 /* 1 - store run */
271 if (lit > 0)
272 {
273 /* code current literal run */
274 if (lit == 1 && c->r1_m_len == M2_MIN_LEN)
275 {
276 /* Code a context sensitive R1 match. */
277 assert((op[-2] >> M2O_BITS) == (M2_MARKER >> M2O_BITS));
278 op[-2] &= M2O_MASK;
279 assert((op[-2] >> M2O_BITS) == 0);
280 /* copy 1 literal */
281 *op++ = *ii++;
282 assert(ii + ahead == c->ip - c->look);
283 c->r1_r++;
284 }
285 else
286 {
287 op = STORE_RUN(op,ii,lit);
288 }
289 if (lit < R0FAST)
290 c->r1_m_len = m_len;
291 else
292 c->r1_m_len = 0;
293 lit = 0;
294 }
295 else
296 c->r1_m_len = 0;
297
298 /* 2 - code match */
299 op = code_match(c,op,m_len,m_off);
300 r = find_match(c,swd,m_len,1+ahead);
301 assert(r == 0); LZO_UNUSED(r);
302 }
303
304 c->codesize = pd(op, out);
305 }
306
307
308 /* store final run */
309 if (lit > 0)
310 op = STORE_RUN(op,ii,lit);
311
312 #if defined(LZO_EOF_CODE)
313 *op++ = M3_MARKER | 1;
314 *op++ = 0;
315 *op++ = 0;
316 #endif
317
318 c->codesize = pd(op, out);
319 assert(c->textsize == in_len);
320
321 *out_len = pd(op, out);
322
323 if (c->cb && c->cb->nprogress)
324 (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
325
326 #if 0
327 printf("%ld %ld -> %ld: %ld %ld %ld %ld %ld\n",
328 (long) c->textsize, (long)in_len, (long) c->codesize,
329 c->r1_r, c->m3_r, c->m2_m, c->m3_m, c->lazy);
330 #endif
331 return LZO_E_OK;
332 }
333
334
335
336 /***********************************************************************
337 //
338 ************************************************************************/
339
340 LZO_PUBLIC(int)
lzo1b_999_compress(const lzo_bytep in,lzo_uint in_len,lzo_bytep out,lzo_uintp out_len,lzo_voidp wrkmem)341 lzo1b_999_compress ( const lzo_bytep in , lzo_uint in_len,
342 lzo_bytep out, lzo_uintp out_len,
343 lzo_voidp wrkmem )
344 {
345 return lzo1b_999_compress_callback(in,in_len,out,out_len,wrkmem,
346 (lzo_callback_p) 0, 0);
347 }
348
349
350 /* vim:set ts=4 sw=4 et: */
351