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 <asm-generic/bitsperlong.h> 7 #include <linux/align.h> 8 #include <linux/bitops.h> 9 #include <linux/find.h> 10 #include <stdlib.h> 11 #include <linux/kernel.h> 12 13 #define DECLARE_BITMAP(name,bits) \ 14 unsigned long name[BITS_TO_LONGS(bits)] 15 16 unsigned int __bitmap_weight(const unsigned long *bitmap, int bits); 17 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, 18 const unsigned long *bitmap2, int bits); 19 bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, 20 const unsigned long *bitmap2, unsigned int bits); 21 bool __bitmap_equal(const unsigned long *bitmap1, 22 const unsigned long *bitmap2, unsigned int bits); 23 void __bitmap_set(unsigned long *map, unsigned int start, int len); 24 void __bitmap_clear(unsigned long *map, unsigned int start, int len); 25 bool __bitmap_intersects(const unsigned long *bitmap1, 26 const unsigned long *bitmap2, unsigned int bits); 27 bool __bitmap_subset(const unsigned long *bitmap1, 28 const unsigned long *bitmap2, unsigned int nbits); 29 bool __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, 30 const unsigned long *bitmap2, unsigned int nbits); 31 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, 32 const unsigned long *bitmap2, unsigned int nbits); 33 34 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1))) 35 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) 36 37 #define bitmap_size(nbits) (ALIGN(nbits, BITS_PER_LONG) / BITS_PER_BYTE) 38 39 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits) 40 { 41 if (small_const_nbits(nbits)) 42 *dst = 0UL; 43 else { 44 memset(dst, 0, bitmap_size(nbits)); 45 } 46 } 47 48 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits) 49 { 50 unsigned int nlongs = BITS_TO_LONGS(nbits); 51 if (!small_const_nbits(nbits)) { 52 unsigned int len = (nlongs - 1) * sizeof(unsigned long); 53 memset(dst, 0xff, len); 54 } 55 dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits); 56 } 57 58 static __always_inline 59 void bitmap_copy(unsigned long *dst, const unsigned long *src, unsigned int nbits) 60 { 61 unsigned int len = bitmap_size(nbits); 62 63 if (small_const_nbits(nbits)) 64 *dst = *src; 65 else 66 memcpy(dst, src, len); 67 } 68 69 static inline bool bitmap_empty(const unsigned long *src, unsigned int nbits) 70 { 71 if (small_const_nbits(nbits)) 72 return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); 73 74 return find_first_bit(src, nbits) == nbits; 75 } 76 77 static inline bool bitmap_full(const unsigned long *src, unsigned int nbits) 78 { 79 if (small_const_nbits(nbits)) 80 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); 81 82 return find_first_zero_bit(src, nbits) == nbits; 83 } 84 85 static inline unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits) 86 { 87 if (small_const_nbits(nbits)) 88 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits)); 89 return __bitmap_weight(src, nbits); 90 } 91 92 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, 93 const unsigned long *src2, unsigned int nbits) 94 { 95 if (small_const_nbits(nbits)) 96 *dst = *src1 | *src2; 97 else 98 __bitmap_or(dst, src1, src2, nbits); 99 } 100 101 static __always_inline 102 bool bitmap_andnot(unsigned long *dst, const unsigned long *src1, 103 const unsigned long *src2, unsigned int nbits) 104 { 105 if (small_const_nbits(nbits)) 106 return (*dst = *src1 & ~(*src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; 107 return __bitmap_andnot(dst, src1, src2, nbits); 108 } 109 110 static inline unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags __maybe_unused) 111 { 112 return malloc(bitmap_size(nbits)); 113 } 114 115 /** 116 * bitmap_zalloc - Allocate bitmap 117 * @nbits: Number of bits 118 */ 119 static inline unsigned long *bitmap_zalloc(int nbits) 120 { 121 return calloc(1, bitmap_size(nbits)); 122 } 123 124 /* 125 * bitmap_free - Free bitmap 126 * @bitmap: pointer to bitmap 127 */ 128 static inline void bitmap_free(unsigned long *bitmap) 129 { 130 free(bitmap); 131 } 132 133 /* 134 * bitmap_scnprintf - print bitmap list into buffer 135 * @bitmap: bitmap 136 * @nbits: size of bitmap 137 * @buf: buffer to store output 138 * @size: size of @buf 139 */ 140 size_t bitmap_scnprintf(unsigned long *bitmap, unsigned int nbits, 141 char *buf, size_t size); 142 143 /** 144 * bitmap_and - Do logical and on bitmaps 145 * @dst: resulting bitmap 146 * @src1: operand 1 147 * @src2: operand 2 148 * @nbits: size of bitmap 149 */ 150 static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1, 151 const unsigned long *src2, unsigned int nbits) 152 { 153 if (small_const_nbits(nbits)) 154 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0; 155 return __bitmap_and(dst, src1, src2, nbits); 156 } 157 158 #ifdef __LITTLE_ENDIAN 159 #define BITMAP_MEM_ALIGNMENT 8 160 #else 161 #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long)) 162 #endif 163 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1) 164 165 static inline bool bitmap_equal(const unsigned long *src1, 166 const unsigned long *src2, unsigned int nbits) 167 { 168 if (small_const_nbits(nbits)) 169 return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); 170 if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) && 171 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) 172 return !memcmp(src1, src2, nbits / 8); 173 return __bitmap_equal(src1, src2, nbits); 174 } 175 176 static inline bool bitmap_intersects(const unsigned long *src1, 177 const unsigned long *src2, 178 unsigned int nbits) 179 { 180 if (small_const_nbits(nbits)) 181 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; 182 else 183 return __bitmap_intersects(src1, src2, nbits); 184 } 185 186 static __always_inline 187 bool bitmap_subset(const unsigned long *src1, const unsigned long *src2, unsigned int nbits) 188 { 189 if (small_const_nbits(nbits)) 190 return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits)); 191 else 192 return __bitmap_subset(src1, src2, nbits); 193 } 194 195 static inline void bitmap_set(unsigned long *map, unsigned int start, unsigned int nbits) 196 { 197 if (__builtin_constant_p(nbits) && nbits == 1) 198 __set_bit(start, map); 199 else if (small_const_nbits(start + nbits)) 200 *map |= GENMASK(start + nbits - 1, start); 201 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) && 202 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && 203 __builtin_constant_p(nbits & BITMAP_MEM_MASK) && 204 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) 205 memset((char *)map + start / 8, 0xff, nbits / 8); 206 else 207 __bitmap_set(map, start, nbits); 208 } 209 210 static inline void bitmap_clear(unsigned long *map, unsigned int start, 211 unsigned int nbits) 212 { 213 if (__builtin_constant_p(nbits) && nbits == 1) 214 __clear_bit(start, map); 215 else if (small_const_nbits(start + nbits)) 216 *map &= ~GENMASK(start + nbits - 1, start); 217 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) && 218 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && 219 __builtin_constant_p(nbits & BITMAP_MEM_MASK) && 220 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) 221 memset((char *)map + start / 8, 0, nbits / 8); 222 else 223 __bitmap_clear(map, start, nbits); 224 } 225 226 static __always_inline 227 void bitmap_xor(unsigned long *dst, const unsigned long *src1, 228 const unsigned long *src2, unsigned int nbits) 229 { 230 if (small_const_nbits(nbits)) 231 *dst = *src1 ^ *src2; 232 else 233 __bitmap_xor(dst, src1, src2, nbits); 234 } 235 236 #endif /* _TOOLS_LINUX_BITMAP_H */ 237