source: MondoRescue/branches/3.2/mindi-busybox/archival/libarchive/lzo1x_d.c@ 3377

Last change on this file since 3377 was 3232, checked in by Bruno Cornec, 12 years ago
  • Update mindi-busybox to 1.21.1
  • Property svn:eol-style set to native
File size: 9.1 KB
Line 
1/* implementation of the LZO1X decompression 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#include "libbb.h"
27#include "liblzo.h"
28
29/***********************************************************************
30// decompress a block of data.
31************************************************************************/
32/* safe decompression with overrun testing */
33int lzo1x_decompress_safe(const uint8_t* in, unsigned in_len,
34 uint8_t* out, unsigned* out_len,
35 void* wrkmem UNUSED_PARAM)
36{
37 register uint8_t* op;
38 register const uint8_t* ip;
39 register unsigned t;
40#if defined(COPY_DICT)
41 unsigned m_off;
42 const uint8_t* dict_end;
43#else
44 register const uint8_t* m_pos = NULL; /* possibly not needed */
45#endif
46 const uint8_t* const ip_end = in + in_len;
47#if defined(HAVE_ANY_OP)
48 uint8_t* const op_end = out + *out_len;
49#endif
50#if defined(LZO1Z)
51 unsigned last_m_off = 0;
52#endif
53
54// LZO_UNUSED(wrkmem);
55
56#if defined(COPY_DICT)
57 if (dict) {
58 if (dict_len > M4_MAX_OFFSET) {
59 dict += dict_len - M4_MAX_OFFSET;
60 dict_len = M4_MAX_OFFSET;
61 }
62 dict_end = dict + dict_len;
63 } else {
64 dict_len = 0;
65 dict_end = NULL;
66 }
67#endif /* COPY_DICT */
68
69 *out_len = 0;
70
71 op = out;
72 ip = in;
73
74 if (*ip > 17) {
75 t = *ip++ - 17;
76 if (t < 4)
77 goto match_next;
78 assert(t > 0); NEED_OP(t); NEED_IP(t+1);
79 do *op++ = *ip++; while (--t > 0);
80 goto first_literal_run;
81 }
82
83 while (TEST_IP && TEST_OP) {
84 t = *ip++;
85 if (t >= 16)
86 goto match;
87 /* a literal run */
88 if (t == 0) {
89 NEED_IP(1);
90 while (*ip == 0) {
91 t += 255;
92 ip++;
93 NEED_IP(1);
94 }
95 t += 15 + *ip++;
96 }
97 /* copy literals */
98 assert(t > 0);
99 NEED_OP(t+3);
100 NEED_IP(t+4);
101#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
102# if !defined(LZO_UNALIGNED_OK_4)
103 if (PTR_ALIGNED2_4(op, ip))
104# endif
105 {
106 COPY4(op, ip);
107 op += 4;
108 ip += 4;
109 if (--t > 0) {
110 if (t >= 4) {
111 do {
112 COPY4(op, ip);
113 op += 4;
114 ip += 4;
115 t -= 4;
116 } while (t >= 4);
117 if (t > 0)
118 do *op++ = *ip++; while (--t > 0);
119 } else {
120 do *op++ = *ip++; while (--t > 0);
121 }
122 }
123 }
124# if !defined(LZO_UNALIGNED_OK_4)
125 else
126# endif
127#endif
128#if !defined(LZO_UNALIGNED_OK_4)
129 {
130 *op++ = *ip++;
131 *op++ = *ip++;
132 *op++ = *ip++;
133 do *op++ = *ip++; while (--t > 0);
134 }
135#endif
136
137 first_literal_run:
138 t = *ip++;
139 if (t >= 16)
140 goto match;
141#if defined(COPY_DICT)
142#if defined(LZO1Z)
143 m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
144 last_m_off = m_off;
145#else
146 m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
147#endif
148 NEED_OP(3);
149 t = 3; COPY_DICT(t,m_off)
150#else /* !COPY_DICT */
151#if defined(LZO1Z)
152 t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
153 m_pos = op - t;
154 last_m_off = t;
155#else
156 m_pos = op - (1 + M2_MAX_OFFSET);
157 m_pos -= t >> 2;
158 m_pos -= *ip++ << 2;
159#endif
160 TEST_LB(m_pos); NEED_OP(3);
161 *op++ = *m_pos++;
162 *op++ = *m_pos++;
163 *op++ = *m_pos;
164#endif /* COPY_DICT */
165 goto match_done;
166
167 /* handle matches */
168 do {
169 match:
170 if (t >= 64) { /* a M2 match */
171#if defined(COPY_DICT)
172#if defined(LZO1X)
173 m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
174 t = (t >> 5) - 1;
175#elif defined(LZO1Y)
176 m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
177 t = (t >> 4) - 3;
178#elif defined(LZO1Z)
179 m_off = t & 0x1f;
180 if (m_off >= 0x1c)
181 m_off = last_m_off;
182 else {
183 m_off = 1 + (m_off << 6) + (*ip++ >> 2);
184 last_m_off = m_off;
185 }
186 t = (t >> 5) - 1;
187#endif
188#else /* !COPY_DICT */
189#if defined(LZO1X)
190 m_pos = op - 1;
191 m_pos -= (t >> 2) & 7;
192 m_pos -= *ip++ << 3;
193 t = (t >> 5) - 1;
194#elif defined(LZO1Y)
195 m_pos = op - 1;
196 m_pos -= (t >> 2) & 3;
197 m_pos -= *ip++ << 2;
198 t = (t >> 4) - 3;
199#elif defined(LZO1Z)
200 {
201 unsigned off = t & 0x1f;
202 m_pos = op;
203 if (off >= 0x1c) {
204 assert(last_m_off > 0);
205 m_pos -= last_m_off;
206 } else {
207 off = 1 + (off << 6) + (*ip++ >> 2);
208 m_pos -= off;
209 last_m_off = off;
210 }
211 }
212 t = (t >> 5) - 1;
213#endif
214 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
215 goto copy_match;
216#endif /* COPY_DICT */
217 }
218 else if (t >= 32) { /* a M3 match */
219 t &= 31;
220 if (t == 0) {
221 NEED_IP(1);
222 while (*ip == 0) {
223 t += 255;
224 ip++;
225 NEED_IP(1);
226 }
227 t += 31 + *ip++;
228 }
229#if defined(COPY_DICT)
230#if defined(LZO1Z)
231 m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
232 last_m_off = m_off;
233#else
234 m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
235#endif
236#else /* !COPY_DICT */
237#if defined(LZO1Z)
238 {
239 unsigned off = 1 + (ip[0] << 6) + (ip[1] >> 2);
240 m_pos = op - off;
241 last_m_off = off;
242 }
243#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
244 m_pos = op - 1;
245 m_pos -= (* (const lzo_ushortp) ip) >> 2;
246#else
247 m_pos = op - 1;
248 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
249#endif
250#endif /* COPY_DICT */
251 ip += 2;
252 }
253 else if (t >= 16) { /* a M4 match */
254#if defined(COPY_DICT)
255 m_off = (t & 8) << 11;
256#else /* !COPY_DICT */
257 m_pos = op;
258 m_pos -= (t & 8) << 11;
259#endif /* COPY_DICT */
260 t &= 7;
261 if (t == 0) {
262 NEED_IP(1);
263 while (*ip == 0) {
264 t += 255;
265 ip++;
266 NEED_IP(1);
267 }
268 t += 7 + *ip++;
269 }
270#if defined(COPY_DICT)
271#if defined(LZO1Z)
272 m_off += (ip[0] << 6) + (ip[1] >> 2);
273#else
274 m_off += (ip[0] >> 2) + (ip[1] << 6);
275#endif
276 ip += 2;
277 if (m_off == 0)
278 goto eof_found;
279 m_off += 0x4000;
280#if defined(LZO1Z)
281 last_m_off = m_off;
282#endif
283#else /* !COPY_DICT */
284#if defined(LZO1Z)
285 m_pos -= (ip[0] << 6) + (ip[1] >> 2);
286#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
287 m_pos -= (* (const lzo_ushortp) ip) >> 2;
288#else
289 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
290#endif
291 ip += 2;
292 if (m_pos == op)
293 goto eof_found;
294 m_pos -= 0x4000;
295#if defined(LZO1Z)
296 last_m_off = pd((const uint8_t*)op, m_pos);
297#endif
298#endif /* COPY_DICT */
299 }
300 else { /* a M1 match */
301#if defined(COPY_DICT)
302#if defined(LZO1Z)
303 m_off = 1 + (t << 6) + (*ip++ >> 2);
304 last_m_off = m_off;
305#else
306 m_off = 1 + (t >> 2) + (*ip++ << 2);
307#endif
308 NEED_OP(2);
309 t = 2; COPY_DICT(t,m_off)
310#else /* !COPY_DICT */
311#if defined(LZO1Z)
312 t = 1 + (t << 6) + (*ip++ >> 2);
313 m_pos = op - t;
314 last_m_off = t;
315#else
316 m_pos = op - 1;
317 m_pos -= t >> 2;
318 m_pos -= *ip++ << 2;
319#endif
320 TEST_LB(m_pos); NEED_OP(2);
321 *op++ = *m_pos++;
322 *op++ = *m_pos;
323#endif /* COPY_DICT */
324 goto match_done;
325 }
326
327 /* copy match */
328#if defined(COPY_DICT)
329
330 NEED_OP(t+3-1);
331 t += 3-1; COPY_DICT(t,m_off)
332
333#else /* !COPY_DICT */
334
335 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
336#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
337# if !defined(LZO_UNALIGNED_OK_4)
338 if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos)) {
339 assert((op - m_pos) >= 4); /* both pointers are aligned */
340# else
341 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
342# endif
343 COPY4(op,m_pos);
344 op += 4; m_pos += 4; t -= 4 - (3 - 1);
345 do {
346 COPY4(op,m_pos);
347 op += 4; m_pos += 4; t -= 4;
348 } while (t >= 4);
349 if (t > 0)
350 do *op++ = *m_pos++; while (--t > 0);
351 }
352 else
353#endif
354 {
355 copy_match:
356 *op++ = *m_pos++; *op++ = *m_pos++;
357 do *op++ = *m_pos++; while (--t > 0);
358 }
359
360#endif /* COPY_DICT */
361
362 match_done:
363#if defined(LZO1Z)
364 t = ip[-1] & 3;
365#else
366 t = ip[-2] & 3;
367#endif
368 if (t == 0)
369 break;
370
371 /* copy literals */
372 match_next:
373 assert(t > 0);
374 assert(t < 4);
375 NEED_OP(t);
376 NEED_IP(t+1);
377#if 0
378 do *op++ = *ip++; while (--t > 0);
379#else
380 *op++ = *ip++;
381 if (t > 1) {
382 *op++ = *ip++;
383 if (t > 2)
384 *op++ = *ip++;
385 }
386#endif
387 t = *ip++;
388 } while (TEST_IP && TEST_OP);
389 }
390
391//#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
392 /* no EOF code was found */
393 *out_len = pd(op, out);
394 return LZO_E_EOF_NOT_FOUND;
395//#endif
396
397 eof_found:
398 assert(t == 1);
399 *out_len = pd(op, out);
400 return (ip == ip_end ? LZO_E_OK :
401 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
402
403//#if defined(HAVE_NEED_IP)
404 input_overrun:
405 *out_len = pd(op, out);
406 return LZO_E_INPUT_OVERRUN;
407//#endif
408
409//#if defined(HAVE_NEED_OP)
410 output_overrun:
411 *out_len = pd(op, out);
412 return LZO_E_OUTPUT_OVERRUN;
413//#endif
414
415//#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
416 lookbehind_overrun:
417 *out_len = pd(op, out);
418 return LZO_E_LOOKBEHIND_OVERRUN;
419//#endif
420}
Note: See TracBrowser for help on using the repository browser.