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