From d38e80ee04afe582e70150d3884e56c05f3fd7a8 Mon Sep 17 00:00:00 2001 From: pixel Date: Sat, 27 Nov 2004 21:44:44 +0000 Subject: Large dos2unix commit... --- lib/lzss.cpp | 928 +++++++++++++++++++++++++++++------------------------------ 1 file changed, 464 insertions(+), 464 deletions(-) (limited to 'lib/lzss.cpp') diff --git a/lib/lzss.cpp b/lib/lzss.cpp index 7b134aa..1d7ecfb 100644 --- a/lib/lzss.cpp +++ b/lib/lzss.cpp @@ -1,464 +1,464 @@ -/* - * 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 -#include -#include -#include -#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); - lzss_maxsize = MIN(lzss_maxsize, 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; -} +/* + * 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 +#include +#include +#include +#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); + lzss_maxsize = MIN(lzss_maxsize, 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; +} -- cgit v1.2.3