find_bit.c 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193
  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 (dhowells@redhat.com)
  6. *
  7. * Copyright (C) 2008 IBM Corporation
  8. * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
  9. * (Inspired by David Howell's find_next_bit implementation)
  10. *
  11. * Rewritten by Yury Norov <yury.norov@gmail.com> 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/kernel.h>
  18. #include <linux/minmax.h>
  19. #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
  20. !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \
  21. !defined(find_next_and_bit)
  22. /*
  23. * This is a common helper function for find_next_bit, find_next_zero_bit, and
  24. * find_next_and_bit. The differences are:
  25. * - The "invert" argument, which is XORed with each fetched word before
  26. * searching it for one bits.
  27. * - The optional "addr2", which is anded with "addr1" if present.
  28. */
  29. static unsigned long _find_next_bit(const unsigned long *addr1,
  30. const unsigned long *addr2, unsigned long nbits,
  31. unsigned long start, unsigned long invert, unsigned long le)
  32. {
  33. unsigned long tmp, mask;
  34. if (unlikely(start >= nbits))
  35. return nbits;
  36. tmp = addr1[start / BITS_PER_LONG];
  37. if (addr2)
  38. tmp &= addr2[start / BITS_PER_LONG];
  39. tmp ^= invert;
  40. /* Handle 1st word. */
  41. mask = BITMAP_FIRST_WORD_MASK(start);
  42. if (le)
  43. mask = swab(mask);
  44. tmp &= mask;
  45. start = round_down(start, BITS_PER_LONG);
  46. while (!tmp) {
  47. start += BITS_PER_LONG;
  48. if (start >= nbits)
  49. return nbits;
  50. tmp = addr1[start / BITS_PER_LONG];
  51. if (addr2)
  52. tmp &= addr2[start / BITS_PER_LONG];
  53. tmp ^= invert;
  54. }
  55. if (le)
  56. tmp = swab(tmp);
  57. return min(start + __ffs(tmp), nbits);
  58. }
  59. #endif
  60. #ifndef find_next_bit
  61. /*
  62. * Find the next set bit in a memory region.
  63. */
  64. unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  65. unsigned long offset)
  66. {
  67. return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
  68. }
  69. EXPORT_SYMBOL(find_next_bit);
  70. #endif
  71. #ifndef find_next_zero_bit
  72. unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  73. unsigned long offset)
  74. {
  75. return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
  76. }
  77. EXPORT_SYMBOL(find_next_zero_bit);
  78. #endif
  79. #if !defined(find_next_and_bit)
  80. unsigned long find_next_and_bit(const unsigned long *addr1,
  81. const unsigned long *addr2, unsigned long size,
  82. unsigned long offset)
  83. {
  84. return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
  85. }
  86. EXPORT_SYMBOL(find_next_and_bit);
  87. #endif
  88. #ifndef find_first_bit
  89. /*
  90. * Find the first set bit in a memory region.
  91. */
  92. unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  93. {
  94. unsigned long idx;
  95. for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  96. if (addr[idx])
  97. return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  98. }
  99. return size;
  100. }
  101. EXPORT_SYMBOL(find_first_bit);
  102. #endif
  103. #ifndef find_first_zero_bit
  104. /*
  105. * Find the first cleared bit in a memory region.
  106. */
  107. unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
  108. {
  109. unsigned long idx;
  110. for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  111. if (addr[idx] != ~0UL)
  112. return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
  113. }
  114. return size;
  115. }
  116. EXPORT_SYMBOL(find_first_zero_bit);
  117. #endif
  118. #ifndef find_last_bit
  119. unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
  120. {
  121. if (size) {
  122. unsigned long val = BITMAP_LAST_WORD_MASK(size);
  123. unsigned long idx = (size-1) / BITS_PER_LONG;
  124. do {
  125. val &= addr[idx];
  126. if (val)
  127. return idx * BITS_PER_LONG + __fls(val);
  128. val = ~0ul;
  129. } while (idx--);
  130. }
  131. return size;
  132. }
  133. EXPORT_SYMBOL(find_last_bit);
  134. #endif
  135. #ifdef __BIG_ENDIAN
  136. #ifndef find_next_zero_bit_le
  137. unsigned long find_next_zero_bit_le(const void *addr, unsigned
  138. long size, unsigned long offset)
  139. {
  140. return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
  141. }
  142. EXPORT_SYMBOL(find_next_zero_bit_le);
  143. #endif
  144. #ifndef find_next_bit_le
  145. unsigned long find_next_bit_le(const void *addr, unsigned
  146. long size, unsigned long offset)
  147. {
  148. return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
  149. }
  150. EXPORT_SYMBOL(find_next_bit_le);
  151. #endif
  152. #endif /* __BIG_ENDIAN */
  153. unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
  154. unsigned long size, unsigned long offset)
  155. {
  156. offset = find_next_bit(addr, size, offset);
  157. if (offset == size)
  158. return size;
  159. offset = round_down(offset, 8);
  160. *clump = bitmap_get_value8(addr, offset);
  161. return offset;
  162. }
  163. EXPORT_SYMBOL(find_next_clump8);