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