# Thread: Questions on range encoder implementation

1. ## Questions on range encoder implementation

Hi!

I'm trying to implement a simple range encoder and despite lots of material on the Net on this topic, I start feeling that I'm getting lost. There are lots of examples, all of them different and lots of implementation choices nearly in every line one would wright down.

So, I would appreciate very much if anybody could answer some of my questions:

First of all I've chosen one implementation to follow: "Range Encoder" by Arturo Campos, just because it was mentioned in the Arithmetic Coding tutorial which I'm following.

My concern is primarily about compression ratio and then about the speed. The speed is very important too, but not at the expense of any significant compression ratio losses.

So, the Q.1 is - if my choice was right at all (rate coding instead of simple arithmetic coding, and Arturo Campos implementation as a reference)

As for theory and practice, I understand everything except encoder renormalize phase. I have so many questions here that I don't even know where to start. Lets start from the beginning:

Question 2: Range initialization value:

In Campos' code the range initial value is 0x80000000. In some other implementations I've walked through init values are something like DWORD(-1), which is 0xFFFFFFFF. Both options have no sense to me. As far as I understand we decide to work with 32bit integers without last bit to prevent overflow. What would make sense here is something like 0x7FFFFFFF - the largest 31bit number. Why 0x80000000? Why 0xFFFFFFFF?...

The other questions are about the code. Here it is:

Encoder renormalize:
• While ( range <= Bottom_value ) As long as it's not above than Bottom_value (it means we can still output)
• if ( low < ( 0FFh << Shift_bits ) ) If higher part is 0FFh a carry will occur which we can't afford
• Yes We had a range with a potential carry (which we can't capture with our precision)
• Output_byte ( buffer ) Output the byte
• For ( ; help != 0 ; --help ) Output all underflow bytes pending for output
• Output_byte ( 0FFh )
• Buffer = low >> Shift_bits Assign to the byte to output the high bytes of low
• No Now check for actual carry
• if ( ( low And Top_value) != 0) Check carry bit
• Yes
• Output_byte ( buffer + 1 ) The +1 comes from the carry which propagates till the byte saved
• For ( ; help != 0 ; --help ) Output all underflow bytes pending for output
• Output_byte ( 00h ) 0FFh's become 0's (the carry!)
• Buffer = low >> Shift_bits Assign to the byte to output the high bytes of low
• No
• ++Buffer
• Range << 8 Shift out byte which we have already outputted or are going to be outputted (in case of 0FFh)
• Low << 8
• Low And ( Top_value - 1 ) Clear carry bit
• Repeat

Question 3:
the loop condition.

In wikipedia article on Range encoding, the loop condition is written like this:

// check if left-most digit is same throughout range
while (low / 10000 == (low + range) / 10000)

I do understand what happens here: for all further (low, range) values that we will get in further iterations the first digit will stay the same and hence we can output it already, etc... I suspect that this: While ( range <= Bottom_value ) has to mean the same, but I really don't understand why. The Bottom_value is 0x00800000.

Question 4: The overflow and underflow and handling of them

The most dark part for me. As I understand, we can get two situations when iterating low and range, each of which we have to handle exceptionally:

a) Overflow: when low + new_value will become more than 0x7FFFFFFF. Then we have to handle it somehow.
b) Undeflow: when low and range become so close to each other that there is no more bits left between them to represent the interval and thus continue iterations.

So, I absolutely don't understand how these situations are handled in inner if ( low < ( 0FFh << Shift_bits ) ) { ... } branch and why does it look like this. Could anyone explain?

Ilya.  Reply With Quote

2. Is this for coding bits or for a larger alphabet?  Reply With Quote

3. This is for alphabet of size 2^15  Reply With Quote

4. Maybe try the carryless range coder from PPMd? I think if the range crosses a byte boundary that wouldn't let you normalize then you throw away part of the range.  Reply With Quote

5. > There are lots of examples, all of them different and lots of
> implementation choices nearly in every line one would wright down.

Yeah, but in fact lots of these choices affect the coder properties
(like max speed with specific precision of symbol probabilities,
coder/decoder delay, support for >binary alphabets etc - there's lot
more to it than just speed and compression).

> First of all I've chosen one implementation to follow: "Range
> Encoder" by Arturo Campos, just because it was mentioned in the
> Arithmetic Coding tutorial which I'm following.

I'd suggest http://www.ctxmodel.net/rem.pl?-37

Overall, it seems that "compression scene" and "official" sources
(books, academic papers etc) are especially out of sync on this topic.

> My concern is primarily about compression ratio and then about the speed.
> The speed is very important too, but not at the expense of any
> significant compression ratio losses.

Ok, but actually with current cpu architectures (32-bit and more)
the coding precision is hardly an issue at all.
The overheads which we're normally able to encounter are at the
scale of 100 bytes per 1M of compressed data, ie 0.01%.

Anyway, the model is much more important in that sense.

> In Campos' code the range initial value is 0x80000000. In some other
> implementations I've walked through init values are something like
> DWORD(-1), which is 0xFFFFFFFF. Both options have no sense to me. As
> far as I understand we decide to work with 32bit integers without
> last bit to prevent overflow. What would make sense here is
> something like 0x7FFFFFFF - the largest 31bit number. Why
> 0x80000000? Why 0xFFFFFFFF?...

Some versions work with 32-bit range - these would usually set initial range to 2^32-1,
because they can't put 2^32 there and also initial value doesn't really matter all that much -
at worst we'd only lose a few bits even if its initialized with 1<<16 or something.

Also there's an additional option of storing (range-1) in the variable
and fixing it up by extra tweaks in range update:
1) range' = range*freq/total; // normal
2) range' = (range*freq+range)/total-1; // range-1 fixup
The latter is in theory more precise, but the actual difference is really hard to notice
(usually less than a byte).

Then, other versions (like original M.Schindler's rangecoder) work with 31-bit range
because like that it becomes easier to detect carry - in practice this doesn't make
any sense at all, aside from making the coder more complicated due to extra shifts.
Anyway, in this case the full initial range should be 2^31 if range variable is unsigned,
but it can be also set to 2^31-1 if it has to be signed for some reasons (like java not
having unsigned types).

> while (low / 10000 == (low + range) / 10000)
> I suspect that this: While ( range <= Bottom_value ) has to mean the
> same, but I really don't understand why.

Its not really the same. Low's bits higher than log2(range)'th can only
be affected by carry (not directly by bits of symbol's interval low bound,
which is <range), which allows for a simple implementation of long addition.

Actually there's a tradeoff, because higher range value means better compression
(ideally we can do bitwise renorm so range would be always in [2^31..2^32-1] )
but having to do more renorm iterations makes coding slower.
Still, in rangecoders, normally the Bottom_value is Initial_value/256, because that
allows to shift out a whole byte from low.

> a) Overflow: when low + new_value will become more than 0x7FFFFFFF.
> Then we have to handle it somehow.

Yes, but in this case we just have to proparage the carry.
Low is actually stored with higher precision than it looks
(there's a cached leading byte ("buffer" in your code) and potentially a string of FFs
(of length "help" in your code))
and the carry doesn't fit in the low part, so we have to update
the cached part too (but then we can flush it).

> b) Undeflow: when low and range become so close to each other that
> there is no more bits left between them to represent the interval
> and thus continue iterations.

Yes, but this only matters in carryless coders (which avoid the carry
by reducing the range, instead of doing the long arithmetics).

> So, I absolutely don't understand how these situations are handled
> in inner if ( low < ( 0FFh << Shift_bits ) ) { ... } branch and why
> does it look like this. Could anyone explain?

Well, as I said, the full value of low is Buffer . 0xFF x help . low.
Now, (low<(0FFh<<Shift_bits)) means that high byte of low is not 0xFF
so we can't just increment the 0xFF counter, and (low And Top_value)
means the carry, because low is stored with 31-bit precision there.  Reply With Quote

arithmetic encoder, range encoder 