Sachin Garg

Programming is like composing poetry, its like making music...

Range Coder in Java

Range coder is a very popular algorithm used for entropy coding in compression algorithms. I needed Java source code for Range Coding but couldn't find any and had to code one myself, so here it is for others who might be looking for it.

Source Code

This range coder is based upon the carry-less range coder implementation by Dmitry Subbotin, and uses 64-bit variables for improved performance. Archive contains a generic range coder and decoder, along with a byte stream order-zero model implemented as subclasses of Java's I/O streams. You can browse the source tree here.

Download Java Source (7KB)

Changes Made

One of the major troubles with Java is it's total lack of unsigned variables (yes, this came as a huge surprise to me too). Most compression and encryption algorithms depend greatly on concept of 'Byte' which is presumed to be unsigned (0-255), but welcome to Java world, no unsigned variables. Moreover, the result of many arithmetic operations is different when variables are signed, especially when code relies on bit-shifting. This is again very common in compression and encryption algorithms.

Also, reserving (in this case wasting) a bit for sign, results in loss of precision when doing calculations for range coding. As Range Coder is byte based, this wastes 8 higher order bits, leaving very little room for calculations. So I chose to use Java's 64-bit long type. With 64-bit processors becoming increasing popular, it makes sense for software to use this extra available processing power (read on for detailed discussion on effect of precision on compression ratio).

Sachin Garg  New Delhi, India  © Copyright 2001-20011. All rights reserved.
The Data Compression News Blog  The Image Compression Benchmark  Rawzor - lossless compression for camera raw images

Questions or comments?