// modified by Luigi Auriemma

// (c) Bulat Ziganshin <Bulat.Ziganshin@gmail.com>
// (c) Joachim Henke
// GPL'ed code of Tornado - fast LZ77 compression algorithm.
#include "Compression.h"
#include "MatchFinder.cpp"
#include "EntropyCoder.cpp"
#include "LZ77_Coder.cpp"
#include "DataTables.cpp"

// Compression method parameters
struct PackMethod
{
    int  number;            // Preset number
    int  encoding_method;   // Coder (0 - storing, 1 - bytecoder, 2 - bitcoder, 3 - huffman, 4 - arithmetic)
    bool find_tables;       // Enable searching for MM tables
    int  hash_row_width;    // Length of hash row
    uint hashsize;          // Hash size
    int  caching_finder;    // Force/prohibit using caching match finder
    uint buffer;            // Buffer (dictionary) size
    int  match_parser;      // Match parser (1 - greedy, 2 - lazy, 3 - flexible, 4 - optimal, 5 - even better)
    int  hash3;             // 2/3-byte hash presence and type
    int  shift;             // How much bytes to shift out/keep when window slides
    int  update_step;       // How much bytes are skipped in mf.update()
    uint auxhash_size;      // Auxiliary hash size
    int  auxhash_row_width; // Length of auxiliary hash row
};

extern "C" {
// Main compression and decompression routines
int tor_compress   (PackMethod m, CALLBACK_FUNC *callback, void *auxdata);
int tor_decompress (CALLBACK_FUNC *callback, void *auxdata);
}

enum { STORING=0, BYTECODER=1, BITCODER=2, HUFCODER=3, ARICODER=4, ROLZ_HUFCODER=13 };
enum { GREEDY=1, LAZY=2 };

// Preconfigured compression modes
PackMethod std_Tornado_method[] =
    //                 tables row  hashsize  caching buffer parser  hash3 shift update   auxhash
    { {  0, STORING,   false,   0,        0, 0,      1*mb,  0     ,   0,    0,  999,       0,    0 }
    , {  1, BYTECODER, false,   1,    16*kb, 0,      1*mb,  GREEDY,   0,    0,  999,       0,    0 }
    , {  2, BITCODER,  false,   1,    64*kb, 0,      2*mb,  GREEDY,   0,    0,  999,       0,    0 }
    , {  3, HUFCODER,  true,    2,   128*kb, 0,      4*mb,  GREEDY,   0,    0,  999,       0,    0 }
    , {  4, HUFCODER,  true,    2,     2*mb, 1,      8*mb,  GREEDY,   0,    0,  999,       0,    0 }
    , {  5, ARICODER,  true,    4,     8*mb, 1,     16*mb,  LAZY  ,   1,    0,  999,       0,    0 }
    , {  6, ARICODER,  true,    8,    32*mb, 1,     64*mb,  LAZY  ,   1,    0,    4,       0,    0 }
    , {  7, ARICODER,  true,   32,   128*mb, 5,    256*mb,  LAZY  ,   2,    0,    1,  128*kb,    4 }
    , {  8, ARICODER,  true,  128,   512*mb, 5,   1024*mb,  LAZY  ,   2,    0,    1,  128*kb,    4 }
    , {  9, ARICODER,  true,  256,  2048*mb, 5,   1024*mb,  LAZY  ,   2,    0,    1,  512*kb,    4 }
    , { 10, ARICODER,  true,  256,  2048*mb, 6,   1024*mb,  LAZY  ,   2,    0,    1,    2*mb,   32 }
    , { 11, ARICODER,  true,  200,  1600*mb, 7,   1024*mb,  LAZY  ,   2,    0,    1,  512*mb,  256 }
    };

// Default compression parameters are equivalent to option -5
const int default_Tornado_method = 5;

// If data table was not encountered in last table_dist bytes, don't check next table_shift bytes in order to make things faster
const int table_dist=256*1024, table_shift=128;

// Minimum lookahead for next match which compressor tries to guarantee.
// Also minimum amount of allocated space after end of buf (this allows to use things like p[11] without additional checks)
#define LOOKAHEAD 256


// Округлим размер хеша с учётом hash_row_width
uint round_to_nearest_hashsize (LongMemSize hashsize, uint hash_row_width)
{return mymin (round_to_nearest_power_of(mymin(hashsize,2*gb-1) / hash_row_width, 2) * hash_row_width, 2*gb-1);}

// Dictionary size depending on memory available for dictionary+outbuf (opposite to tornado_compressor_outbuf_size)
uint tornado_compressor_calc_dict (uint mem)
{return compress_all_at_once?  mem/9*4
                            :  mem>2*LARGE_BUFFER_SIZE ? mem-LARGE_BUFFER_SIZE : mem/2;}

// Output buffer size for compressor (the worst case is bytecoder that adds 2 bits per byte on incompressible data)
uint tornado_compressor_outbuf_size (uint buffer, int bytes_to_compress = -1)
{return bytes_to_compress!=-1? bytes_to_compress+(bytes_to_compress/4)+512 :
        compress_all_at_once?  buffer+(buffer/4)+512 :
                               mymin (buffer+512, LARGE_BUFFER_SIZE);}

// Output buffer size for decompressor
uint tornado_decompressor_outbuf_size (uint buffer)
{return compress_all_at_once?  buffer+(buffer/8)+512 :
                               mymax (buffer, LARGE_BUFFER_SIZE);}

#define BUF_SIZE (16*mb)

const int ROLZ_EOF_CODE=256;  // code used to indicate EOF (the same as match with length 0)
const int MATCH_SIZE=64;
const int ENTRIES2 = 64*kb, ROW_SIZE2=4, BASE2=0;
const int ENTRIES3 =  0*kb, ROW_SIZE3=0, BASE3=ENTRIES2*ROW_SIZE2;
const int ENTRIES4 =  0*kb, ROW_SIZE4=0, BASE4=ENTRIES3*ROW_SIZE3+BASE3;
const int TOTAL_ENTRIES = ENTRIES2*ROW_SIZE2 + ENTRIES3*ROW_SIZE3 + ENTRIES4*ROW_SIZE4;
const int MINLEN=1;
inline uint rolz_hashing(BYTE *p, int BYTES, int ENTRIES)
{
    return ENTRIES>=64*kb && BYTES==2?   *(uint16*)(p-BYTES)
         : ENTRIES>=256   && BYTES==1?   *(uint8*) (p-BYTES)
         : ((*(uint*)(p-BYTES) & (((1<<BYTES)<<(BYTES*7))-1)) * 123456791) / (gb/(ENTRIES/4));
}

#define HUFFMAN_TREES                          520
#define HUFFMAN_ELEMS                          (256+(ROW_SIZE2+ROW_SIZE3+ROW_SIZE4)*MATCH_SIZE)
#define ROLZ_ENCODE_DIRECT(context, symbol)    coder.encode(context, symbol)

// Save match to buffer, encoding performed in another thread
#define ROLZ_ENCODE(context, symbol)    (*x++ = ((context)<<16) + (symbol))
// Do actual encode of data item saved in buffer
#define ROLZ_ENCODE2(data)              ROLZ_ENCODE_DIRECT((data)>>16, (data)&0xFFFF)

struct  entry {BYTE *ptr; uint32 cache;};
static  entry hash [TOTAL_ENTRIES];

struct Buffers {uint32 *x0;  int bufsize;};
                               
int tor_decompress0_rolz (CALLBACK_FUNC *callback, void *auxdata)
{
    int errcode = FREEARC_OK;                             // Error code of last "write" call
    zeroArray(hash);
    static HuffmanDecoderOrder1 <HUFFMAN_TREES, HUFFMAN_ELEMS>   decoder (callback, auxdata, BUF_SIZE, HUFFMAN_ELEMS+1);
    if (decoder.error() != FREEARC_OK)  return decoder.error();
    BYTE  buf[BUF_SIZE+MATCH_SIZE],  *p=buf,  last_char=0;
    BYTE *cycle_h[MATCH_SIZE],  dummy[MATCH_SIZE];  iterate(MATCH_SIZE, cycle_h[i] = dummy);  int i=0;
    static BYTE *hash_ptr[TOTAL_ENTRIES];

    for (;;)
    {
        uint idx = rolz_hashing(p,3,ENTRIES3);         // ROLZ entry
        entry *h = &hash[idx];

        uint c = decoder.decode(last_char);
        if (c < 256) {
            *p++ = c;
        } else if (c==ROLZ_EOF_CODE) {
            break;
        } else {
            BYTE *match  =  hash_ptr[idx] >= p-MATCH_SIZE? hash_ptr[idx] : (BYTE *)&h[0];
            int len      = c-256;
            do   *p++ = *match++;
            while (--len);
        }

        // Save match bytes to ROLZ hash (со сдвигом на 16 матчей назад поскольку байты не сразу появляются ;)
        memcpy (cycle_h[i], p, MATCH_SIZE);
        hash_ptr[idx] = p;         // после WRITE станет некорректным, нужен hash_ptr_level показываюзий сколько вхождений данного idx сейчас содержится в cycle_h
        cycle_h[i]    = (BYTE *)&h[0];
        i = (i+1) % MATCH_SIZE;

        // Save context for order-1 coder and flush buffer if required
        last_char = p[-1];
        if (p-buf >= BUF_SIZE)
            {WRITE (buf, BUF_SIZE);  p=buf;}
    }
    WRITE (buf, p-buf);            // Flush outbuf
finished:
    return errcode;
}

// LZ77 decompressor ******************************************************************************

// If condition is true, write data to outstream
#define WRITE_DATA_IF(condition)                                                                  \
{                                                                                                 \
    if (condition) {                                                                              \
        if (decoder.error() != FREEARC_OK)  goto finished;                                        \
        tables.undiff_tables (write_start, output);                                               \
        debug (printf ("==== write %08x:%x ====\n", write_start-outbuf+offset, output-write_start)); \
        WRITE (write_start, output-write_start);                                                  \
        tables.diff_tables (write_start, output);                                                 \
        write_start = output;  /* next time we should start writing from this pos */              \
                                                                                                  \
        /* Check that we should shift the output pointer to start of buffer */                    \
        if (output >= outbuf + bufsize) {                                                         \
            offset_overflow |= (offset > (uint64(1) << 63));                                      \
            offset      += output-outbuf;                                                         \
            write_start -= output-outbuf;                                                         \
            write_end   -= output-outbuf;                                                         \
            tables.shift (output,outbuf);                                                         \
            output      -= output-outbuf;  /* output = outbuf; */                                 \
        }                                                                                         \
                                                                                                  \
        /* If we wrote data because write_end was reached (not because */                         \
        /* table list was filled), then set write_end into its next position */                   \
        if (write_start >= write_end) {                                                           \
            /* Set up next write chunk to HUGE_BUFFER_SIZE or until buffer end - whatever is smaller */ \
            write_end = write_start + mymin (outbuf+bufsize-write_start, HUGE_BUFFER_SIZE);       \
        }                                                                                         \
    }                                                                                             \
}


template <class Decoder>
int tor_decompress0 (CALLBACK_FUNC *callback, void *auxdata, int _bufsize, int minlen)
{
    //SET_JMP_POINT (FREEARC_ERRCODE_GENERAL);
    int errcode = FREEARC_OK;                             // Error code of last "write" call
    Decoder decoder (callback, auxdata, _bufsize);        // LZ77 decoder parses raw input bitstream and returns literals&matches
    if (decoder.error() != FREEARC_OK)  return decoder.error();
    uint bufsize = tornado_decompressor_outbuf_size (_bufsize);  // Size of output buffer
    BYTE *outbuf = (byte*) BigAlloc (bufsize+PAD_FOR_TABLES*2);  // Circular buffer for decompressed data
    if (!outbuf)  return FREEARC_ERRCODE_NOT_ENOUGH_MEMORY;
    outbuf += PAD_FOR_TABLES;       // We need at least PAD_FOR_TABLES bytes available before and after outbuf in order to simplify datatables undiffing
    BYTE *output      = outbuf;     // Current position in decompressed data buffer
    BYTE *write_start = outbuf;     // Data up to this point was already writen to outsream
    BYTE *write_end   = outbuf + mymin (bufsize, HUGE_BUFFER_SIZE); // Flush buffer when output pointer reaches this point
    if (compress_all_at_once)  write_end = outbuf + bufsize + 1;    // All data should be written after decompression finished
    uint64 offset = 0;                    // Current outfile position corresponding to beginning of outbuf
    int offset_overflow = 0;              // Flags that offset was overflowed so we can't use it for match checking
    DataTables tables;                    // Info about data tables that should be undiffed
    for (;;) {
        // Check whether next input element is a literal or a match
        if (decoder.is_literal()) {
            // Decode it as a literal
            BYTE c = decoder.getchar();
            print_literal (output-outbuf+offset, c);
            *output++ = c;
            WRITE_DATA_IF (output >= write_end);  // Write next data chunk to outstream if required

        } else {
            // Decode it as a match
            UINT len  = decoder.getlen(minlen);
            UINT dist = decoder.getdist();
            print_match (output-outbuf+offset, len, dist);

            // Check for simple match (i.e. match not requiring any special handling, >99% of matches fall into this category)
            if (output-outbuf>=dist && write_end-output>len) {
                BYTE *p = output-dist;
                do   *output++ = *p++;
                while (--len);

            // Check that it's a proper match
            } else if (len<IMPOSSIBLE_LEN) {
                // Check that compressed data are not broken
                if (dist>bufsize || len>2*_bufsize || (output-outbuf+offset<dist && !offset_overflow))  {errcode=FREEARC_ERRCODE_BAD_COMPRESSED_DATA; goto finished;}
                // Slow match copying route for cases when output-dist points before buffer beginning,
                // or p may wrap at buffer end, or output pointer may run over write point
                BYTE *p  =  output-outbuf>=dist? output-dist : output-dist+bufsize;
                do {
                    *output++ = *p++;
                    if (p==outbuf+bufsize)  p=outbuf;
                    WRITE_DATA_IF (output >= write_end);
                } while (--len);

            // Check for special len/dist code used to encode EOF
            } else if (len==IMPOSSIBLE_LEN && dist==IMPOSSIBLE_DIST) {
                WRITE_DATA_IF (TRUE);  // Flush outbuf
                goto finished;

            // Otherwise it's a special code used to represent info about diffed data tables
            } else {
                len -= IMPOSSIBLE_LEN;
                if (len==0 || dist*len > 2*_bufsize)  {errcode=FREEARC_ERRCODE_BAD_COMPRESSED_DATA; goto finished;}
                stat_only (printf ("\n%d: Start %x, end %x, length %d      ", len, int(output-outbuf+offset), int(output-outbuf+offset+len*dist), len*dist));
                // Add new table to list: len is row length of table and dist is number of rows
                tables.add (len, output, dist);
                // If list of data tables is full then flush it by preprocessing
                // and writing to outstream already filled part of outbuf
                WRITE_DATA_IF (tables.filled() && !compress_all_at_once);
            }
        }
    }
finished:
    BigFree(outbuf-PAD_FOR_TABLES);
    // Return decoder error code, errcode or FREEARC_OK
    return decoder.error() < 0 ?  decoder.error() :
           errcode         < 0 ?  errcode
                               :  FREEARC_OK;
}


int tor_decompress (CALLBACK_FUNC *callback, void *auxdata, void *buf, int bytes_to_compress)
{
    int errcode;
    // First 6 bytes of compressed data are encoding method, minimum match length and buffer size
    BYTE header[2];       READ (header, 2);
   {uint encoding_method = header[0];
    uint minlen          = header[1];
    uint bufsize;         READ4 (bufsize);

    switch (encoding_method) {

    case BYTECODER:
            return tor_decompress0 <LZ77_ByteDecoder> (callback, auxdata, bufsize, minlen);

    case BITCODER:
            return tor_decompress0 <LZ77_BitDecoder>  (callback, auxdata, bufsize, minlen);

    case HUFCODER:
            return tor_decompress0 <LZ77_Decoder <HuffmanDecoder<EOB_CODE> > > (callback, auxdata, bufsize, minlen);

    case ARICODER:
            return tor_decompress0 <LZ77_Decoder <ArithDecoder<EOB_CODE> >   > (callback, auxdata, bufsize, minlen);

    case ROLZ_HUFCODER:
            return tor_decompress0_rolz (callback, auxdata);

    default:
            errcode = FREEARC_ERRCODE_BAD_COMPRESSED_DATA;
    }}
finished: return errcode;
}




int mycallback (const char *what, void *buf, int size, void *r_) {
    static unsigned char    *in     = NULL;
    static unsigned int     insz    = 0;
    static unsigned char    *out    = NULL;
    static unsigned int     outsz   = 0;
    static unsigned char    *out_start    = NULL;
    
    if (strequ(what,"myinit_input")) {
        in = (unsigned char *)buf;
        insz = size;
    } else if (strequ(what,"myinit_output")) {
        out = (unsigned char *)buf;
        outsz = size;
        out_start = out;
    } else if (strequ(what,"myoutput_size")) {
        return out - out_start;
        
    } else if (strequ(what,"read")) {
        if(size > insz) size = insz;
        memcpy(buf, in, size);
        in += size;
        insz -= size;
    } else if (strequ(what,"write") /* || strequ(what,"quasiwrite")*/) {
        if(size > outsz) size = outsz;
        memcpy(out, buf, size);
        out += size;
        outsz -= size;
    }
    return FREEARC_OK;
}

extern "C" int tornado_decompress(unsigned char *in, int insz, unsigned char *out, int outsz) {
    mycallback("myinit_input", in, insz, NULL);
    mycallback("myinit_output", out, outsz, NULL);
    if(tor_decompress(&mycallback, NULL, NULL, 0) != FREEARC_OK) return -1;
    return mycallback("myoutput_size", NULL, 0, NULL);
}


