1 /* lzo1f_9x.c -- implementation of the LZO1F-999 compression algorithm
3 This file is part of the LZO real-time data compression library.
5 Copyright (C) 1996-2015 Markus Franz Xaver Johannes Oberhumer
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.
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.
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.
23 Markus F.X.J. Oberhumer
24 <markus@oberhumer.com>
25 http://www.oberhumer.com/opensource/lzo/
32 /***********************************************************************
34 ************************************************************************/
36 #define SWD_N 16383 /* size of ring buffer */
37 #define SWD_THRESHOLD 2 /* lower limit for match length */
38 #define SWD_F 2048 /* upper limit for match length */
42 #define LZO_COMPRESS_T lzo1f_999_t
43 #define lzo_swd_t lzo1f_999_swd_t
44 #include "lzo_mchw.ch"
48 /***********************************************************************
50 ************************************************************************/
53 code_match ( LZO_COMPRESS_T
*c
, lzo_bytep op
, lzo_uint m_len
, lzo_uint m_off
)
55 if (m_len
<= M2_MAX_LEN
&& m_off
<= M2_MAX_OFFSET
)
58 *op
++ = LZO_BYTE(((m_len
- 2) << 5) | ((m_off
& 7) << 2));
59 *op
++ = LZO_BYTE(m_off
>> 3);
62 else if (m_len
== M2_MIN_LEN
&& m_off
<= 2 * M2_MAX_OFFSET
&&
65 assert(m_off
> M2_MAX_OFFSET
);
66 m_off
-= 1 + M2_MAX_OFFSET
;
67 *op
++ = LZO_BYTE(((m_off
& 7) << 2));
68 *op
++ = LZO_BYTE(m_off
>> 3);
73 if (m_len
<= M3_MAX_LEN
)
74 *op
++ = LZO_BYTE(M3_MARKER
| (m_len
- 2));
78 *op
++ = M3_MARKER
| 0;
85 *op
++ = LZO_BYTE(m_len
);
87 *op
++ = LZO_BYTE((m_off
& 63) << 2);
88 *op
++ = LZO_BYTE(m_off
>> 6);
97 STORE_RUN ( lzo_bytep op
, const lzo_bytep ii
, lzo_uint t
, lzo_bytep out
)
99 if (t
< 4 && op
> out
)
100 op
[-2] = LZO_BYTE(op
[-2] | t
);
105 lzo_uint tt
= t
- 31;
114 *op
++ = LZO_BYTE(tt
);
116 do *op
++ = *ii
++; while (--t
> 0);
122 /***********************************************************************
123 // this is a public function, but there is no prototype in a header file
124 ************************************************************************/
127 lzo1f_999_compress_callback ( const lzo_bytep in
, lzo_uint in_len
,
128 lzo_bytep out
, lzo_uintp out_len
,
131 lzo_uint max_chain
);
134 lzo1f_999_compress_callback ( const lzo_bytep in
, lzo_uint in_len
,
135 lzo_bytep out
, lzo_uintp out_len
,
143 lzo_uint m_len
, m_off
;
145 LZO_COMPRESS_T
* const c
= &cc
;
146 lzo_swd_p
const swd
= (lzo_swd_p
) wrkmem
;
150 LZO_COMPILE_TIME_ASSERT(LZO1F_999_MEM_COMPRESS
>= SIZEOF_LZO_SWD_T
)
154 c
->in_end
= in
+ in_len
;
156 c
->r1_r
= c
->m2_m
= c
->m3_m
= 0;
159 ii
= c
->ip
; /* point to start of literal run */
161 c
->r1_lit
= c
->r1_m_len
= 0;
163 r
= init_match(c
,swd
,NULL
,0,0);
167 swd
->max_chain
= max_chain
;
169 r
= find_match(c
,swd
,0,0);
174 int lazy_match_min_gain
= -1;
180 assert(c
->ip
- c
->look
>= in
);
182 ii
= c
->ip
- c
->look
;
183 assert(ii
+ lit
== c
->ip
- c
->look
);
184 assert(swd
->b_char
== *(c
->ip
- c
->look
));
186 if ((m_len
< M2_MIN_LEN
) ||
187 (m_len
< M3_MIN_LEN
&& m_off
> M2_MAX_OFFSET
))
193 assert(c
->ip
- c
->look
- m_off
>= in
);
194 assert(c
->ip
- c
->look
- m_off
+ m_len
< c
->ip
);
195 assert(lzo_memcmp(c
->ip
- c
->look
, c
->ip
- c
->look
- m_off
,
199 lazy_match_min_gain
= 1;
201 lazy_match_min_gain
= 3;
203 lazy_match_min_gain
= 3;
205 lazy_match_min_gain
= 1;
208 /* try a lazy match */
209 if (m_len
> 0 && lazy_match_min_gain
>= 0 && c
->look
> m_len
)
211 r
= find_match(c
,swd
,1,0);
212 assert(r
== 0); LZO_UNUSED(r
);
215 if (m_len
<= M2_MAX_LEN
&& m_off
<= M2_MAX_OFFSET
&&
216 c
->m_off
> M2_MAX_OFFSET
)
218 lazy_match_min_gain
+= 1;
220 else if (c
->m_len
<= M2_MAX_LEN
&&
221 c
->m_off
<= M2_MAX_OFFSET
&&
222 m_off
> M2_MAX_OFFSET
)
224 if (lazy_match_min_gain
> 0)
225 lazy_match_min_gain
-= 1;
227 else if (m_len
== M2_MIN_LEN
&& c
->m_len
== M2_MIN_LEN
&&
228 c
->m_off
<= 2 * M2_MAX_OFFSET
&&
229 m_off
> M2_MAX_OFFSET
)
231 if (lazy_match_min_gain
> 0)
232 lazy_match_min_gain
-= 1;
235 if (c
->m_len
>= m_len
+ lazy_match_min_gain
)
241 assert(lzo_memcmp(c
->ip
- c
->look
, c
->ip
- c
->look
- m_off
,
245 assert(ii
+ lit
== c
->ip
- c
->look
);
251 assert(ii
+ lit
+ 1 == c
->ip
- c
->look
);
255 assert(ii
+ lit
+ ahead
== c
->ip
- c
->look
);
262 r
= find_match(c
,swd
,1,0);
263 assert(r
== 0); LZO_UNUSED(r
);
270 op
= STORE_RUN(op
,ii
,lit
,out
);
276 c
->r1_lit
= c
->r1_m_len
= 0;
279 op
= code_match(c
,op
,m_len
,m_off
);
280 r
= find_match(c
,swd
,m_len
,1+ahead
);
281 assert(r
== 0); LZO_UNUSED(r
);
284 c
->codesize
= pd(op
, out
);
288 /* store final run */
290 op
= STORE_RUN(op
,ii
,lit
,out
);
292 #if defined(LZO_EOF_CODE)
293 *op
++ = M3_MARKER
| 1;
298 c
->codesize
= pd(op
, out
);
299 assert(c
->textsize
== in_len
);
301 *out_len
= pd(op
, out
);
303 if (c
->cb
&& c
->cb
->nprogress
)
304 (*c
->cb
->nprogress
)(c
->cb
, c
->textsize
, c
->codesize
, 0);
307 printf("%ld %ld -> %ld: %ld %ld %ld %ld\n",
308 (long) c
->textsize
, (long)in_len
, (long) c
->codesize
,
309 c
->r1_r
, c
->m2_m
, c
->m3_m
, c
->lazy
);
316 /***********************************************************************
318 ************************************************************************/
321 lzo1f_999_compress ( const lzo_bytep in
, lzo_uint in_len
,
322 lzo_bytep out
, lzo_uintp out_len
,
325 return lzo1f_999_compress_callback(in
,in_len
,out
,out_len
,wrkmem
,
326 (lzo_callback_p
) 0, 0);
330 /* vim:set ts=4 sw=4 et: */