tools/include/linux/bitmap.h

   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 #define bitmap_size(nbits)      (ALIGN(nbits, BITS_PER_LONG) / BITS_PER_BYTE)
  30
  31 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
  32 {
  33         if (small_const_nbits(nbits))
  34                 *dst = 0UL;
  35         else {
  36                 memset(dst, 0, bitmap_size(nbits));
  37         }
  38 }
  39
  40 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
  41 {
  42         unsigned int nlongs = BITS_TO_LONGS(nbits);
  43         if (!small_const_nbits(nbits)) {
  44                 unsigned int len = (nlongs - 1) * sizeof(unsigned long);
  45                 memset(dst, 0xff,  len);
  46         }
  47         dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
  48 }
  49
  50 static inline bool bitmap_empty(const unsigned long *src, unsigned int nbits)
  51 {
  52         if (small_const_nbits(nbits))
  53                 return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
  54
  55         return find_first_bit(src, nbits) == nbits;
  56 }
  57
  58 static inline bool bitmap_full(const unsigned long *src, unsigned int nbits)
  59 {
  60         if (small_const_nbits(nbits))
  61                 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
  62
  63         return find_first_zero_bit(src, nbits) == nbits;
  64 }
  65
  66 static inline unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits)
  67 {
  68         if (small_const_nbits(nbits))
  69                 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
  70         return __bitmap_weight(src, nbits);
  71 }
  72
  73 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
  74                              const unsigned long *src2, unsigned int nbits)
  75 {
  76         if (small_const_nbits(nbits))
  77                 *dst = *src1 | *src2;
  78         else
  79                 __bitmap_or(dst, src1, src2, nbits);
  80 }
  81
  82 /**
  83  * bitmap_zalloc - Allocate bitmap
  84  * @nbits: Number of bits
  85  */
  86 static inline unsigned long *bitmap_zalloc(int nbits)
  87 {
  88         return calloc(1, bitmap_size(nbits));
  89 }
  90
  91 /*
  92  * bitmap_free - Free bitmap
  93  * @bitmap: pointer to bitmap
  94  */
  95 static inline void bitmap_free(unsigned long *bitmap)
  96 {
  97         free(bitmap);
  98 }
  99
 100 /*
 101  * bitmap_scnprintf - print bitmap list into buffer
 102  * @bitmap: bitmap
 103  * @nbits: size of bitmap
 104  * @buf: buffer to store output
 105  * @size: size of @buf
 106  */
 107 size_t bitmap_scnprintf(unsigned long *bitmap, unsigned int nbits,
 108                         char *buf, size_t size);
 109
 110 /**
 111  * bitmap_and - Do logical and on bitmaps
 112  * @dst: resulting bitmap
 113  * @src1: operand 1
 114  * @src2: operand 2
 115  * @nbits: size of bitmap
 116  */
 117 static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1,
 118                              const unsigned long *src2, unsigned int nbits)
 119 {
 120         if (small_const_nbits(nbits))
 121                 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
 122         return __bitmap_and(dst, src1, src2, nbits);
 123 }
 124
 125 #ifdef __LITTLE_ENDIAN
 126 #define BITMAP_MEM_ALIGNMENT 8
 127 #else
 128 #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
 129 #endif
 130 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
 131
 132 static inline bool bitmap_equal(const unsigned long *src1,
 133                                 const unsigned long *src2, unsigned int nbits)
 134 {
 135         if (small_const_nbits(nbits))
 136                 return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
 137         if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
 138             IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
 139                 return !memcmp(src1, src2, nbits / 8);
 140         return __bitmap_equal(src1, src2, nbits);
 141 }
 142
 143 static inline bool bitmap_intersects(const unsigned long *src1,
 144                                      const unsigned long *src2,
 145                                      unsigned int nbits)
 146 {
 147         if (small_const_nbits(nbits))
 148                 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
 149         else
 150                 return __bitmap_intersects(src1, src2, nbits);
 151 }
 152
 153 static inline void bitmap_clear(unsigned long *map, unsigned int start,
 154                                unsigned int nbits)
 155 {
 156         if (__builtin_constant_p(nbits) && nbits == 1)
 157                 __clear_bit(start, map);
 158         else if (small_const_nbits(start + nbits))
 159                 *map &= ~GENMASK(start + nbits - 1, start);
 160         else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
 161                  IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
 162                  __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
 163                  IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
 164                 memset((char *)map + start / 8, 0, nbits / 8);
 165         else
 166                 __bitmap_clear(map, start, nbits);
 167 }
 168 #endif /* _TOOLS_LINUX_BITMAP_H */