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 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         (void) le;
  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
  49         /*
  50          * Due to the lack of swab() in tools, and the fact that it doesn't
  51          * need little-endian support, just comment it out
  52          */
  53 #if (0)
  54         if (le)
  55                 mask = swab(mask);
  56 #endif
  57
  58         tmp &= mask;
  59
  60         start = round_down(start, BITS_PER_LONG);
  61
  62         while (!tmp) {
  63                 start += BITS_PER_LONG;
  64                 if (start >= nbits)
  65                         return nbits;
  66
  67                 tmp = addr1[start / BITS_PER_LONG];
  68                 if (addr2)
  69                         tmp &= addr2[start / BITS_PER_LONG];
  70                 tmp ^= invert;
  71         }
  72
  73 #if (0)
  74         if (le)
  75                 tmp = swab(tmp);
  76 #endif
  77
  78         return min(start + __ffs(tmp), nbits);
  79 }
  80 #endif
  81
  82 #ifndef find_first_bit
  83 /*
  84  * Find the first set bit in a memory region.
  85  */
  86 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
  87 {
  88         unsigned long idx;
  89
  90         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  91                 if (addr[idx])
  92                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  93         }
  94
  95         return size;
  96 }
  97 #endif
  98
  99 #ifndef find_first_and_bit
 100 /*
 101  * Find the first set bit in two memory regions.
 102  */
 103 unsigned long _find_first_and_bit(const unsigned long *addr1,
 104                                   const unsigned long *addr2,
 105                                   unsigned long size)
 106 {
 107         unsigned long idx, val;
 108
 109         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 110                 val = addr1[idx] & addr2[idx];
 111                 if (val)
 112                         return min(idx * BITS_PER_LONG + __ffs(val), size);
 113         }
 114
 115         return size;
 116 }
 117 #endif
 118
 119 #ifndef find_first_zero_bit
 120 /*
 121  * Find the first cleared bit in a memory region.
 122  */
 123 unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
 124 {
 125         unsigned long idx;
 126
 127         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 128                 if (addr[idx] != ~0UL)
 129                         return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
 130         }
 131
 132         return size;
 133 }
 134 #endif