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 | |
9 | namespace taichi { |
10 | |
11 | namespace bit { |
12 | |
13 | Bitset::Bitset() { |
14 | } |
15 | |
16 | Bitset::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 | |
23 | std::size_t Bitset::size() const { |
24 | return vec_.size() * kBits; |
25 | } |
26 | |
27 | void Bitset::reset() { |
28 | for (auto &value : vec_) { |
29 | value = 0; |
30 | } |
31 | } |
32 | |
33 | void Bitset::flip(int x) { |
34 | vec_[x / kBits] ^= ((value_t)1) << (x % kBits); |
35 | } |
36 | |
37 | bool Bitset::any() const { |
38 | for (auto &val : vec_) { |
39 | if (val) |
40 | return true; |
41 | } |
42 | return false; |
43 | } |
44 | |
45 | bool Bitset::none() const { |
46 | return !any(); |
47 | } |
48 | |
49 | Bitset::reference Bitset::operator[](int x) { |
50 | return reference(vec_, x); |
51 | } |
52 | |
53 | Bitset &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 | |
62 | Bitset Bitset::operator&(const Bitset &other) const { |
63 | Bitset result = *this; |
64 | result &= other; |
65 | return result; |
66 | } |
67 | |
68 | Bitset &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 | |
77 | Bitset Bitset::operator|(const Bitset &other) const { |
78 | Bitset result = *this; |
79 | result |= other; |
80 | return result; |
81 | } |
82 | |
83 | Bitset &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 | |
92 | Bitset 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 | |
101 | int Bitset::find_first_one() const { |
102 | return lower_bound(0); |
103 | } |
104 | |
105 | int 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 | |
128 | std::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 | |
146 | Bitset::reference::reference(std::vector<value_t> &vec, int x) |
147 | : pos_(&vec[x / kBits]), digit_(((value_t)1) << (x % kBits)) { |
148 | } |
149 | |
150 | Bitset::reference::operator bool() const { |
151 | return *pos_ & digit_; |
152 | } |
153 | |
154 | bool Bitset::reference::operator~() const { |
155 | return ~*pos_ & digit_; |
156 | } |
157 | |
158 | Bitset::reference &Bitset::reference::operator=(bool x) { |
159 | if (x) |
160 | *pos_ |= digit_; |
161 | else |
162 | *pos_ &= kMask ^ digit_; |
163 | return *this; |
164 | } |
165 | |
166 | Bitset::reference &Bitset::reference::operator=( |
167 | const Bitset::reference &other) { |
168 | *this = bool(other); |
169 | return *this; |
170 | } |
171 | |
172 | Bitset::reference &Bitset::reference::flip() { |
173 | *pos_ ^= digit_; |
174 | return *this; |
175 | } |
176 | |
177 | std::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 | |
186 | using namespace bit; |
187 | |
188 | struct 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 | |
195 | TI_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 | |