/* lzo1x_c.ch -- implementation of the LZO1[XY]-1 compression 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/

 */

#if 1 && defined(DO_COMPRESS) && !defined(do_compress)

   /* choose a unique name to better help PGO optimizations */

#  define do_compress       LZO_PP_ECONCAT2(DO_COMPRESS,_core)

#endif

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

// compress a block of data.

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

static __lzo_noinline lzo_uint

do_compress ( const lzo_bytep in , lzo_uint  in_len,

                    lzo_bytep out, lzo_uintp out_len,

                    lzo_uint  ti,  lzo_voidp wrkmem)

{

    const lzo_bytep ip;

    lzo_bytep op;

    const lzo_bytep const in_end = in + in_len;

    const lzo_bytep const ip_end = in + in_len - 20;

    const lzo_bytep ii;

    lzo_dict_p const dict = (lzo_dict_p) wrkmem;

    op = out;

    ip = in;

    ii = ip;

    ip += ti < 4 ? 4 - ti : 0;

    for (;;)

    {

        const lzo_bytep m_pos;

#if !(LZO_DETERMINISTIC)

        LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, m_off, 0);

        lzo_uint m_len;

        lzo_uint dindex;

next:

        if __lzo_unlikely(ip >= ip_end)

            break;

        DINDEX1(dindex,ip);

        GINDEX(m_pos,m_off,dict,dindex,in);

        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))

            goto literal;

#if 1

        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])

            goto try_match;

        DINDEX2(dindex,ip);

#endif

        GINDEX(m_pos,m_off,dict,dindex,in);

        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))

            goto literal;

        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])

            goto try_match;

        goto literal;

try_match:

#if (LZO_OPT_UNALIGNED32)

        if (UA_GET_NE32(m_pos) != UA_GET_NE32(ip))

#else

        if (m_pos[0] != ip[0] || m_pos[1] != ip[1] || m_pos[2] != ip[2] || m_pos[3] != ip[3])

#endif

        {

            /* a literal */

literal:

            UPDATE_I(dict,0,dindex,ip,in);

            ip += 1 + ((ip - ii) >> 5);

            continue;

        }

/*match:*/

        UPDATE_I(dict,0,dindex,ip,in);

#else

        lzo_uint m_off;

        lzo_uint m_len;

        {

        lzo_uint32_t dv;

        lzo_uint dindex;

literal:

        ip += 1 + ((ip - ii) >> 5);

next:

        if __lzo_unlikely(ip >= ip_end)

            break;

        dv = UA_GET_LE32(ip);

        dindex = DINDEX(dv,ip);

        GINDEX(m_off,m_pos,in+dict,dindex,in);

        UPDATE_I(dict,0,dindex,ip,in);

        if __lzo_unlikely(dv != UA_GET_LE32(m_pos))

            goto literal;

        }

#endif

    /* a match */

        ii -= ti; ti = 0;

        {

        lzo_uint t = pd(ip,ii);

        if (t != 0)

        {

            if (t <= 3)

            {

                op[-2] = LZO_BYTE(op[-2] | t);

#if (LZO_OPT_UNALIGNED32)

                UA_COPY4(op, ii);

                op += t;

#else

                { do *op++ = *ii++; while (--t > 0); }

#endif

            }

#if (LZO_OPT_UNALIGNED32) || (LZO_OPT_UNALIGNED64)

            else if (t <= 16)

            {

                *op++ = LZO_BYTE(t - 3);

                UA_COPY8(op, ii);

                UA_COPY8(op+8, ii+8);

                op += t;

            }

#endif

            else

            {

                if (t <= 18)

                    *op++ = LZO_BYTE(t - 3);

                else

                {

                    lzo_uint tt = t - 18;

                    *op++ = 0;

                    while __lzo_unlikely(tt > 255)

                    {

                        tt -= 255;

                        UA_SET1(op, 0);

                        op++;

                    }

                    assert(tt > 0);

                    *op++ = LZO_BYTE(tt);

                }

#if (LZO_OPT_UNALIGNED32) || (LZO_OPT_UNALIGNED64)

                do {

                    UA_COPY8(op, ii);

                    UA_COPY8(op+8, ii+8);

                    op += 16; ii += 16; t -= 16;

                } while (t >= 16); if (t > 0)

#endif

                { do *op++ = *ii++; while (--t > 0); }

            }

        }

        }

        m_len = 4;

        {

#if (LZO_OPT_UNALIGNED64)

        lzo_uint64_t v;

        v = UA_GET_NE64(ip + m_len) ^ UA_GET_NE64(m_pos + m_len);

        if __lzo_unlikely(v == 0) {

            do {

                m_len += 8;

                v = UA_GET_NE64(ip + m_len) ^ UA_GET_NE64(m_pos + m_len);

                if __lzo_unlikely(ip + m_len >= ip_end)

                    goto m_len_done;

            } while (v == 0);

        }

#if (LZO_ABI_BIG_ENDIAN) && defined(lzo_bitops_ctlz64)

        m_len += lzo_bitops_ctlz64(v) / CHAR_BIT;

#elif (LZO_ABI_BIG_ENDIAN)

        if ((v >> (64 - CHAR_BIT)) == 0) do {

            v <<= CHAR_BIT;

            m_len += 1;

        } while ((v >> (64 - CHAR_BIT)) == 0);

#elif (LZO_ABI_LITTLE_ENDIAN) && defined(lzo_bitops_cttz64)

        m_len += lzo_bitops_cttz64(v) / CHAR_BIT;

#elif (LZO_ABI_LITTLE_ENDIAN)

        if ((v & UCHAR_MAX) == 0) do {

            v >>= CHAR_BIT;

            m_len += 1;

        } while ((v & UCHAR_MAX) == 0);

#else

        if (ip[m_len] == m_pos[m_len]) do {

            m_len += 1;

        } while (ip[m_len] == m_pos[m_len]);

#endif

#elif (LZO_OPT_UNALIGNED32)

        lzo_uint32_t v;

        v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len);

        if __lzo_unlikely(v == 0) {

            do {

                m_len += 4;

                v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len);

                if (v != 0)

                    break;

                m_len += 4;

                v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len);

                if __lzo_unlikely(ip + m_len >= ip_end)

                    goto m_len_done;

            } while (v == 0);

        }

#if (LZO_ABI_BIG_ENDIAN) && defined(lzo_bitops_ctlz32)

        m_len += lzo_bitops_ctlz32(v) / CHAR_BIT;

#elif (LZO_ABI_BIG_ENDIAN)

        if ((v >> (32 - CHAR_BIT)) == 0) do {

            v <<= CHAR_BIT;

            m_len += 1;

        } while ((v >> (32 - CHAR_BIT)) == 0);

#elif (LZO_ABI_LITTLE_ENDIAN) && defined(lzo_bitops_cttz32)

        m_len += lzo_bitops_cttz32(v) / CHAR_BIT;

#elif (LZO_ABI_LITTLE_ENDIAN)

        if ((v & UCHAR_MAX) == 0) do {

            v >>= CHAR_BIT;

            m_len += 1;

        } while ((v & UCHAR_MAX) == 0);

#else

        if (ip[m_len] == m_pos[m_len]) do {

            m_len += 1;

        } while (ip[m_len] == m_pos[m_len]);

#endif

#else

        if __lzo_unlikely(ip[m_len] == m_pos[m_len]) {

            do {

                m_len += 1;

                if (ip[m_len] != m_pos[m_len])

                    break;

                m_len += 1;

                if (ip[m_len] != m_pos[m_len])

                    break;

                m_len += 1;

                if (ip[m_len] != m_pos[m_len])

                    break;

                m_len += 1;

                if (ip[m_len] != m_pos[m_len])

                    break;

                m_len += 1;

                if (ip[m_len] != m_pos[m_len])

                    break;

                m_len += 1;

                if (ip[m_len] != m_pos[m_len])

                    break;

                m_len += 1;

                if (ip[m_len] != m_pos[m_len])

                    break;

                m_len += 1;

                if __lzo_unlikely(ip + m_len >= ip_end)

                    goto m_len_done;

            } while (ip[m_len] == m_pos[m_len]);

        }

#endif

        }

m_len_done:

        m_off = pd(ip,m_pos);

        ip += m_len;

        ii = ip;

        if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)

        {

            m_off -= 1;

#if defined(LZO1X)

            *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));

            *op++ = LZO_BYTE(m_off >> 3);

#elif defined(LZO1Y)

            *op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2));

            *op++ = LZO_BYTE(m_off >> 2);

#endif

        }

        else if (m_off <= M3_MAX_OFFSET)

        {

            m_off -= 1;

            if (m_len <= M3_MAX_LEN)

                *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));

            else

            {

                m_len -= M3_MAX_LEN;

                *op++ = M3_MARKER | 0;

                while __lzo_unlikely(m_len > 255)

                {

                    m_len -= 255;

                    UA_SET1(op, 0);

                    op++;

                }

                *op++ = LZO_BYTE(m_len);

            }

            *op++ = LZO_BYTE(m_off << 2);

            *op++ = LZO_BYTE(m_off >> 6);

        }

        else

        {

            m_off -= 0x4000;

            if (m_len <= M4_MAX_LEN)

                *op++ = LZO_BYTE(M4_MARKER | ((m_off >> 11) & 8) | (m_len - 2));

            else

            {

                m_len -= M4_MAX_LEN;

                *op++ = LZO_BYTE(M4_MARKER | ((m_off >> 11) & 8));

                while __lzo_unlikely(m_len > 255)

                {

                    m_len -= 255;

                    UA_SET1(op, 0);

                    op++;

                }

                *op++ = LZO_BYTE(m_len);

            }

            *op++ = LZO_BYTE(m_off << 2);

            *op++ = LZO_BYTE(m_off >> 6);

        }

        goto next;

    }

    *out_len = pd(op, out);

    return pd(in_end,ii-ti);

}

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

// public entry point

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

LZO_PUBLIC(int)

DO_COMPRESS      ( const lzo_bytep in , lzo_uint  in_len,

                         lzo_bytep out, lzo_uintp out_len,

                         lzo_voidp wrkmem )

{

    const lzo_bytep ip = in;

    lzo_bytep op = out;

    lzo_uint l = in_len;

    lzo_uint t = 0;

    while (l > 20)

    {

        lzo_uint ll = l;

        lzo_uintptr_t ll_end;

#if 0 || (LZO_DETERMINISTIC)

        ll = LZO_MIN(ll, 49152);

#endif

        ll_end = (lzo_uintptr_t)ip + ll;

        if ((ll_end + ((t + ll) >> 5)) <= ll_end || (const lzo_bytep)(ll_end + ((t + ll) >> 5)) <= ip + ll)

            break;

#if (LZO_DETERMINISTIC)

        lzo_memset(wrkmem, 0, ((lzo_uint)1 << D_BITS) * sizeof(lzo_dict_t));

#endif

        t = do_compress(ip,ll,op,out_len,t,wrkmem);

        ip += ll;

        op += *out_len;

        l  -= ll;

    }

    t += l;

    if (t > 0)

    {

        const lzo_bytep ii = in + in_len - t;

        if (op == out && t <= 238)

            *op++ = LZO_BYTE(17 + t);

        else if (t <= 3)

            op[-2] = LZO_BYTE(op[-2] | t);

        else if (t <= 18)

            *op++ = LZO_BYTE(t - 3);

        else

        {

            lzo_uint tt = t - 18;

            *op++ = 0;

            while (tt > 255)

            {

                tt -= 255;

                UA_SET1(op, 0);

                op++;

            }

            assert(tt > 0);

            *op++ = LZO_BYTE(tt);

        }

        UA_COPYN(op, ii, t);

        op += t;

    }

    *op++ = M4_MARKER | 1;

    *op++ = 0;

    *op++ = 0;

    *out_len = pd(op, out);

    return LZO_E_OK;

}

/*

vi:ts=4:et

*/