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 5 #ifndef UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_ 6 #define UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_ 7 8 #include "base/basictypes.h" 9 #include "base/logging.h" 10 11 namespace ui { 12 13 // Port of BitSet32 from Android 14 // * platform/system/core/include/utils/BitSet.h 15 // * Change-Id: I9bbf41f9d2d4a2593b0e6d7d8be7e283f985bade 16 // * Please update the Change-Id as upstream Android changes are pulled. 17 struct BitSet32 { 18 uint32_t value; 19 BitSet32BitSet3220 inline BitSet32() : value(0) {} BitSet32BitSet3221 explicit inline BitSet32(uint32_t value) : value(value) {} 22 23 // Gets the value associated with a particular bit index. value_for_bitBitSet3224 static inline uint32_t value_for_bit(uint32_t n) { 25 DCHECK_LE(n, 31U); 26 return 0x80000000 >> n; 27 } 28 29 // Clears the bit set. clearBitSet3230 inline void clear() { value = 0; } 31 32 // Returns the number of marked bits in the set. countBitSet3233 inline uint32_t count() const { return popcnt(value); } 34 35 // Returns true if the bit set does not contain any marked bits. is_emptyBitSet3236 inline bool is_empty() const { return !value; } 37 38 // Returns true if the bit set does not contain any unmarked bits. is_fullBitSet3239 inline bool is_full() const { return value == 0xffffffff; } 40 41 // Returns true if the specified bit is marked. has_bitBitSet3242 inline bool has_bit(uint32_t n) const { 43 return (value & value_for_bit(n)) != 0; 44 } 45 46 // Marks the specified bit. mark_bitBitSet3247 inline void mark_bit(uint32_t n) { value |= value_for_bit(n); } 48 49 // Clears the specified bit. clear_bitBitSet3250 inline void clear_bit(uint32_t n) { value &= ~value_for_bit(n); } 51 52 // Finds the first marked bit in the set. 53 // Result is undefined if all bits are unmarked. first_marked_bitBitSet3254 inline uint32_t first_marked_bit() const { return clz(value); } 55 56 // Finds the first unmarked bit in the set. 57 // Result is undefined if all bits are marked. first_unmarked_bitBitSet3258 inline uint32_t first_unmarked_bit() const { return clz(~value); } 59 60 // Finds the last marked bit in the set. 61 // Result is undefined if all bits are unmarked. last_marked_bitBitSet3262 inline uint32_t last_marked_bit() const { return 31 - ctz(value); } 63 64 // Finds the first marked bit in the set and clears it. Returns the bit 65 // index. 66 // Result is undefined if all bits are unmarked. clear_first_marked_bitBitSet3267 inline uint32_t clear_first_marked_bit() { 68 uint32_t n = first_marked_bit(); 69 clear_bit(n); 70 return n; 71 } 72 73 // Finds the first unmarked bit in the set and marks it. Returns the bit 74 // index. 75 // Result is undefined if all bits are marked. mark_first_unmarked_bitBitSet3276 inline uint32_t mark_first_unmarked_bit() { 77 uint32_t n = first_unmarked_bit(); 78 mark_bit(n); 79 return n; 80 } 81 82 // Finds the last marked bit in the set and clears it. Returns the bit index. 83 // Result is undefined if all bits are unmarked. clear_last_marked_bitBitSet3284 inline uint32_t clear_last_marked_bit() { 85 uint32_t n = last_marked_bit(); 86 clear_bit(n); 87 return n; 88 } 89 90 // Gets the inde of the specified bit in the set, which is the number of 91 // marked bits that appear before the specified bit. get_index_of_bitBitSet3292 inline uint32_t get_index_of_bit(uint32_t n) const { 93 DCHECK_LE(n, 31U); 94 return popcnt(value & ~(0xffffffffUL >> n)); 95 } 96 97 inline bool operator==(const BitSet32& other) const { 98 return value == other.value; 99 } 100 inline bool operator!=(const BitSet32& other) const { 101 return value != other.value; 102 } 103 104 private: 105 #if defined(COMPILER_GCC) || defined(__clang__) popcntBitSet32106 static inline uint32_t popcnt(uint32_t v) { return __builtin_popcount(v); } clzBitSet32107 static inline uint32_t clz(uint32_t v) { return __builtin_clz(v); } ctzBitSet32108 static inline uint32_t ctz(uint32_t v) { return __builtin_ctz(v); } 109 #else 110 // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 111 static inline uint32_t popcnt(uint32_t v) { 112 v = v - ((v >> 1) & 0x55555555); 113 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 114 return (((v + (v >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; 115 } 116 // TODO(jdduke): Use intrinsics (BitScan{Forward,Reverse}) with MSVC. 117 static inline uint32_t clz(uint32_t v) { 118 v |= (v >> 1); 119 v |= (v >> 2); 120 v |= (v >> 4); 121 v |= (v >> 8); 122 v |= (v >> 16); 123 return 32 - popcnt(v); 124 } 125 static inline uint32_t ctz(uint32_t v) { 126 return popcnt((v & static_cast<uint32_t>(-static_cast<int>(v))) - 1); 127 } 128 #endif 129 }; 130 131 } // namespace ui 132 133 #endif // UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_ 134