Reland: Refactor mutation strategies into a standalone library

[aarongreen]

Summary

https://reviews.llvm.org/D102447 attempted to introduces libMutagen/libclang_rt.mutagen.a as a subset of libFuzzer/libclang_rt.fuzzer.a, and was landed as https://reviews.llvm.org/rGc4a41cd77c15c2905ac74beeec09f8343a65a549.

A bug involving uninitialized function pointers in two unit tests only surfaced on Darwin, leading it to be reverted in https://github.com/llvm/llvm-project/commit/fd0a2f75ff4f25a4759afeb72b42ba1b6ccea93f.

This patch is identical to the previous one, except that it zero-initializes the config struct and properly forwards the function pointers in MutagenInterface::SetUp in tests/MutagenUnittest.cpp.

[aarongreen]

I have to hit pause on this. While the normal cmake approach passes, I just noticed the standalone approach to building the unit test doesn't.

[morehouse]

Could we put this diff in the other review? It will be easier to see what's changed that way. (You might need to re-open that review to update the diff).

[aarongreen]

Added some feature macros to detect msan and include msan_interface properly for the standalone build.

[aarongreen]

Original revision reopened instead.

compiler-rt/lib/fuzzer/CMakeLists.txt

 set(LIBFUZZER_SOURCES
-  FuzzerCrossOver.cpp
   FuzzerDataFlowTrace.cpp
   FuzzerDriver.cpp
   FuzzerExtFunctionsDlsym.cpp
   FuzzerExtFunctionsWeak.cpp
   FuzzerExtFunctionsWindows.cpp
   FuzzerExtraCounters.cpp
   FuzzerFork.cpp
   FuzzerIO.cpp

 
 set(LIBFUZZER_HEADERS
   FuzzerBuiltins.h
   FuzzerBuiltinsMsvc.h
   FuzzerCommand.h
   FuzzerCorpus.h
   FuzzerDataFlowTrace.h
   FuzzerDefs.h
-  FuzzerDictionary.h
   FuzzerExtFunctions.def
   FuzzerExtFunctions.h
   FuzzerFlags.def
   FuzzerFork.h
   FuzzerIO.h
   FuzzerInterface.h
   FuzzerInternal.h
   FuzzerMerge.h
if(MSVC)
   # Windows.
   list(APPEND LIBFUZZER_CFLAGS -D_HAS_EXCEPTIONS=0)
 else()
   if(NOT HAS_THREAD_LOCAL)
     list(APPEND LIBFUZZER_CFLAGS -Dthread_local=__thread)
   endif()
 endif()
 
+macro(partially_link_libcxx name dir arch)
+  if(${arch} MATCHES "i386")
+    set(EMULATION_ARGUMENT "-m" "elf_i386")
+  else()
+    set(EMULATION_ARGUMENT "")
+  endif()
+  set(cxx_${arch}_merge_dir "${CMAKE_CURRENT_BINARY_DIR}/cxx_${arch}_merge.dir")
+  file(MAKE_DIRECTORY ${cxx_${arch}_merge_dir})
+  add_custom_command(TARGET clang_rt.${name}-${arch} POST_BUILD
+    COMMAND ${CMAKE_LINKER} ${EMULATION_ARGUMENT} --whole-archive "$<TARGET_LINKER_FILE:clang_rt.${name}-${arch}>" --no-whole-archive ${dir}/lib/libc++.a -r -o ${name}.o
+    COMMAND ${CMAKE_OBJCOPY} --localize-hidden ${name}.o
+    COMMAND ${CMAKE_COMMAND} -E remove "$<TARGET_LINKER_FILE:clang_rt.${name}-${arch}>"
+    COMMAND ${CMAKE_AR} qcs "$<TARGET_LINKER_FILE:clang_rt.${name}-${arch}>" ${name}.o
+    WORKING_DIRECTORY ${cxx_${arch}_merge_dir}
+  )
+endmacro()
+
+add_subdirectory(mutagen)
+foreach(X IN LISTS LIBFUZZER_MUTAGEN_SOURCES)
+    list(APPEND LIBFUZZER_SOURCES "mutagen/${X}")
+endforeach()
+foreach(X IN LISTS LIBFUZZER_MUTAGEN_HEADERS)
+    list(APPEND LIBFUZZER_HEADERS "mutagen/${X}")
+endforeach()
+include_directories(.)
+
 add_compiler_rt_component(fuzzer)
 
 add_compiler_rt_object_libraries(RTfuzzer
   OS ${FUZZER_SUPPORTED_OS}
   ARCHS ${FUZZER_SUPPORTED_ARCH}
   SOURCES ${LIBFUZZER_SOURCES}
   ADDITIONAL_HEADERS ${LIBFUZZER_HEADERS}
   CFLAGS ${LIBFUZZER_CFLAGS}
add_compiler_rt_runtime(clang_rt.fuzzer_interceptors
   ARCHS ${FUZZER_SUPPORTED_ARCH}
   OBJECT_LIBS RTfuzzer_interceptors
   CFLAGS ${LIBFUZZER_CFLAGS}
   PARENT_TARGET fuzzer)
 
 if(OS_NAME MATCHES "Linux|Fuchsia" AND
    COMPILER_RT_LIBCXX_PATH AND
    COMPILER_RT_LIBCXXABI_PATH)
-  macro(partially_link_libcxx name dir arch)
-    if(${arch} MATCHES "i386")
-      set(EMULATION_ARGUMENT "-m" "elf_i386")
-    else()
-      set(EMULATION_ARGUMENT "")
-    endif()
-    set(cxx_${arch}_merge_dir "${CMAKE_CURRENT_BINARY_DIR}/cxx_${arch}_merge.dir")
-    file(MAKE_DIRECTORY ${cxx_${arch}_merge_dir})
-    add_custom_command(TARGET clang_rt.${name}-${arch} POST_BUILD
-      COMMAND ${CMAKE_LINKER} ${EMULATION_ARGUMENT} --whole-archive "$<TARGET_LINKER_FILE:clang_rt.${name}-${arch}>" --no-whole-archive ${dir}/lib/libc++.a -r -o ${name}.o
-      COMMAND ${CMAKE_OBJCOPY} --localize-hidden ${name}.o
-      COMMAND ${CMAKE_COMMAND} -E remove "$<TARGET_LINKER_FILE:clang_rt.${name}-${arch}>"
-      COMMAND ${CMAKE_AR} qcs "$<TARGET_LINKER_FILE:clang_rt.${name}-${arch}>" ${name}.o
-      WORKING_DIRECTORY ${cxx_${arch}_merge_dir}
-    )
-  endmacro()
-
   foreach(arch ${FUZZER_SUPPORTED_ARCH})
     get_target_flags_for_arch(${arch} TARGET_CFLAGS)
     set(LIBCXX_${arch}_PREFIX ${CMAKE_CURRENT_BINARY_DIR}/libcxx_fuzzer_${arch})
     add_custom_libcxx(libcxx_fuzzer_${arch} ${LIBCXX_${arch}_PREFIX}
       CFLAGS ${TARGET_CFLAGS}
       CMAKE_ARGS -DCMAKE_CXX_COMPILER_WORKS=ON
                  -DCMAKE_POSITION_INDEPENDENT_CODE=ON
                  -DLIBCXXABI_ENABLE_EXCEPTIONS=OFF

compiler-rt/lib/fuzzer/FuzzerDefs.h

 
 #ifndef LLVM_FUZZER_DEFS_H
 #define LLVM_FUZZER_DEFS_H
 
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <cstring>
+#include <limits>
 #include <memory>
 #include <set>
 #include <string>
 #include <vector>
 
-
 namespace fuzzer {
 
 template <class T> T Min(T a, T b) { return a < b ? a : b; }
 template <class T> T Max(T a, T b) { return a > b ? a : b; }
 
 class Random;
-class Dictionary;
-class DictionaryEntry;
-class MutationDispatcher;
 struct FuzzingOptions;
 class InputCorpus;
 struct InputInfo;
 struct ExternalFunctions;
 
 // Global interface to functions that may or may not be available.
 extern ExternalFunctions *EF;
 

 template<typename T>
 using Vector = std::vector<T, fuzzer_allocator<T>>;
 
 template<typename T>
 using Set = std::set<T, std::less<T>, fuzzer_allocator<T>>;
 
 typedef Vector<uint8_t> Unit;
 typedef Vector<Unit> UnitVector;
+
+// A simple POD sized array of bytes.
+template <size_t kMaxSizeT> class FixedWord {
+public:
+  static const size_t kMaxSize = kMaxSizeT;
+  FixedWord() { memset(Data, 0, kMaxSize); }
+  FixedWord(const uint8_t *B, size_t S) { Set(B, S); }
+
+  void Set(const uint8_t *B, size_t S) {
+    static_assert(kMaxSizeT <= std::numeric_limits<uint8_t>::max(),
+                  "FixedWord::kMaxSizeT cannot fit in a uint8_t.");
+    assert(S <= kMaxSize);
+    memcpy(Data, B, S);
+    Size = static_cast<uint8_t>(S);
+  }
+
+  bool operator==(const FixedWord<kMaxSize> &w) const {
+    return Size == w.Size && 0 == memcmp(Data, w.Data, Size);
+  }
+
+  static size_t GetMaxSize() { return kMaxSize; }
+  const uint8_t *data() const { return Data; }
+  uint8_t size() const { return Size; }
+
+private:
+  uint8_t Size = 0;
+  uint8_t Data[kMaxSize];
+};
+
+typedef FixedWord<64> Word;
+
 typedef int (*UserCallback)(const uint8_t *Data, size_t Size);
 
 int FuzzerDriver(int *argc, char ***argv, UserCallback Callback);
 
 uint8_t *ExtraCountersBegin();
 uint8_t *ExtraCountersEnd();
 void ClearExtraCounters();
 
 extern bool RunningUserCallback;
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_DEFS_H

compiler-rt/lib/fuzzer/FuzzerDictionary.h

-//===- FuzzerDictionary.h - Internal header for the Fuzzer ------*- C++ -* ===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-// fuzzer::Dictionary
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_FUZZER_DICTIONARY_H
-#define LLVM_FUZZER_DICTIONARY_H
-
-#include "FuzzerDefs.h"
-#include "FuzzerIO.h"
-#include "FuzzerUtil.h"
-#include <algorithm>
-#include <limits>
-
-namespace fuzzer {
-// A simple POD sized array of bytes.
-template <size_t kMaxSizeT> class FixedWord {
-public:
-  static const size_t kMaxSize = kMaxSizeT;
-  FixedWord() {}
-  FixedWord(const uint8_t *B, size_t S) { Set(B, S); }
-
-  void Set(const uint8_t *B, size_t S) {
-    static_assert(kMaxSizeT <= std::numeric_limits<uint8_t>::max(),
-                  "FixedWord::kMaxSizeT cannot fit in a uint8_t.");
-    assert(S <= kMaxSize);
-    memcpy(Data, B, S);
-    Size = static_cast<uint8_t>(S);
-  }
-
-  bool operator==(const FixedWord<kMaxSize> &w) const {
-    return Size == w.Size && 0 == memcmp(Data, w.Data, Size);
-  }
-
-  static size_t GetMaxSize() { return kMaxSize; }
-  const uint8_t *data() const { return Data; }
-  uint8_t size() const { return Size; }
-
-private:
-  uint8_t Size = 0;
-  uint8_t Data[kMaxSize];
-};
-
-typedef FixedWord<64> Word;
-
-class DictionaryEntry {
- public:
-  DictionaryEntry() {}
-  DictionaryEntry(Word W) : W(W) {}
-  DictionaryEntry(Word W, size_t PositionHint) : W(W), PositionHint(PositionHint) {}
-  const Word &GetW() const { return W; }
-
-  bool HasPositionHint() const { return PositionHint != std::numeric_limits<size_t>::max(); }
-  size_t GetPositionHint() const {
-    assert(HasPositionHint());
-    return PositionHint;
-  }
-  void IncUseCount() { UseCount++; }
-  void IncSuccessCount() { SuccessCount++; }
-  size_t GetUseCount() const { return UseCount; }
-  size_t GetSuccessCount() const {return SuccessCount; }
-
-  void Print(const char *PrintAfter = "\n") {
-    PrintASCII(W.data(), W.size());
-    if (HasPositionHint())
-      Printf("@%zd", GetPositionHint());
-    Printf("%s", PrintAfter);
-  }
-
-private:
-  Word W;
-  size_t PositionHint = std::numeric_limits<size_t>::max();
-  size_t UseCount = 0;
-  size_t SuccessCount = 0;
-};
-
-class Dictionary {
- public:
-  static const size_t kMaxDictSize = 1 << 14;
-
-  bool ContainsWord(const Word &W) const {
-    return std::any_of(begin(), end(), [&](const DictionaryEntry &DE) {
-      return DE.GetW() == W;
-    });
-  }
-  const DictionaryEntry *begin() const { return &DE[0]; }
-  const DictionaryEntry *end() const { return begin() + Size; }
-  DictionaryEntry & operator[] (size_t Idx) {
-    assert(Idx < Size);
-    return DE[Idx];
-  }
-  void push_back(DictionaryEntry DE) {
-    if (Size < kMaxDictSize)
-      this->DE[Size++] = DE;
-  }
-  void clear() { Size = 0; }
-  bool empty() const { return Size == 0; }
-  size_t size() const { return Size; }
-
-private:
-  DictionaryEntry DE[kMaxDictSize];
-  size_t Size = 0;
-};
-
-// Parses one dictionary entry.
-// If successful, write the enty to Unit and returns true,
-// otherwise returns false.
-bool ParseOneDictionaryEntry(const std::string &Str, Unit *U);
-// Parses the dictionary file, fills Units, returns true iff all lines
-// were parsed successfully.
-bool ParseDictionaryFile(const std::string &Text, Vector<Unit> *Units);
-
-}  // namespace fuzzer
-
-#endif  // LLVM_FUZZER_DICTIONARY_H

compiler-rt/lib/fuzzer/FuzzerDriver.cpp

 #include "FuzzerIO.h"
 #include "FuzzerInterface.h"
 #include "FuzzerInternal.h"
 #include "FuzzerMerge.h"
 #include "FuzzerMutate.h"
 #include "FuzzerPlatform.h"
 #include "FuzzerRandom.h"
 #include "FuzzerTracePC.h"
+#include "mutagen/MutagenDispatcher.h"
 #include <algorithm>
 #include <atomic>
 #include <chrono>
 #include <cstdlib>
 #include <cstring>
+#include <fstream>
 #include <mutex>
 #include <string>
 #include <thread>
-#include <fstream>
 
 // This function should be present in the libFuzzer so that the client
 // binary can test for its existence.
 #if LIBFUZZER_MSVC
 extern "C" void __libfuzzer_is_present() {}
 #if defined(_M_IX86) || defined(__i386__)
 #pragma comment(linker, "/include:___libfuzzer_is_present")
 #else
if (Flags.collect_data_flow && !Flags.fork && !Flags.merge) {
     if (RunIndividualFiles)
       return CollectDataFlow(Flags.collect_data_flow, Flags.data_flow_trace,
                         ReadCorpora({}, *Inputs));
     else
       return CollectDataFlow(Flags.collect_data_flow, Flags.data_flow_trace,
                         ReadCorpora(*Inputs, {}));
   }
 
-  Random Rand(Seed);
-  auto *MD = new MutationDispatcher(Rand, Options);
+  LLVMMutagenConfiguration Config;
+  ConfigureMutagen(Seed, Options, &Config);
+  auto *MD = new MutationDispatcher(&Config);
   auto *Corpus = new InputCorpus(Options.OutputCorpus, Entropic);
   auto *F = new Fuzzer(Callback, *Corpus, *MD, Options);
 
   for (auto &U: Dictionary)
     if (U.size() <= Word::GetMaxSize())
       MD->AddWordToManualDictionary(Word(U.data(), U.size()));
 
       // Threads are only supported by Chrome. Don't use them with emscripten

compiler-rt/lib/fuzzer/FuzzerInternal.h

 
 #include "FuzzerDataFlowTrace.h"
 #include "FuzzerDefs.h"
 #include "FuzzerExtFunctions.h"
 #include "FuzzerInterface.h"
 #include "FuzzerOptions.h"
 #include "FuzzerSHA1.h"
 #include "FuzzerValueBitMap.h"
+#include "mutagen/MutagenDispatcher.h"
 #include <algorithm>
 #include <atomic>
 #include <chrono>
 #include <climits>
 #include <cstdlib>
 #include <string.h>
 
 namespace fuzzer {
+namespace {
 
 using namespace std::chrono;
+using mutagen::MutationDispatcher;
+
+} // namespace
 
 class Fuzzer {
 public:
 
   Fuzzer(UserCallback CB, InputCorpus &Corpus, MutationDispatcher &MD,
          FuzzingOptions Options);
   ~Fuzzer();
   void Loop(Vector<SizedFile> &CorporaFiles);

compiler-rt/lib/fuzzer/FuzzerLoop.cpp

void Fuzzer::StaticDeathCallback() {
   assert(F);
   F->DeathCallback();
 }
 
 void Fuzzer::DumpCurrentUnit(const char *Prefix) {
   if (!CurrentUnitData)
     return; // Happens when running individual inputs.
   ScopedDisableMsanInterceptorChecks S;
-  MD.PrintMutationSequence();
+  PrintMutationSequence(MD);
   Printf("; base unit: %s\n", Sha1ToString(BaseSha1).c_str());
   size_t UnitSize = CurrentUnitSize;
   if (UnitSize <= kMaxUnitSizeToPrint) {
     PrintHexArray(CurrentUnitData, UnitSize, "\n");
     PrintASCII(CurrentUnitData, UnitSize, "\n");
   }
   WriteUnitToFileWithPrefix({CurrentUnitData, CurrentUnitData + UnitSize},
                             Prefix);
bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
   if (NumNewFeatures || ForceAddToCorpus) {
     TPC.UpdateObservedPCs();
     auto NewII =
         Corpus.AddToCorpus({Data, Data + Size}, NumNewFeatures, MayDeleteFile,
                            TPC.ObservedFocusFunction(), ForceAddToCorpus,
                            TimeOfUnit, UniqFeatureSetTmp, DFT, II);
     WriteFeatureSetToFile(Options.FeaturesDir, Sha1ToString(NewII->Sha1),
                           NewII->UniqFeatureSet);
+    const auto &MS = MD.MutationSequence();
     WriteEdgeToMutationGraphFile(Options.MutationGraphFile, NewII, II,
-                                 MD.MutationSequence());
+                                 MS.GetString());
     return true;
   }
   if (II && FoundUniqFeaturesOfII &&
       II->DataFlowTraceForFocusFunction.empty() &&
       FoundUniqFeaturesOfII == II->UniqFeatureSet.size() &&
       II->U.size() > Size) {
     auto OldFeaturesFile = Sha1ToString(II->Sha1);
     Corpus.Replace(II, {Data, Data + Size});

 }
 
 void Fuzzer::PrintStatusForNewUnit(const Unit &U, const char *Text) {
   if (!Options.PrintNEW)
     return;
   PrintStats(Text, "");
   if (Options.Verbosity) {
     Printf(" L: %zd/%zd ", U.size(), Corpus.MaxInputSize());
-    MD.PrintMutationSequence(Options.Verbosity >= 2);
+    PrintMutationSequence(MD, Options.Verbosity >= 2);
     Printf("\n");
   }
 }
 
 void Fuzzer::ReportNewCoverage(InputInfo *II, const Unit &U) {
   II->NumSuccessfullMutations++;
   MD.RecordSuccessfulMutationSequence();
   PrintStatusForNewUnit(U, II->Reduced ? "REDUCE" : "NEW   ");
while (true) {
 
     // Perform several mutations and runs.
     MutateAndTestOne();
 
     PurgeAllocator();
   }
 
   PrintStats("DONE  ", "\n");
-  MD.PrintRecommendedDictionary();
+  PrintRecommendedDictionary(MD);
 }
 
 void Fuzzer::MinimizeCrashLoop(const Unit &U) {
   if (U.size() <= 1)
     return;
   while (!TimedOut() && TotalNumberOfRuns < Options.MaxNumberOfRuns) {
     MD.StartMutationSequence();
     memcpy(CurrentUnitData, U.data(), U.size());

compiler-rt/lib/fuzzer/FuzzerMutate.h

 //===- FuzzerMutate.h - Internal header for the Fuzzer ----------*- C++ -* ===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // fuzzer::MutationDispatcher
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_FUZZER_MUTATE_H
 #define LLVM_FUZZER_MUTATE_H
 
-#include "FuzzerDefs.h"
-#include "FuzzerDictionary.h"
 #include "FuzzerOptions.h"
-#include "FuzzerRandom.h"
+#include "mutagen/Mutagen.h"
+#include "mutagen/MutagenDispatcher.h"
 
 namespace fuzzer {
+namespace {
 
-class MutationDispatcher {
-public:
-  MutationDispatcher(Random &Rand, const FuzzingOptions &Options);
-  ~MutationDispatcher() {}
-  /// Indicate that we are about to start a new sequence of mutations.
-  void StartMutationSequence();
-  /// Print the current sequence of mutations. Only prints the full sequence
-  /// when Verbose is true.
-  void PrintMutationSequence(bool Verbose = true);
-  /// Return the current sequence of mutations.
-  std::string MutationSequence();
-  /// Indicate that the current sequence of mutations was successful.
-  void RecordSuccessfulMutationSequence();
-  /// Mutates data by invoking user-provided mutator.
-  size_t Mutate_Custom(uint8_t *Data, size_t Size, size_t MaxSize);
-  /// Mutates data by invoking user-provided crossover.
-  size_t Mutate_CustomCrossOver(uint8_t *Data, size_t Size, size_t MaxSize);
-  /// Mutates data by shuffling bytes.
-  size_t Mutate_ShuffleBytes(uint8_t *Data, size_t Size, size_t MaxSize);
-  /// Mutates data by erasing bytes.
-  size_t Mutate_EraseBytes(uint8_t *Data, size_t Size, size_t MaxSize);
-  /// Mutates data by inserting a byte.
-  size_t Mutate_InsertByte(uint8_t *Data, size_t Size, size_t MaxSize);
-  /// Mutates data by inserting several repeated bytes.
-  size_t Mutate_InsertRepeatedBytes(uint8_t *Data, size_t Size, size_t MaxSize);
-  /// Mutates data by changing one byte.
-  size_t Mutate_ChangeByte(uint8_t *Data, size_t Size, size_t MaxSize);
-  /// Mutates data by changing one bit.
-  size_t Mutate_ChangeBit(uint8_t *Data, size_t Size, size_t MaxSize);
-  /// Mutates data by copying/inserting a part of data into a different place.
-  size_t Mutate_CopyPart(uint8_t *Data, size_t Size, size_t MaxSize);
-
-  /// Mutates data by adding a word from the manual dictionary.
-  size_t Mutate_AddWordFromManualDictionary(uint8_t *Data, size_t Size,
-                                            size_t MaxSize);
-
-  /// Mutates data by adding a word from the TORC.
-  size_t Mutate_AddWordFromTORC(uint8_t *Data, size_t Size, size_t MaxSize);
-
-  /// Mutates data by adding a word from the persistent automatic dictionary.
-  size_t Mutate_AddWordFromPersistentAutoDictionary(uint8_t *Data, size_t Size,
-                                                    size_t MaxSize);
-
-  /// Tries to find an ASCII integer in Data, changes it to another ASCII int.
-  size_t Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, size_t MaxSize);
-  /// Change a 1-, 2-, 4-, or 8-byte integer in interesting ways.
-  size_t Mutate_ChangeBinaryInteger(uint8_t *Data, size_t Size, size_t MaxSize);
-
-  /// CrossOver Data with CrossOverWith.
-  size_t Mutate_CrossOver(uint8_t *Data, size_t Size, size_t MaxSize);
-
-  /// Applies one of the configured mutations.
-  /// Returns the new size of data which could be up to MaxSize.
-  size_t Mutate(uint8_t *Data, size_t Size, size_t MaxSize);
-
-  /// Applies one of the configured mutations to the bytes of Data
-  /// that have '1' in Mask.
-  /// Mask.size() should be >= Size.
-  size_t MutateWithMask(uint8_t *Data, size_t Size, size_t MaxSize,
-                        const Vector<uint8_t> &Mask);
-
-  /// Applies one of the default mutations. Provided as a service
-  /// to mutation authors.
-  size_t DefaultMutate(uint8_t *Data, size_t Size, size_t MaxSize);
-
-  /// Creates a cross-over of two pieces of Data, returns its size.
-  size_t CrossOver(const uint8_t *Data1, size_t Size1, const uint8_t *Data2,
-                   size_t Size2, uint8_t *Out, size_t MaxOutSize);
-
-  void AddWordToManualDictionary(const Word &W);
-
-  void PrintRecommendedDictionary();
-
-  void SetCrossOverWith(const Unit *U) { CrossOverWith = U; }
-
-  Random &GetRand() { return Rand; }
-
- private:
-  struct Mutator {
-    size_t (MutationDispatcher::*Fn)(uint8_t *Data, size_t Size, size_t Max);
-    const char *Name;
-  };
-
-  size_t AddWordFromDictionary(Dictionary &D, uint8_t *Data, size_t Size,
-                               size_t MaxSize);
-  size_t MutateImpl(uint8_t *Data, size_t Size, size_t MaxSize,
-                    Vector<Mutator> &Mutators);
-
-  size_t InsertPartOf(const uint8_t *From, size_t FromSize, uint8_t *To,
-                      size_t ToSize, size_t MaxToSize);
-  size_t CopyPartOf(const uint8_t *From, size_t FromSize, uint8_t *To,
-                    size_t ToSize);
-  size_t ApplyDictionaryEntry(uint8_t *Data, size_t Size, size_t MaxSize,
-                              DictionaryEntry &DE);
-
-  template <class T>
-  DictionaryEntry MakeDictionaryEntryFromCMP(T Arg1, T Arg2,
-                                             const uint8_t *Data, size_t Size);
-  DictionaryEntry MakeDictionaryEntryFromCMP(const Word &Arg1, const Word &Arg2,
-                                             const uint8_t *Data, size_t Size);
-  DictionaryEntry MakeDictionaryEntryFromCMP(const void *Arg1, const void *Arg2,
-                                             const void *Arg1Mutation,
-                                             const void *Arg2Mutation,
-                                             size_t ArgSize,
-                                             const uint8_t *Data, size_t Size);
-
-  Random &Rand;
-  const FuzzingOptions Options;
-
-  // Dictionary provided by the user via -dict=DICT_FILE.
-  Dictionary ManualDictionary;
-  // Persistent dictionary modified by the fuzzer, consists of
-  // entries that led to successful discoveries in the past mutations.
-  Dictionary PersistentAutoDictionary;
-
-  Vector<DictionaryEntry *> CurrentDictionaryEntrySequence;
-
-  static const size_t kCmpDictionaryEntriesDequeSize = 16;
-  DictionaryEntry CmpDictionaryEntriesDeque[kCmpDictionaryEntriesDequeSize];
-  size_t CmpDictionaryEntriesDequeIdx = 0;
-
-  const Unit *CrossOverWith = nullptr;
-  Vector<uint8_t> MutateInPlaceHere;
-  Vector<uint8_t> MutateWithMaskTemp;
-  // CustomCrossOver needs its own buffer as a custom implementation may call
-  // LLVMFuzzerMutate, which in turn may resize MutateInPlaceHere.
-  Vector<uint8_t> CustomCrossOverInPlaceHere;
-
-  Vector<Mutator> Mutators;
-  Vector<Mutator> DefaultMutators;
-  Vector<Mutator> CurrentMutatorSequence;
-};
+using mutagen::MutationDispatcher;
+
+} // namespace
+
+void ConfigureMutagen(unsigned int Seed, const FuzzingOptions &Options,
+                      LLVMMutagenConfiguration *OutConfig);
+
+void PrintRecommendedDictionary(MutationDispatcher &MD);
+
+void PrintMutationSequence(MutationDispatcher &MD, bool Verbose = true);
 
 }  // namespace fuzzer
 
 #endif  // LLVM_FUZZER_MUTATE_H

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

-//===- FuzzerMutate.cpp - Mutate a test input -----------------------------===//
+//===- FuzzerMutate.cpp - Mutation utilities -----------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
-// Mutate a test input.
+// Mutate utilities.
 //===----------------------------------------------------------------------===//
 
-#include "FuzzerDefs.h"
+#include "FuzzerMutate.h"
 #include "FuzzerExtFunctions.h"
 #include "FuzzerIO.h"
-#include "FuzzerMutate.h"
-#include "FuzzerOptions.h"
 #include "FuzzerTracePC.h"
+#include "FuzzerUtil.h"
 
 namespace fuzzer {
+namespace {
 
-const size_t Dictionary::kMaxDictSize;
-static const size_t kMaxMutationsToPrint = 10;
-
-static void PrintASCII(const Word &W, const char *PrintAfter) {
-  PrintASCII(W.data(), W.size(), PrintAfter);
-}
-
-MutationDispatcher::MutationDispatcher(Random &Rand,
-                                       const FuzzingOptions &Options)
-    : Rand(Rand), Options(Options) {
-  DefaultMutators.insert(
-      DefaultMutators.begin(),
-      {
-          {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"},
-          {&MutationDispatcher::Mutate_InsertByte, "InsertByte"},
-          {&MutationDispatcher::Mutate_InsertRepeatedBytes,
-           "InsertRepeatedBytes"},
-          {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"},
-          {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"},
-          {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"},
-          {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"},
-          {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"},
-          {&MutationDispatcher::Mutate_CopyPart, "CopyPart"},
-          {&MutationDispatcher::Mutate_CrossOver, "CrossOver"},
-          {&MutationDispatcher::Mutate_AddWordFromManualDictionary,
-           "ManualDict"},
-          {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary,
-           "PersAutoDict"},
-      });
-  if(Options.UseCmp)
-    DefaultMutators.push_back(
-        {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"});
-
-  if (EF->LLVMFuzzerCustomMutator)
-    Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"});
-  else
-    Mutators = DefaultMutators;
-
-  if (EF->LLVMFuzzerCustomCrossOver)
-    Mutators.push_back(
-        {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"});
-}
-
-static char RandCh(Random &Rand) {
-  if (Rand.RandBool())
-    return static_cast<char>(Rand(256));
-  const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00";
-  return Special[Rand(sizeof(Special) - 1)];
-}
-
-size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size,
-                                         size_t MaxSize) {
-  if (EF->__msan_unpoison)
-    EF->__msan_unpoison(Data, Size);
-  if (EF->__msan_unpoison_param)
-    EF->__msan_unpoison_param(4);
-  return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize,
-                                     Rand.Rand<unsigned int>());
-}
-
-size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size,
-                                                  size_t MaxSize) {
-  if (Size == 0)
-    return 0;
-  if (!CrossOverWith) return 0;
-  const Unit &Other = *CrossOverWith;
-  if (Other.empty())
-    return 0;
-  CustomCrossOverInPlaceHere.resize(MaxSize);
-  auto &U = CustomCrossOverInPlaceHere;
-
-  if (EF->__msan_unpoison) {
-    EF->__msan_unpoison(Data, Size);
-    EF->__msan_unpoison(Other.data(), Other.size());
-    EF->__msan_unpoison(U.data(), U.size());
-  }
-  if (EF->__msan_unpoison_param)
-    EF->__msan_unpoison_param(7);
-  size_t NewSize = EF->LLVMFuzzerCustomCrossOver(
-      Data, Size, Other.data(), Other.size(), U.data(), U.size(),
-      Rand.Rand<unsigned int>());
-
-  if (!NewSize)
-    return 0;
-  assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit");
-  memcpy(Data, U.data(), NewSize);
-  return NewSize;
-}
-
-size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size,
-                                               size_t MaxSize) {
-  if (Size > MaxSize || Size == 0) return 0;
-  size_t ShuffleAmount =
-      Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size.
-  size_t ShuffleStart = Rand(Size - ShuffleAmount);
-  assert(ShuffleStart + ShuffleAmount <= Size);
-  std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand);
-  return Size;
-}
-
-size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size,
-                                             size_t MaxSize) {
-  if (Size <= 1) return 0;
-  size_t N = Rand(Size / 2) + 1;
-  assert(N < Size);
-  size_t Idx = Rand(Size - N + 1);
-  // Erase Data[Idx:Idx+N].
-  memmove(Data + Idx, Data + Idx + N, Size - Idx - N);
-  // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx);
-  return Size - N;
-}
-
-size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size,
-                                             size_t MaxSize) {
-  if (Size >= MaxSize) return 0;
-  size_t Idx = Rand(Size + 1);
-  // Insert new value at Data[Idx].
-  memmove(Data + Idx + 1, Data + Idx, Size - Idx);
-  Data[Idx] = RandCh(Rand);
-  return Size + 1;
+void FromTORC4(size_t Idx, uint32_t *A, uint32_t *B) {
+  const auto &X = TPC.TORC4.Get(Idx);
+  *A = X.A;
+  *B = X.B;
 }
 
-size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data,
-                                                      size_t Size,
-                                                      size_t MaxSize) {
-  const size_t kMinBytesToInsert = 3;
-  if (Size + kMinBytesToInsert >= MaxSize) return 0;
-  size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128);
-  size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert;
-  assert(Size + N <= MaxSize && N);
-  size_t Idx = Rand(Size + 1);
-  // Insert new values at Data[Idx].
-  memmove(Data + Idx + N, Data + Idx, Size - Idx);
-  // Give preference to 0x00 and 0xff.
-  uint8_t Byte = static_cast<uint8_t>(
-      Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255));
-  for (size_t i = 0; i < N; i++)
-    Data[Idx + i] = Byte;
-  return Size + N;
+void FromTORC8(size_t Idx, uint64_t *A, uint64_t *B) {
+  const auto &X = TPC.TORC8.Get(Idx);
+  *A = X.A;
+  *B = X.B;
 }
 
-size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size,
-                                             size_t MaxSize) {
-  if (Size > MaxSize) return 0;
-  size_t Idx = Rand(Size);
-  Data[Idx] = RandCh(Rand);
-  return Size;
+void FromTORCW(size_t Idx, const uint8_t **DataA, size_t *SizeA,
+               const uint8_t **DataB, size_t *SizeB) {
+  const auto &X = TPC.TORCW.Get(Idx);
+  *DataA = X.A.data();
+  *SizeA = X.A.size();
+  *DataB = X.B.data();
+  *SizeB = X.B.size();
 }
 
-size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
-                                            size_t MaxSize) {
-  if (Size > MaxSize) return 0;
-  size_t Idx = Rand(Size);
-  Data[Idx] ^= 1 << Rand(8);
-  return Size;
+void FromMMT(size_t Idx, const uint8_t **Data, size_t *Size) {
+  auto W = TPC.MMT.Get(Idx);
+  *Data = W.data();
+  *Size = W.size();
 }
 
-size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data,
-                                                              size_t Size,
-                                                              size_t MaxSize) {
-  return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize);
+void PrintASCII(const Word &W, const char *PrintAfter) {
+  fuzzer::PrintASCII(W.data(), W.size(), PrintAfter);
 }
 
-size_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size,
-                                                size_t MaxSize,
-                                                DictionaryEntry &DE) {
-  const Word &W = DE.GetW();
-  bool UsePositionHint = DE.HasPositionHint() &&
-                         DE.GetPositionHint() + W.size() < Size &&
-                         Rand.RandBool();
-  if (Rand.RandBool()) {  // Insert W.
-    if (Size + W.size() > MaxSize) return 0;
-    size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1);
-    memmove(Data + Idx + W.size(), Data + Idx, Size - Idx);
-    memcpy(Data + Idx, W.data(), W.size());
-    Size += W.size();
-  } else {  // Overwrite some bytes with W.
-    if (W.size() > Size) return 0;
-    size_t Idx =
-        UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1 - W.size());
-    memcpy(Data + Idx, W.data(), W.size());
-  }
-  return Size;
-}
+} // namespace
 
-// Somewhere in the past we have observed a comparison instructions
-// with arguments Arg1 Arg2. This function tries to guess a dictionary
-// entry that will satisfy that comparison.
-// It first tries to find one of the arguments (possibly swapped) in the
-// input and if it succeeds it creates a DE with a position hint.
-// Otherwise it creates a DE with one of the arguments w/o a position hint.
-DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
-    const void *Arg1, const void *Arg2,
-    const void *Arg1Mutation, const void *Arg2Mutation,
-    size_t ArgSize, const uint8_t *Data,
-    size_t Size) {
-  bool HandleFirst = Rand.RandBool();
-  const void *ExistingBytes, *DesiredBytes;
-  Word W;
-  const uint8_t *End = Data + Size;
-  for (int Arg = 0; Arg < 2; Arg++) {
-    ExistingBytes = HandleFirst ? Arg1 : Arg2;
-    DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation;
-    HandleFirst = !HandleFirst;
-    W.Set(reinterpret_cast<const uint8_t*>(DesiredBytes), ArgSize);
-    const size_t kMaxNumPositions = 8;
-    size_t Positions[kMaxNumPositions];
-    size_t NumPositions = 0;
-    for (const uint8_t *Cur = Data;
-         Cur < End && NumPositions < kMaxNumPositions; Cur++) {
-      Cur =
-          (const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize);
-      if (!Cur) break;
-      Positions[NumPositions++] = Cur - Data;
-    }
-    if (!NumPositions) continue;
-    return DictionaryEntry(W, Positions[Rand(NumPositions)]);
-  }
-  DictionaryEntry DE(W);
-  return DE;
-}
-
-
-template <class T>
-DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
-    T Arg1, T Arg2, const uint8_t *Data, size_t Size) {
-  if (Rand.RandBool()) Arg1 = Bswap(Arg1);
-  if (Rand.RandBool()) Arg2 = Bswap(Arg2);
-  T Arg1Mutation = static_cast<T>(Arg1 + Rand(-1, 1));
-  T Arg2Mutation = static_cast<T>(Arg2 + Rand(-1, 1));
-  return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation,
-                                    sizeof(Arg1), Data, Size);
-}
-
-DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
-    const Word &Arg1, const Word &Arg2, const uint8_t *Data, size_t Size) {
-  return MakeDictionaryEntryFromCMP(Arg1.data(), Arg2.data(), Arg1.data(),
-                                    Arg2.data(), Arg1.size(), Data, Size);
-}
-
-size_t MutationDispatcher::Mutate_AddWordFromTORC(
-    uint8_t *Data, size_t Size, size_t MaxSize) {
-  Word W;
-  DictionaryEntry DE;
-  switch (Rand(4)) {
-  case 0: {
-    auto X = TPC.TORC8.Get(Rand.Rand<size_t>());
-    DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size);
-  } break;
-  case 1: {
-    auto X = TPC.TORC4.Get(Rand.Rand<size_t>());
-    if ((X.A >> 16) == 0 && (X.B >> 16) == 0 && Rand.RandBool())
-      DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, Size);
-    else
-      DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size);
-  } break;
-  case 2: {
-    auto X = TPC.TORCW.Get(Rand.Rand<size_t>());
-    DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size);
-  } break;
-  case 3: if (Options.UseMemmem) {
-      auto X = TPC.MMT.Get(Rand.Rand<size_t>());
-      DE = DictionaryEntry(X);
-  } break;
-  default:
-    assert(0);
-  }
-  if (!DE.GetW().size()) return 0;
-  Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE);
-  if (!Size) return 0;
-  DictionaryEntry &DERef =
-      CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ %
-                                kCmpDictionaryEntriesDequeSize];
-  DERef = DE;
-  CurrentDictionaryEntrySequence.push_back(&DERef);
-  return Size;
-}
-
-size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary(
-    uint8_t *Data, size_t Size, size_t MaxSize) {
-  return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize);
-}
-
-size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data,
-                                                 size_t Size, size_t MaxSize) {
-  if (Size > MaxSize) return 0;
-  if (D.empty()) return 0;
-  DictionaryEntry &DE = D[Rand(D.size())];
-  Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE);
-  if (!Size) return 0;
-  DE.IncUseCount();
-  CurrentDictionaryEntrySequence.push_back(&DE);
-  return Size;
-}
-
-// Overwrites part of To[0,ToSize) with a part of From[0,FromSize).
-// Returns ToSize.
-size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize,
-                                      uint8_t *To, size_t ToSize) {
-  // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize).
-  size_t ToBeg = Rand(ToSize);
-  size_t CopySize = Rand(ToSize - ToBeg) + 1;
-  assert(ToBeg + CopySize <= ToSize);
-  CopySize = std::min(CopySize, FromSize);
-  size_t FromBeg = Rand(FromSize - CopySize + 1);
-  assert(FromBeg + CopySize <= FromSize);
-  memmove(To + ToBeg, From + FromBeg, CopySize);
-  return ToSize;
-}
-
-// Inserts part of From[0,ToSize) into To.
-// Returns new size of To on success or 0 on failure.
-size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize,
-                                        uint8_t *To, size_t ToSize,
-                                        size_t MaxToSize) {
-  if (ToSize >= MaxToSize) return 0;
-  size_t AvailableSpace = MaxToSize - ToSize;
-  size_t MaxCopySize = std::min(AvailableSpace, FromSize);
-  size_t CopySize = Rand(MaxCopySize) + 1;
-  size_t FromBeg = Rand(FromSize - CopySize + 1);
-  assert(FromBeg + CopySize <= FromSize);
-  size_t ToInsertPos = Rand(ToSize + 1);
-  assert(ToInsertPos + CopySize <= MaxToSize);
-  size_t TailSize = ToSize - ToInsertPos;
-  if (To == From) {
-    MutateInPlaceHere.resize(MaxToSize);
-    memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize);
-    memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
-    memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize);
-  } else {
-    memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
-    memmove(To + ToInsertPos, From + FromBeg, CopySize);
-  }
-  return ToSize + CopySize;
+void ConfigureMutagen(unsigned int Seed, const FuzzingOptions &Options,
+                      LLVMMutagenConfiguration *OutConfig) {
+  OutConfig->Seed = Seed;
+  OutConfig->UseCmp = Options.UseCmp;
+  OutConfig->FromTORC4 = FromTORC4;
+  OutConfig->FromTORC8 = FromTORC8;
+  OutConfig->FromTORCW = FromTORCW;
+  OutConfig->UseMemmem = Options.UseMemmem;
+  OutConfig->FromMMT = FromMMT;
+  OutConfig->CustomMutator = EF->LLVMFuzzerCustomMutator;
+  OutConfig->CustomCrossOver = EF->LLVMFuzzerCustomCrossOver;
+  OutConfig->MSanUnpoison = EF->__msan_unpoison;
+  OutConfig->MSanUnpoisonParam = EF->__msan_unpoison_param;
 }
 
-size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size,
-                                           size_t MaxSize) {
-  if (Size > MaxSize || Size == 0) return 0;
-  // If Size == MaxSize, `InsertPartOf(...)` will
-  // fail so there's no point using it in this case.
-  if (Size == MaxSize || Rand.RandBool())
-    return CopyPartOf(Data, Size, Data, Size);
-  else
-    return InsertPartOf(Data, Size, Data, Size, MaxSize);
-}
-
-size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size,
-                                                     size_t MaxSize) {
-  if (Size > MaxSize) return 0;
-  size_t B = Rand(Size);
-  while (B < Size && !isdigit(Data[B])) B++;
-  if (B == Size) return 0;
-  size_t E = B;
-  while (E < Size && isdigit(Data[E])) E++;
-  assert(B < E);
-  // now we have digits in [B, E).
-  // strtol and friends don't accept non-zero-teminated data, parse it manually.
-  uint64_t Val = Data[B] - '0';
-  for (size_t i = B + 1; i < E; i++)
-    Val = Val * 10 + Data[i] - '0';
-
-  // Mutate the integer value.
-  switch(Rand(5)) {
-    case 0: Val++; break;
-    case 1: Val--; break;
-    case 2: Val /= 2; break;
-    case 3: Val *= 2; break;
-    case 4: Val = Rand(Val * Val); break;
-    default: assert(0);
-  }
-  // Just replace the bytes with the new ones, don't bother moving bytes.
-  for (size_t i = B; i < E; i++) {
-    size_t Idx = E + B - i - 1;
-    assert(Idx >= B && Idx < E);
-    Data[Idx] = (Val % 10) + '0';
-    Val /= 10;
-  }
-  return Size;
-}
-
-template<class T>
-size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) {
-  if (Size < sizeof(T)) return 0;
-  size_t Off = Rand(Size - sizeof(T) + 1);
-  assert(Off + sizeof(T) <= Size);
-  T Val;
-  if (Off < 64 && !Rand(4)) {
-    Val = static_cast<T>(Size);
-    if (Rand.RandBool())
-      Val = Bswap(Val);
-  } else {
-    memcpy(&Val, Data + Off, sizeof(Val));
-    T Add = static_cast<T>(Rand(21));
-    Add -= 10;
-    if (Rand.RandBool())
-      Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes.
-    else
-      Val = Val + Add;               // Add assuming current endiannes.
-    if (Add == 0 || Rand.RandBool()) // Maybe negate.
-      Val = -Val;
-  }
-  memcpy(Data + Off, &Val, sizeof(Val));
-  return Size;
-}
-
-size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data,
-                                                      size_t Size,
-                                                      size_t MaxSize) {
-  if (Size > MaxSize) return 0;
-  switch (Rand(4)) {
-    case 3: return ChangeBinaryInteger<uint64_t>(Data, Size, Rand);
-    case 2: return ChangeBinaryInteger<uint32_t>(Data, Size, Rand);
-    case 1: return ChangeBinaryInteger<uint16_t>(Data, Size, Rand);
-    case 0: return ChangeBinaryInteger<uint8_t>(Data, Size, Rand);
-    default: assert(0);
-  }
-  return 0;
-}
-
-size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size,
-                                            size_t MaxSize) {
-  if (Size > MaxSize) return 0;
-  if (Size == 0) return 0;
-  if (!CrossOverWith) return 0;
-  const Unit &O = *CrossOverWith;
-  if (O.empty()) return 0;
-  size_t NewSize = 0;
-  switch(Rand(3)) {
-    case 0:
-      MutateInPlaceHere.resize(MaxSize);
-      NewSize = CrossOver(Data, Size, O.data(), O.size(),
-                          MutateInPlaceHere.data(), MaxSize);
-      memcpy(Data, MutateInPlaceHere.data(), NewSize);
-      break;
-    case 1:
-      NewSize = InsertPartOf(O.data(), O.size(), Data, Size, MaxSize);
-      if (!NewSize)
-        NewSize = CopyPartOf(O.data(), O.size(), Data, Size);
-      break;
-    case 2:
-      NewSize = CopyPartOf(O.data(), O.size(), Data, Size);
-      break;
-    default: assert(0);
-  }
-  assert(NewSize > 0 && "CrossOver returned empty unit");
-  assert(NewSize <= MaxSize && "CrossOver returned overisized unit");
-  return NewSize;
-}
-
-void MutationDispatcher::StartMutationSequence() {
-  CurrentMutatorSequence.clear();
-  CurrentDictionaryEntrySequence.clear();
-}
-
-// Copy successful dictionary entries to PersistentAutoDictionary.
-void MutationDispatcher::RecordSuccessfulMutationSequence() {
-  for (auto DE : CurrentDictionaryEntrySequence) {
-    // PersistentAutoDictionary.AddWithSuccessCountOne(DE);
-    DE->IncSuccessCount();
-    assert(DE->GetW().size());
-    // Linear search is fine here as this happens seldom.
-    if (!PersistentAutoDictionary.ContainsWord(DE->GetW()))
-      PersistentAutoDictionary.push_back(*DE);
-  }
-}
-
-void MutationDispatcher::PrintRecommendedDictionary() {
-  Vector<DictionaryEntry> V;
-  for (auto &DE : PersistentAutoDictionary)
-    if (!ManualDictionary.ContainsWord(DE.GetW()))
-      V.push_back(DE);
-  if (V.empty()) return;
+void PrintRecommendedDictionary(MutationDispatcher &MD) {
+  auto RecommendedDictionary = MD.RecommendDictionary();
+  if (RecommendedDictionary.empty())
+    return;
   Printf("###### Recommended dictionary. ######\n");
-  for (auto &DE: V) {
+  for (auto &DE : RecommendedDictionary) {
     assert(DE.GetW().size());
     Printf("\"");
     PrintASCII(DE.GetW(), "\"");
     Printf(" # Uses: %zd\n", DE.GetUseCount());
   }
   Printf("###### End of recommended dictionary. ######\n");
 }
 
-void MutationDispatcher::PrintMutationSequence(bool Verbose) {
-  Printf("MS: %zd ", CurrentMutatorSequence.size());
-  size_t EntriesToPrint =
-      Verbose ? CurrentMutatorSequence.size()
-              : std::min(kMaxMutationsToPrint, CurrentMutatorSequence.size());
-  for (size_t i = 0; i < EntriesToPrint; i++)
-    Printf("%s-", CurrentMutatorSequence[i].Name);
-  if (!CurrentDictionaryEntrySequence.empty()) {
-    Printf(" DE: ");
-    EntriesToPrint = Verbose ? CurrentDictionaryEntrySequence.size()
-                             : std::min(kMaxMutationsToPrint,
-                                        CurrentDictionaryEntrySequence.size());
-    for (size_t i = 0; i < EntriesToPrint; i++) {
-      Printf("\"");
-      PrintASCII(CurrentDictionaryEntrySequence[i]->GetW(), "\"-");
-    }
-  }
-}
-
-std::string MutationDispatcher::MutationSequence() {
-  std::string MS;
-  for (auto M : CurrentMutatorSequence) {
-    MS += M.Name;
-    MS += "-";
-  }
-  return MS;
-}
-
-size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
-  return MutateImpl(Data, Size, MaxSize, Mutators);
-}
-
-size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size,
-                                         size_t MaxSize) {
-  return MutateImpl(Data, Size, MaxSize, DefaultMutators);
-}
-
-// Mutates Data in place, returns new size.
-size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
-                                      size_t MaxSize,
-                                      Vector<Mutator> &Mutators) {
-  assert(MaxSize > 0);
-  // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
-  // in which case they will return 0.
-  // Try several times before returning un-mutated data.
-  for (int Iter = 0; Iter < 100; Iter++) {
-    auto M = Mutators[Rand(Mutators.size())];
-    size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
-    if (NewSize && NewSize <= MaxSize) {
-      if (Options.OnlyASCII)
-        ToASCII(Data, NewSize);
-      CurrentMutatorSequence.push_back(M);
-      return NewSize;
-    }
-  }
-  *Data = ' ';
-  return 1;   // Fallback, should not happen frequently.
-}
-
-// Mask represents the set of Data bytes that are worth mutating.
-size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size,
-                                          size_t MaxSize,
-                                          const Vector<uint8_t> &Mask) {
-  size_t MaskedSize = std::min(Size, Mask.size());
-  // * Copy the worthy bytes into a temporary array T
-  // * Mutate T
-  // * Copy T back.
-  // This is totally unoptimized.
-  auto &T = MutateWithMaskTemp;
-  if (T.size() < Size)
-    T.resize(Size);
-  size_t OneBits = 0;
-  for (size_t I = 0; I < MaskedSize; I++)
-    if (Mask[I])
-      T[OneBits++] = Data[I];
-
-  if (!OneBits) return 0;
-  assert(!T.empty());
-  size_t NewSize = Mutate(T.data(), OneBits, OneBits);
-  assert(NewSize <= OneBits);
-  (void)NewSize;
-  // Even if NewSize < OneBits we still use all OneBits bytes.
-  for (size_t I = 0, J = 0; I < MaskedSize; I++)
-    if (Mask[I])
-      Data[I] = T[J++];
-  return Size;
-}
-
-void MutationDispatcher::AddWordToManualDictionary(const Word &W) {
-  ManualDictionary.push_back(
-      {W, std::numeric_limits<size_t>::max()});
+void PrintMutationSequence(MutationDispatcher &MD, bool Verbose) {
+  const auto &MS = MD.MutationSequence();
+  const auto &DS = MD.DictionaryEntrySequence();
+  Printf("MS: %zd %s", MS.size(), MS.GetString(Verbose).c_str());
+  if (!DS.empty())
+    Printf(" DE: %s", DS.GetString(Verbose).c_str());
 }
 
 }  // namespace fuzzer

compiler-rt/lib/fuzzer/FuzzerRandom.h

 //===- FuzzerRandom.h - Internal header for the Fuzzer ----------*- C++ -* ===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // fuzzer::Random
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_FUZZER_RANDOM_H
 #define LLVM_FUZZER_RANDOM_H
 
+#include <cassert>
 #include <random>
 
 namespace fuzzer {
 class Random : public std::minstd_rand {
  public:
   Random(unsigned int seed) : std::minstd_rand(seed) {}
   result_type operator()() { return this->std::minstd_rand::operator()(); }
   template <typename T>

compiler-rt/lib/fuzzer/FuzzerTracePC.h

 //===- FuzzerTracePC.h - Internal header for the Fuzzer ---------*- C++ -* ===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // fuzzer::TracePC
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_FUZZER_TRACE_PC
 #define LLVM_FUZZER_TRACE_PC
 
 #include "FuzzerDefs.h"
-#include "FuzzerDictionary.h"
+#include "FuzzerUtil.h"
 #include "FuzzerValueBitMap.h"
 
 #include <set>
 #include <unordered_map>
 
 namespace fuzzer {
 
 // TableOfRecentCompares (TORC) remembers the most recently performed
struct TableOfRecentCompares {
   };
   ATTRIBUTE_NO_SANITIZE_ALL
   void Insert(size_t Idx, const T &Arg1, const T &Arg2) {
     Idx = Idx % kSize;
     Table[Idx].A = Arg1;
     Table[Idx].B = Arg2;
   }
 
-  Pair Get(size_t I) { return Table[I % kSize]; }
+  const Pair &Get(size_t I) { return Table[I % kSize]; }
 
   Pair Table[kSize];
 };
 
 template <size_t kSizeT>
 struct MemMemTable {
   static const size_t kSize = kSizeT;
   Word MemMemWords[kSize];

compiler-rt/lib/fuzzer/FuzzerTracePC.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "FuzzerTracePC.h"
 #include "FuzzerBuiltins.h"
 #include "FuzzerBuiltinsMsvc.h"
 #include "FuzzerCorpus.h"
 #include "FuzzerDefs.h"
-#include "FuzzerDictionary.h"
 #include "FuzzerExtFunctions.h"
 #include "FuzzerIO.h"
 #include "FuzzerPlatform.h"
 #include "FuzzerUtil.h"
 #include "FuzzerValueBitMap.h"
 #include <set>
 
 // Used by -fsanitize-coverage=stack-depth to track stack depth

compiler-rt/lib/fuzzer/FuzzerUtil.h

 std::string DescribePC(const char *SymbolizedFMT, uintptr_t PC);
 
 void PrintStackTrace();
 
 void PrintMemoryProfile();
 
 unsigned NumberOfCpuCores();
 
+// Parses one dictionary entry.
+// If successful, write the enty to Unit and returns true,
+// otherwise returns false.
+bool ParseOneDictionaryEntry(const std::string &Str, Unit *U);
+
+// Parses the dictionary file, fills Units, returns true iff all lines
+// were parsed successfully.
+bool ParseDictionaryFile(const std::string &Text, Vector<Unit> *Units);
+
 // Platform specific functions.
 void SetSignalHandler(const FuzzingOptions& Options);
 
 void SleepSeconds(int Seconds);
 
 unsigned long GetPid();
 
 size_t GetPeakRSSMb();
 
 int ExecuteCommand(const Command &Cmd);
 bool ExecuteCommand(const Command &Cmd, std::string *CmdOutput);
 
 // Fuchsia does not have popen/pclose.
 FILE *OpenProcessPipe(const char *Command, const char *Mode);
 int CloseProcessPipe(FILE *F);
 
-const void *SearchMemory(const void *haystack, size_t haystacklen,
-                         const void *needle, size_t needlelen);
-
 std::string CloneArgsWithoutX(const Vector<std::string> &Args,
                               const char *X1, const char *X2);
 
 inline std::string CloneArgsWithoutX(const Vector<std::string> &Args,
                                      const char *X) {
   return CloneArgsWithoutX(Args, X, X);
 }
 

compiler-rt/lib/fuzzer/FuzzerUtilFuchsia.cpp

bool ExecuteCommand(const Command &BaseCmd, std::string *CmdOutput) {
   Command Cmd(BaseCmd);
   Cmd.setOutputFile(LogFilePath);
   int Ret = ExecuteCommand(Cmd);
   *CmdOutput = FileToString(LogFilePath);
   RemoveFile(LogFilePath);
   return Ret == 0;
 }
 
-const void *SearchMemory(const void *Data, size_t DataLen, const void *Patt,
-                         size_t PattLen) {
-  return memmem(Data, DataLen, Patt, PattLen);
-}
-
 // In fuchsia, accessing /dev/null is not supported. There's nothing
 // similar to a file that discards everything that is written to it.
 // The way of doing something similar in fuchsia is by using
 // fdio_null_create and binding that to a file descriptor.
 void DiscardOutput(int Fd) {
   fdio_t *fdio_null = fdio_null_create();
   if (fdio_null == nullptr) return;
   int nullfd = fdio_bind_to_fd(fdio_null, -1, 0);
   if (nullfd < 0) return;
   dup2(nullfd, Fd);
 }
 
 } // namespace fuzzer
 
 #endif // LIBFUZZER_FUCHSIA

compiler-rt/lib/fuzzer/FuzzerUtilPosix.cpp

 FILE *OpenProcessPipe(const char *Command, const char *Mode) {
   return popen(Command, Mode);
 }
 
 int CloseProcessPipe(FILE *F) {
   return pclose(F);
 }
 
-const void *SearchMemory(const void *Data, size_t DataLen, const void *Patt,
-                         size_t PattLen) {
-  return memmem(Data, DataLen, Patt, PattLen);
-}
-
 std::string DisassembleCmd(const std::string &FileName) {
   return "objdump -d " + FileName;
 }
 
 std::string SearchRegexCmd(const std::string &Regex) {
   return "grep '" + Regex + "'";
 }
 
 }  // namespace fuzzer
 
 #endif // LIBFUZZER_POSIX

compiler-rt/lib/fuzzer/FuzzerUtilWindows.cpp

bool ExecuteCommand(const Command &Cmd, std::string *CmdOutput) {
   if (CmdOutput) {
     char TmpBuffer[128];
     while (fgets(TmpBuffer, sizeof(TmpBuffer), Pipe))
       CmdOutput->append(TmpBuffer);
   }
   return _pclose(Pipe) == 0;
 }
 
-const void *SearchMemory(const void *Data, size_t DataLen, const void *Patt,
-                         size_t PattLen) {
-  // TODO: make this implementation more efficient.
-  const char *Cdata = (const char *)Data;
-  const char *Cpatt = (const char *)Patt;
-
-  if (!Data || !Patt || DataLen == 0 || PattLen == 0 || DataLen < PattLen)
-    return NULL;
-
-  if (PattLen == 1)
-    return memchr(Data, *Cpatt, DataLen);
-
-  const char *End = Cdata + DataLen - PattLen + 1;
-
-  for (const char *It = Cdata; It < End; ++It)
-    if (It[0] == Cpatt[0] && memcmp(It, Cpatt, PattLen) == 0)
-      return It;
-
-  return NULL;
-}
-
 std::string DisassembleCmd(const std::string &FileName) {
   Vector<std::string> command_vector;
   command_vector.push_back("dumpbin /summary > nul");
   if (ExecuteCommand(Command(command_vector)) == 0)
     return "dumpbin /disasm " + FileName;
   Printf("libFuzzer: couldn't find tool to disassemble (dumpbin)\n");
   exit(1);
 }

compiler-rt/lib/fuzzer/build.sh

 #!/bin/sh
 LIBFUZZER_SRC_DIR=$(dirname $0)
+LIBMUTAGEN_SRC_DIR=$LIBFUZZER_SRC_DIR/mutagen
 CXX="${CXX:-clang}"
-for f in $LIBFUZZER_SRC_DIR/*.cpp; do
-  $CXX -g -O2 -fno-omit-frame-pointer -std=c++11 $f -c &
+for f in $LIBFUZZER_SRC_DIR/*.cpp $LIBMUTAGEN_SRC_DIR/*.cpp; do
+  $CXX -g -O2 -fno-omit-frame-pointer -std=c++11 $f -c -I$LIBFUZZER_SRC_DIR &
 done
 wait
 rm -f libFuzzer.a
-ar ru libFuzzer.a Fuzzer*.o
-rm -f Fuzzer*.o
-
+ar ru libFuzzer.a Fuzzer*.o Mutagen*.o
+rm -f Fuzzer*.o Mutagen*.o

compiler-rt/lib/fuzzer/mutagen/CMakeLists.txt

+set(MUTAGEN_SOURCES
+  Mutagen.cpp
+  MutagenCrossOver.cpp
+  MutagenDispatcher.cpp
+  MutagenUtilPosix.cpp
+  MutagenUtilWindows.cpp)
+
+set(MUTAGEN_HEADERS
+  Mutagen.h
+  MutagenDictionary.h
+  MutagenDispatcher.h
+  MutagenUtil.h)
+
+# Expose the files in this library to libFuzzer for optimized, direct inclusion.
+set(LIBFUZZER_MUTAGEN_SOURCES ${MUTAGEN_SOURCES} PARENT_SCOPE)
+set(LIBFUZZER_MUTAGEN_HEADERS ${MUTAGEN_HEADERS} PARENT_SCOPE)
+
+# Reuse the following variables from libFuzzer:
+#   FUZZER_SUPPORTED_ARCH
+#   FUZZER_SUPPORTED_OS
+#   LIBFUZZER_CFLAGS
+#   LIBFUZZER_DEPS
+include_directories(..)
+
+add_compiler_rt_component(mutagen)
+
+add_compiler_rt_object_libraries(RTmutagen
+  OS ${FUZZER_SUPPORTED_OS}
+  ARCHS ${FUZZER_SUPPORTED_ARCH}
+  SOURCES ${MUTAGEN_SOURCES}
+  ADDITIONAL_HEADERS ${MUTAGEN_HEADERS}
+  CFLAGS ${LIBFUZZER_CFLAGS}
+  DEPS ${LIBFUZZER_DEPS})
+
+add_compiler_rt_runtime(clang_rt.mutagen
+  STATIC
+  OS ${FUZZER_SUPPORTED_OS}
+  ARCHS ${FUZZER_SUPPORTED_ARCH}
+  OBJECT_LIBS RTmutagen
+  CFLAGS ${LIBFUZZER_CFLAGS}
+  PARENT_TARGET mutagen)
+
+if(OS_NAME MATCHES "Linux|Fuchsia" AND
+   COMPILER_RT_LIBCXX_PATH AND
+   COMPILER_RT_LIBCXXABI_PATH)
+  foreach(arch ${FUZZER_SUPPORTED_ARCH})
+    get_target_flags_for_arch(${arch} TARGET_CFLAGS)
+    set(LIBCXX_${arch}_PREFIX ${CMAKE_CURRENT_BINARY_DIR}/libcxx_mutagen_${arch})
+    add_custom_libcxx(libcxx_mutagen_${arch} ${LIBCXX_${arch}_PREFIX}
+      CFLAGS ${TARGET_CFLAGS}
+      CMAKE_ARGS -DCMAKE_CXX_COMPILER_WORKS=ON
+                 -DCMAKE_POSITION_INDEPENDENT_CODE=ON
+                 -DLIBCXXABI_ENABLE_EXCEPTIONS=OFF
+                 -DLIBCXX_ABI_NAMESPACE=__Fuzzer)
+    target_compile_options(RTmutagen.${arch} PRIVATE -isystem ${LIBCXX_${arch}_PREFIX}/include/c++/v1)
+    add_dependencies(RTmutagen.${arch} libcxx_mutagen_${arch}-build)
+    partially_link_libcxx(mutagen ${LIBCXX_${arch}_PREFIX} ${arch})
+  endforeach()
+endif()

compiler-rt/lib/fuzzer/mutagen/Mutagen.h

+//===- Mutagen.h - Interface header for the mutagen -------------*- C++ -* ===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Define the interface between libMutagen and its consumers.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_FUZZER_MUTAGEN_H
+#define LLVM_FUZZER_MUTAGEN_H
+
+#include "FuzzerPlatform.h"
+#include <stddef.h>
+#include <stdint.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif // __cplusplus
+
+#define MAX_WORD_SIZE 64
+
+typedef struct {
+  // PRNG seed.
+  unsigned int Seed;
+
+  // If non-zero, use CMP traces to guide mutations. Ignored if any of
+  // |FromTORC4|, |FromTORC8|, or |FromTORCW| are null.
+  int UseCmp;
+  void (*FromTORC4)(size_t Idx, uint32_t *Arg1, uint32_t *Arg2);
+  void (*FromTORC8)(size_t Idx, uint64_t *Arg1, uint64_t *Arg2);
+  void (*FromTORCW)(size_t Idx, const uint8_t **Data1, size_t *Size1,
+                    const uint8_t **Data2, size_t *Size2);
+
+  // If non-zero, use hints from intercepting memmem, strstr, etc. Ignored if
+  // |UseCmp| is zero or if |FromMMT| is null.
+  int UseMemmem;
+  void (*FromMMT)(size_t Idx, const uint8_t **Data, size_t *Size);
+
+  // If non-zero, generate only ASCII (isprint+isspace) inputs.
+  int OnlyASCII;
+
+  // Optional user-provided custom mutator.
+  size_t (*CustomMutator)(uint8_t *Data, size_t Size, size_t MaxSize,
+                          unsigned int Seed);
+
+  // Optional user-provided custom cross-over function.
+  size_t (*CustomCrossOver)(const uint8_t *Data1, size_t Size1,
+                            const uint8_t *Data2, size_t Size2, uint8_t *Out,
+                            size_t MaxOutSize, unsigned int Seed);
+
+  // Optional MemorySanitizer callbacks.
+  void (*MSanUnpoison)(const volatile void *, size_t size);
+  void (*MSanUnpoisonParam)(size_t n);
+} LLVMMutagenConfiguration;
+
+// Re-seeds the PRNG and sets mutator-related options.
+ATTRIBUTE_INTERFACE void
+LLVMMutagenConfigure(const LLVMMutagenConfiguration *config);
+
+// Writes the mutation sequence to |Out|, and returns the number of
+// characters it wrote, or would have written given a large enough buffer,
+// excluding the null terminator. Thus, a return value of |Max| or greater
+// indicates the sequence was truncated (like snprintf). May truncate the
+// sequence unless |Verbose| is non-zero. Sets |OutNumItems| to the number of
+// items in the untruncated sequence.
+ATTRIBUTE_INTERFACE size_t LLVMMutagenGetMutationSequence(int Verbose,
+                                                          char *Out, size_t Max,
+                                                          size_t *OutNumItems);
+
+// Writes the dictionary entry sequence to |Out|, and returns the number of
+// characters it wrote, or would have written given a large enough buffer,
+// excluding a null terminator. Thus, a return value of |Max| or greater
+// indicates the sequence was truncated (like snprintf). May truncate the
+// sequence unless |Verbose| is non-zero. Sets |OutNumItems| to the number of
+// items in the untruncated sequence.
+ATTRIBUTE_INTERFACE size_t LLVMMutagenGetDictionaryEntrySequence(
+    int Verbose, char *Out, size_t Max, size_t *OutNumItems);
+
+// Instructs the library to record the current mutation sequence as successful
+// at increasing coverage.
+ATTRIBUTE_INTERFACE void LLVMMutagenRecordSequence();
+
+// Clears the mutation and dictionary entry sequences.
+ATTRIBUTE_INTERFACE void LLVMMutagenResetSequence();
+
+// Adds data used by various mutators to produce new inputs.
+ATTRIBUTE_INTERFACE void LLVMMutagenSetCrossOverWith(const uint8_t *Data,
+                                                     size_t Size);
+ATTRIBUTE_INTERFACE void LLVMMutagenAddWordToDictionary(const uint8_t *Word,
+                                                        size_t Size);
+
+// Mutates the contents of |Data| and returns the new size.
+ATTRIBUTE_INTERFACE size_t LLVMMutagenMutate(uint8_t *Data, size_t Size,
+                                             size_t Max);
+
+// Like |LLVMMutagenMutate|, but never selects the custom mutators and is
+// therefore suitable to be called from them.
+ATTRIBUTE_INTERFACE size_t LLVMMutagenDefaultMutate(uint8_t *Data, size_t Size,
+                                                    size_t Max);
+
+// Creates a recommended dictionary and returns its number of entries. The
+// entries can be retrieved by subsequent calls to
+// |LLVMMutagenRecommendDictionaryEntry|.
+ATTRIBUTE_INTERFACE size_t LLVMMutagenRecommendDictionary();
+
+// Returns the ASCII representation of the next recommended dictionary entry,
+// or null if no entries remain (or |LLVMMutagenRecommendDictionary| wasn't
+// called). If non-null, the return pointer is valid until the next call to this
+// method, and if provided, |OutUseCount| is set to the entry's use count.
+ATTRIBUTE_INTERFACE const char *
+LLVMMutagenRecommendDictionaryEntry(size_t *OutUseCount);
+
+#ifdef __cplusplus
+} // extern "C"
+#endif // __cplusplus
+
+#endif // LLVM_FUZZER_MUTAGEN_H

compiler-rt/lib/fuzzer/mutagen/Mutagen.cpp

+//===- Mutagen.cpp - Interface header for the mutagen -----------*- C++ -* ===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Define the interface between libMutagen and its consumers.
+//===----------------------------------------------------------------------===//
+
+#include "Mutagen.h"
+#include "FuzzerDefs.h"
+#include "MutagenDispatcher.h"
+#include <algorithm>
+#include <cstdio>
+#include <string>
+
+namespace mutagen {
+namespace {
+
+MutationDispatcher *MD = nullptr;
+
+} // namespace
+
+MutationDispatcher *GetMutationDispatcherForTest() { return MD; }
+
+} // namespace mutagen
+
+using fuzzer::Unit;
+using mutagen::MD;
+using mutagen::MutationDispatcher;
+using mutagen::Word;
+
+extern "C" {
+
+ATTRIBUTE_INTERFACE void
+LLVMMutagenConfigure(const LLVMMutagenConfiguration *Config) {
+  if (MD)
+    delete MD;
+  MD = new MutationDispatcher(Config);
+}
+
+ATTRIBUTE_INTERFACE void LLVMMutagenResetSequence() {
+  MD->StartMutationSequence();
+}
+
+ATTRIBUTE_INTERFACE void LLVMMutagenSetCrossOverWith(const uint8_t *Data,
+                                                     size_t Size) {
+  static Unit CrossOverWith;
+  Unit U(Data, Data + Size);
+  CrossOverWith = std::move(U);
+  MD->SetCrossOverWith(&CrossOverWith);
+}
+
+ATTRIBUTE_INTERFACE size_t LLVMMutagenMutate(uint8_t *Data, size_t Size,
+                                             size_t Max) {
+  return MD->Mutate(Data, Size, Max);
+}
+
+ATTRIBUTE_INTERFACE size_t LLVMMutagenDefaultMutate(uint8_t *Data, size_t Size,
+                                                    size_t Max) {
+  return MD->DefaultMutate(Data, Size, Max);
+}
+
+ATTRIBUTE_INTERFACE void LLVMMutagenRecordSequence() {
+  MD->RecordSuccessfulMutationSequence();
+}
+
+ATTRIBUTE_INTERFACE size_t LLVMMutagenGetMutationSequence(int Verbose,
+                                                          char *Out, size_t Max,
+                                                          size_t *OutNumItems) {
+  const auto &Seq = MD->MutationSequence();
+  if (OutNumItems)
+    *OutNumItems = Seq.size();
+  return snprintf(Out, Max, "%s", Seq.GetString(Verbose).c_str());
+}
+
+ATTRIBUTE_INTERFACE void LLVMMutagenAddWordToDictionary(const uint8_t *Data,
+                                                        size_t Size) {
+  MD->AddWordToManualDictionary(Word(Data, std::min(Size, Word::GetMaxSize())));
+}
+
+ATTRIBUTE_INTERFACE size_t LLVMMutagenGetDictionaryEntrySequence(
+    int Verbose, char *Out, size_t Max, size_t *OutNumItems) {
+  const auto &Seq = MD->DictionaryEntrySequence();
+  if (OutNumItems)
+    *OutNumItems = Seq.size();
+  return snprintf(Out, Max, "%s", Seq.GetString(Verbose).c_str());
+}
+
+ATTRIBUTE_INTERFACE size_t LLVMMutagenRecommendDictionary() {
+  return MD->RecommendDictionary().size();
+}
+
+ATTRIBUTE_INTERFACE const char *
+LLVMMutagenRecommendDictionaryEntry(size_t *OutUseCount) {
+  return MD->RecommendDictionaryEntry(OutUseCount);
+}
+
+} // extern "C"

compiler-rt/lib/fuzzer/mutagen/MutagenCrossOver.cpp

-//===- FuzzerCrossOver.cpp - Cross over two test inputs -------------------===//
+//===- MutagenCrossOver.cpp - Cross over two test inputs ------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // Cross over test inputs.
 //===----------------------------------------------------------------------===//
 
-#include "FuzzerDefs.h"
-#include "FuzzerMutate.h"
 #include "FuzzerRandom.h"
+#include "MutagenDispatcher.h"
 #include <cstring>
 
-namespace fuzzer {
+namespace mutagen {
 
 // Cross Data1 and Data2, store the result (up to MaxOutSize bytes) in Out.
 size_t MutationDispatcher::CrossOver(const uint8_t *Data1, size_t Size1,
                                      const uint8_t *Data2, size_t Size2,
                                      uint8_t *Out, size_t MaxOutSize) {
   assert(Size1 || Size2);
   MaxOutSize = Rand(MaxOutSize) + 1;
   size_t OutPos = 0;
if (*InPos < InSize) {
       size_t InSizeLeft = InSize - *InPos;
       size_t MaxExtraSize = std::min(OutSizeLeft, InSizeLeft);
       size_t ExtraSize = Rand(MaxExtraSize) + 1;
       memcpy(Out + OutPos, Data + *InPos, ExtraSize);
       OutPos += ExtraSize;
       (*InPos) += ExtraSize;
     }
     // Use the other input data on the next iteration.
-    InPos  = CurrentlyUsingFirstData ? &Pos2 : &Pos1;
+    InPos = CurrentlyUsingFirstData ? &Pos2 : &Pos1;
     InSize = CurrentlyUsingFirstData ? Size2 : Size1;
-    Data   = CurrentlyUsingFirstData ? Data2 : Data1;
+    Data = CurrentlyUsingFirstData ? Data2 : Data1;
     CurrentlyUsingFirstData = !CurrentlyUsingFirstData;
   }
   return OutPos;
 }
 
-}  // namespace fuzzer
+} // namespace mutagen

compiler-rt/lib/fuzzer/mutagen/MutagenDictionary.h

+//===- MutagenDictionary.h - Internal header for the mutagen ----*- C++ -* ===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// mutagen::Dictionary
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_FUZZER_MUTAGEN_DICTIONARY_H
+#define LLVM_FUZZER_MUTAGEN_DICTIONARY_H
+
+#include "FuzzerDefs.h"
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+
+namespace mutagen {
+namespace {
+
+using fuzzer::Word;
+
+} // namespace
+
+class DictionaryEntry {
+public:
+  DictionaryEntry() {}
+  DictionaryEntry(Word W) : W(W) {}
+  DictionaryEntry(Word W, size_t PositionHint)
+      : W(W), PositionHint(PositionHint) {}
+  const Word &GetW() const { return W; }
+
+  bool HasPositionHint() const {
+    return PositionHint != std::numeric_limits<size_t>::max();
+  }
+  size_t GetPositionHint() const {
+    assert(HasPositionHint());
+    return PositionHint;
+  }
+  void IncUseCount() { UseCount++; }
+  void IncSuccessCount() { SuccessCount++; }
+  size_t GetUseCount() const { return UseCount; }
+  size_t GetSuccessCount() const { return SuccessCount; }
+
+private:
+  Word W;
+  size_t PositionHint = std::numeric_limits<size_t>::max();
+  size_t UseCount = 0;
+  size_t SuccessCount = 0;
+};
+
+class Dictionary {
+public:
+  static const size_t kMaxDictSize = 1 << 14;
+
+  bool ContainsWord(const Word &W) const {
+    return std::any_of(begin(), end(), [&](const DictionaryEntry &DE) {
+      return DE.GetW() == W;
+    });
+  }
+  const DictionaryEntry *begin() const { return &DE[0]; }
+  const DictionaryEntry *end() const { return begin() + Size; }
+  DictionaryEntry &operator[](size_t Idx) {
+    assert(Idx < Size);
+    return DE[Idx];
+  }
+  void push_back(DictionaryEntry DE) {
+    if (Size < kMaxDictSize)
+      this->DE[Size++] = DE;
+  }
+  void clear() { Size = 0; }
+  bool empty() const { return Size == 0; }
+  size_t size() const { return Size; }
+
+private:
+  DictionaryEntry DE[kMaxDictSize];
+  size_t Size = 0;
+};
+
+} // namespace mutagen
+
+#endif // LLVM_FUZZER_MUTAGEN_DICTIONARY_H

compiler-rt/lib/fuzzer/mutagen/MutagenDispatcher.h

+//===- MutagenDispatcher.h - Internal header for the mutagen ----*- C++ -* ===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// mutagen::MutationDispatcher
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_FUZZER_MUTAGEN_DISPATCHER_H
+#define LLVM_FUZZER_MUTAGEN_DISPATCHER_H
+
+#include "FuzzerRandom.h"
+#include "Mutagen.h"
+#include "MutagenDictionary.h"
+#include "MutagenSequence.h"
+#include <cstddef>
+#include <cstdint>
+#include <string>
+
+namespace mutagen {
+namespace {
+
+using fuzzer::Random;
+using fuzzer::Unit;
+using fuzzer::Vector;
+using fuzzer::Word;
+
+} // namespace
+
+class MutationDispatcher final {
+public:
+  struct Mutator {
+    size_t (MutationDispatcher::*Fn)(uint8_t *Data, size_t Size, size_t Max);
+    const char *Name;
+  };
+
+  explicit MutationDispatcher(const LLVMMutagenConfiguration *Config);
+  ~MutationDispatcher() = default;
+
+  /// Indicate that we are about to start a new sequence of mutations.
+  void StartMutationSequence();
+  /// Returns the current sequence of mutations. May truncate the sequence
+  /// unless Verbose is true. Sets |OutSize| to the length of the untrancated
+  /// sequence, if provided.
+  const Sequence<Mutator> &MutationSequence();
+  /// Returns the current sequence of dictionary entries. May truncate the
+  /// sequence unless Verbose is true. Sets |OutSize| to the length of the
+  /// untrancated sequence, if provided.
+  const Sequence<DictionaryEntry *> &DictionaryEntrySequence();
+  /// Indicate that the current sequence of mutations was successful.
+  void RecordSuccessfulMutationSequence();
+  /// Mutates data by invoking user-provided mutator.
+  size_t Mutate_Custom(uint8_t *Data, size_t Size, size_t MaxSize);
+  /// Mutates data by invoking user-provided crossover.
+  size_t Mutate_CustomCrossOver(uint8_t *Data, size_t Size, size_t MaxSize);
+  /// Mutates data by shuffling bytes.
+  size_t Mutate_ShuffleBytes(uint8_t *Data, size_t Size, size_t MaxSize);
+  /// Mutates data by erasing bytes.
+  size_t Mutate_EraseBytes(uint8_t *Data, size_t Size, size_t MaxSize);
+  /// Mutates data by inserting a byte.
+  size_t Mutate_InsertByte(uint8_t *Data, size_t Size, size_t MaxSize);
+  /// Mutates data by inserting several repeated bytes.
+  size_t Mutate_InsertRepeatedBytes(uint8_t *Data, size_t Size, size_t MaxSize);
+  /// Mutates data by changing one byte.
+  size_t Mutate_ChangeByte(uint8_t *Data, size_t Size, size_t MaxSize);
+  /// Mutates data by changing one bit.
+  size_t Mutate_ChangeBit(uint8_t *Data, size_t Size, size_t MaxSize);
+  /// Mutates data by copying/inserting a part of data into a different place.
+  size_t Mutate_CopyPart(uint8_t *Data, size_t Size, size_t MaxSize);
+
+  /// Mutates data by adding a word from the manual dictionary.
+  size_t Mutate_AddWordFromManualDictionary(uint8_t *Data, size_t Size,
+                                            size_t MaxSize);
+
+  /// Mutates data by adding a word from the TORC.
+  size_t Mutate_AddWordFromTORC(uint8_t *Data, size_t Size, size_t MaxSize);
+
+  /// Mutates data by adding a word from the persistent automatic dictionary.
+  size_t Mutate_AddWordFromPersistentAutoDictionary(uint8_t *Data, size_t Size,
+                                                    size_t MaxSize);
+
+  /// Tries to find an ASCII integer in Data, changes it to another ASCII int.
+  size_t Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size, size_t MaxSize);
+  /// Change a 1-, 2-, 4-, or 8-byte integer in interesting ways.
+  size_t Mutate_ChangeBinaryInteger(uint8_t *Data, size_t Size, size_t MaxSize);
+
+  /// CrossOver Data with CrossOverWith.
+  size_t Mutate_CrossOver(uint8_t *Data, size_t Size, size_t MaxSize);
+
+  size_t AddWordFromDictionary(Dictionary &D, uint8_t *Data, size_t Size,
+                               size_t MaxSize);
+  size_t MutateImpl(uint8_t *Data, size_t Size, size_t MaxSize,
+                    Vector<Mutator> &Mutators);
+
+  size_t InsertPartOf(const uint8_t *From, size_t FromSize, uint8_t *To,
+                      size_t ToSize, size_t MaxToSize);
+  size_t CopyPartOf(const uint8_t *From, size_t FromSize, uint8_t *To,
+                    size_t ToSize);
+  size_t ApplyDictionaryEntry(uint8_t *Data, size_t Size, size_t MaxSize,
+                              DictionaryEntry &DE);
+
+  template <class T>
+  DictionaryEntry MakeDictionaryEntryFromCMP(T Arg1, T Arg2,
+                                             const uint8_t *Data, size_t Size);
+  DictionaryEntry MakeDictionaryEntryFromCMP(const Word &Arg1, const Word &Arg2,
+                                             const uint8_t *Data, size_t Size);
+  DictionaryEntry MakeDictionaryEntryFromCMP(const void *Arg1, const void *Arg2,
+                                             const void *Arg1Mutation,
+                                             const void *Arg2Mutation,
+                                             size_t ArgSize,
+                                             const uint8_t *Data, size_t Size);
+
+  /// Applies one of the configured mutations.
+  /// Returns the new size of data which could be up to MaxSize.
+  size_t Mutate(uint8_t *Data, size_t Size, size_t MaxSize);
+
+  /// Applies one of the configured mutations to the bytes of Data
+  /// that have '1' in Mask.
+  /// Mask.size() should be >= Size.
+  size_t MutateWithMask(uint8_t *Data, size_t Size, size_t MaxSize,
+                        const Vector<uint8_t> &Mask);
+
+  /// Applies one of the default mutations. Provided as a service
+  /// to mutation authors.
+  size_t DefaultMutate(uint8_t *Data, size_t Size, size_t MaxSize);
+
+  /// Creates a cross-over of two pieces of Data, returns its size.
+  size_t CrossOver(const uint8_t *Data1, size_t Size1, const uint8_t *Data2,
+                   size_t Size2, uint8_t *Out, size_t MaxOutSize);
+
+  void AddWordToManualDictionary(const Word &W);
+
+  // Creates a recommended dictionary and returns its number of entries. The
+  // entries can be retrieved by subsequent calls to
+  // |LLVMMutagenRecommendDictionaryEntry|.
+  const Dictionary &RecommendDictionary();
+
+  // Returns the ASCII representation of the next recommended dictionary entry,
+  // and sets |OutUseCount| to its use count. The return pointer is valid until
+  // the next call to this method.
+  const char *RecommendDictionaryEntry(size_t *OutUseCount);
+
+  void SetCrossOverWith(const Unit *U) { CrossOverWith = U; }
+
+  Random &GetRand() { return Rand; }
+
+private:
+  // Imports and validates the disptacher's configuration.
+  void SetConfig(const LLVMMutagenConfiguration *Config);
+
+  Random Rand;
+  LLVMMutagenConfiguration Config;
+
+  // Dictionary provided by the user via -dict=DICT_FILE.
+  Dictionary ManualDictionary;
+  // Persistent dictionary modified by the fuzzer, consists of
+  // entries that led to successful discoveries in the past mutations.
+  Dictionary PersistentAutoDictionary;
+  // Recommended dictionary buolt by |RecommendDictionary|.
+  Dictionary RecommendedDictionary;
+  size_t NextRecommendedDictionaryEntry = 0;
+  std::string DictionaryEntryWord;
+
+  Sequence<DictionaryEntry *> CurrentDictionaryEntrySequence;
+
+  static const size_t kCmpDictionaryEntriesDequeSize = 16;
+  DictionaryEntry CmpDictionaryEntriesDeque[kCmpDictionaryEntriesDequeSize];
+  size_t CmpDictionaryEntriesDequeIdx = 0;
+
+  const Unit *CrossOverWith = nullptr;
+  Vector<uint8_t> MutateInPlaceHere;
+  Vector<uint8_t> MutateWithMaskTemp;
+  // CustomCrossOver needs its own buffer as a custom implementation may call
+  // LLVMFuzzerMutate, which in turn may resize MutateInPlaceHere.
+  Vector<uint8_t> CustomCrossOverInPlaceHere;
+
+  Vector<Mutator> Mutators;
+  Vector<Mutator> DefaultMutators;
+  Sequence<Mutator> CurrentMutatorSequence;
+};
+
+// Returns a pointer to the MutationDispatcher is use by MutagenInterface.
+// This should only be used for testing.
+MutationDispatcher *GetMutationDispatcherForTest();
+
+} // namespace mutagen
+
+#endif // LLVM_FUZZER_MUTAGEN_DISPATCHER_H

compiler-rt/lib/fuzzer/mutagen/MutagenDispatcher.cpp

+//===- MutagenDispatcher.cpp - Mutate a test input ------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Mutate a test input.
+//===----------------------------------------------------------------------===//
+
+#include "MutagenDispatcher.h"
+#include "FuzzerBuiltins.h"
+#include "FuzzerPlatform.h"
+#include "MutagenUtil.h"
+#include <iomanip>
+#include <sstream>
+
+namespace mutagen {
+namespace {
+
+using fuzzer::Bswap;
+
+std::string ToASCII(const uint8_t *Data, size_t Size) {
+  std::ostringstream OSS;
+  for (size_t i = 0; i < Size; i++) {
+    uint16_t Byte = Data[i];
+    if (Byte == '\\')
+      OSS << "\\\\";
+    else if (Byte == '"')
+      OSS << "\\\"";
+    else if (Byte >= 32 && Byte < 127)
+      OSS << static_cast<char>(Byte);
+    else
+      OSS << "\\x" << std::hex << std::setw(2) << std::setfill('0') << Byte
+          << std::dec;
+  }
+  return OSS.str();
+}
+
+std::string ToASCII(const Word &W) { return ToASCII(W.data(), W.size()); }
+
+} // namespace
+
+void MutationDispatcher::SetConfig(const LLVMMutagenConfiguration *C) {
+  memcpy(&Config, C, sizeof(Config));
+  if (!Config.FromTORC4 || !Config.FromTORC8 || !Config.FromTORCW)
+    Config.UseCmp = 0;
+  if (!Config.FromMMT)
+    Config.UseMemmem = 0;
+}
+
+MutationDispatcher::MutationDispatcher(const LLVMMutagenConfiguration *config)
+    : Rand(config->Seed) {
+  SetConfig(config);
+  DefaultMutators.insert(
+      DefaultMutators.begin(),
+      {
+          {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"},
+          {&MutationDispatcher::Mutate_InsertByte, "InsertByte"},
+          {&MutationDispatcher::Mutate_InsertRepeatedBytes,
+           "InsertRepeatedBytes"},
+          {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"},
+          {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"},
+          {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"},
+          {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"},
+          {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"},
+          {&MutationDispatcher::Mutate_CopyPart, "CopyPart"},
+          {&MutationDispatcher::Mutate_CrossOver, "CrossOver"},
+          {&MutationDispatcher::Mutate_AddWordFromManualDictionary,
+           "ManualDict"},
+          {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary,
+           "PersAutoDict"},
+      });
+  if (Config.UseCmp)
+    DefaultMutators.push_back(
+        {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"});
+
+  if (Config.CustomMutator)
+    Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"});
+  else
+    Mutators = DefaultMutators;
+
+  if (Config.CustomCrossOver)
+    Mutators.push_back(
+        {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"});
+}
+
+static char RandCh(Random &Rand) {
+  if (Rand.RandBool())
+    return static_cast<char>(Rand(256));
+  const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00";
+  return Special[Rand(sizeof(Special) - 1)];
+}
+
+size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size,
+                                         size_t MaxSize) {
+  if (Config.MSanUnpoison)
+    Config.MSanUnpoison(Data, Size);
+  if (Config.MSanUnpoisonParam)
+    Config.MSanUnpoisonParam(4);
+  return Config.CustomMutator(Data, Size, MaxSize, Rand.Rand<unsigned int>());
+}
+
+size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size,
+                                                  size_t MaxSize) {
+  if (Size == 0)
+    return 0;
+  if (!CrossOverWith)
+    return 0;
+  const Unit &Other = *CrossOverWith;
+  if (Other.empty())
+    return 0;
+  CustomCrossOverInPlaceHere.resize(MaxSize);
+  auto &U = CustomCrossOverInPlaceHere;
+
+  if (Config.MSanUnpoison) {
+    Config.MSanUnpoison(Data, Size);
+    Config.MSanUnpoison(Other.data(), Other.size());
+    Config.MSanUnpoison(U.data(), U.size());
+  }
+  if (Config.MSanUnpoisonParam)
+    Config.MSanUnpoisonParam(7);
+  size_t NewSize =
+      Config.CustomCrossOver(Data, Size, Other.data(), Other.size(), U.data(),
+                             U.size(), Rand.Rand<unsigned int>());
+
+  if (!NewSize)
+    return 0;
+  assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit");
+  memcpy(Data, U.data(), NewSize);
+  return NewSize;
+}
+
+size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size,
+                                               size_t MaxSize) {
+  if (Size > MaxSize || Size == 0)
+    return 0;
+  size_t ShuffleAmount =
+      Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size.
+  size_t ShuffleStart = Rand(Size - ShuffleAmount);
+  assert(ShuffleStart + ShuffleAmount <= Size);
+  std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand);
+  return Size;
+}
+
+size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size,
+                                             size_t MaxSize) {
+  if (Size <= 1)
+    return 0;
+  size_t N = Rand(Size / 2) + 1;
+  assert(N < Size);
+  size_t Idx = Rand(Size - N + 1);
+  // Erase Data[Idx:Idx+N].
+  memmove(Data + Idx, Data + Idx + N, Size - Idx - N);
+  // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx);
+  return Size - N;
+}
+
+size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size,
+                                             size_t MaxSize) {
+  if (Size >= MaxSize)
+    return 0;
+  size_t Idx = Rand(Size + 1);
+  // Insert new value at Data[Idx].
+  memmove(Data + Idx + 1, Data + Idx, Size - Idx);
+  Data[Idx] = RandCh(Rand);
+  return Size + 1;
+}
+
+size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data,
+                                                      size_t Size,
+                                                      size_t MaxSize) {
+  const size_t kMinBytesToInsert = 3;
+  if (Size + kMinBytesToInsert >= MaxSize)
+    return 0;
+  size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128);
+  size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert;
+  assert(Size + N <= MaxSize && N);
+  size_t Idx = Rand(Size + 1);
+  // Insert new values at Data[Idx].
+  memmove(Data + Idx + N, Data + Idx, Size - Idx);
+  // Give preference to 0x00 and 0xff.
+  uint8_t Byte = static_cast<uint8_t>(
+      Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255));
+  for (size_t i = 0; i < N; i++)
+    Data[Idx + i] = Byte;
+  return Size + N;
+}
+
+size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size,
+                                             size_t MaxSize) {
+  if (Size > MaxSize)
+    return 0;
+  size_t Idx = Rand(Size);
+  Data[Idx] = RandCh(Rand);
+  return Size;
+}
+
+size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
+                                            size_t MaxSize) {
+  if (Size > MaxSize)
+    return 0;
+  size_t Idx = Rand(Size);
+  Data[Idx] ^= 1 << Rand(8);
+  return Size;
+}
+
+size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data,
+                                                              size_t Size,
+                                                              size_t MaxSize) {
+  return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize);
+}
+
+size_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size,
+                                                size_t MaxSize,
+                                                DictionaryEntry &DE) {
+  const Word &W = DE.GetW();
+  bool UsePositionHint = DE.HasPositionHint() &&
+                         DE.GetPositionHint() + W.size() < Size &&
+                         Rand.RandBool();
+  if (Rand.RandBool()) { // Insert W.
+    if (Size + W.size() > MaxSize)
+      return 0;
+    size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1);
+    memmove(Data + Idx + W.size(), Data + Idx, Size - Idx);
+    memcpy(Data + Idx, W.data(), W.size());
+    Size += W.size();
+  } else { // Overwrite some bytes with W.
+    if (W.size() > Size)
+      return 0;
+    size_t Idx =
+        UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1 - W.size());
+    memcpy(Data + Idx, W.data(), W.size());
+  }
+  return Size;
+}
+
+// Somewhere in the past we have observed a comparison instructions
+// with arguments Arg1 Arg2. This function tries to guess a dictionary
+// entry that will satisfy that comparison.
+// It first tries to find one of the arguments (possibly swapped) in the
+// input and if it succeeds it creates a DE with a position hint.
+// Otherwise it creates a DE with one of the arguments w/o a position hint.
+DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
+    const void *Arg1, const void *Arg2, const void *Arg1Mutation,
+    const void *Arg2Mutation, size_t ArgSize, const uint8_t *Data,
+    size_t Size) {
+  bool HandleFirst = Rand.RandBool();
+  const void *ExistingBytes, *DesiredBytes;
+  Word W;
+  const uint8_t *End = Data + Size;
+  for (int Arg = 0; Arg < 2; Arg++) {
+    ExistingBytes = HandleFirst ? Arg1 : Arg2;
+    DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation;
+    HandleFirst = !HandleFirst;
+    W.Set(reinterpret_cast<const uint8_t *>(DesiredBytes), ArgSize);
+    const size_t kMaxNumPositions = 8;
+    size_t Positions[kMaxNumPositions];
+    size_t NumPositions = 0;
+    for (const uint8_t *Cur = Data;
+         Cur < End && NumPositions < kMaxNumPositions; Cur++) {
+      Cur =
+          (const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize);
+      if (!Cur)
+        break;
+      Positions[NumPositions++] = Cur - Data;
+    }
+    if (!NumPositions)
+      continue;
+    return DictionaryEntry(W, Positions[Rand(NumPositions)]);
+  }
+  DictionaryEntry DE(W);
+  return DE;
+}
+
+template <class T>
+DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
+    T Arg1, T Arg2, const uint8_t *Data, size_t Size) {
+  if (Rand.RandBool())
+    Arg1 = Bswap(Arg1);
+  if (Rand.RandBool())
+    Arg2 = Bswap(Arg2);
+  T Arg1Mutation = static_cast<T>(Arg1 + Rand(-1, 1));
+  T Arg2Mutation = static_cast<T>(Arg2 + Rand(-1, 1));
+  return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation,
+                                    sizeof(Arg1), Data, Size);
+}
+
+size_t MutationDispatcher::Mutate_AddWordFromTORC(uint8_t *Data, size_t Size,
+                                                  size_t MaxSize) {
+  Word W;
+  DictionaryEntry DE;
+  switch (Rand(4)) {
+  case 0: {
+    uint64_t A, B;
+    Config.FromTORC8(Rand.Rand<size_t>(), &A, &B);
+    DE = MakeDictionaryEntryFromCMP(A, B, Data, Size);
+  } break;
+  case 1: {
+    uint32_t A, B;
+    Config.FromTORC4(Rand.Rand<size_t>(), &A, &B);
+    if ((A >> 16) == 0 && (B >> 16) == 0 && Rand.RandBool())
+      DE = MakeDictionaryEntryFromCMP((uint16_t)A, (uint16_t)B, Data, Size);
+    else
+      DE = MakeDictionaryEntryFromCMP(A, B, Data, Size);
+  } break;
+  case 2: {
+    const uint8_t *DataA, *DataB;
+    size_t SizeA, SizeB;
+    Config.FromTORCW(Rand.Rand<size_t>(), &DataA, &SizeA, &DataB, &SizeB);
+    DE = MakeDictionaryEntryFromCMP(DataA, DataB, DataA, DataB, SizeA, Data,
+                                    Size);
+  } break;
+  case 3:
+    if (Config.UseMemmem) {
+      const uint8_t *DataW;
+      size_t SizeW;
+      Config.FromMMT(Rand.Rand<size_t>(), &DataW, &SizeW);
+      DE = DictionaryEntry(Word(DataW, SizeW));
+    }
+    break;
+  default:
+    assert(0);
+  }
+  if (!DE.GetW().size())
+    return 0;
+  Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE);
+  if (!Size)
+    return 0;
+  DictionaryEntry &DERef =
+      CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ %
+                                kCmpDictionaryEntriesDequeSize];
+  DERef = DE;
+  CurrentDictionaryEntrySequence.push_back(&DERef);
+  return Size;
+}
+
+size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary(
+    uint8_t *Data, size_t Size, size_t MaxSize) {
+  return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize);
+}
+
+size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data,
+                                                 size_t Size, size_t MaxSize) {
+  if (Size > MaxSize)
+    return 0;
+  if (D.empty())
+    return 0;
+  DictionaryEntry &DE = D[Rand(D.size())];
+  Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE);
+  if (!Size)
+    return 0;
+  DE.IncUseCount();
+  CurrentDictionaryEntrySequence.push_back(&DE);
+  return Size;
+}
+
+// Overwrites part of To[0,ToSize) with a part of From[0,FromSize).
+// Returns ToSize.
+size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize,
+                                      uint8_t *To, size_t ToSize) {
+  // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize).
+  size_t ToBeg = Rand(ToSize);
+  size_t CopySize = Rand(ToSize - ToBeg) + 1;
+  assert(ToBeg + CopySize <= ToSize);
+  CopySize = std::min(CopySize, FromSize);
+  size_t FromBeg = Rand(FromSize - CopySize + 1);
+  assert(FromBeg + CopySize <= FromSize);
+  memmove(To + ToBeg, From + FromBeg, CopySize);
+  return ToSize;
+}
+
+// Inserts part of From[0,ToSize) into To.
+// Returns new size of To on success or 0 on failure.
+size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize,
+                                        uint8_t *To, size_t ToSize,
+                                        size_t MaxToSize) {
+  if (ToSize >= MaxToSize)
+    return 0;
+  size_t AvailableSpace = MaxToSize - ToSize;
+  size_t MaxCopySize = std::min(AvailableSpace, FromSize);
+  size_t CopySize = Rand(MaxCopySize) + 1;
+  size_t FromBeg = Rand(FromSize - CopySize + 1);
+  assert(FromBeg + CopySize <= FromSize);
+  size_t ToInsertPos = Rand(ToSize + 1);
+  assert(ToInsertPos + CopySize <= MaxToSize);
+  size_t TailSize = ToSize - ToInsertPos;
+  if (To == From) {
+    MutateInPlaceHere.resize(MaxToSize);
+    memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize);
+    memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
+    memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize);
+  } else {
+    memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
+    memmove(To + ToInsertPos, From + FromBeg, CopySize);
+  }
+  return ToSize + CopySize;
+}
+
+size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size,
+                                           size_t MaxSize) {
+  if (Size > MaxSize || Size == 0)
+    return 0;
+  // If Size == MaxSize, `InsertPartOf(...)` will
+  // fail so there's no point using it in this case.
+  if (Size == MaxSize || Rand.RandBool())
+    return CopyPartOf(Data, Size, Data, Size);
+  else
+    return InsertPartOf(Data, Size, Data, Size, MaxSize);
+}
+
+size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size,
+                                                     size_t MaxSize) {
+  if (Size > MaxSize)
+    return 0;
+  size_t B = Rand(Size);
+  while (B < Size && !isdigit(Data[B]))
+    B++;
+  if (B == Size)
+    return 0;
+  size_t E = B;
+  while (E < Size && isdigit(Data[E]))
+    E++;
+  assert(B < E);
+  // now we have digits in [B, E).
+  // strtol and friends don't accept non-zero-teminated data, parse it manually.
+  uint64_t Val = Data[B] - '0';
+  for (size_t i = B + 1; i < E; i++)
+    Val = Val * 10 + Data[i] - '0';
+
+  // Mutate the integer value.
+  switch (Rand(5)) {
+  case 0:
+    Val++;
+    break;
+  case 1:
+    Val--;
+    break;
+  case 2:
+    Val /= 2;
+    break;
+  case 3:
+    Val *= 2;
+    break;
+  case 4:
+    Val = Rand(Val * Val);
+    break;
+  default:
+    assert(0);
+  }
+  // Just replace the bytes with the new ones, don't bother moving bytes.
+  for (size_t i = B; i < E; i++) {
+    size_t Idx = E + B - i - 1;
+    assert(Idx >= B && Idx < E);
+    Data[Idx] = (Val % 10) + '0';
+    Val /= 10;
+  }
+  return Size;
+}
+
+template <class T>
+size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) {
+  if (Size < sizeof(T))
+    return 0;
+  size_t Off = Rand(Size - sizeof(T) + 1);
+  assert(Off + sizeof(T) <= Size);
+  T Val;
+  if (Off < 64 && !Rand(4)) {
+    Val = static_cast<T>(Size);
+    if (Rand.RandBool())
+      Val = Bswap(Val);
+  } else {
+    memcpy(&Val, Data + Off, sizeof(Val));
+    T Add = static_cast<T>(Rand(21));
+    Add -= 10;
+    if (Rand.RandBool())
+      Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes.
+    else
+      Val = Val + Add;               // Add assuming current endiannes.
+    if (Add == 0 || Rand.RandBool()) // Maybe negate.
+      Val = -Val;
+  }
+  memcpy(Data + Off, &Val, sizeof(Val));
+  return Size;
+}
+
+size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data,
+                                                      size_t Size,
+                                                      size_t MaxSize) {
+  if (Size > MaxSize)
+    return 0;
+  switch (Rand(4)) {
+  case 3:
+    return ChangeBinaryInteger<uint64_t>(Data, Size, Rand);
+  case 2:
+    return ChangeBinaryInteger<uint32_t>(Data, Size, Rand);
+  case 1:
+    return ChangeBinaryInteger<uint16_t>(Data, Size, Rand);
+  case 0:
+    return ChangeBinaryInteger<uint8_t>(Data, Size, Rand);
+  default:
+    assert(0);
+  }
+  return 0;
+}
+
+size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size,
+                                            size_t MaxSize) {
+  if (Size > MaxSize)
+    return 0;
+  if (Size == 0)
+    return 0;
+  if (!CrossOverWith)
+    return 0;
+  const Unit &O = *CrossOverWith;
+  if (O.empty())
+    return 0;
+  size_t NewSize = 0;
+  switch (Rand(3)) {
+  case 0:
+    MutateInPlaceHere.resize(MaxSize);
+    NewSize = CrossOver(Data, Size, O.data(), O.size(),
+                        MutateInPlaceHere.data(), MaxSize);
+    memcpy(Data, MutateInPlaceHere.data(), NewSize);
+    break;
+  case 1:
+    NewSize = InsertPartOf(O.data(), O.size(), Data, Size, MaxSize);
+    if (!NewSize)
+      NewSize = CopyPartOf(O.data(), O.size(), Data, Size);
+    break;
+  case 2:
+    NewSize = CopyPartOf(O.data(), O.size(), Data, Size);
+    break;
+  default:
+    assert(0);
+  }
+  assert(NewSize > 0 && "CrossOver returned empty unit");
+  assert(NewSize <= MaxSize && "CrossOver returned overisized unit");
+  return NewSize;
+}
+
+void MutationDispatcher::StartMutationSequence() {
+  CurrentMutatorSequence.clear();
+  CurrentDictionaryEntrySequence.clear();
+}
+
+// Copy successful dictionary entries to PersistentAutoDictionary.
+void MutationDispatcher::RecordSuccessfulMutationSequence() {
+  for (auto *DE : CurrentDictionaryEntrySequence) {
+    // PersistentAutoDictionary.AddWithSuccessCountOne(DE);
+    DE->IncSuccessCount();
+    assert(DE->GetW().size());
+    // Linear search is fine here as this happens seldom.
+    if (!PersistentAutoDictionary.ContainsWord(DE->GetW()))
+      PersistentAutoDictionary.push_back(*DE);
+  }
+}
+
+const Dictionary &MutationDispatcher::RecommendDictionary() {
+  RecommendedDictionary.clear();
+  for (auto &DE : PersistentAutoDictionary)
+    if (!ManualDictionary.ContainsWord(DE.GetW()))
+      RecommendedDictionary.push_back(DE);
+  NextRecommendedDictionaryEntry = 0;
+  return RecommendedDictionary;
+}
+
+const char *MutationDispatcher::RecommendDictionaryEntry(size_t *UseCount) {
+  if (NextRecommendedDictionaryEntry >= RecommendedDictionary.size())
+    return nullptr;
+  auto &DE = RecommendedDictionary[NextRecommendedDictionaryEntry++];
+  assert(DE.GetW().size());
+  DictionaryEntryWord = ToASCII(DE.GetW());
+  if (UseCount)
+    *UseCount = DE.GetUseCount();
+  return DictionaryEntryWord.c_str();
+}
+
+const Sequence<MutationDispatcher::Mutator> &
+MutationDispatcher::MutationSequence() {
+  CurrentMutatorSequence.SetString([](Mutator M) { return M.Name; });
+  return CurrentMutatorSequence;
+}
+
+const Sequence<DictionaryEntry *> &
+MutationDispatcher::DictionaryEntrySequence() {
+  CurrentDictionaryEntrySequence.SetString([](DictionaryEntry *DE) {
+    return std::string("\"") + ToASCII(DE->GetW()) + std::string("\"");
+  });
+  return CurrentDictionaryEntrySequence;
+}
+
+size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
+  return MutateImpl(Data, Size, MaxSize, Mutators);
+}
+
+size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size,
+                                         size_t MaxSize) {
+  return MutateImpl(Data, Size, MaxSize, DefaultMutators);
+}
+
+// Mutates Data in place, returns new size.
+size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
+                                      size_t MaxSize,
+                                      Vector<Mutator> &Mutators) {
+  assert(MaxSize > 0);
+  // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
+  // in which case they will return 0.
+  // Try several times before returning un-mutated data.
+  for (int Iter = 0; Iter < 100; Iter++) {
+    auto M = Mutators[Rand(Mutators.size())];
+    size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
+    if (NewSize && NewSize <= MaxSize) {
+      if (Config.OnlyASCII)
+        ToASCII(Data, NewSize);
+      CurrentMutatorSequence.push_back(M);
+      return NewSize;
+    }
+  }
+  *Data = ' ';
+  return 1; // Fallback, should not happen frequently.
+}
+
+// Mask represents the set of Data bytes that are worth mutating.
+size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size,
+                                          size_t MaxSize,
+                                          const Vector<uint8_t> &Mask) {
+  size_t MaskedSize = std::min(Size, Mask.size());
+  // * Copy the worthy bytes into a temporary array T
+  // * Mutate T
+  // * Copy T back.
+  // This is totally unoptimized.
+  auto &T = MutateWithMaskTemp;
+  if (T.size() < Size)
+    T.resize(Size);
+  size_t OneBits = 0;
+  for (size_t I = 0; I < MaskedSize; I++)
+    if (Mask[I])
+      T[OneBits++] = Data[I];
+
+  if (!OneBits)
+    return 0;
+  assert(!T.empty());
+  size_t NewSize = Mutate(T.data(), OneBits, OneBits);
+  assert(NewSize <= OneBits);
+  (void)NewSize;
+  // Even if NewSize < OneBits we still use all OneBits bytes.
+  for (size_t I = 0, J = 0; I < MaskedSize; I++)
+    if (Mask[I])
+      Data[I] = T[J++];
+  return Size;
+}
+
+void MutationDispatcher::AddWordToManualDictionary(const Word &W) {
+  ManualDictionary.push_back({W, std::numeric_limits<size_t>::max()});
+}
+
+} // namespace mutagen

compiler-rt/lib/fuzzer/mutagen/MutagenSequence.h

+//===- MutagenSequence.h - Internal header for the mutagen ------*- C++ -* ===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// mutagen::Sequence
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_FUZZER_MUTAGEN_SEQUENCE_H
+#define LLVM_FUZZER_MUTAGEN_SEQUENCE_H
+
+#include "FuzzerDefs.h"
+#include <sstream>
+#include <string>
+
+namespace mutagen {
+namespace {
+
+using fuzzer::Vector;
+
+} // namespace
+
+// The Sequence type bundles together a list of items, a string representation,
+// and a position in that string suitable for truncating it when overly long,
+// e.g. after the tenth item.
+template <typename T> class Sequence {
+public:
+  constexpr static size_t kMaxBriefItems = 10;
+
+  void clear() {
+    Items.clear();
+    Size = 0;
+    Str.clear();
+    Brief = 0;
+  }
+
+  bool empty() const { return Size == 0; }
+
+  size_t size() const { return Size; }
+
+  void push_back(T t) { Items.push_back(t); }
+
+  typename Vector<T>::const_iterator begin() const { return Items.begin(); }
+  typename Vector<T>::iterator begin() { return Items.begin(); }
+
+  typename Vector<T>::const_iterator end() const { return Items.end(); }
+  typename Vector<T>::iterator end() { return Items.end(); }
+
+  std::string GetString(bool Verbose = true) const {
+    return Verbose ? Str : Str.substr(0, Brief);
+  }
+
+  // Constructs the string representation of the sequence, using a callback that
+  // converts items to strings.
+  template <typename ItemCallback>
+  // std::string ItemCallback(T Item);
+  void SetString(ItemCallback ConvertToASCII) {
+    // No change since last call.
+    if (Size == Items.size())
+      return;
+    Size = Items.size();
+    std::ostringstream OSS;
+    size_t i = 0;
+    for (; i < Size && i < kMaxBriefItems; i++)
+      OSS << ConvertToASCII(Items[i]) << "-";
+    Brief = static_cast<size_t>(OSS.tellp());
+    for (; i < Size; i++)
+      OSS << ConvertToASCII(Items[i]) << "-";
+    Str = OSS.str();
+  }
+
+private:
+  Vector<T> Items;
+  size_t Size = 0;
+  std::string Str;
+  size_t Brief = 0;
+};
+
+template <typename T>
+typename Vector<T>::const_iterator begin(const Sequence<T> &S) {
+  return S.begin();
+}
+
+template <typename T> typename Vector<T>::iterator begin(Sequence<T> &S) {
+  return S.begin();
+}
+
+template <typename T>
+typename Vector<T>::const_iterator end(const Sequence<T> &S) {
+  return S.end();
+}
+
+template <typename T> typename Vector<T>::iterator end(Sequence<T> &S) {
+  return S.end();
+}
+
+} // namespace mutagen
+
+#endif // LLVM_FUZZER_MUTAGEN_SEQUENCE_H

compiler-rt/lib/fuzzer/mutagen/MutagenUtil.h

+//===- MutagenUtil.h - Internal header for the mutagen Utils ----*- C++ -* ===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Util functions.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_FUZZER_MUTAGEN_UTIL_H
+#define LLVM_FUZZER_MUTAGEN_UTIL_H
+
+#include <cstddef>
+#include <cstdint>
+
+namespace mutagen {
+
+const void *SearchMemory(const void *haystack, size_t haystacklen,
+                         const void *needle, size_t needlelen);
+
+} // namespace mutagen
+
+#endif // LLVM_FUZZER_MUTAGEN_UTIL_H

compiler-rt/lib/fuzzer/mutagen/MutagenUtilPosix.cpp

+//===- MutagenUtilPosix.cpp - Misc utils for Posix. -----------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Misc utils implementation using Posix API.
+//===----------------------------------------------------------------------===//
+#include "FuzzerPlatform.h"
+#if (LIBFUZZER_POSIX || LIBFUZZER_FUCHSIA)
+#include <cstring>
+
+namespace mutagen {
+
+const void *SearchMemory(const void *Data, size_t DataLen, const void *Patt,
+                         size_t PattLen) {
+  return memmem(Data, DataLen, Patt, PattLen);
+}
+
+} // namespace mutagen
+
+#endif // (LIBFUZZER_POSIX || LIBFUZZER_FUCHSIA)

compiler-rt/lib/fuzzer/mutagen/MutagenUtilWindows.cpp

+//===- MutagenUtilWindows.cpp - Misc utils for Windows. -------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Misc utils implementation for Windows.
+//===----------------------------------------------------------------------===//
+#include "FuzzerPlatform.h"
+#if LIBFUZZER_WINDOWS
+#include <cstddef>
+#include <cstdio>
+#include <cstring>
+
+namespace mutagen {
+
+const void *SearchMemory(const void *Data, size_t DataLen, const void *Patt,
+                         size_t PattLen) {
+  // TODO: make this implementation more efficient.
+  const char *Cdata = (const char *)Data;
+  const char *Cpatt = (const char *)Patt;
+
+  if (!Data || !Patt || DataLen == 0 || PattLen == 0 || DataLen < PattLen)
+    return NULL;
+
+  if (PattLen == 1)
+    return memchr(Data, *Cpatt, DataLen);
+
+  const char *End = Cdata + DataLen - PattLen + 1;
+
+  for (const char *It = Cdata; It < End; ++It)
+    if (It[0] == Cpatt[0] && memcmp(It, Cpatt, PattLen) == 0)
+      return It;
+
+  return NULL;
+}
+
+} // namespace mutagen
+
+#endif // LIBFUZZER_WINDOWS

compiler-rt/lib/fuzzer/mutagen/build.sh

+#!/bin/sh
+LIBMUTAGEN_SRC_DIR=$(dirname $0)
+LIBFUZZER_SRC_DIR=$LIBMUTAGEN_SRC_DIR/..
+CXX="${CXX:-clang}"
+for f in $LIBMUTAGEN_SRC_DIR/*.cpp; do
+  $CXX -g -O2 -fno-omit-frame-pointer -std=c++11 $f -c -I$LIBFUZZER_SRC_DIR &
+done
+wait
+rm -f libMutagen.a
+ar ru libMutagen.a Mutagen*.o
+rm -f Mutagen*.o
+

compiler-rt/lib/fuzzer/tests/CMakeLists.txt

 endif()
 
 add_custom_target(FuzzerUnitTests)
 set_target_properties(FuzzerUnitTests PROPERTIES FOLDER "Compiler-RT Tests")
 
 add_custom_target(FuzzedDataProviderUnitTests)
 set_target_properties(FuzzedDataProviderUnitTests PROPERTIES FOLDER "Compiler-RT Tests")
 
+add_custom_target(MutagenUnitTests)
+set_target_properties(MutagenUnitTests PROPERTIES FOLDER "Compiler-RT Tests")
+
 set(LIBFUZZER_UNITTEST_LINK_FLAGS ${COMPILER_RT_UNITTEST_LINK_FLAGS})
 list(APPEND LIBFUZZER_UNITTEST_LINK_FLAGS --driver-mode=g++)
 
 if(WIN32)
   list(APPEND LIBFUZZER_UNITTEST_LINK_FLAGS -Wl,-defaultlib:libcmt,-defaultlib:oldnames)
 else()
   if (APPLE)
     list(APPEND LIBFUZZER_UNITTEST_CFLAGS -isysroot ${DARWIN_osx_SYSROOT})
if ("-fvisibility=hidden" IN_LIST LIBFUZZER_CFLAGS)
   list(APPEND LIBFUZZER_UNITTEST_CFLAGS "-fvisibility=hidden")
 endif()
 
 if(COMPILER_RT_DEFAULT_TARGET_ARCH IN_LIST FUZZER_SUPPORTED_ARCH)
   # libFuzzer unit tests are only run on the host machine.
   set(arch ${COMPILER_RT_DEFAULT_TARGET_ARCH})
 
   set(LIBFUZZER_TEST_RUNTIME RTFuzzerTest.${arch})
+  set(LIBMUTAGEN_TEST_RUNTIME RTMutagenTest.${arch})
   if(APPLE)
     set(LIBFUZZER_TEST_RUNTIME_OBJECTS
       $<TARGET_OBJECTS:RTfuzzer.osx>)
+    set(LIBMUTAGEN_TEST_RUNTIME_OBJECTS
+      $<TARGET_OBJECTS:RTmutagen.osx>)
   else()
     set(LIBFUZZER_TEST_RUNTIME_OBJECTS
       $<TARGET_OBJECTS:RTfuzzer.${arch}>)
+    set(LIBMUTAGEN_TEST_RUNTIME_OBJECTS
+      $<TARGET_OBJECTS:RTmutagen.${arch}>)
   endif()
   add_library(${LIBFUZZER_TEST_RUNTIME} STATIC
-    ${LIBFUZZER_TEST_RUNTIME_OBJECTS})
+    ${LIBFUZZER_TEST_RUNTIME_OBJECTS}
+    ${LIBMUTAGEN_TEST_RUNTIME_OBJECTS})
   set_target_properties(${LIBFUZZER_TEST_RUNTIME} PROPERTIES
     ARCHIVE_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
     FOLDER "Compiler-RT Runtime tests")
 
+  add_library(${LIBMUTAGEN_TEST_RUNTIME} STATIC
+    ${LIBMUTAGEN_TEST_RUNTIME_OBJECTS})
+  set_target_properties(${LIBMUTAGEN_TEST_RUNTIME} PROPERTIES
+    ARCHIVE_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}
+    FOLDER "Compiler-RT Runtime tests")
+
   if(CMAKE_SYSTEM_NAME STREQUAL "Linux" AND
      COMPILER_RT_LIBCXX_PATH AND
      COMPILER_RT_LIBCXXABI_PATH)
     file(GLOB libfuzzer_headers ../*.h)
     set(LIBFUZZER_TEST_RUNTIME_DEPS libcxx_fuzzer_${arch}-build ${libfuzzer_headers})
     set(LIBFUZZER_TEST_RUNTIME_CFLAGS -isystem ${LIBCXX_${arch}_PREFIX}/include/c++/v1)
     set(LIBFUZZER_TEST_RUNTIME_LINK_FLAGS ${LIBCXX_${arch}_PREFIX}/lib/libc++.a)
+    file(GLOB libmutagen_headers ../mutagen/*.h)
+    set(LIBMUTAGEN_TEST_RUNTIME_DEPS libcxx_fuzzer_${arch}-build ${libmutagen_headers})
   endif()
 
   set(FuzzerTestObjects)
   generate_compiler_rt_tests(FuzzerTestObjects
     FuzzerUnitTests "Fuzzer-${arch}-Test" ${arch}
     SOURCES FuzzerUnittest.cpp ${COMPILER_RT_GTEST_SOURCE}
     RUNTIME ${LIBFUZZER_TEST_RUNTIME}
-    DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} 
+    DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS}
     CFLAGS ${LIBFUZZER_UNITTEST_CFLAGS} ${LIBFUZZER_TEST_RUNTIME_CFLAGS}
     LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS})
   set_target_properties(FuzzerUnitTests PROPERTIES
     RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
 
   set(FuzzedDataProviderTestObjects)
   generate_compiler_rt_tests(FuzzedDataProviderTestObjects
     FuzzedDataProviderUnitTests "FuzzerUtils-${arch}-Test" ${arch}
     SOURCES FuzzedDataProviderUnittest.cpp ${COMPILER_RT_GTEST_SOURCE}
     DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} ${COMPILER_RT_SOURCE_DIR}/include/fuzzer/FuzzedDataProvider.h
     CFLAGS ${LIBFUZZER_UNITTEST_CFLAGS} ${LIBFUZZER_TEST_RUNTIME_CFLAGS}
     LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS})
   set_target_properties(FuzzedDataProviderUnitTests PROPERTIES
     RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
+
+  set(MutagenTestObjects)
+  generate_compiler_rt_tests(MutagenTestObjects
+    MutagenUnitTests "Mutagen-${arch}-Test" ${arch}
+    SOURCES MutagenUnittest.cpp ${COMPILER_RT_GTEST_SOURCE}
+    RUNTIME ${LIBFUZZER_TEST_RUNTIME}
+    DEPS gtest ${LIBFUZZER_TEST_RUNTIME_DEPS} ${LIBMUTAGEN_TEST_RUNTIME_DEPS}
+    CFLAGS ${LIBFUZZER_UNITTEST_CFLAGS} ${LIBFUZZER_TEST_RUNTIME_CFLAGS}
+    LINK_FLAGS ${LIBFUZZER_UNITTEST_LINK_FLAGS} ${LIBFUZZER_TEST_RUNTIME_LINK_FLAGS})
+  set_target_properties(MutagenUnitTests PROPERTIES
+    RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
 endif()

compiler-rt/lib/fuzzer/tests/FuzzerUnittest.cpp

 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 
 // Avoid ODR violations (LibFuzzer is built without ASan and this test is built
 // with ASan) involving C++ standard library types when using libcxx.
 #define _LIBCPP_HAS_NO_ASAN
 
 // Do not attempt to use LLVM ostream etc from gtest.
 #define GTEST_NO_LLVM_SUPPORT 1
 
 #include "FuzzerCorpus.h"
-#include "FuzzerDictionary.h"
 #include "FuzzerInternal.h"
 #include "FuzzerMerge.h"
 #include "FuzzerMutate.h"
 #include "FuzzerRandom.h"
 #include "FuzzerTracePC.h"
 #include "gtest/gtest.h"
 #include <memory>
 #include <set>
#if LIBFUZZER_WINDOWS
   EXPECT_EQ(Basename("foo\\bar"), "bar");
   EXPECT_EQ(Basename("foo\\bar/baz"), "baz");
   EXPECT_EQ(Basename("\\bar"), "bar");
   EXPECT_EQ(Basename("foo\\x"), "x");
   EXPECT_EQ(Basename("foo\\"), "");
 #endif
 }
 
-TEST(Fuzzer, CrossOver) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-  Unit A({0, 1, 2}), B({5, 6, 7});
-  Unit C;
-  Unit Expected[] = {
-       { 0 },
-       { 0, 1 },
-       { 0, 5 },
-       { 0, 1, 2 },
-       { 0, 1, 5 },
-       { 0, 5, 1 },
-       { 0, 5, 6 },
-       { 0, 1, 2, 5 },
-       { 0, 1, 5, 2 },
-       { 0, 1, 5, 6 },
-       { 0, 5, 1, 2 },
-       { 0, 5, 1, 6 },
-       { 0, 5, 6, 1 },
-       { 0, 5, 6, 7 },
-       { 0, 1, 2, 5, 6 },
-       { 0, 1, 5, 2, 6 },
-       { 0, 1, 5, 6, 2 },
-       { 0, 1, 5, 6, 7 },
-       { 0, 5, 1, 2, 6 },
-       { 0, 5, 1, 6, 2 },
-       { 0, 5, 1, 6, 7 },
-       { 0, 5, 6, 1, 2 },
-       { 0, 5, 6, 1, 7 },
-       { 0, 5, 6, 7, 1 },
-       { 0, 1, 2, 5, 6, 7 },
-       { 0, 1, 5, 2, 6, 7 },
-       { 0, 1, 5, 6, 2, 7 },
-       { 0, 1, 5, 6, 7, 2 },
-       { 0, 5, 1, 2, 6, 7 },
-       { 0, 5, 1, 6, 2, 7 },
-       { 0, 5, 1, 6, 7, 2 },
-       { 0, 5, 6, 1, 2, 7 },
-       { 0, 5, 6, 1, 7, 2 },
-       { 0, 5, 6, 7, 1, 2 }
-  };
-  for (size_t Len = 1; Len < 8; Len++) {
-    Set<Unit> FoundUnits, ExpectedUnitsWitThisLength;
-    for (int Iter = 0; Iter < 3000; Iter++) {
-      C.resize(Len);
-      size_t NewSize = MD->CrossOver(A.data(), A.size(), B.data(), B.size(),
-                                     C.data(), C.size());
-      C.resize(NewSize);
-      FoundUnits.insert(C);
-    }
-    for (const Unit &U : Expected)
-      if (U.size() <= Len)
-        ExpectedUnitsWitThisLength.insert(U);
-    EXPECT_EQ(ExpectedUnitsWitThisLength, FoundUnits);
-  }
-}
-
 TEST(Fuzzer, Hash) {
   uint8_t A[] = {'a', 'b', 'c'};
   fuzzer::Unit U(A, A + sizeof(A));
   EXPECT_EQ("a9993e364706816aba3e25717850c26c9cd0d89d", fuzzer::Hash(U));
   U.push_back('d');
   EXPECT_EQ("81fe8bfe87576c3ecb22426f8e57847382917acf", fuzzer::Hash(U));
 }
 
-typedef size_t (MutationDispatcher::*Mutator)(uint8_t *Data, size_t Size,
-                                              size_t MaxSize);
-
-void TestEraseBytes(Mutator M, int NumIter) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  uint8_t REM0[8] = {0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t REM1[8] = {0x00, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t REM2[8] = {0x00, 0x11, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t REM3[8] = {0x00, 0x11, 0x22, 0x44, 0x55, 0x66, 0x77};
-  uint8_t REM4[8] = {0x00, 0x11, 0x22, 0x33, 0x55, 0x66, 0x77};
-  uint8_t REM5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x66, 0x77};
-  uint8_t REM6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x77};
-  uint8_t REM7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
-
-  uint8_t REM8[6] = {0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t REM9[6] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55};
-  uint8_t REM10[6] = {0x00, 0x11, 0x22, 0x55, 0x66, 0x77};
-
-  uint8_t REM11[5] = {0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t REM12[5] = {0x00, 0x11, 0x22, 0x33, 0x44};
-  uint8_t REM13[5] = {0x00, 0x44, 0x55, 0x66, 0x77};
-
-
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-  int FoundMask = 0;
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-    size_t NewSize = (*MD.*M)(T, sizeof(T), sizeof(T));
-    if (NewSize == 7 && !memcmp(REM0, T, 7)) FoundMask |= 1 << 0;
-    if (NewSize == 7 && !memcmp(REM1, T, 7)) FoundMask |= 1 << 1;
-    if (NewSize == 7 && !memcmp(REM2, T, 7)) FoundMask |= 1 << 2;
-    if (NewSize == 7 && !memcmp(REM3, T, 7)) FoundMask |= 1 << 3;
-    if (NewSize == 7 && !memcmp(REM4, T, 7)) FoundMask |= 1 << 4;
-    if (NewSize == 7 && !memcmp(REM5, T, 7)) FoundMask |= 1 << 5;
-    if (NewSize == 7 && !memcmp(REM6, T, 7)) FoundMask |= 1 << 6;
-    if (NewSize == 7 && !memcmp(REM7, T, 7)) FoundMask |= 1 << 7;
-
-    if (NewSize == 6 && !memcmp(REM8, T, 6)) FoundMask |= 1 << 8;
-    if (NewSize == 6 && !memcmp(REM9, T, 6)) FoundMask |= 1 << 9;
-    if (NewSize == 6 && !memcmp(REM10, T, 6)) FoundMask |= 1 << 10;
-
-    if (NewSize == 5 && !memcmp(REM11, T, 5)) FoundMask |= 1 << 11;
-    if (NewSize == 5 && !memcmp(REM12, T, 5)) FoundMask |= 1 << 12;
-    if (NewSize == 5 && !memcmp(REM13, T, 5)) FoundMask |= 1 << 13;
-  }
-  EXPECT_EQ(FoundMask, (1 << 14) - 1);
-}
-
-TEST(FuzzerMutate, EraseBytes1) {
-  TestEraseBytes(&MutationDispatcher::Mutate_EraseBytes, 200);
-}
-TEST(FuzzerMutate, EraseBytes2) {
-  TestEraseBytes(&MutationDispatcher::Mutate, 2000);
-}
-
-void TestInsertByte(Mutator M, int NumIter) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-  int FoundMask = 0;
-  uint8_t INS0[8] = {0xF1, 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
-  uint8_t INS1[8] = {0x00, 0xF2, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
-  uint8_t INS2[8] = {0x00, 0x11, 0xF3, 0x22, 0x33, 0x44, 0x55, 0x66};
-  uint8_t INS3[8] = {0x00, 0x11, 0x22, 0xF4, 0x33, 0x44, 0x55, 0x66};
-  uint8_t INS4[8] = {0x00, 0x11, 0x22, 0x33, 0xF5, 0x44, 0x55, 0x66};
-  uint8_t INS5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0xF6, 0x55, 0x66};
-  uint8_t INS6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0xF7, 0x66};
-  uint8_t INS7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF8};
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
-    size_t NewSize = (*MD.*M)(T, 7, 8);
-    if (NewSize == 8 && !memcmp(INS0, T, 8)) FoundMask |= 1 << 0;
-    if (NewSize == 8 && !memcmp(INS1, T, 8)) FoundMask |= 1 << 1;
-    if (NewSize == 8 && !memcmp(INS2, T, 8)) FoundMask |= 1 << 2;
-    if (NewSize == 8 && !memcmp(INS3, T, 8)) FoundMask |= 1 << 3;
-    if (NewSize == 8 && !memcmp(INS4, T, 8)) FoundMask |= 1 << 4;
-    if (NewSize == 8 && !memcmp(INS5, T, 8)) FoundMask |= 1 << 5;
-    if (NewSize == 8 && !memcmp(INS6, T, 8)) FoundMask |= 1 << 6;
-    if (NewSize == 8 && !memcmp(INS7, T, 8)) FoundMask |= 1 << 7;
-  }
-  EXPECT_EQ(FoundMask, 255);
-}
-
-TEST(FuzzerMutate, InsertByte1) {
-  TestInsertByte(&MutationDispatcher::Mutate_InsertByte, 1 << 15);
-}
-TEST(FuzzerMutate, InsertByte2) {
-  TestInsertByte(&MutationDispatcher::Mutate, 1 << 17);
-}
-
-void TestInsertRepeatedBytes(Mutator M, int NumIter) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-  int FoundMask = 0;
-  uint8_t INS0[7] = {0x00, 0x11, 0x22, 0x33, 'a', 'a', 'a'};
-  uint8_t INS1[7] = {0x00, 0x11, 0x22, 'a', 'a', 'a', 0x33};
-  uint8_t INS2[7] = {0x00, 0x11, 'a', 'a', 'a', 0x22, 0x33};
-  uint8_t INS3[7] = {0x00, 'a', 'a', 'a', 0x11, 0x22, 0x33};
-  uint8_t INS4[7] = {'a', 'a', 'a', 0x00, 0x11, 0x22, 0x33};
-
-  uint8_t INS5[8] = {0x00, 0x11, 0x22, 0x33, 'b', 'b', 'b', 'b'};
-  uint8_t INS6[8] = {0x00, 0x11, 0x22, 'b', 'b', 'b', 'b', 0x33};
-  uint8_t INS7[8] = {0x00, 0x11, 'b', 'b', 'b', 'b', 0x22, 0x33};
-  uint8_t INS8[8] = {0x00, 'b', 'b', 'b', 'b', 0x11, 0x22, 0x33};
-  uint8_t INS9[8] = {'b', 'b', 'b', 'b', 0x00, 0x11, 0x22, 0x33};
-
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33};
-    size_t NewSize = (*MD.*M)(T, 4, 8);
-    if (NewSize == 7 && !memcmp(INS0, T, 7)) FoundMask |= 1 << 0;
-    if (NewSize == 7 && !memcmp(INS1, T, 7)) FoundMask |= 1 << 1;
-    if (NewSize == 7 && !memcmp(INS2, T, 7)) FoundMask |= 1 << 2;
-    if (NewSize == 7 && !memcmp(INS3, T, 7)) FoundMask |= 1 << 3;
-    if (NewSize == 7 && !memcmp(INS4, T, 7)) FoundMask |= 1 << 4;
-
-    if (NewSize == 8 && !memcmp(INS5, T, 8)) FoundMask |= 1 << 5;
-    if (NewSize == 8 && !memcmp(INS6, T, 8)) FoundMask |= 1 << 6;
-    if (NewSize == 8 && !memcmp(INS7, T, 8)) FoundMask |= 1 << 7;
-    if (NewSize == 8 && !memcmp(INS8, T, 8)) FoundMask |= 1 << 8;
-    if (NewSize == 8 && !memcmp(INS9, T, 8)) FoundMask |= 1 << 9;
-
-  }
-  EXPECT_EQ(FoundMask, (1 << 10) - 1);
-}
-
-TEST(FuzzerMutate, InsertRepeatedBytes1) {
-  TestInsertRepeatedBytes(&MutationDispatcher::Mutate_InsertRepeatedBytes, 10000);
-}
-TEST(FuzzerMutate, InsertRepeatedBytes2) {
-  TestInsertRepeatedBytes(&MutationDispatcher::Mutate, 300000);
-}
-
-void TestChangeByte(Mutator M, int NumIter) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-  int FoundMask = 0;
-  uint8_t CH0[8] = {0xF0, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH1[8] = {0x00, 0xF1, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH2[8] = {0x00, 0x11, 0xF2, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH3[8] = {0x00, 0x11, 0x22, 0xF3, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0xF4, 0x55, 0x66, 0x77};
-  uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0xF5, 0x66, 0x77};
-  uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0xF5, 0x77};
-  uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF7};
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[9] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-    size_t NewSize = (*MD.*M)(T, 8, 9);
-    if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0;
-    if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1;
-    if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2;
-    if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3;
-    if (NewSize == 8 && !memcmp(CH4, T, 8)) FoundMask |= 1 << 4;
-    if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5;
-    if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6;
-    if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7;
-  }
-  EXPECT_EQ(FoundMask, 255);
-}
-
-TEST(FuzzerMutate, ChangeByte1) {
-  TestChangeByte(&MutationDispatcher::Mutate_ChangeByte, 1 << 15);
-}
-TEST(FuzzerMutate, ChangeByte2) {
-  TestChangeByte(&MutationDispatcher::Mutate, 1 << 17);
-}
-
-void TestChangeBit(Mutator M, int NumIter) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-  int FoundMask = 0;
-  uint8_t CH0[8] = {0x01, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH1[8] = {0x00, 0x13, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH2[8] = {0x00, 0x11, 0x02, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH3[8] = {0x00, 0x11, 0x22, 0x37, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0x54, 0x55, 0x66, 0x77};
-  uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x54, 0x66, 0x77};
-  uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x76, 0x77};
-  uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF7};
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[9] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-    size_t NewSize = (*MD.*M)(T, 8, 9);
-    if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0;
-    if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1;
-    if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2;
-    if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3;
-    if (NewSize == 8 && !memcmp(CH4, T, 8)) FoundMask |= 1 << 4;
-    if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5;
-    if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6;
-    if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7;
-  }
-  EXPECT_EQ(FoundMask, 255);
-}
-
-TEST(FuzzerMutate, ChangeBit1) {
-  TestChangeBit(&MutationDispatcher::Mutate_ChangeBit, 1 << 16);
-}
-TEST(FuzzerMutate, ChangeBit2) {
-  TestChangeBit(&MutationDispatcher::Mutate, 1 << 18);
-}
-
-void TestShuffleBytes(Mutator M, int NumIter) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-  int FoundMask = 0;
-  uint8_t CH0[7] = {0x00, 0x22, 0x11, 0x33, 0x44, 0x55, 0x66};
-  uint8_t CH1[7] = {0x11, 0x00, 0x33, 0x22, 0x44, 0x55, 0x66};
-  uint8_t CH2[7] = {0x00, 0x33, 0x11, 0x22, 0x44, 0x55, 0x66};
-  uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x44, 0x55, 0x66, 0x33};
-  uint8_t CH4[7] = {0x00, 0x11, 0x22, 0x33, 0x55, 0x44, 0x66};
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
-    size_t NewSize = (*MD.*M)(T, 7, 7);
-    if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0;
-    if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1;
-    if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2;
-    if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3;
-    if (NewSize == 7 && !memcmp(CH4, T, 7)) FoundMask |= 1 << 4;
-  }
-  EXPECT_EQ(FoundMask, 31);
-}
-
-TEST(FuzzerMutate, ShuffleBytes1) {
-  TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 17);
-}
-TEST(FuzzerMutate, ShuffleBytes2) {
-  TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 20);
-}
-
-void TestCopyPart(Mutator M, int NumIter) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-  int FoundMask = 0;
-  uint8_t CH0[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11};
-  uint8_t CH1[7] = {0x55, 0x66, 0x22, 0x33, 0x44, 0x55, 0x66};
-  uint8_t CH2[7] = {0x00, 0x55, 0x66, 0x33, 0x44, 0x55, 0x66};
-  uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x66};
-  uint8_t CH4[7] = {0x00, 0x11, 0x11, 0x22, 0x33, 0x55, 0x66};
-
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
-    size_t NewSize = (*MD.*M)(T, 7, 7);
-    if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0;
-    if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1;
-    if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2;
-    if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3;
-    if (NewSize == 7 && !memcmp(CH4, T, 7)) FoundMask |= 1 << 4;
-  }
-
-  uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22};
-  uint8_t CH6[8] = {0x22, 0x33, 0x44, 0x00, 0x11, 0x22, 0x33, 0x44};
-  uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x33, 0x44};
-  uint8_t CH8[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x22, 0x33, 0x44};
-  uint8_t CH9[8] = {0x00, 0x11, 0x22, 0x22, 0x33, 0x44, 0x33, 0x44};
-
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-    size_t NewSize = (*MD.*M)(T, 5, 8);
-    if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5;
-    if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6;
-    if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7;
-    if (NewSize == 8 && !memcmp(CH8, T, 8)) FoundMask |= 1 << 8;
-    if (NewSize == 8 && !memcmp(CH9, T, 8)) FoundMask |= 1 << 9;
-  }
-
-  EXPECT_EQ(FoundMask, 1023);
-}
-
-TEST(FuzzerMutate, CopyPart1) {
-  TestCopyPart(&MutationDispatcher::Mutate_CopyPart, 1 << 10);
-}
-TEST(FuzzerMutate, CopyPart2) {
-  TestCopyPart(&MutationDispatcher::Mutate, 1 << 13);
-}
-TEST(FuzzerMutate, CopyPartNoInsertAtMaxSize) {
-  // This (non exhaustively) tests if `Mutate_CopyPart` tries to perform an
-  // insert on an input of size `MaxSize`.  Performing an insert in this case
-  // will lead to the mutation failing.
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-  uint8_t Data[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22};
-  size_t MaxSize = sizeof(Data);
-  for (int count = 0; count < (1 << 18); ++count) {
-    size_t NewSize = MD->Mutate_CopyPart(Data, MaxSize, MaxSize);
-    ASSERT_EQ(NewSize, MaxSize);
-  }
-}
-
-void TestAddWordFromDictionary(Mutator M, int NumIter) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-  uint8_t Word1[4] = {0xAA, 0xBB, 0xCC, 0xDD};
-  uint8_t Word2[3] = {0xFF, 0xEE, 0xEF};
-  MD->AddWordToManualDictionary(Word(Word1, sizeof(Word1)));
-  MD->AddWordToManualDictionary(Word(Word2, sizeof(Word2)));
-  int FoundMask = 0;
-  uint8_t CH0[7] = {0x00, 0x11, 0x22, 0xAA, 0xBB, 0xCC, 0xDD};
-  uint8_t CH1[7] = {0x00, 0x11, 0xAA, 0xBB, 0xCC, 0xDD, 0x22};
-  uint8_t CH2[7] = {0x00, 0xAA, 0xBB, 0xCC, 0xDD, 0x11, 0x22};
-  uint8_t CH3[7] = {0xAA, 0xBB, 0xCC, 0xDD, 0x00, 0x11, 0x22};
-  uint8_t CH4[6] = {0x00, 0x11, 0x22, 0xFF, 0xEE, 0xEF};
-  uint8_t CH5[6] = {0x00, 0x11, 0xFF, 0xEE, 0xEF, 0x22};
-  uint8_t CH6[6] = {0x00, 0xFF, 0xEE, 0xEF, 0x11, 0x22};
-  uint8_t CH7[6] = {0xFF, 0xEE, 0xEF, 0x00, 0x11, 0x22};
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[7] = {0x00, 0x11, 0x22};
-    size_t NewSize = (*MD.*M)(T, 3, 7);
-    if (NewSize == 7 && !memcmp(CH0, T, 7)) FoundMask |= 1 << 0;
-    if (NewSize == 7 && !memcmp(CH1, T, 7)) FoundMask |= 1 << 1;
-    if (NewSize == 7 && !memcmp(CH2, T, 7)) FoundMask |= 1 << 2;
-    if (NewSize == 7 && !memcmp(CH3, T, 7)) FoundMask |= 1 << 3;
-    if (NewSize == 6 && !memcmp(CH4, T, 6)) FoundMask |= 1 << 4;
-    if (NewSize == 6 && !memcmp(CH5, T, 6)) FoundMask |= 1 << 5;
-    if (NewSize == 6 && !memcmp(CH6, T, 6)) FoundMask |= 1 << 6;
-    if (NewSize == 6 && !memcmp(CH7, T, 6)) FoundMask |= 1 << 7;
-  }
-  EXPECT_EQ(FoundMask, 255);
-}
-
-TEST(FuzzerMutate, AddWordFromDictionary1) {
-  TestAddWordFromDictionary(
-      &MutationDispatcher::Mutate_AddWordFromManualDictionary, 1 << 15);
-}
-
-TEST(FuzzerMutate, AddWordFromDictionary2) {
-  TestAddWordFromDictionary(&MutationDispatcher::Mutate, 1 << 15);
-}
-
-void TestChangeASCIIInteger(Mutator M, int NumIter) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-
-  uint8_t CH0[8] = {'1', '2', '3', '4', '5', '6', '7', '7'};
-  uint8_t CH1[8] = {'1', '2', '3', '4', '5', '6', '7', '9'};
-  uint8_t CH2[8] = {'2', '4', '6', '9', '1', '3', '5', '6'};
-  uint8_t CH3[8] = {'0', '6', '1', '7', '2', '8', '3', '9'};
-  int FoundMask = 0;
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[8] = {'1', '2', '3', '4', '5', '6', '7', '8'};
-    size_t NewSize = (*MD.*M)(T, 8, 8);
-    /**/ if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0;
-    else if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1;
-    else if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2;
-    else if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3;
-    else if (NewSize == 8)                       FoundMask |= 1 << 4;
-  }
-  EXPECT_EQ(FoundMask, 31);
-}
-
-TEST(FuzzerMutate, ChangeASCIIInteger1) {
-  TestChangeASCIIInteger(&MutationDispatcher::Mutate_ChangeASCIIInteger,
-                         1 << 15);
-}
-
-TEST(FuzzerMutate, ChangeASCIIInteger2) {
-  TestChangeASCIIInteger(&MutationDispatcher::Mutate, 1 << 15);
-}
-
-void TestChangeBinaryInteger(Mutator M, int NumIter) {
-  std::unique_ptr<ExternalFunctions> t(new ExternalFunctions());
-  fuzzer::EF = t.get();
-  Random Rand(0);
-  std::unique_ptr<MutationDispatcher> MD(new MutationDispatcher(Rand, {}));
-
-  uint8_t CH0[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x79};
-  uint8_t CH1[8] = {0x00, 0x11, 0x22, 0x31, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH2[8] = {0xff, 0x10, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH3[8] = {0x00, 0x11, 0x2a, 0x33, 0x44, 0x55, 0x66, 0x77};
-  uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x4f, 0x66, 0x77};
-  uint8_t CH5[8] = {0xff, 0xee, 0xdd, 0xcc, 0xbb, 0xaa, 0x99, 0x88};
-  uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x00, 0x00, 0x00, 0x08, 0x77}; // Size
-  uint8_t CH7[8] = {0x00, 0x08, 0x00, 0x33, 0x44, 0x55, 0x66, 0x77}; // Sw(Size)
-
-  int FoundMask = 0;
-  for (int i = 0; i < NumIter; i++) {
-    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
-    size_t NewSize = (*MD.*M)(T, 8, 8);
-    /**/ if (NewSize == 8 && !memcmp(CH0, T, 8)) FoundMask |= 1 << 0;
-    else if (NewSize == 8 && !memcmp(CH1, T, 8)) FoundMask |= 1 << 1;
-    else if (NewSize == 8 && !memcmp(CH2, T, 8)) FoundMask |= 1 << 2;
-    else if (NewSize == 8 && !memcmp(CH3, T, 8)) FoundMask |= 1 << 3;
-    else if (NewSize == 8 && !memcmp(CH4, T, 8)) FoundMask |= 1 << 4;
-    else if (NewSize == 8 && !memcmp(CH5, T, 8)) FoundMask |= 1 << 5;
-    else if (NewSize == 8 && !memcmp(CH6, T, 8)) FoundMask |= 1 << 6;
-    else if (NewSize == 8 && !memcmp(CH7, T, 8)) FoundMask |= 1 << 7;
-  }
-  EXPECT_EQ(FoundMask, 255);
-}
-
-TEST(FuzzerMutate, ChangeBinaryInteger1) {
-  TestChangeBinaryInteger(&MutationDispatcher::Mutate_ChangeBinaryInteger,
-                         1 << 12);
-}
-
-TEST(FuzzerMutate, ChangeBinaryInteger2) {
-  TestChangeBinaryInteger(&MutationDispatcher::Mutate, 1 << 15);
-}
-
-
 TEST(FuzzerDictionary, ParseOneDictionaryEntry) {
   Unit U;
   EXPECT_FALSE(ParseOneDictionaryEntry("", &U));
   EXPECT_FALSE(ParseOneDictionaryEntry(" ", &U));
   EXPECT_FALSE(ParseOneDictionaryEntry("\t  ", &U));
   EXPECT_FALSE(ParseOneDictionaryEntry("  \" ", &U));
   EXPECT_FALSE(ParseOneDictionaryEntry("  zz\" ", &U));
   EXPECT_FALSE(ParseOneDictionaryEntry("  \"zz ", &U));

compiler-rt/lib/fuzzer/tests/MutagenUnittest.cpp

+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+
+#include "mutagen/Mutagen.h"
+#include "mutagen/MutagenDispatcher.h"
+#include "mutagen/MutagenSequence.h"
+#include "mutagen/MutagenUtil.h"
+#include "gtest/gtest.h"
+#include <chrono>
+
+// Avoid using fuzzer::ExternalFunctions, since it may not be linked against
+// the test binary.
+#if defined(__has_feature)
+#if __has_feature(memory_sanitizer)
+#define HAS_MSAN 1
+#include <sanitizer/msan_interface.h>
+#else
+#define HAS_MSAN 0
+#endif // __has_feature(memory_sanitizer)
+#else
+#define HAS_MSAN 0
+#endif // defined(__has_feature)
+
+namespace mutagen {
+namespace {
+
+using fuzzer::Set;
+
+std::unique_ptr<MutationDispatcher> CreateMutationDispatcher() {
+  LLVMMutagenConfiguration Config;
+  memset(&Config, 0, sizeof(Config));
+  return std::unique_ptr<MutationDispatcher>(new MutationDispatcher(&Config));
+}
+
+typedef size_t (MutationDispatcher::*Mutator)(uint8_t *Data, size_t Size,
+                                              size_t MaxSize);
+
+TEST(MutationDispatcher, CrossOver) {
+  auto MD = CreateMutationDispatcher();
+  Unit A({0, 1, 2}), B({5, 6, 7});
+  Unit C;
+  Unit Expected[] = {{0},
+                     {0, 1},
+                     {0, 5},
+                     {0, 1, 2},
+                     {0, 1, 5},
+                     {0, 5, 1},
+                     {0, 5, 6},
+                     {0, 1, 2, 5},
+                     {0, 1, 5, 2},
+                     {0, 1, 5, 6},
+                     {0, 5, 1, 2},
+                     {0, 5, 1, 6},
+                     {0, 5, 6, 1},
+                     {0, 5, 6, 7},
+                     {0, 1, 2, 5, 6},
+                     {0, 1, 5, 2, 6},
+                     {0, 1, 5, 6, 2},
+                     {0, 1, 5, 6, 7},
+                     {0, 5, 1, 2, 6},
+                     {0, 5, 1, 6, 2},
+                     {0, 5, 1, 6, 7},
+                     {0, 5, 6, 1, 2},
+                     {0, 5, 6, 1, 7},
+                     {0, 5, 6, 7, 1},
+                     {0, 1, 2, 5, 6, 7},
+                     {0, 1, 5, 2, 6, 7},
+                     {0, 1, 5, 6, 2, 7},
+                     {0, 1, 5, 6, 7, 2},
+                     {0, 5, 1, 2, 6, 7},
+                     {0, 5, 1, 6, 2, 7},
+                     {0, 5, 1, 6, 7, 2},
+                     {0, 5, 6, 1, 2, 7},
+                     {0, 5, 6, 1, 7, 2},
+                     {0, 5, 6, 7, 1, 2}};
+  for (size_t Len = 1; Len < 8; Len++) {
+    Set<Unit> FoundUnits, ExpectedUnitsWitThisLength;
+    for (int Iter = 0; Iter < 3000; Iter++) {
+      C.resize(Len);
+      size_t NewSize = MD->CrossOver(A.data(), A.size(), B.data(), B.size(),
+                                     C.data(), C.size());
+      C.resize(NewSize);
+      FoundUnits.insert(C);
+    }
+    for (const Unit &U : Expected)
+      if (U.size() <= Len)
+        ExpectedUnitsWitThisLength.insert(U);
+    EXPECT_EQ(ExpectedUnitsWitThisLength, FoundUnits);
+  }
+}
+
+void TestEraseBytes(Mutator M, int NumIter) {
+  uint8_t REM0[8] = {0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t REM1[8] = {0x00, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t REM2[8] = {0x00, 0x11, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t REM3[8] = {0x00, 0x11, 0x22, 0x44, 0x55, 0x66, 0x77};
+  uint8_t REM4[8] = {0x00, 0x11, 0x22, 0x33, 0x55, 0x66, 0x77};
+  uint8_t REM5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x66, 0x77};
+  uint8_t REM6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x77};
+  uint8_t REM7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
+
+  uint8_t REM8[6] = {0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t REM9[6] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55};
+  uint8_t REM10[6] = {0x00, 0x11, 0x22, 0x55, 0x66, 0x77};
+
+  uint8_t REM11[5] = {0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t REM12[5] = {0x00, 0x11, 0x22, 0x33, 0x44};
+  uint8_t REM13[5] = {0x00, 0x44, 0x55, 0x66, 0x77};
+
+  auto MD = CreateMutationDispatcher();
+  int FoundMask = 0;
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+    size_t NewSize = (*MD.*M)(T, sizeof(T), sizeof(T));
+    if (NewSize == 7 && !memcmp(REM0, T, 7))
+      FoundMask |= 1 << 0;
+    if (NewSize == 7 && !memcmp(REM1, T, 7))
+      FoundMask |= 1 << 1;
+    if (NewSize == 7 && !memcmp(REM2, T, 7))
+      FoundMask |= 1 << 2;
+    if (NewSize == 7 && !memcmp(REM3, T, 7))
+      FoundMask |= 1 << 3;
+    if (NewSize == 7 && !memcmp(REM4, T, 7))
+      FoundMask |= 1 << 4;
+    if (NewSize == 7 && !memcmp(REM5, T, 7))
+      FoundMask |= 1 << 5;
+    if (NewSize == 7 && !memcmp(REM6, T, 7))
+      FoundMask |= 1 << 6;
+    if (NewSize == 7 && !memcmp(REM7, T, 7))
+      FoundMask |= 1 << 7;
+
+    if (NewSize == 6 && !memcmp(REM8, T, 6))
+      FoundMask |= 1 << 8;
+    if (NewSize == 6 && !memcmp(REM9, T, 6))
+      FoundMask |= 1 << 9;
+    if (NewSize == 6 && !memcmp(REM10, T, 6))
+      FoundMask |= 1 << 10;
+
+    if (NewSize == 5 && !memcmp(REM11, T, 5))
+      FoundMask |= 1 << 11;
+    if (NewSize == 5 && !memcmp(REM12, T, 5))
+      FoundMask |= 1 << 12;
+    if (NewSize == 5 && !memcmp(REM13, T, 5))
+      FoundMask |= 1 << 13;
+  }
+  EXPECT_EQ(FoundMask, (1 << 14) - 1);
+}
+
+TEST(MutationDispatcher, EraseBytes1) {
+  TestEraseBytes(&MutationDispatcher::Mutate_EraseBytes, 200);
+}
+TEST(MutationDispatcher, EraseBytes2) {
+  TestEraseBytes(&MutationDispatcher::Mutate, 2000);
+}
+
+void TestInsertByte(Mutator M, int NumIter) {
+  auto MD = CreateMutationDispatcher();
+  int FoundMask = 0;
+  uint8_t INS0[8] = {0xF1, 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
+  uint8_t INS1[8] = {0x00, 0xF2, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
+  uint8_t INS2[8] = {0x00, 0x11, 0xF3, 0x22, 0x33, 0x44, 0x55, 0x66};
+  uint8_t INS3[8] = {0x00, 0x11, 0x22, 0xF4, 0x33, 0x44, 0x55, 0x66};
+  uint8_t INS4[8] = {0x00, 0x11, 0x22, 0x33, 0xF5, 0x44, 0x55, 0x66};
+  uint8_t INS5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0xF6, 0x55, 0x66};
+  uint8_t INS6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0xF7, 0x66};
+  uint8_t INS7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF8};
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
+    size_t NewSize = (*MD.*M)(T, 7, 8);
+    if (NewSize == 8 && !memcmp(INS0, T, 8))
+      FoundMask |= 1 << 0;
+    if (NewSize == 8 && !memcmp(INS1, T, 8))
+      FoundMask |= 1 << 1;
+    if (NewSize == 8 && !memcmp(INS2, T, 8))
+      FoundMask |= 1 << 2;
+    if (NewSize == 8 && !memcmp(INS3, T, 8))
+      FoundMask |= 1 << 3;
+    if (NewSize == 8 && !memcmp(INS4, T, 8))
+      FoundMask |= 1 << 4;
+    if (NewSize == 8 && !memcmp(INS5, T, 8))
+      FoundMask |= 1 << 5;
+    if (NewSize == 8 && !memcmp(INS6, T, 8))
+      FoundMask |= 1 << 6;
+    if (NewSize == 8 && !memcmp(INS7, T, 8))
+      FoundMask |= 1 << 7;
+  }
+  EXPECT_EQ(FoundMask, 255);
+}
+
+TEST(MutationDispatcher, InsertByte1) {
+  TestInsertByte(&MutationDispatcher::Mutate_InsertByte, 1 << 15);
+}
+TEST(MutationDispatcher, InsertByte2) {
+  TestInsertByte(&MutationDispatcher::Mutate, 1 << 17);
+}
+
+void TestInsertRepeatedBytes(Mutator M, int NumIter) {
+  auto MD = CreateMutationDispatcher();
+  int FoundMask = 0;
+  uint8_t INS0[7] = {0x00, 0x11, 0x22, 0x33, 'a', 'a', 'a'};
+  uint8_t INS1[7] = {0x00, 0x11, 0x22, 'a', 'a', 'a', 0x33};
+  uint8_t INS2[7] = {0x00, 0x11, 'a', 'a', 'a', 0x22, 0x33};
+  uint8_t INS3[7] = {0x00, 'a', 'a', 'a', 0x11, 0x22, 0x33};
+  uint8_t INS4[7] = {'a', 'a', 'a', 0x00, 0x11, 0x22, 0x33};
+
+  uint8_t INS5[8] = {0x00, 0x11, 0x22, 0x33, 'b', 'b', 'b', 'b'};
+  uint8_t INS6[8] = {0x00, 0x11, 0x22, 'b', 'b', 'b', 'b', 0x33};
+  uint8_t INS7[8] = {0x00, 0x11, 'b', 'b', 'b', 'b', 0x22, 0x33};
+  uint8_t INS8[8] = {0x00, 'b', 'b', 'b', 'b', 0x11, 0x22, 0x33};
+  uint8_t INS9[8] = {'b', 'b', 'b', 'b', 0x00, 0x11, 0x22, 0x33};
+
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33};
+    size_t NewSize = (*MD.*M)(T, 4, 8);
+    if (NewSize == 7 && !memcmp(INS0, T, 7))
+      FoundMask |= 1 << 0;
+    if (NewSize == 7 && !memcmp(INS1, T, 7))
+      FoundMask |= 1 << 1;
+    if (NewSize == 7 && !memcmp(INS2, T, 7))
+      FoundMask |= 1 << 2;
+    if (NewSize == 7 && !memcmp(INS3, T, 7))
+      FoundMask |= 1 << 3;
+    if (NewSize == 7 && !memcmp(INS4, T, 7))
+      FoundMask |= 1 << 4;
+
+    if (NewSize == 8 && !memcmp(INS5, T, 8))
+      FoundMask |= 1 << 5;
+    if (NewSize == 8 && !memcmp(INS6, T, 8))
+      FoundMask |= 1 << 6;
+    if (NewSize == 8 && !memcmp(INS7, T, 8))
+      FoundMask |= 1 << 7;
+    if (NewSize == 8 && !memcmp(INS8, T, 8))
+      FoundMask |= 1 << 8;
+    if (NewSize == 8 && !memcmp(INS9, T, 8))
+      FoundMask |= 1 << 9;
+  }
+  EXPECT_EQ(FoundMask, (1 << 10) - 1);
+}
+
+TEST(MutationDispatcher, InsertRepeatedBytes1) {
+  TestInsertRepeatedBytes(&MutationDispatcher::Mutate_InsertRepeatedBytes,
+                          10000);
+}
+TEST(MutationDispatcher, InsertRepeatedBytes2) {
+  TestInsertRepeatedBytes(&MutationDispatcher::Mutate, 300000);
+}
+
+void TestChangeByte(Mutator M, int NumIter) {
+  auto MD = CreateMutationDispatcher();
+  int FoundMask = 0;
+  uint8_t CH0[8] = {0xF0, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH1[8] = {0x00, 0xF1, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH2[8] = {0x00, 0x11, 0xF2, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH3[8] = {0x00, 0x11, 0x22, 0xF3, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0xF4, 0x55, 0x66, 0x77};
+  uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0xF5, 0x66, 0x77};
+  uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0xF5, 0x77};
+  uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF7};
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[9] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+    size_t NewSize = (*MD.*M)(T, 8, 9);
+    if (NewSize == 8 && !memcmp(CH0, T, 8))
+      FoundMask |= 1 << 0;
+    if (NewSize == 8 && !memcmp(CH1, T, 8))
+      FoundMask |= 1 << 1;
+    if (NewSize == 8 && !memcmp(CH2, T, 8))
+      FoundMask |= 1 << 2;
+    if (NewSize == 8 && !memcmp(CH3, T, 8))
+      FoundMask |= 1 << 3;
+    if (NewSize == 8 && !memcmp(CH4, T, 8))
+      FoundMask |= 1 << 4;
+    if (NewSize == 8 && !memcmp(CH5, T, 8))
+      FoundMask |= 1 << 5;
+    if (NewSize == 8 && !memcmp(CH6, T, 8))
+      FoundMask |= 1 << 6;
+    if (NewSize == 8 && !memcmp(CH7, T, 8))
+      FoundMask |= 1 << 7;
+  }
+  EXPECT_EQ(FoundMask, 255);
+}
+
+TEST(MutationDispatcher, ChangeByte1) {
+  TestChangeByte(&MutationDispatcher::Mutate_ChangeByte, 1 << 15);
+}
+TEST(MutationDispatcher, ChangeByte2) {
+  TestChangeByte(&MutationDispatcher::Mutate, 1 << 17);
+}
+
+void TestChangeBit(Mutator M, int NumIter) {
+  auto MD = CreateMutationDispatcher();
+  int FoundMask = 0;
+  uint8_t CH0[8] = {0x01, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH1[8] = {0x00, 0x13, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH2[8] = {0x00, 0x11, 0x02, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH3[8] = {0x00, 0x11, 0x22, 0x37, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0x54, 0x55, 0x66, 0x77};
+  uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x54, 0x66, 0x77};
+  uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x76, 0x77};
+  uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0xF7};
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[9] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+    size_t NewSize = (*MD.*M)(T, 8, 9);
+    if (NewSize == 8 && !memcmp(CH0, T, 8))
+      FoundMask |= 1 << 0;
+    if (NewSize == 8 && !memcmp(CH1, T, 8))
+      FoundMask |= 1 << 1;
+    if (NewSize == 8 && !memcmp(CH2, T, 8))
+      FoundMask |= 1 << 2;
+    if (NewSize == 8 && !memcmp(CH3, T, 8))
+      FoundMask |= 1 << 3;
+    if (NewSize == 8 && !memcmp(CH4, T, 8))
+      FoundMask |= 1 << 4;
+    if (NewSize == 8 && !memcmp(CH5, T, 8))
+      FoundMask |= 1 << 5;
+    if (NewSize == 8 && !memcmp(CH6, T, 8))
+      FoundMask |= 1 << 6;
+    if (NewSize == 8 && !memcmp(CH7, T, 8))
+      FoundMask |= 1 << 7;
+  }
+  EXPECT_EQ(FoundMask, 255);
+}
+
+TEST(MutationDispatcher, ChangeBit1) {
+  TestChangeBit(&MutationDispatcher::Mutate_ChangeBit, 1 << 16);
+}
+TEST(MutationDispatcher, ChangeBit2) {
+  TestChangeBit(&MutationDispatcher::Mutate, 1 << 18);
+}
+
+void TestShuffleBytes(Mutator M, int NumIter) {
+  auto MD = CreateMutationDispatcher();
+  int FoundMask = 0;
+  uint8_t CH0[7] = {0x00, 0x22, 0x11, 0x33, 0x44, 0x55, 0x66};
+  uint8_t CH1[7] = {0x11, 0x00, 0x33, 0x22, 0x44, 0x55, 0x66};
+  uint8_t CH2[7] = {0x00, 0x33, 0x11, 0x22, 0x44, 0x55, 0x66};
+  uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x44, 0x55, 0x66, 0x33};
+  uint8_t CH4[7] = {0x00, 0x11, 0x22, 0x33, 0x55, 0x44, 0x66};
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
+    size_t NewSize = (*MD.*M)(T, 7, 7);
+    if (NewSize == 7 && !memcmp(CH0, T, 7))
+      FoundMask |= 1 << 0;
+    if (NewSize == 7 && !memcmp(CH1, T, 7))
+      FoundMask |= 1 << 1;
+    if (NewSize == 7 && !memcmp(CH2, T, 7))
+      FoundMask |= 1 << 2;
+    if (NewSize == 7 && !memcmp(CH3, T, 7))
+      FoundMask |= 1 << 3;
+    if (NewSize == 7 && !memcmp(CH4, T, 7))
+      FoundMask |= 1 << 4;
+  }
+  EXPECT_EQ(FoundMask, 31);
+}
+
+TEST(MutationDispatcher, ShuffleBytes1) {
+  TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 17);
+}
+TEST(MutationDispatcher, ShuffleBytes2) {
+  TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 20);
+}
+
+void TestCopyPart(Mutator M, int NumIter) {
+  auto MD = CreateMutationDispatcher();
+  int FoundMask = 0;
+  uint8_t CH0[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11};
+  uint8_t CH1[7] = {0x55, 0x66, 0x22, 0x33, 0x44, 0x55, 0x66};
+  uint8_t CH2[7] = {0x00, 0x55, 0x66, 0x33, 0x44, 0x55, 0x66};
+  uint8_t CH3[7] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x66};
+  uint8_t CH4[7] = {0x00, 0x11, 0x11, 0x22, 0x33, 0x55, 0x66};
+
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[7] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66};
+    size_t NewSize = (*MD.*M)(T, 7, 7);
+    if (NewSize == 7 && !memcmp(CH0, T, 7))
+      FoundMask |= 1 << 0;
+    if (NewSize == 7 && !memcmp(CH1, T, 7))
+      FoundMask |= 1 << 1;
+    if (NewSize == 7 && !memcmp(CH2, T, 7))
+      FoundMask |= 1 << 2;
+    if (NewSize == 7 && !memcmp(CH3, T, 7))
+      FoundMask |= 1 << 3;
+    if (NewSize == 7 && !memcmp(CH4, T, 7))
+      FoundMask |= 1 << 4;
+  }
+
+  uint8_t CH5[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22};
+  uint8_t CH6[8] = {0x22, 0x33, 0x44, 0x00, 0x11, 0x22, 0x33, 0x44};
+  uint8_t CH7[8] = {0x00, 0x11, 0x22, 0x00, 0x11, 0x22, 0x33, 0x44};
+  uint8_t CH8[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x22, 0x33, 0x44};
+  uint8_t CH9[8] = {0x00, 0x11, 0x22, 0x22, 0x33, 0x44, 0x33, 0x44};
+
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+    size_t NewSize = (*MD.*M)(T, 5, 8);
+    if (NewSize == 8 && !memcmp(CH5, T, 8))
+      FoundMask |= 1 << 5;
+    if (NewSize == 8 && !memcmp(CH6, T, 8))
+      FoundMask |= 1 << 6;
+    if (NewSize == 8 && !memcmp(CH7, T, 8))
+      FoundMask |= 1 << 7;
+    if (NewSize == 8 && !memcmp(CH8, T, 8))
+      FoundMask |= 1 << 8;
+    if (NewSize == 8 && !memcmp(CH9, T, 8))
+      FoundMask |= 1 << 9;
+  }
+
+  EXPECT_EQ(FoundMask, 1023);
+}
+
+TEST(MutationDispatcher, CopyPart1) {
+  TestCopyPart(&MutationDispatcher::Mutate_CopyPart, 1 << 10);
+}
+TEST(MutationDispatcher, CopyPart2) {
+  TestCopyPart(&MutationDispatcher::Mutate, 1 << 13);
+}
+TEST(MutationDispatcher, CopyPartNoInsertAtMaxSize) {
+  // This (non exhaustively) tests if `Mutate_CopyPart` tries to perform an
+  // insert on an input of size `MaxSize`.  Performing an insert in this case
+  // will lead to the mutation failing.
+  auto MD = CreateMutationDispatcher();
+  uint8_t Data[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x00, 0x11, 0x22};
+  size_t MaxSize = sizeof(Data);
+  for (int count = 0; count < (1 << 18); ++count) {
+    size_t NewSize = MD->Mutate_CopyPart(Data, MaxSize, MaxSize);
+    ASSERT_EQ(NewSize, MaxSize);
+  }
+}
+
+void TestAddWordFromDictionary(Mutator M, int NumIter) {
+  auto MD = CreateMutationDispatcher();
+  uint8_t Word1[4] = {0xAA, 0xBB, 0xCC, 0xDD};
+  uint8_t Word2[3] = {0xFF, 0xEE, 0xEF};
+  MD->AddWordToManualDictionary(Word(Word1, sizeof(Word1)));
+  MD->AddWordToManualDictionary(Word(Word2, sizeof(Word2)));
+  int FoundMask = 0;
+  uint8_t CH0[7] = {0x00, 0x11, 0x22, 0xAA, 0xBB, 0xCC, 0xDD};
+  uint8_t CH1[7] = {0x00, 0x11, 0xAA, 0xBB, 0xCC, 0xDD, 0x22};
+  uint8_t CH2[7] = {0x00, 0xAA, 0xBB, 0xCC, 0xDD, 0x11, 0x22};
+  uint8_t CH3[7] = {0xAA, 0xBB, 0xCC, 0xDD, 0x00, 0x11, 0x22};
+  uint8_t CH4[6] = {0x00, 0x11, 0x22, 0xFF, 0xEE, 0xEF};
+  uint8_t CH5[6] = {0x00, 0x11, 0xFF, 0xEE, 0xEF, 0x22};
+  uint8_t CH6[6] = {0x00, 0xFF, 0xEE, 0xEF, 0x11, 0x22};
+  uint8_t CH7[6] = {0xFF, 0xEE, 0xEF, 0x00, 0x11, 0x22};
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[7] = {0x00, 0x11, 0x22};
+    size_t NewSize = (*MD.*M)(T, 3, 7);
+    if (NewSize == 7 && !memcmp(CH0, T, 7))
+      FoundMask |= 1 << 0;
+    if (NewSize == 7 && !memcmp(CH1, T, 7))
+      FoundMask |= 1 << 1;
+    if (NewSize == 7 && !memcmp(CH2, T, 7))
+      FoundMask |= 1 << 2;
+    if (NewSize == 7 && !memcmp(CH3, T, 7))
+      FoundMask |= 1 << 3;
+    if (NewSize == 6 && !memcmp(CH4, T, 6))
+      FoundMask |= 1 << 4;
+    if (NewSize == 6 && !memcmp(CH5, T, 6))
+      FoundMask |= 1 << 5;
+    if (NewSize == 6 && !memcmp(CH6, T, 6))
+      FoundMask |= 1 << 6;
+    if (NewSize == 6 && !memcmp(CH7, T, 6))
+      FoundMask |= 1 << 7;
+  }
+  EXPECT_EQ(FoundMask, 255);
+}
+
+TEST(MutationDispatcher, AddWordFromDictionary1) {
+  TestAddWordFromDictionary(
+      &MutationDispatcher::Mutate_AddWordFromManualDictionary, 1 << 15);
+}
+
+TEST(MutationDispatcher, AddWordFromDictionary2) {
+  TestAddWordFromDictionary(&MutationDispatcher::Mutate, 1 << 15);
+}
+
+void TestChangeASCIIInteger(Mutator M, int NumIter) {
+  auto MD = CreateMutationDispatcher();
+
+  uint8_t CH0[8] = {'1', '2', '3', '4', '5', '6', '7', '7'};
+  uint8_t CH1[8] = {'1', '2', '3', '4', '5', '6', '7', '9'};
+  uint8_t CH2[8] = {'2', '4', '6', '9', '1', '3', '5', '6'};
+  uint8_t CH3[8] = {'0', '6', '1', '7', '2', '8', '3', '9'};
+  int FoundMask = 0;
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[8] = {'1', '2', '3', '4', '5', '6', '7', '8'};
+    size_t NewSize = (*MD.*M)(T, 8, 8);
+    /**/ if (NewSize == 8 && !memcmp(CH0, T, 8))
+      FoundMask |= 1 << 0;
+    else if (NewSize == 8 && !memcmp(CH1, T, 8))
+      FoundMask |= 1 << 1;
+    else if (NewSize == 8 && !memcmp(CH2, T, 8))
+      FoundMask |= 1 << 2;
+    else if (NewSize == 8 && !memcmp(CH3, T, 8))
+      FoundMask |= 1 << 3;
+    else if (NewSize == 8)
+      FoundMask |= 1 << 4;
+  }
+  EXPECT_EQ(FoundMask, 31);
+}
+
+TEST(MutationDispatcher, ChangeASCIIInteger1) {
+  TestChangeASCIIInteger(&MutationDispatcher::Mutate_ChangeASCIIInteger,
+                         1 << 15);
+}
+
+TEST(MutationDispatcher, ChangeASCIIInteger2) {
+  TestChangeASCIIInteger(&MutationDispatcher::Mutate, 1 << 15);
+}
+
+void TestChangeBinaryInteger(Mutator M, int NumIter) {
+  auto MD = CreateMutationDispatcher();
+
+  uint8_t CH0[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x79};
+  uint8_t CH1[8] = {0x00, 0x11, 0x22, 0x31, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH2[8] = {0xff, 0x10, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH3[8] = {0x00, 0x11, 0x2a, 0x33, 0x44, 0x55, 0x66, 0x77};
+  uint8_t CH4[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x4f, 0x66, 0x77};
+  uint8_t CH5[8] = {0xff, 0xee, 0xdd, 0xcc, 0xbb, 0xaa, 0x99, 0x88};
+  uint8_t CH6[8] = {0x00, 0x11, 0x22, 0x00, 0x00, 0x00, 0x08, 0x77}; // Size
+  uint8_t CH7[8] = {0x00, 0x08, 0x00, 0x33, 0x44, 0x55, 0x66, 0x77}; // Sw(Size)
+
+  int FoundMask = 0;
+  for (int i = 0; i < NumIter; i++) {
+    uint8_t T[8] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77};
+    size_t NewSize = (*MD.*M)(T, 8, 8);
+    /**/ if (NewSize == 8 && !memcmp(CH0, T, 8))
+      FoundMask |= 1 << 0;
+    else if (NewSize == 8 && !memcmp(CH1, T, 8))
+      FoundMask |= 1 << 1;
+    else if (NewSize == 8 && !memcmp(CH2, T, 8))
+      FoundMask |= 1 << 2;
+    else if (NewSize == 8 && !memcmp(CH3, T, 8))
+      FoundMask |= 1 << 3;
+    else if (NewSize == 8 && !memcmp(CH4, T, 8))
+      FoundMask |= 1 << 4;
+    else if (NewSize == 8 && !memcmp(CH5, T, 8))
+      FoundMask |= 1 << 5;
+    else if (NewSize == 8 && !memcmp(CH6, T, 8))
+      FoundMask |= 1 << 6;
+    else if (NewSize == 8 && !memcmp(CH7, T, 8))
+      FoundMask |= 1 << 7;
+  }
+  EXPECT_EQ(FoundMask, 255);
+}
+
+TEST(MutationDispatcher, ChangeBinaryInteger1) {
+  TestChangeBinaryInteger(&MutationDispatcher::Mutate_ChangeBinaryInteger,
+                          1 << 12);
+}
+
+TEST(MutationDispatcher, ChangeBinaryInteger2) {
+  TestChangeBinaryInteger(&MutationDispatcher::Mutate, 1 << 15);
+}
+
+// Test fixture for MutagenInterface unit tests.
+static const char *kWord1 = "word1";
+static const char *kWord2 = "word2";
+
+class MutagenInterface : public ::testing::Test {
+protected:
+  void SetUp() override {
+    Current = this;
+    memset(&Config, 0, sizeof(Config));
+
+    Config.Seed = 1;
+
+    Config.UseCmp = 1;
+    Config.FromTORC4 = [](size_t Idx, uint32_t *Arg1, uint32_t *Arg2) {
+      ++(Current->FromTORC4Calls);
+      *Arg1 = 0x0401;
+      *Arg2 = 0x0402;
+    };
+    Config.FromTORC8 = [](size_t Idx, uint64_t *Arg1, uint64_t *Arg2) {
+      ++(Current->FromTORC8Calls);
+      *Arg1 = 0x0801;
+      *Arg2 = 0x0802;
+    };
+    Config.FromTORCW = [](size_t Idx, const uint8_t **Data1, size_t *Size1,
+                          const uint8_t **Data2, size_t *Size2) {
+      ++(Current->FromTORCWCalls);
+      *Data1 = reinterpret_cast<const uint8_t *>(kWord1);
+      *Size1 = strlen(kWord1);
+      *Data2 = reinterpret_cast<const uint8_t *>(kWord2);
+      *Size2 = strlen(kWord2);
+    };
+
+    Config.UseMemmem = 0;
+    Config.FromMMT = [](size_t Idx, const uint8_t **Data, size_t *Size) {
+      ++(Current->FromMMTCalls);
+      *Data = reinterpret_cast<const uint8_t *>(kWord1);
+      *Size = strlen(kWord1);
+    };
+
+    Config.OnlyASCII = 0;
+
+    Config.CustomMutator = [](uint8_t *Data, size_t Size, size_t MaxSize,
+                              unsigned int Seed) {
+      ++(Current->CustomMutatorCalls);
+      return LLVMMutagenDefaultMutate(Data, Size, MaxSize);
+    };
+
+    Config.CustomCrossOver =
+        [](const uint8_t *Data1, size_t Size1, const uint8_t *Data2,
+           size_t Size2, uint8_t *Out, size_t MaxOutSize, unsigned int Seed) {
+          ++(Current->CustomCrossOverCalls);
+          auto *MD = GetMutationDispatcherForTest();
+          return MD->CrossOver(Data1, Size1, Data2, Size2, Out, MaxOutSize);
+        };
+
+#if HAS_MSAN
+    Config.MSanUnpoison = __msan_unpoison;
+    Config.MSanUnpoisonParam = __msan_unpoison_param;
+#endif // HAS_MSAN
+
+    U = Unit({1, 2, 3, 4});
+    U.reserve(8);
+  }
+
+  void TearDown() override {
+    Current = nullptr;
+    memset(&Config, 0, sizeof(Config));
+    LLVMMutagenConfigure(&Config);
+  }
+
+  LLVMMutagenConfiguration Config;
+  Unit U;
+
+  size_t FromTORC4Calls = 0;
+  size_t FromTORC8Calls = 0;
+  size_t FromTORCWCalls = 0;
+  size_t FromMMTCalls = 0;
+  size_t CustomMutatorCalls = 0;
+  size_t CustomCrossOverCalls = 0;
+
+private:
+  static MutagenInterface *Current;
+};
+
+MutagenInterface *MutagenInterface::Current = nullptr;
+
+// Unit tests for MutagenInterface.
+
+TEST_F(MutagenInterface, Configure) {
+  Config.OnlyASCII = 1;
+  LLVMMutagenConfigure(&Config);
+  auto *MD = GetMutationDispatcherForTest();
+  ASSERT_NE(MD, nullptr);
+
+  Random Rand1(Config.Seed);
+  Random &Rand2 = MD->GetRand();
+  for (size_t i = 0; i < 10; ++i)
+    EXPECT_EQ(Rand1(), Rand2());
+
+  Config.Seed = static_cast<unsigned>(
+      std::chrono::system_clock::now().time_since_epoch().count());
+  Config.OnlyASCII = 0;
+  LLVMMutagenConfigure(&Config);
+  MD = GetMutationDispatcherForTest();
+  ASSERT_NE(MD, nullptr);
+
+  Random Rand3(Config.Seed);
+  Random &Rand4 = MD->GetRand();
+  for (size_t i = 0; i < 10; ++i)
+    EXPECT_EQ(Rand3(), Rand4());
+}
+
+TEST_F(MutagenInterface, UseTORCs) {
+  // If !UseCmp, none of the TORC/MMT callbacks are called, regardless of
+  // UseMemmem.
+  Config.UseCmp = 0;
+  Config.UseMemmem = 1;
+  LLVMMutagenConfigure(&Config);
+  for (size_t i = 0; i < 200; ++i)
+    LLVMMutagenMutate(U.data(), U.size(), U.capacity());
+  EXPECT_EQ(FromTORC4Calls, 0U);
+  EXPECT_EQ(FromTORC8Calls, 0U);
+  EXPECT_EQ(FromTORCWCalls, 0U);
+  EXPECT_EQ(FromMMTCalls, 0U);
+
+  // If UseCmp, but !UseMemmem, only the TORC callbacks are invoked.
+  Config.UseCmp = 1;
+  Config.UseMemmem = 0;
+  LLVMMutagenConfigure(&Config);
+  for (size_t i = 0; i < 200; ++i)
+    LLVMMutagenMutate(U.data(), U.size(), U.capacity());
+  EXPECT_NE(FromTORC4Calls, 0U);
+  EXPECT_NE(FromTORC8Calls, 0U);
+  EXPECT_NE(FromTORCWCalls, 0U);
+  EXPECT_EQ(FromMMTCalls, 0U);
+
+  // If UseCmp and UseMemmem, all the TORC/MMT callbacks are invoked.
+  Config.UseCmp = 1;
+  Config.UseMemmem = 1;
+  LLVMMutagenConfigure(&Config);
+  for (size_t i = 0; i < 200; ++i)
+    LLVMMutagenMutate(U.data(), U.size(), U.capacity());
+  EXPECT_NE(FromTORC4Calls, 0U);
+  EXPECT_NE(FromTORC8Calls, 0U);
+  EXPECT_NE(FromTORCWCalls, 0U);
+  EXPECT_NE(FromMMTCalls, 0U);
+}
+
+TEST_F(MutagenInterface, CustomCallbacks) {
+  // DefaultMutate never selects custom callbacks.
+  LLVMMutagenConfigure(&Config);
+  for (size_t i = 0; i < 200; ++i)
+    LLVMMutagenDefaultMutate(U.data(), U.size(), U.capacity());
+
+  // Valid.
+  auto *MD = GetMutationDispatcherForTest();
+  EXPECT_EQ(CustomMutatorCalls, 0U);
+  MD->Mutate_Custom(U.data(), U.size(), U.capacity());
+  EXPECT_EQ(CustomMutatorCalls, 1U);
+
+  // Null cross-over input disables CustomCrossOver.
+  LLVMMutagenSetCrossOverWith(nullptr, 0);
+  MD->Mutate_CustomCrossOver(U.data(), U.size(), U.capacity());
+  EXPECT_EQ(CustomCrossOverCalls, 0U);
+
+  // Zero-length cross-over input disables CustomCrossOver.
+  Unit CrossOverWith = {4, 3, 2, 1};
+  LLVMMutagenSetCrossOverWith(CrossOverWith.data(), 0);
+  MD->Mutate_CustomCrossOver(U.data(), U.size(), U.capacity());
+  EXPECT_EQ(CustomCrossOverCalls, 0U);
+
+  // Valid.
+  LLVMMutagenSetCrossOverWith(CrossOverWith.data(), CrossOverWith.size());
+  MD->Mutate_CustomCrossOver(U.data(), U.size(), U.capacity());
+  EXPECT_EQ(CustomCrossOverCalls, 1U);
+
+  // Can mutate without custom callbacks.
+  Config.CustomMutator = nullptr;
+  Config.CustomCrossOver = nullptr;
+  LLVMMutagenConfigure(&Config);
+  for (size_t i = 0; i < 200; ++i)
+    LLVMMutagenMutate(U.data(), U.size(), U.capacity());
+}
+
+TEST_F(MutagenInterface, MutationSequence) {
+  LLVMMutagenConfigure(&Config);
+  char Buf[1024];
+  size_t NumItems;
+
+  Set<std::string> Names = {
+      "ShuffleBytes", "EraseBytes", "InsertBytes", "InsertRepeatedBytes",
+      "ChangeByte",   "ChangeBit",  "CopyPart",    "ChangeASCIIInt",
+      "ChangeBinInt",
+  };
+  std::string Name;
+  std::istringstream ISS;
+
+  // Empty sequences
+  auto Size = LLVMMutagenGetMutationSequence(true, Buf, sizeof(Buf), &NumItems);
+  EXPECT_STREQ(Buf, "");
+  EXPECT_EQ(Size, 0U);
+  EXPECT_EQ(NumItems, 0U);
+
+  while (true) {
+    // Can get size without output parameters.
+    Size = LLVMMutagenGetMutationSequence(true, nullptr, 0, &NumItems);
+    if (NumItems > Sequence<Mutator>::kMaxBriefItems)
+      break;
+    // !Verbose has no effect for <= 10 items.
+    EXPECT_EQ(LLVMMutagenGetMutationSequence(false, nullptr, 0, nullptr), Size);
+    EXPECT_GT(LLVMMutagenDefaultMutate(U.data(), U.size(), U.capacity()), 0U);
+  }
+
+  // All items are valid.
+  LLVMMutagenGetMutationSequence(true, Buf, sizeof(Buf), nullptr);
+  ISS.str(Buf);
+  size_t N = 0;
+  while (std::getline(ISS, Name, '-')) {
+    EXPECT_GT(Names.count(Name), 0U);
+    ++N;
+  }
+  EXPECT_EQ(N, NumItems);
+
+  // !Verbose truncates, but items are still valid.
+  EXPECT_LT(LLVMMutagenGetMutationSequence(false, Buf, sizeof(Buf), nullptr),
+            Size);
+  ISS.str(Buf);
+  N = 0;
+  while (std::getline(ISS, Name, '-')) {
+    EXPECT_GT(Names.count(Name), 0U);
+    ++N;
+  }
+  EXPECT_LT(N, NumItems);
+
+  // Truncated sequence is a prefix of its untruncated equivalent.
+  std::string Truncated(Buf);
+  LLVMMutagenGetMutationSequence(true, Buf, sizeof(Buf), &NumItems);
+  Buf[Truncated.size()] = '\0';
+  EXPECT_STREQ(Truncated.c_str(), Buf);
+
+  // Stops at the end of |Buf|, and null terminates.
+  EXPECT_EQ(LLVMMutagenGetMutationSequence(true, Buf, Size - 1, nullptr), Size);
+  EXPECT_EQ(strlen(Buf), Size - 2);
+
+  // Clear the sequence.
+  LLVMMutagenResetSequence();
+  EXPECT_EQ(LLVMMutagenGetMutationSequence(true, nullptr, 0, nullptr), 0U);
+}
+
+static uint8_t FromASCIINybble(char C) {
+  if ('0' <= C && C <= '9')
+    return static_cast<uint8_t>(C - '0');
+  if ('A' <= C && C <= 'F')
+    return static_cast<uint8_t>(C - 'A' + 10);
+  assert('a' <= C && C <= 'f');
+  return static_cast<uint8_t>(C - 'a' + 10);
+}
+
+static Word FromASCII(const char *DE) {
+  Unit Tmp;
+  bool Escape = false;
+  size_t Hex = 0;
+  uint8_t Nybble = 0;
+  for (char C = *DE++; C; C = *DE++) {
+    if (Hex == 2) {
+      Nybble = FromASCIINybble(C);
+      --Hex;
+    } else if (Hex == 1) {
+      Tmp.push_back(static_cast<uint8_t>(Nybble << 4) | FromASCIINybble(C));
+      --Hex;
+    } else if (Escape) {
+      switch (C) {
+      case '\\':
+      case '"':
+        Tmp.push_back(static_cast<uint8_t>(C));
+        break;
+      case 'x':
+        Hex = 2;
+        break;
+      default:
+        assert(false && "FromASCII failure.");
+      }
+      Escape = false;
+    } else if (C == '\\') {
+      Escape = true;
+    } else {
+      Tmp.push_back(static_cast<uint8_t>(C));
+    }
+  }
+  return Word(Tmp.data(), Tmp.size());
+}
+
+TEST_F(MutagenInterface, Dictionaries) {
+  LLVMMutagenConfigure(&Config);
+  size_t NumItems;
+  char Buf[1024];
+  std::istringstream ISS;
+  std::string Str;
+
+  // Empty sequences
+  auto Size =
+      LLVMMutagenGetDictionaryEntrySequence(true, Buf, sizeof(Buf), &NumItems);
+  EXPECT_STREQ(Buf, "");
+  EXPECT_EQ(Size, 0U);
+  EXPECT_EQ(NumItems, 0U);
+
+  auto *MD = GetMutationDispatcherForTest();
+  while (true) {
+    // Can get size without output parameters.
+    Size = LLVMMutagenGetDictionaryEntrySequence(true, nullptr, 0, &NumItems);
+    if (NumItems > Sequence<DictionaryEntry *>::kMaxBriefItems)
+      break;
+    // !Verbose has no effect for <= 10 items.
+    EXPECT_EQ(LLVMMutagenGetDictionaryEntrySequence(false, nullptr, 0, nullptr),
+              Size);
+    MD->Mutate_AddWordFromTORC(U.data(), U.size(), U.capacity());
+  }
+
+  // All items are valid.
+  LLVMMutagenGetDictionaryEntrySequence(true, Buf, sizeof(Buf), nullptr);
+  ISS.str(Buf);
+  size_t N = 0;
+  while (std::getline(ISS, Str, '-')) {
+    ASSERT_FALSE(Str.empty());
+    EXPECT_EQ(Str[0], '"');
+    EXPECT_EQ(Str[Str.size() - 1], '"');
+    ++N;
+  }
+  EXPECT_EQ(N, NumItems);
+
+  // !Verbose truncates, but items are still valid.
+  EXPECT_LT(
+      LLVMMutagenGetDictionaryEntrySequence(false, Buf, sizeof(Buf), nullptr),
+      Size);
+  ISS.str(Buf);
+  N = 0;
+  while (std::getline(ISS, Str, '-')) {
+    ASSERT_FALSE(Str.empty());
+    EXPECT_EQ(Str[0], '"');
+    EXPECT_EQ(Str[Str.size() - 1], '"');
+    ++N;
+  }
+  EXPECT_LT(N, NumItems);
+
+  // Truncated sequence is a prefix of its untruncated equivalent.
+  std::string Truncated(Buf);
+  LLVMMutagenGetDictionaryEntrySequence(true, Buf, sizeof(Buf), &NumItems);
+  Buf[Truncated.size()] = '\0';
+  EXPECT_STREQ(Truncated.c_str(), Buf);
+
+  // Stops at the end of |Buf|, and null terminates.
+  EXPECT_EQ(LLVMMutagenGetDictionaryEntrySequence(true, Buf, Size - 1, nullptr),
+            Size);
+  EXPECT_EQ(strlen(Buf), Size - 2);
+
+  // Clear the sequence.
+  LLVMMutagenResetSequence();
+  EXPECT_EQ(LLVMMutagenGetDictionaryEntrySequence(true, nullptr, 0, nullptr),
+            0U);
+
+  // Retuns null if no recommendations.
+  size_t UseCount = 0;
+  EXPECT_EQ(LLVMMutagenRecommendDictionaryEntry(&UseCount), nullptr);
+  EXPECT_EQ(LLVMMutagenRecommendDictionary(), 0U);
+  EXPECT_EQ(LLVMMutagenRecommendDictionaryEntry(&UseCount), nullptr);
+
+  // Record sequences.
+  for (size_t i = 0; i < 5; ++i) {
+    for (size_t i = 0; i < 5; ++i) {
+      MD->Mutate_AddWordFromTORC(U.data(), U.size(), U.capacity());
+    }
+    LLVMMutagenRecordSequence();
+  }
+
+  size_t NumDEs = LLVMMutagenRecommendDictionary();
+  EXPECT_NE(NumDEs, 0U);
+  for (size_t i = 0; i < NumDEs; ++i) {
+    auto *DE = LLVMMutagenRecommendDictionaryEntry(&UseCount);
+    EXPECT_NE(DE, nullptr);
+    EXPECT_EQ(UseCount, 0U);
+  }
+
+  // Increment the use counts of entries.
+  for (size_t i = 0; i < 100; ++i)
+    MD->Mutate_AddWordFromPersistentAutoDictionary(U.data(), U.size(),
+                                                   U.capacity());
+  NumDEs = LLVMMutagenRecommendDictionary();
+  EXPECT_NE(NumDEs, 0U);
+  for (size_t i = 0; i < NumDEs; ++i) {
+    auto *DE = LLVMMutagenRecommendDictionaryEntry(&UseCount);
+    EXPECT_NE(DE, nullptr);
+    EXPECT_NE(UseCount, 0U);
+  }
+
+  // Add the first few words manually to exclude them from recommendations.
+  Vector<Word> ManualAdditions;
+  NumDEs = LLVMMutagenRecommendDictionary();
+  ASSERT_GT(NumDEs, 3U);
+  for (size_t i = 0; i < 3; ++i) {
+    auto *DE = LLVMMutagenRecommendDictionaryEntry(nullptr);
+    auto W = FromASCII(DE);
+    LLVMMutagenAddWordToDictionary(W.data(), W.size());
+    ManualAdditions.push_back(W);
+  }
+  N = NumDEs;
+
+  // Get the recommended dictionary without the manual additions.
+  NumDEs = LLVMMutagenRecommendDictionary();
+  EXPECT_EQ(NumDEs, N - 3);
+  for (size_t i = 0; i < NumDEs; ++i) {
+    auto *DE = LLVMMutagenRecommendDictionaryEntry(nullptr);
+    ASSERT_NE(DE, nullptr);
+    Word W1(reinterpret_cast<const uint8_t *>(DE), strlen(DE));
+    for (const auto &W2 : ManualAdditions)
+      EXPECT_FALSE(W1 == W2);
+  }
+}
+
+} // namespace
+} // namespace mutagen
+
+#undef HAS_MSAN
+
+int main(int argc, char **argv) {
+  testing::InitGoogleTest(&argc, argv);
+  return RUN_ALL_TESTS();
+}

compiler-rt/test/fuzzer/CMakeLists.txt

 set(FUZZER_TEST_ARCH ${FUZZER_SUPPORTED_ARCH})
 if (APPLE)
   darwin_filter_host_archs(FUZZER_SUPPORTED_ARCH FUZZER_TEST_ARCH)
 endif()
 
 if(COMPILER_RT_INCLUDE_TESTS)
   list(APPEND LIBFUZZER_TEST_DEPS FuzzerUnitTests)
   list(APPEND LIBFUZZER_TEST_DEPS FuzzedDataProviderUnitTests)
+  list(APPEND LIBFUZZER_TEST_DEPS MutagenUnitTests)
 endif()
 
 add_custom_target(check-fuzzer)
 
 if(COMPILER_RT_INCLUDE_TESTS)
   # libFuzzer unit tests.
   configure_lit_site_cfg(
     ${CMAKE_CURRENT_SOURCE_DIR}/unit/lit.site.cfg.py.in