]>
Commit | Line | Data |
---|---|---|
1e59de90 TL |
1 | //===- FuzzerValueBitMap.h - INTERNAL - Bit map -----------------*- C++ -* ===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // ValueBitMap. | |
10 | //===----------------------------------------------------------------------===// | |
11 | ||
12 | #ifndef LLVM_FUZZER_VALUE_BIT_MAP_H | |
13 | #define LLVM_FUZZER_VALUE_BIT_MAP_H | |
14 | ||
15 | #include "FuzzerDefs.h" | |
16 | ||
17 | namespace fuzzer { | |
18 | ||
19 | // A bit map containing kMapSizeInWords bits. | |
20 | struct ValueBitMap { | |
21 | static const size_t kMapSizeInBits = 65371; // Prime. | |
22 | static const size_t kMapSizeInBitsAligned = 65536; // 2^16 | |
23 | static const size_t kBitsInWord = (sizeof(uintptr_t) * 8); | |
24 | static const size_t kMapSizeInWords = kMapSizeInBitsAligned / kBitsInWord; | |
25 | public: | |
26 | static const size_t kNumberOfItems = kMapSizeInBits; | |
27 | // Clears all bits. | |
28 | void Reset() { memset(Map, 0, sizeof(Map)); } | |
29 | ||
30 | // Computes a hash function of Value and sets the corresponding bit. | |
31 | // Returns true if the bit was changed from 0 to 1. | |
32 | inline bool AddValue(uintptr_t Value) { | |
33 | uintptr_t Idx = Value < kMapSizeInBits ? Value : Value % kMapSizeInBits; | |
34 | uintptr_t WordIdx = Idx / kBitsInWord; | |
35 | uintptr_t BitIdx = Idx % kBitsInWord; | |
36 | uintptr_t Old = Map[WordIdx]; | |
37 | uintptr_t New = Old | (1UL << BitIdx); | |
38 | Map[WordIdx] = New; | |
39 | return New != Old; | |
40 | } | |
41 | ||
42 | inline bool Get(uintptr_t Idx) { | |
43 | assert(Idx < kMapSizeInBits); | |
44 | uintptr_t WordIdx = Idx / kBitsInWord; | |
45 | uintptr_t BitIdx = Idx % kBitsInWord; | |
46 | return Map[WordIdx] & (1UL << BitIdx); | |
47 | } | |
48 | ||
49 | size_t GetNumBitsSinceLastMerge() const { return NumBits; } | |
50 | ||
51 | // Merges 'Other' into 'this', clears 'Other', updates NumBits, | |
52 | // returns true if new bits were added. | |
53 | ATTRIBUTE_TARGET_POPCNT | |
54 | bool MergeFrom(ValueBitMap &Other) { | |
55 | uintptr_t Res = 0; | |
56 | size_t OldNumBits = NumBits; | |
57 | for (size_t i = 0; i < kMapSizeInWords; i++) { | |
58 | auto O = Other.Map[i]; | |
59 | auto M = Map[i]; | |
60 | if (O) { | |
61 | Map[i] = (M |= O); | |
62 | Other.Map[i] = 0; | |
63 | } | |
64 | if (M) | |
65 | Res += __builtin_popcountl(M); | |
66 | } | |
67 | NumBits = Res; | |
68 | return OldNumBits < NumBits; | |
69 | } | |
70 | ||
71 | template <class Callback> | |
72 | void ForEach(Callback CB) { | |
73 | for (size_t i = 0; i < kMapSizeInWords; i++) | |
74 | if (uintptr_t M = Map[i]) | |
75 | for (size_t j = 0; j < sizeof(M) * 8; j++) | |
76 | if (M & ((uintptr_t)1 << j)) | |
77 | CB(i * sizeof(M) * 8 + j); | |
78 | } | |
79 | ||
80 | private: | |
81 | size_t NumBits = 0; | |
82 | uintptr_t Map[kMapSizeInWords] __attribute__((aligned(512))); | |
83 | }; | |
84 | ||
85 | } // namespace fuzzer | |
86 | ||
87 | #endif // LLVM_FUZZER_VALUE_BIT_MAP_H |