LXR qemu/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 */
  20unsigned 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
  72found_first:
  73    tmp &= (~0UL >> (BITS_PER_LONG - size));
  74    if (tmp == 0UL) {           /* Are any bits set? */
  75        return result + size;   /* Nope. */
  76    }
  77found_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 */
  85unsigned 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
 121found_first:
 122    tmp |= ~0UL << size;
 123    if (tmp == ~0UL) {          /* Are any bits zero? */
 124        return result + size;   /* Nope. */
 125    }
 126found_middle:
 127    return result + ctzl(~tmp);
 128}
 129
 130unsigned 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}
 158