1 /* lzo1f_1.c -- implementation of the LZO1F-1 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/
30 #include <lzo/lzo1f.h>
33 /***********************************************************************
35 ************************************************************************/
37 #define M2_MAX_OFFSET 0x0800
38 #define M3_MAX_OFFSET 0x3fff
43 #define LZO_HASH LZO_HASH_LZO_INCREMENTAL_A
46 #define D_INDEX1(d,p) d = DM(DMUL(0x21,DX3(p,5,5,6)) >> 5)
47 #define D_INDEX2(d,p) d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)
51 /***********************************************************************
52 // compress a block of data.
53 ************************************************************************/
56 int do_compress ( const lzo_bytep in
, lzo_uint in_len
,
57 lzo_bytep out
, lzo_uintp out_len
,
62 const lzo_bytep
const in_end
= in
+ in_len
;
63 const lzo_bytep
const ip_end
= in
+ in_len
- 9;
65 lzo_dict_p
const dict
= (lzo_dict_p
) wrkmem
;
74 const lzo_bytep m_pos
;
75 LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint
, m_off
, 0);
81 GINDEX(m_pos
,m_off
,dict
,dindex
,in
);
82 if (LZO_CHECK_MPOS_NON_DET(m_pos
,m_off
,in
,ip
,M3_MAX_OFFSET
))
85 if (m_off
<= M2_MAX_OFFSET
|| m_pos
[3] == ip
[3])
89 GINDEX(m_pos
,m_off
,dict
,dindex
,in
);
90 if (LZO_CHECK_MPOS_NON_DET(m_pos
,m_off
,in
,ip
,M3_MAX_OFFSET
))
92 if (m_off
<= M2_MAX_OFFSET
|| m_pos
[3] == ip
[3])
98 #if 0 && (LZO_OPT_UNALIGNED16)
99 if (UA_GET_NE16(m_pos
) != UA_GET_NE16(ip
))
101 if (m_pos
[0] != ip
[0] || m_pos
[1] != ip
[1])
107 if (m_pos
[2] == ip
[2])
111 if (m_off
<= M2_MAX_OFFSET
)
115 if (lit
== 3) /* better compression, but slower */
117 assert(op
- 2 > out
); op
[-2] |= LZO_BYTE(3);
118 *op
++ = *ii
++; *op
++ = *ii
++; *op
++ = *ii
++;
130 UPDATE_I(dict
,0,dindex
,ip
,in
);
138 UPDATE_I(dict
,0,dindex
,ip
,in
);
139 /* store current literal run */
145 if (t
< 4 && op
> out
)
146 op
[-2] = LZO_BYTE(op
[-2] | t
);
151 lzo_uint tt
= t
- 31;
161 *op
++ = LZO_BYTE(tt
);
163 do *op
++ = *ii
++; while (--t
> 0);
170 if (*m_pos
++ != *ip
++ || *m_pos
++ != *ip
++ || *m_pos
++ != *ip
++ ||
171 *m_pos
++ != *ip
++ || *m_pos
++ != *ip
++ || *m_pos
++ != *ip
++)
175 assert(m_len
>= 3); assert(m_len
<= 8);
177 if (m_off
<= M2_MAX_OFFSET
)
180 *op
++ = LZO_BYTE(((m_len
- 2) << 5) | ((m_off
& 7) << 2));
181 *op
++ = LZO_BYTE(m_off
>> 3);
183 else if (m_len
== 3 && m_off
<= 2*M2_MAX_OFFSET
&& lit
> 0)
186 /* m_off -= M2_MAX_OFFSET; */
187 *op
++ = LZO_BYTE(((m_off
& 7) << 2));
188 *op
++ = LZO_BYTE(m_off
>> 3);
192 *op
++ = LZO_BYTE(M3_MARKER
| (m_len
- 2));
193 *op
++ = LZO_BYTE((m_off
& 63) << 2);
194 *op
++ = LZO_BYTE(m_off
>> 6);
202 while (ip
< end
&& *m_pos
== *ip
)
209 *op
++ = LZO_BYTE(M3_MARKER
| (m_len
- 2));
213 *op
++ = M3_MARKER
| 0;
221 *op
++ = LZO_BYTE(m_len
);
223 *op
++ = LZO_BYTE((m_off
& 63) << 2);
224 *op
++ = LZO_BYTE(m_off
>> 6);
233 /* store final literal run */
234 if (pd(in_end
,ii
) > 0)
236 lzo_uint t
= pd(in_end
,ii
);
238 if (t
< 4 && op
> out
)
239 op
[-2] = LZO_BYTE(op
[-2] | t
);
244 lzo_uint tt
= t
- 31;
254 *op
++ = LZO_BYTE(tt
);
260 *out_len
= pd(op
, out
);
265 /***********************************************************************
266 // public entry point
267 ************************************************************************/
270 lzo1f_1_compress ( const lzo_bytep in
, lzo_uint in_len
,
271 lzo_bytep out
, lzo_uintp out_len
,
279 else if (in_len
<= 10)
281 *op
++ = LZO_BYTE(in_len
);
282 do *op
++ = *in
++; while (--in_len
> 0);
283 *out_len
= pd(op
, out
);
286 r
= do_compress(in
,in_len
,out
,out_len
,wrkmem
);
291 op
[0] = M3_MARKER
| 1;
301 /* vim:set ts=4 sw=4 et: */