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 /*
  22  * Common helper for find_bit() function family
  23  * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
  24  * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
  25  * @size: The bitmap size in bits
  26  */
  27 #define FIND_FIRST_BIT(FETCH, MUNGE, size)                                      \
  28 ({                                                                              \
  29         unsigned long idx, val, sz = (size);                                    \
  30                                                                                 \
  31         for (idx = 0; idx * BITS_PER_LONG < sz; idx++) {                        \
  32                 val = (FETCH);                                                  \
  33                 if (val) {                                                      \
  34                         sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz);  \
  35                         break;                                                  \
  36                 }                                                               \
  37         }                                                                       \
  38                                                                                 \
  39         sz;                                                                     \
  40 })
  41
  42 /*
  43  * Common helper for find_next_bit() function family
  44  * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
  45  * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
  46  * @size: The bitmap size in bits
  47  * @start: The bitnumber to start searching at
  48  */
  49 #define FIND_NEXT_BIT(FETCH, MUNGE, size, start)                                \
  50 ({                                                                              \
  51         unsigned long mask, idx, tmp, sz = (size), __start = (start);           \
  52                                                                                 \
  53         if (unlikely(__start >= sz))                                            \
  54                 goto out;                                                       \
  55                                                                                 \
  56         mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start));                          \
  57         idx = __start / BITS_PER_LONG;                                          \
  58                                                                                 \
  59         for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) {                       \
  60                 if ((idx + 1) * BITS_PER_LONG >= sz)                            \
  61                         goto out;                                               \
  62                 idx++;                                                          \
  63         }                                                                       \
  64                                                                                 \
  65         sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz);                  \
  66 out:                                                                            \
  67         sz;                                                                     \
  68 })
  69
  70 #ifndef find_first_bit
  71 /*
  72  * Find the first set bit in a memory region.
  73  */
  74 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
  75 {
  76         return FIND_FIRST_BIT(addr[idx], /* nop */, size);
  77 }
  78 #endif
  79
  80 #ifndef find_first_and_bit
  81 /*
  82  * Find the first set bit in two memory regions.
  83  */
  84 unsigned long _find_first_and_bit(const unsigned long *addr1,
  85                                   const unsigned long *addr2,
  86                                   unsigned long size)
  87 {
  88         return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, 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         return FIND_FIRST_BIT(~addr[idx], /* nop */, size);
  99 }
 100 #endif
 101
 102 #ifndef find_next_bit
 103 unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start)
 104 {
 105         return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start);
 106 }
 107 #endif
 108
 109 #ifndef find_next_and_bit
 110 unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
 111                                         unsigned long nbits, unsigned long start)
 112 {
 113         return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start);
 114 }
 115 #endif
 116
 117 #ifndef find_next_zero_bit
 118 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
 119                                          unsigned long start)
 120 {
 121         return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
 122 }
 123 #endif