From e2fa0166aa8cb791e2e7d8b47adb6e07cbfcc549 Mon Sep 17 00:00:00 2001 From: Pixel Date: Mon, 27 May 2002 20:05:33 +0000 Subject: Fixing LZSS name. --- FAQ-lz77.txt | 241 -------------- FAQ-lzss.txt | 242 ++++++++++++++ Makefile | 10 +- VP/Makefile | 10 +- Xenogears/Makefile | 10 +- Xenogears/script-comp.cpp | 4 +- Xenogears/test-dlz77.cpp | 7 - Xenogears/test-dlzss.cpp | 7 + Xenogears/test-lz77.cpp | 7 - Xenogears/test-lzss.cpp | 7 + dteutils.cpp | 7 +- lz77.cpp | 799 ---------------------------------------------- lz77.h | 62 ---- lzss.cpp | 799 ++++++++++++++++++++++++++++++++++++++++++++++ lzss.h | 62 ++++ 15 files changed, 1138 insertions(+), 1136 deletions(-) delete mode 100644 FAQ-lz77.txt create mode 100644 FAQ-lzss.txt delete mode 100644 Xenogears/test-dlz77.cpp create mode 100644 Xenogears/test-dlzss.cpp delete mode 100644 Xenogears/test-lz77.cpp create mode 100644 Xenogears/test-lzss.cpp delete mode 100644 lz77.cpp delete mode 100644 lz77.h create mode 100644 lzss.cpp create mode 100644 lzss.h diff --git a/FAQ-lz77.txt b/FAQ-lz77.txt deleted file mode 100644 index 65433f6..0000000 --- a/FAQ-lz77.txt +++ /dev/null @@ -1,241 +0,0 @@ - - - -Q: What is the lz77 compression? What is the terminology you used? -A: The lz77 compression is a quite simple algorithm, which works in stream. - You have to "copy" the uncompressed bytes from the stream, and sometime, - you encounter what I've called "restart blocks" which tells two things: - a backward jump, and a lenght. The jump value tells you of how many bytes - you have to "rewind", and the length tells you how many bytes you have to - copy from there. For example if you have the compressed stream: - - One Ring to rule them all, find. - - then you will decompress it by: - - One Ring to rule them all, One Ring to find them. - - because when you hit the , it tells you to copy 12 bytes from - 27 bytes backward, and when you hit the , it tells you to - copy 5 bytes from 28 bytes backward. - - - -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: How is the file stored? -A: From a general manner, you have a 4 bytes length to know where to stop - when you are uncompressing. As you may have noticed, you have normal - bytes and compressed blocks. So you can have a bitmap which tells you - if the bytes are normal bytes or restart blocks. As an example, let's - look the Lord of the Rings compression: - - |Bitmaps | Datas - |--------|---------------------------|--------| - |00000000| 4f 6e 65 20 52 69 6e 67 |One Ring| - |00000000| 20 74 6f 20 72 75 6c 65 | to rule| - |00000000| 20 74 68 65 6d 20 61 6c | them al| - |00010000| 6c 2c 20<1b 90>66 69 6e 64|l, ..find| - |10000000|<1b 20>2e |...| - - If you have a 0 in the bitmap, then you know you have to simply copy the - byte you find, and if you have a 1, you have to read the two next bytes, - 'unpack' them to find the backward jump and the length, then copy the - corresponding bytes. As an exercise, try to find how I've 'packed' the - length and the backward jump into the above array. - - Since you need two bytes to write a restart block, you will have to add - three to the unpacked length. - - Here is the final form of the packed file: - -0000: 31 00 00 00 00 4F 6E 65 20 52 69 6E 67 00 20 74 1 One Ring t -0010: 6F 20 72 75 6C 65 00 20 74 68 65 6D 20 61 6C 08 o rule them al. -0020: 6C 2C 20 1B 90 66 69 6E 64 01 1B 20 2E l, ..find.. .. - - Note how the bitmaps are stored. - - - -Q: How are the jump and length packed? -A: You may find infos on the net like: - - O3 O2 O1 O0 L3 L2 L1 L0 | OB OA O9 O8 O7 O6 O5 O4 - - This means that the two infos are packed like this: the offset (jump) has the - four lower bits in the four upper bits of the first byte, then the eight upper - bits are directly stored into the second byte. Thus, the backward jump is - stored on 12 bits. The length is stored in four bits, and they are stored in - the four lower bits of the first byte. So the length may vary from 3 to 18. - - - -Q: What is the relationship between the schemes into the software and the - thing you pasted above? -A: It's quite easy. The computation formula is the following: - - decomp_length = shift(val1 & scheme.l_mask_1, scheme.l_shft_1) | - shift(val2 & scheme.l_mask_2, scheme.l_shft_2); - decomp_jump = shift(val1 & scheme.j_mask_1, scheme.j_shft_1) | - shift(val2 & scheme.j_mask_2, scheme.j_shft_2); - - - So, if you want to write the eight parameters for the above thingy, you - will have to set them to this: - - l_mask_1 = 0x0f | l_mask_2 = 0x00 | j_mask_1 = 0xf0 | j_mask_2 = 0xff - l_shft_1 = 0 | l_shft_2 = 0 | j_shft_1 = -4 | j_shft_2 = 4 - - What is he most difficult to understand is the jump value. We want to build - the jump value as: OB OA O9 O8 O7 O6 O5 O4 O3 O2 O1 O0. - - Let's first work on the first byte. - -) We have to only keep the Ox bits - -) Then we have to move them to the right. - - The mask is here to suppress the unwanted bits. So for our case, the mask is - 0xf0 since it's the four high bits. The shift is here to move the bits. A - negative value means to move them to the right, and a positive means to the - left. So since we have to make the bits go to the four lower bits, we have - a shift of -4 - - For the second byte: - -) We keep all the bits, but - -) we have to make room for the four bits from the first byte. - - The mask don't have to suppress anything, so it's set to 0xff. And now, the - shift is set to 4 to make enough room. - - Finally, the software will build the jump with those four parameters. - - -Q: What are the others parameters? -A: You have: - - 1iscomp overlap negative 16bits ptrb - filling inverse onejump window - - This will change the behaviour of the compression/decompression algorithm. - - The 1iscomp will inverse the bitmap from the default. The default is, a 1 in - the bitmap is uncompressed. - - The overlap is a boolean to tell the compressor to use the overlap trick. - Some roms does use it, but is a little hard to explain here. - - This is the same for the negative trick. - - The 16bits behavior is quite specific to the FF6 PSX. Everything is coded - using 16 bits words instead of 8 bits words. And thus, the compression - algorithm is more difficult. As for now, it's broken. - - The ptrb means "pointer behavior". It can take the value 0, 1 or 2. The - behavior '0' is the common one: the jump is the number of bytes to - count back to find the start of the needle to copy. The '1' is to tell - the jump is an offset from the maximum backward jump possible (ie - from the start point of the window). The '2' is a very dumb behavior: - it tells that the jump is the absolute offset. The window *won't* slide. - - The filling option activates the RLE behavior. - - The inverse is a boolean to tell to reverse the order of the bits in the - bitmaps - - The onejump tells to add one to the final jump value. Some streams are - shifted by one because by default, a jump of 0 means nothing. So it - is dumb to miss one possible backward jump. - - The window offset tells the absolute window start for the 2th pointer - behavior. Yeah, this is necessary. Coders of Metal Max are pretty crazy. - - - -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 - maximum value for a jump and a length are determined on how the two infos - are packed into the restart block. - - For example, if you have 12 bits for the jump and 4 for the length, you will - have a maximum of 0xfff for the jump and 18 for the length (18 because it's - 0xf + 3) - - Here comes the negative trick: when you are uncompressing the first bytes, - you will still be able to have a jump which is *beyond* the beginning of the - decompressed file. Later, when your file will grow up, this won't be possible - anymore of course, since its size will be over the maximum jump size. - - So, sometime, you can consider that *if* you have a negative value, it's not - a fault: you just read zeros. Understood? BTW, most of the case, the negative - restart will be very near the begin of the file. So if you have to copy five - bytes distant of 1000 bytes from the beginning of the file, *this* is - probably a fault, or a misunderstood scheme. - - - Next, the overlap trick. It's more difficult to understand though. You have - to understand the decompressor's algorithm a bit. When it hits a restart - block, it computes the jump and the length, then it will begin to copy the - bytes from the old decompressed datas, one byte after the other. - - So the trick is here: when you are copying the bytes, the algorithm will - be able to reuse them immediately for the current copy, since they are - already written. The restart block will use "itself". - - Let's have an example: - - If you want to compress the stream: - - 123123123123 - - you will have two solutions. Either with, either without the overlap trick. - Without the overlap trick, here is the compressed stream: - - 123123 - - This is obvious hu? Now, with the overlap trick: - - 123 - - Try to take a piece of paper and to decompress those two thingy, maybe this - will help you understand. - - - -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 - 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 - algorithm used by the game *maybe* is able to handle them. - - - -Q: What is the filling thing? -A: It's an RLE like behavior. In Valkyrie Profile, when the length hit the - maximum value, then it means it's a RLE block, and not a restart block. - That's why you've got the eight options: - - - fmask1 fshft1 fmask2 fshft2 vmask1 vshft1 vmask2 vshft2 - - Basically, they are the same as the {j,l}{mask,shft}{1,2} options, but - this time you tell where to find the 'value' which has to be copied, - and the 'filling', ie the number of times this value will be copied. - - -Q: What is the 2th filling behaviour? -A: Get out of here. It's a ugly ugly ugly hack. Forget it. Now! - - diff --git a/FAQ-lzss.txt b/FAQ-lzss.txt new file mode 100644 index 0000000..f9a9819 --- /dev/null +++ b/FAQ-lzss.txt @@ -0,0 +1,242 @@ + + + +Q: What is the lz77 compression? What is the terminology you used? +A: The lz77 compression is a quite simple algorithm, which works in stream. + You have to "copy" the uncompressed bytes from the stream, and sometime, + you encounter what I've called "restart blocks" which tells two things: + a backward jump, and a lenght. The jump value tells you of how many bytes + you have to "rewind", and the length tells you how many bytes you have to + copy from there. For example if you have the compressed stream: + + One Ring to rule them all, find. + + then you will decompress it by: + + One Ring to rule them all, One Ring to find them. + + because when you hit the , it tells you to copy 12 bytes from + 27 bytes backward, and when you hit the , it tells you to + copy 5 bytes from 28 bytes backward. + + + +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 + + + +Q: How is the file stored? +A: From a general manner, you have a 4 bytes length to know where to stop + when you are uncompressing. As you may have noticed, you have normal + bytes and compressed blocks. So you can have a bitmap which tells you + if the bytes are normal bytes or restart blocks. As an example, let's + look the Lord of the Rings compression: + + |Bitmaps | Datas + |--------|---------------------------|--------| + |00000000| 4f 6e 65 20 52 69 6e 67 |One Ring| + |00000000| 20 74 6f 20 72 75 6c 65 | to rule| + |00000000| 20 74 68 65 6d 20 61 6c | them al| + |00010000| 6c 2c 20<1b 90>66 69 6e 64|l, ..find| + |10000000|<1b 20>2e |...| + + If you have a 0 in the bitmap, then you know you have to simply copy the + byte you find, and if you have a 1, you have to read the two next bytes, + 'unpack' them to find the backward jump and the length, then copy the + corresponding bytes. As an exercise, try to find how I've 'packed' the + length and the backward jump into the above array. + + Since you need two bytes to write a restart block, you will have to add + three to the unpacked length. + + Here is the final form of the packed file: + +0000: 31 00 00 00 00 4F 6E 65 20 52 69 6E 67 00 20 74 1 One Ring t +0010: 6F 20 72 75 6C 65 00 20 74 68 65 6D 20 61 6C 08 o rule them al. +0020: 6C 2C 20 1B 90 66 69 6E 64 01 1B 20 2E l, ..find.. .. + + Note how the bitmaps are stored. + + + +Q: How are the jump and length packed? +A: You may find infos on the net like: + + O3 O2 O1 O0 L3 L2 L1 L0 | OB OA O9 O8 O7 O6 O5 O4 + + This means that the two infos are packed like this: the offset (jump) has the + four lower bits in the four upper bits of the first byte, then the eight upper + bits are directly stored into the second byte. Thus, the backward jump is + stored on 12 bits. The length is stored in four bits, and they are stored in + the four lower bits of the first byte. So the length may vary from 3 to 18. + + + +Q: What is the relationship between the schemes into the software and the + thing you pasted above? +A: It's quite easy. The computation formula is the following: + + decomp_length = shift(val1 & scheme.l_mask_1, scheme.l_shft_1) | + shift(val2 & scheme.l_mask_2, scheme.l_shft_2); + decomp_jump = shift(val1 & scheme.j_mask_1, scheme.j_shft_1) | + shift(val2 & scheme.j_mask_2, scheme.j_shft_2); + + + So, if you want to write the eight parameters for the above thingy, you + will have to set them to this: + + l_mask_1 = 0x0f | l_mask_2 = 0x00 | j_mask_1 = 0xf0 | j_mask_2 = 0xff + l_shft_1 = 0 | l_shft_2 = 0 | j_shft_1 = -4 | j_shft_2 = 4 + + What is he most difficult to understand is the jump value. We want to build + the jump value as: OB OA O9 O8 O7 O6 O5 O4 O3 O2 O1 O0. + + Let's first work on the first byte. + -) We have to only keep the Ox bits + -) Then we have to move them to the right. + + The mask is here to suppress the unwanted bits. So for our case, the mask is + 0xf0 since it's the four high bits. The shift is here to move the bits. A + negative value means to move them to the right, and a positive means to the + left. So since we have to make the bits go to the four lower bits, we have + a shift of -4 + + For the second byte: + -) We keep all the bits, but + -) we have to make room for the four bits from the first byte. + + The mask don't have to suppress anything, so it's set to 0xff. And now, the + shift is set to 4 to make enough room. + + Finally, the software will build the jump with those four parameters. + + +Q: What are the others parameters? +A: You have: + + 1iscomp overlap negative 16bits ptrb + filling inverse onejump window + + This will change the behaviour of the compression/decompression algorithm. + + The 1iscomp will inverse the bitmap from the default. The default is, a 1 in + the bitmap is uncompressed. + + The overlap is a boolean to tell the compressor to use the overlap trick. + Some roms does use it, but is a little hard to explain here. + + This is the same for the negative trick. + + The 16bits behavior is quite specific to the FF6 PSX. Everything is coded + using 16 bits words instead of 8 bits words. And thus, the compression + algorithm is more difficult. As for now, it's broken. + + The ptrb means "pointer behavior". It can take the value 0, 1 or 2. The + behavior '0' is the common one: the jump is the number of bytes to + count back to find the start of the needle to copy. The '1' is to tell + the jump is an offset from the maximum backward jump possible (ie + from the start point of the window). The '2' is a very dumb behavior: + it tells that the jump is the absolute offset. The window *won't* slide. + + The filling option activates the RLE behavior. + + The inverse is a boolean to tell to reverse the order of the bits in the + bitmaps + + The onejump tells to add one to the final jump value. Some streams are + shifted by one because by default, a jump of 0 means nothing. So it + is dumb to miss one possible backward jump. + + The window offset tells the absolute window start for the 2th pointer + behavior. Yeah, this is necessary. Coders of Metal Max are pretty crazy. + + + +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 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. + + For example, if you have 12 bits for the jump and 4 for the length, you will + have a maximum of 0xfff for the jump and 18 for the length (18 because it's + 0xf + 3) + + Here comes the negative trick: when you are uncompressing the first bytes, + you will still be able to have a jump which is *beyond* the beginning of the + decompressed file. Later, when your file will grow up, this won't be possible + anymore of course, since its size will be over the maximum jump size. + + So, sometime, you can consider that *if* you have a negative value, it's not + a fault: you just read zeros. Understood? BTW, most of the case, the negative + restart will be very near the begin of the file. So if you have to copy five + bytes distant of 1000 bytes from the beginning of the file, *this* is + probably a fault, or a misunderstood scheme. + + + Next, the overlap trick. It's more difficult to understand though. You have + to understand the decompressor's algorithm a bit. When it hits a restart + block, it computes the jump and the length, then it will begin to copy the + bytes from the old decompressed datas, one byte after the other. + + So the trick is here: when you are copying the bytes, the algorithm will + be able to reuse them immediately for the current copy, since they are + already written. The restart block will use "itself". + + Let's have an example: + + If you want to compress the stream: + + 123123123123 + + you will have two solutions. Either with, either without the overlap trick. + Without the overlap trick, here is the compressed stream: + + 123123 + + This is obvious hu? Now, with the overlap trick: + + 123 + + Try to take a piece of paper and to decompress those two thingy, maybe this + will help you understand. + + + +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 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 lzss stream was created, but the decompression + algorithm used by the game *maybe* is able to handle them. + + + +Q: What is the filling thing? +A: It's an RLE like behavior. In Valkyrie Profile, when the length hit the + maximum value, then it means it's a RLE block, and not a restart block. + That's why you've got the eight options: + + + fmask1 fshft1 fmask2 fshft2 vmask1 vshft1 vmask2 vshft2 + + Basically, they are the same as the {j,l}{mask,shft}{1,2} options, but + this time you tell where to find the 'value' which has to be copied, + and the 'filling', ie the number of times this value will be copied. + + +Q: What is the 2th filling behaviour? +A: Get out of here. It's a ugly ugly ugly hack. Forget it. Now! + + diff --git a/Makefile b/Makefile index 1fef412..f285d59 100755 --- a/Makefile +++ b/Makefile @@ -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 #include -#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-dlz77.cpp deleted file mode 100644 index 98373a6..0000000 --- a/Xenogears/test-dlz77.cpp +++ /dev/null @@ -1,7 +0,0 @@ -#include -#include "lz77.h" - -int main(void) { - lz77_decomp(0, 1); - return 0; -} diff --git a/Xenogears/test-dlzss.cpp b/Xenogears/test-dlzss.cpp new file mode 100644 index 0000000..ecd0f7e --- /dev/null +++ b/Xenogears/test-dlzss.cpp @@ -0,0 +1,7 @@ +#include +#include "lzss.h" + +int main(void) { + lzss_decomp(0, 1); + return 0; +} diff --git a/Xenogears/test-lz77.cpp b/Xenogears/test-lz77.cpp deleted file mode 100644 index 8efce98..0000000 --- a/Xenogears/test-lz77.cpp +++ /dev/null @@ -1,7 +0,0 @@ -#include -#include "lz77.h" - -int main(void) { - lz77_comp(0, 1); - return 0; -} diff --git a/Xenogears/test-lzss.cpp b/Xenogears/test-lzss.cpp new file mode 100644 index 0000000..0257e99 --- /dev/null +++ b/Xenogears/test-lzss.cpp @@ -0,0 +1,7 @@ +#include +#include "lzss.h" + +int main(void) { + 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) { diff --git a/lz77.cpp b/lz77.cpp deleted file mode 100644 index 10423d4..0000000 --- a/lz77.cpp +++ /dev/null @@ -1,799 +0,0 @@ -/* - * 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 -#include "fileutils.h" -#include "generic.h" -#include "lz77.h" - -int lz77_maxsize = 18; -int lz77_maxptr = 0x0fff; -int tolerate = 1; -int blockb = 0; - -scheme_t 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 */ - {"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}, - {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} -}; - -scheme_t scheme = schemes[0]; - -char swap_bits(char 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 shift(unsigned int c, int s) { - return s > 0 ? (c << s) : c >> (-s); -} - -void compute_limits(void) { - unsigned char val1, val2; - - val1 = val2 = 0xff; - - lz77_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) | - shift(val2 & scheme.j_mask_2, scheme.j_shft_2); - - lz77_maxsize = lz77_maxsize + 3 + scheme.sixteen_bits; - lz77_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", lz77_maxsize, lz77_maxptr); -} - -unsigned long lz77_decomp(FILE * f_source, FILE * f_cible, long 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; - 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; - long length, reads; - - compute_limits(); - - fread(&length, 1, 4, f_source); - 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 { - fread(&bitmap, 1, 1, f_source); - if (scheme.sixteen_bits) { - fread(&fbitmap, 1, 1, f_source); - printm(M_INFO, "16bits behavior, false bitmap = %02x\n", fbitmap); - } - if (scheme.bitmap_inversed) { - bitmap = swap_bits(bitmap); - } - printm(M_INFO, "Begin of block, bitmap = %02x\n", bitmap); - for (i = 0; i < 8; i++) { - printm(M_INFO, " - Chunk %i (offset cible = %li = 0x%04x, offset source = %li = 0x%04x)\n", i, ftell(f_cible), ftell(f_cible), ftell(f_source), ftell(f_source)); - if (whole_count >= length) - break; - if ((bitmap & 1) ^ scheme.one_is_compressed) { - for (j = 0; j < (scheme.sixteen_bits ? 2 : 1); j++) { - reads = fread(&valeur, 1, 1, f_source); - if (!reads) { - printm(M_WARNING, " WARNING! PADDING!\n"); - free(text_buf); - return length; - } - printm(M_INFO, " Copying 0x%02x\n", valeur); - fwrite(&valeur, 1, 1, f_cible); - text_buf[r++] = valeur; - whole_count++; - } - } else { - fread(&val1, 1, 1, f_source); - fread(&val2, 1, 1, f_source); - 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 &= lz77_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_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); - 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++) { - fwrite(&valeur, 1, 1, f_cible); - 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 - lz77_maxptr - 1 + decomp_jump; - break; - case 2: - decomp_offset = decomp_jump - scheme.window_start; - break; - } - 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; - fwrite(&valeur, 1, 1, f_cible); - 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 { - fwrite(&text_buf[decomp_count], 1, 1, f_cible); - 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 lz77_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) { - char redo[256]; - long length, i, p, ptr, maxlength; - - i = 1; - redo[0] = p = 0; - while (i < lz77_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] == lz77_rd(r, i)) { - if (p == (lz77_maxsize - 1)) { - *l = lz77_maxsize; - return i - lz77_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; -} - -long blk, bitmap_count; - -unsigned char * lz77_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; - 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 - lz77_maxptr; - farest = farest > ((-lz77_maxsize) * scheme.negative_trick) ? farest : -lz77_maxsize * scheme.negative_trick; - needle_length = ptr - farest; - if (scheme.ptrb == 2) { - farest = 0; - needle_length = MIN(lz77_maxptr - scheme.window_start, ptr); - } - needle = lz77_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, 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_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 = lz77_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 lz77_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); - if (delta) { - length += *delta; - } - fwrite(&length, 1, 4, f_cible); - if (delta) { - length -= *delta; - } - fwrite(c, 1, l, f_cible); - free(c); - free(r); -} - -#ifdef LZ77_MAIN - -char * fn1, * fn2, * pname; - -int lga = 0; -int compress = 1; - -struct option long_options[] = { - {"1iscomp", 1, &lga, 1 }, - {"overlap", 1, &lga, 2 }, - {"16bits", 1, &lga, 11 }, - {"negative", 1, &lga, 12 }, - {"ptrb", 1, &lga, 13 }, - {"filling", 1, &lga, 14 }, - {"inverse", 1, &lga, 23 }, - {"onejump", 1, &lga, 24 }, - {"window", 1, &lga, 25 }, - {"lmask1", 1, &lga, 3 }, - {"lshft1", 1, &lga, 4 }, - {"lmask2", 1, &lga, 5 }, - {"lshft2", 1, &lga, 6 }, - {"jmask1", 1, &lga, 7 }, - {"jshft1", 1, &lga, 8 }, - {"jmask2", 1, &lga, 9 }, - {"jshft2", 1, &lga, 10 }, - {"fmask1", 1, &lga, 15 }, - {"fshft1", 1, &lga, 16 }, - {"fmask2", 1, &lga, 17 }, - {"fshft2", 1, &lga, 18 }, - {"vmask1", 1, &lga, 19 }, - {"vshft1", 1, &lga, 20 }, - {"vmask2", 1, &lga, 21 }, - {"vshft2", 1, &lga, 22 }, - {"help", 0, NULL, 'h'}, - {"scheme", 1, NULL, 's'}, - {"length", 1, NULL, 'l'}, - {"version", 0, NULL, 'V'}, - {"verbose", 0, NULL, 'v'}, - {"show", 0, NULL, 'S'}, - {"dump", 0, NULL, 'D'}, - {"compress", 0, NULL, 'c'}, - {"decompress", 0, NULL, 'd'}, - {"blocks", 0, NULL, 'b'}, - {0, 0, NULL, 0 } -}; - -void showhelp(void) { - printm(M_BARE, -"Usages:\n" -" %s <--help|-h|-H|-?> Show this help and exit.\n" -" %s <--dump> Show the built-in schemes and exit.\n" -" %s <--version|-V> Show the version and copyrights and exit.\n" -" %s [-c|-d] [-s ] [-l ] [-S] [-v] \n" -"\n" -"-c --compress Compress to \n" -"-d --decompress Decompress to \n" -"-s --scheme= Loads the built-in scheme number \n" -"-l --length= Specify the true length for decompression,\n" -" or enable the padding behavior for compression.\n" -"-S --show Show the actual scheme before processing.\n" -"-v --verbose Display a *LOT* of informations.\n" -"-b --blocks Switch to blocks decompression behaviour\n" -"\n" -"Additionnaly you have the scheme manipulation options:\n" -"--1iscomp --overlap --negative --16bits --ptrb\n" -"--filling --inverse --onejump --window\n" -"--lmask1 --lshft1 --lmask2 --lshft2 --jmask1 --jshft1 --jmask2 --jshft2\n" -"--vmask1 --vshft1 --vmask2 --vshft2 --fmask1 --fshft1 --fmask2 --fshft2\n" -"\n" -"If you don't know what they are, forget them.\n" -"\n" -"Default behavior is to %scompress.\n" -"\n", pname, pname, pname, pname, compress ? "" : "de"); -} - -void showscheme(void) { - printm(M_BARE, -"Actual scheme:\n" -"--1iscomp %i\n" -"--overlap %i\n" -"--negative %i\n" -"--16bits %i\n" -"--ptrb %i\n" -"--filling %i\n" -"--inverse %i\n" -"--onejump %i\n" -"--window %i\n" -"--lmask1 0x%02x\n" -"--lshft1 %i\n" -"--lmask2 0x%02x\n" -"--lshft2 %i\n" -"--jmask1 0x%02x\n" -"--jshft1 %i\n" -"--jmask2 0x%02x\n" -"--jshft2 %i\n" -"--fmask1 0x%02x\n" -"--fshft1 %i\n" -"--fmask2 0x%02x\n" -"--fshft2 %i\n" -"--vmask1 0x%02x\n" -"--vshft1 %i\n" -"--vmask2 0x%02x\n" -"--vshft2 %i\n" -"\n", scheme.one_is_compressed, scheme.overlap_trick, scheme.negative_trick, scheme.sixteen_bits, -scheme.ptrb, scheme.filling, scheme.bitmap_inversed, scheme.one_jump, scheme.window_start, -scheme.l_mask_1, scheme.l_shft_1, scheme.l_mask_2, scheme.l_shft_2, -scheme.j_mask_1, scheme.j_shft_1, scheme.j_mask_2, scheme.j_shft_2, -scheme.f_mask_1, scheme.f_shft_1, scheme.f_mask_2, scheme.f_shft_2, -scheme.v_mask_1, scheme.v_shft_1, scheme.v_mask_2, scheme.v_shft_2); -} - -void dump(void) { - int i; - - printm(M_BARE, "Built-in schemes:\n"); - for (i = 0; schemes[i].name; i++) { - printm(M_BARE, "%2i - %s\n", i, schemes[i].name); - } -} - -int main(int argc, char ** argv) { - long length = -1; - FILE * f1, * f2; - int p, show = 0; - int c, s, t; - - pname = strdup(argv[0]); - p = strlen(pname) - 5; - - verbosity = M_STATUS; - - if (!strcasecmp(pname + p, "dlz77")) { - compress = 0; - } - - printm(M_BARE, -LZ77_NAME " compressor/decompressor version " LZ77_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" -"Special thanks to Yazoo, who taught me PSX hacking.\n" -"\n"); - - while ((c = getopt_long(argc, argv, "Hhs:l:vVScdb", long_options, NULL)) != EOF) { - switch (c) { - case 0: - switch (lga) { - case 1: - t = atoi(optarg); - if ((t != 1) && (t != 0)) { - printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); - } else { - scheme.one_is_compressed = t; - } - break; - case 2: - t = atoi(optarg); - if ((t != 1) && (t != 0)) { - printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); - } else { - scheme.overlap_trick = t; - } - break; - case 3: - sscanf(optarg, "%i", &scheme.l_mask_1); - break; - case 4: - scheme.l_shft_1 = atoi(optarg); - break; - case 5: - sscanf(optarg, "%i", &scheme.l_mask_2); - break; - case 6: - scheme.l_shft_2 = atoi(optarg); - break; - case 7: - sscanf(optarg, "%i", &scheme.j_mask_1); - break; - case 8: - scheme.j_shft_1 = atoi(optarg); - break; - case 9: - sscanf(optarg, "%i", &scheme.j_mask_2); - break; - case 10: - scheme.j_mask_2 = atoi(optarg); - break; - case 11: - t = atoi(optarg); - if ((t != 1) && (t != 0)) { - printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); - } else { - scheme.sixteen_bits = t; - } - break; - case 12: - t = atoi(optarg); - if ((t != 1) && (t != 0)) { - printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); - } else { - scheme.negative_trick = t; - } - break; - case 13: - t = atoi(optarg); - if ((t != 2) && (t != 1) && (t != 0)) { - printm(M_ERROR, "Invalid value for ter: %s\n", optarg); - } else { - scheme.ptrb = t; - } - break; - case 14: - t = atoi(optarg); - if ((t != 2) && (t != 1) && (t != 0)) { - printm(M_ERROR, "Invalid value for ter: %s\n", optarg); - } else { - scheme.filling = t; - } - break; - case 15: - sscanf(optarg, "%i", &scheme.f_mask_1); - break; - case 16: - scheme.f_shft_1 = atoi(optarg); - break; - case 17: - sscanf(optarg, "%i", &scheme.f_mask_2); - break; - case 18: - scheme.f_shft_2 = atoi(optarg); - break; - case 19: - sscanf(optarg, "%i", &scheme.v_mask_1); - break; - case 20: - scheme.v_shft_1 = atoi(optarg); - break; - case 21: - sscanf(optarg, "%i", &scheme.v_mask_2); - break; - case 22: - scheme.v_mask_2 = atoi(optarg); - break; - case 23: - t = atoi(optarg); - if ((t != 1) && (t != 0)) { - printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); - } else { - scheme.bitmap_inversed = t; - } - break; - case 24: - t = atoi(optarg); - if ((t != 1) && (t != 0)) { - printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); - } else { - scheme.one_jump = t; - } - break; - case 25: - t = sscanf(optarg, "%i", &scheme.window_start); - break; - default: - showhelp(); - printm(M_ERROR, "Unknow option.\n"); - exit(-1); - } - break; - case '?': - case 'H': - case 'h': - showhelp(); - exit(0); - case 's': - s = atoi(optarg); - scheme = schemes[s]; - break; - case 'l': - length = atoi(optarg); - break; - case 'v': - verbosity = M_INFO; - break; - case 'V': - exit(0); - case 'S': - show = 1; - break; - case 'D': - dump(); - exit(0); - break; - case 'd': - compress = 0; - break; - case 'c': - compress = 1; - break; - case 'b': - blockb = 1; - break; - default: - showhelp(); - printm(M_ERROR, "Unknow option.\n"); - exit(-1); - } - } - - if (show) showscheme(); - - if (optind != (argc - 2)) { - if (optind > (argc - 2)) { - printm(M_ERROR, "Not enough filenames\n"); - exit(-1); - } else { - printm(M_ERROR, "Too much arguments\n"); - exit(-1); - } - } - - fn1 = argv[optind++]; - fn2 = argv[optind++]; - - if (!(f1 = fopen(fn1, "r"))) { - printm(M_ERROR, "Error opening file %s for reading.\n", fn1); - } - - if (!(f2 = fopen(fn2, "w"))) { - printm(M_ERROR, "Error opening file %s for writing.\n", fn2); - } - - if (compress) { - printm(M_STATUS, "Compressing `%s' to `%s'...\n", fn1, fn2); - } else { - printm(M_STATUS, "Decompressing `%s' to `%s'...\n", fn1, fn2); - } - - if (compress) { - if (length == -1) { - lz77_comp(f1, f2); - } else { - lz77_comp(f1, f2, &length); - } - } else { - length = lz77_decomp(f1, f2, length); - } - - printm(M_STATUS, "Done, filesize changed from %i to %i.\n", filesize(f1), filesize(f2)); - if (!bitmap_count) - bitmap_count = 8; - if (compress) - printm(M_STATUS, "Compressed %i = 0x%08x blocs, containing %i = 0x%08x chunks.\n", blk + 1, blk + 1, blk * 8 + bitmap_count, blk * 8 + bitmap_count); - - fclose(f1); - fclose(f2); - - exit(0); -} - -#endif diff --git a/lz77.h b/lz77.h deleted file mode 100644 index 34888c5..0000000 --- a/lz77.h +++ /dev/null @@ -1,62 +0,0 @@ -/* - * 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 - */ - -#ifndef __LZ77_H__ -#define __lZ77_H__ - -#include -#include - -#define LZ77_VERSION "3.0.0-pre1" -#define LZ77_NAME "LZ77" - -typedef struct { - char * name; - int one_is_compressed, bitmap_inversed, one_jump, overlap_trick, negative_trick, sixteen_bits, ptrb, filling; - int window_start; - int l_mask_1, l_shft_1, l_mask_2, l_shft_2; - int j_mask_1, j_shft_1, j_mask_2, j_shft_2; - int f_mask_1, f_shft_1, f_mask_2, f_shft_2; - int v_mask_1, v_shft_1, v_mask_2, v_shft_2; -} scheme_t; - -enum { - XENO = 0, - DBZ, - FF7, - LM, - MM, - OB, - LODOSS, - FF6, - VP_1, - VP_2, - END -}; - -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); - -char swap_bits(char); - -#endif diff --git a/lzss.cpp b/lzss.cpp new file mode 100644 index 0000000..6e19bf3 --- /dev/null +++ b/lzss.cpp @@ -0,0 +1,799 @@ +/* + * 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 +#include "fileutils.h" +#include "generic.h" +#include "lzss.h" + +int lzss_maxsize = 18; +int lzss_maxptr = 0x0fff; +int tolerate = 1; +int blockb = 0; + +scheme_t 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 */ + {"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}, + {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} +}; + +scheme_t scheme = schemes[0]; + +char swap_bits(char 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 shift(unsigned int c, int s) { + return s > 0 ? (c << s) : c >> (-s); +} + +void 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 long lzss_decomp(FILE * f_source, FILE * f_cible, long 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; + 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; + long length, reads; + + compute_limits(); + + fread(&length, 1, 4, f_source); + 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 { + fread(&bitmap, 1, 1, f_source); + if (scheme.sixteen_bits) { + fread(&fbitmap, 1, 1, f_source); + printm(M_INFO, "16bits behavior, false bitmap = %02x\n", fbitmap); + } + if (scheme.bitmap_inversed) { + bitmap = swap_bits(bitmap); + } + printm(M_INFO, "Begin of block, bitmap = %02x\n", bitmap); + for (i = 0; i < 8; i++) { + printm(M_INFO, " - Chunk %i (offset cible = %li = 0x%04x, offset source = %li = 0x%04x)\n", i, ftell(f_cible), ftell(f_cible), ftell(f_source), ftell(f_source)); + if (whole_count >= length) + break; + if ((bitmap & 1) ^ scheme.one_is_compressed) { + for (j = 0; j < (scheme.sixteen_bits ? 2 : 1); j++) { + reads = fread(&valeur, 1, 1, f_source); + if (!reads) { + printm(M_WARNING, " WARNING! PADDING!\n"); + free(text_buf); + return length; + } + printm(M_INFO, " Copying 0x%02x\n", valeur); + fwrite(&valeur, 1, 1, f_cible); + text_buf[r++] = valeur; + whole_count++; + } + } else { + fread(&val1, 1, 1, f_source); + fread(&val2, 1, 1, f_source); + 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; + decomp_jump += scheme.one_jump; + decomp_length = decomp_length + 3 + scheme.sixteen_bits; + decomp_fill = decomp_fill + 3 + scheme.sixteen_bits; + 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); + 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++) { + fwrite(&valeur, 1, 1, f_cible); + 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; + break; + case 2: + decomp_offset = decomp_jump - scheme.window_start; + break; + } + 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; + fwrite(&valeur, 1, 1, f_cible); + 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 { + fwrite(&text_buf[decomp_count], 1, 1, f_cible); + 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_rd(unsigned char * t, long p) { + return ((p < 0) ? 0 : (t[p])); +} + +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 < 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; +} + +long blk, bitmap_count; + +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; + 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_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 = lzss_memcomp(r, &l, delta); + if (delta) { + length += *delta; + } + fwrite(&length, 1, 4, f_cible); + if (delta) { + length -= *delta; + } + fwrite(c, 1, l, f_cible); + free(c); + free(r); +} + +#ifdef lzss_MAIN + +char * fn1, * fn2, * pname; + +int lga = 0; +int compress = 1; + +struct option long_options[] = { + {"1iscomp", 1, &lga, 1 }, + {"overlap", 1, &lga, 2 }, + {"16bits", 1, &lga, 11 }, + {"negative", 1, &lga, 12 }, + {"ptrb", 1, &lga, 13 }, + {"filling", 1, &lga, 14 }, + {"inverse", 1, &lga, 23 }, + {"onejump", 1, &lga, 24 }, + {"window", 1, &lga, 25 }, + {"lmask1", 1, &lga, 3 }, + {"lshft1", 1, &lga, 4 }, + {"lmask2", 1, &lga, 5 }, + {"lshft2", 1, &lga, 6 }, + {"jmask1", 1, &lga, 7 }, + {"jshft1", 1, &lga, 8 }, + {"jmask2", 1, &lga, 9 }, + {"jshft2", 1, &lga, 10 }, + {"fmask1", 1, &lga, 15 }, + {"fshft1", 1, &lga, 16 }, + {"fmask2", 1, &lga, 17 }, + {"fshft2", 1, &lga, 18 }, + {"vmask1", 1, &lga, 19 }, + {"vshft1", 1, &lga, 20 }, + {"vmask2", 1, &lga, 21 }, + {"vshft2", 1, &lga, 22 }, + {"help", 0, NULL, 'h'}, + {"scheme", 1, NULL, 's'}, + {"length", 1, NULL, 'l'}, + {"version", 0, NULL, 'V'}, + {"verbose", 0, NULL, 'v'}, + {"show", 0, NULL, 'S'}, + {"dump", 0, NULL, 'D'}, + {"compress", 0, NULL, 'c'}, + {"decompress", 0, NULL, 'd'}, + {"blocks", 0, NULL, 'b'}, + {0, 0, NULL, 0 } +}; + +void showhelp(void) { + printm(M_BARE, +"Usages:\n" +" %s <--help|-h|-H|-?> Show this help and exit.\n" +" %s <--dump> Show the built-in schemes and exit.\n" +" %s <--version|-V> Show the version and copyrights and exit.\n" +" %s [-c|-d] [-s ] [-l ] [-S] [-v] \n" +"\n" +"-c --compress Compress to \n" +"-d --decompress Decompress to \n" +"-s --scheme= Loads the built-in scheme number \n" +"-l --length= Specify the true length for decompression,\n" +" or enable the padding behavior for compression.\n" +"-S --show Show the actual scheme before processing.\n" +"-v --verbose Display a *LOT* of informations.\n" +"-b --blocks Switch to blocks decompression behaviour\n" +"\n" +"Additionnaly you have the scheme manipulation options:\n" +"--1iscomp --overlap --negative --16bits --ptrb\n" +"--filling --inverse --onejump --window\n" +"--lmask1 --lshft1 --lmask2 --lshft2 --jmask1 --jshft1 --jmask2 --jshft2\n" +"--vmask1 --vshft1 --vmask2 --vshft2 --fmask1 --fshft1 --fmask2 --fshft2\n" +"\n" +"If you don't know what they are, forget them.\n" +"\n" +"Default behavior is to %scompress.\n" +"\n", pname, pname, pname, pname, compress ? "" : "de"); +} + +void showscheme(void) { + printm(M_BARE, +"Actual scheme:\n" +"--1iscomp %i\n" +"--overlap %i\n" +"--negative %i\n" +"--16bits %i\n" +"--ptrb %i\n" +"--filling %i\n" +"--inverse %i\n" +"--onejump %i\n" +"--window %i\n" +"--lmask1 0x%02x\n" +"--lshft1 %i\n" +"--lmask2 0x%02x\n" +"--lshft2 %i\n" +"--jmask1 0x%02x\n" +"--jshft1 %i\n" +"--jmask2 0x%02x\n" +"--jshft2 %i\n" +"--fmask1 0x%02x\n" +"--fshft1 %i\n" +"--fmask2 0x%02x\n" +"--fshft2 %i\n" +"--vmask1 0x%02x\n" +"--vshft1 %i\n" +"--vmask2 0x%02x\n" +"--vshft2 %i\n" +"\n", scheme.one_is_compressed, scheme.overlap_trick, scheme.negative_trick, scheme.sixteen_bits, +scheme.ptrb, scheme.filling, scheme.bitmap_inversed, scheme.one_jump, scheme.window_start, +scheme.l_mask_1, scheme.l_shft_1, scheme.l_mask_2, scheme.l_shft_2, +scheme.j_mask_1, scheme.j_shft_1, scheme.j_mask_2, scheme.j_shft_2, +scheme.f_mask_1, scheme.f_shft_1, scheme.f_mask_2, scheme.f_shft_2, +scheme.v_mask_1, scheme.v_shft_1, scheme.v_mask_2, scheme.v_shft_2); +} + +void dump(void) { + int i; + + printm(M_BARE, "Built-in schemes:\n"); + for (i = 0; schemes[i].name; i++) { + printm(M_BARE, "%2i - %s\n", i, schemes[i].name); + } +} + +int main(int argc, char ** argv) { + long length = -1; + FILE * f1, * f2; + int p, show = 0; + int c, s, t; + + pname = strdup(argv[0]); + p = strlen(pname) - 5; + + verbosity = M_STATUS; + + if (!strcasecmp(pname + p, "dlzss")) { + compress = 0; + } + + printm(M_BARE, +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 'lzss' schemes FAQ.\n" +"Special thanks to Yazoo, who taught me PSX hacking.\n" +"\n"); + + while ((c = getopt_long(argc, argv, "Hhs:l:vVScdb", long_options, NULL)) != EOF) { + switch (c) { + case 0: + switch (lga) { + case 1: + t = atoi(optarg); + if ((t != 1) && (t != 0)) { + printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); + } else { + scheme.one_is_compressed = t; + } + break; + case 2: + t = atoi(optarg); + if ((t != 1) && (t != 0)) { + printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); + } else { + scheme.overlap_trick = t; + } + break; + case 3: + sscanf(optarg, "%i", &scheme.l_mask_1); + break; + case 4: + scheme.l_shft_1 = atoi(optarg); + break; + case 5: + sscanf(optarg, "%i", &scheme.l_mask_2); + break; + case 6: + scheme.l_shft_2 = atoi(optarg); + break; + case 7: + sscanf(optarg, "%i", &scheme.j_mask_1); + break; + case 8: + scheme.j_shft_1 = atoi(optarg); + break; + case 9: + sscanf(optarg, "%i", &scheme.j_mask_2); + break; + case 10: + scheme.j_mask_2 = atoi(optarg); + break; + case 11: + t = atoi(optarg); + if ((t != 1) && (t != 0)) { + printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); + } else { + scheme.sixteen_bits = t; + } + break; + case 12: + t = atoi(optarg); + if ((t != 1) && (t != 0)) { + printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); + } else { + scheme.negative_trick = t; + } + break; + case 13: + t = atoi(optarg); + if ((t != 2) && (t != 1) && (t != 0)) { + printm(M_ERROR, "Invalid value for ter: %s\n", optarg); + } else { + scheme.ptrb = t; + } + break; + case 14: + t = atoi(optarg); + if ((t != 2) && (t != 1) && (t != 0)) { + printm(M_ERROR, "Invalid value for ter: %s\n", optarg); + } else { + scheme.filling = t; + } + break; + case 15: + sscanf(optarg, "%i", &scheme.f_mask_1); + break; + case 16: + scheme.f_shft_1 = atoi(optarg); + break; + case 17: + sscanf(optarg, "%i", &scheme.f_mask_2); + break; + case 18: + scheme.f_shft_2 = atoi(optarg); + break; + case 19: + sscanf(optarg, "%i", &scheme.v_mask_1); + break; + case 20: + scheme.v_shft_1 = atoi(optarg); + break; + case 21: + sscanf(optarg, "%i", &scheme.v_mask_2); + break; + case 22: + scheme.v_mask_2 = atoi(optarg); + break; + case 23: + t = atoi(optarg); + if ((t != 1) && (t != 0)) { + printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); + } else { + scheme.bitmap_inversed = t; + } + break; + case 24: + t = atoi(optarg); + if ((t != 1) && (t != 0)) { + printm(M_ERROR, "Invalid value for boolean: %s\n", optarg); + } else { + scheme.one_jump = t; + } + break; + case 25: + t = sscanf(optarg, "%i", &scheme.window_start); + break; + default: + showhelp(); + printm(M_ERROR, "Unknow option.\n"); + exit(-1); + } + break; + case '?': + case 'H': + case 'h': + showhelp(); + exit(0); + case 's': + s = atoi(optarg); + scheme = schemes[s]; + break; + case 'l': + length = atoi(optarg); + break; + case 'v': + verbosity = M_INFO; + break; + case 'V': + exit(0); + case 'S': + show = 1; + break; + case 'D': + dump(); + exit(0); + break; + case 'd': + compress = 0; + break; + case 'c': + compress = 1; + break; + case 'b': + blockb = 1; + break; + default: + showhelp(); + printm(M_ERROR, "Unknow option.\n"); + exit(-1); + } + } + + if (show) showscheme(); + + if (optind != (argc - 2)) { + if (optind > (argc - 2)) { + printm(M_ERROR, "Not enough filenames\n"); + exit(-1); + } else { + printm(M_ERROR, "Too much arguments\n"); + exit(-1); + } + } + + fn1 = argv[optind++]; + fn2 = argv[optind++]; + + if (!(f1 = fopen(fn1, "r"))) { + printm(M_ERROR, "Error opening file %s for reading.\n", fn1); + } + + if (!(f2 = fopen(fn2, "w"))) { + printm(M_ERROR, "Error opening file %s for writing.\n", fn2); + } + + if (compress) { + printm(M_STATUS, "Compressing `%s' to `%s'...\n", fn1, fn2); + } else { + printm(M_STATUS, "Decompressing `%s' to `%s'...\n", fn1, fn2); + } + + if (compress) { + if (length == -1) { + lzss_comp(f1, f2); + } else { + lzss_comp(f1, f2, &length); + } + } else { + length = lzss_decomp(f1, f2, length); + } + + printm(M_STATUS, "Done, filesize changed from %i to %i.\n", filesize(f1), filesize(f2)); + if (!bitmap_count) + bitmap_count = 8; + if (compress) + printm(M_STATUS, "Compressed %i = 0x%08x blocs, containing %i = 0x%08x chunks.\n", blk + 1, blk + 1, blk * 8 + bitmap_count, blk * 8 + bitmap_count); + + fclose(f1); + fclose(f2); + + exit(0); +} + +#endif diff --git a/lzss.h b/lzss.h new file mode 100644 index 0000000..e26cfc6 --- /dev/null +++ b/lzss.h @@ -0,0 +1,62 @@ +/* + * 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 + */ + +#ifndef __LZ77_H__ +#define __lZ77_H__ + +#include +#include + +#define LZ77_VERSION "3.0.0-pre1" +#define LZ77_NAME "LZ77" + +typedef struct { + char * name; + int one_is_compressed, bitmap_inversed, one_jump, overlap_trick, negative_trick, sixteen_bits, ptrb, filling; + int window_start; + int l_mask_1, l_shft_1, l_mask_2, l_shft_2; + int j_mask_1, j_shft_1, j_mask_2, j_shft_2; + int f_mask_1, f_shft_1, f_mask_2, f_shft_2; + int v_mask_1, v_shft_1, v_mask_2, v_shft_2; +} scheme_t; + +enum { + XENO = 0, + DBZ, + FF7, + LM, + MM, + OB, + LODOSS, + FF6, + VP_1, + VP_2, + END +}; + +extern scheme_t scheme, schemes[]; + +extern int tolerate; + +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); + +#endif -- cgit v1.2.3