ui/events/gesture_detection/bitset_32.h

   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: 02c9460a0a05f27e0501f9e64cdf24091e7d3579
  16 // * Please update the Change-Id as upstream Android changes are pulled.
  17 struct BitSet32 {
  18   uint32_t value;
  19
  20   inline BitSet32() : value(0) {}
  21   explicit inline BitSet32(uint32_t value) : value(value) {}
  22
  23   // Gets the value associated with a particular bit index.
  24   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.
  30   inline void clear() { value = 0; }
  31
  32   // Returns the number of marked bits in the set.
  33   inline uint32_t count() const { return popcnt(value); }
  34
  35   // Returns true if the bit set does not contain any marked bits.
  36   inline bool is_empty() const { return !value; }
  37
  38   // Returns true if the bit set does not contain any unmarked bits.
  39   inline bool is_full() const { return value == 0xffffffff; }
  40
  41   // Returns true if the specified bit is marked.
  42   inline bool has_bit(uint32_t n) const {
  43     return (value & value_for_bit(n)) != 0;
  44   }
  45
  46   // Marks the specified bit.
  47   inline void mark_bit(uint32_t n) { value |= value_for_bit(n); }
  48
  49   // Clears the specified bit.
  50   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.
  54   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.
  58   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.
  62   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.
  67   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.
  76   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.
  84   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 index of the specified bit in the set, which is the number of
  91   // marked bits that appear before the specified bit.
  92   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   inline BitSet32 operator&(const BitSet32& other) const {
 104     return BitSet32(value & other.value);
 105   }
 106   inline BitSet32& operator&=(const BitSet32& other) {
 107     value &= other.value;
 108     return *this;
 109   }
 110   inline BitSet32 operator|(const BitSet32& other) const {
 111     return BitSet32(value | other.value);
 112   }
 113   inline BitSet32& operator|=(const BitSet32& other) {
 114     value |= other.value;
 115     return *this;
 116   }
 117
 118  private:
 119 #if defined(COMPILER_GCC) || defined(__clang__)
 120   static inline uint32_t popcnt(uint32_t v) { return __builtin_popcountl(v); }
 121   // We use these helpers as the signature of __builtin_c{l,t}z has
 122   // "unsigned int" for the input, which is only guaranteed to be 16b, not 32.
 123   // The compiler should optimize this away.
 124   static inline uint32_t clz(uint32_t v) {
 125     if (sizeof(unsigned int) == sizeof(uint32_t)) {
 126       return __builtin_clz(v);
 127     } else {
 128       return __builtin_clzl(v);
 129     }
 130   }
 131   static inline uint32_t ctz(uint32_t v) {
 132     if (sizeof(unsigned int) == sizeof(uint32_t)) {
 133       return __builtin_ctz(v);
 134     } else {
 135       return __builtin_ctzl(v);
 136     }
 137   }
 138 #else
 139   // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
 140   static inline uint32_t popcnt(uint32_t v) {
 141     v = v - ((v >> 1) & 0x55555555);
 142     v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
 143     return (((v + (v >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
 144   }
 145   // TODO(jdduke): Use intrinsics (BitScan{Forward,Reverse}) with MSVC.
 146   static inline uint32_t clz(uint32_t v) {
 147     v |= (v >> 1);
 148     v |= (v >> 2);
 149     v |= (v >> 4);
 150     v |= (v >> 8);
 151     v |= (v >> 16);
 152     return 32 - popcnt(v);
 153   }
 154   static inline uint32_t ctz(uint32_t v) {
 155     return popcnt((v & static_cast<uint32_t>(-static_cast<int>(v))) - 1);
 156   }
 157 #endif
 158 };
 159
 160 }  // namespace ui
 161
 162 #endif  // UI_EVENTS_GESTURE_DETECTION_BITSET_32_H_