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