tools/lib/find_bit.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /* bit search implementation
   3  *
   4  * Copied from lib/find_bit.c to tools/lib/find_bit.c
   5  *
   6  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
   7  * Written by David Howells (dhowells@redhat.com)
   8  *
   9  * Copyright (C) 2008 IBM Corporation
  10  * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
  11  * (Inspired by David Howell's find_next_bit implementation)
  12  *
  13  * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
  14  * size and improve performance, 2015.
  15  */
  16
  17 #include <linux/bitops.h>
  18 #include <linux/bitmap.h>
  19 #include <linux/kernel.h>
  20
  21 #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
  22                 !defined(find_next_and_bit)
  23
  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 inline unsigned long _find_next_bit(const unsigned long *addr1,
  32                 const unsigned long *addr2, unsigned long nbits,
  33                 unsigned long start, unsigned long invert)
  34 {
  35         unsigned long tmp;
  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         tmp &= BITMAP_FIRST_WORD_MASK(start);
  47         start = round_down(start, BITS_PER_LONG);
  48
  49         while (!tmp) {
  50                 start += BITS_PER_LONG;
  51                 if (start >= nbits)
  52                         return nbits;
  53
  54                 tmp = addr1[start / BITS_PER_LONG];
  55                 if (addr2)
  56                         tmp &= addr2[start / BITS_PER_LONG];
  57                 tmp ^= invert;
  58         }
  59
  60         return min(start + __ffs(tmp), nbits);
  61 }
  62 #endif
  63
  64 #ifndef find_next_bit
  65 /*
  66  * Find the next set bit in a memory region.
  67  */
  68 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  69                             unsigned long offset)
  70 {
  71         return _find_next_bit(addr, NULL, size, offset, 0UL);
  72 }
  73 #endif
  74
  75 #ifndef find_first_bit
  76 /*
  77  * Find the first set bit in a memory region.
  78  */
  79 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  80 {
  81         unsigned long idx;
  82
  83         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  84                 if (addr[idx])
  85                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  86         }
  87
  88         return size;
  89 }
  90 #endif
  91
  92 #ifndef find_first_zero_bit
  93 /*
  94  * Find the first cleared bit in a memory region.
  95  */
  96 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
  97 {
  98         unsigned long idx;
  99
 100         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 101                 if (addr[idx] != ~0UL)
 102                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
 103         }
 104
 105         return size;
 106 }
 107 #endif
 108
 109 #ifndef find_next_zero_bit
 110 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
 111                                  unsigned long offset)
 112 {
 113         return _find_next_bit(addr, NULL, size, offset, ~0UL);
 114 }
 115 #endif
 116
 117 #ifndef find_next_and_bit
 118 unsigned long find_next_and_bit(const unsigned long *addr1,
 119                 const unsigned long *addr2, unsigned long size,
 120                 unsigned long offset)
 121 {
 122         return _find_next_bit(addr1, addr2, size, offset, 0UL);
 123 }
 124 #endif