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