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