find_next_bit.c 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181
  1. /* find_next_bit.c: fallback find next bit implementation
  2. *
  3. * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
  4. * Written by David Howells (dhowells@redhat.com)
  5. *
  6. * This program is free software; you can redistribute it and/or
  7. * modify it under the terms of the GNU General Public License
  8. * as published by the Free Software Foundation; either version
  9. * 2 of the License, or (at your option) any later version.
  10. */
  11. #include <linux/bitops.h>
  12. #include <linux/module.h>
  13. #include <asm/types.h>
  14. #include <asm/byteorder.h>
  15. #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
  16. /**
  17. * find_next_bit - find the next set bit in a memory region
  18. * @addr: The address to base the search on
  19. * @offset: The bitnumber to start searching at
  20. * @size: The maximum size to search
  21. */
  22. unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  23. unsigned long offset)
  24. {
  25. const unsigned long *p = addr + BITOP_WORD(offset);
  26. unsigned long result = offset & ~(BITS_PER_LONG-1);
  27. unsigned long tmp;
  28. if (offset >= size)
  29. return size;
  30. size -= result;
  31. offset %= BITS_PER_LONG;
  32. if (offset) {
  33. tmp = *(p++);
  34. tmp &= (~0UL << offset);
  35. if (size < BITS_PER_LONG)
  36. goto found_first;
  37. if (tmp)
  38. goto found_middle;
  39. size -= BITS_PER_LONG;
  40. result += BITS_PER_LONG;
  41. }
  42. while (size & ~(BITS_PER_LONG-1)) {
  43. if ((tmp = *(p++)))
  44. goto found_middle;
  45. result += BITS_PER_LONG;
  46. size -= BITS_PER_LONG;
  47. }
  48. if (!size)
  49. return result;
  50. tmp = *p;
  51. found_first:
  52. tmp &= (~0UL >> (BITS_PER_LONG - size));
  53. if (tmp == 0UL) /* Are any bits set? */
  54. return result + size; /* Nope. */
  55. found_middle:
  56. return result + __ffs(tmp);
  57. }
  58. EXPORT_SYMBOL(find_next_bit);
  59. /*
  60. * This implementation of find_{first,next}_zero_bit was stolen from
  61. * Linus' asm-alpha/bitops.h.
  62. */
  63. unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  64. unsigned long offset)
  65. {
  66. const unsigned long *p = addr + BITOP_WORD(offset);
  67. unsigned long result = offset & ~(BITS_PER_LONG-1);
  68. unsigned long tmp;
  69. if (offset >= size)
  70. return size;
  71. size -= result;
  72. offset %= BITS_PER_LONG;
  73. if (offset) {
  74. tmp = *(p++);
  75. tmp |= ~0UL >> (BITS_PER_LONG - offset);
  76. if (size < BITS_PER_LONG)
  77. goto found_first;
  78. if (~tmp)
  79. goto found_middle;
  80. size -= BITS_PER_LONG;
  81. result += BITS_PER_LONG;
  82. }
  83. while (size & ~(BITS_PER_LONG-1)) {
  84. if (~(tmp = *(p++)))
  85. goto found_middle;
  86. result += BITS_PER_LONG;
  87. size -= BITS_PER_LONG;
  88. }
  89. if (!size)
  90. return result;
  91. tmp = *p;
  92. found_first:
  93. tmp |= ~0UL << size;
  94. if (tmp == ~0UL) /* Are any bits zero? */
  95. return result + size; /* Nope. */
  96. found_middle:
  97. return result + ffz(tmp);
  98. }
  99. EXPORT_SYMBOL(find_next_zero_bit);
  100. #ifdef __BIG_ENDIAN
  101. /* include/linux/byteorder does not support "unsigned long" type */
  102. static inline unsigned long ext2_swabp(const unsigned long * x)
  103. {
  104. #if BITS_PER_LONG == 64
  105. return (unsigned long) __swab64p((u64 *) x);
  106. #elif BITS_PER_LONG == 32
  107. return (unsigned long) __swab32p((u32 *) x);
  108. #else
  109. #error BITS_PER_LONG not defined
  110. #endif
  111. }
  112. /* include/linux/byteorder doesn't support "unsigned long" type */
  113. static inline unsigned long ext2_swab(const unsigned long y)
  114. {
  115. #if BITS_PER_LONG == 64
  116. return (unsigned long) __swab64((u64) y);
  117. #elif BITS_PER_LONG == 32
  118. return (unsigned long) __swab32((u32) y);
  119. #else
  120. #error BITS_PER_LONG not defined
  121. #endif
  122. }
  123. unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned
  124. long size, unsigned long offset)
  125. {
  126. const unsigned long *p = addr + BITOP_WORD(offset);
  127. unsigned long result = offset & ~(BITS_PER_LONG - 1);
  128. unsigned long tmp;
  129. if (offset >= size)
  130. return size;
  131. size -= result;
  132. offset &= (BITS_PER_LONG - 1UL);
  133. if (offset) {
  134. tmp = ext2_swabp(p++);
  135. tmp |= (~0UL >> (BITS_PER_LONG - offset));
  136. if (size < BITS_PER_LONG)
  137. goto found_first;
  138. if (~tmp)
  139. goto found_middle;
  140. size -= BITS_PER_LONG;
  141. result += BITS_PER_LONG;
  142. }
  143. while (size & ~(BITS_PER_LONG - 1)) {
  144. if (~(tmp = *(p++)))
  145. goto found_middle_swap;
  146. result += BITS_PER_LONG;
  147. size -= BITS_PER_LONG;
  148. }
  149. if (!size)
  150. return result;
  151. tmp = ext2_swabp(p);
  152. found_first:
  153. tmp |= ~0UL << size;
  154. if (tmp == ~0UL) /* Are any bits zero? */
  155. return result + size; /* Nope. Skip ffz */
  156. found_middle:
  157. return result + ffz(tmp);
  158. found_middle_swap:
  159. return result + ffz(ext2_swab(tmp));
  160. }
  161. EXPORT_SYMBOL(generic_find_next_zero_le_bit);
  162. #endif /* __BIG_ENDIAN */