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 */
23typedef 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
48static inline fxp_t
49fxp_add(fxp_t a, fxp_t b) {
50 return a + b;
51}
52
53static inline fxp_t
54fxp_sub(fxp_t a, fxp_t b) {
55 assert(a >= b);
56 return a - b;
57}
58
59static inline fxp_t
60fxp_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
70static inline fxp_t
71fxp_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
82static inline uint32_t
83fxp_round_down(fxp_t a) {
84 return a >> 16;
85}
86
87static inline uint32_t
88fxp_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 */
98static inline size_t
99fxp_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 */
123bool fxp_parse(fxp_t *a, const char *ptr, char **end);
124void fxp_print(fxp_t a, char buf[FXP_BUF_SIZE]);
125
126#endif /* JEMALLOC_INTERNAL_FXP_H */
127