Re: Range coder algorithm details


"Rasmus Møller" <gcomp.rasemil@xxxxxxxxxxxxxxx> wrote in message
news:1135293149.780960.256110@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> Hello to the group,
>
> please comment if I have made any obvious error below.
>
> I want to code a sequence of 1-bit flags.
> Each flag has p in the range [1,255] (out of 256).
> Initialization is L=0x00000000 and R=0x01000000
> (24 bit range, 8 bit free for multiplication)
>
> Coding each bit :
>
> r = (R*p)>>8
> if (bit) { R = r } else { L = L+r ; R = R-r }
>
> When R < 256 /* flush and check for underflow */ {
> H = L+R ;
> M = ((L+H)>>1)) & 0x00FF0000 , output byte M>>16
> if (L & 0x00FF0000)<>(H & 0x00FF0000) /*underflow*/ {
> if (H-M) > (M-L) /*shrink upper*/ { L = M ; R = H-M }
> else /*shrink to lower interval*/ { R = H-M }
> }
> L = (L & 0x0000FFFF) << 8
> R = ((R & 0x0000FFFF) << 8) + 0x000000FF
> }
>
> Details about termination left out on purpose.
> I am a little insecure about a few things:
>
> - is it okay to start with R of 0x01000000 instead of 0x00FFFFFF
> - is it okay to add FF to the range R after shifting left
> - is it okay to always flush only once, as R >0 before R<<8
> - when decoding, if the value is exactly equal to L+((R*p)>>8),
> it belongs in upper interval (in this case value=false) doesn't it?
>
> TIA and please be gentle
>

you have almost recreated the style of coder used in paq and friends...

here is a clip from one of my coders:

void BPAQ_OutputBit(int i, unsigned int w)
{
unsigned int r, r2, v;
int j;

r=bpaq_rmax-bpaq_rmin;
#ifdef BPAQ_NOLONGLONG
v=bpaq_rmin+(r>>BPAQ_WBITS)*w;
v+=((r&BPAQ_WMASK)*w)>>BPAQ_WBITS;
#else
v=bpaq_rmin+((((ull)r)*((ull)(w<<(32-BPAQ_WBITS))))>>32);
#endif

if(i)bpaq_rmin=v+1;
else bpaq_rmax=v;

//while bits
while((bpaq_rmin&0xFF000000)==(bpaq_rmax&0xFF000000))
{
BPAQ_OutputByte(bpaq_rmin>>24);
bpaq_rmin<<=8;
bpaq_rmax<<=8;
bpaq_rmax|=255;
}
}

int BPAQ_InputBit(unsigned int w)
{
unsigned int r, r2, v, i;

r=bpaq_rmax-bpaq_rmin;
#ifdef BPAQ_NOLONGLONG
v=bpaq_rmin+(r>>BPAQ_WBITS)*w;
v+=((r&BPAQ_WMASK)*w)>>BPAQ_WBITS;
#else
v=bpaq_rmin+((((ull)r)*((ull)(w<<(32-BPAQ_WBITS))))>>32);
#endif

i=(bpaq_rval>v);
if(i)bpaq_rmin=v+1;
else bpaq_rmax=v;

//while bits
while((bpaq_rmin&0xFF000000)==(bpaq_rmax&0xFF000000))
{
bpaq_rmin<<=8;
bpaq_rmax<<=8;
bpaq_rmax|=255;

bpaq_rval<<=8;
bpaq_rval|=BPAQ_InputByte();
}

return(i);
}

maybe you can figure this out...

note that:
probabilities are 16 bits in this coder (actually, they are whatever
BPAQ_WBITS is set to).

using 8 bit probabilities, and a 24 bit range, you could eliminate some of
the math:
void BPAQ_OutputBit(int i, unsigned int w)
{
unsigned int r, r2, v;
int j;

r=bpaq_rmax-bpaq_rmin;
v=bpaq_rmin+((r*w)>>8);

if(i)bpaq_rmin=v+1;
else bpaq_rmax=v;

//while bits
while((bpaq_rmin&0xFF0000)==(bpaq_rmax&0xFF0000))
// or while(!(bpaq_rmin^bpaq_rmax)&0xFF0000))
{
BPAQ_OutputByte(bpaq_rmin>>16);
bpaq_rmin<<=8;
bpaq_rmax<<=8;
bpaq_rmax|=255;
}
}

I have personally not found any real speed difference between the '2 and,
equals' and 'xor, and, not' approaches.

keeping the min and range as the representation, in my experience, is more
complicated and slower for this style of coder, but one can try if they
want...

> Rasmus
>


.

Relevant Pages