/*-
 * Copyright 2003-2005 Colin Percival
 * 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 "bsdiff.h"
#include <QDebug>
#include <iostream>
#include <QMessageBox>

#define MIN(x,y) (((x)<(y)) ? (x) : (y))

static void split(off_t *I, off_t *V, off_t start, off_t len, off_t h)
{
    off_t i, j, k, x, tmp, jj, kk;

    if(len < 16) {
        for(k = start; k < start + len; k += j) {
            j = 1;
            x = V[I[k] + h];
            for(i = 1; k + i < start + len; i++) {
                if(V[I[k+i] + h] < x) {
                    x = V[I[k + i] + h];
                    j = 0;
                };
                if(V[I[k + i] + h] == x) {
                    tmp = I[k + j];
                    I[k + j] = I[k + i];
                    I[k + i] = tmp;
                    j++;
                };
            };
            for(i = 0; i < j; i++) V[I[k + i]] = k + j - 1;
            if(j == 1) I[k] = -1;
        };
        return;
    };

    x = V[I[start + len / 2] + h];
    jj = 0;
    kk = 0;
    for(i = start; i < start + len; i++) {
        if(V[I[i] + h] < x) jj++;
        if(V[I[i] + h] == x) kk++;
    };
    jj += start;
    kk += jj;

    i = start;
    j = 0;
    k = 0;
    while(i < jj) {
        if(V[I[i] + h] < x) {
            i++;
        } else if(V[I[i] + h] == x) {
            tmp = I[i];
            I[i] = I[jj + j];
            I[jj + j] = tmp;
            j++;
        } else {
            tmp = I[i];
            I[i] = I[kk + k];
            I[kk + k] = tmp;
            k++;
        };
    };

    while(jj + j < kk) {
        if(V[I[jj + j] + h] == x) {
            j++;
        } else {
            tmp = I[jj + j];
            I[jj + j] = I[kk + k];
            I[kk + k] = tmp;
            k++;
        };
    };

    if(jj > start) split(I, V, start, jj-start, h);

    for(i = 0; i < kk - jj; i++) V[I[jj + i]] = kk - 1;
    if(jj == kk - 1) I[jj] = -1;

    if(start + len > kk) split(I, V, kk, start + len - kk, h);
}

static void qsufsort(off_t *I, off_t *V, uint8_t *old_data, off_t oldsize)
{
    off_t buckets[256];
    off_t i, h, len;

    for(i = 0; i < 256; i++)
        buckets[i]=0;
    for(i = 0; i < oldsize; i++)
        buckets[old_data[i]]++;
    for(i = 1;i < 256; i++)
        buckets[i] += buckets[i-1];
    for(i = 255; i > 0; i--)
        buckets[i] = buckets[i-1];
    buckets[0]=0;

    for(i = 0; i < oldsize; i++) I[++buckets[old_data[i]]] = i;
    I[0] = oldsize;
    for(i = 0; i < oldsize; i++) V[i] = buckets[old_data[i]];
    V[oldsize] = 0;
    for(i = 1; i < 256; i++) if(buckets[i] == buckets[i - 1] + 1)
        I[buckets[i]] = -1;
    I[0]=-1;

    for(h = 1; I[0] != -(oldsize + 1); h += h) {
        len = 0;
        for(i = 0; i < oldsize + 1; ) {
            if(I[i] < 0) {
                len -= I[i];
                i -= I[i];
            } else {
                if(len) I[i - len] = -len;
                len = V[I[i]] + 1 - i;
                split(I, V, i, len, h);
                i += len;
                len = 0;
            };
        };
        if(len) I[i - len] = -len;
    };

    for(i = 0; i < oldsize + 1; i++) I[V[i]] = i;
}

static off_t matchlen(uint8_t *old_data, off_t oldsize, uint8_t *new_data, off_t newsize)
{
    off_t i;

    for(i = 0; (i < oldsize) && (i < newsize); i++)
        if(old_data[i] != new_data[i]) break;

    return i;
}

static off_t search(off_t *I, uint8_t *old_data, off_t oldsize,
        uint8_t *new_data, off_t newsize, off_t st, off_t en, off_t *pos)
{
    off_t x,y;

    if(en - st < 2) {
        x=matchlen(old_data + I[st], oldsize - I[st], new_data, newsize);
        y=matchlen(old_data + I[en], oldsize - I[en], new_data, newsize);

        if(x > y) {
            *pos = I[st];
            return x;
        } else {
            *pos = I[en];
            return y;
        }
    };

    x = st + (en - st) / 2;
    if(memcmp(old_data + I[x], new_data, MIN(oldsize - I[x], newsize)) < 0) {
        return search(I, old_data, oldsize, new_data, newsize, x, en, pos);
    } else {
        return search(I, old_data, oldsize, new_data, newsize, st, x, pos);
    };
}

static void offtout(off_t x,uint8_t *buf)
{
    off_t y = x;


    buf[0] = y % 256; y -= buf[0];
    y = y / 256; buf[1] = y % 256; y -= buf[1];
    y = y / 256; buf[2] = y % 256; y -= buf[2];
    y = y / 256; buf[3] = y % 256; y -= buf[3];

}

int bsdiff(MasterThread *func_owner, uint8_t *old_data, off_t oldsize, uint8_t *new_data,
           off_t newsize, uint8_t *patch_data, off_t *patchdata_size)
{
    off_t *I,*V;
    off_t scan,pos = 0,len;
    off_t lastscan,lastpos,lastoffset;
    off_t oldscore,scsc;
    off_t s,Sf,lenf,Sb,lenb;
    off_t overlap,Ss,lens;
    off_t i;
    off_t patchdata_pos = 0;
    uint8_t ctrl_data;

    /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
        that we never try to malloc(0) and get a NULL pointer */




    if(((I = new off_t[oldsize + 1]) == NULL) ||
        ((V = new off_t[oldsize + 1]) == NULL)){
        QMessageBox msgBox;
        msgBox.setText("内存不足");
        msgBox.exec();

    }

    qsufsort(I, V, old_data, oldsize);

    delete []V;



    scan = 0; len = 0;
    lastscan = 0; lastpos = 0; lastoffset = 0;
    while(scan < newsize) {
        oldscore = 0;

        emit func_owner->Complete_Rate(scan / (newsize / 50));

        for(scsc = scan += len; scan < newsize; scan++) {
            len = search(I, old_data, oldsize, new_data + scan, newsize - scan,
                    0, oldsize, &pos);

            for( ; scsc < scan + len; scsc++)
            if((scsc + lastoffset < oldsize) &&
                (old_data[scsc + lastoffset] == new_data[scsc]))
                oldscore++;

            if(((len == oldscore) && (len != 0)) ||
                (len > oldscore + 8)) break;

            if((scan + lastoffset < oldsize) &&
                (old_data[scan + lastoffset] == new_data[scan]))
                oldscore--;
        };

        if((len != oldscore) || (scan == newsize)) {
            s = 0; Sf = 0; lenf = 0;
            for(i = 0; (lastscan + i < scan) && (lastpos + i < oldsize); ) {
                if(old_data[lastpos + i] == new_data[lastscan + i]) s++;
                i++;
                if(s * 2 - i > Sf * 2 - lenf) { Sf = s; lenf = i; };
            };

            lenb = 0;
            if(scan < newsize) {
                s = 0; Sb = 0;
                for(i = 1; (scan >= lastscan + i) && (pos >= i); i++) {
                    if(old_data[pos - i] == new_data[scan - i]) s++;
                    if(s * 2 - i > Sb * 2 - lenb) { Sb = s; lenb = i; };
                };
            };

            if(lastscan + lenf > scan - lenb) {
                overlap = (lastscan + lenf) - (scan - lenb);
                s = 0; Ss = 0; lens = 0;
                for(i = 0; i < overlap; i++) {
                    if(new_data[lastscan + lenf - overlap + i] ==
                       old_data[lastpos + lenf - overlap + i]) s++;
                    if(new_data[scan - lenb + i] ==
                       old_data[pos - lenb + i]) s--;
                    if(s > Ss) { Ss = s; lens = i + 1; };
                };

                lenf += lens - overlap;
                lenb -= lens;
            };

            uint8_t lastpos_ctrl_len;
            uint8_t diff_ctrl_len;
            uint8_t extra_ctrl_len;

            if(lastpos / (1 << 24)){
                lastpos_ctrl_len = 3;
            }
            else if(lastpos / (1 << 16)){
                lastpos_ctrl_len = 2;
            }
            else if(lastpos / (1 << 8)){
                lastpos_ctrl_len = 1;
            }
            else{
                lastpos_ctrl_len = 0;
            }
            ctrl_data = lastpos_ctrl_len << 6;

            if(lenf / (1 << 24)){
                diff_ctrl_len = 4;
            }
            else if(lenf / (1 << 16)){
                diff_ctrl_len = 3;
            }
            else if(lenf / (1 << 8)){
                diff_ctrl_len = 2;
            }
            else if(lenf > 0){
                diff_ctrl_len = 1;
            }
            else{
                diff_ctrl_len = 0;
            }
            ctrl_data += diff_ctrl_len << 3;

            if(((scan - lenb) - (lastscan + lenf)) / (1 << 24)){
                extra_ctrl_len = 4;
            }
            else if(((scan - lenb) - (lastscan + lenf)) / (1 << 16)){
                extra_ctrl_len = 3;
            }
            else if(((scan - lenb) - (lastscan + lenf)) / (1 << 8)){
                extra_ctrl_len = 2;
            }
            else if(((scan - lenb) - (lastscan + lenf)) > 0){
                extra_ctrl_len = 1;
            }
            else{
                extra_ctrl_len = 0;
            }
            ctrl_data += extra_ctrl_len;

            if(diff_ctrl_len || extra_ctrl_len){
                patch_data[patchdata_pos++] = ctrl_data;

                offtout(lastpos, &patch_data[patchdata_pos]);
                patchdata_pos += lastpos_ctrl_len + 1;
                offtout(lenf, &patch_data[patchdata_pos]);
                patchdata_pos += diff_ctrl_len;
                offtout(((scan - lenb) - (lastscan + lenf)), &patch_data[patchdata_pos]);
                patchdata_pos += extra_ctrl_len;

                for(i = 0; i < lenf; i++)
                    patch_data[patchdata_pos++] = new_data[lastscan + i] - old_data[lastpos + i];
                for(i = 0; i < (scan - lenb) - (lastscan + lenf); i++)
                    patch_data[patchdata_pos++] = new_data[lastscan + lenf + i];
            }


            lastscan = scan - lenb;
            lastpos = pos - lenb;
            lastoffset = pos - scan;
        };
    };






    /* Free the memory we used */
    delete []I;
    *patchdata_size = patchdata_pos;

    return patchdata_pos;
}