Commit | Line | Data |
---|---|---|
2874c5fd | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
64af4e0d | 2 | /* bit search implementation |
23e1a358 | 3 | * |
64af4e0d | 4 | * Copied from lib/find_bit.c to tools/lib/find_bit.c |
23e1a358 ACM |
5 | * |
6 | * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. | |
7 | * Written by David Howells (dhowells@redhat.com) | |
8 | * | |
64af4e0d ACM |
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. | |
23e1a358 ACM |
15 | */ |
16 | ||
17 | #include <linux/bitops.h> | |
64af4e0d ACM |
18 | #include <linux/bitmap.h> |
19 | #include <linux/kernel.h> | |
23e1a358 | 20 | |
23e1a358 | 21 | /* |
6333cb31 YN |
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 | |
23e1a358 | 26 | */ |
6333cb31 YN |
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 | }) | |
ea81c1ef | 41 | |
6333cb31 YN |
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 | }) | |
23e1a358 ACM |
69 | |
70 | #ifndef find_first_bit | |
71 | /* | |
72 | * Find the first set bit in a memory region. | |
73 | */ | |
eaae7841 | 74 | unsigned long _find_first_bit(const unsigned long *addr, unsigned long size) |
23e1a358 | 75 | { |
6333cb31 | 76 | return FIND_FIRST_BIT(addr[idx], /* nop */, size); |
23e1a358 ACM |
77 | } |
78 | #endif | |
02bc11de | 79 | |
4ade0818 YN |
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 | { | |
6333cb31 | 88 | return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size); |
4ade0818 YN |
89 | } |
90 | #endif | |
91 | ||
02bc11de JO |
92 | #ifndef find_first_zero_bit |
93 | /* | |
94 | * Find the first cleared bit in a memory region. | |
95 | */ | |
eaae7841 | 96 | unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size) |
02bc11de | 97 | { |
6333cb31 YN |
98 | return FIND_FIRST_BIT(~addr[idx], /* nop */, size); |
99 | } | |
100 | #endif | |
02bc11de | 101 | |
6333cb31 YN |
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 | |
02bc11de | 108 | |
6333cb31 YN |
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); | |
02bc11de JO |
122 | } |
123 | #endif |