Refactor mutation strategies into a standalone library

[aarongreen]

Summary

This change introduces libMutagen/libclang_rt.mutagen.a as a subset of libFuzzer/libclang_rt.fuzzer.a. This library contains only the fuzzing strategies used by libFuzzer to produce new test inputs from provided inputs, dictionaries, and SanitizerCoverage feedback.

Most of this change is simply moving sections of code to one side or the other of the library boundary. The only meaningful new code is:

• The Mutagen.h interface and its implementation in Mutagen.cpp.
• The following methods in MutagenDispatcher.cpp:
  • UseCmp
  • UseMemmem
  • SetCustomMutator
  • SetCustomCrossOver
  • LateInitialize (similar to the MutationDispatcher's original constructor)
  • Mutate_AddWordFromTORC (uses callbacks instead of accessing TPC directly)
  • StartMutationSequence
  • MutationSequence
  • DictionaryEntrySequence
  • RecommendDictionary
  • RecommendDictionaryEntry
• FuzzerMutate.cpp (which now justs sets callbacks and handles printing)
• MutagenUnittest.cpp (which adds tests of Mutagen.h)

A note on performance: This change was tested with a 100 passes of test/fuzzer/LargeTest.cpp with 1000 runs per pass, both with and without the change. The running time distribution was qualitatively similar both with and without the change, and the average difference was within 30 microseconds (2.240 ms/run vs 2.212 ms/run, respectively). Both times were much higher than observed with the fully optimized system clang (~0.38 ms/run), most likely due to the combination of CMake "dev mode" settings (e.g. CMAKE_BUILD_TYPE="Debug", LLVM_ENABLE_LTO=OFF, etc.). The difference between the two versions built similarly seems to be "in the noise" and suggests no meaningful performance degradation.

[morehouse]

compiler-rt/lib/fuzzer/FuzzerUtil.h

58

These functions appear unused.

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

27–28

37

I think we have an off-by-one error here.

Needed does not include the null terminator, so ToCopy is the number of bytes *not* including the null byte. But the function comment says it should include the null byte.

i.e. we are writing one extra byte (the null terminator) than we said we would.

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

62–63

72

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

73

Why initialize lazily?

If explicitly initialize, we can avoid the if (!Initialized) check in Mutate.

117

This is missing a recent bugfix for libFuzzer + MSan:

if (EF->__msan_unpoison)
  EF->__msan_unpoison(Data, Size);
if (EF->__msan_unpoison_param)
  EF->__msan_unpoison_param(4);

131

Similar MSan bugfix is missing here.

239

This line is missing a recent off-by-one bugfix.

555

Maybe a Sequence::clear() function would make sense.

566

This line is missing a recent bugfix.

591

It's confusing what's going on in this function. I think it might be clearer if we make Sequence into a class type that manages its own members.

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

21 ↗

(On Diff #345294)

This appears unused. Also, we don't we use the one in FuzzerUtil?

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

26

s/NULL/nullptr

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

47

Is the CrossOver test intentionally deleted?

[aarongreen]

compiler-rt/lib/fuzzer/FuzzerUtil.h

58

They are used by FuzzerDriver and FuzzerUnittest. They were always implemented in FuzzerUtil.cpp, but declared in the old FuzzerDictionary.h. When the latter file moved "over the line" to mutagen/MutagenDictionary, it made sense to relocate them to FuzzerUtil.h.

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

27–28

Obsolete with MutagenSequence.

37

I wanted this to be snprintf-like, but I was worried about performance. That's a bit silly: we print mutation and dictionary entry sequences infrequently enough that the right way to go is just to use snprintf and have done.

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

73

It was too allow UseCmp, UseMemmem, SetCustomMutator, and SetCustomCrossOver to be called between the constructor and Mutate.

But, the need for msan_unposion and msan_unpoison_param has pushed me over the edge: I've elected to create an 'LLVMMutagenConfiguration` struct instead, that has all these options and function pointers and can be set together by the constructor.

591

See the new mutagen/MutagenSequence.h.

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

21 ↗

(On Diff #345294)

Whoops, good catch. At one point I tried moving the TORCs "across the line". For performance reasons, I decided to keep them closer to the TPC and use the From* callbacks instead.

More generally, I've tried hard to minimize the dependences of libMutagen on libFuzzer to make it as standalone as possible. At the moment, there's a few header dependencies for things I didn't want to duplicate.

The ideal, final state would be for libMutagen not to depend on any libFuzzer source, and libFuzzer to only depend on Mutagen.h.

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

26

I don't disagree, but I think that kind of clean up so happen in a different change. This is a straight copy/paste from FuzzerUtilWindows.cpp on main.

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

47

Nope, I think I copied "FuzzerMutate" tests, and then deleted everything that looked like a mutate test, including CrossOver. It's been added back to MutagenUnittest, while the Hash test has been restored to FuzzerUnittest.

[aarongreen]

3 out of the 4 lines clang-tidy complains about match what's in other source files on main; this change addresses the last one.

[morehouse]

Please remove libMutagen.a from the diff before landing since we don't have libFuzzer.a in the current tree either.

[aarongreen]

In D102447#2777667, @morehouse wrote:

Please remove libMutagen.a from the diff before landing since we don't have libFuzzer.a in the current tree either.

Or better yet, I should fix my gitignore so I stop making that mistake. :|

[morehouse]

Multiples tests are failing on the bots: https://lab.llvm.org/buildbot/#/builders/75/builds/6122/steps/7/logs/stdio

Failed Tests (3):
  libFuzzer :: magic-separator.test
  libFuzzer :: noasan-strstr.test
  libFuzzer :: strstr.test

Also on Windows: https://lab.llvm.org/buildbot/#/builders/127/builds/11499

Failed Tests (25):
  libFuzzer :: bad-strcmp.test
  libFuzzer :: fork.test
  libFuzzer :: fuzzer-customcrossover.test
  libFuzzer :: fuzzer-customcrossoverandmutate.test
  libFuzzer :: fuzzer-dict.test
  libFuzzer :: fuzzer-dirs.test
  libFuzzer :: fuzzer-fdmask.test
  libFuzzer :: fuzzer-finalstats.test
  libFuzzer :: fuzzer-flags.test
  libFuzzer :: fuzzer-oom.test
  libFuzzer :: fuzzer-seed.test
  libFuzzer :: fuzzer-threaded.test
  libFuzzer :: large.test
  libFuzzer :: len_control.test
  libFuzzer :: max-number-of-runs.test
  libFuzzer :: print-func.test
  libFuzzer :: recommended-dictionary.test
  libFuzzer :: reduce_inputs.test
  libFuzzer :: seed_inputs.test
  libFuzzer :: shrink.test
  libFuzzer :: strstr.test
  libFuzzer :: three-bytes.test
  libFuzzer :: trace-malloc-2.test
  libFuzzer :: trace-malloc-unbalanced.test
  libFuzzer :: trace-malloc.test

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

12

Needed to compile on Windows.

[aarongreen]

Fixed an issue with msan function pointers being uninitialized.

[aarongreen]

Add no-sanitize-all to from* functions.

[aarongreen]

The previous patch was a long-shot to try to get clang-tidy to find clang/clang.h. It didn't work, so there's no reason to modify tests/CMakeLists.txt. The patch reverts it.

[morehouse]

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

41–44

Why is ATTRIBUTE_NO_SANITIZE_ALL needed?

It can't hurt, I'm just curious. AFAIK we don't normally compile the libFuzzer code itself with sanitizers anymore.

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

615

Does the unittest run with MSan currently?

[aarongreen]

Okay, so after return from a few weeks vacation, I've tried to examine the three tests that failed earlier in detail. I added counters for additions to the TORCs, MMT, and ValueProfileMap to ensure no signal was being lost, and compared the log of successful mutation sequences before and after the change.

strstr.test and nonasan-strstr.test produce exactly the same output with and without this change, modulo things like memory addresses.

The output for the magic-separator.test on the other hand, does differ slightly. With this change, it appears to execute *faster* by the slightest amount and therefore ends up producing a different sequence of mutations. My best guess is the TimeOfUnit for one or more inputs are hovering right around one of the edges in InputInfo::UpdateEnergy, resulting in a different distribution. The result is the failure is found in about half as many iterations with the change as without.

I can get the test to produce the same sequence of mutations by adding microsecond delays after ~1700 runs.

Given all of this, I believe the patch should pass the tests now and can be relanded. I have some residual uncertainty from the fact that I haven't been able to reproduce the failures locally, but given the data I have, I can't find any other discrepancy introduced by the change.

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

41–44

I was concerned that the calls to From* might be introducing noise into the TORCs/MMT. But, as you say, none of this is instrumented. I'll remove them.

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

615

Not without a lot of hoop-jumping to rebuild libcxx, gtest, libFuzzer, etc. with MSan enabled. It's not really worth the hassle, so I'm changing the preprocessor condition to instead emit a compilation error if you try to compile the unit test with -fsanitize=memory.

[morehouse]

LGTM

[aarongreen]

Update: I'm still having trouble reproducing the Windows-only failure in a handful of integration tests. I'm de-prioritizing this just a bit on my end as it's not strictly necessary for a near-term demo. I will return and figure the Windows issue out, though, as it *is* necessary to land this change and make it available to Fuchsia downstream.

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 -O2 -fno-omit-frame-pointer -std=c++17 $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
+set -e
+LIBMUTAGEN_SRC_DIR=$(dirname $0)
+CXX="${CXX:-clang}"
+for f in $LIBMUTAGEN_SRC_DIR/*.cpp; do
+  $CXX -O2 -fno-omit-frame-pointer -std=c++11 -I$LIBMUTAGEN_SRC_DIR/.. $f -c &
+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>
+
+namespace mutagen {
+namespace {
+
+using fuzzer::Set;
+
+std::unique_ptr<MutationDispatcher> CreateMutationDispatcher() {
+  LLVMMutagenConfiguration Config;
+  memset(&Config, 0, sizeof(Config));
+  return std::make_unique<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;
+
+    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);
+        };
+
+    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
+
+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