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).
|