Blame src/lzo1b_d.ch

Packit Service 5195f2
/* lzo1b_d.ch -- implementation of the LZO1B decompression algorithm
Packit Service 5195f2
Packit Service 5195f2
   This file is part of the LZO real-time data compression library.
Packit Service 5195f2
Packit Service 5195f2
   Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer
Packit Service 5195f2
   All Rights Reserved.
Packit Service 5195f2
Packit Service 5195f2
   The LZO library is free software; you can redistribute it and/or
Packit Service 5195f2
   modify it under the terms of the GNU General Public License as
Packit Service 5195f2
   published by the Free Software Foundation; either version 2 of
Packit Service 5195f2
   the License, or (at your option) any later version.
Packit Service 5195f2
Packit Service 5195f2
   The LZO library is distributed in the hope that it will be useful,
Packit Service 5195f2
   but WITHOUT ANY WARRANTY; without even the implied warranty of
Packit Service 5195f2
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Packit Service 5195f2
   GNU General Public License for more details.
Packit Service 5195f2
Packit Service 5195f2
   You should have received a copy of the GNU General Public License
Packit Service 5195f2
   along with the LZO library; see the file COPYING.
Packit Service 5195f2
   If not, write to the Free Software Foundation, Inc.,
Packit Service 5195f2
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
Packit Service 5195f2
Packit Service 5195f2
   Markus F.X.J. Oberhumer
Packit Service 5195f2
   <markus@oberhumer.com>
Packit Service 5195f2
   http://www.oberhumer.com/opensource/lzo/
Packit Service 5195f2
 */
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
#include "lzo1_d.ch"
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// decompress a block of data.
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
LZO_PUBLIC(int)
Packit Service 5195f2
DO_DECOMPRESS    ( const lzo_bytep in , lzo_uint  in_len,
Packit Service 5195f2
                         lzo_bytep out, lzo_uintp out_len,
Packit Service 5195f2
                         lzo_voidp wrkmem )
Packit Service 5195f2
{
Packit Service 5195f2
    lzo_bytep op;
Packit Service 5195f2
    const lzo_bytep ip;
Packit Service 5195f2
    lzo_uint t;
Packit Service 5195f2
    const lzo_bytep m_pos;
Packit Service 5195f2
Packit Service 5195f2
    const lzo_bytep const ip_end = in + in_len;
Packit Service 5195f2
#if defined(HAVE_ANY_OP)
Packit Service 5195f2
    lzo_bytep const op_end = out + *out_len;
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
    LZO_UNUSED(wrkmem);
Packit Service 5195f2
Packit Service 5195f2
    op = out;
Packit Service 5195f2
    ip = in;
Packit Service 5195f2
Packit Service 5195f2
    while (TEST_IP_AND_TEST_OP)
Packit Service 5195f2
    {
Packit Service 5195f2
        t = *ip++;      /* get marker */
Packit Service 5195f2
Packit Service 5195f2
        if (t < R0MIN)      /* a literal run */
Packit Service 5195f2
        {
Packit Service 5195f2
            if (t == 0)             /* a R0 literal run */
Packit Service 5195f2
            {
Packit Service 5195f2
                NEED_IP(1);
Packit Service 5195f2
                t = *ip++;
Packit Service 5195f2
                if (t >= R0FAST - R0MIN)            /* a long R0 run */
Packit Service 5195f2
                {
Packit Service 5195f2
                    t -= R0FAST - R0MIN;
Packit Service 5195f2
                    if (t == 0)
Packit Service 5195f2
                        t = R0FAST;
Packit Service 5195f2
                    else
Packit Service 5195f2
                    {
Packit Service 5195f2
#if 0
Packit Service 5195f2
                        t = 256u << ((unsigned) t);
Packit Service 5195f2
#else
Packit Service 5195f2
                        /* help the optimizer */
Packit Service 5195f2
                        lzo_uint tt = 256;
Packit Service 5195f2
                        do tt <<= 1; while (--t > 0);
Packit Service 5195f2
                        t = tt;
Packit Service 5195f2
#endif
Packit Service 5195f2
                    }
Packit Service 5195f2
Packit Service 5195f2
                    NEED_IP(t); NEED_OP(t);
Packit Service 5195f2
#if 1 && (LZO_OPT_UNALIGNED32)
Packit Service 5195f2
                    do {
Packit Service 5195f2
                        UA_COPY4(op+0, ip+0);
Packit Service 5195f2
                        UA_COPY4(op+4, ip+4);
Packit Service 5195f2
                        op += 8; ip += 8;
Packit Service 5195f2
                        t -= 8;
Packit Service 5195f2
                    } while (t > 0);
Packit Service 5195f2
#else
Packit Service 5195f2
                    MEMCPY8_DS(op,ip,t);
Packit Service 5195f2
#endif
Packit Service 5195f2
                    continue;
Packit Service 5195f2
                }
Packit Service 5195f2
                t += R0MIN;                         /* a short R0 run */
Packit Service 5195f2
            }
Packit Service 5195f2
Packit Service 5195f2
            NEED_IP(t); NEED_OP(t);
Packit Service 5195f2
            /* copy literal run */
Packit Service 5195f2
#if 1 && (LZO_OPT_UNALIGNED32)
Packit Service 5195f2
            if (t >= 4)
Packit Service 5195f2
            {
Packit Service 5195f2
                do {
Packit Service 5195f2
                    UA_COPY4(op, ip);
Packit Service 5195f2
                    op += 4; ip += 4; t -= 4;
Packit Service 5195f2
                } while (t >= 4);
Packit Service 5195f2
                if (t > 0) do *op++ = *ip++; while (--t > 0);
Packit Service 5195f2
            }
Packit Service 5195f2
            else
Packit Service 5195f2
#endif
Packit Service 5195f2
            {
Packit Service 5195f2
#if (M3O_BITS < 7)
Packit Service 5195f2
literal1:
Packit Service 5195f2
#endif
Packit Service 5195f2
                do *op++ = *ip++; while (--t > 0);
Packit Service 5195f2
            }
Packit Service 5195f2
Packit Service 5195f2
#if (M3O_BITS == 7)
Packit Service 5195f2
literal2:
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
            /* after a literal a match must follow */
Packit Service 5195f2
            while (TEST_IP_AND_TEST_OP)
Packit Service 5195f2
            {
Packit Service 5195f2
                t = *ip++;          /* get R1 marker */
Packit Service 5195f2
                if (t >= R0MIN)
Packit Service 5195f2
                    goto match;
Packit Service 5195f2
Packit Service 5195f2
                NEED_IP(2); NEED_OP(M2_MIN_LEN + 1);
Packit Service 5195f2
Packit Service 5195f2
            /* R1 match - a M2_MIN_LEN match + 1 byte literal */
Packit Service 5195f2
                assert((t & M2O_MASK) == t);
Packit Service 5195f2
                m_pos = op - M2_MIN_OFFSET;
Packit Service 5195f2
                m_pos -= t | (((lzo_uint) *ip++) << M2O_BITS);
Packit Service 5195f2
                assert(m_pos >= out); assert(m_pos < op);
Packit Service 5195f2
                TEST_LB(m_pos);
Packit Service 5195f2
                COPY_M2;
Packit Service 5195f2
                *op++ = *ip++;
Packit Service 5195f2
            }
Packit Service 5195f2
Packit Service 5195f2
#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
Packit Service 5195f2
            break;
Packit Service 5195f2
#endif
Packit Service 5195f2
        }
Packit Service 5195f2
Packit Service 5195f2
match:
Packit Service 5195f2
Packit Service 5195f2
        if (t >= M2_MARKER)             /* a M2 match */
Packit Service 5195f2
        {
Packit Service 5195f2
            /* get match offset */
Packit Service 5195f2
            NEED_IP(1);
Packit Service 5195f2
            m_pos = op - M2_MIN_OFFSET;
Packit Service 5195f2
            m_pos -= (t & M2O_MASK) | (((lzo_uint) *ip++) << M2O_BITS);
Packit Service 5195f2
            assert(m_pos >= out); assert(m_pos < op);
Packit Service 5195f2
            TEST_LB(m_pos);
Packit Service 5195f2
Packit Service 5195f2
            /* get match len */
Packit Service 5195f2
            t = (t >> M2O_BITS) - 1;
Packit Service 5195f2
            NEED_OP(t + M2_MIN_LEN - 1);
Packit Service 5195f2
            COPY_M2X;
Packit Service 5195f2
            MEMCPY_DS(op,m_pos,t);
Packit Service 5195f2
        }
Packit Service 5195f2
        else                            /* a M3 or M4 match */
Packit Service 5195f2
        {
Packit Service 5195f2
            /* get match len */
Packit Service 5195f2
            t &= M3L_MASK;
Packit Service 5195f2
            if (t == 0)         /* a M4 match */
Packit Service 5195f2
            {
Packit Service 5195f2
                NEED_IP(1);
Packit Service 5195f2
                while (*ip == 0)
Packit Service 5195f2
                {
Packit Service 5195f2
                    t += 255;
Packit Service 5195f2
                    ip++;
Packit Service 5195f2
                    TEST_OV(t);
Packit Service 5195f2
                    NEED_IP(1);
Packit Service 5195f2
                }
Packit Service 5195f2
                t += (M4_MIN_LEN - M3_MIN_LEN) + *ip++;
Packit Service 5195f2
            }
Packit Service 5195f2
Packit Service 5195f2
            /* get match offset */
Packit Service 5195f2
            NEED_IP(2);
Packit Service 5195f2
            m_pos = op - (M3_MIN_OFFSET - M3_EOF_OFFSET);
Packit Service 5195f2
            m_pos -= *ip++ & M3O_MASK;
Packit Service 5195f2
            m_pos -= (lzo_uint)(*ip++) << M3O_BITS;
Packit Service 5195f2
#if defined(LZO_EOF_CODE)
Packit Service 5195f2
            if (m_pos == op)
Packit Service 5195f2
                goto eof_found;
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
            /* copy match */
Packit Service 5195f2
            assert(m_pos >= out); assert(m_pos < op);
Packit Service 5195f2
            TEST_LB(m_pos); NEED_OP(t + M3_MIN_LEN - 1);
Packit Service 5195f2
#if (LZO_OPT_UNALIGNED32)
Packit Service 5195f2
            if (t >= 2 * 4 - (M3_MIN_LEN - 1) && (op - m_pos) >= 4)
Packit Service 5195f2
            {
Packit Service 5195f2
                UA_COPY4(op, m_pos);
Packit Service 5195f2
                op += 4; m_pos += 4; t -= 4 - (M3_MIN_LEN - 1);
Packit Service 5195f2
                do {
Packit Service 5195f2
                    UA_COPY4(op, m_pos);
Packit Service 5195f2
                    op += 4; m_pos += 4; t -= 4;
Packit Service 5195f2
                } while (t >= 4);
Packit Service 5195f2
                if (t > 0) do *op++ = *m_pos++; while (--t > 0);
Packit Service 5195f2
            }
Packit Service 5195f2
            else
Packit Service 5195f2
#endif
Packit Service 5195f2
            {
Packit Service 5195f2
            COPY_M3X;
Packit Service 5195f2
            MEMCPY_DS(op,m_pos,t);
Packit Service 5195f2
            }
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
#if (M3O_BITS < 7)
Packit Service 5195f2
            t = ip[-2] >> M3O_BITS;
Packit Service 5195f2
            if (t)
Packit Service 5195f2
            {
Packit Service 5195f2
                NEED_IP(t); NEED_OP(t);
Packit Service 5195f2
                goto literal1;
Packit Service 5195f2
            }
Packit Service 5195f2
#elif (M3O_BITS == 7)
Packit Service 5195f2
            /* optimized version */
Packit Service 5195f2
            if (ip[-2] & (1 << M3O_BITS))
Packit Service 5195f2
            {
Packit Service 5195f2
                NEED_IP(1); NEED_OP(1);
Packit Service 5195f2
                *op++ = *ip++;
Packit Service 5195f2
                goto literal2;
Packit Service 5195f2
            }
Packit Service 5195f2
#endif
Packit Service 5195f2
        }
Packit Service 5195f2
    }
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
#if defined(LZO_EOF_CODE)
Packit Service 5195f2
#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
Packit Service 5195f2
    /* no EOF code was found */
Packit Service 5195f2
    *out_len = pd(op, out);
Packit Service 5195f2
    return LZO_E_EOF_NOT_FOUND;
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
eof_found:
Packit Service 5195f2
    assert(t == 1);
Packit Service 5195f2
#endif
Packit Service 5195f2
    *out_len = pd(op, out);
Packit Service 5195f2
    return (ip == ip_end ? LZO_E_OK :
Packit Service 5195f2
           (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
#if defined(HAVE_NEED_IP)
Packit Service 5195f2
input_overrun:
Packit Service 5195f2
    *out_len = pd(op, out);
Packit Service 5195f2
    return LZO_E_INPUT_OVERRUN;
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
#if defined(HAVE_NEED_OP)
Packit Service 5195f2
output_overrun:
Packit Service 5195f2
    *out_len = pd(op, out);
Packit Service 5195f2
    return LZO_E_OUTPUT_OVERRUN;
Packit Service 5195f2
#endif
Packit Service 5195f2
Packit Service 5195f2
#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
Packit Service 5195f2
lookbehind_overrun:
Packit Service 5195f2
    *out_len = pd(op, out);
Packit Service 5195f2
    return LZO_E_LOOKBEHIND_OVERRUN;
Packit Service 5195f2
#endif
Packit Service 5195f2
}
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/*
Packit Service 5195f2
vi:ts=4:et
Packit Service 5195f2
*/
Packit Service 5195f2