kern/src/find_next_bit.c

   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  */
  25 unsigned 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
  56 found_first:
  57         tmp &= (~0UL >> (BITS_PER_LONG - size));
  58         if (tmp == 0UL)         /* Are any bits set? */
  59                 return result + size;   /* Nope. */
  60 found_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  */
  68 unsigned 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
  99 found_first:
 100         tmp |= ~0UL << size;
 101         if (tmp == ~0UL)        /* Are any bits zero? */
 102                 return result + size;   /* Nope. */
 103 found_middle:
 104         return result + ffz(tmp);
 105 }
 106
 107 /*
 108  * Find the first set bit in a memory region.
 109  */
 110 unsigned 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. */
 128 found:
 129         return result + __ffs(tmp);
 130 }
 131
 132 /*
 133  * Find the first cleared bit in a memory region.
 134  */
 135 unsigned 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. */
 153 found:
 154         return result + ffz(tmp);
 155 }
 156