/*-
 * Copyright 2020 chenkang
 * All rights reserved
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted providing that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */



#include "lzzip.h"
#include "bsdiff.h"
#include <string.h>
#include <masterthread.h>
#include <QObject>
#include <QDebug>

#define H(key)  (((((*key) << 8) | *(key + 1))) & (HASH_SIZE - 1))
#define HASH_SIZE (1 << 16)


int LZzip(MasterThread *func_owner, uint8_t *in_data, off_t indata_len, off_t newfile_len, uint8_t *out_data, off_t *outdata_len, int zip_flag)
{
    uint8_t waitzip_buf[255];
    off_t waitzipbuf_len;
    off_t indata_pos;
    off_t last_indata_pos;
    off_t outdata_pos;
    off_t IndexData_Len;
    off_t INDEXPOS_DIVISION1, INDEXPOS_DIVISION2, INDEXPOS_DIVISION3, INDEXPOS_DIVISION4;
    off_t MATCH_DIVISION1, MATCH_DIVISION2, MATCH_DIVISION3, MATCH_DIVISION4;

    hash_list *htab;
    hash_list *hsearch, *htemp;

    INDEXPOS_DIVISION1 = 64;
    MATCH_DIVISION1 = 3;
    INDEXPOS_DIVISION2 = 1 << (zip_flag / 2 + 10);
    MATCH_DIVISION2 = (1 << (4 - zip_flag / 2)) + 2;
    INDEXPOS_DIVISION3 = 1 << (10 + zip_flag);
    MATCH_DIVISION3 = (1 << (10 - zip_flag)) + 3;
    INDEXPOS_DIVISION4 = 1 << (10 + zip_flag);
    MATCH_DIVISION4 = (1 << (18 - zip_flag)) + 4;

    const off_t IndexMax_Len = 1<< (10 + zip_flag);


    /*初始化哈希表*/
    htab = new hash_list [HASH_SIZE];
    memset(htab, 0, HASH_SIZE * sizeof(hash_list));

    indata_pos = 0;
    last_indata_pos = 0;
    IndexData_Len = 0;
    waitzipbuf_len = 0;
    outdata_pos = 0;

    outdata_pos += 8;
    out_data[outdata_pos++] = zip_flag;
    out_data[outdata_pos++] = in_data[indata_pos++];
    if((++IndexData_Len) > IndexMax_Len){
        IndexData_Len = IndexMax_Len;
    }


    while(indata_pos < indata_len - 1){
        off_t MaxIndex_Pos = 0;
        off_t MaxMatch_Len = 0;
        if((last_indata_pos / (indata_len / 50)) != (indata_pos / (indata_len / 50))){
            emit func_owner->Complete_Rate(50 + indata_pos / (indata_len / 50));
        }
        last_indata_pos = indata_pos;
        /*更新哈希表*/
//        if(addmatch_len > IndexMax_Len){
//            ip = &in_data[indata_pos] - IndexMax_Len;
//            addmatch_len = IndexMax_Len;
//        }
//        while(addmatch_len--){
//            hash_index = H(ip);
//            hsearch = &htab[hash_index];
//            if(hsearch->next){
//                if(&in_data[indata_pos] - hsearch->next->anchor > IndexMax_Len){
//                    hsearch->next->anchor = ip;
//                }
//                else{
//                    htemp = new hash_list;
//                    htemp->anchor = ip;
//                    htemp->next = hsearch->next;
//                    htemp->prev = hsearch;
//                    htemp->next->prev = htemp;
//                    hsearch->next = htemp;
//                }
//            }
//            else{
//                htemp = new hash_list;
//                htemp->anchor = ip;
//                htemp->next = NULL;
//                htemp->prev = hsearch;
//                hsearch->next = htemp;
//            }
//            ip++;

//        }

        /*寻找匹配*/
        hsearch = htab[H(&in_data[indata_pos])].next;
        while(hsearch){
            uint8_t *match_ip, *in_dataip;
            off_t Match_Len = 2;

            if(&in_data[indata_pos] - hsearch->anchor > IndexMax_Len){
                hsearch->prev->next = NULL;
                do{
                    htab[H(&in_data[indata_pos])].len--;
                    htemp = hsearch;
                    hsearch= hsearch->next;
                    delete htemp;
                }while(hsearch);
                continue;
            }
            match_ip = hsearch->anchor + 2;
            in_dataip = &in_data[indata_pos] + 2;
            while(in_dataip < (in_data + indata_len) && (*match_ip) == (*in_dataip)){
                Match_Len++;
                if(Match_Len >= MATCH_DIVISION4)
                    break;
                match_ip++;
                in_dataip++;
            }
            if((Match_Len > MaxMatch_Len)){
                MaxMatch_Len = Match_Len;
                MaxIndex_Pos = in_dataip - match_ip - 1;
            }
            hsearch = hsearch->next;
        }

        if(1){
            htemp = new hash_list;
            htemp->anchor = &in_data[indata_pos];
            htemp->next = htab[H(&in_data[indata_pos])].next;
            htab[H(&in_data[indata_pos])].next = htemp;
            htemp->prev = &htab[H(&in_data[indata_pos])];
            if(htemp->next)
                htemp->next->prev = htemp;
            htab[H(&in_data[indata_pos])].len++;
        }

        if(MaxMatch_Len <= 1){
            waitzip_buf[waitzipbuf_len++] = in_data[indata_pos++];
            if((++IndexData_Len) > IndexMax_Len){
                IndexData_Len = IndexMax_Len;
            }
            if(waitzipbuf_len >= 16){
                out_data[outdata_pos++] = (waitzipbuf_len - 1) | 0xf0;
                for(off_t i = 0; i < waitzipbuf_len; i++)
                    out_data[outdata_pos++] = waitzip_buf[i];
                waitzipbuf_len = 0;
            }
        }
        else if((MaxMatch_Len <= MATCH_DIVISION1) && (MaxIndex_Pos < INDEXPOS_DIVISION1)){
            if(waitzipbuf_len > 0){
                out_data[outdata_pos++] = (waitzipbuf_len - 1) | 0xf0;
                for(off_t i = 0; i < waitzipbuf_len; i++)
                    out_data[outdata_pos++] = waitzip_buf[i];
                waitzipbuf_len = 0;
            }
            indata_pos += MaxMatch_Len;
            if((IndexData_Len + MaxMatch_Len) > IndexMax_Len){
                IndexData_Len = IndexMax_Len;
            }
            else{
                IndexData_Len += MaxMatch_Len;
            }

            MaxMatch_Len = (MaxIndex_Pos << 1) | (MaxMatch_Len - 2);
            out_data[outdata_pos++] = MaxMatch_Len;
        }
        else if((MaxMatch_Len <= 2) && (MaxIndex_Pos >= INDEXPOS_DIVISION1)){
            waitzip_buf[waitzipbuf_len++] = in_data[indata_pos++];
            if((++IndexData_Len) > IndexMax_Len){
                IndexData_Len = IndexMax_Len;
            }
            if(waitzipbuf_len >= 16){
                out_data[outdata_pos++] = (waitzipbuf_len - 1) | 0xf0;
                for(off_t i = 0; i < waitzipbuf_len; i++)
                    out_data[outdata_pos++] = waitzip_buf[i];
                waitzipbuf_len = 0;
            }
        }
        else if((MaxMatch_Len <= MATCH_DIVISION2) && (MaxIndex_Pos < INDEXPOS_DIVISION2)){
            if(waitzipbuf_len > 0){
                out_data[outdata_pos++] = (waitzipbuf_len - 1) | 0xf0;
                for(off_t i = 0; i < waitzipbuf_len; i++)
                    out_data[outdata_pos++] = waitzip_buf[i];
                waitzipbuf_len = 0;
            }
            indata_pos += MaxMatch_Len;
            if((IndexData_Len + MaxMatch_Len) > IndexMax_Len){
                IndexData_Len = IndexMax_Len;
            }
            else{
                IndexData_Len += MaxMatch_Len;
            }

            switch(INDEXPOS_DIVISION2){
            case 1 << 10:
                MaxMatch_Len = (MaxIndex_Pos << 4) | (MaxMatch_Len - 3) | (1 << 15);
                break;
            case 1 << 11:
                MaxMatch_Len = (MaxIndex_Pos << 3) | (MaxMatch_Len - 3) | (1 << 15);
                break;
            case 1 << 12:
                MaxMatch_Len = (MaxIndex_Pos << 2) | (MaxMatch_Len - 3) | (1 << 15);
                break;
            default:
                break;
            }
            out_data[outdata_pos++] = (MaxMatch_Len >> 8) & 0xff;                                    //控制数据中高位位于低地址，低位位于高地址
            out_data[outdata_pos++] = MaxMatch_Len & 0xff;
        }
        else if((MaxMatch_Len <= 3) && (MaxIndex_Pos >= INDEXPOS_DIVISION2)){
            waitzip_buf[waitzipbuf_len++] = in_data[indata_pos++];
            if((++IndexData_Len) > IndexMax_Len){
                IndexData_Len = IndexMax_Len;
            }
            if(waitzipbuf_len >= 16){
                out_data[outdata_pos++] = (waitzipbuf_len - 1) | 0xf0;
                for(off_t i = 0; i < waitzipbuf_len; i++)
                    out_data[outdata_pos++] = waitzip_buf[i];
                waitzipbuf_len = 0;
            }
        }
        else if((MaxMatch_Len <= MATCH_DIVISION3) && (MaxIndex_Pos < INDEXPOS_DIVISION3)){
            if(waitzipbuf_len > 0){
                out_data[outdata_pos++] = (waitzipbuf_len - 1) | 0xf0;
                for(off_t i = 0; i < waitzipbuf_len; i++)
                    out_data[outdata_pos++] = waitzip_buf[i];
                waitzipbuf_len = 0;
            }
            indata_pos += MaxMatch_Len;
            if((IndexData_Len + MaxMatch_Len) > IndexMax_Len){
                IndexData_Len = IndexMax_Len;
            }
            else{
                IndexData_Len += MaxMatch_Len;
            }

            switch(INDEXPOS_DIVISION3){
            case 1 << 10:
                MaxMatch_Len = (MaxIndex_Pos << 10) | (MaxMatch_Len - 4) | (3 << 22);
                break;
            case 1 << 11:
                MaxMatch_Len = (MaxIndex_Pos << 9) | (MaxMatch_Len - 4) | (3 << 22);
                break;
            case 1 << 12:
                MaxMatch_Len = (MaxIndex_Pos << 8) | (MaxMatch_Len - 4) | (3 << 22);
                break;
            case 1 << 13:
                MaxMatch_Len = (MaxIndex_Pos << 7) | (MaxMatch_Len - 4) | (3 << 22);
                break;
            case 1 << 14:
                MaxMatch_Len = (MaxIndex_Pos << 6) | (MaxMatch_Len - 4) | (3 << 22);
                break;
            case 1 << 15:
                MaxMatch_Len = (MaxIndex_Pos << 5) | (MaxMatch_Len - 4) | (3 << 22);
                break;
            default:
                break;
            }
            out_data[outdata_pos++] = (MaxMatch_Len >> 16) & 0xff;
            out_data[outdata_pos++] = (MaxMatch_Len >> 8) & 0xff;
            out_data[outdata_pos++] = MaxMatch_Len & 0xff;
        }
        else if((MaxMatch_Len <= 4) && (MaxIndex_Pos >= INDEXPOS_DIVISION3)){
            waitzip_buf[waitzipbuf_len++] = in_data[indata_pos++];
            if((++IndexData_Len) > IndexMax_Len){
                IndexData_Len = IndexMax_Len;
            }
            if(waitzipbuf_len >= 16){
                out_data[outdata_pos++] = (waitzipbuf_len - 1) | 0xf0;
                for(off_t i = 0; i < waitzipbuf_len; i++)
                    out_data[outdata_pos++] = waitzip_buf[i];
                waitzipbuf_len = 0;
            }
        }
        else{
            if(waitzipbuf_len > 0){
                out_data[outdata_pos++] = (waitzipbuf_len - 1) | 0xf0;
                for(off_t i = 0; i < waitzipbuf_len; i++)
                    out_data[outdata_pos++] = waitzip_buf[i];
                waitzipbuf_len = 0;
            }
            indata_pos += MaxMatch_Len;
            if((IndexData_Len + MaxMatch_Len) > IndexMax_Len){
                IndexData_Len = IndexMax_Len;
            }
            else{
                IndexData_Len += MaxMatch_Len;
            }
            switch(INDEXPOS_DIVISION4){
            case 1 << 10:
                MaxMatch_Len = (MaxIndex_Pos << 18) | (MaxMatch_Len - 5) | (7 << 29);
                break;
            case 1 << 11:
                MaxMatch_Len = (MaxIndex_Pos << 17) | (MaxMatch_Len - 5) | (7 << 29);
                break;
            case 1 << 12:
                MaxMatch_Len = (MaxIndex_Pos << 16) | (MaxMatch_Len - 5) | (7 << 29);
                break;
            case 1 << 13:
                MaxMatch_Len = (MaxIndex_Pos << 15) | (MaxMatch_Len - 5) | (7 << 29);
                break;
            case 1 << 14:
                MaxMatch_Len = (MaxIndex_Pos << 14) | (MaxMatch_Len - 5) | (7 << 29);
                break;
            case 1 << 15:
                MaxMatch_Len = (MaxIndex_Pos << 13) | (MaxMatch_Len - 5) | (7 << 29);
                break;
            default:
                break;
            }
            out_data[outdata_pos++] = (MaxMatch_Len >> 24) & 0xff;
            out_data[outdata_pos++] = (MaxMatch_Len >> 16) & 0xff;
            out_data[outdata_pos++] = (MaxMatch_Len >> 8) & 0xff;
            out_data[outdata_pos++] = MaxMatch_Len & 0xff;
        }
    }
    if(indata_pos == indata_len - 1){
        waitzip_buf[waitzipbuf_len++] = in_data[indata_pos++];
    }
    if(waitzipbuf_len){
        out_data[outdata_pos++] = (waitzipbuf_len - 1) | 0xf0;
        for(off_t i = 0; i < waitzipbuf_len; i++)
            out_data[outdata_pos++] = waitzip_buf[i];
        waitzipbuf_len = 0;
    }

    *outdata_len = outdata_pos;
    out_data [4] = newfile_len & 0xff;
    out_data [5] = (newfile_len >> 8) & 0xff;
    out_data [6] = (newfile_len >> 16) & 0xff;
    out_data [7] = (newfile_len >> 24) & 0xff;


    for(int i = 0; i < HASH_SIZE; i++){
        hsearch = htab[i].next;
        while(hsearch){
            htemp = hsearch;
            hsearch = hsearch->next;
            delete htemp;
        }
    }


    return outdata_pos;
}