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
  26 /*
  27  * This is a common helper function for find_next_bit and
  28  * find_next_zero_bit.  The difference is the "invert" argument, which
  29  * is XORed with each fetched word before searching it for one bits.
  30  */
  31 static unsigned long _find_next_bit(const unsigned long *addr,
  32                 unsigned long nbits, unsigned long start, unsigned long invert)
  33 {
  34         unsigned long tmp;
  35
  36         if (unlikely(start >= nbits))
  37                 return nbits;
  38
  39         tmp = addr[start / BITS_PER_LONG] ^ invert;
  40
  41         /* Handle 1st word. */
  42         tmp &= BITMAP_FIRST_WORD_MASK(start);
  43         start = round_down(start, BITS_PER_LONG);
  44
  45         while (!tmp) {
  46                 start += BITS_PER_LONG;
  47                 if (start >= nbits)
  48                         return nbits;
  49
  50                 tmp = addr[start / BITS_PER_LONG] ^ invert;
  51         }
  52
  53         return min(start + __ffs(tmp), nbits);
  54 }
  55 #endif
  56
  57 #ifndef find_next_bit
  58 /*
  59  * Find the next set bit in a memory region.
  60  */
  61 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  62                             unsigned long offset)
  63 {
  64         return _find_next_bit(addr, size, offset, 0UL);
  65 }
  66 EXPORT_SYMBOL(find_next_bit);
  67 #endif
  68
  69 #ifndef find_next_zero_bit
  70 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  71                                  unsigned long offset)
  72 {
  73         return _find_next_bit(addr, size, offset, ~0UL);
  74 }
  75 EXPORT_SYMBOL(find_next_zero_bit);
  76 #endif
  77
  78 #ifndef find_first_bit
  79 /*
  80  * Find the first set bit in a memory region.
  81  */
  82 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  83 {
  84         unsigned long idx;
  85
  86         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  87                 if (addr[idx])
  88                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  89         }
  90
  91         return size;
  92 }
  93 EXPORT_SYMBOL(find_first_bit);
  94 #endif
  95
  96 #ifndef find_first_zero_bit
  97 /*
  98  * Find the first cleared bit in a memory region.
  99  */
 100 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 101 {
 102         unsigned long idx;
 103
 104         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 105                 if (addr[idx] != ~0UL)
 106                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
 107         }
 108
 109         return size;
 110 }
 111 EXPORT_SYMBOL(find_first_zero_bit);
 112 #endif
 113
 114 #ifndef find_last_bit
 115 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
 116 {
 117         if (size) {
 118                 unsigned long val = BITMAP_LAST_WORD_MASK(size);
 119                 unsigned long idx = (size-1) / BITS_PER_LONG;
 120
 121                 do {
 122                         val &= addr[idx];
 123                         if (val)
 124                                 return idx * BITS_PER_LONG + __fls(val);
 125
 126                         val = ~0ul;
 127                 } while (idx--);
 128         }
 129         return size;
 130 }
 131 EXPORT_SYMBOL(find_last_bit);
 132 #endif
 133
 134 #ifdef __BIG_ENDIAN
 135
 136 /* include/linux/byteorder does not support "unsigned long" type */
 137 static inline unsigned long ext2_swab(const unsigned long y)
 138 {
 139 #if BITS_PER_LONG == 64
 140         return (unsigned long) __swab64((u64) y);
 141 #elif BITS_PER_LONG == 32
 142         return (unsigned long) __swab32((u32) y);
 143 #else
 144 #error BITS_PER_LONG not defined
 145 #endif
 146 }
 147
 148 #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
 149 static unsigned long _find_next_bit_le(const unsigned long *addr,
 150                 unsigned long nbits, unsigned long start, unsigned long invert)
 151 {
 152         unsigned long tmp;
 153
 154         if (unlikely(start >= nbits))
 155                 return nbits;
 156
 157         tmp = addr[start / BITS_PER_LONG] ^ invert;
 158
 159         /* Handle 1st word. */
 160         tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
 161         start = round_down(start, BITS_PER_LONG);
 162
 163         while (!tmp) {
 164                 start += BITS_PER_LONG;
 165                 if (start >= nbits)
 166                         return nbits;
 167
 168                 tmp = addr[start / BITS_PER_LONG] ^ invert;
 169         }
 170
 171         return min(start + __ffs(ext2_swab(tmp)), nbits);
 172 }
 173 #endif
 174
 175 #ifndef find_next_zero_bit_le
 176 unsigned long find_next_zero_bit_le(const void *addr, unsigned
 177                 long size, unsigned long offset)
 178 {
 179         return _find_next_bit_le(addr, size, offset, ~0UL);
 180 }
 181 EXPORT_SYMBOL(find_next_zero_bit_le);
 182 #endif
 183
 184 #ifndef find_next_bit_le
 185 unsigned long find_next_bit_le(const void *addr, unsigned
 186                 long size, unsigned long offset)
 187 {
 188         return _find_next_bit_le(addr, size, offset, 0UL);
 189 }
 190 EXPORT_SYMBOL(find_next_bit_le);
 191 #endif
 192
 193 #endif /* __BIG_ENDIAN */