1 | /* implementation of the LZO1[XY]-1 compression algorithm
|
---|
2 |
|
---|
3 | This file is part of the LZO real-time data compression library.
|
---|
4 |
|
---|
5 | Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer
|
---|
6 | All Rights Reserved.
|
---|
7 |
|
---|
8 | Markus F.X.J. Oberhumer <markus@oberhumer.com>
|
---|
9 | http://www.oberhumer.com/opensource/lzo/
|
---|
10 |
|
---|
11 | The LZO library is free software; you can redistribute it and/or
|
---|
12 | modify it under the terms of the GNU General Public License as
|
---|
13 | published by the Free Software Foundation; either version 2 of
|
---|
14 | the License, or (at your option) any later version.
|
---|
15 |
|
---|
16 | The LZO library is distributed in the hope that it will be useful,
|
---|
17 | but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
19 | GNU General Public License for more details.
|
---|
20 |
|
---|
21 | You should have received a copy of the GNU General Public License
|
---|
22 | along with the LZO library; see the file COPYING.
|
---|
23 | If not, write to the Free Software Foundation, Inc.,
|
---|
24 | 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
|
---|
25 | */
|
---|
26 |
|
---|
27 | /***********************************************************************
|
---|
28 | // compress a block of data.
|
---|
29 | ************************************************************************/
|
---|
30 | static NOINLINE unsigned
|
---|
31 | do_compress(const uint8_t* in, unsigned in_len,
|
---|
32 | uint8_t* out, unsigned* out_len,
|
---|
33 | void* wrkmem)
|
---|
34 | {
|
---|
35 | register const uint8_t* ip;
|
---|
36 | uint8_t* op;
|
---|
37 | const uint8_t* const in_end = in + in_len;
|
---|
38 | const uint8_t* const ip_end = in + in_len - M2_MAX_LEN - 5;
|
---|
39 | const uint8_t* ii;
|
---|
40 | const void* *const dict = (const void**) wrkmem;
|
---|
41 |
|
---|
42 | op = out;
|
---|
43 | ip = in;
|
---|
44 | ii = ip;
|
---|
45 |
|
---|
46 | ip += 4;
|
---|
47 | for (;;) {
|
---|
48 | register const uint8_t* m_pos;
|
---|
49 | unsigned m_off;
|
---|
50 | unsigned m_len;
|
---|
51 | unsigned dindex;
|
---|
52 |
|
---|
53 | D_INDEX1(dindex,ip);
|
---|
54 | GINDEX(m_pos,m_off,dict,dindex,in);
|
---|
55 | if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
|
---|
56 | goto literal;
|
---|
57 | #if 1
|
---|
58 | if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
|
---|
59 | goto try_match;
|
---|
60 | D_INDEX2(dindex,ip);
|
---|
61 | #endif
|
---|
62 | GINDEX(m_pos,m_off,dict,dindex,in);
|
---|
63 | if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
|
---|
64 | goto literal;
|
---|
65 | if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
|
---|
66 | goto try_match;
|
---|
67 | goto literal;
|
---|
68 |
|
---|
69 | try_match:
|
---|
70 | #if 1 && defined(LZO_UNALIGNED_OK_2)
|
---|
71 | if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip)
|
---|
72 | #else
|
---|
73 | if (m_pos[0] != ip[0] || m_pos[1] != ip[1])
|
---|
74 | #endif
|
---|
75 | {
|
---|
76 | } else {
|
---|
77 | if (m_pos[2] == ip[2]) {
|
---|
78 | #if 0
|
---|
79 | if (m_off <= M2_MAX_OFFSET)
|
---|
80 | goto match;
|
---|
81 | if (lit <= 3)
|
---|
82 | goto match;
|
---|
83 | if (lit == 3) { /* better compression, but slower */
|
---|
84 | assert(op - 2 > out); op[-2] |= (uint8_t)(3);
|
---|
85 | *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
|
---|
86 | goto code_match;
|
---|
87 | }
|
---|
88 | if (m_pos[3] == ip[3])
|
---|
89 | #endif
|
---|
90 | goto match;
|
---|
91 | }
|
---|
92 | else {
|
---|
93 | /* still need a better way for finding M1 matches */
|
---|
94 | #if 0
|
---|
95 | /* a M1 match */
|
---|
96 | #if 0
|
---|
97 | if (m_off <= M1_MAX_OFFSET && lit > 0 && lit <= 3)
|
---|
98 | #else
|
---|
99 | if (m_off <= M1_MAX_OFFSET && lit == 3)
|
---|
100 | #endif
|
---|
101 | {
|
---|
102 | register unsigned t;
|
---|
103 |
|
---|
104 | t = lit;
|
---|
105 | assert(op - 2 > out); op[-2] |= (uint8_t)(t);
|
---|
106 | do *op++ = *ii++; while (--t > 0);
|
---|
107 | assert(ii == ip);
|
---|
108 | m_off -= 1;
|
---|
109 | *op++ = (uint8_t)(M1_MARKER | ((m_off & 3) << 2));
|
---|
110 | *op++ = (uint8_t)(m_off >> 2);
|
---|
111 | ip += 2;
|
---|
112 | goto match_done;
|
---|
113 | }
|
---|
114 | #endif
|
---|
115 | }
|
---|
116 | }
|
---|
117 |
|
---|
118 | /* a literal */
|
---|
119 | literal:
|
---|
120 | UPDATE_I(dict, 0, dindex, ip, in);
|
---|
121 | ++ip;
|
---|
122 | if (ip >= ip_end)
|
---|
123 | break;
|
---|
124 | continue;
|
---|
125 |
|
---|
126 | /* a match */
|
---|
127 | match:
|
---|
128 | UPDATE_I(dict, 0, dindex, ip, in);
|
---|
129 | /* store current literal run */
|
---|
130 | if (pd(ip, ii) > 0) {
|
---|
131 | register unsigned t = pd(ip, ii);
|
---|
132 |
|
---|
133 | if (t <= 3) {
|
---|
134 | assert(op - 2 > out);
|
---|
135 | op[-2] |= (uint8_t)(t);
|
---|
136 | }
|
---|
137 | else if (t <= 18)
|
---|
138 | *op++ = (uint8_t)(t - 3);
|
---|
139 | else {
|
---|
140 | register unsigned tt = t - 18;
|
---|
141 |
|
---|
142 | *op++ = 0;
|
---|
143 | while (tt > 255) {
|
---|
144 | tt -= 255;
|
---|
145 | *op++ = 0;
|
---|
146 | }
|
---|
147 | assert(tt > 0);
|
---|
148 | *op++ = (uint8_t)(tt);
|
---|
149 | }
|
---|
150 | do *op++ = *ii++; while (--t > 0);
|
---|
151 | }
|
---|
152 |
|
---|
153 | /* code the match */
|
---|
154 | assert(ii == ip);
|
---|
155 | ip += 3;
|
---|
156 | if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++
|
---|
157 | || m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++
|
---|
158 | #ifdef LZO1Y
|
---|
159 | || m_pos[ 9] != *ip++ || m_pos[10] != *ip++ || m_pos[11] != *ip++
|
---|
160 | || m_pos[12] != *ip++ || m_pos[13] != *ip++ || m_pos[14] != *ip++
|
---|
161 | #endif
|
---|
162 | ) {
|
---|
163 | --ip;
|
---|
164 | m_len = pd(ip, ii);
|
---|
165 | assert(m_len >= 3);
|
---|
166 | assert(m_len <= M2_MAX_LEN);
|
---|
167 |
|
---|
168 | if (m_off <= M2_MAX_OFFSET) {
|
---|
169 | m_off -= 1;
|
---|
170 | #if defined(LZO1X)
|
---|
171 | *op++ = (uint8_t)(((m_len - 1) << 5) | ((m_off & 7) << 2));
|
---|
172 | *op++ = (uint8_t)(m_off >> 3);
|
---|
173 | #elif defined(LZO1Y)
|
---|
174 | *op++ = (uint8_t)(((m_len + 1) << 4) | ((m_off & 3) << 2));
|
---|
175 | *op++ = (uint8_t)(m_off >> 2);
|
---|
176 | #endif
|
---|
177 | }
|
---|
178 | else if (m_off <= M3_MAX_OFFSET) {
|
---|
179 | m_off -= 1;
|
---|
180 | *op++ = (uint8_t)(M3_MARKER | (m_len - 2));
|
---|
181 | goto m3_m4_offset;
|
---|
182 | } else {
|
---|
183 | #if defined(LZO1X)
|
---|
184 | m_off -= 0x4000;
|
---|
185 | assert(m_off > 0);
|
---|
186 | assert(m_off <= 0x7fff);
|
---|
187 | *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2));
|
---|
188 | goto m3_m4_offset;
|
---|
189 | #elif defined(LZO1Y)
|
---|
190 | goto m4_match;
|
---|
191 | #endif
|
---|
192 | }
|
---|
193 | }
|
---|
194 | else {
|
---|
195 | {
|
---|
196 | const uint8_t* end = in_end;
|
---|
197 | const uint8_t* m = m_pos + M2_MAX_LEN + 1;
|
---|
198 | while (ip < end && *m == *ip)
|
---|
199 | m++, ip++;
|
---|
200 | m_len = pd(ip, ii);
|
---|
201 | }
|
---|
202 | assert(m_len > M2_MAX_LEN);
|
---|
203 |
|
---|
204 | if (m_off <= M3_MAX_OFFSET) {
|
---|
205 | m_off -= 1;
|
---|
206 | if (m_len <= 33)
|
---|
207 | *op++ = (uint8_t)(M3_MARKER | (m_len - 2));
|
---|
208 | else {
|
---|
209 | m_len -= 33;
|
---|
210 | *op++ = M3_MARKER | 0;
|
---|
211 | goto m3_m4_len;
|
---|
212 | }
|
---|
213 | } else {
|
---|
214 | #if defined(LZO1Y)
|
---|
215 | m4_match:
|
---|
216 | #endif
|
---|
217 | m_off -= 0x4000;
|
---|
218 | assert(m_off > 0);
|
---|
219 | assert(m_off <= 0x7fff);
|
---|
220 | if (m_len <= M4_MAX_LEN)
|
---|
221 | *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2));
|
---|
222 | else {
|
---|
223 | m_len -= M4_MAX_LEN;
|
---|
224 | *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11));
|
---|
225 | m3_m4_len:
|
---|
226 | while (m_len > 255) {
|
---|
227 | m_len -= 255;
|
---|
228 | *op++ = 0;
|
---|
229 | }
|
---|
230 | assert(m_len > 0);
|
---|
231 | *op++ = (uint8_t)(m_len);
|
---|
232 | }
|
---|
233 | }
|
---|
234 | m3_m4_offset:
|
---|
235 | *op++ = (uint8_t)((m_off & 63) << 2);
|
---|
236 | *op++ = (uint8_t)(m_off >> 6);
|
---|
237 | }
|
---|
238 | #if 0
|
---|
239 | match_done:
|
---|
240 | #endif
|
---|
241 | ii = ip;
|
---|
242 | if (ip >= ip_end)
|
---|
243 | break;
|
---|
244 | }
|
---|
245 |
|
---|
246 | *out_len = pd(op, out);
|
---|
247 | return pd(in_end, ii);
|
---|
248 | }
|
---|
249 |
|
---|
250 | /***********************************************************************
|
---|
251 | // public entry point
|
---|
252 | ************************************************************************/
|
---|
253 | int DO_COMPRESS(const uint8_t* in, unsigned in_len,
|
---|
254 | uint8_t* out, unsigned* out_len,
|
---|
255 | void* wrkmem)
|
---|
256 | {
|
---|
257 | uint8_t* op = out;
|
---|
258 | unsigned t;
|
---|
259 |
|
---|
260 | if (in_len <= M2_MAX_LEN + 5)
|
---|
261 | t = in_len;
|
---|
262 | else {
|
---|
263 | t = do_compress(in,in_len,op,out_len,wrkmem);
|
---|
264 | op += *out_len;
|
---|
265 | }
|
---|
266 |
|
---|
267 | if (t > 0) {
|
---|
268 | const uint8_t* ii = in + in_len - t;
|
---|
269 |
|
---|
270 | if (op == out && t <= 238)
|
---|
271 | *op++ = (uint8_t)(17 + t);
|
---|
272 | else if (t <= 3)
|
---|
273 | op[-2] |= (uint8_t)(t);
|
---|
274 | else if (t <= 18)
|
---|
275 | *op++ = (uint8_t)(t - 3);
|
---|
276 | else {
|
---|
277 | unsigned tt = t - 18;
|
---|
278 |
|
---|
279 | *op++ = 0;
|
---|
280 | while (tt > 255) {
|
---|
281 | tt -= 255;
|
---|
282 | *op++ = 0;
|
---|
283 | }
|
---|
284 | assert(tt > 0);
|
---|
285 | *op++ = (uint8_t)(tt);
|
---|
286 | }
|
---|
287 | do *op++ = *ii++; while (--t > 0);
|
---|
288 | }
|
---|
289 |
|
---|
290 | *op++ = M4_MARKER | 1;
|
---|
291 | *op++ = 0;
|
---|
292 | *op++ = 0;
|
---|
293 |
|
---|
294 | *out_len = pd(op, out);
|
---|
295 | return 0; /*LZO_E_OK*/
|
---|
296 | }
|
---|