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