/* lzo1x_oo.ch -- LZO1X compressed data optimizer

   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/

 */

#define TEST_IP     (ip < ip_end)

#define TEST_OP     (op <= op_end)

#define TEST_IP_AND_TEST_OP (TEST_IP && TEST_OP)

#define NO_LIT      LZO_UINT_MAX

/***********************************************************************

//

************************************************************************/

static void copy2(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off)

{

    assert(off > 0);

    ip[0] = m_pos[0];

    if (off == 1)

        ip[1] = m_pos[0];

    else

        ip[1] = m_pos[1];

}

static void copy3(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off)

{

    assert(off > 0);

    ip[0] = m_pos[0];

    if (off == 1)

    {

        ip[2] = ip[1] = m_pos[0];

    }

    else if (off == 2)

    {

        ip[1] = m_pos[1];

        ip[2] = m_pos[0];

    }

    else

    {

        ip[1] = m_pos[1];

        ip[2] = m_pos[2];

    }

}

/***********************************************************************

// optimize a block of data.

************************************************************************/

LZO_PUBLIC(int)

DO_OPTIMIZE          (       lzo_bytep in , lzo_uint  in_len,

                             lzo_bytep out, lzo_uintp out_len,

                             lzo_voidp wrkmem )

{

    lzo_bytep op;

    lzo_bytep ip;

    lzo_uint t;

    lzo_bytep m_pos;

    lzo_bytep const ip_end = in + in_len;

    lzo_bytep const op_end = out + *out_len;

    lzo_bytep litp = NULL;

    lzo_uint lit = 0;

    lzo_uint next_lit = NO_LIT;

    lzo_uint nl;

    unsigned long o_m1_a = 0, o_m1_b = 0, o_m2 = 0, o_m3_a = 0, o_m3_b = 0;

    LZO_UNUSED(wrkmem);

    *out_len = 0;

    op = out;

    ip = in;

    assert(in_len >= 3);

    if (*ip > 17)

    {

        t = *ip++ - 17;

        if (t < 4)

            goto match_next;

        goto first_literal_run;

    }

    assert(*ip < 16 || (*ip == 17 && in_len == 3));

    while (TEST_IP_AND_TEST_OP)

    {

        t = *ip++;

        if (t >= 16)

            goto match;

        /* a literal run */

        litp = ip - 1;

        if (t == 0)

        {

            t = 15;

            while (*ip == 0)

                t += 255, ip++;

            t += *ip++;

        }

        lit = t + 3;

        /* copy literals */

copy_literal_run:

        *op++ = *ip++; *op++ = *ip++; *op++ = *ip++;

first_literal_run:

        do *op++ = *ip++; while (--t > 0);

        t = *ip++;

        if (t >= 16)

            goto match;

#if defined(LZO1X)

        m_pos = op - 1 - 0x800;

#elif defined(LZO1Y)

        m_pos = op - 1 - 0x400;

#endif

        m_pos -= t >> 2;

        m_pos -= *ip++ << 2;

        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;

        lit = 0;

        goto match_done;

        /* handle matches */

        do {

            if (t < 16)                     /* a M1 match */

            {

                m_pos = op - 1;

                m_pos -= t >> 2;

                m_pos -= *ip++ << 2;

                if (litp == NULL)

                    goto copy_m1;

                /* assert that there was a match just before */

                assert(lit >= 1 && lit <= 3);

                assert(litp == ip - 2 - lit - 2);

                assert((lzo_uint)(*litp & 3) == lit);

                nl = ip[-2] & 3;

                /* test if a match follows */

                if (nl == 0 && lit == 1 && ip[0] >= 16)

                {

                    next_lit = nl;

                    /* adjust length of previous short run */

                    lit += 2;

                    *litp = LZO_BYTE((*litp & ~3) | lit);

                    /* copy over the 2 literals that replace the match */

                    copy2(ip-2,m_pos,pd(op,m_pos));

                    o_m1_a++;

                }

                /* test if a literal run follows */

                else if (nl == 0 && ip[0] < 16 && ip[0] != 0 &&

                         (lit + 2 + ip[0] < 16))

                {

                    t = *ip++;

                    /* remove short run */

                    *litp &= ~3;

                    /* copy over the 2 literals that replace the match */

                    copy2(ip-3+1,m_pos,pd(op,m_pos));

                    /* move literals 1 byte ahead */

                    litp += 2;

                    if (lit > 0)

                        lzo_memmove(litp+1,litp,lit);

                    /* insert new length of long literal run */

                    lit += 2 + t + 3; assert(lit <= 18);

                    *litp = LZO_BYTE(lit - 3);

                    o_m1_b++;

                    *op++ = *m_pos++; *op++ = *m_pos++;

                    goto copy_literal_run;

                }

copy_m1:

                *op++ = *m_pos++; *op++ = *m_pos++;

            }

            else

            {

match:

                if (t >= 64)                /* a M2 match */

                {

                    m_pos = op - 1;

#if defined(LZO1X)

                    m_pos -= (t >> 2) & 7;

                    m_pos -= *ip++ << 3;

                    t = (t >> 5) - 1;

#elif defined(LZO1Y)

                    m_pos -= (t >> 2) & 3;

                    m_pos -= *ip++ << 2;

                    t = (t >> 4) - 3;

#endif

                    if (litp == NULL)

                        goto copy_m;

                    nl = ip[-2] & 3;

                    /* test if in beetween two long literal runs */

                    if (t == 1 && lit > 3 && nl == 0 &&

                        ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))

                    {

                        assert(*litp == lit - 3);

                        t = *ip++;

                        /* copy over the 3 literals that replace the match */

                        copy3(ip-1-2,m_pos,pd(op,m_pos));

                        /* set new length of previous literal run */

                        lit += 3 + t + 3; assert(lit <= 18);

                        *litp = LZO_BYTE(lit - 3);

                        o_m2++;

                        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;

                        goto copy_literal_run;

                    }

                }

                else

                {

                    if (t >= 32)            /* a M3 match */

                    {

                        t &= 31;

                        if (t == 0)

                        {

                            t = 31;

                            while (*ip == 0)

                                t += 255, ip++;

                            t += *ip++;

                        }

                        m_pos = op - 1;

                        m_pos -= *ip++ >> 2;

                        m_pos -= *ip++ << 6;

                    }

                    else                    /* a M4 match */

                    {

                        m_pos = op;

                        m_pos -= (t & 8) << 11;

                        t &= 7;

                        if (t == 0)

                        {

                            t = 7;

                            while (*ip == 0)

                                t += 255, ip++;

                            t += *ip++;

                        }

                        m_pos -= *ip++ >> 2;

                        m_pos -= *ip++ << 6;

                        if (m_pos == op)

                            goto eof_found;

                        m_pos -= 0x4000;

                    }

                    if (litp == NULL)

                        goto copy_m;

                    nl = ip[-2] & 3;

                    /* test if in beetween two matches */

                    if (t == 1 && lit == 0 && nl == 0 && ip[0] >= 16)

                    {

                        assert(litp == ip - 3 - lit - 2);

                        assert((lzo_uint)(*litp & 3) == lit);

                        next_lit = nl;

                        /* make a previous short run */

                        lit += 3;

                        *litp = LZO_BYTE((*litp & ~3) | lit);

                        /* copy over the 3 literals that replace the match */

                        copy3(ip-3,m_pos,pd(op,m_pos));

                        o_m3_a++;

                    }

                    /* test if a literal run follows */

                    else if (t == 1 && lit <= 3 && nl == 0 &&

                             ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))

                    {

                        assert(litp == ip - 3 - lit - 2);

                        assert((lzo_uint)(*litp & 3) == lit);

                        t = *ip++;

                        /* remove short run */

                        *litp &= ~3;

                        /* copy over the 3 literals that replace the match */

                        copy3(ip-4+1,m_pos,pd(op,m_pos));

                        /* move literals 1 byte ahead */

                        litp += 2;

                        if (lit > 0)

                            lzo_memmove(litp+1,litp,lit);

                        /* insert new length of long literal run */

                        lit += 3 + t + 3; assert(lit <= 18);

                        *litp = LZO_BYTE(lit - 3);

                        o_m3_b++;

                        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;

                        goto copy_literal_run;

                    }

                }

copy_m:

                *op++ = *m_pos++; *op++ = *m_pos++;

                do *op++ = *m_pos++; while (--t > 0);

            }

match_done:

            if (next_lit == NO_LIT)

            {

                t = ip[-2] & 3;

                lit = t;

                litp = ip - 2;

            }

            else

                t = next_lit;

            assert(t <= 3);

            next_lit = NO_LIT;

            if (t == 0)

                break;

            /* copy literals */

match_next:

            do *op++ = *ip++; while (--t > 0);

            t = *ip++;

        } while (TEST_IP_AND_TEST_OP);

    }

    /* no EOF code was found */

    *out_len = pd(op, out);

    return LZO_E_EOF_NOT_FOUND;

eof_found:

    assert(t == 1);

#if 0

    printf("optimize: %5lu %5lu   %5lu   %5lu %5lu\n",

           o_m1_a, o_m1_b, o_m2, o_m3_a, o_m3_b);

#endif

    LZO_UNUSED(o_m1_a); LZO_UNUSED(o_m1_b); LZO_UNUSED(o_m2);

    LZO_UNUSED(o_m3_a); LZO_UNUSED(o_m3_b);

    *out_len = pd(op, out);

    return (ip == ip_end ? LZO_E_OK :

           (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));

}

/*

vi:ts=4:et

*/