1/*******************************************************************************
2 Copyright (c) The Taichi Authors (2016- ). All Rights Reserved.
3 The use of this software is governed by the LICENSE file.
4*******************************************************************************/
5
6#include "taichi/util/testing.h"
7#include "taichi/util/bit.h"
8
9namespace taichi {
10
11namespace bit {
12
13Bitset::Bitset() {
14}
15
16Bitset::Bitset(int n) {
17 if (n % kBits != 0) {
18 n += kBits - n % kBits;
19 }
20 vec_ = std::vector<value_t>(n / kBits, 0);
21}
22
23std::size_t Bitset::size() const {
24 return vec_.size() * kBits;
25}
26
27void Bitset::reset() {
28 for (auto &value : vec_) {
29 value = 0;
30 }
31}
32
33void Bitset::flip(int x) {
34 vec_[x / kBits] ^= ((value_t)1) << (x % kBits);
35}
36
37bool Bitset::any() const {
38 for (auto &val : vec_) {
39 if (val)
40 return true;
41 }
42 return false;
43}
44
45bool Bitset::none() const {
46 return !any();
47}
48
49Bitset::reference Bitset::operator[](int x) {
50 return reference(vec_, x);
51}
52
53Bitset &Bitset::operator&=(const Bitset &other) {
54 const int len = vec_.size();
55 TI_ASSERT(len == other.vec_.size());
56 for (int i = 0; i < len; i++) {
57 vec_[i] &= other.vec_[i];
58 }
59 return *this;
60}
61
62Bitset Bitset::operator&(const Bitset &other) const {
63 Bitset result = *this;
64 result &= other;
65 return result;
66}
67
68Bitset &Bitset::operator|=(const Bitset &other) {
69 const int len = vec_.size();
70 TI_ASSERT(len == other.vec_.size());
71 for (int i = 0; i < len; i++) {
72 vec_[i] |= other.vec_[i];
73 }
74 return *this;
75}
76
77Bitset Bitset::operator|(const Bitset &other) const {
78 Bitset result = *this;
79 result |= other;
80 return result;
81}
82
83Bitset &Bitset::operator^=(const Bitset &other) {
84 const int len = vec_.size();
85 TI_ASSERT(len == other.vec_.size());
86 for (int i = 0; i < len; i++) {
87 vec_[i] ^= other.vec_[i];
88 }
89 return *this;
90}
91
92Bitset Bitset::operator~() const {
93 Bitset result(size());
94 const int len = vec_.size();
95 for (int i = 0; i < len; i++) {
96 result.vec_[i] = ~vec_[i];
97 }
98 return result;
99}
100
101int Bitset::find_first_one() const {
102 return lower_bound(0);
103}
104
105int Bitset::lower_bound(int x) const {
106 const int len = vec_.size();
107 if (x >= len * kBits) {
108 return -1;
109 }
110 if (x < 0) {
111 x = 0;
112 }
113 int i = x / kBits;
114 if (x % kBits != 0) {
115 if (auto test = vec_[i] & (kMask ^ ((1ULL << (x % kBits)) - 1))) {
116 return i * kBits + log2int(lowbit(test));
117 }
118 i++;
119 }
120 for (; i < len; i++) {
121 if (vec_[i]) {
122 return i * kBits + log2int(lowbit(vec_[i]));
123 }
124 }
125 return -1;
126}
127
128std::vector<int> Bitset::or_eq_get_update_list(const Bitset &other) {
129 const int len = vec_.size();
130 TI_ASSERT(len == other.vec_.size());
131 std::vector<int> result;
132 for (int i = 0; i < len; i++) {
133 auto update = other.vec_[i] & ~vec_[i];
134 if (update) {
135 vec_[i] |= update;
136 for (int j = 0; j < kBits; j++) {
137 if ((update >> j) & 1) {
138 result.push_back((i * kBits) | j);
139 }
140 }
141 }
142 }
143 return result;
144}
145
146Bitset::reference::reference(std::vector<value_t> &vec, int x)
147 : pos_(&vec[x / kBits]), digit_(((value_t)1) << (x % kBits)) {
148}
149
150Bitset::reference::operator bool() const {
151 return *pos_ & digit_;
152}
153
154bool Bitset::reference::operator~() const {
155 return ~*pos_ & digit_;
156}
157
158Bitset::reference &Bitset::reference::operator=(bool x) {
159 if (x)
160 *pos_ |= digit_;
161 else
162 *pos_ &= kMask ^ digit_;
163 return *this;
164}
165
166Bitset::reference &Bitset::reference::operator=(
167 const Bitset::reference &other) {
168 *this = bool(other);
169 return *this;
170}
171
172Bitset::reference &Bitset::reference::flip() {
173 *pos_ ^= digit_;
174 return *this;
175}
176
177std::ostream &operator<<(std::ostream &os, const Bitset &b) {
178 for (auto &val : b.vec_)
179 for (int j = 0; j < Bitset::kBits; j++)
180 os << ((val >> j) & 1 ? '1' : '0');
181 return os;
182}
183
184} // namespace bit
185
186using namespace bit;
187
188struct Flags : public Bits<32> {
189 using Base = Bits<32>;
190 TI_BIT_FIELD(bool, apple, 0);
191 TI_BIT_FIELD(bool, banana, 1);
192 TI_BIT_FIELD(uint8, cherry, 2);
193};
194
195TI_TEST("bit") {
196 Bits<32> b;
197 b.set<5>(1);
198 CHECK(b.get() == 32);
199 b.set<10, 8>(255);
200 CHECK(b.get() == 255 * 1024 + 32);
201 b.set<11, 1>(0);
202 CHECK(b.get() == 255 * 1024 + 32 - 2048);
203 b.set<11, 2>(3);
204 CHECK(b.get() == 255 * 1024 + 32);
205 b.set<11, 2>(0);
206 CHECK(b.get() == 255 * 1024 + 32 - 2 * 3072);
207 b.set<11, 2>(1);
208 CHECK(b.get() == 255 * 1024 + 32 - 4096);
209
210 Flags f;
211 f.set_apple(true);
212 CHECK(f.get_apple() == true);
213 f.set_apple(false);
214 CHECK(f.get_apple() == false);
215 f.set_banana(true);
216 CHECK(f.get_banana() == true);
217 CHECK(f.get_apple() == false);
218 f.set_apple(false);
219 CHECK(f.get_apple() == false);
220 f.set_apple(true);
221 f.set_cherry(63);
222 CHECK(f.get_cherry() == 63);
223 f.set_banana(false);
224 CHECK(f.get_cherry() == 63);
225
226 struct Decomp {
227 uint8 a, b, c, d;
228 };
229
230 uint32 v = 0xabcd1234;
231 auto &dec = reinterpret_bits<Decomp>(v);
232 CHECK(dec.a == 0x34);
233 CHECK(dec.b == 0x12);
234 CHECK(dec.c == 0xcd);
235 CHECK(dec.d == 0xab);
236 dec.d = 0xef;
237 CHECK(v == 0xefcd1234);
238
239 CHECK(reinterpret_bits<float32>(reinterpret_bits<uint32>(1.32_f32)) ==
240 1.32_f32);
241
242 // float64 t = 123.456789;
243 // auto e = extract(t);
244 // TI_P(std::get<0>(e));
245 // TI_P(std::get<1>(e));
246 // CHECK(t == compress(std::get<0>(e), std::get<1>(e)));
247}
248} // namespace taichi
249