File:  [Qemu by Fabrice Bellard] / qemu / bitops.h
Revision 1.1.1.1 (vendor branch): download - view: text, annotated - select for diffs
Tue Apr 24 18:56:44 2018 UTC (3 years, 1 month ago) by root
Branches: qemu, MAIN
CVS tags: qemu1101, qemu1001, qemu1000, qemu0151, HEAD
qemu 0.15.1

    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:  */
   69: static inline unsigned long bitops_flsl(unsigned long word)
   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);
  190: 	unsigned long old = *p;
  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: 
  272: #endif

unix.superglobalmegacorp.com