LibCompress

[jjsheets2]

For those who don't know, I have recently added LibCompress to the SVN.

LibCompress is an LZW based encryption algorithm. It is fairly fast. (Less than half a second to compress 20KB of data on my crappy computer at work, about a tenth of a second to decompress the result)

I have tried to make the algorithm as efficient as I possibly could. Compression is lossless, and the ratio depends entirely on the quality of the uncompressed data. As long as the input data does not contain "/000" characters, the output will not have any either, making it suitable for use with AceComm-3.0 and other such libraries.

[Moddington]

Hmmm, if I remember correctly, the data transfer limit is something like 14kb per so long, so this could be pretty handy for addons that need to transfer a lot of data.

[galmok]

Well, I have written a huffman compress/uncompress algorithm and I think we should merge the different algorithm into the same library.

My huffman algorithm encodes about twice as fast as your LZW algorithm, producing better compression on my test data. Decompression is however about same speed as compression, i.e. somewhat slower than your LZW decompression.

Other algorithms may arise and therefore I suggest we implement a simple standard for compressed data, consisting of a 1 byte header to select compression algorithm and the data following the header byte is passed to the appropriate decompression algorithm.

For compression, we could ask for a specific compression algorithm or have LibCompress try all compression algorithms to see if any of the compression methods can compress the data.

My huffman algorithm will in worst cast produce compressed data 1 byte larger then the uncompressed data. That 1 byte is the header byte. Currently I use byte value 0 to indicate uncompressed data and byte value 1 to indicate huffman compressed data.

Example of huffman-compressing 20000 random byte values ranged 0-24 (25 symbols, actual byte values are insignificant):

encoding time: 0.032
decoding time: 0.046
Original size: 20000
Compressed size: 11824
Compression ratio: 0.5912

My algorithms have been optimized for speed. Thereby not saying further optimizations are impossible.

The is a bug in LibCompress right now:

if (#uncompressed > ressize) or (uncompressed:sub(1,1) == "/001") then

should be:

if (#uncompressed > ressize) or (uncompressed:sub(1,1) == "\001") then

If LibCompress was to have several compression methods, your LZW would require a permanent prefix byte value for compressed data. Right now you use "\001" to indicate that data is compressed but if trying to compress data with a \001 prefixed, you get the compressed data stream, even if it is much larger than the uncompressed data:

Compressing 20001 bytes values 0-24 with an initial byte value \001:

encoding time: 0.063
decoding time: 0.031
Original size: 20001
Compressed size: 26658
Compression ratio: 1.3328333583321

Always using a prefix byte will help solve this problem as you will always be able to flag compressed data properly (and be able to compress data regardless of input byte values).

A last problem is compressing the string "" which will cause an error.

If you prefer not to merge the algorithms, I'll have to figure out a good name (was thinking about LibCompress, but now it is taken. )

[galmok]

I put my code here for people to test.

http://pastey.net/87899

[jjsheets2]

Galmok, if you have SVN access, you're welcome to make your proposed changes. I would however suggest the following compression IDs:

\000 - Never used (because communications hates \000 characters)
\001 - Uncompressed
\002 - LZW
\003 - Huffman

Also, if you can get your algorithm to guarantee no \000 characters in compressed output that would be really good for communication uses.

[galmok]

I have no problems with the suggested IDs.

I cannot guarantee that the compressed huffman data does not contain \000 byte values. The huffman algorithm does not operate on byte values as such, but packs words of varying bit-length into bytes for storage. This can result in all sorts of byte values. It is up to a channel-encoder to make sure all byte values can be transmitted over a given communication channel or be stored in savedvariables files.

I would guess encoding all 0 byte values would make the data grow by about 1-2% or so.

[jjsheets2]

Perhaps we should add an option to the compress/decompress functions to guarantee comms safety, changing all occurances of \000 and \001 to \001\255 and \001\001 respectively in the compress code, while converting in the reverse direction in decompress. This way, the user of the library doesn't need to worry about this implementation detail.

Either way it is not too important.

[galmok]

I don't think this is is what a compression algorithm should do. Some addons have their own channel encoding and us messing with the datastream will not be optimal. Keep the things seperate I say.

I haven't any wowace SVN access yet, but may get it eventually.

[yssaril]

honestly the only thing something like this would ever be really used is for communication since memory shouldn't be an issue client side so since we are already messing with strings you might as well finish the job and make them ready for transmission or at least give the option the make them transmittable

hmm just tried it and it didn't do anything to my string

This string is the one i get after using the AceSerializer on my table:

"^1^T^N1^T^SHeader^SSunstrider~`Isle^t^N2^T^Slevel^N3^SDescription^SIf~`there~`is~`only~`one~`lesson~`you~`deign~`to~`remember~`from~`your~`time~`on~`Sunstrider~`Isle,~`let~`it~`be~`this~`-~`control~`your~`thirst~`for~`magic.~`~`It~`is~`a~`thirst~`unending,~`Bust~`-~`you~`must~`absorb~`energy~`to~`survive~`via~`Mana~`Tap,~`and~`you~`must~`control~`how~`you~`release~`it~`via~`Arcane~`Torrent.~`~`Failure~`is~`to~`become~`one~`of~`the~`Wretched...~`hopelessly~`addicted~`and~`insane.~J~JSeek~`out~`creatures~`on~`the~`isle~`that~`have~`mana~`and~`Mana~`Tap~`them.~`~`Learn~`to~`master~`your~`cravings~`of~`power.~`~`When~`you~`have~`sufficiently~`fed,~`return~`to~`me.^Slink^S8346^SChoices^T^N1^T^Slink^S20999^t^N2^T^Slink^S21000^t^N3^T^Slink^S21001^t^t^Slonglink^S|cff40c040|Hquest:8346:3|h[Thirst~`Unending]|h|r^SLeaderBoard^T^N1^T^Sneeded^S6^Stype^Smonster^Scurrent^S3^t^t^SsuggestedGroup^N0^t^N3^T^SDescription^SYour~`effort~`has~`made~`something~`clear~`that,~`honestly,~`I~`wish~`were~`not~`true.~`~`The~`unchecked~`power~`of~`the~`Burning~`Crystals~`has~`maligned~`a~`much~`larger~`swath~`of~`the~`isle's~`natural~`balance~`than~`I~`thought.~`~`We~`must~`now~`take~`on~`more~`unfortunate~`measures~`to~`reclaim~`control.~J~JThe~`nearby~`lynxes~`have~`succumbed~`to~`the~`influence~`of~`the~`crystals,~`and~`they~`must~`be~`put~`down.~`~`Bring~`their~`collars,~`Bust,~`as~`I~`may~`yet~`be~`able~`to~`fashion~`a~`magical~`restraint~`to~`turn~`some~`back~`from~`being~`uncontrolled.^Slink^S8326^Smoney^N50^SsuggestedGroup^N0^Slonglink^S|cff40c040|Hquest:8326:3|h[Unfortunate~`Measures]|h|r^SisComplete^N1^SChoices^T^N1^T^Slink^S20994^t^N2^T^Slink^S20993^t^N3^T^Slink^S20992^t^t^Slevel^N3^SLeaderBoard^T^N1^T^Sneeded^S8^Sdone^N1^Scurrent^S8^Stype^Sitem^t^t^t^N4^T^SLeaderBoard^T^N1^T^Sneeded^S6^Stype^Sitem^Scurrent^S2^t^t^SDescription^SIt's~`a~`shame~`that~`we've~`lost~`control~`of~`many~`of~`the~`creatures~`here~`on~`the~`island.~`~`This~`was~`once~`a~`tranquil~`place~`of~`study~`and~`research.~`~`Now~`it's~`all~`we~`can~`do~`to~`keep~`from~`being~`attacked~`by~`our~`own~`creations!~J~JI'm~`going~`to~`offer~`you~`a~`chance~`to~`receive~`a~`magical~`boon~`in~`exchange~`for~`some~`collecting~`work~`on~`your~`part.~`~`Bring~`me~`a~`stack~`of~`arcane~`slivers~`that~`are~`found~`on~`the~`mana-using~`creatures~`of~`Sunstrider~`Isle,~`and~`I~`will~`cast~`a~`spell~`on~`you~`that~`should~`aid~`your~`adventures~`on~`the~`isle.^Slink^S8336^Slevel^N4^SRewards^T^N1^T^Slink^S20991^t^t^SsuggestedGroup^N0^Slonglink^S|cffffff00|Hquest:8336:4|h[A~`Fistful~`of~`Slivers]|h|r^t^N5^T^SDescription^SWith~`all~`the~`chaos~`happening~`here~`at~`the~`Sunspire,~`I~`haven't~`had~`a~`chance~`to~`collect~`my~`belongings~`I've~`left~`outside~`at~`various~`places~`on~`the~`isle.~`~`I~`must~`maintain~`my~`vigil~`over~`the~`Sunwell~`here,~`so~`I'll~`ask~`you~`to~`collect~`them~`in~`my~`stead.~J~JI~`need~`my~`scrying~`orb,~`my~`scroll~`of~`Scourge~`magic,~`and~`my~`journal.~`~`Use~`this~`satchel~`for~`some~`extra~`space,~`as~`my~`things~`are~`rather~`bulky.~`~`Return~`them~`to~`me~`and~`I'll~`give~`you~`a~`little~`something~`-~`you~`know,~`for~`the~`effort;~`you~`can~`keep~`the~`satchel~`as~`well!^Slink^S8330^Smoney^N75^SsuggestedGroup^N0^Slonglink^S|cffffff00|Hquest:8330:4|h[Solanian's~`Belongings]|h|r^SChoices^T^N1^T^Slink^S20996^t^N2^T^Slink^S20995^t^t^Slevel^N4^SLeaderBoard^T^N1^T^Sneeded^S1^Stype^Sitem^Scurrent^S0^t^N2^T^Sneeded^S1^Stype^Sitem^Scurrent^S0^t^N3^T^Sneeded^S1^Stype^Sitem^Scurrent^S0^t^t^t^N6^T^Slevel^N4^SDescription^SDay~`after~`day~`I~`stand~`here,~`watching,~`waiting.~`~`I've~`been~`accused~`of~`dwelling~`too~`much~`on~`our~`past,~`while~`my~`eyes~`look~`to~`the~`horizon.~`~`But~`it~`is~`my~`firm~`belief~`that~`each~`visitor~`to~`this~`island~`should~`honor~`those~`who~`have~`sacrificed~`all~`so~`that~`they~`may~`continue~`to~`do~`so.~J~JDath'Remar~`Sunstrider~`was~`our~`first~`king.~`~`He~`led~`us~`here~`from~`Kalimdor~`through~`the~`Maelstrom.~J~JSeek~`out~`his~`shrine~`to~`the~`west~`and~`do~`not~`return~`to~`me~`until~`you~`have~`read~`the~`plaque~`upon~`it~`in~`his~`honor.^Slink^S8345^Smoney^N150^Slonglink^S|cffffff00|Hquest:8345:4|h[The~`Shrine~`of~`Dath'Remar]|h|r^SsuggestedGroup^N0^SLeaderBoard^T^N1^T^Sneeded^S1^Stype^Sobject^Scurrent^S0^t^t^t^Scc^S9382c9^t^^"

This string is the return from the above string passed the compression function:

"^1^T^N1^T^SHeader^SSunstrider~`Isle^t^N2^T^Slevel^N3^SDescription^SIf~`there~`is~`only~`one~`lesson~`you~`deign~`to~`remember~`from~`your~`time~`on~`Sunstrider~`Isle,~`let~`it~`be~`this~`-~`control~`your~`thirst~`for~`magic.~`~`It~`is~`a~`thirst~`unending,~`Bust~`-~`you~`must~`absorb~`energy~`to~`survive~`via~`Mana~`Tap,~`and~`you~`must~`control~`how~`you~`release~`it~`via~`Arcane~`Torrent.~`~`Failure~`is~`to~`become~`one~`of~`the~`Wretched...~`hopelessly~`addicted~`and~`insane.~J~JSeek~`out~`creatures~`on~`the~`isle~`that~`have~`mana~`and~`Mana~`Tap~`them.~`~`Learn~`to~`master~`your~`cravings~`of~`power.~`~`When~`you~`have~`sufficiently~`fed,~`return~`to~`me.^Slink^S8346^SChoices^T^N1^T^Slink^S20999^t^N2^T^Slink^S21000^t^N3^T^Slink^S21001^t^t^Slonglink^S|cff40c040|Hquest:8346:3|h[Thirst~`Unending]|h|r^SLeaderBoard^T^N1^T^Sneeded^S6^Stype^Smonster^Scurrent^S3^t^t^SsuggestedGroup^N0^t^N3^T^SDescription^SYour~`effort~`has~`made~`something~`clear~`that,~`honestly,~`I~`wish~`were~`not~`true.~`~`The~`unchecked~`power~`of~`the~`Burning~`Crystals~`has~`maligned~`a~`much~`larger~`swath~`of~`the~`isle's~`natural~`balance~`than~`I~`thought.~`~`We~`must~`now~`take~`on~`more~`unfortunate~`measures~`to~`reclaim~`control.~J~JThe~`nearby~`lynxes~`have~`succumbed~`to~`the~`influence~`of~`the~`crystals,~`and~`they~`must~`be~`put~`down.~`~`Bring~`their~`collars,~`Bust,~`as~`I~`may~`yet~`be~`able~`to~`fashion~`a~`magical~`restraint~`to~`turn~`some~`back~`from~`being~`uncontrolled.^Slink^S8326^Smoney^N50^SsuggestedGroup^N0^Slonglink^S|cff40c040|Hquest:8326:3|h[Unfortunate~`Measures]|h|r^SisComplete^N1^SChoices^T^N1^T^Slink^S20994^t^N2^T^Slink^S20993^t^N3^T^Slink^S20992^t^t^Slevel^N3^SLeaderBoard^T^N1^T^Sneeded^S8^Sdone^N1^Scurrent^S8^Stype^Sitem^t^t^t^N4^T^SLeaderBoard^T^N1^T^Sneeded^S6^Stype^Sitem^Scurrent^S2^t^t^SDescription^SIt's~`a~`shame~`that~`we've~`lost~`control~`of~`many~`of~`the~`creatures~`here~`on~`the~`island.~`~`This~`was~`once~`a~`tranquil~`place~`of~`study~`and~`research.~`~`Now~`it's~`all~`we~`can~`do~`to~`keep~`from~`being~`attacked~`by~`our~`own~`creations!~J~JI'm~`going~`to~`offer~`you~`a~`chance~`to~`receive~`a~`magical~`boon~`in~`exchange~`for~`some~`collecting~`work~`on~`your~`part.~`~`Bring~`me~`a~`stack~`of~`arcane~`slivers~`that~`are~`found~`on~`the~`mana-using~`creatures~`of~`Sunstrider~`Isle,~`and~`I~`will~`cast~`a~`spell~`on~`you~`that~`should~`aid~`your~`adventures~`on~`the~`isle.^Slink^S8336^Slevel^N4^SRewards^T^N1^T^Slink^S20991^t^t^SsuggestedGroup^N0^Slonglink^S|cffffff00|Hquest:8336:4|h[A~`Fistful~`of~`Slivers]|h|r^t^N5^T^SDescription^SWith~`all~`the~`chaos~`happening~`here~`at~`the~`Sunspire,~`I~`haven't~`had~`a~`chance~`to~`collect~`my~`belongings~`I've~`left~`outside~`at~`various~`places~`on~`the~`isle.~`~`I~`must~`maintain~`my~`vigil~`over~`the~`Sunwell~`here,~`so~`I'll~`ask~`you~`to~`collect~`them~`in~`my~`stead.~J~JI~`need~`my~`scrying~`orb,~`my~`scroll~`of~`Scourge~`magic,~`and~`my~`journal.~`~`Use~`this~`satchel~`for~`some~`extra~`space,~`as~`my~`things~`are~`rather~`bulky.~`~`Return~`them~`to~`me~`and~`I'll~`give~`you~`a~`little~`something~`-~`you~`know,~`for~`the~`effort;~`you~`can~`keep~`the~`satchel~`as~`well!^Slink^S8330^Smoney^N75^SsuggestedGroup^N0^Slonglink^S|cffffff00|Hquest:8330:4|h[Solanian's~`Belongings]|h|r^SChoices^T^N1^T^Slink^S20996^t^N2^T^Slink^S20995^t^t^Slevel^N4^SLeaderBoard^T^N1^T^Sneeded^S1^Stype^Sitem^Scurrent^S0^t^N2^T^Sneeded^S1^Stype^Sitem^Scurrent^S0^t^N3^T^Sneeded^S1^Stype^Sitem^Scurrent^S0^t^t^t^N6^T^Slevel^N4^SDescription^SDay~`after~`day~`I~`stand~`here,~`watching,~`waiting.~`~`I've~`been~`accused~`of~`dwelling~`too~`much~`on~`our~`past,~`while~`my~`eyes~`look~`to~`the~`horizon.~`~`But~`it~`is~`my~`firm~`belief~`that~`each~`visitor~`to~`this~`island~`should~`honor~`those~`who~`have~`sacrificed~`all~`so~`that~`they~`may~`continue~`to~`do~`so.~J~JDath'Remar~`Sunstrider~`was~`our~`first~`king.~`~`He~`led~`us~`here~`from~`Kalimdor~`through~`the~`Maelstrom.~J~JSeek~`out~`his~`shrine~`to~`the~`west~`and~`do~`not~`return~`to~`me~`until~`you~`have~`read~`the~`plaque~`upon~`it~`in~`his~`honor.^Slink^S8345^Smoney^N150^Slonglink^S|cffffff00|Hquest:8345:4|h[The~`Shrine~`of~`Dath'Remar]|h|r^SsuggestedGroup^N0^SLeaderBoard^T^N1^T^Sneeded^S1^Stype^Sobject^Scurrent^S0^t^t^t^Scc^S9382c9^t^^"

attached is my SV file i dumped the strings to

[Rabbit]

That's not true.

SavedVariables has a limit on size, and there's also a limit to how long a string can be.

I've encountered both problems previously, in extreme cases while developing addons. I've just changed the way an addon works so that instead of taking up so much savedvariable space, it does a lot more computations ingame, leading to a lot higher CPU usage.

This library could help both those cases.