ice/base/ice_bitops.h

/* SPDX-License-Identifier: BSD-3-Clause
 * Copyright(c) 2001-2019
 */

#ifndef _ICE_BITOPS_H_
#define _ICE_BITOPS_H_

/* Define the size of the bitmap chunk */
typedef u32 ice_bitmap_t;


/* Number of bits per bitmap chunk */
#define BITS_PER_CHUNK		(BITS_PER_BYTE * sizeof(ice_bitmap_t))
/* Determine which chunk a bit belongs in */
#define BIT_CHUNK(nr)		((nr) / BITS_PER_CHUNK)
/* How many chunks are required to store this many bits */
#define BITS_TO_CHUNKS(sz)	DIVIDE_AND_ROUND_UP((sz), BITS_PER_CHUNK)
/* Which bit inside a chunk this bit corresponds to */
#define BIT_IN_CHUNK(nr)	((nr) % BITS_PER_CHUNK)
/* How many bits are valid in the last chunk, assumes nr > 0 */
#define LAST_CHUNK_BITS(nr)	((((nr) - 1) % BITS_PER_CHUNK) + 1)
/* Generate a bitmask of valid bits in the last chunk, assumes nr > 0 */
#define LAST_CHUNK_MASK(nr)	(((ice_bitmap_t)~0) >> \
				 (BITS_PER_CHUNK - LAST_CHUNK_BITS(nr)))

#define ice_declare_bitmap(A, sz) \
	ice_bitmap_t A[BITS_TO_CHUNKS(sz)]

static inline bool ice_is_bit_set_internal(u16 nr, const ice_bitmap_t *bitmap)
{
	return !!(*bitmap & BIT(nr));
}

/*
 * If atomic version of the bitops are required, each specific OS
 * implementation will need to implement OS/platform specific atomic
 * version of the functions below:
 *
 * ice_clear_bit_internal
 * ice_set_bit_internal
 * ice_test_and_clear_bit_internal
 * ice_test_and_set_bit_internal
 *
 * and define macro ICE_ATOMIC_BITOPS to overwrite the default non-atomic
 * implementation.
 */
static inline void ice_clear_bit_internal(u16 nr, ice_bitmap_t *bitmap)
{
	*bitmap &= ~BIT(nr);
}

static inline void ice_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
{
	*bitmap |= BIT(nr);
}

static inline bool ice_test_and_clear_bit_internal(u16 nr,
						   ice_bitmap_t *bitmap)
{
	if (ice_is_bit_set_internal(nr, bitmap)) {
		ice_clear_bit_internal(nr, bitmap);
		return true;
	}
	return false;
}

static inline bool ice_test_and_set_bit_internal(u16 nr, ice_bitmap_t *bitmap)
{
	if (ice_is_bit_set_internal(nr, bitmap))
		return true;

	ice_set_bit_internal(nr, bitmap);
	return false;
}

/**
 * ice_is_bit_set - Check state of a bit in a bitmap
 * @bitmap: the bitmap to check
 * @nr: the bit to check
 *
 * Returns true if bit nr of bitmap is set. False otherwise. Assumes that nr
 * is less than the size of the bitmap.
 */
static inline bool ice_is_bit_set(const ice_bitmap_t *bitmap, u16 nr)
{
	return ice_is_bit_set_internal(BIT_IN_CHUNK(nr),
				       &bitmap[BIT_CHUNK(nr)]);
}

/**
 * ice_clear_bit - Clear a bit in a bitmap
 * @bitmap: the bitmap to change
 * @nr: the bit to change
 *
 * Clears the bit nr in bitmap. Assumes that nr is less than the size of the
 * bitmap.
 */
static inline void ice_clear_bit(u16 nr, ice_bitmap_t *bitmap)
{
	ice_clear_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
}

/**
 * ice_set_bit - Set a bit in a bitmap
 * @bitmap: the bitmap to change
 * @nr: the bit to change
 *
 * Sets the bit nr in bitmap. Assumes that nr is less than the size of the
 * bitmap.
 */
static inline void ice_set_bit(u16 nr, ice_bitmap_t *bitmap)
{
	ice_set_bit_internal(BIT_IN_CHUNK(nr), &bitmap[BIT_CHUNK(nr)]);
}

/**
 * ice_test_and_clear_bit - Atomically clear a bit and return the old bit value
 * @nr: the bit to change
 * @bitmap: the bitmap to change
 *
 * Check and clear the bit nr in bitmap. Assumes that nr is less than the size
 * of the bitmap.
 */
static inline bool
ice_test_and_clear_bit(u16 nr, ice_bitmap_t *bitmap)
{
	return ice_test_and_clear_bit_internal(BIT_IN_CHUNK(nr),
					       &bitmap[BIT_CHUNK(nr)]);
}

/**
 * ice_test_and_set_bit - Atomically set a bit and return the old bit value
 * @nr: the bit to change
 * @bitmap: the bitmap to change
 *
 * Check and set the bit nr in bitmap. Assumes that nr is less than the size of
 * the bitmap.
 */
static inline bool
ice_test_and_set_bit(u16 nr, ice_bitmap_t *bitmap)
{
	return ice_test_and_set_bit_internal(BIT_IN_CHUNK(nr),
					     &bitmap[BIT_CHUNK(nr)]);
}

/* ice_zero_bitmap - set bits of bitmap to zero.
 * @bmp: bitmap to set zeros
 * @size: Size of the bitmaps in bits
 *
 * This function sets bits of a bitmap to zero.
 */
static inline void ice_zero_bitmap(ice_bitmap_t *bmp, u16 size)
{
	ice_bitmap_t mask;
	u16 i;

	/* Handle all but last chunk*/
	for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
		bmp[i] = 0;
	/* For the last chunk, we want to take care of not to modify bits
	 * outside the size boundary. ~mask take care of all the bits outside
	 * the boundary.
	 */
	mask = LAST_CHUNK_MASK(size);
	bmp[i] &= ~mask;
}

/**
 * ice_and_bitmap - bitwise AND 2 bitmaps and store result in dst bitmap
 * @dst: Destination bitmap that receive the result of the operation
 * @bmp1: The first bitmap to intersect
 * @bmp2: The second bitmap to intersect wit the first
 * @size: Size of the bitmaps in bits
 *
 * This function performs a bitwise AND on two "source" bitmaps of the same size
 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
 * size as the "source" bitmaps to avoid buffer overflows. This function returns
 * a non-zero value if at least one bit location from both "source" bitmaps is
 * non-zero.
 */
static inline int
ice_and_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
	       const ice_bitmap_t *bmp2, u16 size)
{
	ice_bitmap_t res = 0, mask;
	u16 i;

	/* Handle all but the last chunk */
	for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++) {
		dst[i] = bmp1[i] & bmp2[i];
		res |= dst[i];
	}

	/* We want to take care not to modify any bits outside of the bitmap
	 * size, even in the destination bitmap. Thus, we won't directly
	 * assign the last bitmap, but instead use a bitmask to ensure we only
	 * modify bits which are within the size, and leave any bits above the
	 * size value alone.
	 */
	mask = LAST_CHUNK_MASK(size);
	dst[i] &= ~mask;
	dst[i] |= (bmp1[i] & bmp2[i]) & mask;
	res |= dst[i] & mask;

	return res != 0;
}

/**
 * ice_or_bitmap - bitwise OR 2 bitmaps and store result in dst bitmap
 * @dst: Destination bitmap that receive the result of the operation
 * @bmp1: The first bitmap to intersect
 * @bmp2: The second bitmap to intersect wit the first
 * @size: Size of the bitmaps in bits
 *
 * This function performs a bitwise OR on two "source" bitmaps of the same size
 * and stores the result to "dst" bitmap. The "dst" bitmap must be of the same
 * size as the "source" bitmaps to avoid buffer overflows.
 */
static inline void
ice_or_bitmap(ice_bitmap_t *dst, const ice_bitmap_t *bmp1,
	      const ice_bitmap_t *bmp2, u16 size)
{
	ice_bitmap_t mask;
	u16 i;

	/* Handle all but last chunk*/
	for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
		dst[i] = bmp1[i] | bmp2[i];

	/* We want to only OR bits within the size. Furthermore, we also do
	 * not want to modify destination bits which are beyond the specified
	 * size. Use a bitmask to ensure that we only modify the bits that are
	 * within the specified size.
	 */
	mask = LAST_CHUNK_MASK(size);
	dst[i] &= ~mask;
	dst[i] |= (bmp1[i] | bmp2[i]) & mask;
}

/**
 * ice_find_next_bit - Find the index of the next set bit of a bitmap
 * @bitmap: the bitmap to scan
 * @size: the size in bits of the bitmap
 * @offset: the offset to start at
 *
 * Scans the bitmap and returns the index of the first set bit which is equal
 * to or after the specified offset. Will return size if no bits are set.
 */
static inline u16
ice_find_next_bit(const ice_bitmap_t *bitmap, u16 size, u16 offset)
{
	u16 i, j;

	if (offset >= size)
		return size;

	/* Since the starting position may not be directly on a chunk
	 * boundary, we need to be careful to handle the first chunk specially
	 */
	i = BIT_CHUNK(offset);
	if (bitmap[i] != 0) {
		u16 off = i * BITS_PER_CHUNK;

		for (j = offset % BITS_PER_CHUNK; j < BITS_PER_CHUNK; j++) {
			if (ice_is_bit_set(bitmap, off + j))
				return min(size, (u16)(off + j));
		}
	}

	/* Now we handle the remaining chunks, if any */
	for (i++; i < BITS_TO_CHUNKS(size); i++) {
		if (bitmap[i] != 0) {
			u16 off = i * BITS_PER_CHUNK;

			for (j = 0; j < BITS_PER_CHUNK; j++) {
				if (ice_is_bit_set(bitmap, off + j))
					return min(size, (u16)(off + j));
			}
		}
	}
	return size;
}

/**
 * ice_find_first_bit - Find the index of the first set bit of a bitmap
 * @bitmap: the bitmap to scan
 * @size: the size in bits of the bitmap
 *
 * Scans the bitmap and returns the index of the first set bit. Will return
 * size if no bits are set.
 */
static inline u16 ice_find_first_bit(const ice_bitmap_t *bitmap, u16 size)
{
	return ice_find_next_bit(bitmap, size, 0);
}

/**
 * ice_is_any_bit_set - Return true of any bit in the bitmap is set
 * @bitmap: the bitmap to check
 * @size: the size of the bitmap
 *
 * Equivalent to checking if ice_find_first_bit returns a value less than the
 * bitmap size.
 */
static inline bool ice_is_any_bit_set(ice_bitmap_t *bitmap, u16 size)
{
	return ice_find_first_bit(bitmap, size) < size;
}

/**
 * ice_cp_bitmap - copy bitmaps.
 * @dst: bitmap destination
 * @src: bitmap to copy from
 * @size: Size of the bitmaps in bits
 *
 * This function copy bitmap from src to dst.
 */
static inline void ice_cp_bitmap(ice_bitmap_t *dst, ice_bitmap_t *src, u16 size)
{
	ice_bitmap_t mask;
	u16 i;

	/* Handle all but last chunk*/
	for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
		dst[i] = src[i];

	/* We want to only copy bits within the size.*/
	mask = LAST_CHUNK_MASK(size);
	dst[i] &= ~mask;
	dst[i] |= src[i] & mask;
}

/**
 * ice_cmp_bitmaps - compares two bitmaps.
 * @bmp1: the bitmap to compare
 * @bmp2: the bitmap to compare with bmp1
 * @size: Size of the bitmaps in bits
 *
 * This function compares two bitmaps, and returns result as true or false.
 */
static inline bool
ice_cmp_bitmap(ice_bitmap_t *bmp1, ice_bitmap_t *bmp2, u16 size)
{
	ice_bitmap_t mask;
	u16 i;

	/* Handle all but last chunk*/
	for (i = 0; i < BITS_TO_CHUNKS(size) - 1; i++)
		if (bmp1[i] != bmp2[i])
			return false;

	/* We want to only compare bits within the size.*/
	mask = LAST_CHUNK_MASK(size);
	if ((bmp1[i] & mask) != (bmp2[i] & mask))
		return false;

	return true;
}


#endif /* _ICE_BITOPS_H_ */