WebSVN – Kolibri OS – Diff – /drivers/include/linux/log2.h


/* Integer base 2 logarithm calculation
 *
 * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
 * Written by David Howells (dhowells@redhat.com)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version
 * 2 of the License, or (at your option) any later version.
 */
 
#ifndef _LINUX_LOG2_H
#define _LINUX_LOG2_H
 
#include 
#include 
 
/*
 
 
 
 
 
 
 * non-constant log of base 2 calculators
 * - the arch may override these in asm/bitops.h if they can be implemented
 *   more efficiently than using fls() and fls64()
 * - the arch is not required to handle n==0 if implementing the fallback
 */
#ifndef CONFIG_ARCH_HAS_ILOG2_U32
static inline __attribute__((const))
int __ilog2_u32(u32 n)
{
	return fls(n) - 1;
}
#endif
 
#ifndef CONFIG_ARCH_HAS_ILOG2_U64
static inline __attribute__((const))
int __ilog2_u64(u64 n)
{
	return fls64(n) - 1;
}
#endif
 
/*
 *  Determine whether some value is a power of two, where zero is
 * *not* considered a power of two.
 */
 
static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
	return (n != 0 && ((n & (n - 1)) == 0));
}
 
/*
 * round up to nearest power of two
 */
static inline __attribute__((const))
unsigned long __roundup_pow_of_two(unsigned long n)
{
	return 1UL << fls_long(n - 1);
}
 
/*
 * round down to nearest power of two
 */
static inline __attribute__((const))
unsigned long __rounddown_pow_of_two(unsigned long n)
{
	return 1UL << (fls_long(n) - 1);
}
 
/**
 * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
 * @n - parameter
 *
 * constant-capable log of base 2 calculation
 * - this can be used to initialise global variables from constant data, hence
 *   the massive ternary operator construction
 *
 * selects the appropriately-sized optimised version depending on sizeof(n)
 */
#define ilog2(n)				\
(						\
	__builtin_constant_p(n) ? (		\
		(n) < 2 ? 0 :			\
		(n) & (1ULL << 63) ? 63 :	\
		(n) & (1ULL << 62) ? 62 :	\
		(n) & (1ULL << 61) ? 61 :	\
		(n) & (1ULL << 60) ? 60 :	\
		(n) & (1ULL << 59) ? 59 :	\
		(n) & (1ULL << 58) ? 58 :	\
		(n) & (1ULL << 57) ? 57 :	\
		(n) & (1ULL << 56) ? 56 :	\
		(n) & (1ULL << 55) ? 55 :	\
		(n) & (1ULL << 54) ? 54 :	\
		(n) & (1ULL << 53) ? 53 :	\
		(n) & (1ULL << 52) ? 52 :	\
		(n) & (1ULL << 51) ? 51 :	\
		(n) & (1ULL << 50) ? 50 :	\
		(n) & (1ULL << 49) ? 49 :	\
		(n) & (1ULL << 48) ? 48 :	\
		(n) & (1ULL << 47) ? 47 :	\
		(n) & (1ULL << 46) ? 46 :	\
		(n) & (1ULL << 45) ? 45 :	\
		(n) & (1ULL << 44) ? 44 :	\
		(n) & (1ULL << 43) ? 43 :	\
		(n) & (1ULL << 42) ? 42 :	\
		(n) & (1ULL << 41) ? 41 :	\
		(n) & (1ULL << 40) ? 40 :	\
		(n) & (1ULL << 39) ? 39 :	\
		(n) & (1ULL << 38) ? 38 :	\
		(n) & (1ULL << 37) ? 37 :	\
		(n) & (1ULL << 36) ? 36 :	\
		(n) & (1ULL << 35) ? 35 :	\
		(n) & (1ULL << 34) ? 34 :	\
		(n) & (1ULL << 33) ? 33 :	\
		(n) & (1ULL << 32) ? 32 :	\
		(n) & (1ULL << 31) ? 31 :	\
		(n) & (1ULL << 30) ? 30 :	\
		(n) & (1ULL << 29) ? 29 :	\
		(n) & (1ULL << 28) ? 28 :	\
		(n) & (1ULL << 27) ? 27 :	\
		(n) & (1ULL << 26) ? 26 :	\
		(n) & (1ULL << 25) ? 25 :	\
		(n) & (1ULL << 24) ? 24 :	\
		(n) & (1ULL << 23) ? 23 :	\
		(n) & (1ULL << 22) ? 22 :	\
		(n) & (1ULL << 21) ? 21 :	\
		(n) & (1ULL << 20) ? 20 :	\
		(n) & (1ULL << 19) ? 19 :	\
		(n) & (1ULL << 18) ? 18 :	\
		(n) & (1ULL << 17) ? 17 :	\
		(n) & (1ULL << 16) ? 16 :	\
		(n) & (1ULL << 15) ? 15 :	\
		(n) & (1ULL << 14) ? 14 :	\
		(n) & (1ULL << 13) ? 13 :	\
		(n) & (1ULL << 12) ? 12 :	\
		(n) & (1ULL << 11) ? 11 :	\
		(n) & (1ULL << 10) ? 10 :	\
		(n) & (1ULL <<  9) ?  9 :	\
		(n) & (1ULL <<  8) ?  8 :	\
		(n) & (1ULL <<  7) ?  7 :	\
		(n) & (1ULL <<  6) ?  6 :	\
		(n) & (1ULL <<  5) ?  5 :	\
		(n) & (1ULL <<  4) ?  4 :	\
		(n) & (1ULL <<  3) ?  3 :	\
		(n) & (1ULL <<  2) ?  2 :	\
 
 
 
		1 ) :				\
	(sizeof(n) <= 4) ?			\
	__ilog2_u32(n) :			\
	__ilog2_u64(n)				\
 )
 
/**
 * roundup_pow_of_two - round the given value up to nearest power of two
 * @n - parameter
 *
 * round the given value up to the nearest power of two
 * - the result is undefined when n == 0
 * - this can be used to initialise global variables from constant data
 */
#define roundup_pow_of_two(n)			\
(						\
	__builtin_constant_p(n) ? (		\
		(n == 1) ? 1 :			\
		(1UL << (ilog2((n) - 1) + 1))	\
				   ) :		\
	__roundup_pow_of_two(n)			\
 )
 
/**
 * rounddown_pow_of_two - round the given value down to nearest power of two
 * @n - parameter
 *
 * round the given value down to the nearest power of two
 * - the result is undefined when n == 0
 * - this can be used to initialise global variables from constant data
 */
#define rounddown_pow_of_two(n)			\
(						\
	__builtin_constant_p(n) ? (		\
		(1UL << ilog2(n))) :		\
	__rounddown_pow_of_two(n)		\
 )
 
/**
 * order_base_2 - calculate the (rounded up) base 2 order of the argument
 * @n: parameter
 *
 * The first few values calculated by this routine:
 *  ob2(0) = 0
 *  ob2(1) = 0
 *  ob2(2) = 1
 *  ob2(3) = 2
 *  ob2(4) = 2
 *  ob2(5) = 3
 *  ... and so on.
 */
 
static inline __attribute_const__
int __order_base_2(unsigned long n)
{
	return n > 1 ? ilog2(n - 1) + 1 : 0;
}
 
#define order_base_2(n)				\
(						\
	__builtin_constant_p(n) ? (		\
		((n) == 0 || (n) == 1) ? 0 :	\
		ilog2((n) - 1) + 1) :		\
	__order_base_2(n)			\
)
#endif /* _LINUX_LOG2_H */

Rev 3031	Rev 6934
1	/* Integer base 2 logarithm calculation	1	/* Integer base 2 logarithm calculation
2	*	2	*
3	* Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.	3	* Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
4	* Written by David Howells (dhowells@redhat.com)	4	* Written by David Howells (dhowells@redhat.com)
5	*	5	*
6	* This program is free software; you can redistribute it and/or	6	* This program is free software; you can redistribute it and/or
7	* modify it under the terms of the GNU General Public License	7	* modify it under the terms of the GNU General Public License
8	* as published by the Free Software Foundation; either version	8	* as published by the Free Software Foundation; either version
9	* 2 of the License, or (at your option) any later version.	9	* 2 of the License, or (at your option) any later version.
10	*/	10	*/
11		11
12	#ifndef _LINUX_LOG2_H	12	#ifndef _LINUX_LOG2_H
13	#define _LINUX_LOG2_H	13	#define _LINUX_LOG2_H
14		14
15	#include	15	#include
16	#include	16	#include
17		17
18	/*	18	/*
19	* deal with unrepresentable constant logarithms	-
20	*/	-
21	extern __attribute__((const, noreturn))	-
22	int ____ilog2_NaN(void);	-
23		-
24	/*	-
25	* non-constant log of base 2 calculators	19	* non-constant log of base 2 calculators
26	* - the arch may override these in asm/bitops.h if they can be implemented	20	* - the arch may override these in asm/bitops.h if they can be implemented
27	* more efficiently than using fls() and fls64()	21	* more efficiently than using fls() and fls64()
28	* - the arch is not required to handle n==0 if implementing the fallback	22	* - the arch is not required to handle n==0 if implementing the fallback
29	*/	23	*/
30	#ifndef CONFIG_ARCH_HAS_ILOG2_U32	24	#ifndef CONFIG_ARCH_HAS_ILOG2_U32
31	static inline __attribute__((const))	25	static inline __attribute__((const))
32	int __ilog2_u32(u32 n)	26	int __ilog2_u32(u32 n)
33	{	27	{
34	return fls(n) - 1;	28	return fls(n) - 1;
35	}	29	}
36	#endif	30	#endif
37		31
38	#ifndef CONFIG_ARCH_HAS_ILOG2_U64	32	#ifndef CONFIG_ARCH_HAS_ILOG2_U64
39	static inline __attribute__((const))	33	static inline __attribute__((const))
40	int __ilog2_u64(u64 n)	34	int __ilog2_u64(u64 n)
41	{	35	{
42	return fls64(n) - 1;	36	return fls64(n) - 1;
43	}	37	}
44	#endif	38	#endif
45		39
46	/*	40	/*
47	* Determine whether some value is a power of two, where zero is	41	* Determine whether some value is a power of two, where zero is
48	* not considered a power of two.	42	* not considered a power of two.
49	*/	43	*/
50		44
51	static inline __attribute__((const))	45	static inline __attribute__((const))
52	bool is_power_of_2(unsigned long n)	46	bool is_power_of_2(unsigned long n)
53	{	47	{
54	return (n != 0 && ((n & (n - 1)) == 0));	48	return (n != 0 && ((n & (n - 1)) == 0));
55	}	49	}
56		50
57	/*	51	/*
58	* round up to nearest power of two	52	* round up to nearest power of two
59	*/	53	*/
60	static inline __attribute__((const))	54	static inline __attribute__((const))
61	unsigned long __roundup_pow_of_two(unsigned long n)	55	unsigned long __roundup_pow_of_two(unsigned long n)
62	{	56	{
63	return 1UL << fls_long(n - 1);	57	return 1UL << fls_long(n - 1);
64	}	58	}
65		59
66	/*	60	/*
67	* round down to nearest power of two	61	* round down to nearest power of two
68	*/	62	*/
69	static inline __attribute__((const))	63	static inline __attribute__((const))
70	unsigned long __rounddown_pow_of_two(unsigned long n)	64	unsigned long __rounddown_pow_of_two(unsigned long n)
71	{	65	{
72	return 1UL << (fls_long(n) - 1);	66	return 1UL << (fls_long(n) - 1);
73	}	67	}
74		68
75	/**	69	/**
76	* ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value	70	* ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
77	* @n - parameter	71	* @n - parameter
78	*	72	*
79	* constant-capable log of base 2 calculation	73	* constant-capable log of base 2 calculation
80	* - this can be used to initialise global variables from constant data, hence	74	* - this can be used to initialise global variables from constant data, hence
81	* the massive ternary operator construction	75	* the massive ternary operator construction
82	*	76	*
83	* selects the appropriately-sized optimised version depending on sizeof(n)	77	* selects the appropriately-sized optimised version depending on sizeof(n)
84	*/	78	*/
85	#define ilog2(n) \	79	#define ilog2(n) \
86	( \	80	( \
87	__builtin_constant_p(n) ? ( \	81	__builtin_constant_p(n) ? ( \
88	(n) < 1 ? ____ilog2_NaN() : \	82	(n) < 2 ? 0 : \
89	(n) & (1ULL << 63) ? 63 : \	83	(n) & (1ULL << 63) ? 63 : \
90	(n) & (1ULL << 62) ? 62 : \	84	(n) & (1ULL << 62) ? 62 : \
91	(n) & (1ULL << 61) ? 61 : \	85	(n) & (1ULL << 61) ? 61 : \
92	(n) & (1ULL << 60) ? 60 : \	86	(n) & (1ULL << 60) ? 60 : \
93	(n) & (1ULL << 59) ? 59 : \	87	(n) & (1ULL << 59) ? 59 : \
94	(n) & (1ULL << 58) ? 58 : \	88	(n) & (1ULL << 58) ? 58 : \
95	(n) & (1ULL << 57) ? 57 : \	89	(n) & (1ULL << 57) ? 57 : \
96	(n) & (1ULL << 56) ? 56 : \	90	(n) & (1ULL << 56) ? 56 : \
97	(n) & (1ULL << 55) ? 55 : \	91	(n) & (1ULL << 55) ? 55 : \
98	(n) & (1ULL << 54) ? 54 : \	92	(n) & (1ULL << 54) ? 54 : \
99	(n) & (1ULL << 53) ? 53 : \	93	(n) & (1ULL << 53) ? 53 : \
100	(n) & (1ULL << 52) ? 52 : \	94	(n) & (1ULL << 52) ? 52 : \
101	(n) & (1ULL << 51) ? 51 : \	95	(n) & (1ULL << 51) ? 51 : \
102	(n) & (1ULL << 50) ? 50 : \	96	(n) & (1ULL << 50) ? 50 : \
103	(n) & (1ULL << 49) ? 49 : \	97	(n) & (1ULL << 49) ? 49 : \
104	(n) & (1ULL << 48) ? 48 : \	98	(n) & (1ULL << 48) ? 48 : \
105	(n) & (1ULL << 47) ? 47 : \	99	(n) & (1ULL << 47) ? 47 : \
106	(n) & (1ULL << 46) ? 46 : \	100	(n) & (1ULL << 46) ? 46 : \
107	(n) & (1ULL << 45) ? 45 : \	101	(n) & (1ULL << 45) ? 45 : \
108	(n) & (1ULL << 44) ? 44 : \	102	(n) & (1ULL << 44) ? 44 : \
109	(n) & (1ULL << 43) ? 43 : \	103	(n) & (1ULL << 43) ? 43 : \
110	(n) & (1ULL << 42) ? 42 : \	104	(n) & (1ULL << 42) ? 42 : \
111	(n) & (1ULL << 41) ? 41 : \	105	(n) & (1ULL << 41) ? 41 : \
112	(n) & (1ULL << 40) ? 40 : \	106	(n) & (1ULL << 40) ? 40 : \
113	(n) & (1ULL << 39) ? 39 : \	107	(n) & (1ULL << 39) ? 39 : \
114	(n) & (1ULL << 38) ? 38 : \	108	(n) & (1ULL << 38) ? 38 : \
115	(n) & (1ULL << 37) ? 37 : \	109	(n) & (1ULL << 37) ? 37 : \
116	(n) & (1ULL << 36) ? 36 : \	110	(n) & (1ULL << 36) ? 36 : \
117	(n) & (1ULL << 35) ? 35 : \	111	(n) & (1ULL << 35) ? 35 : \
118	(n) & (1ULL << 34) ? 34 : \	112	(n) & (1ULL << 34) ? 34 : \
119	(n) & (1ULL << 33) ? 33 : \	113	(n) & (1ULL << 33) ? 33 : \
120	(n) & (1ULL << 32) ? 32 : \	114	(n) & (1ULL << 32) ? 32 : \
121	(n) & (1ULL << 31) ? 31 : \	115	(n) & (1ULL << 31) ? 31 : \
122	(n) & (1ULL << 30) ? 30 : \	116	(n) & (1ULL << 30) ? 30 : \
123	(n) & (1ULL << 29) ? 29 : \	117	(n) & (1ULL << 29) ? 29 : \
124	(n) & (1ULL << 28) ? 28 : \	118	(n) & (1ULL << 28) ? 28 : \
125	(n) & (1ULL << 27) ? 27 : \	119	(n) & (1ULL << 27) ? 27 : \
126	(n) & (1ULL << 26) ? 26 : \	120	(n) & (1ULL << 26) ? 26 : \
127	(n) & (1ULL << 25) ? 25 : \	121	(n) & (1ULL << 25) ? 25 : \
128	(n) & (1ULL << 24) ? 24 : \	122	(n) & (1ULL << 24) ? 24 : \
129	(n) & (1ULL << 23) ? 23 : \	123	(n) & (1ULL << 23) ? 23 : \
130	(n) & (1ULL << 22) ? 22 : \	124	(n) & (1ULL << 22) ? 22 : \
131	(n) & (1ULL << 21) ? 21 : \	125	(n) & (1ULL << 21) ? 21 : \
132	(n) & (1ULL << 20) ? 20 : \	126	(n) & (1ULL << 20) ? 20 : \
133	(n) & (1ULL << 19) ? 19 : \	127	(n) & (1ULL << 19) ? 19 : \
134	(n) & (1ULL << 18) ? 18 : \	128	(n) & (1ULL << 18) ? 18 : \
135	(n) & (1ULL << 17) ? 17 : \	129	(n) & (1ULL << 17) ? 17 : \
136	(n) & (1ULL << 16) ? 16 : \	130	(n) & (1ULL << 16) ? 16 : \
137	(n) & (1ULL << 15) ? 15 : \	131	(n) & (1ULL << 15) ? 15 : \
138	(n) & (1ULL << 14) ? 14 : \	132	(n) & (1ULL << 14) ? 14 : \
139	(n) & (1ULL << 13) ? 13 : \	133	(n) & (1ULL << 13) ? 13 : \
140	(n) & (1ULL << 12) ? 12 : \	134	(n) & (1ULL << 12) ? 12 : \
141	(n) & (1ULL << 11) ? 11 : \	135	(n) & (1ULL << 11) ? 11 : \
142	(n) & (1ULL << 10) ? 10 : \	136	(n) & (1ULL << 10) ? 10 : \
143	(n) & (1ULL << 9) ? 9 : \	137	(n) & (1ULL << 9) ? 9 : \
144	(n) & (1ULL << 8) ? 8 : \	138	(n) & (1ULL << 8) ? 8 : \
145	(n) & (1ULL << 7) ? 7 : \	139	(n) & (1ULL << 7) ? 7 : \
146	(n) & (1ULL << 6) ? 6 : \	140	(n) & (1ULL << 6) ? 6 : \
147	(n) & (1ULL << 5) ? 5 : \	141	(n) & (1ULL << 5) ? 5 : \
148	(n) & (1ULL << 4) ? 4 : \	142	(n) & (1ULL << 4) ? 4 : \
149	(n) & (1ULL << 3) ? 3 : \	143	(n) & (1ULL << 3) ? 3 : \
150	(n) & (1ULL << 2) ? 2 : \	144	(n) & (1ULL << 2) ? 2 : \
151	(n) & (1ULL << 1) ? 1 : \	-
152	(n) & (1ULL << 0) ? 0 : \	-
153	____ilog2_NaN() \	-
154	) : \	145	1 ) : \
155	(sizeof(n) <= 4) ? \	146	(sizeof(n) <= 4) ? \
156	__ilog2_u32(n) : \	147	__ilog2_u32(n) : \
157	__ilog2_u64(n) \	148	__ilog2_u64(n) \
158	)	149	)
159		150
160	/**	151	/**
161	* roundup_pow_of_two - round the given value up to nearest power of two	152	* roundup_pow_of_two - round the given value up to nearest power of two
162	* @n - parameter	153	* @n - parameter
163	*	154	*
164	* round the given value up to the nearest power of two	155	* round the given value up to the nearest power of two
165	* - the result is undefined when n == 0	156	* - the result is undefined when n == 0
166	* - this can be used to initialise global variables from constant data	157	* - this can be used to initialise global variables from constant data
167	*/	158	*/
168	#define roundup_pow_of_two(n) \	159	#define roundup_pow_of_two(n) \
169	( \	160	( \
170	__builtin_constant_p(n) ? ( \	161	__builtin_constant_p(n) ? ( \
171	(n == 1) ? 1 : \	162	(n == 1) ? 1 : \
172	(1UL << (ilog2((n) - 1) + 1)) \	163	(1UL << (ilog2((n) - 1) + 1)) \
173	) : \	164	) : \
174	__roundup_pow_of_two(n) \	165	__roundup_pow_of_two(n) \
175	)	166	)
176		167
177	/**	168	/**
178	* rounddown_pow_of_two - round the given value down to nearest power of two	169	* rounddown_pow_of_two - round the given value down to nearest power of two
179	* @n - parameter	170	* @n - parameter
180	*	171	*
181	* round the given value down to the nearest power of two	172	* round the given value down to the nearest power of two
182	* - the result is undefined when n == 0	173	* - the result is undefined when n == 0
183	* - this can be used to initialise global variables from constant data	174	* - this can be used to initialise global variables from constant data
184	*/	175	*/
185	#define rounddown_pow_of_two(n) \	176	#define rounddown_pow_of_two(n) \
186	( \	177	( \
187	__builtin_constant_p(n) ? ( \	178	__builtin_constant_p(n) ? ( \
188	(1UL << ilog2(n))) : \	179	(1UL << ilog2(n))) : \
189	__rounddown_pow_of_two(n) \	180	__rounddown_pow_of_two(n) \
190	)	181	)
191		182
192	/**	183	/**
193	* order_base_2 - calculate the (rounded up) base 2 order of the argument	184	* order_base_2 - calculate the (rounded up) base 2 order of the argument
194	* @n: parameter	185	* @n: parameter
195	*	186	*
196	* The first few values calculated by this routine:	187	* The first few values calculated by this routine:
197	* ob2(0) = 0	188	* ob2(0) = 0
198	* ob2(1) = 0	189	* ob2(1) = 0
199	* ob2(2) = 1	190	* ob2(2) = 1
200	* ob2(3) = 2	191	* ob2(3) = 2
201	* ob2(4) = 2	192	* ob2(4) = 2
202	* ob2(5) = 3	193	* ob2(5) = 3
203	* ... and so on.	194	* ... and so on.
204	*/	195	*/
-		196
205		197	static inline __attribute_const__
-		198	int __order_base_2(unsigned long n)
-		199	{
-		200	return n > 1 ? ilog2(n - 1) + 1 : 0;
-		201	}
-		202
-		203	#define order_base_2(n) \
-		204	( \
-		205	__builtin_constant_p(n) ? ( \
-		206	((n) == 0 \|\| (n) == 1) ? 0 : \
-		207	ilog2((n) - 1) + 1) : \
206	#define order_base_2(n) ilog2(roundup_pow_of_two(n))	208	__order_base_2(n) \
207		209	)
208	#endif /* _LINUX_LOG2_H */	210	#endif /* _LINUX_LOG2_H */

Subversion Repositories Kolibri OS

(root)/drivers/include/linux/log2.h @ 6936 – Rev 3031 → 6934