• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1/* lzo1x_d.ch -- 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-2014 Markus Franz Xaver Johannes Oberhumer
6   All Rights Reserved.
7
8   The LZO library is free software; you can redistribute it and/or
9   modify it under the terms of the GNU General Public License as
10   published by the Free Software Foundation; either version 2 of
11   the License, or (at your option) any later version.
12
13   The LZO library is distributed in the hope that it will be useful,
14   but WITHOUT ANY WARRANTY; without even the implied warranty of
15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16   GNU General Public License for more details.
17
18   You should have received a copy of the GNU General Public License
19   along with the LZO library; see the file COPYING.
20   If not, write to the Free Software Foundation, Inc.,
21   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
22
23   Markus F.X.J. Oberhumer
24   <markus@oberhumer.com>
25   http://www.oberhumer.com/opensource/lzo/
26 */
27
28
29#include "lzo1_d.ch"
30
31
32/***********************************************************************
33// decompress a block of data.
34************************************************************************/
35
36#if defined(DO_DECOMPRESS)
37LZO_PUBLIC(int)
38DO_DECOMPRESS  ( const lzo_bytep in , lzo_uint  in_len,
39                       lzo_bytep out, lzo_uintp out_len,
40                       lzo_voidp wrkmem )
41#endif
42{
43    lzo_bytep op;
44    const lzo_bytep ip;
45    lzo_uint t;
46#if defined(COPY_DICT)
47    lzo_uint m_off;
48    const lzo_bytep dict_end;
49#else
50    const lzo_bytep m_pos;
51#endif
52
53    const lzo_bytep const ip_end = in + in_len;
54#if defined(HAVE_ANY_OP)
55    lzo_bytep const op_end = out + *out_len;
56#endif
57#if defined(LZO1Z)
58    lzo_uint last_m_off = 0;
59#endif
60
61    LZO_UNUSED(wrkmem);
62
63#if defined(COPY_DICT)
64    if (dict)
65    {
66        if (dict_len > M4_MAX_OFFSET)
67        {
68            dict += dict_len - M4_MAX_OFFSET;
69            dict_len = M4_MAX_OFFSET;
70        }
71        dict_end = dict + dict_len;
72    }
73    else
74    {
75        dict_len = 0;
76        dict_end = NULL;
77    }
78#endif /* COPY_DICT */
79
80    *out_len = 0;
81
82    op = out;
83    ip = in;
84
85    NEED_IP(1);
86    if (*ip > 17)
87    {
88        t = *ip++ - 17;
89        if (t < 4)
90            goto match_next;
91        assert(t > 0); NEED_OP(t); NEED_IP(t+3);
92        do *op++ = *ip++; while (--t > 0);
93        goto first_literal_run;
94    }
95
96    for (;;)
97    {
98        NEED_IP(3);
99        t = *ip++;
100        if (t >= 16)
101            goto match;
102        /* a literal run */
103        if (t == 0)
104        {
105            while (*ip == 0)
106            {
107                t += 255;
108                ip++;
109                TEST_IV(t);
110                NEED_IP(1);
111            }
112            t += 15 + *ip++;
113        }
114        /* copy literals */
115        assert(t > 0); NEED_OP(t+3); NEED_IP(t+6);
116#if (LZO_OPT_UNALIGNED64) && (LZO_OPT_UNALIGNED32)
117        t += 3;
118        if (t >= 8) do
119        {
120            UA_COPY8(op,ip);
121            op += 8; ip += 8; t -= 8;
122        } while (t >= 8);
123        if (t >= 4)
124        {
125            UA_COPY4(op,ip);
126            op += 4; ip += 4; t -= 4;
127        }
128        if (t > 0)
129        {
130            *op++ = *ip++;
131            if (t > 1) { *op++ = *ip++; if (t > 2) { *op++ = *ip++; } }
132        }
133#elif (LZO_OPT_UNALIGNED32) || (LZO_ALIGNED_OK_4)
134#if !(LZO_OPT_UNALIGNED32)
135        if (PTR_ALIGNED2_4(op,ip))
136        {
137#endif
138        UA_COPY4(op,ip);
139        op += 4; ip += 4;
140        if (--t > 0)
141        {
142            if (t >= 4)
143            {
144                do {
145                    UA_COPY4(op,ip);
146                    op += 4; ip += 4; t -= 4;
147                } while (t >= 4);
148                if (t > 0) do *op++ = *ip++; while (--t > 0);
149            }
150            else
151                do *op++ = *ip++; while (--t > 0);
152        }
153#if !(LZO_OPT_UNALIGNED32)
154        }
155        else
156#endif
157#endif
158#if !(LZO_OPT_UNALIGNED32)
159        {
160            *op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
161            do *op++ = *ip++; while (--t > 0);
162        }
163#endif
164
165
166first_literal_run:
167
168
169        t = *ip++;
170        if (t >= 16)
171            goto match;
172#if defined(COPY_DICT)
173#if defined(LZO1Z)
174        m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
175        last_m_off = m_off;
176#else
177        m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
178#endif
179        NEED_OP(3);
180        t = 3; COPY_DICT(t,m_off)
181#else /* !COPY_DICT */
182#if defined(LZO1Z)
183        t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
184        m_pos = op - t;
185        last_m_off = t;
186#else
187        m_pos = op - (1 + M2_MAX_OFFSET);
188        m_pos -= t >> 2;
189        m_pos -= *ip++ << 2;
190#endif
191        TEST_LB(m_pos); NEED_OP(3);
192        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos;
193#endif /* COPY_DICT */
194        goto match_done;
195
196
197        /* handle matches */
198        for (;;) {
199match:
200            if (t >= 64)                /* a M2 match */
201            {
202#if defined(COPY_DICT)
203#if defined(LZO1X)
204                m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
205                t = (t >> 5) - 1;
206#elif defined(LZO1Y)
207                m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
208                t = (t >> 4) - 3;
209#elif defined(LZO1Z)
210                m_off = t & 0x1f;
211                if (m_off >= 0x1c)
212                    m_off = last_m_off;
213                else
214                {
215                    m_off = 1 + (m_off << 6) + (*ip++ >> 2);
216                    last_m_off = m_off;
217                }
218                t = (t >> 5) - 1;
219#endif
220#else /* !COPY_DICT */
221#if defined(LZO1X)
222                m_pos = op - 1;
223                m_pos -= (t >> 2) & 7;
224                m_pos -= *ip++ << 3;
225                t = (t >> 5) - 1;
226#elif defined(LZO1Y)
227                m_pos = op - 1;
228                m_pos -= (t >> 2) & 3;
229                m_pos -= *ip++ << 2;
230                t = (t >> 4) - 3;
231#elif defined(LZO1Z)
232                {
233                    lzo_uint off = t & 0x1f;
234                    m_pos = op;
235                    if (off >= 0x1c)
236                    {
237                        assert(last_m_off > 0);
238                        m_pos -= last_m_off;
239                    }
240                    else
241                    {
242                        off = 1 + (off << 6) + (*ip++ >> 2);
243                        m_pos -= off;
244                        last_m_off = off;
245                    }
246                }
247                t = (t >> 5) - 1;
248#endif
249                TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
250                goto copy_match;
251#endif /* COPY_DICT */
252            }
253            else if (t >= 32)           /* a M3 match */
254            {
255                t &= 31;
256                if (t == 0)
257                {
258                    while (*ip == 0)
259                    {
260                        t += 255;
261                        ip++;
262                        TEST_OV(t);
263                        NEED_IP(1);
264                    }
265                    t += 31 + *ip++;
266                    NEED_IP(2);
267                }
268#if defined(COPY_DICT)
269#if defined(LZO1Z)
270                m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
271                last_m_off = m_off;
272#else
273                m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
274#endif
275#else /* !COPY_DICT */
276#if defined(LZO1Z)
277                {
278                    lzo_uint off = 1 + (ip[0] << 6) + (ip[1] >> 2);
279                    m_pos = op - off;
280                    last_m_off = off;
281                }
282#elif (LZO_OPT_UNALIGNED16) && (LZO_ABI_LITTLE_ENDIAN)
283                m_pos = op - 1;
284                m_pos -= UA_GET_LE16(ip) >> 2;
285#else
286                m_pos = op - 1;
287                m_pos -= (ip[0] >> 2) + (ip[1] << 6);
288#endif
289#endif /* COPY_DICT */
290                ip += 2;
291            }
292            else if (t >= 16)           /* a M4 match */
293            {
294#if defined(COPY_DICT)
295                m_off = (t & 8) << 11;
296#else /* !COPY_DICT */
297                m_pos = op;
298                m_pos -= (t & 8) << 11;
299#endif /* COPY_DICT */
300                t &= 7;
301                if (t == 0)
302                {
303                    while (*ip == 0)
304                    {
305                        t += 255;
306                        ip++;
307                        TEST_OV(t);
308                        NEED_IP(1);
309                    }
310                    t += 7 + *ip++;
311                    NEED_IP(2);
312                }
313#if defined(COPY_DICT)
314#if defined(LZO1Z)
315                m_off += (ip[0] << 6) + (ip[1] >> 2);
316#else
317                m_off += (ip[0] >> 2) + (ip[1] << 6);
318#endif
319                ip += 2;
320                if (m_off == 0)
321                    goto eof_found;
322                m_off += 0x4000;
323#if defined(LZO1Z)
324                last_m_off = m_off;
325#endif
326#else /* !COPY_DICT */
327#if defined(LZO1Z)
328                m_pos -= (ip[0] << 6) + (ip[1] >> 2);
329#elif (LZO_OPT_UNALIGNED16) && (LZO_ABI_LITTLE_ENDIAN)
330                m_pos -= UA_GET_LE16(ip) >> 2;
331#else
332                m_pos -= (ip[0] >> 2) + (ip[1] << 6);
333#endif
334                ip += 2;
335                if (m_pos == op)
336                    goto eof_found;
337                m_pos -= 0x4000;
338#if defined(LZO1Z)
339                last_m_off = pd((const lzo_bytep)op, m_pos);
340#endif
341#endif /* COPY_DICT */
342            }
343            else                            /* a M1 match */
344            {
345#if defined(COPY_DICT)
346#if defined(LZO1Z)
347                m_off = 1 + (t << 6) + (*ip++ >> 2);
348                last_m_off = m_off;
349#else
350                m_off = 1 + (t >> 2) + (*ip++ << 2);
351#endif
352                NEED_OP(2);
353                t = 2; COPY_DICT(t,m_off)
354#else /* !COPY_DICT */
355#if defined(LZO1Z)
356                t = 1 + (t << 6) + (*ip++ >> 2);
357                m_pos = op - t;
358                last_m_off = t;
359#else
360                m_pos = op - 1;
361                m_pos -= t >> 2;
362                m_pos -= *ip++ << 2;
363#endif
364                TEST_LB(m_pos); NEED_OP(2);
365                *op++ = *m_pos++; *op++ = *m_pos;
366#endif /* COPY_DICT */
367                goto match_done;
368            }
369
370            /* copy match */
371#if defined(COPY_DICT)
372
373            NEED_OP(t+3-1);
374            t += 3-1; COPY_DICT(t,m_off)
375
376#else /* !COPY_DICT */
377
378            TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
379#if (LZO_OPT_UNALIGNED64) && (LZO_OPT_UNALIGNED32)
380            if (op - m_pos >= 8)
381            {
382                t += (3 - 1);
383                if (t >= 8) do
384                {
385                    UA_COPY8(op,m_pos);
386                    op += 8; m_pos += 8; t -= 8;
387                } while (t >= 8);
388                if (t >= 4)
389                {
390                    UA_COPY4(op,m_pos);
391                    op += 4; m_pos += 4; t -= 4;
392                }
393                if (t > 0)
394                {
395                    *op++ = m_pos[0];
396                    if (t > 1) { *op++ = m_pos[1]; if (t > 2) { *op++ = m_pos[2]; } }
397                }
398            }
399            else
400#elif (LZO_OPT_UNALIGNED32) || (LZO_ALIGNED_OK_4)
401#if !(LZO_OPT_UNALIGNED32)
402            if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos))
403            {
404                assert((op - m_pos) >= 4);  /* both pointers are aligned */
405#else
406            if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4)
407            {
408#endif
409                UA_COPY4(op,m_pos);
410                op += 4; m_pos += 4; t -= 4 - (3 - 1);
411                do {
412                    UA_COPY4(op,m_pos);
413                    op += 4; m_pos += 4; t -= 4;
414                } while (t >= 4);
415                if (t > 0) do *op++ = *m_pos++; while (--t > 0);
416            }
417            else
418#endif
419            {
420copy_match:
421                *op++ = *m_pos++; *op++ = *m_pos++;
422                do *op++ = *m_pos++; while (--t > 0);
423            }
424
425#endif /* COPY_DICT */
426
427match_done:
428#if defined(LZO1Z)
429            t = ip[-1] & 3;
430#else
431            t = ip[-2] & 3;
432#endif
433            if (t == 0)
434                break;
435
436            /* copy literals */
437match_next:
438            assert(t > 0); assert(t < 4); NEED_OP(t); NEED_IP(t+3);
439#if 0
440            do *op++ = *ip++; while (--t > 0);
441#else
442            *op++ = *ip++;
443            if (t > 1) { *op++ = *ip++; if (t > 2) { *op++ = *ip++; } }
444#endif
445            t = *ip++;
446        }
447    }
448
449eof_found:
450    *out_len = pd(op, out);
451    return (ip == ip_end ? LZO_E_OK :
452           (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
453
454
455#if defined(HAVE_NEED_IP)
456input_overrun:
457    *out_len = pd(op, out);
458    return LZO_E_INPUT_OVERRUN;
459#endif
460
461#if defined(HAVE_NEED_OP)
462output_overrun:
463    *out_len = pd(op, out);
464    return LZO_E_OUTPUT_OVERRUN;
465#endif
466
467#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
468lookbehind_overrun:
469    *out_len = pd(op, out);
470    return LZO_E_LOOKBEHIND_OVERRUN;
471#endif
472}
473
474
475/*
476vi:ts=4:et
477*/
478
479