1/* SPDX-License-Identifier: GPL-2.0 */ 2#ifndef _TOOLS_LINUX_BITMAP_H 3#define _TOOLS_LINUX_BITMAP_H 4 5#include <string.h> 6#include <linux/bitops.h> 7#include <linux/find.h> 8#include <stdlib.h> 9#include <linux/kernel.h> 10 11#define DECLARE_BITMAP(name,bits) \ 12 unsigned long name[BITS_TO_LONGS(bits)] 13 14unsigned int __bitmap_weight(const unsigned long *bitmap, int bits); 15void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, 16 const unsigned long *bitmap2, int bits); 17bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, 18 const unsigned long *bitmap2, unsigned int bits); 19bool __bitmap_equal(const unsigned long *bitmap1, 20 const unsigned long *bitmap2, unsigned int bits); 21void bitmap_clear(unsigned long *map, unsigned int start, int len); 22bool __bitmap_intersects(const unsigned long *bitmap1, 23 const unsigned long *bitmap2, unsigned int bits); 24 25#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1))) 26#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) 27 28static inline void bitmap_zero(unsigned long *dst, unsigned int nbits) 29{ 30 if (small_const_nbits(nbits)) 31 *dst = 0UL; 32 else { 33 int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); 34 memset(dst, 0, len); 35 } 36} 37 38static inline void bitmap_fill(unsigned long *dst, unsigned int nbits) 39{ 40 unsigned int nlongs = BITS_TO_LONGS(nbits); 41 if (!small_const_nbits(nbits)) { 42 unsigned int len = (nlongs - 1) * sizeof(unsigned long); 43 memset(dst, 0xff, len); 44 } 45 dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits); 46} 47 48static inline bool bitmap_empty(const unsigned long *src, unsigned int nbits) 49{ 50 if (small_const_nbits(nbits)) 51 return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); 52 53 return find_first_bit(src, nbits) == nbits; 54} 55 56static inline bool bitmap_full(const unsigned long *src, unsigned int nbits) 57{ 58 if (small_const_nbits(nbits)) 59 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); 60 61 return find_first_zero_bit(src, nbits) == nbits; 62} 63 64static inline unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits) 65{ 66 if (small_const_nbits(nbits)) 67 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits)); 68 return __bitmap_weight(src, nbits); 69} 70 71static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, 72 const unsigned long *src2, unsigned int nbits) 73{ 74 if (small_const_nbits(nbits)) 75 *dst = *src1 | *src2; 76 else 77 __bitmap_or(dst, src1, src2, nbits); 78} 79 80/** 81 * bitmap_zalloc - Allocate bitmap 82 * @nbits: Number of bits 83 */ 84static inline unsigned long *bitmap_zalloc(int nbits) 85{ 86 return calloc(1, BITS_TO_LONGS(nbits) * sizeof(unsigned long)); 87} 88 89/* 90 * bitmap_free - Free bitmap 91 * @bitmap: pointer to bitmap 92 */ 93static inline void bitmap_free(unsigned long *bitmap) 94{ 95 free(bitmap); 96} 97 98/* 99 * bitmap_scnprintf - print bitmap list into buffer 100 * @bitmap: bitmap 101 * @nbits: size of bitmap 102 * @buf: buffer to store output 103 * @size: size of @buf 104 */ 105size_t bitmap_scnprintf(unsigned long *bitmap, unsigned int nbits, 106 char *buf, size_t size); 107 108/** 109 * bitmap_and - Do logical and on bitmaps 110 * @dst: resulting bitmap 111 * @src1: operand 1 112 * @src2: operand 2 113 * @nbits: size of bitmap 114 */ 115static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1, 116 const unsigned long *src2, unsigned int nbits) 117{ 118 if (small_const_nbits(nbits)) 119 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0; 120 return __bitmap_and(dst, src1, src2, nbits); 121} 122 123#ifdef __LITTLE_ENDIAN 124#define BITMAP_MEM_ALIGNMENT 8 125#else 126#define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long)) 127#endif 128#define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1) 129#define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) == 0) 130 131static inline bool bitmap_equal(const unsigned long *src1, 132 const unsigned long *src2, unsigned int nbits) 133{ 134 if (small_const_nbits(nbits)) 135 return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); 136 if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) && 137 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) 138 return !memcmp(src1, src2, nbits / 8); 139 return __bitmap_equal(src1, src2, nbits); 140} 141 142static inline bool bitmap_intersects(const unsigned long *src1, 143 const unsigned long *src2, 144 unsigned int nbits) 145{ 146 if (small_const_nbits(nbits)) 147 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; 148 else 149 return __bitmap_intersects(src1, src2, nbits); 150} 151 152#endif /* _TOOLS_LINUX_BITMAP_H */ 153