File:  [Qemu by Fabrice Bellard] / qemu / bitops.c
Revision 1.1.1.1 (vendor branch): download - view: text, annotated - select for diffs
Tue Apr 24 18:56:26 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:  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
    3:  * Written by David Howells (dhowells@redhat.com)
    4:  * Copyright (C) 2008 IBM Corporation
    5:  * Written by Rusty Russell <rusty@rustcorp.com.au>
    6:  * (Inspired by David Howell's find_next_bit implementation)
    7:  *
    8:  * This program is free software; you can redistribute it and/or
    9:  * modify it under the terms of the GNU General Public License
   10:  * as published by the Free Software Foundation; either version
   11:  * 2 of the License, or (at your option) any later version.
   12:  */
   13: 
   14: #include "bitops.h"
   15: 
   16: #define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)
   17: 
   18: /*
   19:  * Find the next set bit in a memory region.
   20:  */
   21: unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
   22: 			    unsigned long offset)
   23: {
   24:     const unsigned long *p = addr + BITOP_WORD(offset);
   25:     unsigned long result = offset & ~(BITS_PER_LONG-1);
   26:     unsigned long tmp;
   27: 
   28:     if (offset >= size) {
   29:         return size;
   30:     }
   31:     size -= result;
   32:     offset %= BITS_PER_LONG;
   33:     if (offset) {
   34:         tmp = *(p++);
   35:         tmp &= (~0UL << offset);
   36:         if (size < BITS_PER_LONG) {
   37:             goto found_first;
   38:         }
   39:         if (tmp) {
   40:             goto found_middle;
   41:         }
   42:         size -= BITS_PER_LONG;
   43:         result += BITS_PER_LONG;
   44:     }
   45:     while (size & ~(BITS_PER_LONG-1)) {
   46:         if ((tmp = *(p++))) {
   47:             goto found_middle;
   48:         }
   49:         result += BITS_PER_LONG;
   50:         size -= BITS_PER_LONG;
   51:     }
   52:     if (!size) {
   53:         return result;
   54:     }
   55:     tmp = *p;
   56: 
   57: found_first:
   58:     tmp &= (~0UL >> (BITS_PER_LONG - size));
   59:     if (tmp == 0UL) {		/* Are any bits set? */
   60:         return result + size;	/* Nope. */
   61:     }
   62: found_middle:
   63:     return result + bitops_ffsl(tmp);
   64: }
   65: 
   66: /*
   67:  * This implementation of find_{first,next}_zero_bit was stolen from
   68:  * Linus' asm-alpha/bitops.h.
   69:  */
   70: unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
   71: 				 unsigned long offset)
   72: {
   73:     const unsigned long *p = addr + BITOP_WORD(offset);
   74:     unsigned long result = offset & ~(BITS_PER_LONG-1);
   75:     unsigned long tmp;
   76: 
   77:     if (offset >= size) {
   78:         return size;
   79:     }
   80:     size -= result;
   81:     offset %= BITS_PER_LONG;
   82:     if (offset) {
   83:         tmp = *(p++);
   84:         tmp |= ~0UL >> (BITS_PER_LONG - offset);
   85:         if (size < BITS_PER_LONG) {
   86:             goto found_first;
   87:         }
   88:         if (~tmp) {
   89:             goto found_middle;
   90:         }
   91:         size -= BITS_PER_LONG;
   92:         result += BITS_PER_LONG;
   93:     }
   94:     while (size & ~(BITS_PER_LONG-1)) {
   95:         if (~(tmp = *(p++))) {
   96:             goto found_middle;
   97:         }
   98:         result += BITS_PER_LONG;
   99:         size -= BITS_PER_LONG;
  100:     }
  101:     if (!size) {
  102:         return result;
  103:     }
  104:     tmp = *p;
  105: 
  106: found_first:
  107:     tmp |= ~0UL << size;
  108:     if (tmp == ~0UL) {	/* Are any bits zero? */
  109:         return result + size;	/* Nope. */
  110:     }
  111: found_middle:
  112:     return result + ffz(tmp);
  113: }
  114: 
  115: unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
  116: {
  117:     unsigned long words;
  118:     unsigned long tmp;
  119: 
  120:     /* Start at final word. */
  121:     words = size / BITS_PER_LONG;
  122: 
  123:     /* Partial final word? */
  124:     if (size & (BITS_PER_LONG-1)) {
  125:         tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
  126:                                        - (size & (BITS_PER_LONG-1)))));
  127:         if (tmp) {
  128:             goto found;
  129:         }
  130:     }
  131: 
  132:     while (words) {
  133:         tmp = addr[--words];
  134:         if (tmp) {
  135:         found:
  136:             return words * BITS_PER_LONG + bitops_flsl(tmp);
  137:         }
  138:     }
  139: 
  140:     /* Not found */
  141:     return size;
  142: }

unix.superglobalmegacorp.com