tools/lib/find_bit.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /* bit search implementation
0003  *
0004  * Copied from lib/find_bit.c to tools/lib/find_bit.c
0005  *
0006  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
0007  * Written by David Howells (dhowells@redhat.com)
0008  *
0009  * Copyright (C) 2008 IBM Corporation
0010  * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
0011  * (Inspired by David Howell's find_next_bit implementation)
0012  *
0013  * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
0014  * size and improve performance, 2015.
0015  */
0016
0017 #include <linux/bitops.h>
0018 #include <linux/bitmap.h>
0019 #include <linux/kernel.h>
0020
0021 #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
0022         !defined(find_next_and_bit)
0023
0024 /*
0025  * This is a common helper function for find_next_bit, find_next_zero_bit, and
0026  * find_next_and_bit. The differences are:
0027  *  - The "invert" argument, which is XORed with each fetched word before
0028  *    searching it for one bits.
0029  *  - The optional "addr2", which is anded with "addr1" if present.
0030  */
0031 unsigned long _find_next_bit(const unsigned long *addr1,
0032         const unsigned long *addr2, unsigned long nbits,
0033         unsigned long start, unsigned long invert, unsigned long le)
0034 {
0035     unsigned long tmp, mask;
0036     (void) le;
0037
0038     if (unlikely(start >= nbits))
0039         return nbits;
0040
0041     tmp = addr1[start / BITS_PER_LONG];
0042     if (addr2)
0043         tmp &= addr2[start / BITS_PER_LONG];
0044     tmp ^= invert;
0045
0046     /* Handle 1st word. */
0047     mask = BITMAP_FIRST_WORD_MASK(start);
0048
0049     /*
0050      * Due to the lack of swab() in tools, and the fact that it doesn't
0051      * need little-endian support, just comment it out
0052      */
0053 #if (0)
0054     if (le)
0055         mask = swab(mask);
0056 #endif
0057
0058     tmp &= mask;
0059
0060     start = round_down(start, BITS_PER_LONG);
0061
0062     while (!tmp) {
0063         start += BITS_PER_LONG;
0064         if (start >= nbits)
0065             return nbits;
0066
0067         tmp = addr1[start / BITS_PER_LONG];
0068         if (addr2)
0069             tmp &= addr2[start / BITS_PER_LONG];
0070         tmp ^= invert;
0071     }
0072
0073 #if (0)
0074     if (le)
0075         tmp = swab(tmp);
0076 #endif
0077
0078     return min(start + __ffs(tmp), nbits);
0079 }
0080 #endif
0081
0082 #ifndef find_first_bit
0083 /*
0084  * Find the first set bit in a memory region.
0085  */
0086 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
0087 {
0088     unsigned long idx;
0089
0090     for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
0091         if (addr[idx])
0092             return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
0093     }
0094
0095     return size;
0096 }
0097 #endif
0098
0099 #ifndef find_first_and_bit
0100 /*
0101  * Find the first set bit in two memory regions.
0102  */
0103 unsigned long _find_first_and_bit(const unsigned long *addr1,
0104                   const unsigned long *addr2,
0105                   unsigned long size)
0106 {
0107     unsigned long idx, val;
0108
0109     for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
0110         val = addr1[idx] & addr2[idx];
0111         if (val)
0112             return min(idx * BITS_PER_LONG + __ffs(val), size);
0113     }
0114
0115     return size;
0116 }
0117 #endif
0118
0119 #ifndef find_first_zero_bit
0120 /*
0121  * Find the first cleared bit in a memory region.
0122  */
0123 unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
0124 {
0125     unsigned long idx;
0126
0127     for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
0128         if (addr[idx] != ~0UL)
0129             return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
0130     }
0131
0132     return size;
0133 }
0134 #endif