1/*
2 * Copyright (C) 2012, 2013, 2016 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <string.h>
29#include <wtf/Atomics.h>
30#include <wtf/FastMalloc.h>
31#include <wtf/PrintStream.h>
32#include <wtf/StdLibExtras.h>
33
34namespace WTF {
35
36class PrintStream;
37
38inline size_t fastBitVectorArrayLength(size_t numBits) { return (numBits + 31) / 32; }
39
40class FastBitVectorWordView {
41public:
42 typedef FastBitVectorWordView ViewType;
43
44 FastBitVectorWordView() { }
45
46 FastBitVectorWordView(const uint32_t* array, size_t numBits)
47 : m_words(array)
48 , m_numBits(numBits)
49 {
50 }
51
52 size_t numBits() const
53 {
54 return m_numBits;
55 }
56
57 uint32_t word(size_t index) const
58 {
59 ASSERT_WITH_SECURITY_IMPLICATION(index < fastBitVectorArrayLength(numBits()));
60 return m_words[index];
61 }
62
63private:
64 const uint32_t* m_words { nullptr };
65 size_t m_numBits { 0 };
66};
67
68class FastBitVectorWordOwner {
69public:
70 typedef FastBitVectorWordView ViewType;
71
72 FastBitVectorWordOwner() = default;
73
74 FastBitVectorWordOwner(FastBitVectorWordOwner&& other)
75 : m_words(std::exchange(other.m_words, nullptr))
76 , m_numBits(std::exchange(other.m_numBits, 0))
77 {
78 }
79
80 FastBitVectorWordOwner(const FastBitVectorWordOwner& other)
81 {
82 *this = other;
83 }
84
85 ~FastBitVectorWordOwner()
86 {
87 if (m_words)
88 fastFree(m_words);
89 }
90
91 FastBitVectorWordView view() const { return FastBitVectorWordView(m_words, m_numBits); }
92
93 FastBitVectorWordOwner& operator=(const FastBitVectorWordOwner& other)
94 {
95 if (arrayLength() != other.arrayLength())
96 setEqualsSlow(other);
97 else {
98 memcpy(m_words, other.m_words, arrayLength() * sizeof(uint32_t));
99 m_numBits = other.m_numBits;
100 }
101 return *this;
102 }
103
104 FastBitVectorWordOwner& operator=(FastBitVectorWordOwner&& other)
105 {
106 std::swap(m_words, other.m_words);
107 std::swap(m_numBits, other.m_numBits);
108 return *this;
109 }
110
111 void setAll()
112 {
113 memset(m_words, 255, arrayLength() * sizeof(uint32_t));
114 }
115
116 void clearAll()
117 {
118 memset(m_words, 0, arrayLength() * sizeof(uint32_t));
119 }
120
121 void set(const FastBitVectorWordOwner& other)
122 {
123 ASSERT_WITH_SECURITY_IMPLICATION(m_numBits == other.m_numBits);
124 memcpy(m_words, other.m_words, arrayLength() * sizeof(uint32_t));
125 }
126
127 size_t numBits() const
128 {
129 return m_numBits;
130 }
131
132 size_t arrayLength() const
133 {
134 return fastBitVectorArrayLength(numBits());
135 }
136
137 void resize(size_t numBits)
138 {
139 if (arrayLength() != fastBitVectorArrayLength(numBits))
140 resizeSlow(numBits);
141 m_numBits = numBits;
142 }
143
144 uint32_t word(size_t index) const
145 {
146 ASSERT_WITH_SECURITY_IMPLICATION(index < arrayLength());
147 return m_words[index];
148 }
149
150 uint32_t& word(size_t index)
151 {
152 ASSERT_WITH_SECURITY_IMPLICATION(index < arrayLength());
153 return m_words[index];
154 }
155
156 const uint32_t* words() const { return m_words; }
157 uint32_t* words() { return m_words; }
158
159private:
160 WTF_EXPORT_PRIVATE void setEqualsSlow(const FastBitVectorWordOwner& other);
161 WTF_EXPORT_PRIVATE void resizeSlow(size_t numBits);
162
163 uint32_t* m_words { nullptr };
164 size_t m_numBits { 0 };
165};
166
167template<typename Left, typename Right>
168class FastBitVectorAndWords {
169public:
170 typedef FastBitVectorAndWords ViewType;
171
172 FastBitVectorAndWords(const Left& left, const Right& right)
173 : m_left(left)
174 , m_right(right)
175 {
176 ASSERT_WITH_SECURITY_IMPLICATION(m_left.numBits() == m_right.numBits());
177 }
178
179 FastBitVectorAndWords view() const { return *this; }
180
181 size_t numBits() const
182 {
183 return m_left.numBits();
184 }
185
186 uint32_t word(size_t index) const
187 {
188 return m_left.word(index) & m_right.word(index);
189 }
190
191private:
192 Left m_left;
193 Right m_right;
194};
195
196template<typename Left, typename Right>
197class FastBitVectorOrWords {
198public:
199 typedef FastBitVectorOrWords ViewType;
200
201 FastBitVectorOrWords(const Left& left, const Right& right)
202 : m_left(left)
203 , m_right(right)
204 {
205 ASSERT_WITH_SECURITY_IMPLICATION(m_left.numBits() == m_right.numBits());
206 }
207
208 FastBitVectorOrWords view() const { return *this; }
209
210 size_t numBits() const
211 {
212 return m_left.numBits();
213 }
214
215 uint32_t word(size_t index) const
216 {
217 return m_left.word(index) | m_right.word(index);
218 }
219
220private:
221 Left m_left;
222 Right m_right;
223};
224
225template<typename View>
226class FastBitVectorNotWords {
227public:
228 typedef FastBitVectorNotWords ViewType;
229
230 FastBitVectorNotWords(const View& view)
231 : m_view(view)
232 {
233 }
234
235 FastBitVectorNotWords view() const { return *this; }
236
237 size_t numBits() const
238 {
239 return m_view.numBits();
240 }
241
242 uint32_t word(size_t index) const
243 {
244 return ~m_view.word(index);
245 }
246
247private:
248 View m_view;
249};
250
251class FastBitVector;
252
253template<typename Words>
254class FastBitVectorImpl {
255public:
256 FastBitVectorImpl()
257 : m_words()
258 {
259 }
260
261 FastBitVectorImpl(const Words& words)
262 : m_words(words)
263 {
264 }
265
266 FastBitVectorImpl(Words&& words)
267 : m_words(WTFMove(words))
268 {
269 }
270
271 size_t numBits() const { return m_words.numBits(); }
272 size_t size() const { return numBits(); }
273
274 size_t arrayLength() const { return fastBitVectorArrayLength(numBits()); }
275
276 template<typename Other>
277 bool operator==(const Other& other) const
278 {
279 if (numBits() != other.numBits())
280 return false;
281 for (size_t i = arrayLength(); i--;) {
282 if (m_words.word(i) != other.m_words.word(i))
283 return false;
284 }
285 return true;
286 }
287
288 template<typename Other>
289 bool operator!=(const Other& other) const
290 {
291 return !(*this == other);
292 }
293
294 bool at(size_t index) const
295 {
296 return atImpl(index);
297 }
298
299 bool operator[](size_t index) const
300 {
301 return atImpl(index);
302 }
303
304 size_t bitCount() const
305 {
306 size_t result = 0;
307 for (size_t index = arrayLength(); index--;)
308 result += WTF::bitCount(m_words.word(index));
309 return result;
310 }
311
312 bool isEmpty() const
313 {
314 for (size_t index = arrayLength(); index--;) {
315 if (m_words.word(index))
316 return false;
317 }
318 return true;
319 }
320
321 template<typename OtherWords>
322 FastBitVectorImpl<FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>> operator&(const FastBitVectorImpl<OtherWords>& other) const
323 {
324 return FastBitVectorImpl<FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>>(FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>(wordView(), other.wordView()));
325 }
326
327 template<typename OtherWords>
328 FastBitVectorImpl<FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>> operator|(const FastBitVectorImpl<OtherWords>& other) const
329 {
330 return FastBitVectorImpl<FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>>(FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>(wordView(), other.wordView()));
331 }
332
333 FastBitVectorImpl<FastBitVectorNotWords<typename Words::ViewType>> operator~() const
334 {
335 return FastBitVectorImpl<FastBitVectorNotWords<typename Words::ViewType>>(FastBitVectorNotWords<typename Words::ViewType>(wordView()));
336 }
337
338 template<typename Func>
339 ALWAYS_INLINE void forEachSetBit(const Func& func) const
340 {
341 size_t n = arrayLength();
342 for (size_t i = 0; i < n; ++i) {
343 uint32_t word = m_words.word(i);
344 size_t j = i * 32;
345 while (word) {
346 if (word & 1)
347 func(j);
348 word >>= 1;
349 j++;
350 }
351 }
352 }
353
354 template<typename Func>
355 ALWAYS_INLINE void forEachClearBit(const Func& func) const
356 {
357 (~*this).forEachSetBit(func);
358 }
359
360 template<typename Func>
361 void forEachBit(bool value, const Func& func) const
362 {
363 if (value)
364 forEachSetBit(func);
365 else
366 forEachClearBit(func);
367 }
368
369 // Starts looking for bits at the index you pass. If that index contains the value you want,
370 // then it will return that index. Returns numBits when we get to the end. For example, you
371 // can write a loop to iterate over all set bits like this:
372 //
373 // for (size_t i = 0; i < bits.numBits(); i = bits.findBit(i + 1, true))
374 // ...
375 ALWAYS_INLINE size_t findBit(size_t startIndex, bool value) const
376 {
377 // If value is true, this produces 0. If value is false, this produces UINT_MAX. It's
378 // written this way so that it performs well regardless of whether value is a constant.
379 uint32_t skipValue = -(static_cast<uint32_t>(value) ^ 1);
380
381 size_t numWords = fastBitVectorArrayLength(m_words.numBits());
382
383 size_t wordIndex = startIndex / 32;
384 size_t startIndexInWord = startIndex - wordIndex * 32;
385
386 while (wordIndex < numWords) {
387 uint32_t word = m_words.word(wordIndex);
388 if (word != skipValue) {
389 size_t index = startIndexInWord;
390 if (findBitInWord(word, index, 32, value))
391 return wordIndex * 32 + index;
392 }
393
394 wordIndex++;
395 startIndexInWord = 0;
396 }
397
398 return numBits();
399 }
400
401 ALWAYS_INLINE size_t findSetBit(size_t index) const
402 {
403 return findBit(index, true);
404 }
405
406 ALWAYS_INLINE size_t findClearBit(size_t index) const
407 {
408 return findBit(index, false);
409 }
410
411 void dump(PrintStream& out) const
412 {
413 for (size_t i = 0; i < numBits(); ++i)
414 out.print((*this)[i] ? "1" : "-");
415 }
416
417 typename Words::ViewType wordView() const { return m_words.view(); }
418
419private:
420 // You'd think that we could remove this friend if we used protected, but you'd be wrong,
421 // because templates.
422 friend class FastBitVector;
423
424 bool atImpl(size_t index) const
425 {
426 ASSERT_WITH_SECURITY_IMPLICATION(index < numBits());
427 return !!(m_words.word(index >> 5) & (1 << (index & 31)));
428 }
429
430 Words m_words;
431};
432
433class FastBitVector : public FastBitVectorImpl<FastBitVectorWordOwner> {
434public:
435 FastBitVector() { }
436
437 FastBitVector(const FastBitVector&) = default;
438 FastBitVector& operator=(const FastBitVector&) = default;
439
440 template<typename OtherWords>
441 FastBitVector(const FastBitVectorImpl<OtherWords>& other)
442 {
443 *this = other;
444 }
445
446 template<typename OtherWords>
447 FastBitVector& operator=(const FastBitVectorImpl<OtherWords>& other)
448 {
449 if (UNLIKELY(numBits() != other.numBits()))
450 resize(other.numBits());
451
452 for (unsigned i = arrayLength(); i--;)
453 m_words.word(i) = other.m_words.word(i);
454 return *this;
455 }
456
457 void resize(size_t numBits)
458 {
459 m_words.resize(numBits);
460 }
461
462 void setAll()
463 {
464 m_words.setAll();
465 }
466
467 void clearAll()
468 {
469 m_words.clearAll();
470 }
471
472 WTF_EXPORT_PRIVATE void clearRange(size_t begin, size_t end);
473
474 // Returns true if the contents of this bitvector changed.
475 template<typename OtherWords>
476 bool setAndCheck(const FastBitVectorImpl<OtherWords>& other)
477 {
478 bool changed = false;
479 ASSERT_WITH_SECURITY_IMPLICATION(numBits() == other.numBits());
480 for (unsigned i = arrayLength(); i--;) {
481 changed |= m_words.word(i) != other.m_words.word(i);
482 m_words.word(i) = other.m_words.word(i);
483 }
484 return changed;
485 }
486
487 template<typename OtherWords>
488 FastBitVector& operator|=(const FastBitVectorImpl<OtherWords>& other)
489 {
490 ASSERT_WITH_SECURITY_IMPLICATION(numBits() == other.numBits());
491 for (unsigned i = arrayLength(); i--;)
492 m_words.word(i) |= other.m_words.word(i);
493 return *this;
494 }
495
496 template<typename OtherWords>
497 FastBitVector& operator&=(const FastBitVectorImpl<OtherWords>& other)
498 {
499 ASSERT_WITH_SECURITY_IMPLICATION(numBits() == other.numBits());
500 for (unsigned i = arrayLength(); i--;)
501 m_words.word(i) &= other.m_words.word(i);
502 return *this;
503 }
504
505 bool at(size_t index) const
506 {
507 return atImpl(index);
508 }
509
510 bool operator[](size_t index) const
511 {
512 return atImpl(index);
513 }
514
515 class BitReference {
516 public:
517 BitReference() { }
518
519 BitReference(uint32_t* word, uint32_t mask)
520 : m_word(word)
521 , m_mask(mask)
522 {
523 }
524
525 explicit operator bool() const
526 {
527 return !!(*m_word & m_mask);
528 }
529
530 BitReference& operator=(bool value)
531 {
532 if (value)
533 *m_word |= m_mask;
534 else
535 *m_word &= ~m_mask;
536 return *this;
537 }
538
539 private:
540 uint32_t* m_word { nullptr };
541 uint32_t m_mask { 0 };
542 };
543
544 BitReference at(size_t index)
545 {
546 ASSERT_WITH_SECURITY_IMPLICATION(index < numBits());
547 return BitReference(&m_words.word(index >> 5), 1 << (index & 31));
548 }
549
550 BitReference operator[](size_t index)
551 {
552 return at(index);
553 }
554
555 // Returns true if the contents changed.
556 ALWAYS_INLINE bool atomicSetAndCheck(size_t index, bool value)
557 {
558 uint32_t* pointer = &m_words.word(index >> 5);
559 uint32_t mask = 1 << (index & 31);
560 for (;;) {
561 uint32_t oldValue = *pointer;
562 uint32_t newValue;
563 if (value) {
564 if (oldValue & mask)
565 return false;
566 newValue = oldValue | mask;
567 } else {
568 if (!(oldValue & mask))
569 return false;
570 newValue = oldValue & ~mask;
571 }
572 if (atomicCompareExchangeWeakRelaxed(pointer, oldValue, newValue))
573 return true;
574 }
575 }
576};
577
578} // namespace WTF
579
580using WTF::FastBitVector;
581