Home | History | Annotate | Download | only in Fuzzer 
      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 = 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 SizeInBits() const { return kMapSizeInBits; }
     56 
     57   template <class Callback>
     58   ATTRIBUTE_NO_SANITIZE_ALL
     59   void ForEach(Callback CB) const {
     60     for (size_t i = 0; i < kMapSizeInWords; i++)
     61       if (uintptr_t M = Map[i])
     62         for (size_t j = 0; j < sizeof(M) * 8; j++)
     63           if (M & ((uintptr_t)1 << j))
     64             CB(i * sizeof(M) * 8 + j);
     65   }
     66 
     67  private:
     68   uintptr_t Map[kMapSizeInWords] __attribute__((aligned(512)));
     69 };
     70 
     71 }  // namespace fuzzer
     72 
     73 #endif  // LLVM_FUZZER_VALUE_BIT_MAP_H
     74