tools/lib/bitmap.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * From lib/bitmap.c
   4  * Helper functions for bitmap.h.
   5  */
   6 #include <linux/bitmap.h>
   7
   8 unsigned int __bitmap_weight(const unsigned long *bitmap, int bits)
   9 {
  10         unsigned int k, w = 0, lim = bits/BITS_PER_LONG;
  11
  12         for (k = 0; k < lim; k++)
  13                 w += hweight_long(bitmap[k]);
  14
  15         if (bits % BITS_PER_LONG)
  16                 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
  17
  18         return w;
  19 }
  20
  21 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  22                  const unsigned long *bitmap2, int bits)
  23 {
  24         int k;
  25         int nr = BITS_TO_LONGS(bits);
  26
  27         for (k = 0; k < nr; k++)
  28                 dst[k] = bitmap1[k] | bitmap2[k];
  29 }
  30
  31 size_t bitmap_scnprintf(unsigned long *bitmap, unsigned int nbits,
  32                         char *buf, size_t size)
  33 {
  34         /* current bit is 'cur', most recently seen range is [rbot, rtop] */
  35         unsigned int cur, rbot, rtop;
  36         bool first = true;
  37         size_t ret = 0;
  38
  39         rbot = cur = find_first_bit(bitmap, nbits);
  40         while (cur < nbits) {
  41                 rtop = cur;
  42                 cur = find_next_bit(bitmap, nbits, cur + 1);
  43                 if (cur < nbits && cur <= rtop + 1)
  44                         continue;
  45
  46                 if (!first)
  47                         ret += scnprintf(buf + ret, size - ret, ",");
  48
  49                 first = false;
  50
  51                 ret += scnprintf(buf + ret, size - ret, "%d", rbot);
  52                 if (rbot < rtop)
  53                         ret += scnprintf(buf + ret, size - ret, "-%d", rtop);
  54
  55                 rbot = cur;
  56         }
  57         return ret;
  58 }
  59
  60 bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
  61                  const unsigned long *bitmap2, unsigned int bits)
  62 {
  63         unsigned int k;
  64         unsigned int lim = bits/BITS_PER_LONG;
  65         unsigned long result = 0;
  66
  67         for (k = 0; k < lim; k++)
  68                 result |= (dst[k] = bitmap1[k] & bitmap2[k]);
  69         if (bits % BITS_PER_LONG)
  70                 result |= (dst[k] = bitmap1[k] & bitmap2[k] &
  71                            BITMAP_LAST_WORD_MASK(bits));
  72         return result != 0;
  73 }
  74
  75 bool __bitmap_equal(const unsigned long *bitmap1,
  76                     const unsigned long *bitmap2, unsigned int bits)
  77 {
  78         unsigned int k, lim = bits/BITS_PER_LONG;
  79         for (k = 0; k < lim; ++k)
  80                 if (bitmap1[k] != bitmap2[k])
  81                         return false;
  82
  83         if (bits % BITS_PER_LONG)
  84                 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
  85                         return false;
  86
  87         return true;
  88 }
  89
  90 bool __bitmap_intersects(const unsigned long *bitmap1,
  91                          const unsigned long *bitmap2, unsigned int bits)
  92 {
  93         unsigned int k, lim = bits/BITS_PER_LONG;
  94         for (k = 0; k < lim; ++k)
  95                 if (bitmap1[k] & bitmap2[k])
  96                         return true;
  97
  98         if (bits % BITS_PER_LONG)
  99                 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
 100                         return true;
 101         return false;
 102 }
 103
 104 void __bitmap_clear(unsigned long *map, unsigned int start, int len)
 105 {
 106         unsigned long *p = map + BIT_WORD(start);
 107         const unsigned int size = start + len;
 108         int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 109         unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 110
 111         while (len - bits_to_clear >= 0) {
 112                 *p &= ~mask_to_clear;
 113                 len -= bits_to_clear;
 114                 bits_to_clear = BITS_PER_LONG;
 115                 mask_to_clear = ~0UL;
 116                 p++;
 117         }
 118         if (len) {
 119                 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 120                 *p &= ~mask_to_clear;
 121         }
 122 }