find.c 1.9 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * MSB0 numbered special bitops handling.
  4. *
  5. * The bits are numbered:
  6. * |0..............63|64............127|128...........191|192...........255|
  7. *
  8. * The reason for this bit numbering is the fact that the hardware sets bits
  9. * in a bitmap starting at bit 0 (MSB) and we don't want to scan the bitmap
  10. * from the 'wrong end'.
  11. */
  12. #include <linux/compiler.h>
  13. #include <linux/bitops.h>
  14. #include <linux/export.h>
  15. unsigned long find_first_bit_inv(const unsigned long *addr, unsigned long size)
  16. {
  17. const unsigned long *p = addr;
  18. unsigned long result = 0;
  19. unsigned long tmp;
  20. while (size & ~(BITS_PER_LONG - 1)) {
  21. if ((tmp = *(p++)))
  22. goto found;
  23. result += BITS_PER_LONG;
  24. size -= BITS_PER_LONG;
  25. }
  26. if (!size)
  27. return result;
  28. tmp = (*p) & (~0UL << (BITS_PER_LONG - size));
  29. if (!tmp) /* Are any bits set? */
  30. return result + size; /* Nope. */
  31. found:
  32. return result + (__fls(tmp) ^ (BITS_PER_LONG - 1));
  33. }
  34. EXPORT_SYMBOL(find_first_bit_inv);
  35. unsigned long find_next_bit_inv(const unsigned long *addr, unsigned long size,
  36. unsigned long offset)
  37. {
  38. const unsigned long *p = addr + (offset / BITS_PER_LONG);
  39. unsigned long result = offset & ~(BITS_PER_LONG - 1);
  40. unsigned long tmp;
  41. if (offset >= size)
  42. return size;
  43. size -= result;
  44. offset %= BITS_PER_LONG;
  45. if (offset) {
  46. tmp = *(p++);
  47. tmp &= (~0UL >> offset);
  48. if (size < BITS_PER_LONG)
  49. goto found_first;
  50. if (tmp)
  51. goto found_middle;
  52. size -= BITS_PER_LONG;
  53. result += BITS_PER_LONG;
  54. }
  55. while (size & ~(BITS_PER_LONG-1)) {
  56. if ((tmp = *(p++)))
  57. goto found_middle;
  58. result += BITS_PER_LONG;
  59. size -= BITS_PER_LONG;
  60. }
  61. if (!size)
  62. return result;
  63. tmp = *p;
  64. found_first:
  65. tmp &= (~0UL << (BITS_PER_LONG - size));
  66. if (!tmp) /* Are any bits set? */
  67. return result + size; /* Nope. */
  68. found_middle:
  69. return result + (__fls(tmp) ^ (BITS_PER_LONG - 1));
  70. }
  71. EXPORT_SYMBOL(find_next_bit_inv);