[mirror_qemu.git] / bitops.h

/*
 * Bitops Module
 *
 * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com>
 *
 * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h
 *
 * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
 * See the COPYING.LIB file in the top-level directory.
 */

#ifndef BITOPS_H
#define BITOPS_H

#include "qemu-common.h"

#define BITS_PER_BYTE           CHAR_BIT
#define BITS_PER_LONG           (sizeof (unsigned long) * BITS_PER_BYTE)

#define BIT(nr)			(1UL << (nr))
#define BIT_MASK(nr)		(1UL << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr)		((nr) / BITS_PER_LONG)
#define BITS_TO_LONGS(nr)	DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))

/**
 * bitops_ffs - find first bit in word.
 * @word: The word to search
 *
 * Undefined if no bit exists, so code should check against 0 first.
 */
static unsigned long bitops_ffsl(unsigned long word)
{
	int num = 0;

#if LONG_MAX > 0x7FFFFFFF
	if ((word & 0xffffffff) == 0) {
		num += 32;
		word >>= 32;
	}
#endif
	if ((word & 0xffff) == 0) {
		num += 16;
		word >>= 16;
	}
	if ((word & 0xff) == 0) {
		num += 8;
		word >>= 8;
	}
	if ((word & 0xf) == 0) {
		num += 4;
		word >>= 4;
	}
	if ((word & 0x3) == 0) {
		num += 2;
		word >>= 2;
	}
	if ((word & 0x1) == 0) {
		num += 1;
        }
	return num;
}

/**
 * bitops_fls - find last (most-significant) set bit in a long word
 * @word: the word to search
 *
 * Undefined if no set bit exists, so code should check against 0 first.
 */
static inline unsigned long bitops_flsl(unsigned long word)
{
	int num = BITS_PER_LONG - 1;

#if LONG_MAX > 0x7FFFFFFF
	if (!(word & (~0ul << 32))) {
		num -= 32;
		word <<= 32;
	}
#endif
	if (!(word & (~0ul << (BITS_PER_LONG-16)))) {
		num -= 16;
		word <<= 16;
	}
	if (!(word & (~0ul << (BITS_PER_LONG-8)))) {
		num -= 8;
		word <<= 8;
	}
	if (!(word & (~0ul << (BITS_PER_LONG-4)))) {
		num -= 4;
		word <<= 4;
	}
	if (!(word & (~0ul << (BITS_PER_LONG-2)))) {
		num -= 2;

		word <<= 2;
	}
	if (!(word & (~0ul << (BITS_PER_LONG-1))))
		num -= 1;
	return num;
}

/**
 * ffz - find first zero in word.
 * @word: The word to search
 *
 * Undefined if no zero exists, so code should check against ~0UL first.
 */
static inline unsigned long ffz(unsigned long word)
{
    return bitops_ffsl(~word);
}

/**
 * set_bit - Set a bit in memory
 * @nr: the bit to set
 * @addr: the address to start counting from
 */
static inline void set_bit(int nr, unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
        unsigned long *p = addr + BIT_WORD(nr);

	*p  |= mask;
}

/**
 * clear_bit - Clears a bit in memory
 * @nr: Bit to clear
 * @addr: Address to start counting from
 */
static inline void clear_bit(int nr, unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
        unsigned long *p = addr + BIT_WORD(nr);

	*p &= ~mask;
}

/**
 * change_bit - Toggle a bit in memory
 * @nr: Bit to change
 * @addr: Address to start counting from
 */
static inline void change_bit(int nr, unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
        unsigned long *p = addr + BIT_WORD(nr);

	*p ^= mask;
}

/**
 * test_and_set_bit - Set a bit and return its old value
 * @nr: Bit to set
 * @addr: Address to count from
 */
static inline int test_and_set_bit(int nr, unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
        unsigned long *p = addr + BIT_WORD(nr);
	unsigned long old = *p;

	*p = old | mask;
	return (old & mask) != 0;
}

/**
 * test_and_clear_bit - Clear a bit and return its old value
 * @nr: Bit to clear
 * @addr: Address to count from
 */
static inline int test_and_clear_bit(int nr, unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
        unsigned long *p = addr + BIT_WORD(nr);
	unsigned long old = *p;

	*p = old & ~mask;
	return (old & mask) != 0;
}

/**
 * test_and_change_bit - Change a bit and return its old value
 * @nr: Bit to change
 * @addr: Address to count from
 */
static inline int test_and_change_bit(int nr, unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
        unsigned long *p = addr + BIT_WORD(nr);
	unsigned long old = *p;

	*p = old ^ mask;
	return (old & mask) != 0;
}

/**
 * test_bit - Determine whether a bit is set
 * @nr: bit number to test
 * @addr: Address to start counting from
 */
static inline int test_bit(int nr, const unsigned long *addr)
{
	return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
}

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

/**
 * find_next_bit - find the next set bit in a memory region
 * @addr: The address to base the search on
 * @offset: The bitnumber to start searching at
 * @size: The bitmap size in bits
 */
unsigned long find_next_bit(const unsigned long *addr,
				   unsigned long size, unsigned long offset);

/**
 * find_next_zero_bit - find the next cleared bit in a memory region
 * @addr: The address to base the search on
 * @offset: The bitnumber to start searching at
 * @size: The bitmap size in bits
 */

unsigned long find_next_zero_bit(const unsigned long *addr,
                                 unsigned long size,
                                 unsigned long offset);

/**
 * find_first_bit - find the first set bit in a memory region
 * @addr: The address to start the search at
 * @size: The maximum size to search
 *
 * Returns the bit number of the first set bit.
 */
static inline unsigned long find_first_bit(const unsigned long *addr,
                                           unsigned long size)
{
    return find_next_bit(addr, size, 0);
}

/**
 * find_first_zero_bit - find the first cleared bit in a memory region
 * @addr: The address to start the search at
 * @size: The maximum size to search
 *
 * Returns the bit number of the first cleared bit.
 */
static inline unsigned long find_first_zero_bit(const unsigned long *addr,
                                                unsigned long size)
{
    return find_next_zero_bit(addr, size, 0);
}

static inline unsigned long hweight_long(unsigned long w)
{
    unsigned long count;

    for (count = 0; w; w >>= 1) {
        count += w & 1;
    }
    return count;
}

/**
 * extract32:
 * @value: the value to extract the bit field from
 * @start: the lowest bit in the bit field (numbered from 0)
 * @length: the length of the bit field
 *
 * Extract from the 32 bit input @value the bit field specified by the
 * @start and @length parameters, and return it. The bit field must
 * lie entirely within the 32 bit word. It is valid to request that
 * all 32 bits are returned (ie @length 32 and @start 0).
 *
 * Returns: the value of the bit field extracted from the input value.
 */
static inline uint32_t extract32(uint32_t value, int start, int length)
{
    assert(start >= 0 && length > 0 && length <= 32 - start);
    return (value >> start) & (~0U >> (32 - length));
}

/**
 * extract64:
 * @value: the value to extract the bit field from
 * @start: the lowest bit in the bit field (numbered from 0)
 * @length: the length of the bit field
 *
 * Extract from the 64 bit input @value the bit field specified by the
 * @start and @length parameters, and return it. The bit field must
 * lie entirely within the 64 bit word. It is valid to request that
 * all 64 bits are returned (ie @length 64 and @start 0).
 *
 * Returns: the value of the bit field extracted from the input value.
 */
static inline uint64_t extract64(uint64_t value, int start, int length)
{
    assert(start >= 0 && length > 0 && length <= 64 - start);
    return (value >> start) & (~0ULL >> (64 - length));
}

/**
 * deposit32:
 * @value: initial value to insert bit field into
 * @start: the lowest bit in the bit field (numbered from 0)
 * @length: the length of the bit field
 * @fieldval: the value to insert into the bit field
 *
 * Deposit @fieldval into the 32 bit @value at the bit field specified
 * by the @start and @length parameters, and return the modified
 * @value. Bits of @value outside the bit field are not modified.
 * Bits of @fieldval above the least significant @length bits are
 * ignored. The bit field must lie entirely within the 32 bit word.
 * It is valid to request that all 32 bits are modified (ie @length
 * 32 and @start 0).
 *
 * Returns: the modified @value.
 */
static inline uint32_t deposit32(uint32_t value, int start, int length,
                                 uint32_t fieldval)
{
    uint32_t mask;
    assert(start >= 0 && length > 0 && length <= 32 - start);
    mask = (~0U >> (32 - length)) << start;
    return (value & ~mask) | ((fieldval << start) & mask);
}

/**
 * deposit64:
 * @value: initial value to insert bit field into
 * @start: the lowest bit in the bit field (numbered from 0)
 * @length: the length of the bit field
 * @fieldval: the value to insert into the bit field
 *
 * Deposit @fieldval into the 64 bit @value at the bit field specified
 * by the @start and @length parameters, and return the modified
 * @value. Bits of @value outside the bit field are not modified.
 * Bits of @fieldval above the least significant @length bits are
 * ignored. The bit field must lie entirely within the 64 bit word.
 * It is valid to request that all 64 bits are modified (ie @length
 * 64 and @start 0).
 *
 * Returns: the modified @value.
 */
static inline uint64_t deposit64(uint64_t value, int start, int length,
                                 uint64_t fieldval)
{
    uint64_t mask;
    assert(start >= 0 && length > 0 && length <= 64 - start);
    mask = (~0ULL >> (64 - length)) << start;
    return (value & ~mask) | ((fieldval << start) & mask);
}

#endif
Commit	Line	Data
e0e53b2f CC	1	/*
	2	* Bitops Module
	3	*
	4	* Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com>
	5	*
	6	* Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h
	7	*
	8	* This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
	9	* See the COPYING.LIB file in the top-level directory.
	10	*/
	11
	12	#ifndef BITOPS_H
	13	#define BITOPS_H
	14
	15	#include "qemu-common.h"
	16
	17	#define BITS_PER_BYTE CHAR_BIT
	18	#define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE)
	19
	20	#define BIT(nr) (1UL << (nr))
	21	#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
	22	#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
	23	#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
	24
	25	/**
	26	* bitops_ffs - find first bit in word.
	27	* @word: The word to search
	28	*
	29	* Undefined if no bit exists, so code should check against 0 first.
	30	*/
	31	static unsigned long bitops_ffsl(unsigned long word)
	32	{
	33	int num = 0;
	34
	35	#if LONG_MAX > 0x7FFFFFFF
	36	if ((word & 0xffffffff) == 0) {
	37	num += 32;
	38	word >>= 32;
	39	}
	40	#endif
	41	if ((word & 0xffff) == 0) {
	42	num += 16;
	43	word >>= 16;
	44	}
	45	if ((word & 0xff) == 0) {
	46	num += 8;
	47	word >>= 8;
	48	}
	49	if ((word & 0xf) == 0) {
	50	num += 4;
	51	word >>= 4;
	52	}
	53	if ((word & 0x3) == 0) {
	54	num += 2;
	55	word >>= 2;
	56	}
	57	if ((word & 0x1) == 0) {
	58	num += 1;
	59	}
	60	return num;
	61	}
	62
	63	/**
	64	* bitops_fls - find last (most-significant) set bit in a long word
65	* @word: the word to search
66	*
67	* Undefined if no set bit exists, so code should check against 0 first.
68	*/
84803d7a	69	static inline unsigned long bitops_flsl(unsigned long word)
e0e53b2f CC	70	{
	71	int num = BITS_PER_LONG - 1;
	72
	73	#if LONG_MAX > 0x7FFFFFFF
	74	if (!(word & (~0ul << 32))) {
	75	num -= 32;
	76	word <<= 32;
	77	}
	78	#endif
	79	if (!(word & (~0ul << (BITS_PER_LONG-16)))) {
	80	num -= 16;
	81	word <<= 16;
	82	}
	83	if (!(word & (~0ul << (BITS_PER_LONG-8)))) {
	84	num -= 8;
	85	word <<= 8;
	86	}
	87	if (!(word & (~0ul << (BITS_PER_LONG-4)))) {
	88	num -= 4;
	89	word <<= 4;
	90	}
	91	if (!(word & (~0ul << (BITS_PER_LONG-2)))) {
	92	num -= 2;
	93
	94	word <<= 2;
	95	}
	96	if (!(word & (~0ul << (BITS_PER_LONG-1))))
	97	num -= 1;
	98	return num;
	99	}
	100
	101	/**
	102	* ffz - find first zero in word.
	103	* @word: The word to search
	104	*
	105	* Undefined if no zero exists, so code should check against ~0UL first.
	106	*/
	107	static inline unsigned long ffz(unsigned long word)
	108	{
	109	return bitops_ffsl(~word);
	110	}
	111
	112	/**
	113	* set_bit - Set a bit in memory
	114	* @nr: the bit to set
	115	* @addr: the address to start counting from
	116	*/
17a4ed8a	117	static inline void set_bit(int nr, unsigned long *addr)
e0e53b2f CC	118	{
e0e53b2f CC	119	unsigned long mask = BIT_MASK(nr);
17a4ed8a	120	unsigned long *p = addr + BIT_WORD(nr);
e0e53b2f CC	121
	122	*p \|= mask;
	123	}
	124
	125	/**
	126	* clear_bit - Clears a bit in memory
	127	* @nr: Bit to clear
	128	* @addr: Address to start counting from
	129	*/
17a4ed8a	130	static inline void clear_bit(int nr, unsigned long *addr)
e0e53b2f CC	131	{
e0e53b2f CC	132	unsigned long mask = BIT_MASK(nr);
17a4ed8a	133	unsigned long *p = addr + BIT_WORD(nr);
e0e53b2f CC	134
	135	*p &= ~mask;
	136	}
	137
	138	/**
	139	* change_bit - Toggle a bit in memory
	140	* @nr: Bit to change
	141	* @addr: Address to start counting from
	142	*/
17a4ed8a	143	static inline void change_bit(int nr, unsigned long *addr)
e0e53b2f CC	144	{
e0e53b2f CC	145	unsigned long mask = BIT_MASK(nr);
17a4ed8a	146	unsigned long *p = addr + BIT_WORD(nr);
e0e53b2f CC	147
	148	*p ^= mask;
	149	}
	150
	151	/**
	152	* test_and_set_bit - Set a bit and return its old value
	153	* @nr: Bit to set
	154	* @addr: Address to count from
	155	*/
17a4ed8a	156	static inline int test_and_set_bit(int nr, unsigned long *addr)
e0e53b2f CC	157	{
e0e53b2f CC	158	unsigned long mask = BIT_MASK(nr);
17a4ed8a	159	unsigned long *p = addr + BIT_WORD(nr);
e0e53b2f CC	160	unsigned long old = *p;
	161
	162	*p = old \| mask;
	163	return (old & mask) != 0;
	164	}
	165
	166	/**
	167	* test_and_clear_bit - Clear a bit and return its old value
	168	* @nr: Bit to clear
	169	* @addr: Address to count from
	170	*/
17a4ed8a	171	static inline int test_and_clear_bit(int nr, unsigned long *addr)
e0e53b2f CC	172	{
e0e53b2f CC	173	unsigned long mask = BIT_MASK(nr);
17a4ed8a	174	unsigned long *p = addr + BIT_WORD(nr);
e0e53b2f CC	175	unsigned long old = *p;
	176
	177	*p = old & ~mask;
	178	return (old & mask) != 0;
	179	}
	180
	181	/**
	182	* test_and_change_bit - Change a bit and return its old value
	183	* @nr: Bit to change
	184	* @addr: Address to count from
	185	*/
17a4ed8a	186	static inline int test_and_change_bit(int nr, unsigned long *addr)
e0e53b2f CC	187	{
e0e53b2f CC	188	unsigned long mask = BIT_MASK(nr);
17a4ed8a	189	unsigned long *p = addr + BIT_WORD(nr);
04483e15	190	unsigned long old = *p;
e0e53b2f CC	191
	192	*p = old ^ mask;
	193	return (old & mask) != 0;
	194	}
	195
	196	/**
	197	* test_bit - Determine whether a bit is set
	198	* @nr: bit number to test
	199	* @addr: Address to start counting from
	200	*/
17a4ed8a	201	static inline int test_bit(int nr, const unsigned long *addr)
e0e53b2f CC	202	{
	203	return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
	204	}
	205
	206	/**
	207	* find_last_bit - find the last set bit in a memory region
	208	* @addr: The address to start the search at
	209	* @size: The maximum size to search
	210	*
	211	* Returns the bit number of the first set bit, or size.
	212	*/
	213	unsigned long find_last_bit(const unsigned long *addr,
	214	unsigned long size);
	215
	216	/**
	217	* find_next_bit - find the next set bit in a memory region
	218	* @addr: The address to base the search on
	219	* @offset: The bitnumber to start searching at
	220	* @size: The bitmap size in bits
	221	*/
	222	unsigned long find_next_bit(const unsigned long *addr,
	223	unsigned long size, unsigned long offset);
	224
	225	/**
	226	* find_next_zero_bit - find the next cleared bit in a memory region
	227	* @addr: The address to base the search on
	228	* @offset: The bitnumber to start searching at
	229	* @size: The bitmap size in bits
	230	*/
	231
	232	unsigned long find_next_zero_bit(const unsigned long *addr,
	233	unsigned long size,
	234	unsigned long offset);
	235
	236	/**
	237	* find_first_bit - find the first set bit in a memory region
	238	* @addr: The address to start the search at
	239	* @size: The maximum size to search
	240	*
	241	* Returns the bit number of the first set bit.
	242	*/
	243	static inline unsigned long find_first_bit(const unsigned long *addr,
	244	unsigned long size)
	245	{
	246	return find_next_bit(addr, size, 0);
	247	}
	248
	249	/**
	250	* find_first_zero_bit - find the first cleared bit in a memory region
	251	* @addr: The address to start the search at
	252	* @size: The maximum size to search
	253	*
	254	* Returns the bit number of the first cleared bit.
	255	*/
	256	static inline unsigned long find_first_zero_bit(const unsigned long *addr,
	257	unsigned long size)
	258	{
	259	return find_next_zero_bit(addr, size, 0);
	260	}
	261
	262	static inline unsigned long hweight_long(unsigned long w)
	263	{
	264	unsigned long count;
	265
266	for (count = 0; w; w >>= 1) {
267	count += w & 1;
268	}
269	return count;
270	}
271
84988cf9 PM	272	/**
	273	* extract32:
	274	* @value: the value to extract the bit field from
	275	* @start: the lowest bit in the bit field (numbered from 0)
	276	* @length: the length of the bit field
	277	*
	278	* Extract from the 32 bit input @value the bit field specified by the
	279	* @start and @length parameters, and return it. The bit field must
	280	* lie entirely within the 32 bit word. It is valid to request that
	281	* all 32 bits are returned (ie @length 32 and @start 0).
	282	*
	283	* Returns: the value of the bit field extracted from the input value.
	284	*/
	285	static inline uint32_t extract32(uint32_t value, int start, int length)
	286	{
	287	assert(start >= 0 && length > 0 && length <= 32 - start);
	288	return (value >> start) & (~0U >> (32 - length));
	289	}
	290
	291	/**
	292	* extract64:
	293	* @value: the value to extract the bit field from
	294	* @start: the lowest bit in the bit field (numbered from 0)
	295	* @length: the length of the bit field
	296	*
	297	* Extract from the 64 bit input @value the bit field specified by the
	298	* @start and @length parameters, and return it. The bit field must
	299	* lie entirely within the 64 bit word. It is valid to request that
	300	* all 64 bits are returned (ie @length 64 and @start 0).
	301	*
	302	* Returns: the value of the bit field extracted from the input value.
	303	*/
	304	static inline uint64_t extract64(uint64_t value, int start, int length)
	305	{
	306	assert(start >= 0 && length > 0 && length <= 64 - start);
	307	return (value >> start) & (~0ULL >> (64 - length));
	308	}
	309
	310	/**
	311	* deposit32:
	312	* @value: initial value to insert bit field into
	313	* @start: the lowest bit in the bit field (numbered from 0)
	314	* @length: the length of the bit field
	315	* @fieldval: the value to insert into the bit field
	316	*
	317	* Deposit @fieldval into the 32 bit @value at the bit field specified
	318	* by the @start and @length parameters, and return the modified
	319	* @value. Bits of @value outside the bit field are not modified.
	320	* Bits of @fieldval above the least significant @length bits are
	321	* ignored. The bit field must lie entirely within the 32 bit word.
ab411770 SW	322	* It is valid to request that all 32 bits are modified (ie @length
ab411770 SW	323	* 32 and @start 0).
84988cf9 PM	324	*
	325	* Returns: the modified @value.
	326	*/
	327	static inline uint32_t deposit32(uint32_t value, int start, int length,
	328	uint32_t fieldval)
	329	{
	330	uint32_t mask;
	331	assert(start >= 0 && length > 0 && length <= 32 - start);
	332	mask = (~0U >> (32 - length)) << start;
	333	return (value & ~mask) \| ((fieldval << start) & mask);
	334	}
	335
	336	/**
ab411770	337	* deposit64:
84988cf9 PM	338	* @value: initial value to insert bit field into
	339	* @start: the lowest bit in the bit field (numbered from 0)
	340	* @length: the length of the bit field
	341	* @fieldval: the value to insert into the bit field
	342	*
	343	* Deposit @fieldval into the 64 bit @value at the bit field specified
	344	* by the @start and @length parameters, and return the modified
	345	* @value. Bits of @value outside the bit field are not modified.
	346	* Bits of @fieldval above the least significant @length bits are
ab411770	347	* ignored. The bit field must lie entirely within the 64 bit word.
84988cf9 PM	348	* It is valid to request that all 64 bits are modified (ie @length
	349	* 64 and @start 0).
	350	*
	351	* Returns: the modified @value.
	352	*/
	353	static inline uint64_t deposit64(uint64_t value, int start, int length,
	354	uint64_t fieldval)
	355	{
	356	uint64_t mask;
	357	assert(start >= 0 && length > 0 && length <= 64 - start);
	358	mask = (~0ULL >> (64 - length)) << start;
	359	return (value & ~mask) \| ((fieldval << start) & mask);
	360	}
	361
e0e53b2f	362	#endif