[deliverable/linux.git] / include / asm-i386 / bitops.h

#ifndef _I386_BITOPS_H
#define _I386_BITOPS_H

/*
 * Copyright 1992, Linus Torvalds.
 */

#include <linux/config.h>
#include <linux/compiler.h>
#include <asm/alternative.h>

/*
 * These have to be done with inline assembly: that way the bit-setting
 * is guaranteed to be atomic. All bit operations return 0 if the bit
 * was cleared before the operation and != 0 if it was not.
 *
 * bit 0 is the LSB of addr; bit 32 is the LSB of (addr+1).
 */

#define ADDR (*(volatile long *) addr)

/**
 * set_bit - Atomically set a bit in memory
 * @nr: the bit to set
 * @addr: the address to start counting from
 *
 * This function is atomic and may not be reordered.  See __set_bit()
 * if you do not require the atomic guarantees.
 *
 * Note: there are no guarantees that this function will not be reordered
 * on non x86 architectures, so if you are writting portable code,
 * make sure not to rely on its reordering guarantees.
 *
 * Note that @nr may be almost arbitrarily large; this function is not
 * restricted to acting on a single-word quantity.
 */
static inline void set_bit(int nr, volatile unsigned long * addr)
{
	__asm__ __volatile__( LOCK_PREFIX
		"btsl %1,%0"
		:"+m" (ADDR)
		:"Ir" (nr));
}

/**
 * __set_bit - Set a bit in memory
 * @nr: the bit to set
 * @addr: the address to start counting from
 *
 * Unlike set_bit(), this function is non-atomic and may be reordered.
 * If it's called on the same region of memory simultaneously, the effect
 * may be that only one operation succeeds.
 */
static inline void __set_bit(int nr, volatile unsigned long * addr)
{
	__asm__(
		"btsl %1,%0"
		:"+m" (ADDR)
		:"Ir" (nr));
}

/**
 * clear_bit - Clears a bit in memory
 * @nr: Bit to clear
 * @addr: Address to start counting from
 *
 * clear_bit() is atomic and may not be reordered.  However, it does
 * not contain a memory barrier, so if it is used for locking purposes,
 * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
 * in order to ensure changes are visible on other processors.
 */
static inline void clear_bit(int nr, volatile unsigned long * addr)
{
	__asm__ __volatile__( LOCK_PREFIX
		"btrl %1,%0"
		:"+m" (ADDR)
		:"Ir" (nr));
}

static inline void __clear_bit(int nr, volatile unsigned long * addr)
{
	__asm__ __volatile__(
		"btrl %1,%0"
		:"+m" (ADDR)
		:"Ir" (nr));
}
#define smp_mb__before_clear_bit()	barrier()
#define smp_mb__after_clear_bit()	barrier()

/**
 * __change_bit - Toggle a bit in memory
 * @nr: the bit to change
 * @addr: the address to start counting from
 *
 * Unlike change_bit(), this function is non-atomic and may be reordered.
 * If it's called on the same region of memory simultaneously, the effect
 * may be that only one operation succeeds.
 */
static inline void __change_bit(int nr, volatile unsigned long * addr)
{
	__asm__ __volatile__(
		"btcl %1,%0"
		:"+m" (ADDR)
		:"Ir" (nr));
}

/**
 * change_bit - Toggle a bit in memory
 * @nr: Bit to change
 * @addr: Address to start counting from
 *
 * change_bit() is atomic and may not be reordered. It may be
 * reordered on other architectures than x86.
 * Note that @nr may be almost arbitrarily large; this function is not
 * restricted to acting on a single-word quantity.
 */
static inline void change_bit(int nr, volatile unsigned long * addr)
{
	__asm__ __volatile__( LOCK_PREFIX
		"btcl %1,%0"
		:"+m" (ADDR)
		:"Ir" (nr));
}

/**
 * test_and_set_bit - Set a bit and return its old value
 * @nr: Bit to set
 * @addr: Address to count from
 *
 * This operation is atomic and cannot be reordered.  
 * It may be reordered on other architectures than x86.
 * It also implies a memory barrier.
 */
static inline int test_and_set_bit(int nr, volatile unsigned long * addr)
{
	int oldbit;

	__asm__ __volatile__( LOCK_PREFIX
		"btsl %2,%1\n\tsbbl %0,%0"
		:"=r" (oldbit),"+m" (ADDR)
		:"Ir" (nr) : "memory");
	return oldbit;
}

/**
 * __test_and_set_bit - Set a bit and return its old value
 * @nr: Bit to set
 * @addr: Address to count from
 *
 * This operation is non-atomic and can be reordered.  
 * If two examples of this operation race, one can appear to succeed
 * but actually fail.  You must protect multiple accesses with a lock.
 */
static inline int __test_and_set_bit(int nr, volatile unsigned long * addr)
{
	int oldbit;

	__asm__(
		"btsl %2,%1\n\tsbbl %0,%0"
		:"=r" (oldbit),"+m" (ADDR)
		:"Ir" (nr));
	return oldbit;
}

/**
 * test_and_clear_bit - Clear a bit and return its old value
 * @nr: Bit to clear
 * @addr: Address to count from
 *
 * This operation is atomic and cannot be reordered.
 * It can be reorderdered on other architectures other than x86.
 * It also implies a memory barrier.
 */
static inline int test_and_clear_bit(int nr, volatile unsigned long * addr)
{
	int oldbit;

	__asm__ __volatile__( LOCK_PREFIX
		"btrl %2,%1\n\tsbbl %0,%0"
		:"=r" (oldbit),"+m" (ADDR)
		:"Ir" (nr) : "memory");
	return oldbit;
}

/**
 * __test_and_clear_bit - Clear a bit and return its old value
 * @nr: Bit to clear
 * @addr: Address to count from
 *
 * This operation is non-atomic and can be reordered.  
 * If two examples of this operation race, one can appear to succeed
 * but actually fail.  You must protect multiple accesses with a lock.
 */
static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
{
	int oldbit;

	__asm__(
		"btrl %2,%1\n\tsbbl %0,%0"
		:"=r" (oldbit),"+m" (ADDR)
		:"Ir" (nr));
	return oldbit;
}

/* WARNING: non atomic and it can be reordered! */
static inline int __test_and_change_bit(int nr, volatile unsigned long *addr)
{
	int oldbit;

	__asm__ __volatile__(
		"btcl %2,%1\n\tsbbl %0,%0"
		:"=r" (oldbit),"+m" (ADDR)
		:"Ir" (nr) : "memory");
	return oldbit;
}

/**
 * test_and_change_bit - Change a bit and return its old value
 * @nr: Bit to change
 * @addr: Address to count from
 *
 * This operation is atomic and cannot be reordered.  
 * It also implies a memory barrier.
 */
static inline int test_and_change_bit(int nr, volatile unsigned long* addr)
{
	int oldbit;

	__asm__ __volatile__( LOCK_PREFIX
		"btcl %2,%1\n\tsbbl %0,%0"
		:"=r" (oldbit),"+m" (ADDR)
		:"Ir" (nr) : "memory");
	return oldbit;
}

#if 0 /* Fool kernel-doc since it doesn't do macros yet */
/**
 * test_bit - Determine whether a bit is set
 * @nr: bit number to test
 * @addr: Address to start counting from
 */
static int test_bit(int nr, const volatile void * addr);
#endif

static __always_inline int constant_test_bit(int nr, const volatile unsigned long *addr)
{
	return ((1UL << (nr & 31)) & (addr[nr >> 5])) != 0;
}

static inline int variable_test_bit(int nr, const volatile unsigned long * addr)
{
	int oldbit;

	__asm__ __volatile__(
		"btl %2,%1\n\tsbbl %0,%0"
		:"=r" (oldbit)
		:"m" (ADDR),"Ir" (nr));
	return oldbit;
}

#define test_bit(nr,addr) \
(__builtin_constant_p(nr) ? \
 constant_test_bit((nr),(addr)) : \
 variable_test_bit((nr),(addr)))

#undef ADDR

/**
 * find_first_zero_bit - find the first zero 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 zero bit, not the number of the byte
 * containing a bit.
 */
static inline int find_first_zero_bit(const unsigned long *addr, unsigned size)
{
	int d0, d1, d2;
	int res;

	if (!size)
		return 0;
	/* This looks at memory. Mark it volatile to tell gcc not to move it around */
	__asm__ __volatile__(
		"movl $-1,%%eax\n\t"
		"xorl %%edx,%%edx\n\t"
		"repe; scasl\n\t"
		"je 1f\n\t"
		"xorl -4(%%edi),%%eax\n\t"
		"subl $4,%%edi\n\t"
		"bsfl %%eax,%%edx\n"
		"1:\tsubl %%ebx,%%edi\n\t"
		"shll $3,%%edi\n\t"
		"addl %%edi,%%edx"
		:"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
		:"1" ((size + 31) >> 5), "2" (addr), "b" (addr) : "memory");
	return res;
}

/**
 * find_next_zero_bit - find the first zero bit in a memory region
 * @addr: The address to base the search on
 * @offset: The bitnumber to start searching at
 * @size: The maximum size to search
 */
int find_next_zero_bit(const unsigned long *addr, int size, int offset);

/**
 * __ffs - find first bit in word.
 * @word: The word to search
 *
 * Undefined if no bit exists, so code should check against 0 first.
 */
static inline unsigned long __ffs(unsigned long word)
{
	__asm__("bsfl %1,%0"
		:"=r" (word)
		:"rm" (word));
	return word;
}

/**
 * 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, not the number of the byte
 * containing a bit.
 */
static inline unsigned find_first_bit(const unsigned long *addr, unsigned size)
{
	unsigned x = 0;

	while (x < size) {
		unsigned long val = *addr++;
		if (val)
			return __ffs(val) + x;
		x += (sizeof(*addr)<<3);
	}
	return x;
}

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

/**
 * 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)
{
	__asm__("bsfl %1,%0"
		:"=r" (word)
		:"r" (~word));
	return word;
}

#define fls64(x)   generic_fls64(x)

#ifdef __KERNEL__

/*
 * Every architecture must define this function. It's the fastest
 * way of searching a 140-bit bitmap where the first 100 bits are
 * unlikely to be set. It's guaranteed that at least one of the 140
 * bits is cleared.
 */
static inline int sched_find_first_bit(const unsigned long *b)
{
	if (unlikely(b[0]))
		return __ffs(b[0]);
	if (unlikely(b[1]))
		return __ffs(b[1]) + 32;
	if (unlikely(b[2]))
		return __ffs(b[2]) + 64;
	if (b[3])
		return __ffs(b[3]) + 96;
	return __ffs(b[4]) + 128;
}

/**
 * ffs - find first bit set
 * @x: the word to search
 *
 * This is defined the same way as
 * the libc and compiler builtin ffs routines, therefore
 * differs in spirit from the above ffz (man ffs).
 */
static inline int ffs(int x)
{
	int r;

	__asm__("bsfl %1,%0\n\t"
		"jnz 1f\n\t"
		"movl $-1,%0\n"
		"1:" : "=r" (r) : "rm" (x));
	return r+1;
}

/**
 * fls - find last bit set
 * @x: the word to search
 *
 * This is defined the same way as ffs.
 */
static inline int fls(int x)
{
	int r;

	__asm__("bsrl %1,%0\n\t"
		"jnz 1f\n\t"
		"movl $-1,%0\n"
		"1:" : "=r" (r) : "rm" (x));
	return r+1;
}

/**
 * hweightN - returns the hamming weight of a N-bit word
 * @x: the word to weigh
 *
 * The Hamming Weight of a number is the total number of bits set in it.
 */

#define hweight32(x) generic_hweight32(x)
#define hweight16(x) generic_hweight16(x)
#define hweight8(x) generic_hweight8(x)

#endif /* __KERNEL__ */

#ifdef __KERNEL__

#define ext2_set_bit(nr,addr) \
	__test_and_set_bit((nr),(unsigned long*)addr)
#define ext2_set_bit_atomic(lock,nr,addr) \
        test_and_set_bit((nr),(unsigned long*)addr)
#define ext2_clear_bit(nr, addr) \
	__test_and_clear_bit((nr),(unsigned long*)addr)
#define ext2_clear_bit_atomic(lock,nr, addr) \
	        test_and_clear_bit((nr),(unsigned long*)addr)
#define ext2_test_bit(nr, addr)      test_bit((nr),(unsigned long*)addr)
#define ext2_find_first_zero_bit(addr, size) \
	find_first_zero_bit((unsigned long*)addr, size)
#define ext2_find_next_zero_bit(addr, size, off) \
	find_next_zero_bit((unsigned long*)addr, size, off)

/* Bitmap functions for the minix filesystem.  */
#define minix_test_and_set_bit(nr,addr) __test_and_set_bit(nr,(void*)addr)
#define minix_set_bit(nr,addr) __set_bit(nr,(void*)addr)
#define minix_test_and_clear_bit(nr,addr) __test_and_clear_bit(nr,(void*)addr)
#define minix_test_bit(nr,addr) test_bit(nr,(void*)addr)
#define minix_find_first_zero_bit(addr,size) \
	find_first_zero_bit((void*)addr,size)

#endif /* __KERNEL__ */

#endif /* _I386_BITOPS_H */
Commit	Line	Data
1da177e4 LT	1	#ifndef _I386_BITOPS_H
	2	#define _I386_BITOPS_H
	3
	4	/*
	5	* Copyright 1992, Linus Torvalds.
	6	*/
	7
	8	#include <linux/config.h>
	9	#include <linux/compiler.h>
9a0b5817	10	#include <asm/alternative.h>
1da177e4 LT	11
	12	/*
	13	* These have to be done with inline assembly: that way the bit-setting
	14	* is guaranteed to be atomic. All bit operations return 0 if the bit
	15	* was cleared before the operation and != 0 if it was not.
	16	*
	17	* bit 0 is the LSB of addr; bit 32 is the LSB of (addr+1).
	18	*/
	19
1da177e4 LT	20	#define ADDR ((volatile long ) addr)
	21
	22	/**
	23	* set_bit - Atomically set a bit in memory
	24	* @nr: the bit to set
	25	* @addr: the address to start counting from
	26	*
	27	* This function is atomic and may not be reordered. See __set_bit()
	28	* if you do not require the atomic guarantees.
	29	*
	30	* Note: there are no guarantees that this function will not be reordered
	31	* on non x86 architectures, so if you are writting portable code,
	32	* make sure not to rely on its reordering guarantees.
	33	*
	34	* Note that @nr may be almost arbitrarily large; this function is not
	35	* restricted to acting on a single-word quantity.
	36	*/
	37	static inline void set_bit(int nr, volatile unsigned long * addr)
	38	{
	39	__asm__ __volatile__( LOCK_PREFIX
	40	"btsl %1,%0"
92934bcb	41	:"+m" (ADDR)
1da177e4 LT	42	:"Ir" (nr));
	43	}
	44
	45	/**
	46	* __set_bit - Set a bit in memory
	47	* @nr: the bit to set
	48	* @addr: the address to start counting from
	49	*
	50	* Unlike set_bit(), this function is non-atomic and may be reordered.
	51	* If it's called on the same region of memory simultaneously, the effect
	52	* may be that only one operation succeeds.
	53	*/
	54	static inline void __set_bit(int nr, volatile unsigned long * addr)
	55	{
	56	__asm__(
	57	"btsl %1,%0"
92934bcb	58	:"+m" (ADDR)
1da177e4 LT	59	:"Ir" (nr));
	60	}
	61
	62	/**
	63	* clear_bit - Clears a bit in memory
	64	* @nr: Bit to clear
	65	* @addr: Address to start counting from
	66	*
	67	* clear_bit() is atomic and may not be reordered. However, it does
	68	* not contain a memory barrier, so if it is used for locking purposes,
	69	* you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
	70	* in order to ensure changes are visible on other processors.
	71	*/
	72	static inline void clear_bit(int nr, volatile unsigned long * addr)
	73	{
	74	__asm__ __volatile__( LOCK_PREFIX
	75	"btrl %1,%0"
92934bcb	76	:"+m" (ADDR)
1da177e4 LT	77	:"Ir" (nr));
	78	}
	79
	80	static inline void __clear_bit(int nr, volatile unsigned long * addr)
	81	{
	82	__asm__ __volatile__(
	83	"btrl %1,%0"
92934bcb	84	:"+m" (ADDR)
1da177e4 LT	85	:"Ir" (nr));
	86	}
	87	#define smp_mb__before_clear_bit() barrier()
	88	#define smp_mb__after_clear_bit() barrier()
	89
	90	/**
	91	* __change_bit - Toggle a bit in memory
	92	* @nr: the bit to change
	93	* @addr: the address to start counting from
	94	*
	95	* Unlike change_bit(), this function is non-atomic and may be reordered.
	96	* If it's called on the same region of memory simultaneously, the effect
	97	* may be that only one operation succeeds.
	98	*/
	99	static inline void __change_bit(int nr, volatile unsigned long * addr)
	100	{
	101	__asm__ __volatile__(
	102	"btcl %1,%0"
92934bcb	103	:"+m" (ADDR)
1da177e4 LT	104	:"Ir" (nr));
	105	}
	106
	107	/**
	108	* change_bit - Toggle a bit in memory
	109	* @nr: Bit to change
	110	* @addr: Address to start counting from
	111	*
	112	* change_bit() is atomic and may not be reordered. It may be
	113	* reordered on other architectures than x86.
	114	* Note that @nr may be almost arbitrarily large; this function is not
	115	* restricted to acting on a single-word quantity.
	116	*/
	117	static inline void change_bit(int nr, volatile unsigned long * addr)
	118	{
	119	__asm__ __volatile__( LOCK_PREFIX
	120	"btcl %1,%0"
92934bcb	121	:"+m" (ADDR)
1da177e4 LT	122	:"Ir" (nr));
	123	}
	124
	125	/**
	126	* test_and_set_bit - Set a bit and return its old value
	127	* @nr: Bit to set
	128	* @addr: Address to count from
	129	*
	130	* This operation is atomic and cannot be reordered.
	131	* It may be reordered on other architectures than x86.
	132	* It also implies a memory barrier.
	133	*/
	134	static inline int test_and_set_bit(int nr, volatile unsigned long * addr)
	135	{
	136	int oldbit;
	137
	138	__asm__ __volatile__( LOCK_PREFIX
	139	"btsl %2,%1\n\tsbbl %0,%0"
92934bcb	140	:"=r" (oldbit),"+m" (ADDR)
1da177e4 LT	141	:"Ir" (nr) : "memory");
	142	return oldbit;
	143	}
	144
	145	/**
	146	* __test_and_set_bit - Set a bit and return its old value
	147	* @nr: Bit to set
	148	* @addr: Address to count from
	149	*
	150	* This operation is non-atomic and can be reordered.
	151	* If two examples of this operation race, one can appear to succeed
	152	* but actually fail. You must protect multiple accesses with a lock.
	153	*/
	154	static inline int __test_and_set_bit(int nr, volatile unsigned long * addr)
	155	{
	156	int oldbit;
	157
	158	__asm__(
	159	"btsl %2,%1\n\tsbbl %0,%0"
92934bcb	160	:"=r" (oldbit),"+m" (ADDR)
1da177e4 LT	161	:"Ir" (nr));
	162	return oldbit;
	163	}
	164
	165	/**
	166	* test_and_clear_bit - Clear a bit and return its old value
	167	* @nr: Bit to clear
	168	* @addr: Address to count from
	169	*
	170	* This operation is atomic and cannot be reordered.
	171	* It can be reorderdered on other architectures other than x86.
	172	* It also implies a memory barrier.
	173	*/
	174	static inline int test_and_clear_bit(int nr, volatile unsigned long * addr)
	175	{
	176	int oldbit;
	177
	178	__asm__ __volatile__( LOCK_PREFIX
	179	"btrl %2,%1\n\tsbbl %0,%0"
92934bcb	180	:"=r" (oldbit),"+m" (ADDR)
1da177e4 LT	181	:"Ir" (nr) : "memory");
	182	return oldbit;
	183	}
	184
	185	/**
	186	* __test_and_clear_bit - Clear a bit and return its old value
	187	* @nr: Bit to clear
	188	* @addr: Address to count from
	189	*
	190	* This operation is non-atomic and can be reordered.
	191	* If two examples of this operation race, one can appear to succeed
	192	* but actually fail. You must protect multiple accesses with a lock.
	193	*/
	194	static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
	195	{
	196	int oldbit;
	197
	198	__asm__(
	199	"btrl %2,%1\n\tsbbl %0,%0"
92934bcb	200	:"=r" (oldbit),"+m" (ADDR)
1da177e4 LT	201	:"Ir" (nr));
	202	return oldbit;
	203	}
	204
	205	/* WARNING: non atomic and it can be reordered! */
	206	static inline int __test_and_change_bit(int nr, volatile unsigned long *addr)
	207	{
	208	int oldbit;
	209
	210	__asm__ __volatile__(
	211	"btcl %2,%1\n\tsbbl %0,%0"
92934bcb	212	:"=r" (oldbit),"+m" (ADDR)
1da177e4 LT	213	:"Ir" (nr) : "memory");
	214	return oldbit;
	215	}
	216
	217	/**
	218	* test_and_change_bit - Change a bit and return its old value
	219	* @nr: Bit to change
	220	* @addr: Address to count from
	221	*
	222	* This operation is atomic and cannot be reordered.
	223	* It also implies a memory barrier.
	224	*/
	225	static inline int test_and_change_bit(int nr, volatile unsigned long* addr)
	226	{
	227	int oldbit;
	228
	229	__asm__ __volatile__( LOCK_PREFIX
	230	"btcl %2,%1\n\tsbbl %0,%0"
92934bcb	231	:"=r" (oldbit),"+m" (ADDR)
1da177e4 LT	232	:"Ir" (nr) : "memory");
	233	return oldbit;
	234	}
	235
	236	#if 0 /* Fool kernel-doc since it doesn't do macros yet */
	237	/**
	238	* test_bit - Determine whether a bit is set
	239	* @nr: bit number to test
	240	* @addr: Address to start counting from
	241	*/
	242	static int test_bit(int nr, const volatile void * addr);
	243	#endif
	244
652050ae	245	static __always_inline int constant_test_bit(int nr, const volatile unsigned long *addr)
1da177e4 LT	246	{
	247	return ((1UL << (nr & 31)) & (addr[nr >> 5])) != 0;
	248	}
	249
	250	static inline int variable_test_bit(int nr, const volatile unsigned long * addr)
	251	{
	252	int oldbit;
	253
	254	__asm__ __volatile__(
	255	"btl %2,%1\n\tsbbl %0,%0"
	256	:"=r" (oldbit)
	257	:"m" (ADDR),"Ir" (nr));
	258	return oldbit;
	259	}
	260
	261	#define test_bit(nr,addr) \
	262	(__builtin_constant_p(nr) ? \
	263	constant_test_bit((nr),(addr)) : \
	264	variable_test_bit((nr),(addr)))
	265
	266	#undef ADDR
	267
	268	/**
	269	* find_first_zero_bit - find the first zero bit in a memory region
	270	* @addr: The address to start the search at
	271	* @size: The maximum size to search
	272	*
	273	* Returns the bit-number of the first zero bit, not the number of the byte
	274	* containing a bit.
	275	*/
	276	static inline int find_first_zero_bit(const unsigned long *addr, unsigned size)
	277	{
	278	int d0, d1, d2;
	279	int res;
	280
	281	if (!size)
	282	return 0;
	283	/* This looks at memory. Mark it volatile to tell gcc not to move it around */
	284	__asm__ __volatile__(
	285	"movl $-1,%%eax\n\t"
	286	"xorl %%edx,%%edx\n\t"
	287	"repe; scasl\n\t"
	288	"je 1f\n\t"
	289	"xorl -4(%%edi),%%eax\n\t"
	290	"subl $4,%%edi\n\t"
	291	"bsfl %%eax,%%edx\n"
	292	"1:\tsubl %%ebx,%%edi\n\t"
	293	"shll $3,%%edi\n\t"
	294	"addl %%edi,%%edx"
	295	:"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
	296	:"1" ((size + 31) >> 5), "2" (addr), "b" (addr) : "memory");
	297	return res;
	298	}
	299
	300	/**
	301	* find_next_zero_bit - find the first zero bit in a memory region
	302	* @addr: The address to base the search on
	303	* @offset: The bitnumber to start searching at
	304	* @size: The maximum size to search
	305	*/
	306	int find_next_zero_bit(const unsigned long *addr, int size, int offset);
	307
cd85c8b4 SR	308	/**
	309	* __ffs - find first bit in word.
	310	* @word: The word to search
	311	*
	312	* Undefined if no bit exists, so code should check against 0 first.
	313	*/
	314	static inline unsigned long __ffs(unsigned long word)
	315	{
	316	__asm__("bsfl %1,%0"
	317	:"=r" (word)
	318	:"rm" (word));
	319	return word;
	320	}
	321
1da177e4 LT	322	/**
	323	* find_first_bit - find the first set bit in a memory region
	324	* @addr: The address to start the search at
	325	* @size: The maximum size to search
	326	*
	327	* Returns the bit-number of the first set bit, not the number of the byte
	328	* containing a bit.
	329	*/
d89c145c	330	static inline unsigned find_first_bit(const unsigned long *addr, unsigned size)
1da177e4	331	{
d89c145c	332	unsigned x = 0;
d6d2a2ab LT	333
	334	while (x < size) {
	335	unsigned long val = *addr++;
	336	if (val)
	337	return __ffs(val) + x;
cd85c8b4	338	x += (sizeof(*addr)<<3);
d6d2a2ab	339	}
cd85c8b4	340	return x;
1da177e4 LT	341	}
	342
	343	/**
	344	* find_next_bit - find the first set bit in a memory region
	345	* @addr: The address to base the search on
	346	* @offset: The bitnumber to start searching at
	347	* @size: The maximum size to search
	348	*/
	349	int find_next_bit(const unsigned long *addr, int size, int offset);
	350
	351	/**
	352	* ffz - find first zero in word.
	353	* @word: The word to search
	354	*
	355	* Undefined if no zero exists, so code should check against ~0UL first.
	356	*/
	357	static inline unsigned long ffz(unsigned long word)
	358	{
	359	__asm__("bsfl %1,%0"
	360	:"=r" (word)
	361	:"r" (~word));
	362	return word;
	363	}
	364
3821af2f	365	#define fls64(x) generic_fls64(x)
1da177e4 LT	366
	367	#ifdef __KERNEL__
	368
	369	/*
	370	* Every architecture must define this function. It's the fastest
	371	* way of searching a 140-bit bitmap where the first 100 bits are
	372	* unlikely to be set. It's guaranteed that at least one of the 140
	373	* bits is cleared.
	374	*/
	375	static inline int sched_find_first_bit(const unsigned long *b)
	376	{
	377	if (unlikely(b[0]))
	378	return __ffs(b[0]);
	379	if (unlikely(b[1]))
	380	return __ffs(b[1]) + 32;
	381	if (unlikely(b[2]))
	382	return __ffs(b[2]) + 64;
	383	if (b[3])
	384	return __ffs(b[3]) + 96;
	385	return __ffs(b[4]) + 128;
	386	}
	387
	388	/**
	389	* ffs - find first bit set
	390	* @x: the word to search
	391	*
	392	* This is defined the same way as
	393	* the libc and compiler builtin ffs routines, therefore
	394	* differs in spirit from the above ffz (man ffs).
	395	*/
	396	static inline int ffs(int x)
	397	{
	398	int r;
	399
	400	__asm__("bsfl %1,%0\n\t"
	401	"jnz 1f\n\t"
	402	"movl $-1,%0\n"
	403	"1:" : "=r" (r) : "rm" (x));
	404	return r+1;
	405	}
	406
d832245d SH	407	/**
	408	* fls - find last bit set
	409	* @x: the word to search
	410	*
	411	* This is defined the same way as ffs.
	412	*/
	413	static inline int fls(int x)
	414	{
	415	int r;
	416
	417	__asm__("bsrl %1,%0\n\t"
	418	"jnz 1f\n\t"
	419	"movl $-1,%0\n"
	420	"1:" : "=r" (r) : "rm" (x));
	421	return r+1;
	422	}
	423
1da177e4 LT	424	/**
	425	* hweightN - returns the hamming weight of a N-bit word
	426	* @x: the word to weigh
	427	*
	428	* The Hamming Weight of a number is the total number of bits set in it.
	429	*/
	430
	431	#define hweight32(x) generic_hweight32(x)
	432	#define hweight16(x) generic_hweight16(x)
	433	#define hweight8(x) generic_hweight8(x)
	434
	435	#endif /* __KERNEL__ */
	436
	437	#ifdef __KERNEL__
	438
	439	#define ext2_set_bit(nr,addr) \
	440	__test_and_set_bit((nr),(unsigned long*)addr)
	441	#define ext2_set_bit_atomic(lock,nr,addr) \
	442	test_and_set_bit((nr),(unsigned long*)addr)
	443	#define ext2_clear_bit(nr, addr) \
	444	__test_and_clear_bit((nr),(unsigned long*)addr)
	445	#define ext2_clear_bit_atomic(lock,nr, addr) \
	446	test_and_clear_bit((nr),(unsigned long*)addr)
	447	#define ext2_test_bit(nr, addr) test_bit((nr),(unsigned long*)addr)
	448	#define ext2_find_first_zero_bit(addr, size) \
	449	find_first_zero_bit((unsigned long*)addr, size)
	450	#define ext2_find_next_zero_bit(addr, size, off) \
	451	find_next_zero_bit((unsigned long*)addr, size, off)
	452
	453	/* Bitmap functions for the minix filesystem. */
	454	#define minix_test_and_set_bit(nr,addr) __test_and_set_bit(nr,(void*)addr)
	455	#define minix_set_bit(nr,addr) __set_bit(nr,(void*)addr)
	456	#define minix_test_and_clear_bit(nr,addr) __test_and_clear_bit(nr,(void*)addr)
	457	#define minix_test_bit(nr,addr) test_bit(nr,(void*)addr)
	458	#define minix_find_first_zero_bit(addr,size) \
	459	find_first_zero_bit((void*)addr,size)
	460
	461	#endif /* __KERNEL__ */
	462
	463	#endif /* _I386_BITOPS_H */