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