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
11namespace 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.
17struct 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