Zephyr API Documentation 4.5.99
A Scalable Open Source RTOS
Loading...
Searching...
No Matches
div64.h
Go to the documentation of this file.
1/*
2 * SPDX-FileCopyrightText: Copyright (c) 2026 BayLibre SAS
3 * SPDX-License-Identifier: Apache-2.0
4 */
5
11
12#ifndef ZEPHYR_INCLUDE_SYS_DIV64_H_
13#define ZEPHYR_INCLUDE_SYS_DIV64_H_
14
15#include <stdbool.h>
16#include <stddef.h>
17#include <stdint.h>
18
19#include <zephyr/toolchain.h>
21
22#ifdef __cplusplus
23extern "C" {
24#endif
25
37
39
40/*
41 * The reciprocals need __builtin_constant_p(), __builtin_clz() and
42 * __builtin_ctz(). A compiler that does not report them through
43 * HAS_BUILTIN() divides plainly, as on a 64-bit target.
44 *
45 * Z_DIV64_IF_CONST(n, a, b) gives a when n is an integer constant
46 * expression, as in a static initializer, and b otherwise. GCC and clang,
47 * in C and C++, and IAR iccarm fold the condition, so the result is a
48 * constant expression when a is. The leading "0 +" keeps GCC from giving
49 * -Wint-in-bool-context when the result is cast to bool and a and b are
50 * both multiplies.
51 */
52#if HAS_BUILTIN(__builtin_constant_p) && HAS_BUILTIN(__builtin_clz) && HAS_BUILTIN(__builtin_ctz)
53#define Z_DIV64_IF_CONST(n, a, b) (0 + (__builtin_constant_p(n) ? (a) : (b)))
54#else
55#define Z_DIV64_NO_BUILTINS
56#define Z_DIV64_IF_CONST(n, a, b) (a)
57#endif
58
59/* Plain division for a constant divisor */
60#if defined(CONFIG_64BIT) || defined(CONFIG_NO_OPTIMIZATIONS) || defined(Z_DIV64_NO_BUILTINS)
61#define Z_DIV64_PLAIN
62#endif
63
64/* Plain division for a run-time divisor */
65#if defined(CONFIG_64BIT) || defined(Z_DIV64_NO_BUILTINS)
66#define Z_DIV64_PLAIN_RECIP
67#endif
68
69/*
70 * n / d = ((n * m) >> 64) >> k, with m ~= 2^64 * p / d:
71 *
72 * 1. p = 2^k is the largest power of two below d, so m uses all 64 bits.
73 * 2. With m rounded up, m * d = 2^(64 + k) + e, and n * m >> (64 + k) is
74 * n / d plus n * e / (d * 2^(64 + k)). That is exact for every 64-bit n
75 * if e <= p.
76 * 3. Otherwise m is rounded down, so m * d = 2^(64 + k) - (d - e), with
77 * d - e < p, and the product gets m added:
78 * (n * m + m) >> 64 = ((n + 1) * m) >> 64. That is the bias. It is exact
79 * for every 64-bit n.
80 * 4. Common factors of two come out of m and p. A smaller m may allow the
81 * short multiply. m has at most k of them, as m * d is within d of
82 * 2^(64 + k).
83 *
84 * In 8 bits, dividing by 10: p = 8, m = ceil(256 * 8 / 10) = 205, e = 2, so
85 * n / 10 = (n * 205) >> 11.
86 *
87 * These are integer constant expressions, so SYS_DIV64_RECIP_INIT() is a
88 * static initializer, and the optimizer folds them for a constant d. With
89 * 2^64 = q * d + r, m rounded down is q * p + r * p / d, and r * p % d is
90 * d - e. A power of two d, 1 included, is a plain shift instead.
91 */
92
93#define Z_DIV64_LOG2(d) (31 - __builtin_clz(((uint32_t)(d) - 1U) | 1U))
94#define Z_DIV64_P(d) (1ULL << Z_DIV64_LOG2(d))
95#define Z_DIV64_Q(d) (UINT64_MAX / (d))
96#define Z_DIV64_R(d) ((UINT64_MAX % (d)) + 1ULL)
97#define Z_DIV64_REM(d) ((Z_DIV64_R(d) * Z_DIV64_P(d)) % (d))
98#define Z_DIV64_BIAS(d) ((Z_DIV64_REM(d) != 0U) && (Z_DIV64_REM(d) < (d) - Z_DIV64_P(d)))
99#define Z_DIV64_M0(d) \
100 ((Z_DIV64_Q(d) * Z_DIV64_P(d)) + ((Z_DIV64_R(d) * Z_DIV64_P(d)) / (d)) + \
101 (((Z_DIV64_REM(d) != 0U) && !Z_DIV64_BIAS(d)) ? 1U : 0U))
102#define Z_DIV64_ZEROS(d) __builtin_ctz((uint32_t)Z_DIV64_M0(d) | (uint32_t)Z_DIV64_P(d))
103#define Z_DIV64_M(d) (Z_DIV64_M0(d) >> Z_DIV64_ZEROS(d))
104#define Z_DIV64_SHIFT(d) ((uint32_t)(Z_DIV64_LOG2(d) - Z_DIV64_ZEROS(d)))
105#define Z_DIV64_LO(x) ((x) & 0xffffffffULL)
106#define Z_DIV64_HI(x) ((x) >> 32)
107
108#define Z_DIV64_FLAG_BIAS 0x80U
109#define Z_DIV64_FLAG_SHIFT 0x40U /* n >> shift, for a power of two */
110#define Z_DIV64_SHIFT_MASK 0x3fU
111#define Z_DIV64_FLAGS(d) (Z_DIV64_SHIFT(d) | (Z_DIV64_BIAS(d) ? Z_DIV64_FLAG_BIAS : 0U))
112
113/* The short form of z_div64_mulhi() needs room for a carry between m's halves. */
114#define Z_DIV64_NO_OVF(d) ((Z_DIV64_HI(Z_DIV64_M(d)) + Z_DIV64_LO(Z_DIV64_M(d))) <= UINT32_MAX)
115
116#define Z_DIV64_ILOG2(d) (31 - __builtin_clz((uint32_t)(d)))
117
118/* (n * m) >> 64, adding m first when @p bias is set. @p bias and @p no_ovf
119 * are constant at each call site, so only one form is emitted.
120 */
121static ALWAYS_INLINE uint64_t z_div64_mulhi(uint64_t n, uint64_t m, bool bias, bool no_ovf)
122{
123 uint32_t m_lo = (uint32_t)m;
124 uint32_t m_hi = (uint32_t)(m >> 32);
125 uint32_t n_lo = (uint32_t)n;
126 uint32_t n_hi = (uint32_t)(n >> 32);
127 uint64_t x;
128 uint64_t y;
129
130 if (no_ovf) {
131 x = ((uint64_t)m_lo * n_lo) + (bias ? m : 0U);
132 x >>= 32;
133 x += (uint64_t)m_lo * n_hi;
134 x += (uint64_t)m_hi * n_lo;
135 x >>= 32;
136 x += (uint64_t)m_hi * n_hi;
137 } else {
138 x = ((uint64_t)m_lo * n_lo) + (bias ? m_lo : 0U);
139 y = ((uint64_t)m_lo * n_hi) + (uint32_t)(x >> 32) + (bias ? m_hi : 0U);
140 x = ((uint64_t)m_hi * n_hi) + (uint32_t)(y >> 32);
141 y = ((uint64_t)m_hi * n_lo) + (uint32_t)y;
142 x += (uint32_t)(y >> 32);
143 }
144
145 return x;
146}
147
148/* n / d from the m and flags of a reciprocal of d. */
149__attribute_const__ uint64_t z_div64_u32_recip(uint64_t n, uint64_t m, uint32_t flags);
150
151struct sys_div64_recip;
152
153/* n / d from a shared reciprocal of d. Those never change, so the result
154 * depends only on the arguments.
155 */
156__attribute_const__ uint64_t z_div64_shared_div(uint64_t n, const struct sys_div64_recip *r);
157
158#if defined(CONFIG_SYS_CLOCK_TICKS_PER_SEC)
159#define Z_DIV64_TICKS ((uint32_t)CONFIG_SYS_CLOCK_TICKS_PER_SEC)
160#else
161#define Z_DIV64_TICKS 0U
162#endif
163
164#if defined(CONFIG_SYS_CLOCK_HW_CYCLES_PER_SEC) && \
165 !defined(CONFIG_TIMER_READS_ITS_FREQUENCY_AT_RUNTIME)
166#define Z_DIV64_CYCLES ((uint32_t)CONFIG_SYS_CLOCK_HW_CYCLES_PER_SEC)
167#else
168#define Z_DIV64_CYCLES 0U
169#endif
170
171/* a / b, or 0 when b is 0 */
172#define Z_DIV64_RATIO(a, b) (((b) != 0U) ? ((uint32_t)(a) / (((b) != 0U) ? (b) : 1U)) : 0U)
173
174/* Common divisors: the time units, the tick and cycle rates, and the ratios
175 * between them that time conversions divide by. An entry below 2 is unused.
176 */
177#define Z_DIV64_SHARED_LIST(X) \
178 X(1000, 1000U) \
179 X(1000000, 1000000U) \
180 X(1000000000, 1000000000U) \
181 X(ticks, Z_DIV64_TICKS) \
182 X(cycles, Z_DIV64_CYCLES) \
183 X(ms_per_tick, Z_DIV64_RATIO(1000U, Z_DIV64_TICKS)) \
184 X(us_per_tick, Z_DIV64_RATIO(1000000U, Z_DIV64_TICKS)) \
185 X(ns_per_tick, Z_DIV64_RATIO(1000000000U, Z_DIV64_TICKS)) \
186 X(ticks_per_ms, Z_DIV64_RATIO(Z_DIV64_TICKS, 1000U)) \
187 X(cycles_per_ms, Z_DIV64_RATIO(Z_DIV64_CYCLES, 1000U)) \
188 X(cycles_per_us, Z_DIV64_RATIO(Z_DIV64_CYCLES, 1000000U)) \
189 X(cycles_per_tick, Z_DIV64_RATIO(Z_DIV64_CYCLES, Z_DIV64_TICKS)) \
190 X(ns_per_cycle, Z_DIV64_RATIO(1000000000U, Z_DIV64_CYCLES))
191
192#define Z_DIV64_SHARED_DECLARE(name, v) extern const struct sys_div64_recip z_div64_recip_##name;
193Z_DIV64_SHARED_LIST(Z_DIV64_SHARED_DECLARE)
194
195#define Z_DIV64_SHARED_MATCH(name, v) \
196 if (((v) > 1U) && (d == (v))) { \
197 return &z_div64_recip_##name; \
198 }
199
200/* The shared reciprocal of d, or NULL. A call passes a pointer to it instead
201 * of loading m and flags.
202 */
203static ALWAYS_INLINE const struct sys_div64_recip *z_div64_shared(uint64_t d)
204{
205 Z_DIV64_SHARED_LIST(Z_DIV64_SHARED_MATCH)
206 return NULL;
207}
208
209/* n / d for a constant d. The derivation folds away once inlined. A
210 * non-constant d, or a build without the optimizer, divides plainly.
211 */
212static ALWAYS_INLINE uint64_t z_div64_u32_const(uint64_t n, uint64_t d, bool inl)
213{
214#if defined(Z_DIV64_PLAIN)
215 ARG_UNUSED(inl);
216 return n / d;
217#else
218 uint64_t q;
219
220 /* The compiler shifts for a power of two, and handles 0 as plain C does. */
221 if (!__builtin_constant_p(d) || (d == 0U) || (d > UINT32_MAX) || IS_POWER_OF_TWO(d)) {
222 return n / d;
223 }
224 if (inl) {
225 q = z_div64_mulhi(n, Z_DIV64_M(d), Z_DIV64_BIAS(d), Z_DIV64_NO_OVF(d)) >>
226 Z_DIV64_SHIFT(d);
227 } else if (z_div64_shared(d) != NULL) {
228 q = z_div64_shared_div(n, z_div64_shared(d));
229 } else {
230 q = z_div64_u32_recip(n, Z_DIV64_M(d), Z_DIV64_FLAGS(d));
231 }
232
233 /* A constant n folds once inlined, and the unused call goes away. Not
234 * branching on it lets the quotient of n / d and n % d be shared.
235 */
236 return __builtin_constant_p(n) ? (n / d) : q;
237#endif
238}
239
240#define Z_DIV64_U32_CONST(n, d, inl) \
241 Z_DIV64_IF_CONST(n, (uint64_t)(n) / (d), z_div64_u32_const((n), (d), (inl)))
242
243static ALWAYS_INLINE uint32_t z_mod64_u32_const(uint64_t n, uint64_t d)
244{
245 return (uint32_t)(n -
246 (z_div64_u32_const(n, d, IS_ENABLED(CONFIG_SPEED_OPTIMIZATIONS)) * d));
247}
248
249static ALWAYS_INLINE int64_t z_sdiv64_u32_const(int64_t n, uint64_t d)
250{
251#if defined(Z_DIV64_PLAIN)
252 return n / (int64_t)d;
253#else
254 uint64_t q = z_div64_u32_const((n < 0) ? (0U - (uint64_t)n) : (uint64_t)n, d,
255 IS_ENABLED(CONFIG_SPEED_OPTIMIZATIONS));
256
257 return (n < 0) ? (int64_t)(0U - q) : (int64_t)q;
258#endif
259}
260
262
277#define sys_div64_u32_const(n, d) Z_DIV64_U32_CONST(n, d, IS_ENABLED(CONFIG_SPEED_OPTIMIZATIONS))
278
290#define sys_div64_u32_const_inline(n, d) Z_DIV64_U32_CONST(n, d, true)
291
303#define sys_mod64_u32_const(n, d) \
304 Z_DIV64_IF_CONST(n, (uint32_t)((uint64_t)(n) % (d)), z_mod64_u32_const((n), (d)))
305
316#define sys_sdiv64_u32_const(n, d) \
317 Z_DIV64_IF_CONST(n, (int64_t)(n) / (int64_t)(d), z_sdiv64_u32_const((n), (d)))
318
327 uint32_t div;
328#if !defined(Z_DIV64_PLAIN_RECIP)
330 uint64_t m;
331#endif
333};
334
340#if defined(Z_DIV64_PLAIN_RECIP)
341#define SYS_DIV64_RECIP_INIT(d) {.div = (d)}
342#else
343#define SYS_DIV64_RECIP_INIT(d) \
344 { \
345 .div = (d), \
346 .flags = IS_POWER_OF_TWO(d) ? (Z_DIV64_ILOG2(d) | Z_DIV64_FLAG_SHIFT) \
347 : Z_DIV64_FLAGS(d), \
348 .m = IS_POWER_OF_TWO(d) ? 0U : Z_DIV64_M(d), \
349 }
350#endif
351
352#if defined(Z_DIV64_PLAIN_RECIP) || defined(__DOXYGEN__)
353
363static inline void sys_div64_recip_init(struct sys_div64_recip *r, uint32_t d)
364{
365 r->div = d;
366}
367
368#else
369
371
372#endif /* Z_DIV64_PLAIN_RECIP || __DOXYGEN__ */
373
382static inline uint64_t sys_div64_recip_div(uint64_t n, const struct sys_div64_recip *r)
383{
384#if defined(Z_DIV64_PLAIN_RECIP)
385 return n / r->div;
386#else
387 return z_div64_u32_recip(n, r->m, r->flags);
388#endif
389}
390
399static inline uint32_t sys_div64_recip_mod(uint64_t n, const struct sys_div64_recip *r)
400{
401#if defined(Z_DIV64_PLAIN_RECIP)
402 return (uint32_t)(n % r->div);
403#else
404 return (uint32_t)n - ((uint32_t)sys_div64_recip_div(n, r) * r->div);
405#endif
406}
407
409
410#ifdef __cplusplus
411}
412#endif
413
414#endif /* ZEPHYR_INCLUDE_SYS_DIV64_H_ */
#define IS_ENABLED(config_macro)
Check for macro definition in compiler-visible expressions.
Definition util_macro.h:166
#define IS_POWER_OF_TWO(x)
Check if a x is a power of two.
Definition util_macro.h:95
static void sys_div64_recip_init(struct sys_div64_recip *r, uint32_t d)
Set up the reciprocal of a divisor.
Definition div64.h:363
static uint64_t sys_div64_recip_div(uint64_t n, const struct sys_div64_recip *r)
Divide a 64-bit value by a reciprocal's divisor.
Definition div64.h:382
static uint32_t sys_div64_recip_mod(uint64_t n, const struct sys_div64_recip *r)
Remainder of a 64-bit value divided by a reciprocal's divisor.
Definition div64.h:399
flags
Definition parser.h:86
__UINT32_TYPE__ uint32_t
Definition stdint.h:90
__UINT64_TYPE__ uint64_t
Definition stdint.h:91
#define UINT32_MAX
Definition stdint.h:29
__INT64_TYPE__ int64_t
Definition stdint.h:75
Reciprocal of a 32-bit divisor known only at run time.
Definition div64.h:325
Macros to abstract toolchain specific capabilities.
Macro utilities.