/* 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
*/