source: MondoRescue/branches/3.3/mindi-busybox/archival/libarchive/lzo1x_d.c@ 3723

Last change on this file since 3723 was 3621, checked in by Bruno Cornec, 10 years ago

New 3?3 banch for incorporation of latest busybox 1.25. Changing minor version to handle potential incompatibilities.
  • Property svn:eol-style set to native
File size: 9.1 KB
RevLine 
[2725]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
[3232]18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
[2725]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 }
[3621]95 TEST_IV(t);
[2725]96 t += 15 + *ip++;
97 }
98 /* copy literals */
99 assert(t > 0);
100 NEED_OP(t+3);
101 NEED_IP(t+4);
102#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
103# if !defined(LZO_UNALIGNED_OK_4)
104 if (PTR_ALIGNED2_4(op, ip))
105# endif
106 {
107 COPY4(op, ip);
108 op += 4;
109 ip += 4;
110 if (--t > 0) {
111 if (t >= 4) {
112 do {
113 COPY4(op, ip);
114 op += 4;
115 ip += 4;
116 t -= 4;
117 } while (t >= 4);
118 if (t > 0)
119 do *op++ = *ip++; while (--t > 0);
120 } else {
121 do *op++ = *ip++; while (--t > 0);
122 }
123 }
124 }
125# if !defined(LZO_UNALIGNED_OK_4)
126 else
127# endif
128#endif
129#if !defined(LZO_UNALIGNED_OK_4)
130 {
131 *op++ = *ip++;
132 *op++ = *ip++;
133 *op++ = *ip++;
134 do *op++ = *ip++; while (--t > 0);
135 }
136#endif
137
138 first_literal_run:
139 t = *ip++;
140 if (t >= 16)
141 goto match;
142#if defined(COPY_DICT)
143#if defined(LZO1Z)
144 m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
145 last_m_off = m_off;
146#else
147 m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
148#endif
149 NEED_OP(3);
150 t = 3; COPY_DICT(t,m_off)
151#else /* !COPY_DICT */
152#if defined(LZO1Z)
153 t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
154 m_pos = op - t;
155 last_m_off = t;
156#else
157 m_pos = op - (1 + M2_MAX_OFFSET);
158 m_pos -= t >> 2;
159 m_pos -= *ip++ << 2;
160#endif
161 TEST_LB(m_pos); NEED_OP(3);
162 *op++ = *m_pos++;
163 *op++ = *m_pos++;
164 *op++ = *m_pos;
165#endif /* COPY_DICT */
166 goto match_done;
167
168 /* handle matches */
169 do {
170 match:
171 if (t >= 64) { /* a M2 match */
172#if defined(COPY_DICT)
173#if defined(LZO1X)
174 m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
175 t = (t >> 5) - 1;
176#elif defined(LZO1Y)
177 m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
178 t = (t >> 4) - 3;
179#elif defined(LZO1Z)
180 m_off = t & 0x1f;
181 if (m_off >= 0x1c)
182 m_off = last_m_off;
183 else {
184 m_off = 1 + (m_off << 6) + (*ip++ >> 2);
185 last_m_off = m_off;
186 }
187 t = (t >> 5) - 1;
188#endif
189#else /* !COPY_DICT */
190#if defined(LZO1X)
191 m_pos = op - 1;
192 m_pos -= (t >> 2) & 7;
193 m_pos -= *ip++ << 3;
194 t = (t >> 5) - 1;
195#elif defined(LZO1Y)
196 m_pos = op - 1;
197 m_pos -= (t >> 2) & 3;
198 m_pos -= *ip++ << 2;
199 t = (t >> 4) - 3;
200#elif defined(LZO1Z)
201 {
202 unsigned off = t & 0x1f;
203 m_pos = op;
204 if (off >= 0x1c) {
205 assert(last_m_off > 0);
206 m_pos -= last_m_off;
207 } else {
208 off = 1 + (off << 6) + (*ip++ >> 2);
209 m_pos -= off;
210 last_m_off = off;
211 }
212 }
213 t = (t >> 5) - 1;
214#endif
215 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
216 goto copy_match;
217#endif /* COPY_DICT */
218 }
219 else if (t >= 32) { /* a M3 match */
220 t &= 31;
221 if (t == 0) {
222 NEED_IP(1);
223 while (*ip == 0) {
224 t += 255;
225 ip++;
226 NEED_IP(1);
227 }
[3621]228 TEST_IV(t);
[2725]229 t += 31 + *ip++;
230 }
231#if defined(COPY_DICT)
232#if defined(LZO1Z)
233 m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
234 last_m_off = m_off;
235#else
236 m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
237#endif
238#else /* !COPY_DICT */
239#if defined(LZO1Z)
240 {
241 unsigned off = 1 + (ip[0] << 6) + (ip[1] >> 2);
242 m_pos = op - off;
243 last_m_off = off;
244 }
245#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
246 m_pos = op - 1;
247 m_pos -= (* (const lzo_ushortp) ip) >> 2;
248#else
249 m_pos = op - 1;
250 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
251#endif
252#endif /* COPY_DICT */
253 ip += 2;
254 }
255 else if (t >= 16) { /* a M4 match */
256#if defined(COPY_DICT)
257 m_off = (t & 8) << 11;
258#else /* !COPY_DICT */
259 m_pos = op;
260 m_pos -= (t & 8) << 11;
261#endif /* COPY_DICT */
262 t &= 7;
263 if (t == 0) {
264 NEED_IP(1);
265 while (*ip == 0) {
266 t += 255;
267 ip++;
268 NEED_IP(1);
269 }
[3621]270 TEST_IV(t);
[2725]271 t += 7 + *ip++;
272 }
273#if defined(COPY_DICT)
274#if defined(LZO1Z)
275 m_off += (ip[0] << 6) + (ip[1] >> 2);
276#else
277 m_off += (ip[0] >> 2) + (ip[1] << 6);
278#endif
279 ip += 2;
280 if (m_off == 0)
281 goto eof_found;
282 m_off += 0x4000;
283#if defined(LZO1Z)
284 last_m_off = m_off;
285#endif
286#else /* !COPY_DICT */
287#if defined(LZO1Z)
288 m_pos -= (ip[0] << 6) + (ip[1] >> 2);
289#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
290 m_pos -= (* (const lzo_ushortp) ip) >> 2;
291#else
292 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
293#endif
294 ip += 2;
295 if (m_pos == op)
296 goto eof_found;
297 m_pos -= 0x4000;
298#if defined(LZO1Z)
299 last_m_off = pd((const uint8_t*)op, m_pos);
300#endif
301#endif /* COPY_DICT */
302 }
303 else { /* a M1 match */
304#if defined(COPY_DICT)
305#if defined(LZO1Z)
306 m_off = 1 + (t << 6) + (*ip++ >> 2);
307 last_m_off = m_off;
308#else
309 m_off = 1 + (t >> 2) + (*ip++ << 2);
310#endif
311 NEED_OP(2);
312 t = 2; COPY_DICT(t,m_off)
313#else /* !COPY_DICT */
314#if defined(LZO1Z)
315 t = 1 + (t << 6) + (*ip++ >> 2);
316 m_pos = op - t;
317 last_m_off = t;
318#else
319 m_pos = op - 1;
320 m_pos -= t >> 2;
321 m_pos -= *ip++ << 2;
322#endif
323 TEST_LB(m_pos); NEED_OP(2);
324 *op++ = *m_pos++;
325 *op++ = *m_pos;
326#endif /* COPY_DICT */
327 goto match_done;
328 }
329
330 /* copy match */
331#if defined(COPY_DICT)
332
333 NEED_OP(t+3-1);
334 t += 3-1; COPY_DICT(t,m_off)
335
336#else /* !COPY_DICT */
337
338 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
339#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
340# if !defined(LZO_UNALIGNED_OK_4)
341 if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos)) {
342 assert((op - m_pos) >= 4); /* both pointers are aligned */
343# else
344 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
345# endif
346 COPY4(op,m_pos);
347 op += 4; m_pos += 4; t -= 4 - (3 - 1);
348 do {
349 COPY4(op,m_pos);
350 op += 4; m_pos += 4; t -= 4;
351 } while (t >= 4);
352 if (t > 0)
353 do *op++ = *m_pos++; while (--t > 0);
354 }
355 else
356#endif
357 {
358 copy_match:
359 *op++ = *m_pos++; *op++ = *m_pos++;
360 do *op++ = *m_pos++; while (--t > 0);
361 }
362
363#endif /* COPY_DICT */
364
365 match_done:
366#if defined(LZO1Z)
367 t = ip[-1] & 3;
368#else
369 t = ip[-2] & 3;
370#endif
371 if (t == 0)
372 break;
373
374 /* copy literals */
375 match_next:
376 assert(t > 0);
377 assert(t < 4);
378 NEED_OP(t);
379 NEED_IP(t+1);
380#if 0
381 do *op++ = *ip++; while (--t > 0);
382#else
383 *op++ = *ip++;
384 if (t > 1) {
385 *op++ = *ip++;
386 if (t > 2)
387 *op++ = *ip++;
388 }
389#endif
390 t = *ip++;
391 } while (TEST_IP && TEST_OP);
392 }
393
394//#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
395 /* no EOF code was found */
396 *out_len = pd(op, out);
397 return LZO_E_EOF_NOT_FOUND;
398//#endif
399
400 eof_found:
401 assert(t == 1);
402 *out_len = pd(op, out);
403 return (ip == ip_end ? LZO_E_OK :
404 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
405
406//#if defined(HAVE_NEED_IP)
407 input_overrun:
408 *out_len = pd(op, out);
409 return LZO_E_INPUT_OVERRUN;
410//#endif
411
412//#if defined(HAVE_NEED_OP)
413 output_overrun:
414 *out_len = pd(op, out);
415 return LZO_E_OUTPUT_OVERRUN;
416//#endif
417
418//#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
419 lookbehind_overrun:
420 *out_len = pd(op, out);
421 return LZO_E_LOOKBEHIND_OVERRUN;
422//#endif
423}
Note: See TracBrowser for help on using the repository browser.