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 */
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.
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
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
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.
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
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
75__CONSTEXPR static inline __ALWAYS_INLINE uint log2_ulong_ceil(ulong val)
76{
77    return _log2_ulong(val, true);
78}
79
80__CONSTEXPR static inline __ALWAYS_INLINE uint valpow2(uint valp2)
81{
82    return 1U << valp2;
83}
84
85__CONSTEXPR static inline __ALWAYS_INLINE uint divpow2(uint val, uint divp2)
86{
87    return val >> divp2;
88}
89
90__CONSTEXPR static inline __ALWAYS_INLINE uint modpow2(uint val, uint modp2)
91{
92    return val & ((1U << modp2) - 1);
93}
94
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).
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