lib/find_bit.c

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