contrib/jemalloc/include/jemalloc/internal/div.h

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