The FreeRADIUS server $Id: 15bac2a4c627c01d1aa2047687b3418955ac7f00 $
Loading...
Searching...
No Matches
math.h
Go to the documentation of this file.
1#pragma once
2/*
3 * This library is free software; you can redistribute it and/or
4 * modify it under the terms of the GNU Lesser General Public
5 * License as published by the Free Software Foundation; either
6 * version 2.1 of the License, or (at your option) any later version.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * Lesser General Public License for more details.
12 *
13 * You should have received a copy of the GNU Lesser General Public
14 * License along with this library; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
16 */
17
18/** Various miscellaneous utility functions
19 *
20 * @file src/lib/util/misc.h
21 *
22 * @copyright 2000,2006 The FreeRADIUS server project
23 */
24RCSIDH(math_h, "$Id: b7b755087d6daab1d81f5beb6d589f1744729406 $")
25
26#include <stdint.h>
27
28#ifdef __cplusplus
29extern "C" {
30#endif
31
32static inline uint64_t fr_roundup_pow2_uint64(uint64_t v)
33{
34#ifdef HAVE_BUILTIN_CLZLL
35 if (v <= 1) return 1;
36 return 1ULL << (64 - __builtin_clzll(v - 1));
37#else
38 if (v == 0) return 1;
39 v--;
40 v |= v >> 1;
41 v |= v >> 2;
42 v |= v >> 4;
43 v |= v >> 8;
44 v |= v >> 16;
45 v |= v >> 32;
46 v++;
47 return v;
48#endif
49}
50
51static inline int64_t fr_roundup_pow2_int64(int64_t v)
52{
53 uint64_t uv;
54
55 if (v <= 1) return 1;
56
57#ifdef HAVE_BUILTIN_CLZLL
58 uv = (uint64_t)(v - 1);
59
60 {
61 int shift = 64 - __builtin_clzll(uv);
62
63 if (shift >= 63) {
64 // would exceed INT64_MAX
65 return 0;
66 }
67 return (int64_t)(1ULL << shift);
68 }
69#else
70 uv = (uint64_t)v;
71 uv--;
72
73 uv |= uv >> 1;
74 uv |= uv >> 2;
75 uv |= uv >> 4;
76 uv |= uv >> 8;
77 uv |= uv >> 16;
78 uv |= uv >> 32;
79 uv++;
80
81 if (uv > (uint64_t)INT64_MAX) {
82 return 0;
83 }
84 return (int64_t)uv;
85#endif
86}
87
88/** Find the highest order high bit in an unsigned 64 bit integer
89 *
90 * @return 0-64 indicating the position of the highest bit,
91 * with 0 indicating no high bits, 1 indicating the 1st
92 * bit and 64 indicating the last bit.
93 */
94static inline uint8_t fr_high_bit_pos(uint64_t num)
95{
96 if (num == 0) return 0; /* num being zero is undefined behaviour for __builtin_clzll */
97
98#ifdef HAVE_BUILTIN_CLZLL
99 return (64 - __builtin_clzll(num));
100#else
101 uint8_t ret = 1;
102 while (num >>= 1) ret++;
103 return ret;
104#endif
105}
106
107/** Find the lowest order high bit in an unsigned 64 bit integer
108 *
109 * @return 0-64 indicating the position of the lowest bit,
110 * with 0 indicating no high bits, 1 indicating the 1st
111 * bit and 64 indicating the last bit.
112 */
113static inline uint8_t fr_low_bit_pos(uint64_t num)
114{
115 if (num == 0) return 0;
116
117#ifdef HAVE_BUILTIN_CLZLL
118 return __builtin_ctzll(num) + 1;
119#else
120 uint8_t ret = 1;
121
122 do {
123 if (num & 0x01) break;
124 ret++;
125 } while (num >>= 1);
126
127 return ret;
128#endif
129}
130
131/** Efficient calculation of log10 of a unsigned 64bit integer
132 *
133 * @param[in] num to calculate log10 of.
134 * @return log10 of the integer
135 */
136static inline uint8_t fr_log10(uint64_t num)
137{
138 static uint64_t const pow_of_10[] =
139 {
140 1ULL,
141 10ULL,
142 100ULL,
143 1000ULL,
144 10000ULL,
145 100000ULL,
146 1000000ULL,
147 10000000ULL,
148 100000000ULL,
149 1000000000ULL,
150 10000000000ULL,
151 100000000000ULL,
152 1000000000000ULL,
153 10000000000000ULL,
154 100000000000000ULL,
155 1000000000000000ULL,
156 10000000000000000ULL,
157 100000000000000000ULL,
158 1000000000000000000ULL,
159 10000000000000000000ULL
160 };
161 uint64_t tmp;
162
163 tmp = (fr_high_bit_pos(num) * 1233) >> 12;
164 return tmp - (num < pow_of_10[tmp]);
165}
166
167/** Multiplies two integers together
168 *
169 * @param[in] _out Where to store the result.
170 * @param[in] _a first argument to multiply.
171 * @param[in] _b second argument to multiply.
172 * @return
173 * - false on overflow.
174 * - true if there was no overflow.
175 */
176#define fr_multiply(_out, _a, _b) !__builtin_mul_overflow(_a, _b, _out)
177
178/** Adds two integers
179 *
180 * @param[in] _out Where to store the result.
181 * @param[in] _a first argument to add.
182 * @param[in] _b second argument to add.
183 * @return
184 * - false on overflow.
185 * - true if there was no overflow.
186 */
187#define fr_add(_out, _a, _b) !__builtin_add_overflow(_a, _b, _out)
188
189/** Subtracts two integers
190 *
191 * @param[in] _out Where to store the result.
192 * @param[in] _a first argument to subtract.
193 * @param[in] _b second argument to subtract.
194 * @return
195 * - false on overflow.
196 * - true if there was no overflow.
197 */
198#define fr_sub(_out, _a, _b) !__builtin_sub_overflow(_a, _b, _out)
199
200/** Round up - Only works if _mul is a power of 2 but avoids division
201 */
202#define ROUND_UP_POW2(_num, _mul) (((_num) + ((_mul) - 1)) & ~((_mul) - 1))
203
204/** Round up - Works in all cases, but is slower
205 */
206#define ROUND_UP(_num, _mul) (((((_num) + ((_mul) - 1))) / (_mul)) * (_mul))
207
208/** Get the ceiling value of integer division
209 *
210 */
211#define ROUND_UP_DIV(_x, _y) (1 + (((_x) - 1) / (_y)))
212
213#ifdef __cplusplus
214}
215#endif
#define RCSIDH(h, id)
Definition build.h:486
static uint64_t fr_roundup_pow2_uint64(uint64_t v)
Definition math.h:32
static int64_t fr_roundup_pow2_int64(int64_t v)
Definition math.h:51
static uint8_t fr_low_bit_pos(uint64_t num)
Find the lowest order high bit in an unsigned 64 bit integer.
Definition math.h:113
static uint8_t fr_log10(uint64_t num)
Efficient calculation of log10 of a unsigned 64bit integer.
Definition math.h:136
static uint8_t fr_high_bit_pos(uint64_t num)
Find the highest order high bit in an unsigned 64 bit integer.
Definition math.h:94
unsigned char uint8_t