uint64_t div96bit(uint64_t W[2], uint32_t D) {
uint64_t y = W[0];
uint64_t x = W[1];
+ int i;
- for (int i = 1; i <= 64; ++i) {
+ for (i = 1; i <= 64 && x; ++i) {
uint32_t t = (int)x >> 31;
x = (x << 1) | (y >> 63);
y = y << 1;
}
}
- return y;
+ return y << (64 - i + 1);
}
}
assert(n <= d && "Probability must be less or equal to 1.");
- // If we can overflow use 96-bit operations.
- if (n > 0 && Frequency > UINT64_MAX / n) {
+ // Calculate Frequency * n.
+ uint64_t mulLo = (Frequency & UINT32_MAX) * n;
+ uint64_t mulHi = (Frequency >> 32) * n;
+ uint64_t mulRes = (mulHi << 32) + mulLo;
+
+ // If there was overflow use 96-bit operations.
+ if (mulHi > UINT32_MAX || mulRes < mulLo) {
// 96-bit value represented as W[1]:W[0].
uint64_t W[2];
return *this;
}
- Frequency *= n;
- Frequency /= d;
+ Frequency = mulRes / d;
return *this;
}