QB64.org Forum
Active Forums => Programs => Topic started by: RhoSigma on November 15, 2018, 10:13:10 am
-
This new small library provides an adaptive LZW compression algorithm nativly written in QB(64) code, no external libraries are required. The work is based on the examples from Rich Geldreich and other examples from Wikipedia and Rosetta Code. However, it is a complete rewrite from scratch. It's Public Domain, so use as you want, spread it, modify/enhance it or delete it, it's all up to you...
EDIT:
Codeboxes removed ...
This library is now part of my Libraries Collection, which you can download from the bonus stuff section here: https://qb64forum.alephc.xyz/index.php?topic=809
-
Looks very useful, RhoSigma! Not having to use an external library grants you a bonus point. Thanks for sharing!
-
Very nice. Better coding than Rich Geldreich's version. THAT was a real pain to refactor into something semi-understandable.
-
Nice work, RhoSigma. Very handy snippet. Thanks for sharing it.
- Dav
-
Thanks, glad you like it.
And yes codeguy, the Rich Geldreich version from 1992? was one of the sources for this work together with some other Wikipedia examples and Rosetta Code examples. As you pointed out, Geldreich's version was not the best version to understand the internals very well, so I finally decided to rewrite the whole thing from scratch.
And btw. Rich Geldreich? - This seems to me like a pseudonym: Rich (in english) = has a lot of money, Geldreich (in german) = has a lot of money :)
-
FYI - Just did a small final update to the "lzwpacker.bm" code box in the initial post, so if you already saved it to your harddisk, then go and grab it again.
Update:
After doing some more tests with very small data sets, it turned out that it makes no sense to compress those at all. Depending on the amount of repeating bytes in the source it won't do any useful compression. If just one byte value is used, then it must repeat at least 9x (eg. "xxxxxxxxx") to get any compression. If the string have variations (eg. "xxxyxxxyxyxzxzzyxy..."), then no compression did occur with less than 22 bytes source size, and I guess with even more variations this value will raise further.
According to this findings, I changed the LzwPack$() function to immediatly reject any source sizes below 64 bytes.
-
Why not just compare original size vs compressed size? If original <= compressed, revert back to uncompressed data.
-
Why not just compare original size vs compressed size? If original <= compressed, revert back to uncompressed data.
That's basicly exactly what the LzwPack$() function regulary does, even with taking the desired minimum ratio parameter into account. I was just thinking why start reserving memory (DIMing arrays) and start processing, if I know the unsuccessful result prior doing so? As the the check of the source size was already there to check for "= 0", it was no big deal to change it checking for "< 64" instead.
-
I hope it's just me, but when I tried the (newly downloaded) lzwpacker.bm using the (newly downloaded) TestLZW.bas with the input file changed to the Clock1.PNG from the cuckoo clock project (originally obtained from [abandoned, outdated and now likely malicious qb64 dot net website - don’t go there]), I got a really bad result: Line 37 (in main module), invalid function call. Clock1.PNG is ~95KiB and TestLZW says it compressed the file to 0.00 KiB in 3/100ths of a second, but then blew up on the Unpack phase -'cause the input file was empty.
If you can't find the Clock1.PNG or the Cuckoo Clock zip file, I can upload it in a BASFILE style output .bas restore program, if you'd like to test it yourself
FWIW, I discovered this when attempting to modify the MAKEDATA program (which is outstanding) so that it would take an existing image file (i.e. Clock1.PNG) do a _LOADIMAGE (instead of a GET,,file) then compress the image as stored in memory using LZWPacker to create the output .bm file. Then when the target program ran, the .bm function, instead of recreating the external FILE, would recreate the internal image in memory and return its image handle.
Ron
-
Well Ron, the LZW-HowTo.bas is only a dirty quick test using the qb64.exe file, which is big enough to consume some time for packing/unpacking as well as giving a good compression ratio. The example was never intended to be used with other input files, especially much smaller ones or those which don't compress very well. In short LZW-HowTo.bas does no error checking at all.
What happens here, is that PNG files probably do not compress at all, as they usually are already compressed using zlib's deflate algorithm. That's why the compressed file is empty, read the description of the LzwPack$() function and you'll see an empty result is the error condition if not sufficient compression is reached. This condition must of course be handled in an application, which LZW-HowTo.bas does not.
The "illegal function call" just happens in the 'Speed' output line because of a division by zero, you can simply click to continue the program. It simply happens because of the small size of your image (and the fact it doesn't compress). The packer errors out here so quickly, that virtually no time is spend, hence time is zero and when trying to calculate the speed it gives us the illegal function call. (Anyway, i've fixed this behavior by explicitly checking for a zero time and faking it to 0,001 seconds then.)
Once again, LZW-HowTo.bas is a quick'n'dirty poor program to illustrate the lzw packer/unpacker with a known to be working file (qb64.exe).
If you wanna use 'lzwpacker.bm' in your application, then make sure you read the function descriptions and handle the mentioned possible failure results as needed by your application.
-
Hi all,
i've just updated the lzwpacker.bm codebox in the initial post above with an important bugfix related to the GOSUB/RETURN behavior shown here: https://qb64forum.alephc.xyz/index.php?topic=857
So if you use this library, then you should immediatly go and grab the new fixed version to avoid problems.
-
Hi all,
i've just updated the lzwpacker.bm codebox in the initial post above with a new improved version, which now uses signatures and cyclic redundant checksums (CRC32) written by LzwPack$(), so that its counterpart LzwUnpack$() can check if it's really called with compressed data from the LzwPack$() function and also can check the unpacked data for random corruption. Also the signature contains the original data size, which is used by LzwUnpack$() to immediately allocate a sufficient output buffer, hence avoiding the required buffer swapping (while unpacking) of the former library version, which did raise the memory requirements in an unproportional way and did also slow down the unpacking process.
So if you use this library, then you should go and grab the new version to be up to date...
-
Thanks for the continued support to this library, RhoSigma.
-
Hi RhoSigma! Thanks for sharing this, it will be useful for me.
-
Fellippe, Ashish and everybody else...
Your welcome, guess that's why we're all here in this place :)
-
I'm definately gonna find a good use for this in my gui project :)
-
Thank you, it's a very usefull program, RhoSigma !
-
I'm having issues using this program on PNG, ICO, and many other filetypes. Are there specific file types that it doesn't seem to like? Every time I try to compress one of those kinds of files it fails. I have tried many other file types with success on some all the way up to 79% compression. Attached is a screenshot from a program I made using your library. You can see in my results screen that it fails on the PNG but it succeeded on the first file in the list which is a BMP. The error that says "Try lowering the compression value" is just the generic output I made for files that fail.
[ This attachment cannot be displayed inline in 'Print Page' view ]
The source code for my program is attached here:
[ This attachment cannot be displayed inline in 'Print Page' view ]
I did edit your BM file for the LZW library so I could use a zip and unzip function that I made but I don't think that is what is causing the issue. I've even tried using the example you provide in the folder with my files and I get the same results. I'm not sure what could cause the failure.
-
How big are the file sizes of those failing files, you probably don't need to expect files < 100 bytes to compress.
PNG files are usually already compressed with zlib's deflate (same as _DEFLETE$ will use) and hence can't be compressed again.
-
I can't check your program, as the archive is missing the following files needed for compilation:
Open-SaveFile.bi
OpenFile.bm
Replace.bm
open-folder.png.MEM
zip-folder.png.MEM
delete.png.MEM
Once again, there's no restriction on any file formats. However, very small files or those already compressed will probably fail even with a given ratio of 0%.
I see also, that you will run the LzwPacked data thru _DEFLATE$, which is probably of less use either. If the data is once packed with my LZW routine, then another _DEFLATE$ call (which is nothing else than a LZW derivate) will probably don't do much, although I guess the LZW implementation used by _DEFLATE$ is a better optimized algorithm than mine and could squeeze out another percent or two.
-
So sorry for forgetting my includes! I always forget those!
Here is the new zipped folder with the full source. I was able to get a slightly smaller file when I used _DEFLATE$ in the sample you provided so I just decided to leave it in there. I appreciate you making these libraries available for everyone. It's really helping me to expand my programs.
-
:( :( :( Nested includes ??? - Bad idea IMHO.
You quickly lose the overview what libraries/code snippets you finally use in your projects and what files you have to distribute when making your source available to others. This may discourage people, so they never take a look to your projects anymore. You should rather consider to make a dependency note in those include files, which need further files to be included, eg. as I did in my qbdebug.bm file, which also needs qbstdarg.bm and qbstdio.bm to work.
However, here is the next level of missing files (hopefully the last nesting level):
OpenFile.ps1.BM (included by OpenFile.BM)
-
My OpenInclude() recursive code merger might be of help if you want to make one large listing with all the $INCLUDE files in the proper place (even nested, which is when the recursive part is necessary). I believe it has been co-opted with my blessing for InForm and maybe even someone else's projects. Steal freely.
OpenInclude():https://www.qb64.org/forum/index.php?topic=106.msg596#msg596 (https://www.qb64.org/forum/index.php?topic=106.msg596#msg596)
Zom-B did something similar but his could not handle $INCLUDE within $INCLUDE. This situation does happen and I don't consider the practice highly unusual. Felipe seemed happy enough with it and I consider him a tough but fair customer.
-
Actually, that isn't a problem. I've moved on to using only _DEFLATE$ and had smaller files all around without need for anything but getting the file as a string, compressing it, and then using _INFLATE$ to decompress the contents. I store the filename in the compressed file so that when the file is unzipped later it can be renamed to the original filename. Thanks, though. As for the nested '$INCLUDE, it is only necessary if running in 64 bit. Hence the $ELSE in the $IF 32BIT block. Since the open file dialog only works in 32 bit I assumed you wouldn't have been needing to use that file since it calls a PowerShell script anyways and you would probably not trust running a stranger's PowerShell script. Anyways, _DEFLATE$ seems to be more efficient for me as it compresses the files to a fraction of your LzwPack function and hasn't failed on any files due to the nature of my zip and unzip functions that I've edited since my last message to you. I appreciate your time and effort assisting me in debugging my program.
-
My OpenInclude() recursive code merger might be of help if you want to make one large listing with all the $INCLUDE files in the proper place (even nested, which is when the recursive part is necessary). I believe it has been co-opted with my blessing for InForm and maybe even someone else's projects. Steal freely.
OpenInclude():https://www.qb64.org/forum/index.php?topic=106.msg596#msg596 (https://www.qb64.org/forum/index.php?topic=106.msg596#msg596)
Zom-B did something similar but his could not handle $INCLUDE within $INCLUDE. This situation does happen and I don't consider the practice highly unusual. Felipe seemed happy enough with it and I consider him a tough but fair customer.
Excellent little program. Thank you for sharing. Definitely will help me distribute my applications easier and keep everything together so I don't annoy people.
-
... Anyways, _DEFLATE$ seems to be more efficient for me as it compresses the files to a fraction of your LzwPack function ...
Of course _DEFLATE$ is much more efficient and absolutely worth to be used instead of my library, which was programmed when we had no native compression commands in QB64. However, my packing library comes still in handy, when programming with older QB64 versions without native compression support.
I appreciate your time and effort assisting me in debugging my program.
Don't worry, you're welcome...