Implementation of the C-PACK compression algorithm

Question

I wish to implement C-PACK compression algorithm. The authors have mentioned that they use FIFO as the replacement for the dictionary of size 64 bytes. I am unable to understand that if I will replace an entry in the dictionary, how will I de-compress the data?

http://ziyang.eecs.umich.edu/~dickrp//publications/chen10aug.pdf

I took an input of 64 kB and passed through the compression algorithm. However, the results of the de-compression was wrong. This was happening because of the dictionary size. I can increase the dictionary size but if my data is of 2 MB, the dictionary will not scale. Can anyone let me know if I missing some basic concept in implmenting this algorithm?

Any help in this regard is highly appreciated.

Answer 1

"This was happening because of the dictionary size." Well, no. Your decompression is wrong because you have a bug. You would need to show your code if you're expecting someone to tell you where you went wrong.

What's you're supposed to do is pretty straightforward. There is a 64-byte dictionary, which consists of 16 32-bit words. When decompressing, you decode the bits, and if there is a bbbb, that is your index into the dictionary. You then use the bytes as indicated by the code from the word in the dictionary at that index (either the first two, the first three, or all four bytes). If the code is (01)BBBB, then you push that word into the dictionary, and drop the oldest word off of the dictionary.