Add a Fuzzer library

Summary:
A simple genetic in-process coverage-guided fuzz testing library.

I've used this fuzzer to test clang-format
(it found 12+ bugs, thanks djasper@ for the fixes!)
and it may also help us test other parts of LLVM.
So why not keep it in the LLVM repository?

I plan to add the cmake build rules later (in a separate patch, if that's ok)
and also add a clang-format-fuzzer target.

See README.txt for details.

Test Plan: Tests will follow separately.

Reviewers: djasper, chandlerc, rnk

Reviewed By: rnk

Subscribers: majnemer, ygribov, dblaikie, llvm-commits

Differential Revision: http://reviews.llvm.org/D7184

llvm-svn: 227252

1 files changed, 46 insertions, 0 deletions

diff --git a/llvm/lib/Fuzzer/FuzzerCrossOver.cpp b/llvm/lib/Fuzzer/FuzzerCrossOver.cpp
new file mode 100644
index 00000000000..87ad555d314
--- /dev/null
+++ b/llvm/lib/Fuzzer/FuzzerCrossOver.cpp
@@ -0,0 +1,46 @@
+//===- FuzzerCrossOver.cpp - Cross over two test inputs -------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Cross over test inputs.
+//===----------------------------------------------------------------------===//
+
+#include "FuzzerInternal.h"
+
+namespace fuzzer {
+
+// Cross A and B, store the result (ap to MaxLen bytes) in U.
+void CrossOver(const Unit &A, const Unit &B, Unit *U, size_t MaxLen) {
+  size_t Size = rand() % MaxLen + 1;
+  U->clear();
+  const Unit *V = &A;
+  size_t PosA = 0;
+  size_t PosB = 0;
+  size_t *Pos = &PosA;
+  while (U->size() < Size && (PosA < A.size() || PosB < B.size())) {
+    // Merge a part of V into U.
+    size_t SizeLeftU = Size - U->size();
+    if (*Pos < V->size()) {
+      size_t SizeLeftV = V->size() - *Pos;
+      size_t MaxExtraSize = std::min(SizeLeftU, SizeLeftV);
+      size_t ExtraSize = rand() % MaxExtraSize + 1;
+      U->insert(U->end(), V->begin() + *Pos, V->begin() + *Pos + ExtraSize);
+      (*Pos) += ExtraSize;
+    }
+
+    // Use the other Unit on the next iteration.
+    if (Pos == &PosA) {
+      Pos = &PosB;
+      V = &B;
+    } else {
+      Pos = &PosA;
+      V = &A;
+    }
+  }
+}
+
+}  // namespace fuzzer