find_bit.c 3.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /* bit search implementation
  3. *
  4. * Copied from lib/find_bit.c to tools/lib/find_bit.c
  5. *
  6. * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
  7. * Written by David Howells (dhowells@redhat.com)
  8. *
  9. * Copyright (C) 2008 IBM Corporation
  10. * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
  11. * (Inspired by David Howell's find_next_bit implementation)
  12. *
  13. * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
  14. * size and improve performance, 2015.
  15. */
  16. #include <linux/bitops.h>
  17. #include <linux/bitmap.h>
  18. #include <linux/kernel.h>
  19. #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
  20. !defined(find_next_and_bit)
  21. /*
  22. * This is a common helper function for find_next_bit, find_next_zero_bit, and
  23. * find_next_and_bit. The differences are:
  24. * - The "invert" argument, which is XORed with each fetched word before
  25. * searching it for one bits.
  26. * - The optional "addr2", which is anded with "addr1" if present.
  27. */
  28. static inline unsigned long _find_next_bit(const unsigned long *addr1,
  29. const unsigned long *addr2, unsigned long nbits,
  30. unsigned long start, unsigned long invert)
  31. {
  32. unsigned long tmp;
  33. if (unlikely(start >= nbits))
  34. return nbits;
  35. tmp = addr1[start / BITS_PER_LONG];
  36. if (addr2)
  37. tmp &= addr2[start / BITS_PER_LONG];
  38. tmp ^= invert;
  39. /* Handle 1st word. */
  40. tmp &= BITMAP_FIRST_WORD_MASK(start);
  41. start = round_down(start, BITS_PER_LONG);
  42. while (!tmp) {
  43. start += BITS_PER_LONG;
  44. if (start >= nbits)
  45. return nbits;
  46. tmp = addr1[start / BITS_PER_LONG];
  47. if (addr2)
  48. tmp &= addr2[start / BITS_PER_LONG];
  49. tmp ^= invert;
  50. }
  51. return min(start + __ffs(tmp), nbits);
  52. }
  53. #endif
  54. #ifndef find_next_bit
  55. /*
  56. * Find the next set bit in a memory region.
  57. */
  58. unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  59. unsigned long offset)
  60. {
  61. return _find_next_bit(addr, NULL, size, offset, 0UL);
  62. }
  63. #endif
  64. #ifndef find_first_bit
  65. /*
  66. * Find the first set bit in a memory region.
  67. */
  68. unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  69. {
  70. unsigned long idx;
  71. for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  72. if (addr[idx])
  73. return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  74. }
  75. return size;
  76. }
  77. #endif
  78. #ifndef find_first_zero_bit
  79. /*
  80. * Find the first cleared bit in a memory region.
  81. */
  82. unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
  83. {
  84. unsigned long idx;
  85. for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  86. if (addr[idx] != ~0UL)
  87. return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
  88. }
  89. return size;
  90. }
  91. #endif
  92. #ifndef find_next_zero_bit
  93. unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  94. unsigned long offset)
  95. {
  96. return _find_next_bit(addr, NULL, size, offset, ~0UL);
  97. }
  98. #endif
  99. #ifndef find_next_and_bit
  100. unsigned long find_next_and_bit(const unsigned long *addr1,
  101. const unsigned long *addr2, unsigned long size,
  102. unsigned long offset)
  103. {
  104. return _find_next_bit(addr1, addr2, size, offset, 0UL);
  105. }
  106. #endif