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
div_compute(div_info_t * div_info,size_t n)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