/*

 *  lzo.c -- LZO1X Compressor from LZO

 *

 *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>

 *

 *  The full LZO package can be found at:

 *  http://www.oberhumer.com/opensource/lzo/

 *

 *  Adapted for Xen (files combined and syntactic/header changes) by:

 *  Dan Magenheimer <dan.magenheimer@oracle.com>

 *

 */

/*

 *  lzodefs.h -- architecture, OS and compiler specific defines

 *

 *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>

 *

 *  The full LZO package can be found at:

 *  http://www.oberhumer.com/opensource/lzo/

 *

 *  Changed for Linux kernel use by:

 *  Nitin Gupta <nitingupta910@gmail.com>

 *  Richard Purdie <rpurdie@openedhand.com>

 */

#define COPY4(dst, src)    \

        put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))

#if defined(__x86_64__)

#define COPY8(dst, src)    \

        put_unaligned(get_unaligned((const u64 *)(src)), (u64 *)(dst))

#else

#define COPY8(dst, src)    \

        COPY4(dst, src); COPY4((dst) + 4, (src) + 4)

#endif

#ifdef __MINIOS__

# include <lib.h>

# if __BYTE_ORDER == __LITTLE_ENDIAN

#  undef __BIG_ENDIAN

# endif

# if __BYTE_ORDER == __BIG_ENDIAN

#  undef __LITTLE_ENDIAN

# endif

#endif

#if defined(__BIG_ENDIAN) && defined(__LITTLE_ENDIAN)

#error "conflicting endian definitions"

#elif defined(__x86_64__)

#define LZO_USE_CTZ64    1

#define LZO_USE_CTZ32    1

#elif defined(__i386__) || defined(__powerpc__)

#define LZO_USE_CTZ32    1

#elif defined(__arm__) && (__LINUX_ARM_ARCH__ >= 5)

#define LZO_USE_CTZ32    1

#endif

#define M1_MAX_OFFSET 0x0400

#define M2_MAX_OFFSET 0x0800

#define M3_MAX_OFFSET 0x4000

#define M4_MAX_OFFSET 0xbfff

#define M1_MIN_LEN 2

#define M1_MAX_LEN 2

#define M2_MIN_LEN 3

#define M2_MAX_LEN 8

#define M3_MIN_LEN 3

#define M3_MAX_LEN 33

#define M4_MIN_LEN 3

#define M4_MAX_LEN 9

#define M1_MARKER 0

#define M2_MARKER 64

#define M3_MARKER 32

#define M4_MARKER 16

#define lzo_dict_t unsigned short

#define D_BITS  13

#define D_SIZE  (1u << D_BITS)

#define D_MASK  (D_SIZE - 1)

#define D_HIGH  ((D_MASK >> 1) + 1)

/*

 *  LZO1X Compressor from LZO

 *

 *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>

 *

 *  The full LZO package can be found at:

 *  http://www.oberhumer.com/opensource/lzo/

 *

 *  Changed for Linux kernel use by:

 *  Nitin Gupta <nitingupta910@gmail.com>

 *  Richard Purdie <rpurdie@openedhand.com>

 */

#ifdef __XEN__

#include <xen/lib.h>

#include <asm/byteorder.h>

#endif

#include <xen/lzo.h>

#define get_unaligned(_p) (*(_p))

#define put_unaligned(_val,_p) (*(_p)=_val)

#define get_unaligned_le16(_p) (*(u16 *)(_p))

#define get_unaligned_le32(_p) (*(u32 *)(_p))

static noinline size_t

lzo1x_1_do_compress(const unsigned char *in, size_t in_len,

                    unsigned char *out, size_t *out_len,

                    size_t ti, void *wrkmem)

{

    const unsigned char *ip;

    unsigned char *op;

    const unsigned char * const in_end = in + in_len;

    const unsigned char * const ip_end = in + in_len - 20;

    const unsigned char *ii;

    lzo_dict_t * const dict = (lzo_dict_t *) wrkmem;

    op = out;

    ip = in;

    ii = ip;

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

    for (;;) {

        const unsigned char *m_pos;

        size_t t, m_len, m_off;

        u32 dv;

    literal:

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

    next:

        if (unlikely(ip >= ip_end))

            break;

        dv = get_unaligned_le32(ip);

        t = ((dv * 0x1824429d) >> (32 - D_BITS)) & D_MASK;

        m_pos = in + dict[t];

        dict[t] = (lzo_dict_t) (ip - in);

        if (unlikely(dv != get_unaligned_le32(m_pos)))

            goto literal;

        ii -= ti;

        ti = 0;

        t = ip - ii;

        if (t != 0) {

            if (t <= 3) {

                op[-2] |= t;

                COPY4(op, ii);

                op += t;

            } else if (t <= 16) {

                *op++ = (t - 3);

                COPY8(op, ii);

                COPY8(op + 8, ii + 8);

                op += t;

            } else {

                if (t <= 18) {

                    *op++ = (t - 3);

                } else {

                    size_t tt = t - 18;

                    *op++ = 0;

                    while (unlikely(tt > 255)) {

                        tt -= 255;

                        *op++ = 0;

                    }

                    *op++ = tt;

                }

                do {

                    COPY8(op, ii);

                    COPY8(op + 8, ii + 8);

                    op += 16;

                    ii += 16;

                    t -= 16;

                } while (t >= 16);

                if (t > 0) do {

                    *op++ = *ii++;

                } while (--t > 0);

            }

        }

        m_len = 4;

        {

#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && defined(LZO_USE_CTZ64)

        u64 v;

        v = get_unaligned((const u64 *) (ip + m_len)) ^

            get_unaligned((const u64 *) (m_pos + m_len));

        if (unlikely(v == 0)) {

            do {

                m_len += 8;

                v = get_unaligned((const u64 *) (ip + m_len)) ^

                    get_unaligned((const u64 *) (m_pos + m_len));

                if (unlikely(ip + m_len >= ip_end))

                    goto m_len_done;

            } while (v == 0);

        }

#  if defined(__LITTLE_ENDIAN)

        m_len += (unsigned) __builtin_ctzll(v) / 8;

#  elif defined(__BIG_ENDIAN)

        m_len += (unsigned) __builtin_clzll(v) / 8;

#  else

#    error "missing endian definition"

#  endif

#elif defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && defined(LZO_USE_CTZ32)

        u32 v;

        v = get_unaligned((const u32 *) (ip + m_len)) ^

            get_unaligned((const u32 *) (m_pos + m_len));

        if (unlikely(v == 0)) {

            do {

                m_len += 4;

                v = get_unaligned((const u32 *) (ip + m_len)) ^

                    get_unaligned((const u32 *) (m_pos + m_len));

                if (v != 0)

                    break;

                m_len += 4;

                v = get_unaligned((const u32 *) (ip + m_len)) ^

                    get_unaligned((const u32 *) (m_pos + m_len));

                if (unlikely(ip + m_len >= ip_end))

                    goto m_len_done;

            } while (v == 0);

        }

#  if defined(__LITTLE_ENDIAN)

        m_len += (unsigned) __builtin_ctz(v) / 8;

#  elif defined(__BIG_ENDIAN)

        m_len += (unsigned) __builtin_clz(v) / 8;

#  else

#    error "missing endian definition"

#  endif

#else

        if (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 (unlikely(ip + m_len >= ip_end))

                    goto m_len_done;

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

        }

#endif

        }

 m_len_done:

        m_off = ip - m_pos;

        ip += m_len;

        ii = ip;

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

            m_off -= 1;

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

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

        } else if (m_off <= M3_MAX_OFFSET) {

            m_off -= 1;

            if (m_len <= M3_MAX_LEN)

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

            else {

                m_len -= M3_MAX_LEN;

                *op++ = M3_MARKER | 0;

                while (unlikely(m_len > 255)) {

                    m_len -= 255;

                    *op++ = 0;

                }

                *op++ = (m_len);

            }

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

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

        } else {

            m_off -= 0x4000;

            if (m_len <= M4_MAX_LEN)

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

                             | (m_len - 2));

            else {

                m_len -= M4_MAX_LEN;

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

                while (unlikely(m_len > 255)) {

                    m_len -= 255;

                    *op++ = 0;

                }

                *op++ = (m_len);

            }

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

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

        }

        goto next;

    }

    *out_len = op - out;

    return in_end - (ii - ti);

}

int lzo1x_1_compress(const unsigned char *in, size_t in_len,

                     unsigned char *out, size_t *out_len,

                     void *wrkmem)

{

    const unsigned char *ip = in;

    unsigned char *op = out;

    size_t l = in_len;

    size_t t = 0;

    while (l > 20) {

        size_t ll = l <= (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1);

        uintptr_t ll_end = (uintptr_t) ip + ll;

        if ((ll_end + ((t + ll) >> 5)) <= ll_end)

            break;

        BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);

        memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));

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

        ip += ll;

        op += *out_len;

        l  -= ll;

    }

    t += l;

    if (t > 0) {

        const unsigned char *ii = in + in_len - t;

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

            *op++ = (17 + t);

        } else if (t <= 3) {

            op[-2] |= t;

        } else if (t <= 18) {

            *op++ = (t - 3);

        } else {

            size_t tt = t - 18;

            *op++ = 0;

            while (tt > 255) {

                tt -= 255;

                *op++ = 0;

            }

            *op++ = tt;

        }

        if (t >= 16) do {

            COPY8(op, ii);

            COPY8(op + 8, ii + 8);

            op += 16;

            ii += 16;

            t -= 16;

        } while (t >= 16);

        if (t > 0) do {

            *op++ = *ii++;

        } while (--t > 0);

    }

    *op++ = M4_MARKER | 1;

    *op++ = 0;

    *op++ = 0;

    *out_len = op - out;

    return LZO_E_OK;

}

/*

 *  LZO1X Decompressor from LZO

 *

 *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>

 *

 *  The full LZO package can be found at:

 *  http://www.oberhumer.com/opensource/lzo/

 *

 *  Changed for Linux kernel use by:

 *  Nitin Gupta <nitingupta910@gmail.com>

 *  Richard Purdie <rpurdie@openedhand.com>

 */

#define HAVE_IP(x)     ((size_t)(ip_end - ip) >= (size_t)(x))

#define HAVE_OP(x)     ((size_t)(op_end - op) >= (size_t)(x))

#define NEED_IP(x)     if (!HAVE_IP(x)) goto input_overrun

#define NEED_OP(x)     if (!HAVE_OP(x)) goto output_overrun

#define TEST_LB(m_pos) if ((m_pos) < out) goto lookbehind_overrun

/* This MAX_255_COUNT is the maximum number of times we can add 255 to a base

 * count without overflowing an integer. The multiply will overflow when

 * multiplying 255 by more than MAXINT/255. The sum will overflow earlier

 * depending on the base count. Since the base count is taken from a u8

 * and a few bits, it is safe to assume that it will always be lower than

 * or equal to 2*255, thus we can always prevent any overflow by accepting

 * two less 255 steps. See Documentation/lzo.txt for more information.

 */

#define MAX_255_COUNT      ((((size_t)~0) / 255) - 2)

int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,

                          unsigned char *out, size_t *out_len)

{

    unsigned char *op;

    const unsigned char *ip;

    size_t t, next;

    size_t state = 0;

    const unsigned char *m_pos;

    const unsigned char * const ip_end = in + in_len;

    unsigned char * const op_end = out + *out_len;

    op = out;

    ip = in;

    if (unlikely(in_len < 3))

        goto input_overrun;

    if (*ip > 17) {

        t = *ip++ - 17;

        if (t < 4) {

            next = t;

            goto match_next;

        }

        goto copy_literal_run;

    }

    for (;;) {

        t = *ip++;

        if (t < 16) {

            if (likely(state == 0)) {

                if (unlikely(t == 0)) {

                    size_t offset;

                    const unsigned char *ip_last = ip;

                    while (unlikely(*ip == 0)) {

                        ip++;

                        NEED_IP(1);

                    }

                    offset = ip - ip_last;

                    if (unlikely(offset > MAX_255_COUNT))

                        return LZO_E_ERROR;

                    offset = (offset << 8) - offset;

                    t += offset + 15 + *ip++;

                }

                t += 3;

 copy_literal_run:

#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)

                if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) {

                    const unsigned char *ie = ip + t;

                    unsigned char *oe = op + t;

                    do {

                        COPY8(op, ip);

                        op += 8;

                        ip += 8;

                        COPY8(op, ip);

                        op += 8;

                        ip += 8;

                    } while (ip < ie);

                    ip = ie;

                    op = oe;

                } else

#endif

                {

                    NEED_OP(t);

                    NEED_IP(t + 3);

                    do {

                        *op++ = *ip++;

                    } while (--t > 0);

                }

                state = 4;

                continue;

            } else if (state != 4) {

                next = t & 3;

                m_pos = op - 1;

                m_pos -= t >> 2;

                m_pos -= *ip++ << 2;

                TEST_LB(m_pos);

                NEED_OP(2);

                op[0] = m_pos[0];

                op[1] = m_pos[1];

                op += 2;

                goto match_next;

            } else {

                next = t & 3;

                m_pos = op - (1 + M2_MAX_OFFSET);

                m_pos -= t >> 2;

                m_pos -= *ip++ << 2;

                t = 3;

            }

        } else if (t >= 64) {

            next = t & 3;

            m_pos = op - 1;

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

            m_pos -= *ip++ << 3;

            t = (t >> 5) - 1 + (3 - 1);

        } else if (t >= 32) {

            t = (t & 31) + (3 - 1);

            if (unlikely(t == 2)) {

                size_t offset;

                const unsigned char *ip_last = ip;

                while (unlikely(*ip == 0)) {

                    ip++;

                    NEED_IP(1);

                }

                offset = ip - ip_last;

                if (unlikely(offset > MAX_255_COUNT))

                    return LZO_E_ERROR;

                offset = (offset << 8) - offset;

                t += offset + 31 + *ip++;

                NEED_IP(2);

            }

            m_pos = op - 1;

            next = get_unaligned_le16(ip);

            ip += 2;

            m_pos -= next >> 2;

            next &= 3;

        } else {

            m_pos = op;

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

            t = (t & 7) + (3 - 1);

            if (unlikely(t == 2)) {

                size_t offset;

                const unsigned char *ip_last = ip;

                while (unlikely(*ip == 0)) {

                    ip++;

                    NEED_IP(1);

                }

                offset = ip - ip_last;

                if (unlikely(offset > MAX_255_COUNT))

                    return LZO_E_ERROR;

                offset = (offset << 8) - offset;

                t += offset + 7 + *ip++;

                NEED_IP(2);

            }

            next = get_unaligned_le16(ip);

            ip += 2;

            m_pos -= next >> 2;

            next &= 3;

            if (m_pos == op)

                goto eof_found;

            m_pos -= 0x4000;

        }

        TEST_LB(m_pos);

#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)

        if (op - m_pos >= 8) {

            unsigned char *oe = op + t;

            if (likely(HAVE_OP(t + 15))) {

                do {

                    COPY8(op, m_pos);

                    op += 8;

                    m_pos += 8;

                    COPY8(op, m_pos);

                    op += 8;

                    m_pos += 8;

                } while (op < oe);

                op = oe;

                if (HAVE_IP(6)) {

                    state = next;

                    COPY4(op, ip);

                    op += next;

                    ip += next;

                    continue;

                }

            } else {

                NEED_OP(t);

                do {

                    *op++ = *m_pos++;

                } while (op < oe);

            }

        } else

#endif

        {

            unsigned char *oe = op + t;

            NEED_OP(t);

            op[0] = m_pos[0];

            op[1] = m_pos[1];

            op += 2;

            m_pos += 2;

            do {

                *op++ = *m_pos++;

            } while (op < oe);

        }

        match_next:

        state = next;

        t = next;

#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)

        if (likely(HAVE_IP(6) && HAVE_OP(4))) {

            COPY4(op, ip);

            op += t;

            ip += t;

        } else

#endif

        {

            NEED_IP(t + 3);

            NEED_OP(t);

            while (t > 0) {

                *op++ = *ip++;

                t--;

            }

        }

    }

 eof_found:

    *out_len = op - out;

    return (t != 3       ? LZO_E_ERROR :

            ip == ip_end ? LZO_E_OK :

            ip <  ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN);

 input_overrun:

    *out_len = op - out;

    return LZO_E_INPUT_OVERRUN;

 output_overrun:

    *out_len = op - out;

    return LZO_E_OUTPUT_OVERRUN;

 lookbehind_overrun:

    *out_len = op - out;

    return LZO_E_LOOKBEHIND_OVERRUN;

}