   Fast Huffman decompression
  I''m trying to come up with a way to store and decompress a Huffman tree for an archive file.I want to avoid any postprocessing of the tree data once it''s loaded into memory. I want the format of the data, when it''s just a chunk of memory, to allow me to decompress stuff *fast*; at the same time, I need to keep memory usage low (I''m looking at something like the GBA as a potential target platform). I think I''ve come up with a solution, but I was wondering if people could take a look and tell me just how optimal it is, and if they can see any improvements.What I''ve got is a sort of ''opcode'' approach. There are two types of node in the tree - leaf and non-leaf nodes - and non-leaf nodes will always have two children. So here''s what I''ve got.Leaf node:''This is a leaf'' opcode (1 byte)Value (1 byte)Non-leaf node:''This is not a leaf'' opcode (1 byte)Offset from start of this node to start of the left child node (1 byte, always positive)Offset from start of this node to start of the right child node (1 byte, always positive)I realise both that the opcodes need only be 1 bit instead of a whole byte, but I''m guessing that messing about with byte boundaries like that would cause more problems than it would solve.I''m also aware that the distance from a parent to a child node can only be 255 bytes; however, even if all the nodes between were non-leaf nodes, that''s still 85 nodes that can fit in there. There''s a maximum of 256 leaf nodes, so the number of nodes between a parent and child should never be more than 85. If it were, then the compression algorithm (which isn''t realtime) could compensate by rearranging the tree.When decompressing:ptr = treeBufferAddress;while(1){ if(IS_NOT_LEAF == *ptr) {  ptr += *(ptr + 1 + getNextBit()); }else{  return *(ptr+1); }}What are the biggest problems I have to watch out for with this? I''m talking about a cache-miss level of problem here.   Richard "Superpig" Fine- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4 | Enginuity5ry. .ibu cy. .y''ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebuPreserve wildlife: pickle a squirrel today! 
  hugi magazine has a number of articles on optimizing various compression algorithms, including huffman, and how to optimize get&putbit routines: hugi mag try issues 12,13,14 and esspecialy 15, and 16,17 ;  That looks fine for a GBA decompressor.  Put it in arm/thumb assembly and it''ll probably decompress at a good speed.  Don''t worry about cache issues on the GBA also, as there isn''t one; there is only a one instruction prefetch, which can be turned off to save battery. ;quote:Original post by Premandrake  That looks fine for a GBA decompressor.  Put it in arm/thumb assembly and it''ll probably decompress at a good speed.  Don''t worry about cache issues on the GBA also, as there isn''t one; there is only a one instruction prefetch, which can be turned off to save battery.   OK, cool. What about other platforms, though? I''m hoping the same archive format can be used on GBA, PC, Mac, and most other consoles... ;  I think I''ve found a way to optimize it further.Assume that the root node is not a leaf. (This should probably always be true, unless what I''m compressing is just a single [repeated] value. If it is I''ll make a special case for it).Therefore, tracing through the tree will always start with a non-leaf node and end with a leaf node, and there will be no leaf nodes between the two.If I limit the distance between a parent node and child node to 127 bytes, I''m only using 7 bits of my offset values, leaving one bit free in each.I can use that free bit to indicate whether the child is a leaf or not.This completely eliminates the extra ''opcode'' byte; non-leaf nodes become left-child(is-child (1bit), offset (7bits)), right-child(is-child (1bit), offset (7bits)), while leaf nodes are just single byte values. The largest possible tree size is thus 256 + 255*2 = 766 bytes, which is somewhat better than the 1277 bytes the original method took up.The biggest problem then is the 127-byte offset limit. I guess the largest possible offset the tree would require would be if the root node had a child right at the end of the stream, but it should be perfectly possible when compressing the data to rearrange the tree so that the offsets are as small as possible. (Are smaller jumps actually faster, anyway?)Are there any conceivable cases in which the 127-byte offset limit actually presents a problem?   Richard "Superpig" Fine- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4 | Enginuity5ry. .ibu cy. .y''ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebuPreserve wildlife: pickle a squirrel today! ;  In my experience, there''s a better approach...Use a preorder listing of the nodes.  For non-leaf nodes, indicate that the node isn''t a leaf.  For the leaf nodes, indicate that it''s a leaf, and what value is there.And that''s all you need.  Using a preorder listing and identifying the leaf nodes gives all the information necessary to rebuild the structure of the tree, and only the values in the leaf nodes matter in a Huffman tree. ;  Isn''t the Arithmetic coder better? It''s simplier as well, faster, cuter... So why not use it? ;quote:Original post by Raghar  Isn''t the Arithmetic coder better? It''s simplier as well, faster, cuter... So why not use it?   As far as I can tell, the Arithmetic coder is just a better way of building the tree - it''s compatible with the decompression part of Huffman. So I should be able to use the same decompression routines, start with Huffman in my compressor, and then upgrade to Arithmetic if things need to be smaller. I''m not compressing anything in realtime (yet) so it should be possible to do pretty much anything. ;  Actually, arithmetic compression is substantially more complicated than Huffman coding and doesn''t even use a tree based structure.  The huffman tree is provably optimal for using integer length bit compression.  Arithmetic coding could store a symbol in 1.3 bits, allowing for even greater compression.Also, decompression speed with arithmetic is substantially worse than huffman, as it the same order of complexity as arithmetic compression.  Also, another thing you may want to look into is adaptive huffman compression, which updates the symbol frequencies as it moves along in the file.  It will be a bit slower overall, but you have no need to encode the huffman tree, and the compression stays about the same (and can even be better sometimes).For some excellent compression tutorials check out Arturo Campos'' home page which has some excellent introductions to the different types of compression in use today.  Also, check out Dr. Ross'' compression crypt.  For more advanced stuff check out Charles Bloom''s homepage, which is a truly impressive collection of work.As for your huffman decompression algorithm, it''s fine the way it is for cache usage.  As long as you don''t start storing each tree node in 64k you''ll be fine .  I have some fast huffman decompression code sitting around here somewhere, I''ll dig around for it, but yours looks quite good. ;quote:Original post by Premandrake  Also, decompression speed with arithmetic is substantially worse than huffman, as it the same order of complexity as arithmetic compression.Ah, OK. That means I won''t use it; decompression speed is my prime critereon for selecting an algorithm. If I optimize my tree structure, I''m thinking that the compression I get with Huffman should be enough.quote:Also, another thing you may want to look into is adaptive huffman compression, which updates the symbol frequencies as it moves along in the file.  It will be a bit slower overall, but you have no need to encode the huffman tree, and the compression stays about the same (and can even be better sometimes).Hmm, I''ll look into it. At the moment I''m writing the compression part of the system. It''s working like this:Scan all the files to be compressed to count frequencies of each of the 256 symbols (and also to check that the files are valid, etc etc).Sort the symbol array so that the most frequently occuring symbols are at the front.Construct a ''trivial tree'' - the left child is always a leaf node, and the right child is always a non-leaf node. So the most frequent symbol will end up with a 1-bit code, and the least frequent symbol will get a 255-bit code.Optimize the tree.What I''ve noticed is that I can take the frequency of each symbol and multiply it by the depth of that symbol''s leaf node in the tree, and get the total number of bits it uses when compressed; thus, for every two symbols, I extract the deeper symbol, pull the shallower symbol down one level, and make the deeper symbol its sibling (so basically I move the deeper symbol, along with its parent node, up the tree). I then recalculate the bits-used value, and if the total change is negative or zero, I keep the change to the tree structure. If it''s positive, I move it back again.The end result should be something that gives me optimal trees. It''ll be somewhat slow, but compression speed isn''t much of an issue for this project. Richard "Superpig" Fine- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4 | Enginuity5ry. .ibu cy. .y''ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebuPreserve wildlife: pickle a squirrel today! 