^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-or-later
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /* bit search implementation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * Copied from lib/find_bit.c to tools/lib/find_bit.c
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * Written by David Howells (dhowells@redhat.com)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * Copyright (C) 2008 IBM Corporation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * (Inspired by David Howell's find_next_bit implementation)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * size and improve performance, 2015.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) #include <linux/bitops.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) #include <linux/bitmap.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) !defined(find_next_and_bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) * This is a common helper function for find_next_bit, find_next_zero_bit, and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * find_next_and_bit. The differences are:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * - The "invert" argument, which is XORed with each fetched word before
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * searching it for one bits.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) * - The optional "addr2", which is anded with "addr1" if present.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) static inline unsigned long _find_next_bit(const unsigned long *addr1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) const unsigned long *addr2, unsigned long nbits,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) unsigned long start, unsigned long invert)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) unsigned long tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) if (unlikely(start >= nbits))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) return nbits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) tmp = addr1[start / BITS_PER_LONG];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) if (addr2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) tmp &= addr2[start / BITS_PER_LONG];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) tmp ^= invert;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) /* Handle 1st word. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) tmp &= BITMAP_FIRST_WORD_MASK(start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) start = round_down(start, BITS_PER_LONG);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) while (!tmp) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) start += BITS_PER_LONG;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) if (start >= nbits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) return nbits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) tmp = addr1[start / BITS_PER_LONG];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) if (addr2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) tmp &= addr2[start / BITS_PER_LONG];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) tmp ^= invert;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) return min(start + __ffs(tmp), nbits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) #ifndef find_next_bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) * Find the next set bit in a memory region.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) unsigned long offset)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) return _find_next_bit(addr, NULL, size, offset, 0UL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) #ifndef find_first_bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) * Find the first set bit in a memory region.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) unsigned long idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) if (addr[idx])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) return size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) #ifndef find_first_zero_bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) * Find the first cleared bit in a memory region.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) unsigned long idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) if (addr[idx] != ~0UL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) return size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) #ifndef find_next_zero_bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) unsigned long offset)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) return _find_next_bit(addr, NULL, size, offset, ~0UL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) #ifndef find_next_and_bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) unsigned long find_next_and_bit(const unsigned long *addr1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) const unsigned long *addr2, unsigned long size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) unsigned long offset)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) return _find_next_bit(addr1, addr2, size, offset, 0UL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) #endif
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags