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