[mirror_ubuntu-jammy-kernel.git] / include / linux / bitops.h

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_BITOPS_H
#define _LINUX_BITOPS_H
#include <asm/types.h>
#include <linux/bits.h>

/* Set bits in the first 'n' bytes when loaded from memory */
#ifdef __LITTLE_ENDIAN
#  define aligned_byte_mask(n) ((1UL << 8*(n))-1)
#else
#  define aligned_byte_mask(n) (~0xffUL << (BITS_PER_LONG - 8 - 8*(n)))
#endif

#define BITS_PER_TYPE(type)	(sizeof(type) * BITS_PER_BYTE)
#define BITS_TO_LONGS(nr)	DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
#define BITS_TO_U64(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
#define BITS_TO_U32(nr)		DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
#define BITS_TO_BYTES(nr)	DIV_ROUND_UP(nr, BITS_PER_TYPE(char))

extern unsigned int __sw_hweight8(unsigned int w);
extern unsigned int __sw_hweight16(unsigned int w);
extern unsigned int __sw_hweight32(unsigned int w);
extern unsigned long __sw_hweight64(__u64 w);

/*
 * Include this here because some architectures need generic_ffs/fls in
 * scope
 */
#include <asm/bitops.h>

#define for_each_set_bit(bit, addr, size) \
	for ((bit) = find_first_bit((addr), (size));		\
	     (bit) < (size);					\
	     (bit) = find_next_bit((addr), (size), (bit) + 1))

/* same as for_each_set_bit() but use bit as value to start with */
#define for_each_set_bit_from(bit, addr, size) \
	for ((bit) = find_next_bit((addr), (size), (bit));	\
	     (bit) < (size);					\
	     (bit) = find_next_bit((addr), (size), (bit) + 1))

#define for_each_clear_bit(bit, addr, size) \
	for ((bit) = find_first_zero_bit((addr), (size));	\
	     (bit) < (size);					\
	     (bit) = find_next_zero_bit((addr), (size), (bit) + 1))

/* same as for_each_clear_bit() but use bit as value to start with */
#define for_each_clear_bit_from(bit, addr, size) \
	for ((bit) = find_next_zero_bit((addr), (size), (bit));	\
	     (bit) < (size);					\
	     (bit) = find_next_zero_bit((addr), (size), (bit) + 1))

/**
 * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
 * @start: bit offset to start search and to store the current iteration offset
 * @clump: location to store copy of current 8-bit clump
 * @bits: bitmap address to base the search on
 * @size: bitmap size in number of bits
 */
#define for_each_set_clump8(start, clump, bits, size) \
	for ((start) = find_first_clump8(&(clump), (bits), (size)); \
	     (start) < (size); \
	     (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))

static inline int get_bitmask_order(unsigned int count)
{
	int order;

	order = fls(count);
	return order;	/* We could be slightly more clever with -1 here... */
}

static __always_inline unsigned long hweight_long(unsigned long w)
{
	return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
}

/**
 * rol64 - rotate a 64-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u64 rol64(__u64 word, unsigned int shift)
{
	return (word << (shift & 63)) | (word >> ((-shift) & 63));
}

/**
 * ror64 - rotate a 64-bit value right
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u64 ror64(__u64 word, unsigned int shift)
{
	return (word >> (shift & 63)) | (word << ((-shift) & 63));
}

/**
 * rol32 - rotate a 32-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u32 rol32(__u32 word, unsigned int shift)
{
	return (word << (shift & 31)) | (word >> ((-shift) & 31));
}

/**
 * ror32 - rotate a 32-bit value right
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u32 ror32(__u32 word, unsigned int shift)
{
	return (word >> (shift & 31)) | (word << ((-shift) & 31));
}

/**
 * rol16 - rotate a 16-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u16 rol16(__u16 word, unsigned int shift)
{
	return (word << (shift & 15)) | (word >> ((-shift) & 15));
}

/**
 * ror16 - rotate a 16-bit value right
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u16 ror16(__u16 word, unsigned int shift)
{
	return (word >> (shift & 15)) | (word << ((-shift) & 15));
}

/**
 * rol8 - rotate an 8-bit value left
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u8 rol8(__u8 word, unsigned int shift)
{
	return (word << (shift & 7)) | (word >> ((-shift) & 7));
}

/**
 * ror8 - rotate an 8-bit value right
 * @word: value to rotate
 * @shift: bits to roll
 */
static inline __u8 ror8(__u8 word, unsigned int shift)
{
	return (word >> (shift & 7)) | (word << ((-shift) & 7));
}

/**
 * sign_extend32 - sign extend a 32-bit value using specified bit as sign-bit
 * @value: value to sign extend
 * @index: 0 based bit index (0<=index<32) to sign bit
 *
 * This is safe to use for 16- and 8-bit types as well.
 */
static __always_inline __s32 sign_extend32(__u32 value, int index)
{
	__u8 shift = 31 - index;
	return (__s32)(value << shift) >> shift;
}

/**
 * sign_extend64 - sign extend a 64-bit value using specified bit as sign-bit
 * @value: value to sign extend
 * @index: 0 based bit index (0<=index<64) to sign bit
 */
static __always_inline __s64 sign_extend64(__u64 value, int index)
{
	__u8 shift = 63 - index;
	return (__s64)(value << shift) >> shift;
}

static inline unsigned fls_long(unsigned long l)
{
	if (sizeof(l) == 4)
		return fls(l);
	return fls64(l);
}

static inline int get_count_order(unsigned int count)
{
	int order;

	order = fls(count) - 1;
	if (count & (count - 1))
		order++;
	return order;
}

/**
 * get_count_order_long - get order after rounding @l up to power of 2
 * @l: parameter
 *
 * it is same as get_count_order() but with long type parameter
 */
static inline int get_count_order_long(unsigned long l)
{
	if (l == 0UL)
		return -1;
	else if (l & (l - 1UL))
		return (int)fls_long(l);
	else
		return (int)fls_long(l) - 1;
}

/**
 * __ffs64 - find first set bit in a 64 bit word
 * @word: The 64 bit word
 *
 * On 64 bit arches this is a synomyn for __ffs
 * The result is not defined if no bits are set, so check that @word
 * is non-zero before calling this.
 */
static inline unsigned long __ffs64(u64 word)
{
#if BITS_PER_LONG == 32
	if (((u32)word) == 0UL)
		return __ffs((u32)(word >> 32)) + 32;
#elif BITS_PER_LONG != 64
#error BITS_PER_LONG not 32 or 64
#endif
	return __ffs((unsigned long)word);
}

/**
 * assign_bit - Assign value to a bit in memory
 * @nr: the bit to set
 * @addr: the address to start counting from
 * @value: the value to assign
 */
static __always_inline void assign_bit(long nr, volatile unsigned long *addr,
				       bool value)
{
	if (value)
		set_bit(nr, addr);
	else
		clear_bit(nr, addr);
}

static __always_inline void __assign_bit(long nr, volatile unsigned long *addr,
					 bool value)
{
	if (value)
		__set_bit(nr, addr);
	else
		__clear_bit(nr, addr);
}

#ifdef __KERNEL__

#ifndef set_mask_bits
#define set_mask_bits(ptr, mask, bits)	\
({								\
	const typeof(*(ptr)) mask__ = (mask), bits__ = (bits);	\
	typeof(*(ptr)) old__, new__;				\
								\
	do {							\
		old__ = READ_ONCE(*(ptr));			\
		new__ = (old__ & ~mask__) | bits__;		\
	} while (cmpxchg(ptr, old__, new__) != old__);		\
								\
	old__;							\
})
#endif

#ifndef bit_clear_unless
#define bit_clear_unless(ptr, clear, test)	\
({								\
	const typeof(*(ptr)) clear__ = (clear), test__ = (test);\
	typeof(*(ptr)) old__, new__;				\
								\
	do {							\
		old__ = READ_ONCE(*(ptr));			\
		new__ = old__ & ~clear__;			\
	} while (!(old__ & test__) &&				\
		 cmpxchg(ptr, old__, new__) != old__);		\
								\
	!(old__ & test__);					\
})
#endif

#ifndef find_last_bit
/**
 * find_last_bit - find the last set bit in a memory region
 * @addr: The address to start the search at
 * @size: The number of bits to search
 *
 * Returns the bit number of the last set bit, or size.
 */
extern unsigned long find_last_bit(const unsigned long *addr,
				   unsigned long size);
#endif

#endif /* __KERNEL__ */
#endif
Commit	Line	Data
b2441318	1	/* SPDX-License-Identifier: GPL-2.0 */
1da177e4 LT	2	#ifndef _LINUX_BITOPS_H
	3	#define _LINUX_BITOPS_H
	4	#include <asm/types.h>
8bd9cb51	5	#include <linux/bits.h>
1da177e4	6
f5a1a536 AS	7	/* Set bits in the first 'n' bytes when loaded from memory */
	8	#ifdef __LITTLE_ENDIAN
	9	# define aligned_byte_mask(n) ((1UL << 8*(n))-1)
	10	#else
	11	# define aligned_byte_mask(n) (~0xffUL << (BITS_PER_LONG - 8 - 8*(n)))
	12	#endif
	13
0bddc1bd	14	#define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE)
9144d75e	15	#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
0bddc1bd YN	16	#define BITS_TO_U64(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
0bddc1bd YN	17	#define BITS_TO_U32(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
dd3e7cba	18	#define BITS_TO_BYTES(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(char))
10ef6b0d	19
4677d4a5 BP	20	extern unsigned int __sw_hweight8(unsigned int w);
	21	extern unsigned int __sw_hweight16(unsigned int w);
	22	extern unsigned int __sw_hweight32(unsigned int w);
	23	extern unsigned long __sw_hweight64(__u64 w);
	24
1da177e4 LT	25	/*
	26	* Include this here because some architectures need generic_ffs/fls in
	27	* scope
	28	*/
	29	#include <asm/bitops.h>
	30
984b3f57	31	#define for_each_set_bit(bit, addr, size) \
1e2ad28f RR	32	for ((bit) = find_first_bit((addr), (size)); \
	33	(bit) < (size); \
	34	(bit) = find_next_bit((addr), (size), (bit) + 1))
	35
	36	/* same as for_each_set_bit() but use bit as value to start with */
307b1cd7	37	#define for_each_set_bit_from(bit, addr, size) \
1e2ad28f RR	38	for ((bit) = find_next_bit((addr), (size), (bit)); \
1e2ad28f RR	39	(bit) < (size); \
3e037454 SN	40	(bit) = find_next_bit((addr), (size), (bit) + 1))
3e037454 SN	41
03f4a822 AM	42	#define for_each_clear_bit(bit, addr, size) \
	43	for ((bit) = find_first_zero_bit((addr), (size)); \
	44	(bit) < (size); \
	45	(bit) = find_next_zero_bit((addr), (size), (bit) + 1))
	46
	47	/* same as for_each_clear_bit() but use bit as value to start with */
	48	#define for_each_clear_bit_from(bit, addr, size) \
	49	for ((bit) = find_next_zero_bit((addr), (size), (bit)); \
	50	(bit) < (size); \
	51	(bit) = find_next_zero_bit((addr), (size), (bit) + 1))
	52
169c474f WBG	53	/**
	54	* for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
	55	* @start: bit offset to start search and to store the current iteration offset
	56	* @clump: location to store copy of current 8-bit clump
	57	* @bits: bitmap address to base the search on
	58	* @size: bitmap size in number of bits
	59	*/
	60	#define for_each_set_clump8(start, clump, bits, size) \
	61	for ((start) = find_first_clump8(&(clump), (bits), (size)); \
	62	(start) < (size); \
	63	(start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))
	64
1a1d48a4	65	static inline int get_bitmask_order(unsigned int count)
1da177e4 LT	66	{
1da177e4 LT	67	int order;
9f41699e	68
1da177e4 LT	69	order = fls(count);
	70	return order; /* We could be slightly more clever with -1 here... */
	71	}
	72
1a1d48a4	73	static __always_inline unsigned long hweight_long(unsigned long w)
1da177e4	74	{
e9bebd6f	75	return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
1da177e4 LT	76	}
1da177e4 LT	77
f2ea0f5f AD	78	/**
	79	* rol64 - rotate a 64-bit value left
	80	* @word: value to rotate
	81	* @shift: bits to roll
	82	*/
	83	static inline __u64 rol64(__u64 word, unsigned int shift)
	84	{
ef4d6f6b	85	return (word << (shift & 63)) \| (word >> ((-shift) & 63));
f2ea0f5f AD	86	}
	87
	88	/**
	89	* ror64 - rotate a 64-bit value right
	90	* @word: value to rotate
	91	* @shift: bits to roll
	92	*/
	93	static inline __u64 ror64(__u64 word, unsigned int shift)
	94	{
ef4d6f6b	95	return (word >> (shift & 63)) \| (word << ((-shift) & 63));
f2ea0f5f AD	96	}
f2ea0f5f AD	97
45f8bde0	98	/**
1da177e4	99	* rol32 - rotate a 32-bit value left
1da177e4 LT	100	* @word: value to rotate
	101	* @shift: bits to roll
	102	*/
	103	static inline __u32 rol32(__u32 word, unsigned int shift)
	104	{
ef4d6f6b	105	return (word << (shift & 31)) \| (word >> ((-shift) & 31));
1da177e4 LT	106	}
1da177e4 LT	107
45f8bde0	108	/**
1da177e4	109	* ror32 - rotate a 32-bit value right
1da177e4 LT	110	* @word: value to rotate
	111	* @shift: bits to roll
	112	*/
	113	static inline __u32 ror32(__u32 word, unsigned int shift)
	114	{
ef4d6f6b	115	return (word >> (shift & 31)) \| (word << ((-shift) & 31));
1da177e4 LT	116	}
1da177e4 LT	117
3afe3925 HH	118	/**
	119	* rol16 - rotate a 16-bit value left
	120	* @word: value to rotate
	121	* @shift: bits to roll
	122	*/
	123	static inline __u16 rol16(__u16 word, unsigned int shift)
	124	{
ef4d6f6b	125	return (word << (shift & 15)) \| (word >> ((-shift) & 15));
3afe3925 HH	126	}
	127
	128	/**
	129	* ror16 - rotate a 16-bit value right
	130	* @word: value to rotate
	131	* @shift: bits to roll
	132	*/
	133	static inline __u16 ror16(__u16 word, unsigned int shift)
	134	{
ef4d6f6b	135	return (word >> (shift & 15)) \| (word << ((-shift) & 15));
3afe3925 HH	136	}
	137
	138	/**
	139	* rol8 - rotate an 8-bit value left
	140	* @word: value to rotate
	141	* @shift: bits to roll
	142	*/
	143	static inline __u8 rol8(__u8 word, unsigned int shift)
	144	{
ef4d6f6b	145	return (word << (shift & 7)) \| (word >> ((-shift) & 7));
3afe3925 HH	146	}
	147
	148	/**
	149	* ror8 - rotate an 8-bit value right
	150	* @word: value to rotate
	151	* @shift: bits to roll
	152	*/
	153	static inline __u8 ror8(__u8 word, unsigned int shift)
	154	{
ef4d6f6b	155	return (word >> (shift & 7)) \| (word << ((-shift) & 7));
3afe3925	156	}
7919a57b AH	157
	158	/**
	159	* sign_extend32 - sign extend a 32-bit value using specified bit as sign-bit
	160	* @value: value to sign extend
	161	* @index: 0 based bit index (0<=index<32) to sign bit
e2eb53aa MK	162	*
e2eb53aa MK	163	* This is safe to use for 16- and 8-bit types as well.
7919a57b	164	*/
f80ac98a	165	static __always_inline __s32 sign_extend32(__u32 value, int index)
7919a57b AH	166	{
	167	__u8 shift = 31 - index;
	168	return (__s32)(value << shift) >> shift;
	169	}
3afe3925	170
48e203e2 MK	171	/**
	172	* sign_extend64 - sign extend a 64-bit value using specified bit as sign-bit
	173	* @value: value to sign extend
	174	* @index: 0 based bit index (0<=index<64) to sign bit
	175	*/
f80ac98a	176	static __always_inline __s64 sign_extend64(__u64 value, int index)
48e203e2 MK	177	{
	178	__u8 shift = 63 - index;
	179	return (__s64)(value << shift) >> shift;
	180	}
	181
962749af AM	182	static inline unsigned fls_long(unsigned long l)
	183	{
	184	if (sizeof(l) == 4)
	185	return fls(l);
	186	return fls64(l);
	187	}
	188
252e5c6e	189	static inline int get_count_order(unsigned int count)
	190	{
	191	int order;
	192
	193	order = fls(count) - 1;
	194	if (count & (count - 1))
	195	order++;
	196	return order;
	197	}
	198
	199	/**
	200	* get_count_order_long - get order after rounding @l up to power of 2
	201	* @l: parameter
	202	*
	203	* it is same as get_count_order() but with long type parameter
	204	*/
	205	static inline int get_count_order_long(unsigned long l)
	206	{
	207	if (l == 0UL)
	208	return -1;
	209	else if (l & (l - 1UL))
	210	return (int)fls_long(l);
	211	else
	212	return (int)fls_long(l) - 1;
	213	}
	214
952043ac SW	215	/**
	216	* __ffs64 - find first set bit in a 64 bit word
	217	* @word: The 64 bit word
	218	*
	219	* On 64 bit arches this is a synomyn for __ffs
	220	* The result is not defined if no bits are set, so check that @word
	221	* is non-zero before calling this.
	222	*/
	223	static inline unsigned long __ffs64(u64 word)
	224	{
	225	#if BITS_PER_LONG == 32
	226	if (((u32)word) == 0UL)
	227	return __ffs((u32)(word >> 32)) + 32;
	228	#elif BITS_PER_LONG != 64
	229	#error BITS_PER_LONG not 32 or 64
	230	#endif
	231	return __ffs((unsigned long)word);
	232	}
	233
5307e2ad LW	234	/**
	235	* assign_bit - Assign value to a bit in memory
	236	* @nr: the bit to set
	237	* @addr: the address to start counting from
	238	* @value: the value to assign
	239	*/
	240	static __always_inline void assign_bit(long nr, volatile unsigned long *addr,
	241	bool value)
	242	{
	243	if (value)
	244	set_bit(nr, addr);
	245	else
	246	clear_bit(nr, addr);
	247	}
	248
	249	static __always_inline void __assign_bit(long nr, volatile unsigned long *addr,
	250	bool value)
	251	{
	252	if (value)
	253	__set_bit(nr, addr);
	254	else
	255	__clear_bit(nr, addr);
	256	}
	257
64970b68	258	#ifdef __KERNEL__
77b9bd9c	259
00a1a053	260	#ifndef set_mask_bits
18127429	261	#define set_mask_bits(ptr, mask, bits) \
00a1a053	262	({ \
18127429 MS	263	const typeof(*(ptr)) mask__ = (mask), bits__ = (bits); \
18127429 MS	264	typeof(*(ptr)) old__, new__; \
00a1a053 TT	265	\
00a1a053 TT	266	do { \
18127429 MS	267	old__ = READ_ONCE(*(ptr)); \
	268	new__ = (old__ & ~mask__) \| bits__; \
	269	} while (cmpxchg(ptr, old__, new__) != old__); \
00a1a053	270	\
1db604f6	271	old__; \
00a1a053 TT	272	})
	273	#endif
	274
85ad1d13	275	#ifndef bit_clear_unless
edfa8728	276	#define bit_clear_unless(ptr, clear, test) \
85ad1d13	277	({ \
edfa8728 MS	278	const typeof(*(ptr)) clear__ = (clear), test__ = (test);\
edfa8728 MS	279	typeof(*(ptr)) old__, new__; \
85ad1d13 GJ	280	\
85ad1d13 GJ	281	do { \
edfa8728 MS	282	old__ = READ_ONCE(*(ptr)); \
	283	new__ = old__ & ~clear__; \
	284	} while (!(old__ & test__) && \
	285	cmpxchg(ptr, old__, new__) != old__); \
85ad1d13	286	\
edfa8728	287	!(old__ & test__); \
85ad1d13 GJ	288	})
	289	#endif
	290
19de85ef	291	#ifndef find_last_bit
ab53d472 RR	292	/**
	293	* find_last_bit - find the last set bit in a memory region
	294	* @addr: The address to start the search at
2c57a0e2	295	* @size: The number of bits to search
ab53d472	296	*
2c57a0e2	297	* Returns the bit number of the last set bit, or size.
ab53d472 RR	298	*/
	299	extern unsigned long find_last_bit(const unsigned long *addr,
	300	unsigned long size);
19de85ef	301	#endif
ab53d472	302
64970b68	303	#endif /* __KERNEL__ */
1da177e4	304	#endif