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

Last change on this file since 3232 was 3232, checked in by bruno, 5 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.