1// SPDX-License-Identifier: GPL-2.0+
2#ifndef __LINUX_BITMAP_H
3#define __LINUX_BITMAP_H
4
5#include <asm/types.h>
6#include <linux/types.h>
7#include <linux/bitops.h>
8#include <linux/string.h>
9
10#ifdef __LITTLE_ENDIAN
11#define BITMAP_MEM_ALIGNMENT 8
12#else
13#define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
14#endif
15#define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
16
17#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
18#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
19#define small_const_nbits(nbits) \
20	(__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
21
22static inline void
23__bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
24	    const unsigned long *bitmap2, unsigned int bits)
25{
26	unsigned int k;
27	unsigned int nr = BITS_TO_LONGS(bits);
28
29	for (k = 0; k < nr; k++)
30		dst[k] = bitmap1[k] | bitmap2[k];
31}
32
33static inline int
34__bitmap_weight(const unsigned long *bitmap, unsigned int bits)
35{
36	unsigned int k, lim = bits / BITS_PER_LONG;
37	int w = 0;
38
39	for (k = 0; k < lim; k++)
40		w += hweight_long(bitmap[k]);
41
42	if (bits % BITS_PER_LONG)
43		w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
44
45	return w;
46}
47
48static inline void
49__bitmap_set(unsigned long *map, unsigned int start, int len)
50{
51	unsigned long *p = map + BIT_WORD(start);
52	const unsigned int size = start + len;
53	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
54	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
55
56	while (len - bits_to_set >= 0) {
57		*p |= mask_to_set;
58		len -= bits_to_set;
59		bits_to_set = BITS_PER_LONG;
60		mask_to_set = ~0UL;
61		p++;
62	}
63	if (len) {
64		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
65		*p |= mask_to_set;
66	}
67}
68
69static inline void
70__bitmap_clear(unsigned long *map, unsigned int start, int len)
71{
72	unsigned long *p = map + BIT_WORD(start);
73	const unsigned int size = start + len;
74	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
75	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
76
77	while (len - bits_to_clear >= 0) {
78		*p &= ~mask_to_clear;
79		len -= bits_to_clear;
80		bits_to_clear = BITS_PER_LONG;
81		mask_to_clear = ~0UL;
82		p++;
83	}
84	if (len) {
85		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
86		*p &= ~mask_to_clear;
87	}
88}
89
90static inline void bitmap_zero(unsigned long *dst, int nbits)
91{
92	if (small_const_nbits(nbits)) {
93		*dst = 0UL;
94	} else {
95		int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
96
97		memset(dst, 0, len);
98	}
99}
100
101static inline unsigned long
102find_next_bit(const unsigned long *addr, unsigned long size,
103	      unsigned long offset)
104{
105	const unsigned long *p = addr + BIT_WORD(offset);
106	unsigned long result = offset & ~(BITS_PER_LONG - 1);
107	unsigned long tmp;
108
109	if (offset >= size)
110		return size;
111	size -= result;
112	offset %= BITS_PER_LONG;
113	if (offset) {
114		tmp = *(p++);
115		tmp &= (~0UL << offset);
116		if (size < BITS_PER_LONG)
117			goto found_first;
118		if (tmp)
119			goto found_middle;
120		size -= BITS_PER_LONG;
121		result += BITS_PER_LONG;
122	}
123	while (size & ~(BITS_PER_LONG - 1)) {
124		tmp = *(p++);
125		if ((tmp))
126			goto found_middle;
127		result += BITS_PER_LONG;
128		size -= BITS_PER_LONG;
129	}
130	if (!size)
131		return result;
132	tmp = *p;
133
134found_first:
135	tmp &= (~0UL >> (BITS_PER_LONG - size));
136	if (tmp == 0UL)		/* Are any bits set? */
137		return result + size;	/* Nope. */
138found_middle:
139	return result + __ffs(tmp);
140}
141
142/*
143 * Find the first set bit in a memory region.
144 */
145static inline unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
146{
147	unsigned long idx;
148
149	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
150		if (addr[idx])
151			return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
152	}
153
154	return size;
155}
156
157#define for_each_set_bit(bit, addr, size) \
158	for ((bit) = find_first_bit((addr), (size));		\
159	     (bit) < (size);					\
160	     (bit) = find_next_bit((addr), (size), (bit) + 1))
161
162static inline unsigned long
163bitmap_find_next_zero_area(unsigned long *map,
164			   unsigned long size,
165			   unsigned long start,
166			   unsigned int nr, unsigned long align_mask)
167{
168	unsigned long index, end, i;
169again:
170	index = find_next_zero_bit(map, size, start);
171
172	/*
173	 * Align allocation
174	 */
175	index = (index + align_mask) & ~align_mask;
176
177	end = index + nr;
178	if (end > size)
179		return end;
180	i = find_next_bit(map, end, index);
181	if (i < end) {
182		start = i + 1;
183		goto again;
184	}
185	return index;
186}
187
188static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
189{
190	if (small_const_nbits(nbits)) {
191		*dst = ~0UL;
192	} else {
193		unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
194
195		memset(dst, 0xff, len);
196	}
197}
198
199static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
200			     const unsigned long *src2, unsigned int nbits)
201{
202	if (small_const_nbits(nbits))
203		*dst = *src1 | *src2;
204	else
205		__bitmap_or(dst, src1, src2, nbits);
206}
207
208static inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
209{
210	if (small_const_nbits(nbits))
211		return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
212	return __bitmap_weight(src, nbits);
213}
214
215static inline void bitmap_set(unsigned long *map, unsigned int start,
216			      unsigned int nbits)
217{
218	if (__builtin_constant_p(nbits) && nbits == 1)
219		__set_bit(start, map);
220	else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
221		 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
222		 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
223		 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
224		memset((char *)map + start / 8, 0xff, nbits / 8);
225	else
226		__bitmap_set(map, start, nbits);
227}
228
229static inline void bitmap_clear(unsigned long *map, unsigned int start,
230				unsigned int nbits)
231{
232	if (__builtin_constant_p(nbits) && nbits == 1)
233		__clear_bit(start, map);
234	else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
235		 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
236		 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
237		 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
238		memset((char *)map + start / 8, 0, nbits / 8);
239	else
240		__bitmap_clear(map, start, nbits);
241}
242
243#endif /* __LINUX_BITMAP_H */
244