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