1*8e33eff8Schristos #ifndef JEMALLOC_INTERNAL_DIV_H 2*8e33eff8Schristos #define JEMALLOC_INTERNAL_DIV_H 3*8e33eff8Schristos 4*8e33eff8Schristos #include "jemalloc/internal/assert.h" 5*8e33eff8Schristos 6*8e33eff8Schristos /* 7*8e33eff8Schristos * This module does the division that computes the index of a region in a slab, 8*8e33eff8Schristos * given its offset relative to the base. 9*8e33eff8Schristos * That is, given a divisor d, an n = i * d (all integers), we'll return i. 10*8e33eff8Schristos * We do some pre-computation to do this more quickly than a CPU division 11*8e33eff8Schristos * instruction. 12*8e33eff8Schristos * We bound n < 2^32, and don't support dividing by one. 13*8e33eff8Schristos */ 14*8e33eff8Schristos 15*8e33eff8Schristos typedef struct div_info_s div_info_t; 16*8e33eff8Schristos struct div_info_s { 17*8e33eff8Schristos uint32_t magic; 18*8e33eff8Schristos #ifdef JEMALLOC_DEBUG 19*8e33eff8Schristos size_t d; 20*8e33eff8Schristos #endif 21*8e33eff8Schristos }; 22*8e33eff8Schristos 23*8e33eff8Schristos void div_init(div_info_t *div_info, size_t divisor); 24*8e33eff8Schristos 25*8e33eff8Schristos static inline size_t 26*8e33eff8Schristos div_compute(div_info_t *div_info, size_t n) { 27*8e33eff8Schristos assert(n <= (uint32_t)-1); 28*8e33eff8Schristos /* 29*8e33eff8Schristos * This generates, e.g. mov; imul; shr on x86-64. On a 32-bit machine, 30*8e33eff8Schristos * the compilers I tried were all smart enough to turn this into the 31*8e33eff8Schristos * appropriate "get the high 32 bits of the result of a multiply" (e.g. 32*8e33eff8Schristos * mul; mov edx eax; on x86, umull on arm, etc.). 33*8e33eff8Schristos */ 34*8e33eff8Schristos size_t i = ((uint64_t)n * (uint64_t)div_info->magic) >> 32; 35*8e33eff8Schristos #ifdef JEMALLOC_DEBUG 36*8e33eff8Schristos assert(i * div_info->d == n); 37*8e33eff8Schristos #endif 38*8e33eff8Schristos return i; 39*8e33eff8Schristos } 40*8e33eff8Schristos 41*8e33eff8Schristos #endif /* JEMALLOC_INTERNAL_DIV_H */ 42