Contents of /tags/mkinitrd-6_5_1/busybox/archival/lzo1x_d.c
Parent Directory | Revision Log
Revision 1519 -
(show annotations)
(download)
Wed Sep 7 17:51:16 2011 UTC (13 years ago) by niro
File MIME type: text/plain
File size: 9269 byte(s)
Wed Sep 7 17:51:16 2011 UTC (13 years ago) by niro
File MIME type: text/plain
File size: 9269 byte(s)
tagged 'mkinitrd-6_5_1'
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 */ |
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 | } |