tag:blogger.com,1999:blog-5246987755651065286.post4157370502892654538..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 10-24-11 - LZ Optimal Parse with A Star Part 1cbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-5246987755651065286.post-91813008484799290622011-12-17T02:41:03.451-08:002011-12-17T02:41:03.451-08:00Hi Charles,
Very interesting blog post. Can't ...Hi Charles,<br />Very interesting blog post. Can't wait for part 2, this is really useful stuff.<br /><br />I played around with A* a bit while implementing lzham, but I got caught up on how to implement a decent admissible heuristic so I moved on to lower hanging fruit. <br /><br />-RichRich Geldreichhttps://www.blogger.com/profile/14358203173986928600noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-49004989959540081642011-11-25T07:38:07.158-08:002011-11-25T07:38:07.158-08:00Let me remind you that you still didn't get to...Let me remind you that you still didn't get to A Star. ;)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-90234122340498460112011-10-28T09:25:36.319-07:002011-10-28T09:25:36.319-07:00God damn you blogger make comments editable.God damn you blogger make comments editable.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-53866525580218585632011-10-28T09:25:13.093-07:002011-10-28T09:25:13.093-07:00Yeah, that's Predictor. Of course the decompr...Yeah, that's Predictor. Of course the decompressor is smaller and faster if you do it branchless, something like :<br /><br />// flag is 0 or 1<br />*out++ = flag ? *in : table[hash];<br />in += flag;cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-61766613320063814102011-10-28T02:30:03.597-07:002011-10-28T02:30:03.597-07:00Max possible theoretical would be great, but I'...Max possible theoretical would be great, but I'm not sure how one would start such a search: Even finding 'codes that will produce the given data' is a bit of a problem, as there could be looping code, self-modifying code, some combination of the two, etc. all of which wouldn't just be one-instruction permutations from another...<br /><br />So you couldn't just do a 'toggle this and judge the quality', as the vast majority won't work at all. One could alter instructions to equivalent instructions in some fashion but that wouldn't likely generate a clever decompressor...<br /><br />How would you go about it and/or has someone tried? It might be fun weekend reading, though I have a sneaking suspicion it'd be exponential time ;) Then again, reminded of the title, pathfinding can be too but people do it every day..jfbhttps://www.blogger.com/profile/11281881673668731049noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-25362616052093541232011-10-28T02:01:36.515-07:002011-10-28T02:01:36.515-07:00Charles, I looked up predictor decompressor and ra...Charles, I looked up predictor decompressor and ran into<br /><br />http://tools.ietf.org/html/rfc1978#page-1<br /><br />Is this the kind you were talking about? I just tried compressing some test data and it works shockingly well considering how understandable and simple the algorithm is. I'll give it a try on my device this weekend.jfbhttps://www.blogger.com/profile/11281881673668731049noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-53553688239869201682011-10-27T00:21:42.022-07:002011-10-27T00:21:42.022-07:00liblzf looks huge and over-complicated for this ap...liblzf looks huge and over-complicated for this application.<br /><br />If memcpy is not included, an LZ decoder should be a lot smaller than 50 bytes.<br /><br />A "Predictor" (aka Finnish) decoder can be done in about 10 instructions.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-51250403194507369862011-10-26T23:47:19.456-07:002011-10-26T23:47:19.456-07:00http://www.retroprogramming.com/2009/06/stuff-prog...http://www.retroprogramming.com/2009/06/stuff-programmers-love-to-play-with-1.html puts LZ at <50 bytes for x86Willhttps://www.blogger.com/profile/10665856385463640225noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-73402453927664212512011-10-26T10:30:35.756-07:002011-10-26T10:30:35.756-07:00Interesting; Crinkler assumes that it has tons of ...Interesting; Crinkler assumes that it has tons of memory available at decompress time and takes advantage of that.<br /><br />For the case of tiny data packets, the key will definitely be heavy optimization at encode time.<br /><br />One interesting option if you really want the max possible theoretical win on tiny data packets is you could actually generate the executable code that reproduces that data. Normally that search is impossibly large, but on such tiny data it might be possible.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-44747160098197407262011-10-26T05:29:45.092-07:002011-10-26T05:29:45.092-07:00Matt Mahoney just posted an interesting entry abou...Matt Mahoney just posted an interesting entry about Crinkler, a compressor which tries to do just that : compress little demos (about ~4K) as much as possible, with a decoder code as small as possible.<br /><br />http://encode.ru/threads/1395-Crinkler<br /><br />But even Crinkler is not targeting anything at 100-150 bytes ranges, since it is itself ~210 bytes large. One has to wonder : why trying so much to compress something that little ? What's the expected gain, and aren't there any other budget which might be better target for "savings" ?Cyanhttps://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-46391236384066646242011-10-26T00:45:47.211-07:002011-10-26T00:45:47.211-07:00Charles, I'm not particularly knowledgeable ab...Charles, I'm not particularly knowledgeable about compression, but I'm wondering if you could tell me:<br /><br />About how small can a better-than-RLE decompressor get? liblzf without bounds checking is 70 bytes + memcpy on ARM Thumb 2, for instance. Can one realistically get something simpler/smaller?<br /><br />I've got a few cases where I have 4KB of code space and have been thinking of compressing the .data section (*very* compressible), but with .data being only say 100-150 bytes uncompressed I haven't found any method that pays off significantly once the decompressor is included. Wondering if you might know of any.<br /><br />Thanks<br /><br />Jamesjfbhttps://www.blogger.com/profile/11281881673668731049noreply@blogger.com