^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /* SPDX-License-Identifier: GPL-2.0-or-later */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /* Integer base 2 logarithm calculation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Written by David Howells (dhowells@redhat.com)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) #ifndef _TOOLS_LINUX_LOG2_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #define _TOOLS_LINUX_LOG2_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) #include <linux/bitops.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) #include <linux/types.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * non-constant log of base 2 calculators
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * - the arch may override these in asm/bitops.h if they can be implemented
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * more efficiently than using fls() and fls64()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * - the arch is not required to handle n==0 if implementing the fallback
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) static inline __attribute__((const))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) int __ilog2_u32(u32 n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) return fls(n) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) static inline __attribute__((const))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) int __ilog2_u64(u64 n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) return fls64(n) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) * Determine whether some value is a power of two, where zero is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) * *not* considered a power of two.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) static inline __attribute__((const))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) bool is_power_of_2(unsigned long n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) return (n != 0 && ((n & (n - 1)) == 0));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) * round up to nearest power of two
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) static inline __attribute__((const))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) unsigned long __roundup_pow_of_two(unsigned long n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) return 1UL << fls_long(n - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) * round down to nearest power of two
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) static inline __attribute__((const))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) unsigned long __rounddown_pow_of_two(unsigned long n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) return 1UL << (fls_long(n) - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * @n - parameter
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) * constant-capable log of base 2 calculation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) * - this can be used to initialise global variables from constant data, hence
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) * the massive ternary operator construction
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) * selects the appropriately-sized optimised version depending on sizeof(n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) #define ilog2(n) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) ( \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) __builtin_constant_p(n) ? ( \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) (n) < 2 ? 0 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) (n) & (1ULL << 63) ? 63 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) (n) & (1ULL << 62) ? 62 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) (n) & (1ULL << 61) ? 61 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) (n) & (1ULL << 60) ? 60 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) (n) & (1ULL << 59) ? 59 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) (n) & (1ULL << 58) ? 58 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) (n) & (1ULL << 57) ? 57 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) (n) & (1ULL << 56) ? 56 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) (n) & (1ULL << 55) ? 55 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) (n) & (1ULL << 54) ? 54 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) (n) & (1ULL << 53) ? 53 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) (n) & (1ULL << 52) ? 52 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) (n) & (1ULL << 51) ? 51 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) (n) & (1ULL << 50) ? 50 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) (n) & (1ULL << 49) ? 49 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) (n) & (1ULL << 48) ? 48 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) (n) & (1ULL << 47) ? 47 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) (n) & (1ULL << 46) ? 46 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) (n) & (1ULL << 45) ? 45 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) (n) & (1ULL << 44) ? 44 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) (n) & (1ULL << 43) ? 43 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) (n) & (1ULL << 42) ? 42 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) (n) & (1ULL << 41) ? 41 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) (n) & (1ULL << 40) ? 40 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) (n) & (1ULL << 39) ? 39 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) (n) & (1ULL << 38) ? 38 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) (n) & (1ULL << 37) ? 37 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) (n) & (1ULL << 36) ? 36 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) (n) & (1ULL << 35) ? 35 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) (n) & (1ULL << 34) ? 34 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) (n) & (1ULL << 33) ? 33 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) (n) & (1ULL << 32) ? 32 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) (n) & (1ULL << 31) ? 31 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) (n) & (1ULL << 30) ? 30 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) (n) & (1ULL << 29) ? 29 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) (n) & (1ULL << 28) ? 28 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) (n) & (1ULL << 27) ? 27 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) (n) & (1ULL << 26) ? 26 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) (n) & (1ULL << 25) ? 25 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) (n) & (1ULL << 24) ? 24 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) (n) & (1ULL << 23) ? 23 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) (n) & (1ULL << 22) ? 22 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) (n) & (1ULL << 21) ? 21 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) (n) & (1ULL << 20) ? 20 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) (n) & (1ULL << 19) ? 19 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) (n) & (1ULL << 18) ? 18 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) (n) & (1ULL << 17) ? 17 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) (n) & (1ULL << 16) ? 16 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) (n) & (1ULL << 15) ? 15 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) (n) & (1ULL << 14) ? 14 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) (n) & (1ULL << 13) ? 13 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) (n) & (1ULL << 12) ? 12 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) (n) & (1ULL << 11) ? 11 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) (n) & (1ULL << 10) ? 10 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) (n) & (1ULL << 9) ? 9 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) (n) & (1ULL << 8) ? 8 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) (n) & (1ULL << 7) ? 7 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) (n) & (1ULL << 6) ? 6 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) (n) & (1ULL << 5) ? 5 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) (n) & (1ULL << 4) ? 4 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) (n) & (1ULL << 3) ? 3 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) (n) & (1ULL << 2) ? 2 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) 1 ) : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) (sizeof(n) <= 4) ? \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) __ilog2_u32(n) : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) __ilog2_u64(n) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) )
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) * roundup_pow_of_two - round the given value up to nearest power of two
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) * @n - parameter
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) * round the given value up to the nearest power of two
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) * - the result is undefined when n == 0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) * - this can be used to initialise global variables from constant data
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) #define roundup_pow_of_two(n) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) ( \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) __builtin_constant_p(n) ? ( \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) (n == 1) ? 1 : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) (1UL << (ilog2((n) - 1) + 1)) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) ) : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) __roundup_pow_of_two(n) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) )
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) * rounddown_pow_of_two - round the given value down to nearest power of two
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) * @n - parameter
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) * round the given value down to the nearest power of two
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) * - the result is undefined when n == 0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) * - this can be used to initialise global variables from constant data
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) #define rounddown_pow_of_two(n) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) ( \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) __builtin_constant_p(n) ? ( \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) (1UL << ilog2(n))) : \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) __rounddown_pow_of_two(n) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) )
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) #endif /* _TOOLS_LINUX_LOG2_H */
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags