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