^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) * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Written by David Howells (dhowells@redhat.com)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * Copyright (C) 2008 IBM Corporation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * (Inspired by David Howell's find_next_bit implementation)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * size and improve performance, 2015.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) #include <linux/bitops.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) #include <linux/bitmap.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) #include <linux/export.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) #include <linux/minmax.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_bit_le) || !defined(find_next_zero_bit_le) || \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) !defined(find_next_and_bit)
^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 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, unsigned long le)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) unsigned long tmp, mask;
^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) mask = BITMAP_FIRST_WORD_MASK(start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) if (le)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) mask = swab(mask);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) tmp &= mask;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) start = round_down(start, BITS_PER_LONG);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) while (!tmp) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) start += BITS_PER_LONG;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) if (start >= nbits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) return nbits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) tmp = addr1[start / BITS_PER_LONG];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) if (addr2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) tmp &= addr2[start / BITS_PER_LONG];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) tmp ^= invert;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) if (le)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) tmp = swab(tmp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) return min(start + __ffs(tmp), nbits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) #ifndef find_next_bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) * Find the next set bit in a memory region.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) unsigned long offset)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) EXPORT_SYMBOL(find_next_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) #ifndef find_next_zero_bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) unsigned long offset)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) EXPORT_SYMBOL(find_next_zero_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) #if !defined(find_next_and_bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) unsigned long find_next_and_bit(const unsigned long *addr1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) const unsigned long *addr2, unsigned long size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) unsigned long offset)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) EXPORT_SYMBOL(find_next_and_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) #ifndef find_first_bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) * Find the first set bit in a memory region.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) unsigned long idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) if (addr[idx])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) return size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) EXPORT_SYMBOL(find_first_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) #ifndef find_first_zero_bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) * Find the first cleared bit in a memory region.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) unsigned long idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) if (addr[idx] != ~0UL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) return size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) EXPORT_SYMBOL(find_first_zero_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) #ifndef find_last_bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) if (size) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) unsigned long val = BITMAP_LAST_WORD_MASK(size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) unsigned long idx = (size-1) / BITS_PER_LONG;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) val &= addr[idx];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) if (val)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) return idx * BITS_PER_LONG + __fls(val);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) val = ~0ul;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) } while (idx--);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) return size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) EXPORT_SYMBOL(find_last_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) #ifdef __BIG_ENDIAN
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) #ifndef find_next_zero_bit_le
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) unsigned long find_next_zero_bit_le(const void *addr, unsigned
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) long size, unsigned long offset)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) EXPORT_SYMBOL(find_next_zero_bit_le);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) #ifndef find_next_bit_le
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) unsigned long find_next_bit_le(const void *addr, unsigned
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) long size, unsigned long offset)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) EXPORT_SYMBOL(find_next_bit_le);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) #endif /* __BIG_ENDIAN */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) unsigned long size, unsigned long offset)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) offset = find_next_bit(addr, size, offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) if (offset == size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) return size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) offset = round_down(offset, 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) *clump = bitmap_get_value8(addr, offset);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) return offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) EXPORT_SYMBOL(find_next_clump8);
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags