Binary code compression based on decision trees
Tamás Gergely, Ferenc Havasi, Tibor Gyimóthy · Proceedings of the Estonian Academy of Sciences Engineering · 2005
More and more embedded systems are used in the world.These machines have limited resources as, e.g., the background storage size.It is important to increase the storage capacity of these machines.A possible solution for this is compressing the files before they are written on the storage device.This is usually done by a general compresssor.There are files containing text or binary data and in many cases binary program code.A general compressor compresses all of them with almost the same efficiency.But a compressor, specialized for one type of input, would compress files of that type much better; thus using many special compressors would save space and increase the virtual capacity of the storage device.Using this idea, our goal was to create a compression algorithm for binary program code.Most compression methods can be separated into two parts: the model and the coder.In this paper we introduce a decision-tree based modelling method.We combined this method with an arithmetic coder and applied it in a modified JFFS2 file system of a Linux distribution, running on a PDA machine.The original file system used only one method for file compression (zlib), the modified file system uses many compressors, including our model-based one.This PDA machine has an ARM processor; thus our method was implemented for the compression of ARM instructions.The results were very promising: depending on the parameters of the method, at least 12.6% of the 13 MB image, created with only zlib compression, were saved, and it costed boot speed slowdown only at most 3 times.