2874c5fd28426 lib/find_bit.c (Thomas Gleixner 2019-05-27 08:55:01 +0200 1) // SPDX-License-Identifier: GPL-2.0-or-later
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 2) /* bit search implementation
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 3) *
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 4) * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 5) * Written by David Howells (dhowells@redhat.com)
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 6) *
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 7) * Copyright (C) 2008 IBM Corporation
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 8) * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 9) * (Inspired by David Howell's find_next_bit implementation)
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 10) *
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 11) * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 12) * size and improve performance, 2015.
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 13) */
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 14)
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 15) #include <linux/bitops.h>
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 16) #include <linux/bitmap.h>
8bc3bcc93a2b4 lib/find_next_bit.c (Paul Gortmaker 2011-11-16 21:29:17 -0500 17) #include <linux/export.h>
aa6159ab99a9a lib/find_bit.c (Andy Shevchenko 2020-12-15 20:42:48 -0800 18) #include <linux/math.h>
b296a6d53339a lib/find_bit.c (Andy Shevchenko 2020-10-15 20:10:21 -0700 19) #include <linux/minmax.h>
aa6159ab99a9a lib/find_bit.c (Andy Shevchenko 2020-12-15 20:42:48 -0800 20) #include <linux/swab.h>
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 21)
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 22) #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 23) !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 24) !defined(find_next_and_bit)
64970b68d2b3e lib/find_next_bit.c (Alexander van Heukelum 2008-03-11 16:17:19 +0100 25) /*
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 26) * This is a common helper function for find_next_bit, find_next_zero_bit, and
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 27) * find_next_and_bit. The differences are:
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 28) * - The "invert" argument, which is XORed with each fetched word before
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 29) * searching it for one bits.
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 30) * - The optional "addr2", which is anded with "addr1" if present.
c7f612cdf091d lib/find_next_bit.c (Akinobu Mita 2006-03-26 01:39:11 -0800 31) */
5c88af59f9abc lib/find_bit.c (Yury Norov 2021-05-06 18:03:03 -0700 32) unsigned long _find_next_bit(const unsigned long *addr1,
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 33) const unsigned long *addr2, unsigned long nbits,
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 34) unsigned long start, unsigned long invert, unsigned long le)
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 35) {
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 36) unsigned long tmp, mask;
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 37)
e4afd2e5567fc lib/find_bit.c (Matthew Wilcox 2017-02-24 15:00:58 -0800 38) if (unlikely(start >= nbits))
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 39) return nbits;
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 40)
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 41) tmp = addr1[start / BITS_PER_LONG];
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 42) if (addr2)
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 43) tmp &= addr2[start / BITS_PER_LONG];
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 44) tmp ^= invert;
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 45)
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 46) /* Handle 1st word. */
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 47) mask = BITMAP_FIRST_WORD_MASK(start);
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 48) if (le)
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 49) mask = swab(mask);
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 50)
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 51) tmp &= mask;
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 52)
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 53) start = round_down(start, BITS_PER_LONG);
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 54)
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 55) while (!tmp) {
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 56) start += BITS_PER_LONG;
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 57) if (start >= nbits)
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 58) return nbits;
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 59)
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 60) tmp = addr1[start / BITS_PER_LONG];
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 61) if (addr2)
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 62) tmp &= addr2[start / BITS_PER_LONG];
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 63) tmp ^= invert;
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 64) }
^1da177e4c3f4 lib/find_next_bit.c (Linus Torvalds 2005-04-16 15:20:36 -0700 65)
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 66) if (le)
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 67) tmp = swab(tmp);
b78c57135d470 lib/find_bit.c (Yury Norov 2020-01-30 22:16:43 -0800 68)
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 69) return min(start + __ffs(tmp), nbits);
c7f612cdf091d lib/find_next_bit.c (Akinobu Mita 2006-03-26 01:39:11 -0800 70) }
5c88af59f9abc lib/find_bit.c (Yury Norov 2021-05-06 18:03:03 -0700 71) EXPORT_SYMBOL(_find_next_bit);
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 72) #endif
0ade34c37012e lib/find_bit.c (Clement Courbet 2018-02-06 15:38:34 -0800 73)
19de85ef574c3 lib/find_next_bit.c (Akinobu Mita 2011-05-26 16:26:09 -0700 74) #ifndef find_first_bit
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 75) /*
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 76) * Find the first set bit in a memory region.
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 77) */
2cc7b6a44ac21 lib/find_bit.c (Yury Norov 2021-05-06 18:03:14 -0700 78) unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 79) {
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 80) unsigned long idx;
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 81)
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 82) for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 83) if (addr[idx])
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 84) return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 85) }
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 86)
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 87) return size;
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 88) }
2cc7b6a44ac21 lib/find_bit.c (Yury Norov 2021-05-06 18:03:14 -0700 89) EXPORT_SYMBOL(_find_first_bit);
19de85ef574c3 lib/find_next_bit.c (Akinobu Mita 2011-05-26 16:26:09 -0700 90) #endif
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 91)
19de85ef574c3 lib/find_next_bit.c (Akinobu Mita 2011-05-26 16:26:09 -0700 92) #ifndef find_first_zero_bit
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 93) /*
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 94) * Find the first cleared bit in a memory region.
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 95) */
2cc7b6a44ac21 lib/find_bit.c (Yury Norov 2021-05-06 18:03:14 -0700 96) unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 97) {
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 98) unsigned long idx;
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 99)
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 100) for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 101) if (addr[idx] != ~0UL)
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 102) return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 103) }
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 104)
2c57a0e233d72 lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:13 -0700 105) return size;
77b9bd9c49442 lib/find_next_bit.c (Alexander van Heukelum 2008-04-01 11:46:19 +0200 106) }
2cc7b6a44ac21 lib/find_bit.c (Yury Norov 2021-05-06 18:03:14 -0700 107) EXPORT_SYMBOL(_find_first_zero_bit);
19de85ef574c3 lib/find_next_bit.c (Akinobu Mita 2011-05-26 16:26:09 -0700 108) #endif
930ae745f5008 lib/find_next_bit.c (Akinobu Mita 2006-03-26 01:39:15 -0800 109)
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 110) #ifndef find_last_bit
2cc7b6a44ac21 lib/find_bit.c (Yury Norov 2021-05-06 18:03:14 -0700 111) unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 112) {
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 113) if (size) {
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 114) unsigned long val = BITMAP_LAST_WORD_MASK(size);
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 115) unsigned long idx = (size-1) / BITS_PER_LONG;
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 116)
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 117) do {
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 118) val &= addr[idx];
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 119) if (val)
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 120) return idx * BITS_PER_LONG + __fls(val);
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 121)
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 122) val = ~0ul;
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 123) } while (idx--);
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 124) }
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 125) return size;
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 126) }
2cc7b6a44ac21 lib/find_bit.c (Yury Norov 2021-05-06 18:03:14 -0700 127) EXPORT_SYMBOL(_find_last_bit);
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 128) #endif
8f6f19dd5143a lib/find_next_bit.c (Yury Norov 2015-04-16 12:43:16 -0700 129)
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 130) unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 131) unsigned long size, unsigned long offset)
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 132) {
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 133) offset = find_next_bit(addr, size, offset);
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 134) if (offset == size)
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 135) return size;
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 136)
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 137) offset = round_down(offset, 8);
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 138) *clump = bitmap_get_value8(addr, offset);
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 139)
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 140) return offset;
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 141) }
169c474fb22d8 lib/find_bit.c (William Breathitt Gray 2019-12-04 16:50:57 -0800 142) EXPORT_SYMBOL(find_next_clump8);
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags