1 /* SPDX-License-Identifier: BSD-3-Clause */
2 /* Copyright (c) 2020, Intel Corporation
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
8 * 1. Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the Intel Corporation nor the names of its
16 * contributors may be used to endorse or promote products derived from
17 * this software without specific prior written permission.
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
33 #ifndef _ICE_BITOPS_H_
34 #define _ICE_BITOPS_H_
36 /* Define the size of the bitmap chunk */
37 typedef u32 ice_bitmap_t;
39 /* Number of bits per bitmap chunk */
40 #define BITS_PER_CHUNK (BITS_PER_BYTE * sizeof(ice_bitmap_t))
41 /* Determine which chunk a bit belongs in */
42 #define BIT_CHUNK(nr) ((nr) / BITS_PER_CHUNK)
43 /* How many chunks are required to store this many bits */
44 #define BITS_TO_CHUNKS(sz) DIVIDE_AND_ROUND_UP((sz), BITS_PER_CHUNK)
45 /* Which bit inside a chunk this bit corresponds to */
46 #define BIT_IN_CHUNK(nr) ((nr) % BITS_PER_CHUNK)
47 /* How many bits are valid in the last chunk, assumes nr > 0 */
48 #define LAST_CHUNK_BITS(nr) ((((nr) - 1) % BITS_PER_CHUNK) + 1)
49 /* Generate a bitmask of valid bits in the last chunk, assumes nr > 0 */
50 #define LAST_CHUNK_MASK(nr) (((ice_bitmap_t)~0) >> \
51 (BITS_PER_CHUNK - LAST_CHUNK_BITS(nr)))
53 #define ice_declare_bitmap(A, sz) \
54 ice_bitmap_t A[BITS_TO_CHUNKS(sz)]
56 static inline bool ice_is_bit_set_internal(u16 nr, const ice_bitmap_t *bitmap)
58 return !!(*bitmap & BIT(nr));
62 * If atomic version of the bitops are required, each specific OS
63 * implementation will need to implement OS/platform specific atomic
64 * version of the functions below:
66 * ice_clear_bit_internal
67 * ice_set_bit_internal
68 * ice_test_and_clear_bit_internal
69 * ice_test_and_set_bit_internal
71 * and define macro ICE_ATOMIC_BITOPS to overwrite the default non-atomic
74 static inline void ice_clear_bit_internal(u16 nr, ice_bitmap_t *bitmap)
79 static inline void ice_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
84 static inline bool ice_test_and_clear_bit_internal(u16 nr,
87 if (ice_is_bit_set_internal(nr, bitmap)) {
88 ice_clear_bit_internal(nr, bitmap);
94 static inline bool ice_test_and_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
96 if (ice_is_bit_set_internal(nr, bitmap))
99 ice_set_bit_internal(nr, bitmap);
104 * ice_is_bit_set - Check state of a bit in a bitmap
105 * @bitmap: the bitmap to check
106 * @nr: the bit to check
108 * Returns true if bit nr of bitmap is set. False otherwise. Assumes that nr
109 * is less than the size of the bitmap.
111 static inline bool ice_is_bit_set(const ice_bitmap_t *bitmap, u16 nr)
113 return ice_is_bit_set_internal(BIT_IN_CHUNK(nr),
114 &bitmap[BIT_CHUNK(nr)]);
118 * ice_clear_bit - Clear a bit in a bitmap
119 * @bitmap: the bitmap to change
120 * @nr: the bit to change
122 * Clears the bit nr in bitmap. Assumes that nr is less than the size of the
125 static inline void ice_clear_bit(u16 nr, ice_bitmap_t *bitmap)
127 ice_clear_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
131 * ice_set_bit - Set a bit in a bitmap
132 * @bitmap: the bitmap to change
133 * @nr: the bit to change
135 * Sets the bit nr in bitmap. Assumes that nr is less than the size of the
138 static inline void ice_set_bit(u16 nr, ice_bitmap_t *bitmap)
140 ice_set_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
144 * ice_test_and_clear_bit - Atomically clear a bit and return the old bit value
145 * @nr: the bit to change
146 * @bitmap: the bitmap to change
148 * Check and clear the bit nr in bitmap. Assumes that nr is less than the size
152 ice_test_and_clear_bit(u16 nr, ice_bitmap_t *bitmap)
154 return ice_test_and_clear_bit_internal(BIT_IN_CHUNK(nr),
155 &bitmap[BIT_CHUNK(nr)]);
159 * ice_test_and_set_bit - Atomically set a bit and return the old bit value
160 * @nr: the bit to change
161 * @bitmap: the bitmap to change
163 * Check and set the bit nr in bitmap. Assumes that nr is less than the size of
167 ice_test_and_set_bit(u16 nr, ice_bitmap_t *bitmap)
169 return ice_test_and_set_bit_internal(BIT_IN_CHUNK(nr),
170 &bitmap[BIT_CHUNK(nr)]);
173 /* ice_zero_bitmap - set bits of bitmap to zero.
174 * @bmp: bitmap to set zeros
175 * @size: Size of the bitmaps in bits
177 * Set all of the bits in a bitmap to zero. Note that this function assumes it
178 * operates on an ice_bitmap_t which was declared using ice_declare_bitmap. It
179 * will zero every bit in the last chunk, even if those bits are beyond the
182 static inline void ice_zero_bitmap(ice_bitmap_t *bmp, u16 size)
184 ice_memset(bmp, 0, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
189 * ice_and_bitmap - bitwise AND 2 bitmaps and store result in dst bitmap
190 * @dst: Destination bitmap that receive the result of the operation
191 * @bmp1: The first bitmap to intersect
192 * @bmp2: The second bitmap to intersect wit the first
193 * @size: Size of the bitmaps in bits
195 * This function performs a bitwise AND on two "source" bitmaps of the same size
196 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
197 * size as the "source" bitmaps to avoid buffer overflows. This function returns
198 * a non-zero value if at least one bit location from both "source" bitmaps is
202 ice_and_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
203 const ice_bitmap_t *bmp2, u16 size)
205 ice_bitmap_t res = 0, mask;
208 /* Handle all but the last chunk */
209 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++) {
210 dst[i] = bmp1[i] & bmp2[i];
214 /* We want to take care not to modify any bits outside of the bitmap
215 * size, even in the destination bitmap. Thus, we won't directly
216 * assign the last bitmap, but instead use a bitmask to ensure we only
217 * modify bits which are within the size, and leave any bits above the
220 mask = LAST_CHUNK_MASK(size);
221 dst[i] = (dst[i] & ~mask) | ((bmp1[i] & bmp2[i]) & mask);
222 res |= dst[i] & mask;
228 * ice_or_bitmap - bitwise OR 2 bitmaps and store result in dst bitmap
229 * @dst: Destination bitmap that receive the result of the operation
230 * @bmp1: The first bitmap to intersect
231 * @bmp2: The second bitmap to intersect wit the first
232 * @size: Size of the bitmaps in bits
234 * This function performs a bitwise OR on two "source" bitmaps of the same size
235 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
236 * size as the "source" bitmaps to avoid buffer overflows.
239 ice_or_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
240 const ice_bitmap_t *bmp2, u16 size)
245 /* Handle all but last chunk */
246 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
247 dst[i] = bmp1[i] | bmp2[i];
249 /* We want to only OR bits within the size. Furthermore, we also do
250 * not want to modify destination bits which are beyond the specified
251 * size. Use a bitmask to ensure that we only modify the bits that are
252 * within the specified size.
254 mask = LAST_CHUNK_MASK(size);
255 dst[i] = (dst[i] & ~mask) | ((bmp1[i] | bmp2[i]) & mask);
259 * ice_xor_bitmap - bitwise XOR 2 bitmaps and store result in dst bitmap
260 * @dst: Destination bitmap that receive the result of the operation
261 * @bmp1: The first bitmap of XOR operation
262 * @bmp2: The second bitmap to XOR with the first
263 * @size: Size of the bitmaps in bits
265 * This function performs a bitwise XOR on two "source" bitmaps of the same size
266 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
267 * size as the "source" bitmaps to avoid buffer overflows.
270 ice_xor_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
271 const ice_bitmap_t *bmp2, u16 size)
276 /* Handle all but last chunk */
277 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
278 dst[i] = bmp1[i] ^ bmp2[i];
280 /* We want to only XOR bits within the size. Furthermore, we also do
281 * not want to modify destination bits which are beyond the specified
282 * size. Use a bitmask to ensure that we only modify the bits that are
283 * within the specified size.
285 mask = LAST_CHUNK_MASK(size);
286 dst[i] = (dst[i] & ~mask) | ((bmp1[i] ^ bmp2[i]) & mask);
290 * ice_andnot_bitmap - bitwise ANDNOT 2 bitmaps and result in dst bitmap
291 * @dst: Destination bitmap that receive the result of the operation
292 * @bmp1: The first bitmap of ANDNOT operation
293 * @bmp2: The second bitmap to ANDNOT operation
294 * @size: Size of the bitmaps in bits
296 * This function performs a bitwise ANDNOT on two "source" bitmaps of the same
297 * size, and stores the result to "dst" bitmap. The "dst" bitmap must be of the
298 * same size as the "source" bitmaps to avoid buffer overflows.
301 ice_andnot_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
302 const ice_bitmap_t *bmp2, u16 size)
307 /* Handle all but last chunk */
308 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
309 dst[i] = bmp1[i] & ~bmp2[i];
311 /* We want to only clear bits within the size. Furthermore, we also do
312 * not want to modify destination bits which are beyond the specified
313 * size. Use a bitmask to ensure that we only modify the bits that are
314 * within the specified size.
316 mask = LAST_CHUNK_MASK(size);
317 dst[i] = (dst[i] & ~mask) | ((bmp1[i] & ~bmp2[i]) & mask);
321 * ice_find_next_bit - Find the index of the next set bit of a bitmap
322 * @bitmap: the bitmap to scan
323 * @size: the size in bits of the bitmap
324 * @offset: the offset to start at
326 * Scans the bitmap and returns the index of the first set bit which is equal
327 * to or after the specified offset. Will return size if no bits are set.
330 ice_find_next_bit(const ice_bitmap_t *bitmap, u16 size, u16 offset)
337 /* Since the starting position may not be directly on a chunk
338 * boundary, we need to be careful to handle the first chunk specially
340 i = BIT_CHUNK(offset);
341 if (bitmap[i] != 0) {
342 u16 off = i * BITS_PER_CHUNK;
344 for (j = offset % BITS_PER_CHUNK; j < BITS_PER_CHUNK; j++) {
345 if (ice_is_bit_set(bitmap, off + j))
346 return min(size, (u16)(off + j));
350 /* Now we handle the remaining chunks, if any */
351 for (i++; i < BITS_TO_CHUNKS(size); i++) {
352 if (bitmap[i] != 0) {
353 u16 off = i * BITS_PER_CHUNK;
355 for (j = 0; j < BITS_PER_CHUNK; j++) {
356 if (ice_is_bit_set(bitmap, off + j))
357 return min(size, (u16)(off + j));
365 * ice_find_first_bit - Find the index of the first set bit of a bitmap
366 * @bitmap: the bitmap to scan
367 * @size: the size in bits of the bitmap
369 * Scans the bitmap and returns the index of the first set bit. Will return
370 * size if no bits are set.
372 static inline u16 ice_find_first_bit(const ice_bitmap_t *bitmap, u16 size)
374 return ice_find_next_bit(bitmap, size, 0);
377 #define ice_for_each_set_bit(_bitpos, _addr, _maxlen) \
378 for ((_bitpos) = ice_find_first_bit((_addr), (_maxlen)); \
379 (_bitpos) < (_maxlen); \
380 (_bitpos) = ice_find_next_bit((_addr), (_maxlen), (_bitpos) + 1))
383 * ice_is_any_bit_set - Return true of any bit in the bitmap is set
384 * @bitmap: the bitmap to check
385 * @size: the size of the bitmap
387 * Equivalent to checking if ice_find_first_bit returns a value less than the
390 static inline bool ice_is_any_bit_set(ice_bitmap_t *bitmap, u16 size)
392 return ice_find_first_bit(bitmap, size) < size;
396 * ice_cp_bitmap - copy bitmaps.
397 * @dst: bitmap destination
398 * @src: bitmap to copy from
399 * @size: Size of the bitmaps in bits
401 * This function copy bitmap from src to dst. Note that this function assumes
402 * it is operating on a bitmap declared using ice_declare_bitmap. It will copy
403 * the entire last chunk even if this contains bits beyond the size.
405 static inline void ice_cp_bitmap(ice_bitmap_t *dst, ice_bitmap_t *src, u16 size)
407 ice_memcpy(dst, src, BITS_TO_CHUNKS(size) * sizeof(ice_bitmap_t),
408 ICE_NONDMA_TO_NONDMA);
412 * ice_bitmap_set - set a number of bits in bitmap from a starting position
413 * @dst: bitmap destination
414 * @pos: first bit position to set
415 * @num_bits: number of bits to set
417 * This function sets bits in a bitmap from pos to (pos + num_bits) - 1.
418 * Note that this function assumes it is operating on a bitmap declared using
419 * ice_declare_bitmap.
422 ice_bitmap_set(ice_bitmap_t *dst, u16 pos, u16 num_bits)
426 for (i = pos; i < num_bits; i++)
431 * ice_bitmap_hweight - hamming weight of bitmap
432 * @bm: bitmap pointer
433 * @size: size of bitmap (in bits)
435 * This function determines the number of set bits in a bitmap.
436 * Note that this function assumes it is operating on a bitmap declared using
437 * ice_declare_bitmap.
440 ice_bitmap_hweight(ice_bitmap_t *bm, u16 size)
445 while (size > (bit = ice_find_next_bit(bm, size, bit))) {
454 * ice_cmp_bitmaps - compares two bitmaps.
455 * @bmp1: the bitmap to compare
456 * @bmp2: the bitmap to compare with bmp1
457 * @size: Size of the bitmaps in bits
459 * This function compares two bitmaps, and returns result as true or false.
462 ice_cmp_bitmap(ice_bitmap_t *bmp1, ice_bitmap_t *bmp2, u16 size)
467 /* Handle all but last chunk */
468 for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
469 if (bmp1[i] != bmp2[i])
472 /* We want to only compare bits within the size */
473 mask = LAST_CHUNK_MASK(size);
474 if ((bmp1[i] & mask) != (bmp2[i] & mask))
482 #undef LAST_CHUNK_BITS
483 #undef LAST_CHUNK_MASK
485 #endif /* _ICE_BITOPS_H_ */