Compressed enough? - ComputerCraft Forums (archive)

HDeffo #1

213 posts

Posted 15 May 2016 - 08:46 PM

Working on a compressed image format for a bigger super secret project. Here are the current compression levels I am getting on simple "GUI" images. Do you think this is enough or should I keep working on pushing the compression farther?

raw file 2759 bytes

18 49
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
e11111111111111111111111111111111111111111111111e
e11111111111111111111111111111111111111111111111e
e74444444444444444444444444444444444444444444447e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77888888888888888888888888888888888888888888877e
e77777777777777777777777777777777777777777777777e
                                                                                                  
2222222222222222222222222222222222222222222222222
2111111111111111111111111111111111111111111111112
2111111111111111111111111111111111111111111111112
2744444444444444444444444444444444444444444444472
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
2777777777777777777777777777777777777777777777772
3333333333333333333333333333333333333333333333333
2222222222222222222222222222222222222222222222222
2111111111random words go here1111111111111111112
2111111111111111111111111111111111111111111111112
2744444444444444444444444444444444444444444444472
277Hello Worldffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277ffffffffffffffThis is a testfffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
277ffffthis is how tests workfffffffffffffffff772
277fffffffffffffffffffffffffffffffffffffffffff772
2777777777777777777777777777777777777777777777772
I can put text here even though theres no back

compressed file using huffman 732 bytes

V@ÁA ÁAAAAÂÂÂÁAÂABBBÂÁÂÂBBBÂBBBBBBBBÂBBBBBBBBBBBBB H¸ôñÂ9 ì°5ô8JaC&frac14;1 ôC¨C". ~&amp;amp;°Só´7&frac12;c C)!úÆý|:ò&amp;gt; À8D#  ¯&amp;amp;Å'îP¸¤CÁX]ØZ*\)ôè1[($^3yfÀCwðïè~v}ìÿ¨ð!A¡PÃ(TtÀ]÷
~&amp;gt; O"©À¯ì&sup2;"¶ì1c5q7 Ã[ü·
Ù2Áý¥òúÃ%,(¦ d&sup3;üb1f¸À:Þ ,°ü÷Ã£Â ®ÞÞ¡Àä
&sup1;}o4ÆlîÁìëS¯ï5c&amp;amp;maÀE&sup1;[95%Ø#¤&sup2;µVENTBÃî&amp;gt;!¨ä )HAÂèZ#n±.ék+òî%üs»M6OT ·wÞ ¢Ö[üÆÆ[ÞPhéKñegïJAÆÖ5ä°"ØéÍ©0';ßhëj·üìÀTSñÁêILßêbjÂ&sup2;ouÅ]ÁVjêC1êð

compressed file not using Huffman 404 bytes

r{@ØýUr

< äÀ À@  Iè>> 8 ¸ Àp Ø ¿

 @ G À   y ÀIÂ&frac14; N  Àð>> 3A	pä
 	Z3X
 

s y
	
yd

x nuT 
n\

t wcwvsq
qCs pocqg	u)

For anyone who doesn't want to do the math the output is 73% smaller than the raw image. Advantage over just implementing real world file types is that I can store the text foreground and background all in one file.

It looks like Huffman was negatively impacting most images so now it only uses Huffman if it detects a gain in compression from it. Now 85% compression

Edited on 15 May 2016 - 08:18 PM

Bomb Bloke #2

Bomb Bloke's profile picture

7083 posts

Location Tasmania (AU)

Posted 16 May 2016 - 01:17 AM

A lot depends on the context in which these images are to be used. The total size of all the images versus decompression time.

If you were making eg a video player, then you wouldn't want to go overboard. Decompression would take too long if too many images are involved. For something like an OS, which still might use a lot of images, you could get away with more compression because you've got more "idle time" to unpack them in.

One bit of advice, though - do your RLE decompression at render-time, and don't bother to store the unpacked version. Done correctly, you'll actually get the images onto the screen faster by decoding every time you draw them.

HDeffo #3

213 posts

Posted 16 May 2016 - 01:48 AM

Bomb Bloke, on 16 May 2016 - 01:17 AM said:
-snip-

currently it takes 0 ticks for an image of 1000 random characters on text background and foreground. So far time doesn't appear to be a factor in this. Unfortunately in regards to your RLE handling advice while I agree that would be smart the API runs a BWT algorithm before the RLE and while decompressing during runtime for text might be feasible I made a bit based RLE algorithm for colors so decompression time is a tad slower on that and would be better only doing it once than to do it repeatedly

Bomb Bloke #4

Bomb Bloke's profile picture

7083 posts

Location Tasmania (AU)

Posted 16 May 2016 - 03:38 AM

Hmm. It feels a little like cheating, but aiming your base file at package I get ~470 bytes. I reckon if I paired that with an RLE encoder I could chop a decent percentage off that, even without a BWT… Though I'm suspecting you'd rather use all your own code. ;)/> Still, want I should give it a go?

HDeffo #5

213 posts

Posted 16 May 2016 - 03:55 AM

What algorithms does package happen to use?

Bomb Bloke #6

Bomb Bloke's profile picture

7083 posts

Location Tasmania (AU)

Posted 16 May 2016 - 05:30 AM

As far as compression goes, LZW (of the type used in the GIF format). Basically the package API was a stepping stone towards porting my GIF API.

HDeffo #7

213 posts

Posted 16 May 2016 - 06:06 AM

Mind if I borrow your LZW implementation and tweak it instead of reinventing the wheel on it? Might improve my compression a good deal

Bomb Bloke #8

Bomb Bloke's profile picture

7083 posts

Location Tasmania (AU)

Posted 16 May 2016 - 06:44 AM

Go for it. I've just updated the "reduced" version into line with the full one - it's about half the size but only has the compress / decompress / open / lines functions. Depending on your needs you can probably chop out the last two functions too, and perhaps apply a minifier.

HDeffo #9

213 posts

Posted 16 May 2016 - 07:05 AM

Was already planning to use package for Lua brush outputs so heck why not give you one more think to take credit for in my program ;)/> lol