Author Topic: Adaptive LZW packer/unpacker  (Read 14050 times)

0 Members and 1 Guest are viewing this topic.

Offline RhoSigma

  • QB64 Developer
  • Forum Resident
  • Posts: 565
    • View Profile
Adaptive LZW packer/unpacker
« 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
« Last Edit: January 31, 2022, 12:20:14 pm by RhoSigma »
My Projects:   https://qb64forum.alephc.xyz/index.php?topic=809
GuiTools - A graphic UI framework (can do multiple UI forms/windows in one program)
Libraries - ImageProcess, StringBuffers (virt. files), MD5/SHA2-Hash, LZW etc.
Bonus - Blankers, QB64/Notepad++ setup pack

FellippeHeitor

  • Guest
Re: Adaptive LZW packer/unpacker
« Reply #1 on: November 15, 2018, 11:53:05 am »
Looks very useful, RhoSigma! Not having to use an external library grants you a bonus point. Thanks for sharing!

Offline codeguy

  • Forum Regular
  • Posts: 174
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #2 on: November 15, 2018, 07:28:52 pm »
Very nice. Better coding than Rich Geldreich's version. THAT was a real pain to refactor into something semi-understandable.

Offline Dav

  • Forum Resident
  • Posts: 792
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #3 on: November 15, 2018, 09:36:36 pm »
Nice work, RhoSigma.  Very handy snippet.  Thanks for sharing it.

- Dav

Offline RhoSigma

  • QB64 Developer
  • Forum Resident
  • Posts: 565
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #4 on: November 16, 2018, 02:21:35 am »
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 :)
« Last Edit: November 16, 2018, 07:28:57 am by RhoSigma »
My Projects:   https://qb64forum.alephc.xyz/index.php?topic=809
GuiTools - A graphic UI framework (can do multiple UI forms/windows in one program)
Libraries - ImageProcess, StringBuffers (virt. files), MD5/SHA2-Hash, LZW etc.
Bonus - Blankers, QB64/Notepad++ setup pack

Offline RhoSigma

  • QB64 Developer
  • Forum Resident
  • Posts: 565
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #5 on: November 16, 2018, 07:26:56 am »
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.
« Last Edit: March 01, 2019, 05:19:39 am by RhoSigma »
My Projects:   https://qb64forum.alephc.xyz/index.php?topic=809
GuiTools - A graphic UI framework (can do multiple UI forms/windows in one program)
Libraries - ImageProcess, StringBuffers (virt. files), MD5/SHA2-Hash, LZW etc.
Bonus - Blankers, QB64/Notepad++ setup pack

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Adaptive LZW packer/unpacker
« Reply #6 on: November 16, 2018, 07:38:46 am »
Why not just compare original size vs compressed size?  If original <= compressed, revert back to uncompressed data.
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline RhoSigma

  • QB64 Developer
  • Forum Resident
  • Posts: 565
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #7 on: November 16, 2018, 08:31:32 am »
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.
« Last Edit: March 01, 2019, 05:20:25 am by RhoSigma »
My Projects:   https://qb64forum.alephc.xyz/index.php?topic=809
GuiTools - A graphic UI framework (can do multiple UI forms/windows in one program)
Libraries - ImageProcess, StringBuffers (virt. files), MD5/SHA2-Hash, LZW etc.
Bonus - Blankers, QB64/Notepad++ setup pack

Offline RonB

  • Newbie
  • Posts: 14
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #8 on: November 19, 2018, 07:47:33 pm »
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

* Screen.MHT (Filesize: 72.83 KB, Downloads: 288)

Offline RhoSigma

  • QB64 Developer
  • Forum Resident
  • Posts: 565
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #9 on: November 19, 2018, 08:19:52 pm »
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.
« Last Edit: June 15, 2019, 04:33:24 pm by RhoSigma »
My Projects:   https://qb64forum.alephc.xyz/index.php?topic=809
GuiTools - A graphic UI framework (can do multiple UI forms/windows in one program)
Libraries - ImageProcess, StringBuffers (virt. files), MD5/SHA2-Hash, LZW etc.
Bonus - Blankers, QB64/Notepad++ setup pack

Offline RhoSigma

  • QB64 Developer
  • Forum Resident
  • Posts: 565
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #10 on: December 09, 2018, 02:44:14 pm »
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.
« Last Edit: January 31, 2022, 12:33:03 pm by RhoSigma »
My Projects:   https://qb64forum.alephc.xyz/index.php?topic=809
GuiTools - A graphic UI framework (can do multiple UI forms/windows in one program)
Libraries - ImageProcess, StringBuffers (virt. files), MD5/SHA2-Hash, LZW etc.
Bonus - Blankers, QB64/Notepad++ setup pack

Offline RhoSigma

  • QB64 Developer
  • Forum Resident
  • Posts: 565
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #11 on: March 01, 2019, 05:51:28 am »
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...
« Last Edit: October 07, 2021, 05:44:48 am by RhoSigma »
My Projects:   https://qb64forum.alephc.xyz/index.php?topic=809
GuiTools - A graphic UI framework (can do multiple UI forms/windows in one program)
Libraries - ImageProcess, StringBuffers (virt. files), MD5/SHA2-Hash, LZW etc.
Bonus - Blankers, QB64/Notepad++ setup pack

FellippeHeitor

  • Guest
Re: Adaptive LZW packer/unpacker
« Reply #12 on: March 01, 2019, 06:15:01 am »
Thanks for the continued support to this library, RhoSigma.

Offline Ashish

  • Forum Resident
  • Posts: 630
  • Never Give Up!
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #13 on: March 03, 2019, 09:50:15 am »
Hi RhoSigma! Thanks for sharing this, it will be useful for me.
if (Me.success) {Me.improve()} else {Me.tryAgain()}


My Projects - https://github.com/AshishKingdom?tab=repositories
OpenGL tutorials - https://ashishkingdom.github.io/OpenGL-Tutorials

Offline RhoSigma

  • QB64 Developer
  • Forum Resident
  • Posts: 565
    • View Profile
Re: Adaptive LZW packer/unpacker
« Reply #14 on: March 03, 2019, 11:26:21 am »
Fellippe, Ashish and everybody else...
Your welcome, guess that's why we're all here in this place :)
« Last Edit: April 22, 2020, 11:03:57 am by RhoSigma »
My Projects:   https://qb64forum.alephc.xyz/index.php?topic=809
GuiTools - A graphic UI framework (can do multiple UI forms/windows in one program)
Libraries - ImageProcess, StringBuffers (virt. files), MD5/SHA2-Hash, LZW etc.
Bonus - Blankers, QB64/Notepad++ setup pack