#include "Shrinker.h"

#if defined(_MSC_VER)
typedef unsigned __int8 u8;
typedef unsigned __int16 u16;
typedef unsigned __int32 u32;
typedef unsigned __int64 u64;
#else
#include <stdint.h>
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
#endif

//the code from LZ4
#if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
# define expect(expr,value)    (__builtin_expect ((expr),(value)) )
#else
# define expect(expr,value)    (expr)
#endif
#define likely(expr)     expect((expr) != 0, 1)
#define unlikely(expr)   expect((expr) != 0, 0)
////////////////////

#define HASH_BITS 15
#define HASH(a) ((a*21788233) >> (32 - HASH_BITS))
#define MINMATCH 4

#include <limits.h>
#if ULONG_MAX == UINT_MAX //32bit
#define MEMCPY_NOOVERLAP(a, b, c) do{do{*(u32*)a = *(u32*)b;a+=4;b+=4;}while(b<c);a-=(b-c);b=c;}while(0)
#define MEMCPY_NOOVERLAP_NOSURPASS(a, b, c) do{c-=4;while(b<c){*(u32*)(a) = *(u32*)(b);a+=4;b+=4;}c+=4;while(b<c)*a++=*b++;}while(0)
#define MEMCPY(a, b, c) do{if (likely(a>b+4)) MEMCPY_NOOVERLAP(a, b, c); else while(b<c) *a++=*b++;}while(0)
#else
#define MEMCPY_NOOVERLAP(a, b, c) do{do{*(u64*)a = *(u64*)b;a+=8;b+=8;}while(b<c);a-=(b-c);b=c;}while(0)
#define MEMCPY_NOOVERLAP_NOSURPASS(a, b, c) do{c-=8;while(b<c){*(u64*)(a) = *(u64*)(b);a+=8;b+=8;}c+=8;while(b<c)*a++=*b++;}while(0)
#define MEMCPY(a, b, c) do{if (likely(a>b+8)) MEMCPY_NOOVERLAP(a, b, c); else while(b<c) *a++=*b++;}while(0)
#endif

int shrinker_compress(void *in, void *out, int size)
{
    u32 ht[(1<<HASH_BITS)];
    u8 *src = (u8*)in, *dst = (u8*)out;
    u8 *src_end = src + size - MINMATCH - 8;
    u8 *dst_end = dst + size - MINMATCH - 8;
    u8 *pfind, *pcur;

    u32 cur_hash;
    u8  *p_last_lit = src;
    u32 cpy_len, match_dist;
    u8 flag, *pflag, cache;
    u32 cur_u32;

    if (size < 32) return -1;
    if (size > (1 << 27) - 1) return -1;

    cur_u32 = *(u32*)src;
    while(likely(src < src_end) && likely(dst < dst_end))
    {
        u32 tmp = src - (u8*)in;
        pcur = src;
        cur_u32 = *(u32*)pcur;
        cur_hash = HASH(cur_u32);
        cache = ht[cur_hash] >> 27;
        pfind = (u8*)in + (ht[cur_hash] & 0x07ffffff);
        ht[cur_hash] = tmp|(*src<<27);

        if (unlikely(cache == (*pcur & 0x1f))
            && pfind + 0xffff >= (u8*)pcur
            && pfind < pcur
            &&*(u32*)pfind == *(u32*)pcur) 
        {  
            pfind += 4; pcur += 4;
            while(likely(pcur < src_end) && *(u32*)pfind == *(u32*)pcur)
            { pfind += 4; pcur += 4;}

            if (likely(pcur < src_end))
            if (*(u16*)pfind == *(u16*)pcur) {pfind += 2; pcur += 2;}
            if (*pfind == *pcur) {pfind++; pcur++;}

            pflag = dst++;
            cpy_len = src - p_last_lit;
            if (likely(cpy_len < 7)) flag = cpy_len << 5;
            else {
                cpy_len -= 7;flag = (7<<5);
                while (cpy_len >= 255)
                { *dst++ = 255;cpy_len -= 255;}
                *dst++ = cpy_len;
            }

            cpy_len = pcur - src  - MINMATCH;
            if (likely(cpy_len < 15))  flag |= cpy_len;
            else {
                cpy_len -= 15; flag |= 15;
                while (cpy_len >= 255)
                { *dst++ = 255;cpy_len -= 255;}
                *dst++ = cpy_len;
            }
            match_dist = pcur - pfind - 1;
            *pflag = flag;
            *dst++ = match_dist & 0xff;
            if (match_dist > 0xff) {
                *pflag |= 16;
                *dst++ = match_dist >> 8;
            }
            MEMCPY_NOOVERLAP(dst, p_last_lit, src);

            cur_u32 = *(u32*)(src+1);
            ht[HASH(cur_u32)] = (src - (u8*)in + 1)|(*(src+1)<<27);
            cur_u32 = *(u32*)(src+3);
            ht[HASH(cur_u32)] = (src - (u8*)in + 3)|(*(src+3)<<27);
            src = pcur;
            p_last_lit = src;
            continue;
        }
        src++;
    }


    if (dst - (u8*)out + 3 >= src - (u8*)in) return -1;
    src = (u8*)in + size;
    pflag = dst++;
    cpy_len = src - p_last_lit;
    if (likely(cpy_len < 7)) flag = cpy_len << 5;
    else {
        cpy_len -= 7; flag = (7<<5);
        while (cpy_len >= 255)
        { *dst++ = 255; cpy_len -= 255;}
        *dst++ = cpy_len;
    }

    flag |= 7 + 16; // any number
    *pflag = flag;
    *dst++ = 0xff; *dst++ = 0xff;
    MEMCPY_NOOVERLAP_NOSURPASS(dst, p_last_lit, src);

    if (dst > dst_end) return -1;
    else return dst - (u8*)out;
}



int shrinker_decompress(void *in, void *out, int size)
{
    u8 *src = (u8*)in, *dst = (u8*)out;
    u8 *end = dst + size;
    u8 *pcpy, *pend;
    u8 flag, long_dist;
    u32 literal_len;
    u32 match_len, match_dist;

    for(;;) {
        flag = *src++;
        literal_len = flag >> 5;
        match_len = flag & 0xf;
        long_dist = flag & 0x10;

        if (unlikely(literal_len == 7)) {
            while((flag = *src++) == 255)
                literal_len += 255;
            literal_len += flag;
        }

        if (unlikely(match_len == 15)) {
            while((flag = *src++) == 255)
                match_len += 255;
            match_len += flag;
        }

        match_dist = *src++;
        if (long_dist) 
        {
            match_dist |= ((*src++) << 8);
            if (unlikely(match_dist == 0xffff)) {
                pend = src + literal_len;
                if (unlikely(dst + literal_len > end)) return -1;
                MEMCPY_NOOVERLAP_NOSURPASS(dst, src, pend);
                break;
            }
        }

        pend = src + literal_len;
        if (unlikely(dst + literal_len > end)) return -1;
        MEMCPY_NOOVERLAP(dst, src, pend);
        pcpy = dst - match_dist - 1;
        pend = pcpy + match_len + MINMATCH;
        if (unlikely(pcpy < (u8*)out || dst + match_len + MINMATCH > end)) return -1;
        MEMCPY(dst, pcpy, pend);
    }
    return dst - (u8*)out;
}