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