1/* lzo1b_d.ch -- implementation of the LZO1B decompression algorithm
2
3   This file is part of the LZO real-time data compression library.
4
5   Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
6   Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
7   Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
8   Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
9   Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
10   Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
11   Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
12   Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
13   Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
14   Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
15   Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
16   Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
17   Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
18   All Rights Reserved.
19
20   The LZO library is free software; you can redistribute it and/or
21   modify it under the terms of the GNU General Public License as
22   published by the Free Software Foundation; either version 2 of
23   the License, or (at your option) any later version.
24
25   The LZO library is distributed in the hope that it will be useful,
26   but WITHOUT ANY WARRANTY; without even the implied warranty of
27   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
28   GNU General Public License for more details.
29
30   You should have received a copy of the GNU General Public License
31   along with the LZO library; see the file COPYING.
32   If not, write to the Free Software Foundation, Inc.,
33   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
34
35   Markus F.X.J. Oberhumer
36   <markus@oberhumer.com>
37   http://www.oberhumer.com/opensource/lzo/
38 */
39
40
41#include "lzo1_d.ch"
42
43
44/***********************************************************************
45// decompress a block of data.
46************************************************************************/
47
48LZO_PUBLIC(int)
49DO_DECOMPRESS    ( const lzo_bytep in , lzo_uint  in_len,
50                         lzo_bytep out, lzo_uintp out_len,
51                         lzo_voidp wrkmem )
52{
53    register lzo_bytep op;
54    register const lzo_bytep ip;
55    register lzo_uint t;
56    register const lzo_bytep m_pos;
57
58    const lzo_bytep const ip_end = in + in_len;
59#if defined(HAVE_ANY_OP)
60    lzo_bytep const op_end = out + *out_len;
61#endif
62
63    LZO_UNUSED(wrkmem);
64
65    op = out;
66    ip = in;
67
68    while (TEST_IP && TEST_OP)
69    {
70        t = *ip++;      /* get marker */
71
72        if (t < R0MIN)      /* a literal run */
73        {
74            if (t == 0)             /* a R0 literal run */
75            {
76                NEED_IP(1);
77                t = *ip++;
78                if (t >= R0FAST - R0MIN)            /* a long R0 run */
79                {
80                    t -= R0FAST - R0MIN;
81                    if (t == 0)
82                        t = R0FAST;
83                    else
84                    {
85#if 0
86                        t = 256u << ((unsigned) t);
87#else
88                        /* help the optimizer */
89                        lzo_uint tt = 256;
90                        do tt <<= 1; while (--t > 0);
91                        t = tt;
92#endif
93                    }
94
95                    NEED_IP(t); NEED_OP(t);
96#if 1 && defined(LZO_UNALIGNED_OK_4)
97                    do {
98                        * (lzo_uint32p) (op+0) = * (const lzo_uint32p) (ip+0);
99                        * (lzo_uint32p) (op+4) = * (const lzo_uint32p) (ip+4);
100                        op += 8; ip += 8;
101                        t -= 8;
102                    } while (t > 0);
103#else
104                    MEMCPY8_DS(op,ip,t);
105#endif
106                    continue;
107                }
108                t += R0MIN;                         /* a short R0 run */
109            }
110
111            NEED_IP(t); NEED_OP(t);
112            /* copy literal run */
113#if 1 && defined(LZO_UNALIGNED_OK_4)
114            if (t >= 4)
115            {
116                do {
117                    * (lzo_uint32p) op = * (const lzo_uint32p) ip;
118                    op += 4; ip += 4; t -= 4;
119                } while (t >= 4);
120                if (t > 0) do *op++ = *ip++; while (--t > 0);
121            }
122            else
123#endif
124            {
125#if (M3O_BITS < 7)
126literal1:
127#endif
128                do *op++ = *ip++; while (--t > 0);
129            }
130
131#if (M3O_BITS == 7)
132literal2:
133#endif
134
135            /* after a literal a match must follow */
136            while (TEST_IP && TEST_OP)
137            {
138                t = *ip++;          /* get R1 marker */
139                if (t >= R0MIN)
140                    goto match;
141
142                NEED_IP(2); NEED_OP(M2_MIN_LEN + 1);
143
144            /* R1 match - a M2_MIN_LEN match + 1 byte literal */
145                assert((t & M2O_MASK) == t);
146                m_pos = op - M2_MIN_OFFSET;
147                m_pos -= t | (((lzo_uint) *ip++) << M2O_BITS);
148                assert(m_pos >= out); assert(m_pos < op);
149                TEST_LB(m_pos);
150                COPY_M2;
151                *op++ = *ip++;
152            }
153
154#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
155            break;
156#endif
157        }
158
159match:
160
161        if (t >= M2_MARKER)             /* a M2 match */
162        {
163            /* get match offset */
164            NEED_IP(1);
165            m_pos = op - M2_MIN_OFFSET;
166            m_pos -= (t & M2O_MASK) | (((lzo_uint) *ip++) << M2O_BITS);
167            assert(m_pos >= out); assert(m_pos < op);
168            TEST_LB(m_pos);
169
170            /* get match len */
171            t = (t >> M2O_BITS) - 1;
172            NEED_OP(t + M2_MIN_LEN - 1);
173            COPY_M2X;
174            MEMCPY_DS(op,m_pos,t);
175        }
176        else                            /* a M3 or M4 match */
177        {
178            /* get match len */
179            t &= M3L_MASK;
180            if (t == 0)         /* a M4 match */
181            {
182                NEED_IP(1);
183                while (*ip == 0)
184                {
185                    t += 255;
186                    ip++;
187                    NEED_IP(1);
188                }
189                t += (M4_MIN_LEN - M3_MIN_LEN) + *ip++;
190            }
191
192            /* get match offset */
193            NEED_IP(2);
194            m_pos = op - (M3_MIN_OFFSET - M3_EOF_OFFSET);
195            m_pos -= *ip++ & M3O_MASK;
196            m_pos -= (lzo_uint)(*ip++) << M3O_BITS;
197#if defined(LZO_EOF_CODE)
198            if (m_pos == op)
199                goto eof_found;
200#endif
201
202            /* copy match */
203            assert(m_pos >= out); assert(m_pos < op);
204            TEST_LB(m_pos); NEED_OP(t + M3_MIN_LEN - 1);
205#if defined(LZO_UNALIGNED_OK_4)
206            if (t >= 2 * 4 - (M3_MIN_LEN - 1) && (op - m_pos) >= 4)
207            {
208                * (lzo_uint32p) op = * (const lzo_uint32p) m_pos;
209                op += 4; m_pos += 4; t -= 4 - (M3_MIN_LEN - 1);
210                do {
211                    * (lzo_uint32p) op = * (const lzo_uint32p) m_pos;
212                    op += 4; m_pos += 4; t -= 4;
213                } while (t >= 4);
214                if (t > 0) do *op++ = *m_pos++; while (--t > 0);
215            }
216            else
217#endif
218            {
219            COPY_M3X;
220            MEMCPY_DS(op,m_pos,t);
221            }
222
223
224#if (M3O_BITS < 7)
225            t = ip[-2] >> M3O_BITS;
226            if (t)
227            {
228                NEED_IP(t); NEED_OP(t);
229                goto literal1;
230            }
231#elif (M3O_BITS == 7)
232            /* optimized version */
233            if (ip[-2] & (1 << M3O_BITS))
234            {
235                NEED_IP(1); NEED_OP(1);
236                *op++ = *ip++;
237                goto literal2;
238            }
239#endif
240        }
241    }
242
243
244#if defined(LZO_EOF_CODE)
245#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
246    /* no EOF code was found */
247    *out_len = pd(op, out);
248    return LZO_E_EOF_NOT_FOUND;
249#endif
250
251eof_found:
252    assert(t == 1);
253#endif
254    *out_len = pd(op, out);
255    return (ip == ip_end ? LZO_E_OK :
256           (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
257
258
259#if defined(HAVE_NEED_IP)
260input_overrun:
261    *out_len = pd(op, out);
262    return LZO_E_INPUT_OVERRUN;
263#endif
264
265#if defined(HAVE_NEED_OP)
266output_overrun:
267    *out_len = pd(op, out);
268    return LZO_E_OUTPUT_OVERRUN;
269#endif
270
271#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
272lookbehind_overrun:
273    *out_len = pd(op, out);
274    return LZO_E_LOOKBEHIND_OVERRUN;
275#endif
276}
277
278
279/*
280vi:ts=4:et
281*/
282
283