kusano 7d535a
/* lzo1x_oo.ch -- LZO1X compressed data optimizer
kusano 7d535a
kusano 7d535a
   This file is part of the LZO real-time data compression library.
kusano 7d535a
kusano 7d535a
   Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
kusano 7d535a
   All Rights Reserved.
kusano 7d535a
kusano 7d535a
   The LZO library is free software; you can redistribute it and/or
kusano 7d535a
   modify it under the terms of the GNU General Public License as
kusano 7d535a
   published by the Free Software Foundation; either version 2 of
kusano 7d535a
   the License, or (at your option) any later version.
kusano 7d535a
kusano 7d535a
   The LZO library is distributed in the hope that it will be useful,
kusano 7d535a
   but WITHOUT ANY WARRANTY; without even the implied warranty of
kusano 7d535a
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
kusano 7d535a
   GNU General Public License for more details.
kusano 7d535a
kusano 7d535a
   You should have received a copy of the GNU General Public License
kusano 7d535a
   along with the LZO library; see the file COPYING.
kusano 7d535a
   If not, write to the Free Software Foundation, Inc.,
kusano 7d535a
   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
kusano 7d535a
kusano 7d535a
   Markus F.X.J. Oberhumer
kusano 7d535a
   <markus@oberhumer.com></markus@oberhumer.com>
kusano 7d535a
   http://www.oberhumer.com/opensource/lzo/
kusano 7d535a
 */
kusano 7d535a
kusano 7d535a
kusano 7d535a
#define TEST_IP     (ip < ip_end)
kusano 7d535a
#define TEST_OP     (op <= op_end)
kusano 7d535a
kusano 7d535a
#define NO_LIT      LZO_UINT_MAX
kusano 7d535a
kusano 7d535a
kusano 7d535a
/***********************************************************************
kusano 7d535a
//
kusano 7d535a
************************************************************************/
kusano 7d535a
kusano 7d535a
static void copy2(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off)
kusano 7d535a
{
kusano 7d535a
    assert(off > 0);
kusano 7d535a
    ip[0] = m_pos[0];
kusano 7d535a
    if (off == 1)
kusano 7d535a
        ip[1] = m_pos[0];
kusano 7d535a
    else
kusano 7d535a
        ip[1] = m_pos[1];
kusano 7d535a
}
kusano 7d535a
kusano 7d535a
kusano 7d535a
static void copy3(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off)
kusano 7d535a
{
kusano 7d535a
    assert(off > 0);
kusano 7d535a
    ip[0] = m_pos[0];
kusano 7d535a
    if (off == 1)
kusano 7d535a
    {
kusano 7d535a
        ip[2] = ip[1] = m_pos[0];
kusano 7d535a
    }
kusano 7d535a
    else if (off == 2)
kusano 7d535a
    {
kusano 7d535a
        ip[1] = m_pos[1];
kusano 7d535a
        ip[2] = m_pos[0];
kusano 7d535a
    }
kusano 7d535a
    else
kusano 7d535a
    {
kusano 7d535a
        ip[1] = m_pos[1];
kusano 7d535a
        ip[2] = m_pos[2];
kusano 7d535a
    }
kusano 7d535a
}
kusano 7d535a
kusano 7d535a
kusano 7d535a
/***********************************************************************
kusano 7d535a
// optimize a block of data.
kusano 7d535a
************************************************************************/
kusano 7d535a
kusano 7d535a
LZO_PUBLIC(int)
kusano 7d535a
DO_OPTIMIZE          (       lzo_bytep in , lzo_uint  in_len,
kusano 7d535a
                             lzo_bytep out, lzo_uintp out_len,
kusano 7d535a
                             lzo_voidp wrkmem )
kusano 7d535a
{
kusano 7d535a
    lzo_bytep op;
kusano 7d535a
    lzo_bytep ip;
kusano 7d535a
    lzo_uint t;
kusano 7d535a
    lzo_bytep m_pos;
kusano 7d535a
    lzo_bytep const ip_end = in + in_len;
kusano 7d535a
    lzo_bytep const op_end = out + *out_len;
kusano 7d535a
    lzo_bytep litp = NULL;
kusano 7d535a
    lzo_uint lit = 0;
kusano 7d535a
    lzo_uint next_lit = NO_LIT;
kusano 7d535a
    lzo_uint nl;
kusano 7d535a
    unsigned long o_m1_a = 0, o_m1_b = 0, o_m2 = 0, o_m3_a = 0, o_m3_b = 0;
kusano 7d535a
kusano 7d535a
    LZO_UNUSED(wrkmem);
kusano 7d535a
kusano 7d535a
    *out_len = 0;
kusano 7d535a
kusano 7d535a
    op = out;
kusano 7d535a
    ip = in;
kusano 7d535a
kusano 7d535a
    assert(in_len >= 3);
kusano 7d535a
    if (*ip > 17)
kusano 7d535a
    {
kusano 7d535a
        t = *ip++ - 17;
kusano 7d535a
        if (t < 4)
kusano 7d535a
            goto match_next;
kusano 7d535a
        goto first_literal_run;
kusano 7d535a
    }
kusano 7d535a
    assert(*ip < 16 || (*ip == 17 && in_len == 3));
kusano 7d535a
kusano 7d535a
    while (TEST_IP && TEST_OP)
kusano 7d535a
    {
kusano 7d535a
        t = *ip++;
kusano 7d535a
        if (t >= 16)
kusano 7d535a
            goto match;
kusano 7d535a
        /* a literal run */
kusano 7d535a
        litp = ip - 1;
kusano 7d535a
        if (t == 0)
kusano 7d535a
        {
kusano 7d535a
            t = 15;
kusano 7d535a
            while (*ip == 0)
kusano 7d535a
                t += 255, ip++;
kusano 7d535a
            t += *ip++;
kusano 7d535a
        }
kusano 7d535a
        lit = t + 3;
kusano 7d535a
        /* copy literals */
kusano 7d535a
copy_literal_run:
kusano 7d535a
        *op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
kusano 7d535a
first_literal_run:
kusano 7d535a
        do *op++ = *ip++; while (--t > 0);
kusano 7d535a
kusano 7d535a
kusano 7d535a
        t = *ip++;
kusano 7d535a
kusano 7d535a
        if (t >= 16)
kusano 7d535a
            goto match;
kusano 7d535a
#if defined(LZO1X)
kusano 7d535a
        m_pos = op - 1 - 0x800;
kusano 7d535a
#elif defined(LZO1Y)
kusano 7d535a
        m_pos = op - 1 - 0x400;
kusano 7d535a
#endif
kusano 7d535a
        m_pos -= t >> 2;
kusano 7d535a
        m_pos -= *ip++ << 2;
kusano 7d535a
        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
kusano 7d535a
        lit = 0;
kusano 7d535a
        goto match_done;
kusano 7d535a
kusano 7d535a
kusano 7d535a
        /* handle matches */
kusano 7d535a
        do {
kusano 7d535a
            if (t < 16)                     /* a M1 match */
kusano 7d535a
            {
kusano 7d535a
                m_pos = op - 1;
kusano 7d535a
                m_pos -= t >> 2;
kusano 7d535a
                m_pos -= *ip++ << 2;
kusano 7d535a
kusano 7d535a
                if (litp == NULL)
kusano 7d535a
                    goto copy_m1;
kusano 7d535a
kusano 7d535a
                /* assert that there was a match just before */
kusano 7d535a
                assert(lit >= 1 && lit <= 3);
kusano 7d535a
                assert(litp == ip - 2 - lit - 2);
kusano 7d535a
                assert((lzo_uint)(*litp & 3) == lit);
kusano 7d535a
                nl = ip[-2] & 3;
kusano 7d535a
                /* test if a match follows */
kusano 7d535a
                if (nl == 0 && lit == 1 && ip[0] >= 16)
kusano 7d535a
                {
kusano 7d535a
                    next_lit = nl;
kusano 7d535a
                    /* adjust length of previous short run */
kusano 7d535a
                    lit += 2;
kusano 7d535a
                    *litp = LZO_BYTE((*litp & ~3) | lit);
kusano 7d535a
                    /* copy over the 2 literals that replace the match */
kusano 7d535a
                    copy2(ip-2,m_pos,pd(op,m_pos));
kusano 7d535a
                    o_m1_a++;
kusano 7d535a
                }
kusano 7d535a
                /* test if a literal run follows */
kusano 7d535a
                else if (nl == 0 && ip[0] < 16 && ip[0] != 0 &&
kusano 7d535a
                         (lit + 2 + ip[0] < 16))
kusano 7d535a
                {
kusano 7d535a
                    t = *ip++;
kusano 7d535a
                    /* remove short run */
kusano 7d535a
                    *litp &= ~3;
kusano 7d535a
                    /* copy over the 2 literals that replace the match */
kusano 7d535a
                    copy2(ip-3+1,m_pos,pd(op,m_pos));
kusano 7d535a
                    /* move literals 1 byte ahead */
kusano 7d535a
                    litp += 2;
kusano 7d535a
                    if (lit > 0)
kusano 7d535a
                        lzo_memmove(litp+1,litp,lit);
kusano 7d535a
                    /* insert new length of long literal run */
kusano 7d535a
                    lit += 2 + t + 3; assert(lit <= 18);
kusano 7d535a
                    *litp = LZO_BYTE(lit - 3);
kusano 7d535a
kusano 7d535a
                    o_m1_b++;
kusano 7d535a
                    *op++ = *m_pos++; *op++ = *m_pos++;
kusano 7d535a
                    goto copy_literal_run;
kusano 7d535a
                }
kusano 7d535a
copy_m1:
kusano 7d535a
                *op++ = *m_pos++; *op++ = *m_pos++;
kusano 7d535a
            }
kusano 7d535a
            else
kusano 7d535a
            {
kusano 7d535a
match:
kusano 7d535a
                if (t >= 64)                /* a M2 match */
kusano 7d535a
                {
kusano 7d535a
                    m_pos = op - 1;
kusano 7d535a
#if defined(LZO1X)
kusano 7d535a
                    m_pos -= (t >> 2) & 7;
kusano 7d535a
                    m_pos -= *ip++ << 3;
kusano 7d535a
                    t = (t >> 5) - 1;
kusano 7d535a
#elif defined(LZO1Y)
kusano 7d535a
                    m_pos -= (t >> 2) & 3;
kusano 7d535a
                    m_pos -= *ip++ << 2;
kusano 7d535a
                    t = (t >> 4) - 3;
kusano 7d535a
#endif
kusano 7d535a
                    if (litp == NULL)
kusano 7d535a
                        goto copy_m;
kusano 7d535a
kusano 7d535a
                    nl = ip[-2] & 3;
kusano 7d535a
                    /* test if in beetween two long literal runs */
kusano 7d535a
                    if (t == 1 && lit > 3 && nl == 0 &&
kusano 7d535a
                        ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))
kusano 7d535a
                    {
kusano 7d535a
                        assert(*litp == lit - 3);
kusano 7d535a
                        t = *ip++;
kusano 7d535a
                        /* copy over the 3 literals that replace the match */
kusano 7d535a
                        copy3(ip-1-2,m_pos,pd(op,m_pos));
kusano 7d535a
                        /* set new length of previous literal run */
kusano 7d535a
                        lit += 3 + t + 3; assert(lit <= 18);
kusano 7d535a
                        *litp = LZO_BYTE(lit - 3);
kusano 7d535a
                        o_m2++;
kusano 7d535a
                        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
kusano 7d535a
                        goto copy_literal_run;
kusano 7d535a
                    }
kusano 7d535a
                }
kusano 7d535a
                else
kusano 7d535a
                {
kusano 7d535a
                    if (t >= 32)            /* a M3 match */
kusano 7d535a
                    {
kusano 7d535a
                        t &= 31;
kusano 7d535a
                        if (t == 0)
kusano 7d535a
                        {
kusano 7d535a
                            t = 31;
kusano 7d535a
                            while (*ip == 0)
kusano 7d535a
                                t += 255, ip++;
kusano 7d535a
                            t += *ip++;
kusano 7d535a
                        }
kusano 7d535a
                        m_pos = op - 1;
kusano 7d535a
                        m_pos -= *ip++ >> 2;
kusano 7d535a
                        m_pos -= *ip++ << 6;
kusano 7d535a
                    }
kusano 7d535a
                    else                    /* a M4 match */
kusano 7d535a
                    {
kusano 7d535a
                        m_pos = op;
kusano 7d535a
                        m_pos -= (t & 8) << 11;
kusano 7d535a
                        t &= 7;
kusano 7d535a
                        if (t == 0)
kusano 7d535a
                        {
kusano 7d535a
                            t = 7;
kusano 7d535a
                            while (*ip == 0)
kusano 7d535a
                                t += 255, ip++;
kusano 7d535a
                            t += *ip++;
kusano 7d535a
                        }
kusano 7d535a
                        m_pos -= *ip++ >> 2;
kusano 7d535a
                        m_pos -= *ip++ << 6;
kusano 7d535a
                        if (m_pos == op)
kusano 7d535a
                            goto eof_found;
kusano 7d535a
                        m_pos -= 0x4000;
kusano 7d535a
                    }
kusano 7d535a
                    if (litp == NULL)
kusano 7d535a
                        goto copy_m;
kusano 7d535a
kusano 7d535a
                    nl = ip[-2] & 3;
kusano 7d535a
                    /* test if in beetween two matches */
kusano 7d535a
                    if (t == 1 && lit == 0 && nl == 0 && ip[0] >= 16)
kusano 7d535a
                    {
kusano 7d535a
                        assert(litp == ip - 3 - lit - 2);
kusano 7d535a
                        assert((lzo_uint)(*litp & 3) == lit);
kusano 7d535a
                        next_lit = nl;
kusano 7d535a
                        /* make a previous short run */
kusano 7d535a
                        lit += 3;
kusano 7d535a
                        *litp = LZO_BYTE((*litp & ~3) | lit);
kusano 7d535a
                        /* copy over the 3 literals that replace the match */
kusano 7d535a
                        copy3(ip-3,m_pos,pd(op,m_pos));
kusano 7d535a
                        o_m3_a++;
kusano 7d535a
                    }
kusano 7d535a
                    /* test if a literal run follows */
kusano 7d535a
                    else if (t == 1 && lit <= 3 && nl == 0 &&
kusano 7d535a
                             ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))
kusano 7d535a
                    {
kusano 7d535a
                        assert(litp == ip - 3 - lit - 2);
kusano 7d535a
                        assert((lzo_uint)(*litp & 3) == lit);
kusano 7d535a
                        t = *ip++;
kusano 7d535a
                        /* remove short run */
kusano 7d535a
                        *litp &= ~3;
kusano 7d535a
                        /* copy over the 3 literals that replace the match */
kusano 7d535a
                        copy3(ip-4+1,m_pos,pd(op,m_pos));
kusano 7d535a
                        /* move literals 1 byte ahead */
kusano 7d535a
                        litp += 2;
kusano 7d535a
                        if (lit > 0)
kusano 7d535a
                            lzo_memmove(litp+1,litp,lit);
kusano 7d535a
                        /* insert new length of long literal run */
kusano 7d535a
                        lit += 3 + t + 3; assert(lit <= 18);
kusano 7d535a
                        *litp = LZO_BYTE(lit - 3);
kusano 7d535a
kusano 7d535a
                        o_m3_b++;
kusano 7d535a
                        *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
kusano 7d535a
                        goto copy_literal_run;
kusano 7d535a
                    }
kusano 7d535a
                }
kusano 7d535a
copy_m:
kusano 7d535a
                *op++ = *m_pos++; *op++ = *m_pos++;
kusano 7d535a
                do *op++ = *m_pos++; while (--t > 0);
kusano 7d535a
            }
kusano 7d535a
kusano 7d535a
match_done:
kusano 7d535a
            if (next_lit == NO_LIT)
kusano 7d535a
            {
kusano 7d535a
                t = ip[-2] & 3;
kusano 7d535a
                lit = t;
kusano 7d535a
                litp = ip - 2;
kusano 7d535a
            }
kusano 7d535a
            else
kusano 7d535a
                t = next_lit;
kusano 7d535a
            assert(t <= 3);
kusano 7d535a
            next_lit = NO_LIT;
kusano 7d535a
            if (t == 0)
kusano 7d535a
                break;
kusano 7d535a
            /* copy literals */
kusano 7d535a
match_next:
kusano 7d535a
            do *op++ = *ip++; while (--t > 0);
kusano 7d535a
            t = *ip++;
kusano 7d535a
        } while (TEST_IP && TEST_OP);
kusano 7d535a
    }
kusano 7d535a
kusano 7d535a
    /* no EOF code was found */
kusano 7d535a
    *out_len = pd(op, out);
kusano 7d535a
    return LZO_E_EOF_NOT_FOUND;
kusano 7d535a
kusano 7d535a
eof_found:
kusano 7d535a
    assert(t == 1);
kusano 7d535a
#if 0
kusano 7d535a
    printf("optimize: %5lu %5lu   %5lu   %5lu %5lu\n",
kusano 7d535a
           o_m1_a, o_m1_b, o_m2, o_m3_a, o_m3_b);
kusano 7d535a
#endif
kusano 7d535a
    LZO_UNUSED(o_m1_a); LZO_UNUSED(o_m1_b); LZO_UNUSED(o_m2);
kusano 7d535a
    LZO_UNUSED(o_m3_a); LZO_UNUSED(o_m3_b);
kusano 7d535a
    *out_len = pd(op, out);
kusano 7d535a
    return (ip == ip_end ? LZO_E_OK :
kusano 7d535a
           (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
kusano 7d535a
}
kusano 7d535a
kusano 7d535a
kusano 7d535a
/*
kusano 7d535a
vi:ts=4:et
kusano 7d535a
*/
kusano 7d535a