[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, volatile unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
	unsigned long *p = ((unsigned long *)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, volatile unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
	unsigned long *p = ((unsigned long *)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, volatile unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
	unsigned long *p = ((unsigned long *)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, volatile unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
	unsigned long *p = ((unsigned long *)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, volatile unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
	unsigned long *p = ((unsigned long *)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, volatile unsigned long *addr)
{
	unsigned long mask = BIT_MASK(nr);
	unsigned long *p = ((unsigned long *)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 volatile 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 64 bits are modified (ie @length
 * 64 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);
}

/**
 * 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 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 32 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	*/
	117	static inline void set_bit(int nr, volatile unsigned long *addr)
	118	{
	119	unsigned long mask = BIT_MASK(nr);
	120	unsigned long p = ((unsigned long )addr) + BIT_WORD(nr);
	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	*/
	130	static inline void clear_bit(int nr, volatile unsigned long *addr)
	131	{
	132	unsigned long mask = BIT_MASK(nr);
	133	unsigned long p = ((unsigned long )addr) + BIT_WORD(nr);
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	*/
143	static inline void change_bit(int nr, volatile unsigned long *addr)
144	{
145	unsigned long mask = BIT_MASK(nr);
146	unsigned long p = ((unsigned long )addr) + BIT_WORD(nr);
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	*/
156	static inline int test_and_set_bit(int nr, volatile unsigned long *addr)
157	{
158	unsigned long mask = BIT_MASK(nr);
159	unsigned long p = ((unsigned long )addr) + BIT_WORD(nr);
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	*/
171	static inline int test_and_clear_bit(int nr, volatile unsigned long *addr)
172	{
173	unsigned long mask = BIT_MASK(nr);
174	unsigned long p = ((unsigned long )addr) + BIT_WORD(nr);
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	*/
186	static inline int test_and_change_bit(int nr, volatile unsigned long *addr)
187	{
188	unsigned long mask = BIT_MASK(nr);
189	unsigned long p = ((unsigned long )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	*/
	201	static inline int test_bit(int nr, const volatile unsigned long *addr)
	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.
	322	* It is valid to request that all 64 bits are modified (ie @length
	323	* 64 and @start 0).
	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	/**
337	* deposit32:
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
347	* ignored. The bit field must lie entirely within the 32 bit word.
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