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 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