akaros/kern/src/find_next_bit.c
<<
>>
Prefs
   1/* find_next_bit.c: fallback find next bit implementation
   2 *
   3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
   4 * Written by David Howells (dhowells@redhat.com)
   5 *
   6 * This program is free software; you can redistribute it and/or
   7 * modify it under the terms of the GNU General Public License
   8 * as published by the Free Software Foundation; either version
   9 * 2 of the License, or (at your option) any later version.
  10 */
  11
  12#include <arch/arch.h>
  13#include <error.h>
  14#include <atomic.h>
  15#include <string.h>
  16#include <assert.h>
  17#include <bitops.h>
  18#include <bitmap.h>
  19
  20#define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
  21
  22/*
  23 * Find the next set bit in a memory region.
  24 */
  25unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  26                            unsigned long offset)
  27{
  28        const unsigned long *p = addr + BITOP_WORD(offset);
  29        unsigned long result = offset & ~(BITS_PER_LONG-1);
  30        unsigned long tmp;
  31
  32        if (offset >= size)
  33                return size;
  34        size -= result;
  35        offset %= BITS_PER_LONG;
  36        if (offset) {
  37                tmp = *(p++);
  38                tmp &= (~0UL << offset);
  39                if (size < BITS_PER_LONG)
  40                        goto found_first;
  41                if (tmp)
  42                        goto found_middle;
  43                size -= BITS_PER_LONG;
  44                result += BITS_PER_LONG;
  45        }
  46        while (size & ~(BITS_PER_LONG-1)) {
  47                if ((tmp = *(p++)))
  48                        goto found_middle;
  49                result += BITS_PER_LONG;
  50                size -= BITS_PER_LONG;
  51        }
  52        if (!size)
  53                return result;
  54        tmp = *p;
  55
  56found_first:
  57        tmp &= (~0UL >> (BITS_PER_LONG - size));
  58        if (tmp == 0UL)         /* Are any bits set? */
  59                return result + size;   /* Nope. */
  60found_middle:
  61        return result + __ffs(tmp);
  62}
  63
  64/*
  65 * This implementation of find_{first,next}_zero_bit was stolen from
  66 * Linus' asm-alpha/bitops.h.
  67 */
  68unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  69                                 unsigned long offset)
  70{
  71        const unsigned long *p = addr + BITOP_WORD(offset);
  72        unsigned long result = offset & ~(BITS_PER_LONG-1);
  73        unsigned long tmp;
  74
  75        if (offset >= size)
  76                return size;
  77        size -= result;
  78        offset %= BITS_PER_LONG;
  79        if (offset) {
  80                tmp = *(p++);
  81                tmp |= ~0UL >> (BITS_PER_LONG - offset);
  82                if (size < BITS_PER_LONG)
  83                        goto found_first;
  84                if (~tmp)
  85                        goto found_middle;
  86                size -= BITS_PER_LONG;
  87                result += BITS_PER_LONG;
  88        }
  89        while (size & ~(BITS_PER_LONG-1)) {
  90                if (~(tmp = *(p++)))
  91                        goto found_middle;
  92                result += BITS_PER_LONG;
  93                size -= BITS_PER_LONG;
  94        }
  95        if (!size)
  96                return result;
  97        tmp = *p;
  98
  99found_first:
 100        tmp |= ~0UL << size;
 101        if (tmp == ~0UL)        /* Are any bits zero? */
 102                return result + size;   /* Nope. */
 103found_middle:
 104        return result + ffz(tmp);
 105}
 106
 107/*
 108 * Find the first set bit in a memory region.
 109 */
 110unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 111{
 112        const unsigned long *p = addr;
 113        unsigned long result = 0;
 114        unsigned long tmp;
 115
 116        while (size & ~(BITS_PER_LONG-1)) {
 117                if ((tmp = *(p++)))
 118                        goto found;
 119                result += BITS_PER_LONG;
 120                size -= BITS_PER_LONG;
 121        }
 122        if (!size)
 123                return result;
 124
 125        tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
 126        if (tmp == 0UL)         /* Are any bits set? */
 127                return result + size;   /* Nope. */
 128found:
 129        return result + __ffs(tmp);
 130}
 131
 132/*
 133 * Find the first cleared bit in a memory region.
 134 */
 135unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 136{
 137        const unsigned long *p = addr;
 138        unsigned long result = 0;
 139        unsigned long tmp;
 140
 141        while (size & ~(BITS_PER_LONG-1)) {
 142                if (~(tmp = *(p++)))
 143                        goto found;
 144                result += BITS_PER_LONG;
 145                size -= BITS_PER_LONG;
 146        }
 147        if (!size)
 148                return result;
 149
 150        tmp = (*p) | (~0UL << size);
 151        if (tmp == ~0UL)        /* Are any bits zero? */
 152                return result + size;   /* Nope. */
 153found:
 154        return result + ffz(tmp);
 155}
 156
 157