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