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 17namespace fuzzer { 18 19// A bit map containing kMapSizeInWords bits. 20struct ValueBitMap { 21 static const size_t kMapSizeInBits = 1 << 16; 22 static const size_t kMapPrimeMod = 65371; // Largest Prime < kMapSizeInBits; 23 static const size_t kBitsInWord = (sizeof(uintptr_t) * 8); 24 static const size_t kMapSizeInWords = kMapSizeInBits / kBitsInWord; 25 public: 26 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 ATTRIBUTE_NO_SANITIZE_ALL 33 inline bool AddValue(uintptr_t Value) { 34 uintptr_t Idx = Value % kMapSizeInBits; 35 uintptr_t WordIdx = Idx / kBitsInWord; 36 uintptr_t BitIdx = Idx % kBitsInWord; 37 uintptr_t Old = Map[WordIdx]; 38 uintptr_t New = Old | (1UL << BitIdx); 39 Map[WordIdx] = New; 40 return New != Old; 41 } 42 43 ATTRIBUTE_NO_SANITIZE_ALL 44 inline bool AddValueModPrime(uintptr_t Value) { 45 return AddValue(Value % kMapPrimeMod); 46 } 47 48 inline bool Get(uintptr_t Idx) { 49 assert(Idx < kMapSizeInBits); 50 uintptr_t WordIdx = Idx / kBitsInWord; 51 uintptr_t BitIdx = Idx % kBitsInWord; 52 return Map[WordIdx] & (1UL << BitIdx); 53 } 54 55 size_t GetNumBitsSinceLastMerge() const { return NumBits; } 56 57 // Merges 'Other' into 'this', clears 'Other', updates NumBits, 58 // returns true if new bits were added. 59 ATTRIBUTE_TARGET_POPCNT 60 bool MergeFrom(ValueBitMap &Other) { 61 uintptr_t Res = 0; 62 size_t OldNumBits = NumBits; 63 for (size_t i = 0; i < kMapSizeInWords; i++) { 64 auto O = Other.Map[i]; 65 auto M = Map[i]; 66 if (O) { 67 Map[i] = (M |= O); 68 Other.Map[i] = 0; 69 } 70 if (M) 71 Res += __builtin_popcountll(M); 72 } 73 NumBits = Res; 74 return OldNumBits < NumBits; 75 } 76 77 template <class Callback> 78 ATTRIBUTE_NO_SANITIZE_ALL 79 void ForEach(Callback CB) const { 80 for (size_t i = 0; i < kMapSizeInWords; i++) 81 if (uintptr_t M = Map[i]) 82 for (size_t j = 0; j < sizeof(M) * 8; j++) 83 if (M & ((uintptr_t)1 << j)) 84 CB(i * sizeof(M) * 8 + j); 85 } 86 87 private: 88 size_t NumBits = 0; 89 uintptr_t Map[kMapSizeInWords] __attribute__((aligned(512))); 90}; 91 92} // namespace fuzzer 93 94#endif // LLVM_FUZZER_VALUE_BIT_MAP_H 95