Home | History | Annotate | Line # | Download | only in internal 
      1 #ifndef JEMALLOC_INTERNAL_FXP_H
      2 #define JEMALLOC_INTERNAL_FXP_H
      3 
      4 /*
      5  * A simple fixed-point math implementation, supporting only unsigned values
      6  * (with overflow being an error).
      7  *
      8  * It's not in general safe to use floating point in core code, because various
      9  * libc implementations we get linked against can assume that malloc won't touch
     10  * floating point state and call it with an unusual calling convention.
     11  */
     12 
     13 /*
     14  * High 16 bits are the integer part, low 16 are the fractional part.  Or
     15  * equivalently, repr == 2**16 * val, where we use "val" to refer to the
     16  * (imaginary) fractional representation of the true value.
     17  *
     18  * We pick a uint32_t here since it's convenient in some places to
     19  * double the representation size (i.e. multiplication and division use
     20  * 64-bit integer types), and a uint64_t is the largest type we're
     21  * certain is available.
     22  */
     23 typedef uint32_t fxp_t;
     24 #define FXP_INIT_INT(x) ((x) << 16)
     25 #define FXP_INIT_PERCENT(pct) (((pct) << 16) / 100)
     26 
     27 /*
     28  * Amount of precision used in parsing and printing numbers.  The integer bound
     29  * is simply because the integer part of the number gets 16 bits, and so is
     30  * bounded by 65536.
     31  *
     32  * We use a lot of precision for the fractional part, even though most of it
     33  * gets rounded off; this lets us get exact values for the important special
     34  * case where the denominator is a small power of 2 (for instance,
     35  * 1/512 == 0.001953125 is exactly representable even with only 16 bits of
     36  * fractional precision).  We need to left-shift by 16 before dividing by
     37  * 10**precision, so we pick precision to be floor(log(2**48)) = 14.
     38  */
     39 #define FXP_INTEGER_PART_DIGITS 5
     40 #define FXP_FRACTIONAL_PART_DIGITS 14
     41 
     42 /*
     43  * In addition to the integer and fractional parts of the number, we need to
     44  * include a null character and (possibly) a decimal point.
     45  */
     46 #define FXP_BUF_SIZE (FXP_INTEGER_PART_DIGITS + FXP_FRACTIONAL_PART_DIGITS + 2)
     47 
     48 static inline fxp_t
     49 fxp_add(fxp_t a, fxp_t b) {
     50 	return a + b;
     51 }
     52 
     53 static inline fxp_t
     54 fxp_sub(fxp_t a, fxp_t b) {
     55 	assert(a >= b);
     56 	return a - b;
     57 }
     58 
     59 static inline fxp_t
     60 fxp_mul(fxp_t a, fxp_t b) {
     61 	uint64_t unshifted = (uint64_t)a * (uint64_t)b;
     62 	/*
     63 	 * Unshifted is (a.val * 2**16) * (b.val * 2**16)
     64 	 *   == (a.val * b.val) * 2**32, but we want
     65 	 * (a.val * b.val) * 2 ** 16.
     66 	 */
     67 	return (uint32_t)(unshifted >> 16);
     68 }
     69 
     70 static inline fxp_t
     71 fxp_div(fxp_t a, fxp_t b) {
     72 	assert(b != 0);
     73 	uint64_t unshifted = ((uint64_t)a << 32) / (uint64_t)b;
     74 	/*
     75 	 * Unshifted is (a.val * 2**16) * (2**32) / (b.val * 2**16)
     76 	 *   == (a.val / b.val) * (2 ** 32), which again corresponds to a right
     77 	 *   shift of 16.
     78 	 */
     79 	return (uint32_t)(unshifted >> 16);
     80 }
     81 
     82 static inline uint32_t
     83 fxp_round_down(fxp_t a) {
     84 	return a >> 16;
     85 }
     86 
     87 static inline uint32_t
     88 fxp_round_nearest(fxp_t a) {
     89 	uint32_t fractional_part = (a  & ((1U << 16) - 1));
     90 	uint32_t increment = (uint32_t)(fractional_part >= (1U << 15));
     91 	return (a >> 16) + increment;
     92 }
     93 
     94 /*
     95  * Approximately computes x * frac, without the size limitations that would be
     96  * imposed by converting u to an fxp_t.
     97  */
     98 static inline size_t
     99 fxp_mul_frac(size_t x_orig, fxp_t frac) {
    100 	assert(frac <= (1U << 16));
    101 	/*
    102 	 * Work around an over-enthusiastic warning about type limits below (on
    103 	 * 32-bit platforms, a size_t is always less than 1ULL << 48).
    104 	 */
    105 	uint64_t x = (uint64_t)x_orig;
    106 	/*
    107 	 * If we can guarantee no overflow, multiply first before shifting, to
    108 	 * preserve some precision.  Otherwise, shift first and then multiply.
    109 	 * In the latter case, we only lose the low 16 bits of a 48-bit number,
    110 	 * so we're still accurate to within 1/2**32.
    111 	 */
    112 	if (x < (1ULL << 48)) {
    113 		return (size_t)((x * frac) >> 16);
    114 	} else {
    115 		return (size_t)((x >> 16) * (uint64_t)frac);
    116 	}
    117 }
    118 
    119 /*
    120  * Returns true on error.  Otherwise, returns false and updates *ptr to point to
    121  * the first character not parsed (because it wasn't a digit).
    122  */
    123 bool fxp_parse(fxp_t *a, const char *ptr, char **end);
    124 void fxp_print(fxp_t a, char buf[FXP_BUF_SIZE]);
    125 
    126 #endif /* JEMALLOC_INTERNAL_FXP_H */
    127