Home | History | Annotate | Download | only in gesture_detection 
      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 
     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 inde 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 
    104  private:
    105 #if defined(COMPILER_GCC) || defined(__clang__)
    106   static inline uint32_t popcnt(uint32_t v) { return __builtin_popcount(v); }
    107   static inline uint32_t clz(uint32_t v) { return __builtin_clz(v); }
    108   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