Author Topic: Arithmetic Coder for BitStream  (Read 2537 times)

the_viking

  • Jr. Member
  • **
  • Posts: 97
  • Karma: 2
    • View Profile
Arithmetic Coder for BitStream
« on: June 15, 2006, 05:26:39 PM »
I just had an idea, as I wanted to write a ranged integer that shouldn't consume more memory as it's needed for values between 0 and 4096 ;)
I remebered an Article from the GDmag some years ago, where they wrote about an "Arithmetic Coder" (i'm sure you know what it is).
So far, I think it would be great if you can do something like:

int n = 194;
stream.WriteRanged(n, 92, 212);

And it would just consume 7 bits because the range is only 120 and you can pack values from 0 to 120 into 7 bits.

The resulting code must be smth like this:

Code: [Select]
WriteRanged(int value, int min, int max)
{
int range = max-min;
int comprValue = value-min;
assert(comprValue >= 0);
int bits = ln(range) / LN_2; // LN_2 = ln(2), has to round up every time
WriteBits(reinterpret_cast<char*>(&comprValue),bits);
}

I'm not fully aware about the logarithmic operation, if it's correct. It might also be cycles consuming, but bandwidth is more expensive ;)

(I testet the calculation with wincalc, seems to work perfectly ;) )

Edit:
Maybe this can improve the WriteDelta*-Methods, too.
If you know the "old value" on both sides, you can send the delta with only using as much bits
as neccessary (range 0->delta). You then just add the delta to the old value on the receiver side.
« Last Edit: June 15, 2006, 05:29:02 PM by the_viking »

Rak'kar

  • Administrator
  • Hero Member
  • *****
  • Posts: 6895
  • Karma: 291
    • View Profile
    • RakNet
Re: Arithmetic Coder for BitStream
« Reply #1 on: June 15, 2006, 06:21:28 PM »
Sounds like a good idea!

A faster way is just to subtract min from max and shift until you reach the leftmost 1 to find out how many bits were used.  There might be better ways as well.