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 | |