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 & ~(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 + ctzl(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 + ctzl(~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 + BITS_PER_LONG - 1 - clzl(tmp);
 137         }
 138     }
 139
 140     /* Not found */
 141     return size;
 142 }