Annotation of /trunk/mkinitrd-magellan/busybox/archival/lzo1x_d.c
Parent Directory | Revision Log
Revision 984 -
(hide annotations)
(download)
Sun May 30 11:32:42 2010 UTC (13 years, 11 months ago) by niro
File MIME type: text/plain
File size: 9269 byte(s)
Sun May 30 11:32:42 2010 UTC (13 years, 11 months ago) by niro
File MIME type: text/plain
File size: 9269 byte(s)
-updated to busybox-1.16.1 and enabled blkid/uuid support in default config
1 | niro | 984 | /* 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 */ | ||
33 | int 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 | } |