lib/find_bit.c

   1 /* bit search implementation
   2  *
   3  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
   4  * Written by David Howells (dhowells@redhat.com)
   5  *
   6  * Copyright (C) 2008 IBM Corporation
   7  * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
   8  * (Inspired by David Howell's find_next_bit implementation)
   9  *
  10  * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
  11  * size and improve performance, 2015.
  12  *
  13  * This program is free software; you can redistribute it and/or
  14  * modify it under the terms of the GNU General Public License
  15  * as published by the Free Software Foundation; either version
  16  * 2 of the License, or (at your option) any later version.
  17  */
  18
  19 #include <linux/bitops.h>
  20 #include <linux/bitmap.h>
  21 #include <linux/export.h>
  22 #include <linux/kernel.h>
  23
  24 #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
  25                 !defined(find_next_and_bit)
  26
  27 /*
  28  * This is a common helper function for find_next_bit, find_next_zero_bit, and
  29  * find_next_and_bit. The differences are:
  30  *  - The "invert" argument, which is XORed with each fetched word before
  31  *    searching it for one bits.
  32  *  - The optional "addr2", which is anded with "addr1" if present.
  33  */
  34 static inline unsigned long _find_next_bit(const unsigned long *addr1,
  35                 const unsigned long *addr2, unsigned long nbits,
  36                 unsigned long start, unsigned long invert)
  37 {
  38         unsigned long tmp;
  39
  40         if (unlikely(start >= nbits))
  41                 return nbits;
  42
  43         tmp = addr1[start / BITS_PER_LONG];
  44         if (addr2)
  45                 tmp &= addr2[start / BITS_PER_LONG];
  46         tmp ^= invert;
  47
  48         /* Handle 1st word. */
  49         tmp &= BITMAP_FIRST_WORD_MASK(start);
  50         start = round_down(start, BITS_PER_LONG);
  51
  52         while (!tmp) {
  53                 start += BITS_PER_LONG;
  54                 if (start >= nbits)
  55                         return nbits;
  56
  57                 tmp = addr1[start / BITS_PER_LONG];
  58                 if (addr2)
  59                         tmp &= addr2[start / BITS_PER_LONG];
  60                 tmp ^= invert;
  61         }
  62
  63         return min(start + __ffs(tmp), nbits);
  64 }
  65 #endif
  66
  67 #ifndef find_next_bit
  68 /*
  69  * Find the next set bit in a memory region.
  70  */
  71 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  72                             unsigned long offset)
  73 {
  74         return _find_next_bit(addr, NULL, size, offset, 0UL);
  75 }
  76 EXPORT_SYMBOL(find_next_bit);
  77 #endif
  78
  79 #ifndef find_next_zero_bit
  80 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  81                                  unsigned long offset)
  82 {
  83         return _find_next_bit(addr, NULL, size, offset, ~0UL);
  84 }
  85 EXPORT_SYMBOL(find_next_zero_bit);
  86 #endif
  87
  88 #if !defined(find_next_and_bit)
  89 unsigned long find_next_and_bit(const unsigned long *addr1,
  90                 const unsigned long *addr2, unsigned long size,
  91                 unsigned long offset)
  92 {
  93         return _find_next_bit(addr1, addr2, size, offset, 0UL);
  94 }
  95 EXPORT_SYMBOL(find_next_and_bit);
  96 #endif
  97
  98 #ifndef find_first_bit
  99 /*
 100  * Find the first set bit in a memory region.
 101  */
 102 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 103 {
 104         unsigned long idx;
 105
 106         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 107                 if (addr[idx])
 108                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
 109         }
 110
 111         return size;
 112 }
 113 EXPORT_SYMBOL(find_first_bit);
 114 #endif
 115
 116 #ifndef find_first_zero_bit
 117 /*
 118  * Find the first cleared bit in a memory region.
 119  */
 120 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 121 {
 122         unsigned long idx;
 123
 124         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 125                 if (addr[idx] != ~0UL)
 126                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
 127         }
 128
 129         return size;
 130 }
 131 EXPORT_SYMBOL(find_first_zero_bit);
 132 #endif
 133
 134 #ifndef find_last_bit
 135 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
 136 {
 137         if (size) {
 138                 unsigned long val = BITMAP_LAST_WORD_MASK(size);
 139                 unsigned long idx = (size-1) / BITS_PER_LONG;
 140
 141                 do {
 142                         val &= addr[idx];
 143                         if (val)
 144                                 return idx * BITS_PER_LONG + __fls(val);
 145
 146                         val = ~0ul;
 147                 } while (idx--);
 148         }
 149         return size;
 150 }
 151 EXPORT_SYMBOL(find_last_bit);
 152 #endif
 153
 154 #ifdef __BIG_ENDIAN
 155
 156 /* include/linux/byteorder does not support "unsigned long" type */
 157 static inline unsigned long ext2_swab(const unsigned long y)
 158 {
 159 #if BITS_PER_LONG == 64
 160         return (unsigned long) __swab64((u64) y);
 161 #elif BITS_PER_LONG == 32
 162         return (unsigned long) __swab32((u32) y);
 163 #else
 164 #error BITS_PER_LONG not defined
 165 #endif
 166 }
 167
 168 #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
 169 static inline unsigned long _find_next_bit_le(const unsigned long *addr1,
 170                 const unsigned long *addr2, unsigned long nbits,
 171                 unsigned long start, unsigned long invert)
 172 {
 173         unsigned long tmp;
 174
 175         if (unlikely(start >= nbits))
 176                 return nbits;
 177
 178         tmp = addr1[start / BITS_PER_LONG];
 179         if (addr2)
 180                 tmp &= addr2[start / BITS_PER_LONG];
 181         tmp ^= invert;
 182
 183         /* Handle 1st word. */
 184         tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
 185         start = round_down(start, BITS_PER_LONG);
 186
 187         while (!tmp) {
 188                 start += BITS_PER_LONG;
 189                 if (start >= nbits)
 190                         return nbits;
 191
 192                 tmp = addr1[start / BITS_PER_LONG];
 193                 if (addr2)
 194                         tmp &= addr2[start / BITS_PER_LONG];
 195                 tmp ^= invert;
 196         }
 197
 198         return min(start + __ffs(ext2_swab(tmp)), nbits);
 199 }
 200 #endif
 201
 202 #ifndef find_next_zero_bit_le
 203 unsigned long find_next_zero_bit_le(const void *addr, unsigned
 204                 long size, unsigned long offset)
 205 {
 206         return _find_next_bit_le(addr, NULL, size, offset, ~0UL);
 207 }
 208 EXPORT_SYMBOL(find_next_zero_bit_le);
 209 #endif
 210
 211 #ifndef find_next_bit_le
 212 unsigned long find_next_bit_le(const void *addr, unsigned
 213                 long size, unsigned long offset)
 214 {
 215         return _find_next_bit_le(addr, NULL, size, offset, 0UL);
 216 }
 217 EXPORT_SYMBOL(find_next_bit_le);
 218 #endif
 219
 220 #endif /* __BIG_ENDIAN */