lib/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 <linux/bitops.h>
  13 #include <linux/module.h>
  14 #include <asm/types.h>
  15 #include <asm/byteorder.h>
  16
  17 #define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
  18
  19 /**
  20  * find_next_bit - find the next set bit in a memory region
  21  * @addr: The address to base the search on
  22  * @offset: The bitnumber to start searching at
  23  * @size: The maximum size to search
  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 EXPORT_SYMBOL(find_next_bit);
  65
  66 /*
  67  * This implementation of find_{first,next}_zero_bit was stolen from
  68  * Linus' asm-alpha/bitops.h.
  69  */
  70 unsigned 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         size -= result;
  80         offset %= BITS_PER_LONG;
  81         if (offset) {
  82                 tmp = *(p++);
  83                 tmp |= ~0UL >> (BITS_PER_LONG - offset);
  84                 if (size < BITS_PER_LONG)
  85                         goto found_first;
  86                 if (~tmp)
  87                         goto found_middle;
  88                 size -= BITS_PER_LONG;
  89                 result += BITS_PER_LONG;
  90         }
  91         while (size & ~(BITS_PER_LONG-1)) {
  92                 if (~(tmp = *(p++)))
  93                         goto found_middle;
  94                 result += BITS_PER_LONG;
  95                 size -= BITS_PER_LONG;
  96         }
  97         if (!size)
  98                 return result;
  99         tmp = *p;
 100
 101 found_first:
 102         tmp |= ~0UL << size;
 103         if (tmp == ~0UL)        /* Are any bits zero? */
 104                 return result + size;   /* Nope. */
 105 found_middle:
 106         return result + ffz(tmp);
 107 }
 108
 109 EXPORT_SYMBOL(find_next_zero_bit);
 110
 111 #ifdef __BIG_ENDIAN
 112
 113 /* include/linux/byteorder does not support "unsigned long" type */
 114 static inline unsigned long ext2_swabp(const unsigned long * x)
 115 {
 116 #if BITS_PER_LONG == 64
 117         return (unsigned long) __swab64p((u64 *) x);
 118 #elif BITS_PER_LONG == 32
 119         return (unsigned long) __swab32p((u32 *) x);
 120 #else
 121 #error BITS_PER_LONG not defined
 122 #endif
 123 }
 124
 125 /* include/linux/byteorder doesn't support "unsigned long" type */
 126 static inline unsigned long ext2_swab(const unsigned long y)
 127 {
 128 #if BITS_PER_LONG == 64
 129         return (unsigned long) __swab64((u64) y);
 130 #elif BITS_PER_LONG == 32
 131         return (unsigned long) __swab32((u32) y);
 132 #else
 133 #error BITS_PER_LONG not defined
 134 #endif
 135 }
 136
 137 unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned
 138                 long size, unsigned long offset)
 139 {
 140         const unsigned long *p = addr + BITOP_WORD(offset);
 141         unsigned long result = offset & ~(BITS_PER_LONG - 1);
 142         unsigned long tmp;
 143
 144         if (offset >= size)
 145                 return size;
 146         size -= result;
 147         offset &= (BITS_PER_LONG - 1UL);
 148         if (offset) {
 149                 tmp = ext2_swabp(p++);
 150                 tmp |= (~0UL >> (BITS_PER_LONG - offset));
 151                 if (size < BITS_PER_LONG)
 152                         goto found_first;
 153                 if (~tmp)
 154                         goto found_middle;
 155                 size -= BITS_PER_LONG;
 156                 result += BITS_PER_LONG;
 157         }
 158
 159         while (size & ~(BITS_PER_LONG - 1)) {
 160                 if (~(tmp = *(p++)))
 161                         goto found_middle_swap;
 162                 result += BITS_PER_LONG;
 163                 size -= BITS_PER_LONG;
 164         }
 165         if (!size)
 166                 return result;
 167         tmp = ext2_swabp(p);
 168 found_first:
 169         tmp |= ~0UL << size;
 170         if (tmp == ~0UL)        /* Are any bits zero? */
 171                 return result + size; /* Nope. Skip ffz */
 172 found_middle:
 173         return result + ffz(tmp);
 174
 175 found_middle_swap:
 176         return result + ffz(ext2_swab(tmp));
 177 }
 178
 179 EXPORT_SYMBOL(generic_find_next_zero_le_bit);
 180
 181 unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned
 182                 long size, unsigned long offset)
 183 {
 184         const unsigned long *p = addr + BITOP_WORD(offset);
 185         unsigned long result = offset & ~(BITS_PER_LONG - 1);
 186         unsigned long tmp;
 187
 188         if (offset >= size)
 189                 return size;
 190         size -= result;
 191         offset &= (BITS_PER_LONG - 1UL);
 192         if (offset) {
 193                 tmp = ext2_swabp(p++);
 194                 tmp &= (~0UL << offset);
 195                 if (size < BITS_PER_LONG)
 196                         goto found_first;
 197                 if (tmp)
 198                         goto found_middle;
 199                 size -= BITS_PER_LONG;
 200                 result += BITS_PER_LONG;
 201         }
 202
 203         while (size & ~(BITS_PER_LONG - 1)) {
 204                 tmp = *(p++);
 205                 if (tmp)
 206                         goto found_middle_swap;
 207                 result += BITS_PER_LONG;
 208                 size -= BITS_PER_LONG;
 209         }
 210         if (!size)
 211                 return result;
 212         tmp = ext2_swabp(p);
 213 found_first:
 214         tmp &= (~0UL >> (BITS_PER_LONG - size));
 215         if (tmp == 0UL)         /* Are any bits set? */
 216                 return result + size; /* Nope. */
 217 found_middle:
 218         return result + __ffs(tmp);
 219
 220 found_middle_swap:
 221         return result + __ffs(ext2_swab(tmp));
 222 }
 223 EXPORT_SYMBOL(generic_find_next_le_bit);
 224 #endif /* __BIG_ENDIAN */