bitset_32.h 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163
  1. // Copyright 2014 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_
  5. #define UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_
  6. #include <stdint.h>
  7. #include "base/check_op.h"
  8. namespace ui {
  9. // Port of BitSet32 from Android
  10. // * platform/system/core/include/utils/BitSet.h
  11. // * Change-Id: 02c9460a0a05f27e0501f9e64cdf24091e7d3579
  12. // * Please update the Change-Id as upstream Android changes are pulled.
  13. struct BitSet32 {
  14. uint32_t value;
  15. inline BitSet32() : value(0) {}
  16. explicit inline BitSet32(uint32_t value) : value(value) {}
  17. // Gets the value associated with a particular bit index.
  18. static inline uint32_t value_for_bit(uint32_t n) {
  19. DCHECK_LE(n, 31U);
  20. return 0x80000000 >> n;
  21. }
  22. // Clears the bit set.
  23. inline void clear() { value = 0; }
  24. // Returns the number of marked bits in the set.
  25. inline uint32_t count() const { return popcnt(value); }
  26. // Returns true if the bit set does not contain any marked bits.
  27. inline bool is_empty() const { return !value; }
  28. // Returns true if the bit set does not contain any unmarked bits.
  29. inline bool is_full() const { return value == 0xffffffff; }
  30. // Returns true if the specified bit is marked.
  31. inline bool has_bit(uint32_t n) const {
  32. return (value & value_for_bit(n)) != 0;
  33. }
  34. // Marks the specified bit.
  35. inline void mark_bit(uint32_t n) { value |= value_for_bit(n); }
  36. // Clears the specified bit.
  37. inline void clear_bit(uint32_t n) { value &= ~value_for_bit(n); }
  38. // Finds the first marked bit in the set.
  39. // Result is undefined if all bits are unmarked.
  40. inline uint32_t first_marked_bit() const { return clz(value); }
  41. // Finds the first unmarked bit in the set.
  42. // Result is undefined if all bits are marked.
  43. inline uint32_t first_unmarked_bit() const { return clz(~value); }
  44. // Finds the last marked bit in the set.
  45. // Result is undefined if all bits are unmarked.
  46. inline uint32_t last_marked_bit() const { return 31 - ctz(value); }
  47. // Finds the first marked bit in the set and clears it. Returns the bit
  48. // index.
  49. // Result is undefined if all bits are unmarked.
  50. inline uint32_t clear_first_marked_bit() {
  51. uint32_t n = first_marked_bit();
  52. clear_bit(n);
  53. return n;
  54. }
  55. // Finds the first unmarked bit in the set and marks it. Returns the bit
  56. // index.
  57. // Result is undefined if all bits are marked.
  58. inline uint32_t mark_first_unmarked_bit() {
  59. uint32_t n = first_unmarked_bit();
  60. mark_bit(n);
  61. return n;
  62. }
  63. // Finds the last marked bit in the set and clears it. Returns the bit index.
  64. // Result is undefined if all bits are unmarked.
  65. inline uint32_t clear_last_marked_bit() {
  66. uint32_t n = last_marked_bit();
  67. clear_bit(n);
  68. return n;
  69. }
  70. // Gets the index of the specified bit in the set, which is the number of
  71. // marked bits that appear before the specified bit.
  72. inline uint32_t get_index_of_bit(uint32_t n) const {
  73. DCHECK_LE(n, 31U);
  74. return popcnt(value & ~(0xffffffffUL >> n));
  75. }
  76. inline bool operator==(const BitSet32& other) const {
  77. return value == other.value;
  78. }
  79. inline bool operator!=(const BitSet32& other) const {
  80. return value != other.value;
  81. }
  82. inline BitSet32 operator&(const BitSet32& other) const {
  83. return BitSet32(value & other.value);
  84. }
  85. inline BitSet32& operator&=(const BitSet32& other) {
  86. value &= other.value;
  87. return *this;
  88. }
  89. inline BitSet32 operator|(const BitSet32& other) const {
  90. return BitSet32(value | other.value);
  91. }
  92. inline BitSet32& operator|=(const BitSet32& other) {
  93. value |= other.value;
  94. return *this;
  95. }
  96. private:
  97. #if defined(COMPILER_GCC) || defined(__clang__)
  98. static inline uint32_t popcnt(uint32_t v) { return __builtin_popcountl(v); }
  99. // We use these helpers as the signature of __builtin_c{l,t}z has
  100. // "unsigned int" for the input, which is only guaranteed to be 16b, not 32.
  101. // The compiler should optimize this away.
  102. static inline uint32_t clz(uint32_t v) {
  103. if (sizeof(unsigned int) == sizeof(uint32_t)) {
  104. return __builtin_clz(v);
  105. } else {
  106. return __builtin_clzl(v);
  107. }
  108. }
  109. static inline uint32_t ctz(uint32_t v) {
  110. if (sizeof(unsigned int) == sizeof(uint32_t)) {
  111. return __builtin_ctz(v);
  112. } else {
  113. return __builtin_ctzl(v);
  114. }
  115. }
  116. #else
  117. // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
  118. static inline uint32_t popcnt(uint32_t v) {
  119. v = v - ((v >> 1) & 0x55555555);
  120. v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  121. return (((v + (v >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
  122. }
  123. // TODO(jdduke): Use intrinsics (BitScan{Forward,Reverse}) with MSVC.
  124. static inline uint32_t clz(uint32_t v) {
  125. v |= (v >> 1);
  126. v |= (v >> 2);
  127. v |= (v >> 4);
  128. v |= (v >> 8);
  129. v |= (v >> 16);
  130. return 32 - popcnt(v);
  131. }
  132. static inline uint32_t ctz(uint32_t v) {
  133. return popcnt((v & static_cast<uint32_t>(-static_cast<int>(v))) - 1);
  134. }
  135. #endif
  136. };
  137. } // namespace ui
  138. #endif // UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_