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