sbi_bitops.c 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
  1. /*
  2. * SPDX-License-Identifier: BSD-2-Clause
  3. *
  4. * Copyright (c) 2020 Western Digital Corporation or its affiliates.
  5. *
  6. * Authors:
  7. * Atish Patra <atish.patra@wdc.com>
  8. * Anup Patel <anup.patel@wdc.com>
  9. */
  10. #include <sbi/sbi_bitops.h>
  11. #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
  12. /**
  13. * find_first_bit - find the first set bit in a memory region
  14. * @addr: The address to start the search at
  15. * @size: The maximum size to search
  16. *
  17. * Returns the bit number of the first set bit.
  18. */
  19. unsigned long find_first_bit(const unsigned long *addr,
  20. unsigned long size)
  21. {
  22. const unsigned long *p = addr;
  23. unsigned long result = 0;
  24. unsigned long tmp;
  25. while (size & ~(BITS_PER_LONG-1)) {
  26. if ((tmp = *(p++)))
  27. goto found;
  28. result += BITS_PER_LONG;
  29. size -= BITS_PER_LONG;
  30. }
  31. if (!size)
  32. return result;
  33. tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
  34. if (tmp == 0UL) /* Are any bits set? */
  35. return result + size; /* Nope. */
  36. found:
  37. return result + __ffs(tmp);
  38. }
  39. /**
  40. * find_first_zero_bit - find the first cleared bit in a memory region
  41. * @addr: The address to start the search at
  42. * @size: The maximum size to search
  43. *
  44. * Returns the bit number of the first cleared bit.
  45. */
  46. unsigned long find_first_zero_bit(const unsigned long *addr,
  47. unsigned long size)
  48. {
  49. const unsigned long *p = addr;
  50. unsigned long result = 0;
  51. unsigned long tmp;
  52. while (size & ~(BITS_PER_LONG-1)) {
  53. if (~(tmp = *(p++)))
  54. goto found;
  55. result += BITS_PER_LONG;
  56. size -= BITS_PER_LONG;
  57. }
  58. if (!size)
  59. return result;
  60. tmp = (*p) | (~0UL << size);
  61. if (tmp == ~0UL) /* Are any bits zero? */
  62. return result + size; /* Nope. */
  63. found:
  64. return result + ffz(tmp);
  65. }
  66. /**
  67. * find_last_bit - find the last set bit in a memory region
  68. * @addr: The address to start the search at
  69. * @size: The maximum size to search
  70. *
  71. * Returns the bit number of the first set bit, or size.
  72. */
  73. unsigned long find_last_bit(const unsigned long *addr,
  74. unsigned long size)
  75. {
  76. unsigned long words;
  77. unsigned long tmp;
  78. /* Start at final word. */
  79. words = size / BITS_PER_LONG;
  80. /* Partial final word? */
  81. if (size & (BITS_PER_LONG-1)) {
  82. tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
  83. - (size & (BITS_PER_LONG-1)))));
  84. if (tmp)
  85. goto found;
  86. }
  87. while (words) {
  88. tmp = addr[--words];
  89. if (tmp) {
  90. found:
  91. return words * BITS_PER_LONG + __fls(tmp);
  92. }
  93. }
  94. /* Not found */
  95. return size;
  96. }
  97. /**
  98. * find_next_bit - find the next set bit in a memory region
  99. * @addr: The address to base the search on
  100. * @offset: The bitnumber to start searching at
  101. * @size: The bitmap size in bits
  102. */
  103. unsigned long find_next_bit(const unsigned long *addr,
  104. unsigned long size, unsigned long offset)
  105. {
  106. const unsigned long *p = addr + BITOP_WORD(offset);
  107. unsigned long result = offset & ~(BITS_PER_LONG-1);
  108. unsigned long tmp;
  109. if (offset >= size)
  110. return size;
  111. size -= result;
  112. offset %= BITS_PER_LONG;
  113. if (offset) {
  114. tmp = *(p++);
  115. tmp &= (~0UL << offset);
  116. if (size < BITS_PER_LONG)
  117. goto found_first;
  118. if (tmp)
  119. goto found_middle;
  120. size -= BITS_PER_LONG;
  121. result += BITS_PER_LONG;
  122. }
  123. while (size & ~(BITS_PER_LONG-1)) {
  124. if ((tmp = *(p++)))
  125. goto found_middle;
  126. result += BITS_PER_LONG;
  127. size -= BITS_PER_LONG;
  128. }
  129. if (!size)
  130. return result;
  131. tmp = *p;
  132. found_first:
  133. tmp &= (~0UL >> (BITS_PER_LONG - size));
  134. if (tmp == 0UL) /* Are any bits set? */
  135. return result + size; /* Nope. */
  136. found_middle:
  137. return result + __ffs(tmp);
  138. }
  139. /**
  140. * find_next_zero_bit - find the next cleared bit in a memory region
  141. * @addr: The address to base the search on
  142. * @offset: The bitnumber to start searching at
  143. * @size: The bitmap size in bits
  144. */
  145. unsigned long find_next_zero_bit(const unsigned long *addr,
  146. unsigned long size,
  147. unsigned long offset)
  148. {
  149. const unsigned long *p = addr + BITOP_WORD(offset);
  150. unsigned long result = offset & ~(BITS_PER_LONG-1);
  151. unsigned long tmp;
  152. if (offset >= size)
  153. return size;
  154. size -= result;
  155. offset %= BITS_PER_LONG;
  156. if (offset) {
  157. tmp = *(p++);
  158. tmp |= ~0UL >> (BITS_PER_LONG - offset);
  159. if (size < BITS_PER_LONG)
  160. goto found_first;
  161. if (~tmp)
  162. goto found_middle;
  163. size -= BITS_PER_LONG;
  164. result += BITS_PER_LONG;
  165. }
  166. while (size & ~(BITS_PER_LONG-1)) {
  167. if (~(tmp = *(p++)))
  168. goto found_middle;
  169. result += BITS_PER_LONG;
  170. size -= BITS_PER_LONG;
  171. }
  172. if (!size)
  173. return result;
  174. tmp = *p;
  175. found_first:
  176. tmp |= ~0UL << size;
  177. if (tmp == ~0UL) /* Are any bits zero? */
  178. return result + size; /* Nope. */
  179. found_middle:
  180. return result + ffz(tmp);
  181. }