util/bitops.c

   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 "qemu/osdep.h"
  15 #include "qemu/bitops.h"
  16
  17 #define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
  18
  19 /*
  20  * Find the next set bit in a memory region.
  21  */
  22 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  23                             unsigned long offset)
  24 {
  25     const unsigned long *p = addr + BITOP_WORD(offset);
  26     unsigned long result = offset & ~(BITS_PER_LONG-1);
  27     unsigned long tmp;
  28
  29     if (offset >= size) {
  30         return size;
  31     }
  32     size -= result;
  33     offset %= BITS_PER_LONG;
  34     if (offset) {
  35         tmp = *(p++);
  36         tmp &= (~0UL << offset);
  37         if (size < BITS_PER_LONG) {
  38             goto found_first;
  39         }
  40         if (tmp) {
  41             goto found_middle;
  42         }
  43         size -= BITS_PER_LONG;
  44         result += BITS_PER_LONG;
  45     }
  46     while (size >= 4*BITS_PER_LONG) {
  47         unsigned long d1, d2, d3;
  48         tmp = *p;
  49         d1 = *(p+1);
  50         d2 = *(p+2);
  51         d3 = *(p+3);
  52         if (tmp) {
  53             goto found_middle;
  54         }
  55         if (d1 | d2 | d3) {
  56             break;
  57         }
  58         p += 4;
  59         result += 4*BITS_PER_LONG;
  60         size -= 4*BITS_PER_LONG;
  61     }
  62     while (size >= BITS_PER_LONG) {
  63         if ((tmp = *(p++))) {
  64             goto found_middle;
  65         }
  66         result += BITS_PER_LONG;
  67         size -= BITS_PER_LONG;
  68     }
  69     if (!size) {
  70         return result;
  71     }
  72     tmp = *p;
  73
  74 found_first:
  75     tmp &= (~0UL >> (BITS_PER_LONG - size));
  76     if (tmp == 0UL) {           /* Are any bits set? */
  77         return result + size;   /* Nope. */
  78     }
  79 found_middle:
  80     return result + ctzl(tmp);
  81 }
  82
  83 /*
  84  * This implementation of find_{first,next}_zero_bit was stolen from
  85  * Linus' asm-alpha/bitops.h.
  86  */
  87 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  88                                  unsigned long offset)
  89 {
  90     const unsigned long *p = addr + BITOP_WORD(offset);
  91     unsigned long result = offset & ~(BITS_PER_LONG-1);
  92     unsigned long tmp;
  93
  94     if (offset >= size) {
  95         return size;
  96     }
  97     size -= result;
  98     offset %= BITS_PER_LONG;
  99     if (offset) {
 100         tmp = *(p++);
 101         tmp |= ~0UL >> (BITS_PER_LONG - offset);
 102         if (size < BITS_PER_LONG) {
 103             goto found_first;
 104         }
 105         if (~tmp) {
 106             goto found_middle;
 107         }
 108         size -= BITS_PER_LONG;
 109         result += BITS_PER_LONG;
 110     }
 111     while (size & ~(BITS_PER_LONG-1)) {
 112         if (~(tmp = *(p++))) {
 113             goto found_middle;
 114         }
 115         result += BITS_PER_LONG;
 116         size -= BITS_PER_LONG;
 117     }
 118     if (!size) {
 119         return result;
 120     }
 121     tmp = *p;
 122
 123 found_first:
 124     tmp |= ~0UL << size;
 125     if (tmp == ~0UL) {  /* Are any bits zero? */
 126         return result + size;   /* Nope. */
 127     }
 128 found_middle:
 129     return result + ctzl(~tmp);
 130 }
 131
 132 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
 133 {
 134     unsigned long words;
 135     unsigned long tmp;
 136
 137     /* Start at final word. */
 138     words = size / BITS_PER_LONG;
 139
 140     /* Partial final word? */
 141     if (size & (BITS_PER_LONG-1)) {
 142         tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
 143                                        - (size & (BITS_PER_LONG-1)))));
 144         if (tmp) {
 145             goto found;
 146         }
 147     }
 148
 149     while (words) {
 150         tmp = addr[--words];
 151         if (tmp) {
 152         found:
 153             return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp);
 154         }
 155     }
 156
 157     /* Not found */
 158     return size;
 159 }