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