rte_bitset.h

Go to the documentation of this file.

/* SPDX-License-Identifier: BSD-3-Clause
 * Copyright(c) 2023 Ericsson AB
 */

#ifndef _RTE_BITSET_H_
#define _RTE_BITSET_H_

#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#include <rte_bitops.h>
#include <rte_branch_prediction.h>
#include <rte_common.h>
#include <rte_compat.h>
#include <rte_debug.h>
#include <rte_memcpy.h>

#ifdef __cplusplus
extern "C" {
#endif

#define RTE_BITSET_WORD_SIZE (sizeof(uint64_t))

#define RTE_BITSET_WORD_BITS (RTE_BITSET_WORD_SIZE * CHAR_BIT)

#define RTE_BITSET_NUM_WORDS(size) \
    ((size + RTE_BITSET_WORD_BITS - 1) / RTE_BITSET_WORD_BITS)

#define RTE_BITSET_SIZE(size) \
    ((size_t)(RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_SIZE))

#define __RTE_BITSET_WORD_IDX(bit_num) ((bit_num) / RTE_BITSET_WORD_BITS)
#define __RTE_BITSET_BIT_OFFSET(bit_num) ((bit_num) % RTE_BITSET_WORD_BITS)
#define __RTE_BITSET_UNUSED(size) \
    ((RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_BITS) - (size))
#define __RTE_BITSET_USED_MASK(size) \
    (UINT64_MAX >> __RTE_BITSET_UNUSED(size))

#define __RTE_BITSET_DELEGATE_N(fun, bitset, bit_num, ...) \
    fun(&(bitset)[__RTE_BITSET_WORD_IDX(bit_num)], __RTE_BITSET_BIT_OFFSET(bit_num), \
        __VA_ARGS__)

/* MSVC doesn't have ##__VA_ARGS__, so argument-less -> special case */
#define __RTE_BITSET_DELEGATE(fun, bitset, bit_num) \
    fun(&(bitset)[__RTE_BITSET_WORD_IDX(bit_num)], __RTE_BITSET_BIT_OFFSET(bit_num))

#define RTE_BITSET_DECLARE(name, size) \
    uint64_t name[RTE_BITSET_NUM_WORDS(size)]

#define __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len) \
    ((len) - 1 - ((var) >= (start_bit) ? (var) - (start_bit) : (size) - (start_bit) + (var)))

#define __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, flags) \
    for ((var) = __rte_bitset_find(bitset, size, start_bit, len, flags); \
            (var) != -1; \
            (var) = __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len) > 0 ? \
                __rte_bitset_find(bitset, size, ((var) + 1) % (size), \
                __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len), flags) : -1)

#define RTE_BITSET_FOREACH_SET(var, bitset, size) \
    __RTE_BITSET_FOREACH(var, bitset, size, 0, size, 0)

#define RTE_BITSET_FOREACH_CLEAR(var, bitset, size) \
    __RTE_BITSET_FOREACH(var, bitset, size, 0, size, __RTE_BITSET_FIND_FLAG_FIND_CLEAR)

#define RTE_BITSET_FOREACH_SET_RANGE(var, bitset, size, start_bit, len) \
    __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, 0)

#define RTE_BITSET_FOREACH_CLEAR_RANGE(var, bitset, size, start_bit, len) \
    __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_FIND_CLEAR)

#define RTE_BITSET_FOREACH_SET_WRAP(var, bitset, size, start_bit, len) \
    __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_WRAP)

#define RTE_BITSET_FOREACH_CLEAR_WRAP(var, bitset, size, start_bit, len) \
    __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \
        __RTE_BITSET_FIND_FLAG_WRAP | __RTE_BITSET_FIND_FLAG_FIND_CLEAR)

__rte_experimental
static inline void
rte_bitset_init(uint64_t *bitset, size_t size)
{
    memset(bitset, 0, RTE_BITSET_SIZE(size));
}

__rte_experimental
static inline bool
rte_bitset_test(const uint64_t *bitset, size_t bit_num)
{
    return __RTE_BITSET_DELEGATE(rte_bit_test, bitset, bit_num);
}

__rte_experimental
static inline void
rte_bitset_set(uint64_t *bitset, size_t bit_num)
{
    __RTE_BITSET_DELEGATE(rte_bit_set, bitset, bit_num);
}

__rte_experimental
static inline void
rte_bitset_clear(uint64_t *bitset, size_t bit_num)
{
    __RTE_BITSET_DELEGATE(rte_bit_clear, bitset, bit_num);
}

__rte_experimental
static inline void
rte_bitset_assign(uint64_t *bitset, size_t bit_num, bool bit_value)
{
    __RTE_BITSET_DELEGATE_N(rte_bit_assign, bitset, bit_num, bit_value);
}

__rte_experimental
static inline void
rte_bitset_flip(uint64_t *bitset, size_t bit_num)
{
    __RTE_BITSET_DELEGATE(rte_bit_flip, bitset, bit_num);
}

__rte_experimental
static inline bool
rte_bitset_atomic_test(const uint64_t *bitset, size_t bit_num, int memory_order)
{
    return __RTE_BITSET_DELEGATE_N(rte_bit_atomic_test, bitset, bit_num, memory_order);
}

__rte_experimental
static inline void
rte_bitset_atomic_set(uint64_t *bitset, size_t bit_num, int memory_order)
{
    __RTE_BITSET_DELEGATE_N(rte_bit_atomic_set, bitset, bit_num, memory_order);
}

__rte_experimental
static inline void
rte_bitset_atomic_clear(uint64_t *bitset, size_t bit_num, int memory_order)
{
    __RTE_BITSET_DELEGATE_N(rte_bit_atomic_clear, bitset, bit_num, memory_order);
}

__rte_experimental
static inline void
rte_bitset_atomic_assign(uint64_t *bitset, size_t bit_num, bool bit_value, int memory_order)
{
    __RTE_BITSET_DELEGATE_N(rte_bit_atomic_assign, bitset, bit_num, bit_value, memory_order);
}

__rte_experimental
static inline void
rte_bitset_atomic_flip(uint64_t *bitset, size_t bit_num, int memory_order)
{
    __RTE_BITSET_DELEGATE_N(rte_bit_atomic_flip, bitset, bit_num, memory_order);
}

__rte_experimental
static inline void
rte_bitset_set_all(uint64_t *bitset, size_t size)
{
    memset(bitset, 0xFF, RTE_BITSET_SIZE(size));
}

__rte_experimental
static inline void
rte_bitset_clear_all(uint64_t *bitset, size_t size)
{
    rte_bitset_init(bitset, size);
}

__rte_experimental
static inline size_t
rte_bitset_count_set(const uint64_t *bitset, size_t size)
{
    size_t i;
    size_t total = 0;

    /*
     * Unused bits in a rte_bitset are always '0', and thus are
     * not included in this count.
     */
    for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++)
        total += rte_popcount64(bitset[i]);

    total += rte_popcount64(bitset[i] & __RTE_BITSET_USED_MASK(size));

    return total;
}

__rte_experimental
static inline size_t
rte_bitset_count_clear(const uint64_t *bitset, size_t size)
{
    return size - rte_bitset_count_set(bitset, size);
}

#define __RTE_BITSET_FIND_FLAG_FIND_CLEAR (1U << 0)
#define __RTE_BITSET_FIND_FLAG_WRAP (1U << 1)

__rte_experimental
static inline ssize_t
__rte_bitset_find_nowrap(const uint64_t *bitset, size_t __rte_unused size, size_t start_bit,
        size_t len, bool find_clear)
{
    size_t word_idx;
    size_t offset;
    size_t end_bit = start_bit + len;

    RTE_ASSERT(end_bit <= size);

    if (unlikely(len == 0))
        return -1;

    word_idx = __RTE_BITSET_WORD_IDX(start_bit);
    offset = __RTE_BITSET_BIT_OFFSET(start_bit);

    while (word_idx <= __RTE_BITSET_WORD_IDX(end_bit - 1)) {
        uint64_t word;

        word = bitset[word_idx];
        if (find_clear)
            word = ~word;

        word >>= offset;

        if (word != 0) {
            size_t ffs = start_bit + rte_bsf64(word);

            /*
             * Check if set bit were among the last,
             * unused bits, in the last word.
             */
            if (unlikely(ffs >= end_bit))
                return -1;

            return ffs;
        }

        start_bit += (RTE_BITSET_WORD_BITS - offset);
        word_idx++;
        offset = 0;
    }

    return -1;

}

__rte_experimental
static inline ssize_t
__rte_bitset_find(const uint64_t *bitset, size_t size, size_t start_bit, size_t len,
        unsigned int flags)
{
    bool find_clear = flags & __RTE_BITSET_FIND_FLAG_FIND_CLEAR;
    bool may_wrap = flags & __RTE_BITSET_FIND_FLAG_WRAP;
    bool does_wrap = (start_bit + len) > size;
    ssize_t rc;

    RTE_ASSERT(len <= size);
    if (!may_wrap)
        RTE_ASSERT(!does_wrap);

    if (may_wrap && does_wrap) {
        size_t len0 = size - start_bit;
        size_t len1 = len - len0;

        rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len0, find_clear);
        if (rc < 0)
            rc =  __rte_bitset_find_nowrap(bitset, size, 0, len1, find_clear);
    } else
        rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len, find_clear);

    return rc;
}

__rte_experimental
static inline ssize_t
rte_bitset_find_first_set(const uint64_t *bitset, size_t size)
{
    return __rte_bitset_find(bitset, size, 0, size, 0);
}

__rte_experimental
static inline ssize_t
rte_bitset_find_set(const uint64_t *bitset, size_t size, size_t start_bit, size_t len)
{
    return __rte_bitset_find(bitset, size, start_bit, len, 0);
}

__rte_experimental
static inline ssize_t
rte_bitset_find_set_wrap(const uint64_t *bitset, size_t size, size_t start_bit, size_t len)
{
    return __rte_bitset_find(bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_WRAP);
}

__rte_experimental
static inline ssize_t
rte_bitset_find_first_clear(const uint64_t *bitset, size_t size)
{
    return __rte_bitset_find(bitset, size, 0, size, __RTE_BITSET_FIND_FLAG_FIND_CLEAR);
}

__rte_experimental
static inline ssize_t
rte_bitset_find_clear(const uint64_t *bitset, size_t size, size_t start_bit, size_t len)
{
    return __rte_bitset_find(bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_FIND_CLEAR);
}

__rte_experimental
static inline ssize_t
rte_bitset_find_clear_wrap(const uint64_t *bitset, size_t size, size_t start_bit, size_t len)
{
    return __rte_bitset_find(bitset, size, start_bit, len,
        __RTE_BITSET_FIND_FLAG_FIND_CLEAR | __RTE_BITSET_FIND_FLAG_WRAP);
}

__rte_experimental
static inline void
rte_bitset_copy(uint64_t *__rte_restrict dst_bitset, const uint64_t *__rte_restrict src_bitset,
        size_t size)
{
    rte_memcpy(dst_bitset, src_bitset, RTE_BITSET_SIZE(size));
}

__rte_experimental
static inline void
rte_bitset_or(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1,
        size_t size)
{
    size_t i;

    for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
        dst_bitset[i] = src_bitset0[i] | src_bitset1[i];
}

__rte_experimental
static inline void
rte_bitset_and(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1,
        size_t size)
{
    size_t i;

    for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
        dst_bitset[i] = src_bitset0[i] & src_bitset1[i];
}

__rte_experimental
static inline void
rte_bitset_xor(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1,
        size_t size)
{
    size_t i;

    for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
        dst_bitset[i] = src_bitset0[i] ^ src_bitset1[i];
}

__rte_experimental
static inline void
rte_bitset_complement(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size)
{
    size_t i;

    for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
        dst_bitset[i] = ~src_bitset[i];
}

__rte_experimental
static inline void
rte_bitset_shift_left(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size,
        size_t shift_bits)
{
    const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS;
    const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS;
    unsigned int dst_idx;

    for (dst_idx = 0; dst_idx < RTE_BITSET_NUM_WORDS(size); dst_idx++) {
        int src_high_idx = dst_idx - src_word_offset;
        uint64_t low_bits = 0;
        uint64_t high_bits = 0;

        if (src_high_idx >= 0) {
            int src_low_idx = src_high_idx - 1;

            high_bits = src_bitset[src_high_idx] << src_bit_offset;

            if (src_bit_offset > 0 && src_low_idx >= 0)
                low_bits = src_bitset[src_low_idx] >>
                    (RTE_BITSET_WORD_BITS - src_bit_offset);
        }
        dst_bitset[dst_idx] = low_bits | high_bits;
    }
}

__rte_experimental
static inline void
rte_bitset_shift_right(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size,
        size_t shift_bits)
{
    const int num_words = RTE_BITSET_NUM_WORDS(size);
    const uint64_t used_mask = __RTE_BITSET_USED_MASK(size);
    const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS;
    const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS;
    int dst_idx;

    for (dst_idx = 0; dst_idx < num_words; dst_idx++) {
        int src_low_idx = src_word_offset + dst_idx;
        int src_high_idx = src_low_idx + 1;
        uint64_t src_low_word_bits = 0;
        uint64_t src_high_word_bits = 0;

        if (src_low_idx < num_words) {
            src_low_word_bits = src_bitset[src_low_idx];

            if (src_low_idx == (num_words - 1))
                src_low_word_bits &= used_mask;

            src_low_word_bits >>= src_bit_offset;

            if (src_bit_offset > 0 && src_high_idx < num_words) {
                src_high_word_bits = src_bitset[src_high_idx];

                if (src_high_idx == (num_words - 1))
                    src_high_word_bits &= used_mask;

                src_high_word_bits <<= (RTE_BITSET_WORD_BITS - src_bit_offset);
            }
        }
        dst_bitset[dst_idx] = src_low_word_bits | src_high_word_bits;
    }
}

__rte_experimental
static inline bool
rte_bitset_equal(const uint64_t *bitset_a, const uint64_t *bitset_b, size_t size)
{
    size_t i;
    uint64_t last_a, last_b;

    for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++)
        if (bitset_a[i] != bitset_b[i])
            return false;

    last_a = bitset_a[i] << __RTE_BITSET_UNUSED(size);
    last_b = bitset_b[i] << __RTE_BITSET_UNUSED(size);

    return last_a == last_b;
}

__rte_experimental
ssize_t
rte_bitset_to_str(const uint64_t *bitset, size_t size, char *buf, size_t capacity);

#ifdef __cplusplus
}
#endif

#endif /* _RTE_BITSET_H_ */