10b57cec5SDimitry Andric //===- FuzzerValueBitMap.h - INTERNAL - Bit map -----------------*- C++ -* ===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // ValueBitMap. 90b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 100b57cec5SDimitry Andric 110b57cec5SDimitry Andric #ifndef LLVM_FUZZER_VALUE_BIT_MAP_H 120b57cec5SDimitry Andric #define LLVM_FUZZER_VALUE_BIT_MAP_H 130b57cec5SDimitry Andric 14*5ffd83dbSDimitry Andric #include "FuzzerPlatform.h" 15*5ffd83dbSDimitry Andric #include <cstdint> 160b57cec5SDimitry Andric 170b57cec5SDimitry Andric namespace fuzzer { 180b57cec5SDimitry Andric 190b57cec5SDimitry Andric // A bit map containing kMapSizeInWords bits. 200b57cec5SDimitry Andric struct ValueBitMap { 210b57cec5SDimitry Andric static const size_t kMapSizeInBits = 1 << 16; 220b57cec5SDimitry Andric static const size_t kMapPrimeMod = 65371; // Largest Prime < kMapSizeInBits; 230b57cec5SDimitry Andric static const size_t kBitsInWord = (sizeof(uintptr_t) * 8); 240b57cec5SDimitry Andric static const size_t kMapSizeInWords = kMapSizeInBits / kBitsInWord; 250b57cec5SDimitry Andric public: 260b57cec5SDimitry Andric 270b57cec5SDimitry Andric // Clears all bits. ResetValueBitMap280b57cec5SDimitry Andric void Reset() { memset(Map, 0, sizeof(Map)); } 290b57cec5SDimitry Andric 300b57cec5SDimitry Andric // Computes a hash function of Value and sets the corresponding bit. 310b57cec5SDimitry Andric // Returns true if the bit was changed from 0 to 1. 320b57cec5SDimitry Andric ATTRIBUTE_NO_SANITIZE_ALL AddValueValueBitMap330b57cec5SDimitry Andric inline bool AddValue(uintptr_t Value) { 340b57cec5SDimitry Andric uintptr_t Idx = Value % kMapSizeInBits; 350b57cec5SDimitry Andric uintptr_t WordIdx = Idx / kBitsInWord; 360b57cec5SDimitry Andric uintptr_t BitIdx = Idx % kBitsInWord; 370b57cec5SDimitry Andric uintptr_t Old = Map[WordIdx]; 380b57cec5SDimitry Andric uintptr_t New = Old | (1ULL << BitIdx); 390b57cec5SDimitry Andric Map[WordIdx] = New; 400b57cec5SDimitry Andric return New != Old; 410b57cec5SDimitry Andric } 420b57cec5SDimitry Andric 430b57cec5SDimitry Andric ATTRIBUTE_NO_SANITIZE_ALL AddValueModPrimeValueBitMap440b57cec5SDimitry Andric inline bool AddValueModPrime(uintptr_t Value) { 450b57cec5SDimitry Andric return AddValue(Value % kMapPrimeMod); 460b57cec5SDimitry Andric } 470b57cec5SDimitry Andric GetValueBitMap480b57cec5SDimitry Andric inline bool Get(uintptr_t Idx) { 490b57cec5SDimitry Andric assert(Idx < kMapSizeInBits); 500b57cec5SDimitry Andric uintptr_t WordIdx = Idx / kBitsInWord; 510b57cec5SDimitry Andric uintptr_t BitIdx = Idx % kBitsInWord; 520b57cec5SDimitry Andric return Map[WordIdx] & (1ULL << BitIdx); 530b57cec5SDimitry Andric } 540b57cec5SDimitry Andric SizeInBitsValueBitMap550b57cec5SDimitry Andric size_t SizeInBits() const { return kMapSizeInBits; } 560b57cec5SDimitry Andric 570b57cec5SDimitry Andric template <class Callback> 580b57cec5SDimitry Andric ATTRIBUTE_NO_SANITIZE_ALL ForEachValueBitMap590b57cec5SDimitry Andric void ForEach(Callback CB) const { 600b57cec5SDimitry Andric for (size_t i = 0; i < kMapSizeInWords; i++) 610b57cec5SDimitry Andric if (uintptr_t M = Map[i]) 620b57cec5SDimitry Andric for (size_t j = 0; j < sizeof(M) * 8; j++) 630b57cec5SDimitry Andric if (M & ((uintptr_t)1 << j)) 640b57cec5SDimitry Andric CB(i * sizeof(M) * 8 + j); 650b57cec5SDimitry Andric } 660b57cec5SDimitry Andric 670b57cec5SDimitry Andric private: 680b57cec5SDimitry Andric ATTRIBUTE_ALIGNED(512) uintptr_t Map[kMapSizeInWords]; 690b57cec5SDimitry Andric }; 700b57cec5SDimitry Andric 710b57cec5SDimitry Andric } // namespace fuzzer 720b57cec5SDimitry Andric 730b57cec5SDimitry Andric #endif // LLVM_FUZZER_VALUE_BIT_MAP_H 74