find_bit.c 6.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /* bit search implementation
  3. *
  4. * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
  5. * Written by David Howells ([email protected])
  6. *
  7. * Copyright (C) 2008 IBM Corporation
  8. * 'find_last_bit' is written by Rusty Russell <[email protected]>
  9. * (Inspired by David Howell's find_next_bit implementation)
  10. *
  11. * Rewritten by Yury Norov <[email protected]> to decrease
  12. * size and improve performance, 2015.
  13. */
  14. #include <linux/bitops.h>
  15. #include <linux/bitmap.h>
  16. #include <linux/export.h>
  17. #include <linux/math.h>
  18. #include <linux/minmax.h>
  19. #include <linux/swab.h>
  20. /*
  21. * Common helper for find_bit() function family
  22. * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
  23. * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
  24. * @size: The bitmap size in bits
  25. */
  26. #define FIND_FIRST_BIT(FETCH, MUNGE, size) \
  27. ({ \
  28. unsigned long idx, val, sz = (size); \
  29. \
  30. for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \
  31. val = (FETCH); \
  32. if (val) { \
  33. sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \
  34. break; \
  35. } \
  36. } \
  37. \
  38. sz; \
  39. })
  40. /*
  41. * Common helper for find_next_bit() function family
  42. * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
  43. * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
  44. * @size: The bitmap size in bits
  45. * @start: The bitnumber to start searching at
  46. */
  47. #define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \
  48. ({ \
  49. unsigned long mask, idx, tmp, sz = (size), __start = (start); \
  50. \
  51. if (unlikely(__start >= sz)) \
  52. goto out; \
  53. \
  54. mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \
  55. idx = __start / BITS_PER_LONG; \
  56. \
  57. for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \
  58. if ((idx + 1) * BITS_PER_LONG >= sz) \
  59. goto out; \
  60. idx++; \
  61. } \
  62. \
  63. sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \
  64. out: \
  65. sz; \
  66. })
  67. #define FIND_NTH_BIT(FETCH, size, num) \
  68. ({ \
  69. unsigned long sz = (size), nr = (num), idx, w, tmp; \
  70. \
  71. for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
  72. if (idx * BITS_PER_LONG + nr >= sz) \
  73. goto out; \
  74. \
  75. tmp = (FETCH); \
  76. w = hweight_long(tmp); \
  77. if (w > nr) \
  78. goto found; \
  79. \
  80. nr -= w; \
  81. } \
  82. \
  83. if (sz % BITS_PER_LONG) \
  84. tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
  85. found: \
  86. sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
  87. out: \
  88. sz; \
  89. })
  90. #ifndef find_first_bit
  91. /*
  92. * Find the first set bit in a memory region.
  93. */
  94. unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
  95. {
  96. return FIND_FIRST_BIT(addr[idx], /* nop */, size);
  97. }
  98. EXPORT_SYMBOL(_find_first_bit);
  99. #endif
  100. #ifndef find_first_and_bit
  101. /*
  102. * Find the first set bit in two memory regions.
  103. */
  104. unsigned long _find_first_and_bit(const unsigned long *addr1,
  105. const unsigned long *addr2,
  106. unsigned long size)
  107. {
  108. return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size);
  109. }
  110. EXPORT_SYMBOL(_find_first_and_bit);
  111. #endif
  112. #ifndef find_first_zero_bit
  113. /*
  114. * Find the first cleared bit in a memory region.
  115. */
  116. unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
  117. {
  118. return FIND_FIRST_BIT(~addr[idx], /* nop */, size);
  119. }
  120. EXPORT_SYMBOL(_find_first_zero_bit);
  121. #endif
  122. #ifndef find_next_bit
  123. unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start)
  124. {
  125. return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start);
  126. }
  127. EXPORT_SYMBOL(_find_next_bit);
  128. #endif
  129. unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
  130. {
  131. return FIND_NTH_BIT(addr[idx], size, n);
  132. }
  133. EXPORT_SYMBOL(__find_nth_bit);
  134. unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
  135. unsigned long size, unsigned long n)
  136. {
  137. return FIND_NTH_BIT(addr1[idx] & addr2[idx], size, n);
  138. }
  139. EXPORT_SYMBOL(__find_nth_and_bit);
  140. unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
  141. unsigned long size, unsigned long n)
  142. {
  143. return FIND_NTH_BIT(addr1[idx] & ~addr2[idx], size, n);
  144. }
  145. EXPORT_SYMBOL(__find_nth_andnot_bit);
  146. #ifndef find_next_and_bit
  147. unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
  148. unsigned long nbits, unsigned long start)
  149. {
  150. return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start);
  151. }
  152. EXPORT_SYMBOL(_find_next_and_bit);
  153. #endif
  154. #ifndef find_next_andnot_bit
  155. unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
  156. unsigned long nbits, unsigned long start)
  157. {
  158. return FIND_NEXT_BIT(addr1[idx] & ~addr2[idx], /* nop */, nbits, start);
  159. }
  160. EXPORT_SYMBOL(_find_next_andnot_bit);
  161. #endif
  162. #ifndef find_next_zero_bit
  163. unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
  164. unsigned long start)
  165. {
  166. return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
  167. }
  168. EXPORT_SYMBOL(_find_next_zero_bit);
  169. #endif
  170. #ifndef find_last_bit
  171. unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
  172. {
  173. if (size) {
  174. unsigned long val = BITMAP_LAST_WORD_MASK(size);
  175. unsigned long idx = (size-1) / BITS_PER_LONG;
  176. do {
  177. val &= addr[idx];
  178. if (val)
  179. return idx * BITS_PER_LONG + __fls(val);
  180. val = ~0ul;
  181. } while (idx--);
  182. }
  183. return size;
  184. }
  185. EXPORT_SYMBOL(_find_last_bit);
  186. #endif
  187. unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
  188. unsigned long size, unsigned long offset)
  189. {
  190. offset = find_next_bit(addr, size, offset);
  191. if (offset == size)
  192. return size;
  193. offset = round_down(offset, 8);
  194. *clump = bitmap_get_value8(addr, offset);
  195. return offset;
  196. }
  197. EXPORT_SYMBOL(find_next_clump8);
  198. #ifdef __BIG_ENDIAN
  199. #ifndef find_first_zero_bit_le
  200. /*
  201. * Find the first cleared bit in an LE memory region.
  202. */
  203. unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)
  204. {
  205. return FIND_FIRST_BIT(~addr[idx], swab, size);
  206. }
  207. EXPORT_SYMBOL(_find_first_zero_bit_le);
  208. #endif
  209. #ifndef find_next_zero_bit_le
  210. unsigned long _find_next_zero_bit_le(const unsigned long *addr,
  211. unsigned long size, unsigned long offset)
  212. {
  213. return FIND_NEXT_BIT(~addr[idx], swab, size, offset);
  214. }
  215. EXPORT_SYMBOL(_find_next_zero_bit_le);
  216. #endif
  217. #ifndef find_next_bit_le
  218. unsigned long _find_next_bit_le(const unsigned long *addr,
  219. unsigned long size, unsigned long offset)
  220. {
  221. return FIND_NEXT_BIT(addr[idx], swab, size, offset);
  222. }
  223. EXPORT_SYMBOL(_find_next_bit_le);
  224. #endif
  225. #endif /* __BIG_ENDIAN */