13cab2bb3Spatrick //===- FuzzerValueBitMap.h - INTERNAL - Bit map -----------------*- C++ -* ===// 23cab2bb3Spatrick // 33cab2bb3Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 43cab2bb3Spatrick // See https://llvm.org/LICENSE.txt for license information. 53cab2bb3Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 63cab2bb3Spatrick // 73cab2bb3Spatrick //===----------------------------------------------------------------------===// 83cab2bb3Spatrick // ValueBitMap. 93cab2bb3Spatrick //===----------------------------------------------------------------------===// 103cab2bb3Spatrick 113cab2bb3Spatrick #ifndef LLVM_FUZZER_VALUE_BIT_MAP_H 123cab2bb3Spatrick #define LLVM_FUZZER_VALUE_BIT_MAP_H 133cab2bb3Spatrick 14*1f9cb04fSpatrick #include "FuzzerPlatform.h" 15*1f9cb04fSpatrick #include <cstdint> 163cab2bb3Spatrick 173cab2bb3Spatrick namespace fuzzer { 183cab2bb3Spatrick 193cab2bb3Spatrick // A bit map containing kMapSizeInWords bits. 203cab2bb3Spatrick struct ValueBitMap { 213cab2bb3Spatrick static const size_t kMapSizeInBits = 1 << 16; 223cab2bb3Spatrick static const size_t kMapPrimeMod = 65371; // Largest Prime < kMapSizeInBits; 233cab2bb3Spatrick static const size_t kBitsInWord = (sizeof(uintptr_t) * 8); 243cab2bb3Spatrick static const size_t kMapSizeInWords = kMapSizeInBits / kBitsInWord; 253cab2bb3Spatrick public: 263cab2bb3Spatrick 273cab2bb3Spatrick // Clears all bits. ResetValueBitMap283cab2bb3Spatrick void Reset() { memset(Map, 0, sizeof(Map)); } 293cab2bb3Spatrick 303cab2bb3Spatrick // Computes a hash function of Value and sets the corresponding bit. 313cab2bb3Spatrick // Returns true if the bit was changed from 0 to 1. 323cab2bb3Spatrick ATTRIBUTE_NO_SANITIZE_ALL AddValueValueBitMap333cab2bb3Spatrick inline bool AddValue(uintptr_t Value) { 343cab2bb3Spatrick uintptr_t Idx = Value % kMapSizeInBits; 353cab2bb3Spatrick uintptr_t WordIdx = Idx / kBitsInWord; 363cab2bb3Spatrick uintptr_t BitIdx = Idx % kBitsInWord; 373cab2bb3Spatrick uintptr_t Old = Map[WordIdx]; 383cab2bb3Spatrick uintptr_t New = Old | (1ULL << BitIdx); 393cab2bb3Spatrick Map[WordIdx] = New; 403cab2bb3Spatrick return New != Old; 413cab2bb3Spatrick } 423cab2bb3Spatrick 433cab2bb3Spatrick ATTRIBUTE_NO_SANITIZE_ALL AddValueModPrimeValueBitMap443cab2bb3Spatrick inline bool AddValueModPrime(uintptr_t Value) { 453cab2bb3Spatrick return AddValue(Value % kMapPrimeMod); 463cab2bb3Spatrick } 473cab2bb3Spatrick GetValueBitMap483cab2bb3Spatrick inline bool Get(uintptr_t Idx) { 493cab2bb3Spatrick assert(Idx < kMapSizeInBits); 503cab2bb3Spatrick uintptr_t WordIdx = Idx / kBitsInWord; 513cab2bb3Spatrick uintptr_t BitIdx = Idx % kBitsInWord; 523cab2bb3Spatrick return Map[WordIdx] & (1ULL << BitIdx); 533cab2bb3Spatrick } 543cab2bb3Spatrick SizeInBitsValueBitMap553cab2bb3Spatrick size_t SizeInBits() const { return kMapSizeInBits; } 563cab2bb3Spatrick 573cab2bb3Spatrick template <class Callback> 583cab2bb3Spatrick ATTRIBUTE_NO_SANITIZE_ALL ForEachValueBitMap593cab2bb3Spatrick void ForEach(Callback CB) const { 603cab2bb3Spatrick for (size_t i = 0; i < kMapSizeInWords; i++) 613cab2bb3Spatrick if (uintptr_t M = Map[i]) 623cab2bb3Spatrick for (size_t j = 0; j < sizeof(M) * 8; j++) 633cab2bb3Spatrick if (M & ((uintptr_t)1 << j)) 643cab2bb3Spatrick CB(i * sizeof(M) * 8 + j); 653cab2bb3Spatrick } 663cab2bb3Spatrick 673cab2bb3Spatrick private: 683cab2bb3Spatrick ATTRIBUTE_ALIGNED(512) uintptr_t Map[kMapSizeInWords]; 693cab2bb3Spatrick }; 703cab2bb3Spatrick 713cab2bb3Spatrick } // namespace fuzzer 723cab2bb3Spatrick 733cab2bb3Spatrick #endif // LLVM_FUZZER_VALUE_BIT_MAP_H 74