1 #include "jemalloc/internal/jemalloc_preamble.h" 2 3 #include "jemalloc/internal/div.h" 4 5 #include "jemalloc/internal/assert.h" 6 7 /* 8 * Suppose we have n = q * d, all integers. We know n and d, and want q = n / d. 9 * 10 * For any k, we have (here, all division is exact; not C-style rounding): 11 * floor(ceil(2^k / d) * n / 2^k) = floor((2^k + r) / d * n / 2^k), where 12 * r = (-2^k) mod d. 13 * 14 * Expanding this out: 15 * ... = floor(2^k / d * n / 2^k + r / d * n / 2^k) 16 * = floor(n / d + (r / d) * (n / 2^k)). 17 * 18 * The fractional part of n / d is 0 (because of the assumption that d divides n 19 * exactly), so we have: 20 * ... = n / d + floor((r / d) * (n / 2^k)) 21 * 22 * So that our initial expression is equal to the quantity we seek, so long as 23 * (r / d) * (n / 2^k) < 1. 24 * 25 * r is a remainder mod d, so r < d and r / d < 1 always. We can make 26 * n / 2 ^ k < 1 by setting k = 32. This gets us a value of magic that works. 27 */ 28 29 void 30 div_init(div_info_t *div_info, size_t d) { 31 /* Nonsensical. */ 32 assert(d != 0); 33 /* 34 * This would make the value of magic too high to fit into a uint32_t 35 * (we would want magic = 2^32 exactly). This would mess with code gen 36 * on 32-bit machines. 37 */ 38 assert(d != 1); 39 40 uint64_t two_to_k = ((uint64_t)1 << 32); 41 uint32_t magic = (uint32_t)(two_to_k / d); 42 43 /* 44 * We want magic = ceil(2^k / d), but C gives us floor. We have to 45 * increment it unless the result was exact (i.e. unless d is a power of 46 * two). 47 */ 48 if (two_to_k % d != 0) { 49 magic++; 50 } 51 div_info->magic = magic; 52 #ifdef JEMALLOC_DEBUG 53 div_info->d = d; 54 #endif 55 } 56