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 | /* |
22 | * Common helper for find_bit() function family |
23 | * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) |
24 | * @MUNGE: The expression that post-processes a word containing found bit (may be empty) |
25 | * @size: The bitmap size in bits |
26 | */ |
27 | #define FIND_FIRST_BIT(FETCH, MUNGE, size) \ |
28 | ({ \ |
29 | unsigned long idx, val, sz = (size); \ |
30 | \ |
31 | for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \ |
32 | val = (FETCH); \ |
33 | if (val) { \ |
34 | sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \ |
35 | break; \ |
36 | } \ |
37 | } \ |
38 | \ |
39 | sz; \ |
40 | }) |
41 | |
42 | /* |
43 | * Common helper for find_next_bit() function family |
44 | * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) |
45 | * @MUNGE: The expression that post-processes a word containing found bit (may be empty) |
46 | * @size: The bitmap size in bits |
47 | * @start: The bitnumber to start searching at |
48 | */ |
49 | #define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \ |
50 | ({ \ |
51 | unsigned long mask, idx, tmp, sz = (size), __start = (start); \ |
52 | \ |
53 | if (unlikely(__start >= sz)) \ |
54 | goto out; \ |
55 | \ |
56 | mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \ |
57 | idx = __start / BITS_PER_LONG; \ |
58 | \ |
59 | for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \ |
60 | if ((idx + 1) * BITS_PER_LONG >= sz) \ |
61 | goto out; \ |
62 | idx++; \ |
63 | } \ |
64 | \ |
65 | sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \ |
66 | out: \ |
67 | sz; \ |
68 | }) |
69 | |
70 | #ifndef find_first_bit |
71 | /* |
72 | * Find the first set bit in a memory region. |
73 | */ |
74 | unsigned long _find_first_bit(const unsigned long *addr, unsigned long size) |
75 | { |
76 | return FIND_FIRST_BIT(addr[idx], /* nop */, size); |
77 | } |
78 | #endif |
79 | |
80 | #ifndef find_first_and_bit |
81 | /* |
82 | * Find the first set bit in two memory regions. |
83 | */ |
84 | unsigned long _find_first_and_bit(const unsigned long *addr1, |
85 | const unsigned long *addr2, |
86 | unsigned long size) |
87 | { |
88 | return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size); |
89 | } |
90 | #endif |
91 | |
92 | #ifndef find_first_zero_bit |
93 | /* |
94 | * Find the first cleared bit in a memory region. |
95 | */ |
96 | unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size) |
97 | { |
98 | return FIND_FIRST_BIT(~addr[idx], /* nop */, size); |
99 | } |
100 | #endif |
101 | |
102 | #ifndef find_next_bit |
103 | unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start) |
104 | { |
105 | return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start); |
106 | } |
107 | #endif |
108 | |
109 | #ifndef find_next_and_bit |
110 | unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, |
111 | unsigned long nbits, unsigned long start) |
112 | { |
113 | return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start); |
114 | } |
115 | #endif |
116 | |
117 | #ifndef find_next_zero_bit |
118 | unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, |
119 | unsigned long start) |
120 | { |
121 | return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start); |
122 | } |
123 | #endif |
124 | |