Log In  

lzw
by GPI
Cart #lzw-1 | 2021-10-30 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
3


I have translated and extend the lua code from here
https://rosettacode.org/wiki/LZW_compression
I tried to reduce the token count, but I wouldn't surprised when someone will shrink it more.

lzw is the codec that for example gif use, it was patented, but it expired 2004.
more information:
https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch

I tested the code with the JELPI-Graphic&Sound data - and it will compress it to 6094 Bytes (from 17152 - ~36%).

With the next update the high-memory above 0x8000 will be useable (at the moment only with a undocumented poke), my plan is to place there 32kbit of graphic and sound data. The problem is, that this memory is not saved and I don't want to store it in the source-code because it is too big.

With this code I can compress the 32kbit and store it in the "rom" (the lower 0x4300 bytes). Create a "build"-cart which fill the 32kbit (for example with the reload()-function from other carts), compress the data and cstore() the compressed data.
Copy the compressed data to the the "game-cart", on start decompress the data in the high-memory-area and copy then the part currently needed in the map/sprite-memory.

About the tape_()-function: Think about it like a "punched tape" - it can be used to store datas with variable bit-size. You can use it also for the "Persistent cart data". Normaly you can place 256 Bytes. When you want for example to save if a door is open or closed, you need only one bit. With this routines you can easily store 256*8 = 2048 Doors. The routine should handle 1 to 16 bit values.

P#99373 2021-10-30 13:10 ( Edited 2021-10-30 18:27)

Thanks for posting this. I've been working on compression for some stuff I'm playing around with. It'll be good to have another compression method to compare with and/or use if/when my own approach isn't working as well as I might like.

P#99377 2021-10-30 15:09

Keep in mind what is really necessary. The best compression is maybe not always the best solution here. I needed something, that can compress 32k in ~17k - less tokens are here more useful than compression.

First I wanted to port deflate (there is a lua-only-code), but there was too many problems like 32bit-values, too big code...

P#99379 2021-10-30 15:15

update a new version.

correct a small bug in the decompress-function:
poke(dest,ord(w)) dest+=1
forgot the ord...

P#99386 2021-10-30 18:28

[Please log in to post a comment]

Follow Lexaloffle:          
Generated 2024-03-28 15:07:06 | 0.011s | Q:15