On Tue, 26 Oct 2021 16:39:13 -0700 Kalesh Singh kaleshsingh@google.com wrote:
// This works best for small divisors if (div > max_div) { // only do a real division return; } shift = 20; mult = ((1 << shift) + div - 1) / div; delta = mult * div - (1 << shift); if (!delta) { /* div is a power of 2 */ max = -1; return; } max = (1 << shift) / delta;I'm still trying to digest the above algorithm.
mult = (2^20 + div - 1) / div;
The "div - 1" is to round up.
Basically, it's doing: X / div = X * (2^20 / div) / 2^20
If div is constant, the 2^20 / div is constant, and the "2^20" is the same as a shift.
So multiplier is 2^20 / div, and the shift is 20.
But because there's rounding errors it is only accurate up to the difference of:
delta = mult * div / 2^20
That is if mult is a power of two, then there would be no rounding errors, and the delta is zero, making the max infinite:
max = 2^20 / delta as delta goes to zero.
But doesn't this add 2 extra divisions? What am I missing here?
The above is only done at parsing not during the trace, where we care about.
We would of course need to use 64 bit operations (maybe only do this for 64 bit machines). And perhaps even use bigger shift values to get a bigger max.
Then we could do:
if (val1 < max) return (val1 * mult) >> shift;
This is done at the time of recording.
Actually, it would be:
if (val1 < max) return (val1 * mult) >> shift; else return val1 / div;
-- Steve