|
Packit Service |
724aca |
#include "jemalloc/internal/jemalloc_preamble.h"
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
#include "jemalloc/internal/div.h"
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
#include "jemalloc/internal/assert.h"
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
/*
|
|
Packit Service |
724aca |
* Suppose we have n = q * d, all integers. We know n and d, and want q = n / d.
|
|
Packit Service |
724aca |
*
|
|
Packit Service |
724aca |
* For any k, we have (here, all division is exact; not C-style rounding):
|
|
Packit Service |
724aca |
* floor(ceil(2^k / d) * n / 2^k) = floor((2^k + r) / d * n / 2^k), where
|
|
Packit Service |
724aca |
* r = (-2^k) mod d.
|
|
Packit Service |
724aca |
*
|
|
Packit Service |
724aca |
* Expanding this out:
|
|
Packit Service |
724aca |
* ... = floor(2^k / d * n / 2^k + r / d * n / 2^k)
|
|
Packit Service |
724aca |
* = floor(n / d + (r / d) * (n / 2^k)).
|
|
Packit Service |
724aca |
*
|
|
Packit Service |
724aca |
* The fractional part of n / d is 0 (because of the assumption that d divides n
|
|
Packit Service |
724aca |
* exactly), so we have:
|
|
Packit Service |
724aca |
* ... = n / d + floor((r / d) * (n / 2^k))
|
|
Packit Service |
724aca |
*
|
|
Packit Service |
724aca |
* So that our initial expression is equal to the quantity we seek, so long as
|
|
Packit Service |
724aca |
* (r / d) * (n / 2^k) < 1.
|
|
Packit Service |
724aca |
*
|
|
Packit Service |
724aca |
* r is a remainder mod d, so r < d and r / d < 1 always. We can make
|
|
Packit Service |
724aca |
* n / 2 ^ k < 1 by setting k = 32. This gets us a value of magic that works.
|
|
Packit Service |
724aca |
*/
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
void
|
|
Packit Service |
724aca |
div_init(div_info_t *div_info, size_t d) {
|
|
Packit Service |
724aca |
/* Nonsensical. */
|
|
Packit Service |
724aca |
assert(d != 0);
|
|
Packit Service |
724aca |
/*
|
|
Packit Service |
724aca |
* This would make the value of magic too high to fit into a uint32_t
|
|
Packit Service |
724aca |
* (we would want magic = 2^32 exactly). This would mess with code gen
|
|
Packit Service |
724aca |
* on 32-bit machines.
|
|
Packit Service |
724aca |
*/
|
|
Packit Service |
724aca |
assert(d != 1);
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
uint64_t two_to_k = ((uint64_t)1 << 32);
|
|
Packit Service |
724aca |
uint32_t magic = (uint32_t)(two_to_k / d);
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
/*
|
|
Packit Service |
724aca |
* We want magic = ceil(2^k / d), but C gives us floor. We have to
|
|
Packit Service |
724aca |
* increment it unless the result was exact (i.e. unless d is a power of
|
|
Packit Service |
724aca |
* two).
|
|
Packit Service |
724aca |
*/
|
|
Packit Service |
724aca |
if (two_to_k % d != 0) {
|
|
Packit Service |
724aca |
magic++;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
div_info->magic = magic;
|
|
Packit Service |
724aca |
#ifdef JEMALLOC_DEBUG
|
|
Packit Service |
724aca |
div_info->d = d;
|
|
Packit Service |
724aca |
#endif
|
|
Packit Service |
724aca |
}
|