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