1 // Copyright 2016 The Fuchsia Authors
2 // Copyright (c) 2008-2014 Travis Geiselbrecht
3 //
4 // Use of this source code is governed by a MIT-style
5 // license that can be found in the LICENSE file or at
6 // https://opensource.org/licenses/MIT
7
8 #pragma once
9
10 #include <sys/types.h>
11 #include <stdbool.h>
12 #include <stdint.h>
13 #include <zircon/compiler.h>
14
15 __BEGIN_CDECLS
16
17 /* routines for dealing with power of 2 values for efficiency
18 * Considers 0 to be a power of 2 */
ispow2(uint val)19 __CONSTEXPR static inline __ALWAYS_INLINE bool ispow2(uint val)
20 {
21 return ((val - 1) & val) == 0;
22 }
23
24 // Compute log2(|val|), rounded as requested by |ceiling|. We define
25 // log2(0) to be 0.
_log2_uint(uint val,bool ceiling)26 __CONSTEXPR static inline __ALWAYS_INLINE uint _log2_uint(uint val, bool ceiling)
27 {
28 if (val == 0)
29 return 0;
30
31 uint log2 = (uint)(sizeof(val) * CHAR_BIT) - 1 - __builtin_clz(val);
32
33 if (ceiling && val - (1u << log2) > 0) {
34 ++log2;
35 }
36
37 return log2;
38 }
39
40 // Compute floor(log2(|val|)), or 0 if |val| is 0
log2_uint_floor(uint val)41 __CONSTEXPR static inline __ALWAYS_INLINE uint log2_uint_floor(uint val)
42 {
43 return _log2_uint(val, false);
44 }
45
46 // Compute ceil(log2(|val|)), or 0 if |val| is 0
log2_uint_ceil(uint val)47 __CONSTEXPR static inline __ALWAYS_INLINE uint log2_uint_ceil(uint val)
48 {
49 return _log2_uint(val, true);
50 }
51
52 // Compute log2(|val|), rounded as requested by |ceiling|. We define
53 // log2(0) to be 0.
_log2_ulong(ulong val,bool ceiling)54 __CONSTEXPR static inline __ALWAYS_INLINE uint _log2_ulong(ulong val, bool ceiling)
55 {
56 if (val == 0)
57 return 0;
58
59 uint log2 = (uint)(sizeof(val) * CHAR_BIT) - 1 - __builtin_clzl(val);
60
61 if (ceiling && val - (1ul << log2) > 0) {
62 ++log2;
63 }
64
65 return log2;
66 }
67
68 // Compute floor(log2(|val|)), or 0 if |val| is 0
log2_ulong_floor(ulong val)69 __CONSTEXPR static inline __ALWAYS_INLINE uint log2_ulong_floor(ulong val)
70 {
71 return _log2_ulong(val, false);
72 }
73
74 // Compute ceil(log2(|val|)), or 0 if |val| is 0
log2_ulong_ceil(ulong val)75 __CONSTEXPR static inline __ALWAYS_INLINE uint log2_ulong_ceil(ulong val)
76 {
77 return _log2_ulong(val, true);
78 }
79
valpow2(uint valp2)80 __CONSTEXPR static inline __ALWAYS_INLINE uint valpow2(uint valp2)
81 {
82 return 1U << valp2;
83 }
84
divpow2(uint val,uint divp2)85 __CONSTEXPR static inline __ALWAYS_INLINE uint divpow2(uint val, uint divp2)
86 {
87 return val >> divp2;
88 }
89
modpow2(uint val,uint modp2)90 __CONSTEXPR static inline __ALWAYS_INLINE uint modpow2(uint val, uint modp2)
91 {
92 return val & ((1U << modp2) - 1);
93 }
94
modpow2_u64(uint64_t val,uint modp2)95 __CONSTEXPR static inline __ALWAYS_INLINE uint64_t modpow2_u64(uint64_t val, uint modp2)
96 {
97 return val & ((1U << modp2) - 1);
98 }
99
100 // Cribbed from:
101 // http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
102 // Returns 0 if given 0 (i.e. considers 0 to be a power of 2 greater than
103 // 2^31).
round_up_pow2_u32(uint32_t v)104 __CONSTEXPR static inline __ALWAYS_INLINE uint32_t round_up_pow2_u32(uint32_t v)
105 {
106 v--;
107 v |= v >> 1;
108 v |= v >> 2;
109 v |= v >> 4;
110 v |= v >> 8;
111 v |= v >> 16;
112 v++;
113 return v;
114 }
115
116 __END_CDECLS
117