Home | History | Annotate | Line # | Download | only in internal 
      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