diff options
| -rw-r--r-- | FAQ-lzss.txt (renamed from FAQ-lz77.txt) | 19 | ||||
| -rwxr-xr-x | Makefile | 10 | ||||
| -rwxr-xr-x | VP/Makefile | 10 | ||||
| -rwxr-xr-x | Xenogears/Makefile | 10 | ||||
| -rw-r--r-- | Xenogears/script-comp.cpp | 4 | ||||
| -rw-r--r-- | Xenogears/test-dlzss.cpp (renamed from Xenogears/test-dlz77.cpp) | 4 | ||||
| -rw-r--r-- | Xenogears/test-lzss.cpp (renamed from Xenogears/test-lz77.cpp) | 4 | ||||
| -rw-r--r-- | dteutils.cpp | 7 | ||||
| -rw-r--r-- | lzss.cpp (renamed from lz77.cpp) | 72 | ||||
| -rw-r--r-- | lzss.h (renamed from lz77.h) | 4 |
10 files changed, 73 insertions, 71 deletions
diff --git a/FAQ-lz77.txt b/FAQ-lzss.txt index 65433f6..f9a9819 100644 --- a/FAQ-lz77.txt +++ b/FAQ-lzss.txt @@ -21,12 +21,13 @@ A: The lz77 compression is a quite simple algorithm, which works in stream. -Q: What are the differences between lz77, lzss and lzw? -A: The lzw is the algorithm name implemented by PKZIP, and thus by WinZIP. - But it uses basically the same scheme as the lz77 algorithm. The lzss - is the name for a fixed maximum backward length window algorithm. - I've named my stuff 'lz77' because it's the generic name for it. - The lzw is in fact two algorithms in one: the Huffman and the lz77. +Q: What are the differences between LZ77, LZ78, LZSS and LZW? +A: The LZW is a modification of the LZ77/8 algorithms by Terry Welch. There + is a sliding dictionnary instead of a sliding window. The LZ77 and LZ78 took + their name from J. Ziv and A. Lempel, made in 1977 and in 1978. The LZSS is + the same, with a bitmap telling the backwards pointers. So the exact name + for the algorithm I wrote is 'lzss'. You can have some good informations + here: http://www.image.ee.cityu.edu.hk/~loben/thesis/index.html @@ -160,7 +161,7 @@ A: You have: Q: What are the overlap and the negative tricks? A: You really want to know? *sigh* Ok, here we go. The negative is still the simplier to understand. When you - are uncompressing a lz77 stream, you read backward jumps and lengths. The + are uncompressing a lzss stream, you read backward jumps and lengths. The maximum value for a jump and a length are determined on how the two infos are packed into the restart block. @@ -212,12 +213,12 @@ A: You really want to know? *sigh* Q: When do I have to active the overlap and negative tricks? A: Well, for the decompressor, it's not really necessary, because it won't crash if the flags are not enabled. But it will warn you so you will be - able to know that the tricks are enabled into the lz77 stream. So if you + able to know that the tricks are enabled into the lzss stream. So if you see that those tricks are enabled, then active the flags so the compressor will be able to take care of them. Something else: you may also test if the tricks are working. Maybe they - wasn't used when your original lz77 stream was created, but the decompression + wasn't used when your original lzss stream was created, but the decompression algorithm used by the game *maybe* is able to handle them. @@ -3,15 +3,15 @@ CPPFLAGS=-Wall -g -I. -O3 -mcpu=i686 -pedantic -pedantic-errors -Werror CXX=g++ -TARGET = lz77 dlz77 yazedc cd-tool dte-tool +TARGET = lzss dlzss yazedc cd-tool dte-tool all: ${TARGET} -lz77: lz77.cpp lz77.h generic.cpp generic.h fileutils.h fileutils.cpp - ${CXX} ${CPPFLAGS} ${LDFLAGS} -DLZ77_MAIN lz77.cpp generic.cpp fileutils.cpp -o lz77 +lzss: lzss.cpp lzss.h generic.cpp generic.h fileutils.h fileutils.cpp + ${CXX} ${CPPFLAGS} ${LDFLAGS} -Dlzss_MAIN lzss.cpp generic.cpp fileutils.cpp -o lzss -dlz77: lz77 - ln -fs lz77 dlz77 +dlzss: lzss + ln -fs lzss dlzss yazedc: yazedc.cpp crctables crctable.out ${CXX} ${CPPFLAGS} ${LDFLAGS} yazedc.cpp -DMAIN -o yazedc diff --git a/VP/Makefile b/VP/Makefile index e24e983..2a6deba 100755 --- a/VP/Makefile +++ b/VP/Makefile @@ -3,18 +3,18 @@ CPPFLAGS=-Wall -g -I. -O3 -mcpu=i686 -pedantic -pedantic-errors -Werror CXX=g++ -TARGET = lz77 dlz77 yazedc cd-tool main_dump VP-CD1.sqr +TARGET = lzss dlzss yazedc cd-tool main_dump VP-CD1.sqr all: ${TARGET} main_dump: main_dump.cpp yazedc.cpp yazedc.h fileutils.cpp fileutils.h cdutils.cpp cdutils.h generic.cpp generic.h crctables crctable.out ${CXX} ${CPPFLAGS} ${LDFLAGS} main_dump.cpp yazedc.cpp fileutils.cpp cdutils.cpp generic.cpp -o main_dump -lz77: lz77.cpp lz77.h generic.cpp generic.h fileutils.h fileutils.cpp - ${CXX} ${CPPFLAGS} ${LDFLAGS} -DLZ77_MAIN lz77.cpp generic.cpp fileutils.cpp -o lz77 +lzss: lzss.cpp lzss.h generic.cpp generic.h fileutils.h fileutils.cpp + ${CXX} ${CPPFLAGS} ${LDFLAGS} -Dlzss_MAIN lzss.cpp generic.cpp fileutils.cpp -o lzss -dlz77: lz77 - ln -fs lz77 dlz77 +dlzss: lzss + ln -fs lzss dlzss yazedc: yazedc.cpp crctables crctable.out ${CXX} ${CPPFLAGS} ${LDFLAGS} yazedc.cpp -DMAIN -o yazedc diff --git a/Xenogears/Makefile b/Xenogears/Makefile index 14c48ff..7bb9299 100755 --- a/Xenogears/Makefile +++ b/Xenogears/Makefile @@ -3,15 +3,15 @@ CPPFLAGS=-Wall -g -I. -O3 -mcpu=i686 CXX=g++ -TARGET = lz77 dlz77 yazedc cd-tool reinsert +TARGET = lzss dlzss yazedc cd-tool reinsert all: ${TARGET} -lz77: lz77.cpp lz77.h generic.cpp generic.h fileutils.h fileutils.cpp - ${CXX} ${CPPFLAGS} ${LDFLAGS} -DLZ77_MAIN lz77.cpp generic.cpp fileutils.cpp -o lz77 +lzss: lzss.cpp lzss.h generic.cpp generic.h fileutils.h fileutils.cpp + ${CXX} ${CPPFLAGS} ${LDFLAGS} -Dlzss_MAIN lzss.cpp generic.cpp fileutils.cpp -o lzss -dlz77: lz77 - ln -fs lz77 dlz77 +dlzss: lzss + ln -fs lzss dlzss yazedc: yazedc.cpp crctables crctable.out ${CXX} ${CPPFLAGS} ${LDFLAGS} yazedc.cpp -DMAIN -o yazedc diff --git a/Xenogears/script-comp.cpp b/Xenogears/script-comp.cpp index 96645df..d01a13f 100644 --- a/Xenogears/script-comp.cpp +++ b/Xenogears/script-comp.cpp @@ -1,6 +1,6 @@ #include <stdio.h> #include <stdlib.h> -#include "lz77.h" +#include "lzss.h" #include "fileutils.h" void process_one_file(int f, int d, int n) { @@ -38,7 +38,7 @@ void process_one_file(int f, int d, int n) { write(d, &true_length, 4); lseek(d, 0, SEEK_END); - lz77_comp(f_part, d, &delta); + lzss_comp(f_part, d, &delta); close(f_part); diff --git a/Xenogears/test-dlz77.cpp b/Xenogears/test-dlzss.cpp index 98373a6..ecd0f7e 100644 --- a/Xenogears/test-dlz77.cpp +++ b/Xenogears/test-dlzss.cpp @@ -1,7 +1,7 @@ #include <stdio.h> -#include "lz77.h" +#include "lzss.h" int main(void) { - lz77_decomp(0, 1); + lzss_decomp(0, 1); return 0; } diff --git a/Xenogears/test-lz77.cpp b/Xenogears/test-lzss.cpp index 8efce98..0257e99 100644 --- a/Xenogears/test-lz77.cpp +++ b/Xenogears/test-lzss.cpp @@ -1,7 +1,7 @@ #include <stdio.h> -#include "lz77.h" +#include "lzss.h" int main(void) { - lz77_comp(0, 1); + lzss_comp(0, 1); return 0; } diff --git a/dteutils.cpp b/dteutils.cpp index 2759dc5..e740abf 100644 --- a/dteutils.cpp +++ b/dteutils.cpp @@ -161,16 +161,17 @@ void dte_reset(void) { void build_dte(void) { int i; unsigned short t, t2; -// unsigned short p = 0; + unsigned short p = 0; for (i = 0; i < dte_text_size; i++) { t = *((unsigned short *) (dte_text + i)); t2 = *((unsigned short *) (dte_text + i + 1)); -/* if (t == p) { + if (t == p) { p = 0; continue; } - p = t; */ + p = t; +// if (!dte_flags[t]) { if ((!dte_flags[t]) && (dte_flags[t2] != 3)) { dte_counters[t]++; if (dte_counters[t] > dte_counter) { @@ -24,10 +24,10 @@ #include <iostream.h> #include "fileutils.h" #include "generic.h" -#include "lz77.h" +#include "lzss.h" -int lz77_maxsize = 18; -int lz77_maxptr = 0x0fff; +int lzss_maxsize = 18; +int lzss_maxptr = 0x0fff; int tolerate = 1; int blockb = 0; @@ -64,13 +64,13 @@ void compute_limits(void) { val1 = val2 = 0xff; - lz77_maxsize = shift(val1 & scheme.l_mask_1, scheme.l_shft_1) | + lzss_maxsize = shift(val1 & scheme.l_mask_1, scheme.l_shft_1) | shift(val2 & scheme.l_mask_2, scheme.l_shft_2); - lz77_maxptr = shift(val1 & scheme.j_mask_1, scheme.j_shft_1) | + lzss_maxptr = shift(val1 & scheme.j_mask_1, scheme.j_shft_1) | shift(val2 & scheme.j_mask_2, scheme.j_shft_2); - lz77_maxsize = lz77_maxsize + 3 + scheme.sixteen_bits; - lz77_maxptr += scheme.one_jump; + 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"); @@ -92,10 +92,10 @@ void compute_limits(void) { exit(-1); } - printm(M_INFO, "Computed values: maxsize = %i, maxptr = 0x%06x\n", lz77_maxsize, lz77_maxptr); + printm(M_INFO, "Computed values: maxsize = %i, maxptr = 0x%06x\n", lzss_maxsize, lzss_maxptr); } -unsigned long lz77_decomp(FILE * f_source, FILE * f_cible, long true_length) +unsigned long lzss_decomp(FILE * f_source, FILE * f_cible, long true_length) { unsigned char bitmap, fbitmap; unsigned char valeur; @@ -163,11 +163,11 @@ unsigned long lz77_decomp(FILE * f_source, FILE * f_cible, long true_length) 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 &= lz77_maxptr; + decomp_jump &= lzss_maxptr; decomp_jump += scheme.one_jump; decomp_length = decomp_length + 3 + scheme.sixteen_bits; decomp_fill = decomp_fill + 3 + scheme.sixteen_bits; - if ((decomp_length == lz77_maxsize) && (scheme.filling)) { + if ((decomp_length == lzss_maxsize) && (scheme.filling)) { if ((decomp_fill == 3) && (scheme.filling == 2)) { fread(&val3, 1, 1, f_source); printm(M_INFO, " Found an extended needle (val1 = 0x%02x, val2 = 0x%02x, val3 = 0x%02x)\n", val1, val2, val3); @@ -190,7 +190,7 @@ unsigned long lz77_decomp(FILE * f_source, FILE * f_cible, long true_length) decomp_offset = r - decomp_jump; break; case 1: - decomp_offset = r - lz77_maxptr - 1 + decomp_jump; + decomp_offset = r - lzss_maxptr - 1 + decomp_jump; break; case 2: decomp_offset = decomp_jump - scheme.window_start; @@ -242,17 +242,17 @@ unsigned long lz77_decomp(FILE * f_source, FILE * f_cible, long true_length) return length; } -unsigned char lz77_rd(unsigned char * t, long p) { +unsigned char lzss_rd(unsigned char * t, long p) { return ((p < 0) ? 0 : (t[p])); } -long lz77_comp_strstr(unsigned char * needle, unsigned char * r, long * l, long sp) { +long lzss_comp_strstr(unsigned char * needle, unsigned char * r, long * l, long sp) { char redo[256]; long length, i, p, ptr, maxlength; i = 1; redo[0] = p = 0; - while (i < lz77_maxsize) { + while (i < lzss_maxsize) { if (needle[i] == needle[p]) { redo[i++] = ++p; } else if (p > 0) { @@ -268,10 +268,10 @@ long lz77_comp_strstr(unsigned char * needle, unsigned char * r, long * l, long ptr = 0; while ((i - sp - (scheme.overlap_trick ? p : 0)) < *l) { - if (needle[p] == lz77_rd(r, i)) { - if (p == (lz77_maxsize - 1)) { - *l = lz77_maxsize; - return i - lz77_maxsize + 1; + if (needle[p] == lzss_rd(r, i)) { + if (p == (lzss_maxsize - 1)) { + *l = lzss_maxsize; + return i - lzss_maxsize + 1; } i++; p++; @@ -293,7 +293,7 @@ long lz77_comp_strstr(unsigned char * needle, unsigned char * r, long * l, long long blk, bitmap_count; -unsigned char * lz77_memcomp(unsigned char * r, long * l, long * delta) { +unsigned char * lzss_memcomp(unsigned char * r, long * l, long * delta) { unsigned char bitmap, * comp; long ptr, needle, needle_length, comp_ptr, bitmap_ptr, val1, val2; long jump, farest, remaining; @@ -314,14 +314,14 @@ unsigned char * lz77_memcomp(unsigned char * r, long * l, long * delta) { printm(M_INFO, " Remaining bytes: %li\n", remaining); bitmap_count++; bitmap >>= 1; - farest = ptr - lz77_maxptr; - farest = farest > ((-lz77_maxsize) * scheme.negative_trick) ? farest : -lz77_maxsize * scheme.negative_trick; + 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(lz77_maxptr - scheme.window_start, ptr); + needle_length = MIN(lzss_maxptr - scheme.window_start, ptr); } - needle = lz77_comp_strstr(&r[ptr], r, &needle_length, farest); + needle = lzss_comp_strstr(&r[ptr], r, &needle_length, farest); if ((needle < 0) && ((-needle) > needle_length)) { needle = -needle_length; } @@ -354,8 +354,8 @@ unsigned char * lz77_memcomp(unsigned char * r, long * l, long * delta) { 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, lz77_rd(r, needle + j - scheme.window_start), ptr + j, lz77_rd(r, ptr + j)); - if (lz77_rd(r, needle + j) != lz77_rd(r, ptr + 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"); } } @@ -367,7 +367,7 @@ unsigned char * lz77_memcomp(unsigned char * r, long * l, long * delta) { case 0: break; case 1: - jump = lz77_maxptr + 1 - jump; + jump = lzss_maxptr + 1 - jump; break; case 2: jump = needle + scheme.window_start; @@ -418,13 +418,13 @@ unsigned char * lz77_memcomp(unsigned char * r, long * l, long * delta) { return comp; } -void lz77_comp(FILE * f_source, FILE * f_cible, long * delta) { +void lzss_comp(FILE * f_source, FILE * f_cible, long * delta) { long length = filesize(f_source), l; unsigned char * r = (unsigned char *) malloc(length), * c; fread(r, 1, length, f_source); l = length; - c = lz77_memcomp(r, &l, delta); + c = lzss_memcomp(r, &l, delta); if (delta) { length += *delta; } @@ -437,7 +437,7 @@ void lz77_comp(FILE * f_source, FILE * f_cible, long * delta) { free(r); } -#ifdef LZ77_MAIN +#ifdef lzss_MAIN char * fn1, * fn2, * pname; @@ -568,15 +568,15 @@ int main(int argc, char ** argv) { verbosity = M_STATUS; - if (!strcasecmp(pname + p, "dlz77")) { + if (!strcasecmp(pname + p, "dlzss")) { compress = 0; } printm(M_BARE, -LZ77_NAME " compressor/decompressor version " LZ77_VERSION ",\n" +lzss_NAME " compressor/decompressor version " lzss_VERSION ",\n" "Copyright (C) 2002 Nicolas \"Pixel\" Noble\n" "This software comes with ABSOLUTELY NO WARRANTY; see COPYING for details\n" -"Thanks to Czar Dragon, for his little 'LZ77' schemes FAQ.\n" +"Thanks to Czar Dragon, for his little 'lzss' schemes FAQ.\n" "Special thanks to Yazoo, who taught me PSX hacking.\n" "\n"); @@ -776,12 +776,12 @@ LZ77_NAME " compressor/decompressor version " LZ77_VERSION ",\n" if (compress) { if (length == -1) { - lz77_comp(f1, f2); + lzss_comp(f1, f2); } else { - lz77_comp(f1, f2, &length); + lzss_comp(f1, f2, &length); } } else { - length = lz77_decomp(f1, f2, length); + length = lzss_decomp(f1, f2, length); } printm(M_STATUS, "Done, filesize changed from %i to %i.\n", filesize(f1), filesize(f2)); @@ -54,8 +54,8 @@ extern scheme_t scheme, schemes[]; extern int tolerate; -unsigned long lz77_decomp(FILE * f_source, FILE * f_cible, long true_length = -1); -void lz77_comp(FILE * f_source, FILE * f_cible, long * delta = NULL); +unsigned long lzss_decomp(FILE * f_source, FILE * f_cible, long true_length = -1); +void lzss_comp(FILE * f_source, FILE * f_cible, long * delta = NULL); char swap_bits(char); |