Code optimization for adaptive binary predictor

[nburns]

I optimized the adaptive binary predictor code in Matt's fpaqc. The code below shows both old and new.

  void update(int y) {

#ifdef SLOWPRED



    // original predictor

    if (y) t[cxt]+=65536-t[cxt]>>5;

    else t[cxt]-=t[cxt]>>5;

#else



    // faster predictor (equivalent)

    t[cxt] -= (t[cxt] - y >> 5) - (-y & 0x7ff);



#endif

    if ((cxt+=cxt+y)>=512) cxt=1;

  }

[hexagone]

I had similar code in Kanzi FPAQPredictor.cpp:

// Update the probability model
// bit == 1 -> prob += (3*((PSCALE-(prob+16))) >> 7);
// bit == 0 -> prob -= (3*(prob+16)) >> 7);
inline void FPAQPredictor::update(int bit)
{
_probs[_ctxIdx] -= ((3 * ((_probs[_ctxIdx] + 16) - (PSCALE & -bit))) >> 7);


if (_ctxIdx < 128 )
_ctxIdx = (_ctxIdx << 1) | bit;
else
_ctxIdx = 1;
}

[nburns]

It looks like it should be possible to make mine a little simpler. I tried just now, but I discovered how subtle and fragile that is (I wrote it a few years ago).

EDIT: There are a lot of annoying problems that can crop up when right shifting (signed vs unsigned, rounding), so I guess that's why the version in the OP looks the way it does.

@hexagone You are probably ignoring the fact that right-shifting has funny rounding behavior on negative numbers, because in your case it probably doesn't matter.