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 #ifndef find_next_bit
  20 /*
  21  * Find the next set bit in a memory region.
  22  */
  23 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  24                             unsigned long offset)
  25 {
  26         const unsigned long *p = addr + BITOP_WORD(offset);
  27         unsigned long result = offset & ~(BITS_PER_LONG-1);
  28         unsigned long tmp;
  29
  30         if (offset >= size)
  31                 return size;
  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                 if (tmp)
  40                         goto found_middle;
  41                 size -= BITS_PER_LONG;
  42                 result += BITS_PER_LONG;
  43         }
  44         while (size & ~(BITS_PER_LONG-1)) {
  45                 if ((tmp = *(p++)))
  46                         goto found_middle;
  47                 result += BITS_PER_LONG;
  48                 size -= BITS_PER_LONG;
  49         }
  50         if (!size)
  51                 return result;
  52         tmp = *p;
  53
  54 found_first:
  55         tmp &= (~0UL >> (BITS_PER_LONG - size));
  56         if (tmp == 0UL)         /* Are any bits set? */
  57                 return result + size;   /* Nope. */
  58 found_middle:
  59         return result + __ffs(tmp);
  60 }
  61 EXPORT_SYMBOL(find_next_bit);
  62 #endif
  63
  64 #ifndef find_next_zero_bit
  65 /*
  66  * This implementation of find_{first,next}_zero_bit was stolen from
  67  * Linus' asm-alpha/bitops.h.
  68  */
  69 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  70                                  unsigned long offset)
  71 {
  72         const unsigned long *p = addr + BITOP_WORD(offset);
  73         unsigned long result = offset & ~(BITS_PER_LONG-1);
  74         unsigned long tmp;
  75
  76         if (offset >= size)
  77                 return size;
  78         size -= result;
  79         offset %= BITS_PER_LONG;
  80         if (offset) {
  81                 tmp = *(p++);
  82                 tmp |= ~0UL >> (BITS_PER_LONG - offset);
  83                 if (size < BITS_PER_LONG)
  84                         goto found_first;
  85                 if (~tmp)
  86                         goto found_middle;
  87                 size -= BITS_PER_LONG;
  88                 result += BITS_PER_LONG;
  89         }
  90         while (size & ~(BITS_PER_LONG-1)) {
  91                 if (~(tmp = *(p++)))
  92                         goto found_middle;
  93                 result += BITS_PER_LONG;
  94                 size -= BITS_PER_LONG;
  95         }
  96         if (!size)
  97                 return result;
  98         tmp = *p;
  99
 100 found_first:
 101         tmp |= ~0UL << size;
 102         if (tmp == ~0UL)        /* Are any bits zero? */
 103                 return result + size;   /* Nope. */
 104 found_middle:
 105         return result + ffz(tmp);
 106 }
 107 EXPORT_SYMBOL(find_next_zero_bit);
 108 #endif
 109
 110 #ifndef find_first_bit
 111 /*
 112  * Find the first set bit in a memory region.
 113  */
 114 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 115 {
 116         const unsigned long *p = addr;
 117         unsigned long result = 0;
 118         unsigned long tmp;
 119
 120         while (size & ~(BITS_PER_LONG-1)) {
 121                 if ((tmp = *(p++)))
 122                         goto found;
 123                 result += BITS_PER_LONG;
 124                 size -= BITS_PER_LONG;
 125         }
 126         if (!size)
 127                 return result;
 128
 129         tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
 130         if (tmp == 0UL)         /* Are any bits set? */
 131                 return result + size;   /* Nope. */
 132 found:
 133         return result + __ffs(tmp);
 134 }
 135 EXPORT_SYMBOL(find_first_bit);
 136 #endif
 137
 138 #ifndef find_first_zero_bit
 139 /*
 140  * Find the first cleared bit in a memory region.
 141  */
 142 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 143 {
 144         const unsigned long *p = addr;
 145         unsigned long result = 0;
 146         unsigned long tmp;
 147
 148         while (size & ~(BITS_PER_LONG-1)) {
 149                 if (~(tmp = *(p++)))
 150                         goto found;
 151                 result += BITS_PER_LONG;
 152                 size -= BITS_PER_LONG;
 153         }
 154         if (!size)
 155                 return result;
 156
 157         tmp = (*p) | (~0UL << size);
 158         if (tmp == ~0UL)        /* Are any bits zero? */
 159                 return result + size;   /* Nope. */
 160 found:
 161         return result + ffz(tmp);
 162 }
 163 EXPORT_SYMBOL(find_first_zero_bit);
 164 #endif
 165
 166 #ifdef __BIG_ENDIAN
 167
 168 /* include/linux/byteorder does not support "unsigned long" type */
 169 static inline unsigned long ext2_swabp(const unsigned long * x)
 170 {
 171 #if BITS_PER_LONG == 64
 172         return (unsigned long) __swab64p((u64 *) x);
 173 #elif BITS_PER_LONG == 32
 174         return (unsigned long) __swab32p((u32 *) x);
 175 #else
 176 #error BITS_PER_LONG not defined
 177 #endif
 178 }
 179
 180 /* include/linux/byteorder doesn't support "unsigned long" type */
 181 static inline unsigned long ext2_swab(const unsigned long y)
 182 {
 183 #if BITS_PER_LONG == 64
 184         return (unsigned long) __swab64((u64) y);
 185 #elif BITS_PER_LONG == 32
 186         return (unsigned long) __swab32((u32) y);
 187 #else
 188 #error BITS_PER_LONG not defined
 189 #endif
 190 }
 191
 192 #ifndef find_next_zero_bit_le
 193 unsigned long find_next_zero_bit_le(const void *addr, unsigned
 194                 long size, unsigned long offset)
 195 {
 196         const unsigned long *p = addr;
 197         unsigned long result = offset & ~(BITS_PER_LONG - 1);
 198         unsigned long tmp;
 199
 200         if (offset >= size)
 201                 return size;
 202         p += BITOP_WORD(offset);
 203         size -= result;
 204         offset &= (BITS_PER_LONG - 1UL);
 205         if (offset) {
 206                 tmp = ext2_swabp(p++);
 207                 tmp |= (~0UL >> (BITS_PER_LONG - offset));
 208                 if (size < BITS_PER_LONG)
 209                         goto found_first;
 210                 if (~tmp)
 211                         goto found_middle;
 212                 size -= BITS_PER_LONG;
 213                 result += BITS_PER_LONG;
 214         }
 215
 216         while (size & ~(BITS_PER_LONG - 1)) {
 217                 if (~(tmp = *(p++)))
 218                         goto found_middle_swap;
 219                 result += BITS_PER_LONG;
 220                 size -= BITS_PER_LONG;
 221         }
 222         if (!size)
 223                 return result;
 224         tmp = ext2_swabp(p);
 225 found_first:
 226         tmp |= ~0UL << size;
 227         if (tmp == ~0UL)        /* Are any bits zero? */
 228                 return result + size; /* Nope. Skip ffz */
 229 found_middle:
 230         return result + ffz(tmp);
 231
 232 found_middle_swap:
 233         return result + ffz(ext2_swab(tmp));
 234 }
 235 EXPORT_SYMBOL(find_next_zero_bit_le);
 236 #endif
 237
 238 #ifndef find_next_bit_le
 239 unsigned long find_next_bit_le(const void *addr, unsigned
 240                 long size, unsigned long offset)
 241 {
 242         const unsigned long *p = addr;
 243         unsigned long result = offset & ~(BITS_PER_LONG - 1);
 244         unsigned long tmp;
 245
 246         if (offset >= size)
 247                 return size;
 248         p += BITOP_WORD(offset);
 249         size -= result;
 250         offset &= (BITS_PER_LONG - 1UL);
 251         if (offset) {
 252                 tmp = ext2_swabp(p++);
 253                 tmp &= (~0UL << offset);
 254                 if (size < BITS_PER_LONG)
 255                         goto found_first;
 256                 if (tmp)
 257                         goto found_middle;
 258                 size -= BITS_PER_LONG;
 259                 result += BITS_PER_LONG;
 260         }
 261
 262         while (size & ~(BITS_PER_LONG - 1)) {
 263                 tmp = *(p++);
 264                 if (tmp)
 265                         goto found_middle_swap;
 266                 result += BITS_PER_LONG;
 267                 size -= BITS_PER_LONG;
 268         }
 269         if (!size)
 270                 return result;
 271         tmp = ext2_swabp(p);
 272 found_first:
 273         tmp &= (~0UL >> (BITS_PER_LONG - size));
 274         if (tmp == 0UL)         /* Are any bits set? */
 275                 return result + size; /* Nope. */
 276 found_middle:
 277         return result + __ffs(tmp);
 278
 279 found_middle_swap:
 280         return result + __ffs(ext2_swab(tmp));
 281 }
 282 EXPORT_SYMBOL(find_next_bit_le);
 283 #endif
 284
 285 #endif /* __BIG_ENDIAN */