Originally Posted by

**fgiesen**
Code:

kCDFMax = kMaxProb + (1 << kRate) - 1;
cdf_mix_i = i + (i >= kCurrentSym) ? (kCDFMax - kNumSyms) : 0;
cdf[i] += (cdf_mix_i - cdf[i]) >> kRate;

So, let's look at the "Simplified Version" from my https://review.xiph.org/1355/ link above.

Mapping between notations, we have kMaxProb = 32768, kRate = rate, kNumSyms = n. Then

Code:

tmp = 2 - (1 << rate) + i + (32767 + (1 << rate) - n)*(i >= val);
=> tmp = i >= val ? (32769 - n + i) : (i + 2 - (1 << rate));

and

Code:

cdf[i] -= (cdf[i] - tmp) >> rate;
=> cdf[i] += -((cdf[i] - tmp) >> rate);
=> cdf[i] += (-(cdf[i] - tmp) + (1 << rate) - 1) >> rate;
=> cdf[i] += (tmp - cdf[i] + (1 << rate) - 1) >> rate;
=> cdf[i] += ((i >= val ? (32769 - n + i) : (i + 2 - (1 << rate))) + (1 << rate) - 1) >> rate;
=> cdf[i] += (i >= val ? (32768 - n + (i + 1) + (1 << rate) - 1) : (i + 1)) >> rate;

That looks exactly like what you have, except with (i + 1) instead of i. Working the other way:

Code:

cdf[i] -= (cdf[i] - tmp) >> rate;
=> cdf[i] -= (cdf[i] - (i >= val ? (32769 - n + i) : (i + 2 - (1 << rate)))) >> rate;
=> cdf[i] -= (cdf[i] - (i + 1) - (i >= val ? (32768 - n) : -((1 << rate) - 1))) >> rate;
=> cdf[i] -= (i + 1);
cdf[i] -= (cdf[i] - (i >= val ? (32768 - n) : -((1 << rate) - 1))) >> rate;
cdf[i] += (i + 1);

And that's the "subtract a probability floor, make any changes you want that keep the probabilities between 0 and (kMaxProb - kNumSyms), then add the floor back" approach.

So except for an off-by-one, what I'm describing and what you're describing are exactly equivalent (and maybe the off-by-one is just explained by the fact that we exclude the 0-term from our cdf, so that cdf[0] is already the probability of value 0). In the last formulation there, it should be clear that the -((1 << rate) - 1) offset is just to ensure that the change is non-zero so long as cdf[i] > 0 (after subtracting off the probability floor). That guarantees that cdf[i] can be reduced all the way down to that floor. In the other direction, no offset is required, since a negative change won't be reduced to 0 by the right shift.