xref: /dflybsd-src/sys/dev/drm/include/linux/log2.h (revision bf05ec5b49b864b7b7fbbd87377fc350e57fa79a)
11392385eSFrançois Tigeot /*-
21392385eSFrançois Tigeot  * Copyright (c) 2010 Isilon Systems, Inc.
31392385eSFrançois Tigeot  * Copyright (c) 2010 iX Systems, Inc.
41392385eSFrançois Tigeot  * Copyright (c) 2010 Panasas, Inc.
51392385eSFrançois Tigeot  * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd.
61392385eSFrançois Tigeot  * All rights reserved.
71392385eSFrançois Tigeot  *
81392385eSFrançois Tigeot  * Redistribution and use in source and binary forms, with or without
91392385eSFrançois Tigeot  * modification, are permitted provided that the following conditions
101392385eSFrançois Tigeot  * are met:
111392385eSFrançois Tigeot  * 1. Redistributions of source code must retain the above copyright
121392385eSFrançois Tigeot  *    notice unmodified, this list of conditions, and the following
131392385eSFrançois Tigeot  *    disclaimer.
141392385eSFrançois Tigeot  * 2. Redistributions in binary form must reproduce the above copyright
151392385eSFrançois Tigeot  *    notice, this list of conditions and the following disclaimer in the
161392385eSFrançois Tigeot  *    documentation and/or other materials provided with the distribution.
171392385eSFrançois Tigeot  *
181392385eSFrançois Tigeot  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
191392385eSFrançois Tigeot  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
201392385eSFrançois Tigeot  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
211392385eSFrançois Tigeot  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
221392385eSFrançois Tigeot  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
231392385eSFrançois Tigeot  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
241392385eSFrançois Tigeot  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
251392385eSFrançois Tigeot  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
261392385eSFrançois Tigeot  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
271392385eSFrançois Tigeot  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
281392385eSFrançois Tigeot  */
291392385eSFrançois Tigeot 
301392385eSFrançois Tigeot #ifndef	_LINUX_LOG2_H_
311392385eSFrançois Tigeot #define	_LINUX_LOG2_H_
321392385eSFrançois Tigeot 
331392385eSFrançois Tigeot #include <linux/types.h>
341392385eSFrançois Tigeot 
351392385eSFrançois Tigeot #include <sys/libkern.h>
361392385eSFrançois Tigeot 
371392385eSFrançois Tigeot static inline unsigned long
381392385eSFrançois Tigeot roundup_pow_of_two(unsigned long x)
391392385eSFrançois Tigeot {
401392385eSFrançois Tigeot 	return (1UL << flsl(x - 1));
411392385eSFrançois Tigeot }
421392385eSFrançois Tigeot 
431392385eSFrançois Tigeot static inline int
441392385eSFrançois Tigeot is_power_of_2(unsigned long n)
451392385eSFrançois Tigeot {
461392385eSFrançois Tigeot 	return (n == roundup_pow_of_two(n));
471392385eSFrançois Tigeot }
481392385eSFrançois Tigeot 
491392385eSFrançois Tigeot static inline unsigned long
501392385eSFrançois Tigeot rounddown_pow_of_two(unsigned long x)
511392385eSFrançois Tigeot {
521392385eSFrançois Tigeot         return (1UL << (flsl(x) - 1));
531392385eSFrançois Tigeot }
541392385eSFrançois Tigeot 
551392385eSFrançois Tigeot 
561392385eSFrançois Tigeot /*
571392385eSFrançois Tigeot  * deal with unrepresentable constant logarithms
581392385eSFrançois Tigeot  */
591392385eSFrançois Tigeot extern __attribute__((const, noreturn))
601392385eSFrançois Tigeot int ____ilog2_NaN(void);
611392385eSFrançois Tigeot 
621392385eSFrançois Tigeot /*
631392385eSFrançois Tigeot  * non-constant log of base 2 calculators
641392385eSFrançois Tigeot  * - the arch may override these in asm/bitops.h if they can be implemented
651392385eSFrançois Tigeot  *   more efficiently than using fls() and fls64()
661392385eSFrançois Tigeot  * - the arch is not required to handle n==0 if implementing the fallback
671392385eSFrançois Tigeot  */
681392385eSFrançois Tigeot #ifndef CONFIG_ARCH_HAS_ILOG2_U32
691392385eSFrançois Tigeot static inline __attribute__((const))
701392385eSFrançois Tigeot int __ilog2_u32(u32 n)
711392385eSFrançois Tigeot {
721392385eSFrançois Tigeot 	return flsl(n) - 1;
731392385eSFrançois Tigeot }
741392385eSFrançois Tigeot #endif
751392385eSFrançois Tigeot 
761392385eSFrançois Tigeot #ifndef CONFIG_ARCH_HAS_ILOG2_U64
771392385eSFrançois Tigeot static inline __attribute__((const))
781392385eSFrançois Tigeot int __ilog2_u64(u64 n)
791392385eSFrançois Tigeot {
801392385eSFrançois Tigeot 	return flsl(n) - 1;
811392385eSFrançois Tigeot }
821392385eSFrançois Tigeot #endif
831392385eSFrançois Tigeot 
841392385eSFrançois Tigeot 
851392385eSFrançois Tigeot /**
861392385eSFrançois Tigeot  * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
871392385eSFrançois Tigeot  * @n - parameter
881392385eSFrançois Tigeot  *
891392385eSFrançois Tigeot  * constant-capable log of base 2 calculation
901392385eSFrançois Tigeot  * - this can be used to initialise global variables from constant data, hence
911392385eSFrançois Tigeot  *   the massive ternary operator construction
921392385eSFrançois Tigeot  *
931392385eSFrançois Tigeot  * selects the appropriately-sized optimised version depending on sizeof(n)
941392385eSFrançois Tigeot  */
951392385eSFrançois Tigeot #define ilog2(n)				\
961392385eSFrançois Tigeot (						\
971392385eSFrançois Tigeot 	__builtin_constant_p(n) ? (		\
981392385eSFrançois Tigeot 		(n) < 1 ? ____ilog2_NaN() :	\
991392385eSFrançois Tigeot 		(n) & (1ULL << 63) ? 63 :	\
1001392385eSFrançois Tigeot 		(n) & (1ULL << 62) ? 62 :	\
1011392385eSFrançois Tigeot 		(n) & (1ULL << 61) ? 61 :	\
1021392385eSFrançois Tigeot 		(n) & (1ULL << 60) ? 60 :	\
1031392385eSFrançois Tigeot 		(n) & (1ULL << 59) ? 59 :	\
1041392385eSFrançois Tigeot 		(n) & (1ULL << 58) ? 58 :	\
1051392385eSFrançois Tigeot 		(n) & (1ULL << 57) ? 57 :	\
1061392385eSFrançois Tigeot 		(n) & (1ULL << 56) ? 56 :	\
1071392385eSFrançois Tigeot 		(n) & (1ULL << 55) ? 55 :	\
1081392385eSFrançois Tigeot 		(n) & (1ULL << 54) ? 54 :	\
1091392385eSFrançois Tigeot 		(n) & (1ULL << 53) ? 53 :	\
1101392385eSFrançois Tigeot 		(n) & (1ULL << 52) ? 52 :	\
1111392385eSFrançois Tigeot 		(n) & (1ULL << 51) ? 51 :	\
1121392385eSFrançois Tigeot 		(n) & (1ULL << 50) ? 50 :	\
1131392385eSFrançois Tigeot 		(n) & (1ULL << 49) ? 49 :	\
1141392385eSFrançois Tigeot 		(n) & (1ULL << 48) ? 48 :	\
1151392385eSFrançois Tigeot 		(n) & (1ULL << 47) ? 47 :	\
1161392385eSFrançois Tigeot 		(n) & (1ULL << 46) ? 46 :	\
1171392385eSFrançois Tigeot 		(n) & (1ULL << 45) ? 45 :	\
1181392385eSFrançois Tigeot 		(n) & (1ULL << 44) ? 44 :	\
1191392385eSFrançois Tigeot 		(n) & (1ULL << 43) ? 43 :	\
1201392385eSFrançois Tigeot 		(n) & (1ULL << 42) ? 42 :	\
1211392385eSFrançois Tigeot 		(n) & (1ULL << 41) ? 41 :	\
1221392385eSFrançois Tigeot 		(n) & (1ULL << 40) ? 40 :	\
1231392385eSFrançois Tigeot 		(n) & (1ULL << 39) ? 39 :	\
1241392385eSFrançois Tigeot 		(n) & (1ULL << 38) ? 38 :	\
1251392385eSFrançois Tigeot 		(n) & (1ULL << 37) ? 37 :	\
1261392385eSFrançois Tigeot 		(n) & (1ULL << 36) ? 36 :	\
1271392385eSFrançois Tigeot 		(n) & (1ULL << 35) ? 35 :	\
1281392385eSFrançois Tigeot 		(n) & (1ULL << 34) ? 34 :	\
1291392385eSFrançois Tigeot 		(n) & (1ULL << 33) ? 33 :	\
1301392385eSFrançois Tigeot 		(n) & (1ULL << 32) ? 32 :	\
1311392385eSFrançois Tigeot 		(n) & (1ULL << 31) ? 31 :	\
1321392385eSFrançois Tigeot 		(n) & (1ULL << 30) ? 30 :	\
1331392385eSFrançois Tigeot 		(n) & (1ULL << 29) ? 29 :	\
1341392385eSFrançois Tigeot 		(n) & (1ULL << 28) ? 28 :	\
1351392385eSFrançois Tigeot 		(n) & (1ULL << 27) ? 27 :	\
1361392385eSFrançois Tigeot 		(n) & (1ULL << 26) ? 26 :	\
1371392385eSFrançois Tigeot 		(n) & (1ULL << 25) ? 25 :	\
1381392385eSFrançois Tigeot 		(n) & (1ULL << 24) ? 24 :	\
1391392385eSFrançois Tigeot 		(n) & (1ULL << 23) ? 23 :	\
1401392385eSFrançois Tigeot 		(n) & (1ULL << 22) ? 22 :	\
1411392385eSFrançois Tigeot 		(n) & (1ULL << 21) ? 21 :	\
1421392385eSFrançois Tigeot 		(n) & (1ULL << 20) ? 20 :	\
1431392385eSFrançois Tigeot 		(n) & (1ULL << 19) ? 19 :	\
1441392385eSFrançois Tigeot 		(n) & (1ULL << 18) ? 18 :	\
1451392385eSFrançois Tigeot 		(n) & (1ULL << 17) ? 17 :	\
1461392385eSFrançois Tigeot 		(n) & (1ULL << 16) ? 16 :	\
1471392385eSFrançois Tigeot 		(n) & (1ULL << 15) ? 15 :	\
1481392385eSFrançois Tigeot 		(n) & (1ULL << 14) ? 14 :	\
1491392385eSFrançois Tigeot 		(n) & (1ULL << 13) ? 13 :	\
1501392385eSFrançois Tigeot 		(n) & (1ULL << 12) ? 12 :	\
1511392385eSFrançois Tigeot 		(n) & (1ULL << 11) ? 11 :	\
1521392385eSFrançois Tigeot 		(n) & (1ULL << 10) ? 10 :	\
1531392385eSFrançois Tigeot 		(n) & (1ULL <<  9) ?  9 :	\
1541392385eSFrançois Tigeot 		(n) & (1ULL <<  8) ?  8 :	\
1551392385eSFrançois Tigeot 		(n) & (1ULL <<  7) ?  7 :	\
1561392385eSFrançois Tigeot 		(n) & (1ULL <<  6) ?  6 :	\
1571392385eSFrançois Tigeot 		(n) & (1ULL <<  5) ?  5 :	\
1581392385eSFrançois Tigeot 		(n) & (1ULL <<  4) ?  4 :	\
1591392385eSFrançois Tigeot 		(n) & (1ULL <<  3) ?  3 :	\
1601392385eSFrançois Tigeot 		(n) & (1ULL <<  2) ?  2 :	\
1611392385eSFrançois Tigeot 		(n) & (1ULL <<  1) ?  1 :	\
1621392385eSFrançois Tigeot 		(n) & (1ULL <<  0) ?  0 :	\
1631392385eSFrançois Tigeot 		____ilog2_NaN()			\
1641392385eSFrançois Tigeot 				   ) :		\
1651392385eSFrançois Tigeot 	(sizeof(n) <= 4) ?			\
1661392385eSFrançois Tigeot 	__ilog2_u32(n) :			\
1671392385eSFrançois Tigeot 	__ilog2_u64(n)				\
1681392385eSFrançois Tigeot  )
1691392385eSFrançois Tigeot 
170*bf05ec5bSzrj #define order_base_2(n) ilog2(roundup_pow_of_two(n))
171*bf05ec5bSzrj 
1721392385eSFrançois Tigeot #endif	/* _LINUX_LOG2_H_ */
173