/* 
 *  PSX-Tools Bundle Pack 
 *  Copyright (C) 2002 Nicolas "Pixel" Noble 
 *  
 *  This program is free software; you can redistribute it and/or modify 
 *  it under the terms of the GNU General Public License as published by 
 *  the Free Software Foundation; either version 2 of the License, or 
 *  (at your option) any later version. 
 * 
 *  This program is distributed in the hope that it will be useful, 
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of 
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 *  GNU General Public License for more details. 
 * 
 *  You should have received a copy of the GNU General Public License 
 *  along with this program; if not, write to the Free Software 
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include "generic.h"
#include "lzss.h"
#include "Handle.h"

lzss::lzss() : tolerate(1), blockb(0), scheme(schemes[0]), lzss_maxsize(18), lzss_maxptr(0x0fff) {
    compute_limits();
}

/*

Valkyrie Profile V2:

JJJJJJJJ LLLLJJJJ
VVVVVVVV 1111RRRR
RRRRRRRR 11110000 VVVVVVVV

*/

const lzss::scheme_t lzss::schemes[] = {
/*    Nom            1  I  J  O  N 16  P  F     W   Lm1 Ls1   Lm2 Ls2   Jm1 Js1   Jm2 Js2   Fm1 Fs1   Fm2 Fs2   Vm1 Vs1   Vm2 Vs2 Flags*/
#if 0 /* Zelda GC */
    {"Yaz0",         0, 1, 1, 0, 0, 0, 0, 0,    0, 0xf0, -4, 0x00,  0, 0x0f,  8, 0xff,  0, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0},
#endif
    {"Xenogears",    1, 0, 0, 1, 0, 0, 0, 0,    0, 0x00,  0, 0xf0, -4, 0xff,  0, 0x0f,  8, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0},
    {"DBZ RPG",      0, 0, 0, 0, 0, 0, 0, 0,    0, 0x0f,  0, 0x00,  0, 0xf0, -4, 0xff,  4, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0},
    {"FF7",          0, 0, 0, 0, 0, 0, 0, 0,    0, 0x00,  0, 0x0f,  0, 0xff,  0, 0xf0,  4, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0},
    {"Leen Mean",    1, 1, 1, 1, 0, 0, 0, 0,    0, 0x0f,  0, 0x00,  0, 0xf0,  4, 0xff,  0, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0},
    {"Metal Max",    0, 0, 0, 1, 0, 0, 2, 0, 0x12, 0x00,  0, 0x0f,  0, 0xff,  0, 0xf0,  4, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0},
    {"Ogre Battle",  0, 0, 0, 1, 0, 0, 1, 0,    0, 0xf8, -3, 0x00,  0, 0x07,  8, 0xff,  0, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0},
    {"Lodoss Wars",  0, 0, 0, 0, 0, 0, 0, 0,    0, 0x00,  0, 0x7f,  0, 0xff,  0, 0x80,  1, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0},
    {"FF6 PSX",      0, 0, 0, 1, 1, 1, 0, 0,    0, 0x1f,  1, 0x00,  0, 0xe0, -4, 0xff,  4, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0},
    {"Valkyrie-1",   0, 0, 0, 1, 1, 0, 0, 0,    0, 0x00,  0, 0xf0, -4, 0xff,  0, 0x0f,  8, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0},
    {"Valkyrie-2",   0, 0, 0, 1, 1, 0, 0, 2,    0, 0x00,  0, 0xf0, -4, 0xff,  0, 0x0f,  8, 0x00,  0, 0x0f,  0, 0xff,  0, 0x00,  0},
    {"ToD",          0, 0, 0,-1, 1, 0, 1, 1,    3, 0x00,  0, 0x0f,  0, 0xff,  0, 0xf0,  4, 0x00,  0, 0xf0, -4, 0xff,  0, 0x00,  0},
    {0            ,  0, 0, 0, 0, 0, 0, 0, 0,    0,    0,  0,    0,  0,    0,  0,    0,  0, 0x00,  0, 0x00,  0, 0x00,  0, 0x00,  0}
};

Byte lzss::swap_bits(Byte i) {
    i = ((i >> 1) & 0x55) | ((i << 1) & 0xaa);
    i = ((i >> 2) & 0x33) | ((i << 2) & 0xcc);
    i = ((i >> 4) & 0x0f) | ((i << 4) & 0xf0);
    return i;
}

unsigned int lzss::shift(unsigned int c, int s) {
    return s > 0 ? (c << s) : c >> (-s);
}

void lzss::compute_limits(void) {
    unsigned char val1, val2;
    
    val1 = val2 = 0xff;
    
    lzss_maxsize = shift(val1 & scheme.l_mask_1, scheme.l_shft_1) |
		   shift(val2 & scheme.l_mask_2, scheme.l_shft_2);
    lzss_maxptr  = shift(val1 & scheme.j_mask_1, scheme.j_shft_1) |
		   shift(val2 & scheme.j_mask_2, scheme.j_shft_2);
    
    lzss_maxsize = lzss_maxsize + 3 + scheme.sixteen_bits;
    lzss_maxptr += scheme.one_jump;
    
    if (scheme.l_mask_1 & scheme.j_mask_1) {
        printm(M_ERROR, "Masks are overlapping for value 1\n");
        exit(-1);
    }

    if (scheme.l_mask_2 & scheme.j_mask_2) {
        printm(M_ERROR, "Masks are overlapping for value 2\n");
        exit(-1);
    }
    
    if (shift(scheme.l_mask_1, scheme.l_shft_1) & shift(scheme.l_mask_2, scheme.l_shft_2)) {
	printm(M_ERROR, "Shifts build an overlap for lenght\n");
	exit(-1);
    }

    if (shift(scheme.j_mask_1, scheme.j_shft_1) & shift(scheme.j_mask_2, scheme.j_shft_2)) {
	printm(M_ERROR, "Shifts build an overlap for jump\n");
	exit(-1);
    }
    
    printm(M_INFO, "Computed values: maxsize = %i, maxptr = 0x%06x\n", lzss_maxsize, lzss_maxptr);
}

unsigned int lzss::lzss_decomp(Handle * f_source, Handle * f_cible, int true_length)
{
    unsigned char bitmap, fbitmap;
    unsigned char valeur;
    unsigned char * text_buf;
    unsigned char val1, val2, val3;
    int negative_error = scheme.negative_trick, overlap_error = scheme.overlap_trick == 1;
    int r = 0;
    int decomp_count;
    int decomp_length;
    int decomp_fill;
    int decomp_jump;
    int decomp_offset = 0;
    int loop_length;
    int whole_count;
    int i, j;
    int length, reads;

    compute_limits();

    f_source->read(&length, 4);
    if (true_length >= 0) {
        length = true_length;
    }
    whole_count = 0;

    printm(M_INFO, "Decompressing %i bytes\n", length);

    text_buf = (unsigned char *) malloc(length + 8);

    do {
	f_source->read(&bitmap, 1);
	if (scheme.sixteen_bits) {
	    f_source->read(&fbitmap, 1);
	    printm(M_INFO, "16bits behavior, false bitmap = %02x\n", fbitmap);
	}
	printm(M_INFO, "Begin of block, bitmap = %02x\n", bitmap);
	if (scheme.bitmap_inversed) {
	    bitmap = swap_bits(bitmap);
	}
	for (i = 0; i < 8; i++) {
	    printm(M_INFO, " - Chunk %i (offset cible = %li = 0x%04x, offset source = %li = 0x%04x)\n", i, f_cible->tell(), f_cible->tell(), f_source->tell(), f_source->tell());
	    if (whole_count >= length)
		   break;
	    if ((bitmap & 1) ^ scheme.one_is_compressed) {
		for (j = 0; j < (scheme.sixteen_bits ? 2 : 1); j++) {
        	    reads = f_source->read(&valeur, 1);
        	    if (!reads) {
			printm(M_WARNING, "    WARNING! PADDING!\n");
			free(text_buf);
			return length;
		    }
		    printm(M_INFO, "    Copying 0x%02x\n", valeur);
		    f_cible->write(&valeur, 1);
		    text_buf[r++] = valeur;
		    whole_count++;
		}
	    } else {
		f_source->read(&val1, 1);
		f_source->read(&val2, 1);
		decomp_length = shift(val1 & scheme.l_mask_1, scheme.l_shft_1) |
			        shift(val2 & scheme.l_mask_2, scheme.l_shft_2);
		decomp_fill   = shift(val1 & scheme.f_mask_1, scheme.f_shft_1) |
			        shift(val2 & scheme.f_mask_2, scheme.f_shft_2);
		decomp_jump   = shift(val1 & scheme.j_mask_1, scheme.j_shft_1) |
				shift(val2 & scheme.j_mask_2, scheme.j_shft_2);
		valeur        = shift(val1 & scheme.v_mask_1, scheme.v_shft_1) |
			        shift(val2 & scheme.v_mask_2, scheme.v_shft_2);
//		decomp_jump &= lzss_maxptr; bad, ugly, non working
		decomp_jump += scheme.one_jump;
		decomp_length = decomp_length + 3 + scheme.sixteen_bits;
		decomp_fill = decomp_fill + 3 + scheme.sixteen_bits;
#if 0 /* Zelda GC */
		decomp_length--;
		if (decomp_length == 2) {
		    printm(M_INFO, "Big jump\n");
		    decomp_length = f_source->readU8() + 18;
		}
#endif
		if ((decomp_length == lzss_maxsize) && (scheme.filling)) {
		    if ((decomp_fill == 3) && (scheme.filling == 2)) {
			f_source->read(&val3, 1);
			printm(M_INFO, "    Found an extended needle (val1 = 0x%02x, val2 = 0x%02x, val3 = 0x%02x)\n", val1, val2, val3);
			decomp_fill = val1 + 19;
			valeur = val3;
		    } else {
			printm(M_INFO, "    Found a 0x%02x-filling needle of %li bytes (val1 = 0x%02x, val2 = 0x%02x)\n", valeur, decomp_fill, val1, val2);
		    }
		    for (decomp_count = 0; decomp_count < decomp_fill; decomp_count++) {
			f_cible->write(&valeur, 1);
			text_buf[r++] = valeur;
			if (!blockb)
			    whole_count++;
		    }
		    if (blockb)
			whole_count++;
		} else {
		    switch (scheme.ptrb) {
		    case 0:
			decomp_offset = r - decomp_jump;
			break;
		    case 1:
			decomp_offset = r - lzss_maxptr - 1 + decomp_jump - scheme.window_start;
			break;
		    case 2:
			decomp_offset = decomp_jump - scheme.window_start;
			break;
		    }
		    decomp_offset += scheme.overlap_trick == -1 ? decomp_length : 0;
		    loop_length = decomp_offset + decomp_length;
		    if ((loop_length >= r) && (!overlap_error)) {
			if (!tolerate) {
			    free(text_buf);
			    return 0;
			}
		        printm(M_ERROR, "Overlap trick used without it beeing enabled in the scheme.\n");
			overlap_error = 1;
		    }
		    printm(M_INFO, "    Found a needle of %li bytes at %li = 0x%04x, jump of %li = 0x%04x (val1 = 0x%02x, val2 = 0x%02x)\n", decomp_length, decomp_offset, decomp_offset, decomp_jump, decomp_jump, val1, val2);
		    for (decomp_count = decomp_offset; decomp_count < loop_length; decomp_count++) {
			if (!blockb)
			    whole_count++;
			if (decomp_count < 0) {
			    valeur = 0;
			    f_cible->write(&valeur, 1);
			    text_buf[r++] = 0;
			    if (!negative_error) {
				if (!tolerate) {
				    free(text_buf);
				    return 0;
			        }
				printm(M_ERROR, "Negative trick used without it beeing enabled in the scheme.\n");
				negative_error = 1;
			    }
			    printm(M_INFO, "Filling with 0\n");
			} else {
			    f_cible->write(&text_buf[decomp_count], 1);
		    	    printm(M_INFO, "@0x%04x: 0x%02x\n", decomp_count, text_buf[decomp_count]);
			    text_buf[r++] = text_buf[decomp_count];
			}
			if (whole_count >= length)
                    	    break;
		    }
		    if (blockb)
			whole_count++;
		}
	    }
	    bitmap >>= 1;
	}
    } while (whole_count < length);
    free(text_buf);
    
    return length;
}

unsigned char lzss::lzss_rd(unsigned char * t, int p) {
    return ((p < 0) ? 0 : (t[p]));
}

int lzss::lzss_comp_strstr(unsigned char * needle, unsigned char * r, int * l, int sp) {
    char redo[256];
    int length, i, p, ptr, maxlength;
    
    i = 1;
    redo[0] = p = 0;
    while (i < lzss_maxsize) {
	if (needle[i] == needle[p]) {
	    redo[i++] = ++p;
	} else if (p > 0) {
	    p = redo[p - 1];
	} else {
	    redo[i++] = 0;
	}
    }
    
    length = maxlength = 0;
    i = sp;
    p = 0;
    ptr = 0;
    
    while ((i - sp - (scheme.overlap_trick ? p : 0)) < *l) {
	if (needle[p] == lzss_rd(r, i)) {
	    if (p == (lzss_maxsize - 1)) {
		*l = lzss_maxsize;
		return i - lzss_maxsize + 1;
	    }
	    i++;
	    p++;
	} else if (p > 0) {
	    if (p > maxlength) {
		if (!((i - p) & scheme.sixteen_bits)) {
		    ptr = i - (maxlength = p);
		}
	    }
	    p = redo[p - 1];
	} else {
	    i++;
	}
    }
    
    *l = maxlength;
    return ptr;
}

unsigned char * lzss::lzss_memcomp(unsigned char * r, int * l, int * delta) {
    unsigned char bitmap, * comp;
    int ptr, needle, needle_length, comp_ptr, bitmap_ptr, val1, val2;
    int jump, farest, remaining;
    int j;
    
    comp = (unsigned char *) malloc(3 * *l);
    
    compute_limits();
    
    ptr = 0;
    blk = 0;
    bitmap_count = 0;
    comp_ptr = 1 + scheme.sixteen_bits;
    bitmap = 0;
    bitmap_ptr = 0;
    printm(M_INFO, "Begin of block 0.\n");
    while ((remaining = *l - ptr) > 0) {
	printm(M_INFO, "   Remaining bytes: %li\n", remaining);
	bitmap_count++;
	bitmap >>= 1;
	farest = ptr - lzss_maxptr;
	farest = farest > ((-lzss_maxsize) * scheme.negative_trick) ? farest : -lzss_maxsize * scheme.negative_trick;
	needle_length = ptr - farest;
	if (scheme.ptrb == 2) {
	    farest = 0;
	    needle_length = MIN(lzss_maxptr - scheme.window_start, ptr);
	}
	needle = lzss_comp_strstr(&r[ptr], r, &needle_length, farest);
	if ((needle < 0) && ((-needle) > needle_length)) {
	    needle = -needle_length;
	}
	printm(M_INFO, " - Chunk %i (offset source = %li = 0x%04x, offset cible = %li = 0x%04x)\n", bitmap_count - 1, ptr, ptr, comp_ptr, comp_ptr);
	jump = ptr - needle;
	needle_length = needle_length > remaining ? remaining : needle_length;
	
	if (needle_length & scheme.sixteen_bits) {
	    needle_length--;
	}
	
	if ((needle < 0) || (!jump)) {
	    printm(M_INFO, "   Nothing found.\n");
	} else {
	    printm(M_INFO, "   Found a needle of %i bytes at offset %i (jump = %i = 0x%04x)\n", needle_length, needle, jump, jump);
	}
	
	if ((needle_length <= (2 + scheme.sixteen_bits)) || (!jump)) {
	    if (needle_length > 2) {
		printm(M_ERROR, "    ** REJECTED **\n");
	    }
	    for (j = 0; j < (scheme.sixteen_bits ? 2 : 1); j++) {
		printm(M_INFO, "    Repeating 0x%02x\n", r[ptr]);
		comp[comp_ptr] = r[ptr];
		ptr++;
		comp_ptr++;
	    }
	    bitmap |= 0x80;
	} else {
	    int j;
	    printm(M_INFO, "    Found a needle of %li bytes at %li = 0x%04x\n", needle_length, needle, needle);
	    for (j = 0; j < needle_length; j++) {
		printm(M_INFO, "@0x%04x: 0x%02x - @0x%04x: 0x%02x\n", needle + j, lzss_rd(r, needle + j - scheme.window_start), ptr + j, lzss_rd(r, ptr + j));
		if (lzss_rd(r, needle + j) != lzss_rd(r, ptr + j)) {
		    printm(M_ERROR, "ERROR!!\n");
		}
	    }
	    jump -= scheme.one_jump;
	    printm(M_INFO, "ptr = %li, needle = %li, jump = %li = 0x%03x\n", ptr, needle, jump, jump);
	    ptr += needle_length;
	    needle_length -= 3;
	    switch (scheme.ptrb) {
	    case 0:
		break;
	    case 1:
		jump = lzss_maxptr + 1 - jump;
		break;
	    case 2:
		jump = needle + scheme.window_start;
		break;
	    }
	    val1 = comp[comp_ptr++] = (shift(jump, -scheme.j_shft_1) & scheme.j_mask_1) |
				      (shift(needle_length, -scheme.l_shft_1) & scheme.l_mask_1);
	    val2 = comp[comp_ptr++] = (shift(jump, -scheme.j_shft_2) & scheme.j_mask_2) |
				      (shift(needle_length, -scheme.l_shft_2) & scheme.l_mask_2);
	    printm(M_INFO, "    writing info1 = 0x%02x, info2 = 0x%02x\n", val1, val2);
	}
	
	bitmap ^= scheme.one_is_compressed << 7;

	if (bitmap_count == 8) {
	    blk++;
	    printm(M_INFO, "End of block, writing bitmap = 0x%02x\n", bitmap);
	    printm(M_INFO, "Begin of block %li.\n", blk);
	    bitmap_count = 0;
	    if (scheme.bitmap_inversed)
		bitmap = swap_bits(bitmap);
	    comp[bitmap_ptr] = bitmap;
	    if (scheme.sixteen_bits) {
		comp[bitmap_ptr + 1] = 0;
	    }
	    bitmap_ptr = comp_ptr;
	    comp_ptr += (scheme.sixteen_bits ? 2 : 1);
	}
    }
    
    if (bitmap_count) {
	bitmap >>= (8 - bitmap_count);
	if (scheme.bitmap_inversed)
	    bitmap = swap_bits(bitmap);
	comp[bitmap_ptr] = bitmap;
	if (scheme.sixteen_bits) {
	    comp[bitmap_ptr + 1] = 0;
	}
    } else {
	comp_ptr--;
    }
    
    if (delta) {
	*delta = (bitmap_count ? 8 - bitmap_count : 0);
    }
    
    *l = comp_ptr;
    return comp;
}

void lzss::lzss_comp(Handle * f_source, Handle * f_cible, int * delta) {
    int length = f_source->GetSize(), l;
    unsigned char * r = (unsigned char *) malloc(length), * c;
    
    f_source->read(r, length);
    l = length;
    c = lzss_memcomp(r, &l, delta);
    if (delta) {
	length += *delta;
    }
    f_cible->write(&length, 4);
    if (delta) {
	length -= *delta;
    }
    f_cible->write(c, l);
    free(c);
    free(r);
}

void lzss::change_scheme(scheme_t new_scheme) {
    scheme = new_scheme;
    compute_limits();
}

lzss::scheme_t lzss::get_scheme() {
    return scheme;
}