/* lzo1b_d.ch -- implementation of the LZO1B decompression algorithm

   This file is part of the LZO real-time data compression library.

   Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer
   All Rights Reserved.

   The LZO library is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of
   the License, or (at your option) any later version.

   The LZO library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with the LZO library; see the file COPYING.
   If not, write to the Free Software Foundation, Inc.,
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

   Markus F.X.J. Oberhumer
   <markus@oberhumer.com>
   http://www.oberhumer.com/opensource/lzo/
 */


#include "lzo1_d.ch"


/***********************************************************************
// decompress a block of data.
************************************************************************/

LZO_PUBLIC(int)
DO_DECOMPRESS    ( const lzo_bytep in , lzo_uint  in_len,
                         lzo_bytep out, lzo_uintp out_len,
                         lzo_voidp wrkmem )
{
    lzo_bytep op;
    const lzo_bytep ip;
    lzo_uint t;
    const lzo_bytep m_pos;

    const lzo_bytep const ip_end = in + in_len;
#if defined(HAVE_ANY_OP)
    lzo_bytep const op_end = out + *out_len;
#endif

    LZO_UNUSED(wrkmem);

    op = out;
    ip = in;

    while (TEST_IP_AND_TEST_OP)
    {
        t = *ip++;      /* get marker */

        if (t < R0MIN)      /* a literal run */
        {
            if (t == 0)             /* a R0 literal run */
            {
                NEED_IP(1);
                t = *ip++;
                if (t >= R0FAST - R0MIN)            /* a long R0 run */
                {
                    t -= R0FAST - R0MIN;
                    if (t == 0)
                        t = R0FAST;
                    else
                    {
#if 0
                        t = 256u << ((unsigned) t);
#else
                        /* help the optimizer */
                        lzo_uint tt = 256;
                        do tt <<= 1; while (--t > 0);
                        t = tt;
#endif
                    }

                    NEED_IP(t); NEED_OP(t);
#if 1 && (LZO_OPT_UNALIGNED32)
                    do {
                        UA_COPY4(op+0, ip+0);
                        UA_COPY4(op+4, ip+4);
                        op += 8; ip += 8;
                        t -= 8;
                    } while (t > 0);
#else
                    MEMCPY8_DS(op,ip,t);
#endif
                    continue;
                }
                t += R0MIN;                         /* a short R0 run */
            }

            NEED_IP(t); NEED_OP(t);
            /* copy literal run */
#if 1 && (LZO_OPT_UNALIGNED32)
            if (t >= 4)
            {
                do {
                    UA_COPY4(op, ip);
                    op += 4; ip += 4; t -= 4;
                } while (t >= 4);
                if (t > 0) do *op++ = *ip++; while (--t > 0);
            }
            else
#endif
            {
#if (M3O_BITS < 7)
literal1:
#endif
                do *op++ = *ip++; while (--t > 0);
            }

#if (M3O_BITS == 7)
literal2:
#endif

            /* after a literal a match must follow */
            while (TEST_IP_AND_TEST_OP)
            {
                t = *ip++;          /* get R1 marker */
                if (t >= R0MIN)
                    goto match;

                NEED_IP(2); NEED_OP(M2_MIN_LEN + 1);

            /* R1 match - a M2_MIN_LEN match + 1 byte literal */
                assert((t & M2O_MASK) == t);
                m_pos = op - M2_MIN_OFFSET;
                m_pos -= t | (((lzo_uint) *ip++) << M2O_BITS);
                assert(m_pos >= out); assert(m_pos < op);
                TEST_LB(m_pos);
                COPY_M2;
                *op++ = *ip++;
            }

#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
            break;
#endif
        }

match:

        if (t >= M2_MARKER)             /* a M2 match */
        {
            /* get match offset */
            NEED_IP(1);
            m_pos = op - M2_MIN_OFFSET;
            m_pos -= (t & M2O_MASK) | (((lzo_uint) *ip++) << M2O_BITS);
            assert(m_pos >= out); assert(m_pos < op);
            TEST_LB(m_pos);

            /* get match len */
            t = (t >> M2O_BITS) - 1;
            NEED_OP(t + M2_MIN_LEN - 1);
            COPY_M2X;
            MEMCPY_DS(op,m_pos,t);
        }
        else                            /* a M3 or M4 match */
        {
            /* get match len */
            t &= M3L_MASK;
            if (t == 0)         /* a M4 match */
            {
                NEED_IP(1);
                while (*ip == 0)
                {
                    t += 255;
                    ip++;
                    TEST_OV(t);
                    NEED_IP(1);
                }
                t += (M4_MIN_LEN - M3_MIN_LEN) + *ip++;
            }

            /* get match offset */
            NEED_IP(2);
            m_pos = op - (M3_MIN_OFFSET - M3_EOF_OFFSET);
            m_pos -= *ip++ & M3O_MASK;
            m_pos -= (lzo_uint)(*ip++) << M3O_BITS;
#if defined(LZO_EOF_CODE)
            if (m_pos == op)
                goto eof_found;
#endif

            /* copy match */
            assert(m_pos >= out); assert(m_pos < op);
            TEST_LB(m_pos); NEED_OP(t + M3_MIN_LEN - 1);
#if (LZO_OPT_UNALIGNED32)
            if (t >= 2 * 4 - (M3_MIN_LEN - 1) && (op - m_pos) >= 4)
            {
                UA_COPY4(op, m_pos);
                op += 4; m_pos += 4; t -= 4 - (M3_MIN_LEN - 1);
                do {
                    UA_COPY4(op, m_pos);
                    op += 4; m_pos += 4; t -= 4;
                } while (t >= 4);
                if (t > 0) do *op++ = *m_pos++; while (--t > 0);
            }
            else
#endif
            {
            COPY_M3X;
            MEMCPY_DS(op,m_pos,t);
            }


#if (M3O_BITS < 7)
            t = ip[-2] >> M3O_BITS;
            if (t)
            {
                NEED_IP(t); NEED_OP(t);
                goto literal1;
            }
#elif (M3O_BITS == 7)
            /* optimized version */
            if (ip[-2] & (1 << M3O_BITS))
            {
                NEED_IP(1); NEED_OP(1);
                *op++ = *ip++;
                goto literal2;
            }
#endif
        }
    }


#if defined(LZO_EOF_CODE)
#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
    /* no EOF code was found */
    *out_len = pd(op, out);
    return LZO_E_EOF_NOT_FOUND;
#endif

eof_found:
    assert(t == 1);
#endif
    *out_len = pd(op, out);
    return (ip == ip_end ? LZO_E_OK :
           (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));


#if defined(HAVE_NEED_IP)
input_overrun:
    *out_len = pd(op, out);
    return LZO_E_INPUT_OVERRUN;
#endif

#if defined(HAVE_NEED_OP)
output_overrun:
    *out_len = pd(op, out);
    return LZO_E_OUTPUT_OVERRUN;
#endif

#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
lookbehind_overrun:
    *out_len = pd(op, out);
    return LZO_E_LOOKBEHIND_OVERRUN;
#endif
}


/*
vi:ts=4:et
*/