Blame src/lzo1x_oo.ch

Packit Service 5195f2
/* lzo1x_oo.ch -- LZO1X compressed data optimizer
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
#define TEST_IP     (ip < ip_end)
Packit Service 5195f2
#define TEST_OP     (op <= op_end)
Packit Service 5195f2
#define TEST_IP_AND_TEST_OP (TEST_IP && TEST_OP)
Packit Service 5195f2
Packit Service 5195f2
#define NO_LIT      LZO_UINT_MAX
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
//
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
static void copy2(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off)
Packit Service 5195f2
{
Packit Service 5195f2
    assert(off > 0);
Packit Service 5195f2
    ip[0] = m_pos[0];
Packit Service 5195f2
    if (off == 1)
Packit Service 5195f2
        ip[1] = m_pos[0];
Packit Service 5195f2
    else
Packit Service 5195f2
        ip[1] = m_pos[1];
Packit Service 5195f2
}
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
static void copy3(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off)
Packit Service 5195f2
{
Packit Service 5195f2
    assert(off > 0);
Packit Service 5195f2
    ip[0] = m_pos[0];
Packit Service 5195f2
    if (off == 1)
Packit Service 5195f2
    {
Packit Service 5195f2
        ip[2] = ip[1] = m_pos[0];
Packit Service 5195f2
    }
Packit Service 5195f2
    else if (off == 2)
Packit Service 5195f2
    {
Packit Service 5195f2
        ip[1] = m_pos[1];
Packit Service 5195f2
        ip[2] = m_pos[0];
Packit Service 5195f2
    }
Packit Service 5195f2
    else
Packit Service 5195f2
    {
Packit Service 5195f2
        ip[1] = m_pos[1];
Packit Service 5195f2
        ip[2] = m_pos[2];
Packit Service 5195f2
    }
Packit Service 5195f2
}
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
/***********************************************************************
Packit Service 5195f2
// optimize a block of data.
Packit Service 5195f2
************************************************************************/
Packit Service 5195f2
Packit Service 5195f2
LZO_PUBLIC(int)
Packit Service 5195f2
DO_OPTIMIZE          (       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
    lzo_bytep ip;
Packit Service 5195f2
    lzo_uint t;
Packit Service 5195f2
    lzo_bytep m_pos;
Packit Service 5195f2
    lzo_bytep const ip_end = in + in_len;
Packit Service 5195f2
    lzo_bytep const op_end = out + *out_len;
Packit Service 5195f2
    lzo_bytep litp = NULL;
Packit Service 5195f2
    lzo_uint lit = 0;
Packit Service 5195f2
    lzo_uint next_lit = NO_LIT;
Packit Service 5195f2
    lzo_uint nl;
Packit Service 5195f2
    unsigned long o_m1_a = 0, o_m1_b = 0, o_m2 = 0, o_m3_a = 0, o_m3_b = 0;
Packit Service 5195f2
Packit Service 5195f2
    LZO_UNUSED(wrkmem);
Packit Service 5195f2
Packit Service 5195f2
    *out_len = 0;
Packit Service 5195f2
Packit Service 5195f2
    op = out;
Packit Service 5195f2
    ip = in;
Packit Service 5195f2
Packit Service 5195f2
    assert(in_len >= 3);
Packit Service 5195f2
    if (*ip > 17)
Packit Service 5195f2
    {
Packit Service 5195f2
        t = *ip++ - 17;
Packit Service 5195f2
        if (t < 4)
Packit Service 5195f2
            goto match_next;
Packit Service 5195f2
        goto first_literal_run;
Packit Service 5195f2
    }
Packit Service 5195f2
    assert(*ip < 16 || (*ip == 17 && in_len == 3));
Packit Service 5195f2
Packit Service 5195f2
    while (TEST_IP_AND_TEST_OP)
Packit Service 5195f2
    {
Packit Service 5195f2
        t = *ip++;
Packit Service 5195f2
        if (t >= 16)
Packit Service 5195f2
            goto match;
Packit Service 5195f2
        /* a literal run */
Packit Service 5195f2
        litp = ip - 1;
Packit Service 5195f2
        if (t == 0)
Packit Service 5195f2
        {
Packit Service 5195f2
            t = 15;
Packit Service 5195f2
            while (*ip == 0)
Packit Service 5195f2
                t += 255, ip++;
Packit Service 5195f2
            t += *ip++;
Packit Service 5195f2
        }
Packit Service 5195f2
        lit = t + 3;
Packit Service 5195f2
        /* copy literals */
Packit Service 5195f2
copy_literal_run:
Packit Service 5195f2
        *op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
Packit Service 5195f2
first_literal_run:
Packit Service 5195f2
        do *op++ = *ip++; while (--t > 0);
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
        t = *ip++;
Packit Service 5195f2
Packit Service 5195f2
        if (t >= 16)
Packit Service 5195f2
            goto match;
Packit Service 5195f2
#if defined(LZO1X)
Packit Service 5195f2
        m_pos = op - 1 - 0x800;
Packit Service 5195f2
#elif defined(LZO1Y)
Packit Service 5195f2
        m_pos = op - 1 - 0x400;
Packit Service 5195f2
#endif
Packit Service 5195f2
        m_pos -= t >> 2;
Packit Service 5195f2
        m_pos -= *ip++ << 2;
Packit Service 5195f2
        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
Packit Service 5195f2
        lit = 0;
Packit Service 5195f2
        goto match_done;
Packit Service 5195f2
Packit Service 5195f2
Packit Service 5195f2
        /* handle matches */
Packit Service 5195f2
        do {
Packit Service 5195f2
            if (t < 16)                     /* a M1 match */
Packit Service 5195f2
            {
Packit Service 5195f2
                m_pos = op - 1;
Packit Service 5195f2
                m_pos -= t >> 2;
Packit Service 5195f2
                m_pos -= *ip++ << 2;
Packit Service 5195f2
Packit Service 5195f2
                if (litp == NULL)
Packit Service 5195f2
                    goto copy_m1;
Packit Service 5195f2
Packit Service 5195f2
                /* assert that there was a match just before */
Packit Service 5195f2
                assert(lit >= 1 && lit <= 3);
Packit Service 5195f2
                assert(litp == ip - 2 - lit - 2);
Packit Service 5195f2
                assert((lzo_uint)(*litp & 3) == lit);
Packit Service 5195f2
                nl = ip[-2] & 3;
Packit Service 5195f2
                /* test if a match follows */
Packit Service 5195f2
                if (nl == 0 && lit == 1 && ip[0] >= 16)
Packit Service 5195f2
                {
Packit Service 5195f2
                    next_lit = nl;
Packit Service 5195f2
                    /* adjust length of previous short run */
Packit Service 5195f2
                    lit += 2;
Packit Service 5195f2
                    *litp = LZO_BYTE((*litp & ~3) | lit);
Packit Service 5195f2
                    /* copy over the 2 literals that replace the match */
Packit Service 5195f2
                    copy2(ip-2,m_pos,pd(op,m_pos));
Packit Service 5195f2
                    o_m1_a++;
Packit Service 5195f2
                }
Packit Service 5195f2
                /* test if a literal run follows */
Packit Service 5195f2
                else if (nl == 0 && ip[0] < 16 && ip[0] != 0 &&
Packit Service 5195f2
                         (lit + 2 + ip[0] < 16))
Packit Service 5195f2
                {
Packit Service 5195f2
                    t = *ip++;
Packit Service 5195f2
                    /* remove short run */
Packit Service 5195f2
                    *litp &= ~3;
Packit Service 5195f2
                    /* copy over the 2 literals that replace the match */
Packit Service 5195f2
                    copy2(ip-3+1,m_pos,pd(op,m_pos));
Packit Service 5195f2
                    /* move literals 1 byte ahead */
Packit Service 5195f2
                    litp += 2;
Packit Service 5195f2
                    if (lit > 0)
Packit Service 5195f2
                        lzo_memmove(litp+1,litp,lit);
Packit Service 5195f2
                    /* insert new length of long literal run */
Packit Service 5195f2
                    lit += 2 + t + 3; assert(lit <= 18);
Packit Service 5195f2
                    *litp = LZO_BYTE(lit - 3);
Packit Service 5195f2
Packit Service 5195f2
                    o_m1_b++;
Packit Service 5195f2
                    *op++ = *m_pos++; *op++ = *m_pos++;
Packit Service 5195f2
                    goto copy_literal_run;
Packit Service 5195f2
                }
Packit Service 5195f2
copy_m1:
Packit Service 5195f2
                *op++ = *m_pos++; *op++ = *m_pos++;
Packit Service 5195f2
            }
Packit Service 5195f2
            else
Packit Service 5195f2
            {
Packit Service 5195f2
match:
Packit Service 5195f2
                if (t >= 64)                /* a M2 match */
Packit Service 5195f2
                {
Packit Service 5195f2
                    m_pos = op - 1;
Packit Service 5195f2
#if defined(LZO1X)
Packit Service 5195f2
                    m_pos -= (t >> 2) & 7;
Packit Service 5195f2
                    m_pos -= *ip++ << 3;
Packit Service 5195f2
                    t = (t >> 5) - 1;
Packit Service 5195f2
#elif defined(LZO1Y)
Packit Service 5195f2
                    m_pos -= (t >> 2) & 3;
Packit Service 5195f2
                    m_pos -= *ip++ << 2;
Packit Service 5195f2
                    t = (t >> 4) - 3;
Packit Service 5195f2
#endif
Packit Service 5195f2
                    if (litp == NULL)
Packit Service 5195f2
                        goto copy_m;
Packit Service 5195f2
Packit Service 5195f2
                    nl = ip[-2] & 3;
Packit Service 5195f2
                    /* test if in beetween two long literal runs */
Packit Service 5195f2
                    if (t == 1 && lit > 3 && nl == 0 &&
Packit Service 5195f2
                        ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))
Packit Service 5195f2
                    {
Packit Service 5195f2
                        assert(*litp == lit - 3);
Packit Service 5195f2
                        t = *ip++;
Packit Service 5195f2
                        /* copy over the 3 literals that replace the match */
Packit Service 5195f2
                        copy3(ip-1-2,m_pos,pd(op,m_pos));
Packit Service 5195f2
                        /* set new length of previous literal run */
Packit Service 5195f2
                        lit += 3 + t + 3; assert(lit <= 18);
Packit Service 5195f2
                        *litp = LZO_BYTE(lit - 3);
Packit Service 5195f2
                        o_m2++;
Packit Service 5195f2
                        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
Packit Service 5195f2
                        goto copy_literal_run;
Packit Service 5195f2
                    }
Packit Service 5195f2
                }
Packit Service 5195f2
                else
Packit Service 5195f2
                {
Packit Service 5195f2
                    if (t >= 32)            /* a M3 match */
Packit Service 5195f2
                    {
Packit Service 5195f2
                        t &= 31;
Packit Service 5195f2
                        if (t == 0)
Packit Service 5195f2
                        {
Packit Service 5195f2
                            t = 31;
Packit Service 5195f2
                            while (*ip == 0)
Packit Service 5195f2
                                t += 255, ip++;
Packit Service 5195f2
                            t += *ip++;
Packit Service 5195f2
                        }
Packit Service 5195f2
                        m_pos = op - 1;
Packit Service 5195f2
                        m_pos -= *ip++ >> 2;
Packit Service 5195f2
                        m_pos -= *ip++ << 6;
Packit Service 5195f2
                    }
Packit Service 5195f2
                    else                    /* a M4 match */
Packit Service 5195f2
                    {
Packit Service 5195f2
                        m_pos = op;
Packit Service 5195f2
                        m_pos -= (t & 8) << 11;
Packit Service 5195f2
                        t &= 7;
Packit Service 5195f2
                        if (t == 0)
Packit Service 5195f2
                        {
Packit Service 5195f2
                            t = 7;
Packit Service 5195f2
                            while (*ip == 0)
Packit Service 5195f2
                                t += 255, ip++;
Packit Service 5195f2
                            t += *ip++;
Packit Service 5195f2
                        }
Packit Service 5195f2
                        m_pos -= *ip++ >> 2;
Packit Service 5195f2
                        m_pos -= *ip++ << 6;
Packit Service 5195f2
                        if (m_pos == op)
Packit Service 5195f2
                            goto eof_found;
Packit Service 5195f2
                        m_pos -= 0x4000;
Packit Service 5195f2
                    }
Packit Service 5195f2
                    if (litp == NULL)
Packit Service 5195f2
                        goto copy_m;
Packit Service 5195f2
Packit Service 5195f2
                    nl = ip[-2] & 3;
Packit Service 5195f2
                    /* test if in beetween two matches */
Packit Service 5195f2
                    if (t == 1 && lit == 0 && nl == 0 && ip[0] >= 16)
Packit Service 5195f2
                    {
Packit Service 5195f2
                        assert(litp == ip - 3 - lit - 2);
Packit Service 5195f2
                        assert((lzo_uint)(*litp & 3) == lit);
Packit Service 5195f2
                        next_lit = nl;
Packit Service 5195f2
                        /* make a previous short run */
Packit Service 5195f2
                        lit += 3;
Packit Service 5195f2
                        *litp = LZO_BYTE((*litp & ~3) | lit);
Packit Service 5195f2
                        /* copy over the 3 literals that replace the match */
Packit Service 5195f2
                        copy3(ip-3,m_pos,pd(op,m_pos));
Packit Service 5195f2
                        o_m3_a++;
Packit Service 5195f2
                    }
Packit Service 5195f2
                    /* test if a literal run follows */
Packit Service 5195f2
                    else if (t == 1 && lit <= 3 && nl == 0 &&
Packit Service 5195f2
                             ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))
Packit Service 5195f2
                    {
Packit Service 5195f2
                        assert(litp == ip - 3 - lit - 2);
Packit Service 5195f2
                        assert((lzo_uint)(*litp & 3) == lit);
Packit Service 5195f2
                        t = *ip++;
Packit Service 5195f2
                        /* remove short run */
Packit Service 5195f2
                        *litp &= ~3;
Packit Service 5195f2
                        /* copy over the 3 literals that replace the match */
Packit Service 5195f2
                        copy3(ip-4+1,m_pos,pd(op,m_pos));
Packit Service 5195f2
                        /* move literals 1 byte ahead */
Packit Service 5195f2
                        litp += 2;
Packit Service 5195f2
                        if (lit > 0)
Packit Service 5195f2
                            lzo_memmove(litp+1,litp,lit);
Packit Service 5195f2
                        /* insert new length of long literal run */
Packit Service 5195f2
                        lit += 3 + t + 3; assert(lit <= 18);
Packit Service 5195f2
                        *litp = LZO_BYTE(lit - 3);
Packit Service 5195f2
Packit Service 5195f2
                        o_m3_b++;
Packit Service 5195f2
                        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
Packit Service 5195f2
                        goto copy_literal_run;
Packit Service 5195f2
                    }
Packit Service 5195f2
                }
Packit Service 5195f2
copy_m:
Packit Service 5195f2
                *op++ = *m_pos++; *op++ = *m_pos++;
Packit Service 5195f2
                do *op++ = *m_pos++; while (--t > 0);
Packit Service 5195f2
            }
Packit Service 5195f2
Packit Service 5195f2
match_done:
Packit Service 5195f2
            if (next_lit == NO_LIT)
Packit Service 5195f2
            {
Packit Service 5195f2
                t = ip[-2] & 3;
Packit Service 5195f2
                lit = t;
Packit Service 5195f2
                litp = ip - 2;
Packit Service 5195f2
            }
Packit Service 5195f2
            else
Packit Service 5195f2
                t = next_lit;
Packit Service 5195f2
            assert(t <= 3);
Packit Service 5195f2
            next_lit = NO_LIT;
Packit Service 5195f2
            if (t == 0)
Packit Service 5195f2
                break;
Packit Service 5195f2
            /* copy literals */
Packit Service 5195f2
match_next:
Packit Service 5195f2
            do *op++ = *ip++; while (--t > 0);
Packit Service 5195f2
            t = *ip++;
Packit Service 5195f2
        } while (TEST_IP_AND_TEST_OP);
Packit Service 5195f2
    }
Packit Service 5195f2
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
Packit Service 5195f2
eof_found:
Packit Service 5195f2
    assert(t == 1);
Packit Service 5195f2
#if 0
Packit Service 5195f2
    printf("optimize: %5lu %5lu   %5lu   %5lu %5lu\n",
Packit Service 5195f2
           o_m1_a, o_m1_b, o_m2, o_m3_a, o_m3_b);
Packit Service 5195f2
#endif
Packit Service 5195f2
    LZO_UNUSED(o_m1_a); LZO_UNUSED(o_m1_b); LZO_UNUSED(o_m2);
Packit Service 5195f2
    LZO_UNUSED(o_m3_a); LZO_UNUSED(o_m3_b);
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
Packit Service 5195f2
/*
Packit Service 5195f2
vi:ts=4:et
Packit Service 5195f2
*/
Packit Service 5195f2