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