Range coder algorithm details

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

Rasmus

.

Relevant Pages

  • Review: WGI Fresno CG (Prelims)
    ... WGI Fresno Color Guard Regional ... the arena if it was okay to sit "anywhere" (and she acknowledged, ... not a bad sabre toss as flags were brought ... A diagonal rifle and sabre toss was executed quite well, ...
    (rec.arts.marching.colorguard)
  • Re: Which assembler can handle the BIG stuff ?
    ... It was the timing I was concerned about. ... even most instructions will destroy rather than preserve flags. ...
    (alt.lang.asm)
  • Re: [Patch] BME, noatime and nodiratime
    ... >> again), here is the first patch, which adds the mount ... > should remove them from flags in the last line, same way we do that for ... okay, ... send the line "unsubscribe linux-kernel" in ...
    (Linux-Kernel)
  • Re: What does f(x++) mean?
    ... Maybe I was oversimplifying a little bit. ... well-defined and okay to write ... is *not* a sequence point, even though the comma operator (also ... Undefined behavior will do that to you. ...
    (comp.lang.c)
  • sequence
    ... TaI need to add a sequence number to a table. ... Most likely this will break normalization rules, BUT that's okay for this ... applet. ... I am comparing data in two tables. ...
    (microsoft.public.access.queries)