bitmap.h 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217
  1. // SPDX-License-Identifier: GPL-2.0+
  2. #ifndef __LINUX_BITMAP_H
  3. #define __LINUX_BITMAP_H
  4. #include <asm/types.h>
  5. #include <linux/types.h>
  6. #include <linux/bitops.h>
  7. #include <linux/string.h>
  8. #ifdef __LITTLE_ENDIAN
  9. #define BITMAP_MEM_ALIGNMENT 8
  10. #else
  11. #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
  12. #endif
  13. #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
  14. #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
  15. #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
  16. #define small_const_nbits(nbits) \
  17. (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
  18. static inline void
  19. __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  20. const unsigned long *bitmap2, unsigned int bits)
  21. {
  22. unsigned int k;
  23. unsigned int nr = BITS_TO_LONGS(bits);
  24. for (k = 0; k < nr; k++)
  25. dst[k] = bitmap1[k] | bitmap2[k];
  26. }
  27. static inline int
  28. __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
  29. {
  30. unsigned int k, lim = bits / BITS_PER_LONG;
  31. int w = 0;
  32. for (k = 0; k < lim; k++)
  33. w += hweight_long(bitmap[k]);
  34. if (bits % BITS_PER_LONG)
  35. w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
  36. return w;
  37. }
  38. static inline void
  39. __bitmap_set(unsigned long *map, unsigned int start, int len)
  40. {
  41. unsigned long *p = map + BIT_WORD(start);
  42. const unsigned int size = start + len;
  43. int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
  44. unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
  45. while (len - bits_to_set >= 0) {
  46. *p |= mask_to_set;
  47. len -= bits_to_set;
  48. bits_to_set = BITS_PER_LONG;
  49. mask_to_set = ~0UL;
  50. p++;
  51. }
  52. if (len) {
  53. mask_to_set &= BITMAP_LAST_WORD_MASK(size);
  54. *p |= mask_to_set;
  55. }
  56. }
  57. static inline void
  58. __bitmap_clear(unsigned long *map, unsigned int start, int len)
  59. {
  60. unsigned long *p = map + BIT_WORD(start);
  61. const unsigned int size = start + len;
  62. int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
  63. unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
  64. while (len - bits_to_clear >= 0) {
  65. *p &= ~mask_to_clear;
  66. len -= bits_to_clear;
  67. bits_to_clear = BITS_PER_LONG;
  68. mask_to_clear = ~0UL;
  69. p++;
  70. }
  71. if (len) {
  72. mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
  73. *p &= ~mask_to_clear;
  74. }
  75. }
  76. static inline void bitmap_zero(unsigned long *dst, int nbits)
  77. {
  78. if (small_const_nbits(nbits)) {
  79. *dst = 0UL;
  80. } else {
  81. int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  82. memset(dst, 0, len);
  83. }
  84. }
  85. static inline unsigned long
  86. find_next_bit(const unsigned long *addr, unsigned long size,
  87. unsigned long offset)
  88. {
  89. const unsigned long *p = addr + BIT_WORD(offset);
  90. unsigned long result = offset & ~(BITS_PER_LONG - 1);
  91. unsigned long tmp;
  92. if (offset >= size)
  93. return size;
  94. size -= result;
  95. offset %= BITS_PER_LONG;
  96. if (offset) {
  97. tmp = *(p++);
  98. tmp &= (~0UL << offset);
  99. if (size < BITS_PER_LONG)
  100. goto found_first;
  101. if (tmp)
  102. goto found_middle;
  103. size -= BITS_PER_LONG;
  104. result += BITS_PER_LONG;
  105. }
  106. while (size & ~(BITS_PER_LONG - 1)) {
  107. tmp = *(p++);
  108. if ((tmp))
  109. goto found_middle;
  110. result += BITS_PER_LONG;
  111. size -= BITS_PER_LONG;
  112. }
  113. if (!size)
  114. return result;
  115. tmp = *p;
  116. found_first:
  117. tmp &= (~0UL >> (BITS_PER_LONG - size));
  118. if (tmp == 0UL) /* Are any bits set? */
  119. return result + size; /* Nope. */
  120. found_middle:
  121. return result + __ffs(tmp);
  122. }
  123. /*
  124. * Find the first set bit in a memory region.
  125. */
  126. static inline unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  127. {
  128. unsigned long idx;
  129. for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  130. if (addr[idx])
  131. return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  132. }
  133. return size;
  134. }
  135. #define for_each_set_bit(bit, addr, size) \
  136. for ((bit) = find_first_bit((addr), (size)); \
  137. (bit) < (size); \
  138. (bit) = find_next_bit((addr), (size), (bit) + 1))
  139. static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
  140. {
  141. if (small_const_nbits(nbits)) {
  142. *dst = ~0UL;
  143. } else {
  144. unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  145. memset(dst, 0xff, len);
  146. }
  147. }
  148. static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
  149. const unsigned long *src2, unsigned int nbits)
  150. {
  151. if (small_const_nbits(nbits))
  152. *dst = *src1 | *src2;
  153. else
  154. __bitmap_or(dst, src1, src2, nbits);
  155. }
  156. static inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
  157. {
  158. if (small_const_nbits(nbits))
  159. return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
  160. return __bitmap_weight(src, nbits);
  161. }
  162. static inline void bitmap_set(unsigned long *map, unsigned int start,
  163. unsigned int nbits)
  164. {
  165. if (__builtin_constant_p(nbits) && nbits == 1)
  166. __set_bit(start, map);
  167. else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
  168. IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
  169. __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
  170. IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
  171. memset((char *)map + start / 8, 0xff, nbits / 8);
  172. else
  173. __bitmap_set(map, start, nbits);
  174. }
  175. static inline void bitmap_clear(unsigned long *map, unsigned int start,
  176. unsigned int nbits)
  177. {
  178. if (__builtin_constant_p(nbits) && nbits == 1)
  179. __clear_bit(start, map);
  180. else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
  181. IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
  182. __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
  183. IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
  184. memset((char *)map + start / 8, 0, nbits / 8);
  185. else
  186. __bitmap_clear(map, start, nbits);
  187. }
  188. #endif /* __LINUX_BITMAP_H */