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  * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
   7  * size and improve performance, 2015.
   8  *
   9  * This program is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU General Public License
  11  * as published by the Free Software Foundation; either version
  12  * 2 of the License, or (at your option) any later version.
  13  */
  14
  15 #include <linux/bitops.h>
  16 #include <linux/export.h>
  17 #include <linux/kernel.h>
  18
  19 #if !defined(find_next_bit) || !defined(find_next_zero_bit)
  20
  21 /*
  22  * This is a common helper function for find_next_bit and
  23  * find_next_zero_bit.  The difference is the "invert" argument, which
  24  * is XORed with each fetched word before searching it for one bits.
  25  */
  26 static unsigned long _find_next_bit(const unsigned long *addr,
  27                 unsigned long nbits, unsigned long start, unsigned long invert)
  28 {
  29         unsigned long tmp;
  30
  31         if (!nbits || start >= nbits)
  32                 return nbits;
  33
  34         tmp = addr[start / BITS_PER_LONG] ^ invert;
  35
  36         /* Handle 1st word. */
  37         tmp &= BITMAP_FIRST_WORD_MASK(start);
  38         start = round_down(start, BITS_PER_LONG);
  39
  40         while (!tmp) {
  41                 start += BITS_PER_LONG;
  42                 if (start >= nbits)
  43                         return nbits;
  44
  45                 tmp = addr[start / BITS_PER_LONG] ^ invert;
  46         }
  47
  48         return min(start + __ffs(tmp), nbits);
  49 }
  50 #endif
  51
  52 #ifndef find_next_bit
  53 /*
  54  * Find the next set bit in a memory region.
  55  */
  56 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  57                             unsigned long offset)
  58 {
  59         return _find_next_bit(addr, size, offset, 0UL);
  60 }
  61 EXPORT_SYMBOL(find_next_bit);
  62 #endif
  63
  64 #ifndef find_next_zero_bit
  65 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  66                                  unsigned long offset)
  67 {
  68         return _find_next_bit(addr, size, offset, ~0UL);
  69 }
  70 EXPORT_SYMBOL(find_next_zero_bit);
  71 #endif
  72
  73 #ifndef find_first_bit
  74 /*
  75  * Find the first set bit in a memory region.
  76  */
  77 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  78 {
  79         unsigned long idx;
  80
  81         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  82                 if (addr[idx])
  83                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  84         }
  85
  86         return size;
  87 }
  88 EXPORT_SYMBOL(find_first_bit);
  89 #endif
  90
  91 #ifndef find_first_zero_bit
  92 /*
  93  * Find the first cleared bit in a memory region.
  94  */
  95 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
  96 {
  97         unsigned long idx;
  98
  99         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 100                 if (addr[idx] != ~0UL)
 101                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
 102         }
 103
 104         return size;
 105 }
 106 EXPORT_SYMBOL(find_first_zero_bit);
 107 #endif
 108
 109 #ifdef __BIG_ENDIAN
 110
 111 /* include/linux/byteorder does not support "unsigned long" type */
 112 static inline unsigned long ext2_swab(const unsigned long y)
 113 {
 114 #if BITS_PER_LONG == 64
 115         return (unsigned long) __swab64((u64) y);
 116 #elif BITS_PER_LONG == 32
 117         return (unsigned long) __swab32((u32) y);
 118 #else
 119 #error BITS_PER_LONG not defined
 120 #endif
 121 }
 122
 123 #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
 124 static unsigned long _find_next_bit_le(const unsigned long *addr,
 125                 unsigned long nbits, unsigned long start, unsigned long invert)
 126 {
 127         unsigned long tmp;
 128
 129         if (!nbits || start >= nbits)
 130                 return nbits;
 131
 132         tmp = addr[start / BITS_PER_LONG] ^ invert;
 133
 134         /* Handle 1st word. */
 135         tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
 136         start = round_down(start, BITS_PER_LONG);
 137
 138         while (!tmp) {
 139                 start += BITS_PER_LONG;
 140                 if (start >= nbits)
 141                         return nbits;
 142
 143                 tmp = addr[start / BITS_PER_LONG] ^ invert;
 144         }
 145
 146         return min(start + __ffs(ext2_swab(tmp)), nbits);
 147 }
 148 #endif
 149
 150 #ifndef find_next_zero_bit_le
 151 unsigned long find_next_zero_bit_le(const void *addr, unsigned
 152                 long size, unsigned long offset)
 153 {
 154         return _find_next_bit_le(addr, size, offset, ~0UL);
 155 }
 156 EXPORT_SYMBOL(find_next_zero_bit_le);
 157 #endif
 158
 159 #ifndef find_next_bit_le
 160 unsigned long find_next_bit_le(const void *addr, unsigned
 161                 long size, unsigned long offset)
 162 {
 163         return _find_next_bit_le(addr, size, offset, 0UL);
 164 }
 165 EXPORT_SYMBOL(find_next_bit_le);
 166 #endif
 167
 168 #endif /* __BIG_ENDIAN */