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