LXR qemu/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 "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 */
  21unsigned 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
  57found_first:
  58    tmp &= (~0UL >> (BITS_PER_LONG - size));
  59    if (tmp == 0UL) {           /* Are any bits set? */
  60        return result + size;   /* Nope. */
  61    }
  62found_middle:
  63    return result + bitops_ffsl(tmp);
  64}
  65
  66/*
  67 * This implementation of find_{first,next}_zero_bit was stolen from
  68 * Linus' asm-alpha/bitops.h.
  69 */
  70unsigned 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
 106found_first:
 107    tmp |= ~0UL << size;
 108    if (tmp == ~0UL) {  /* Are any bits zero? */
 109        return result + size;   /* Nope. */
 110    }
 111found_middle:
 112    return result + ffz(tmp);
 113}
 114
 115unsigned 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 + bitops_flsl(tmp);
 137        }
 138    }
 139
 140    /* Not found */
 141    return size;
 142}
 143