Index: lib/Fuzzer/FuzzerInternal.h
===================================================================
--- lib/Fuzzer/FuzzerInternal.h
+++ lib/Fuzzer/FuzzerInternal.h
@@ -137,6 +137,22 @@
   size_t RandBool() { return Rand() % 2; }
   size_t operator()(size_t n) { return n ? Rand() % n : 0; }
   std::mt19937 &Get_mt19937() { return R; }
+  // Shuffle data in the range [First, End)
+  //
+  // We do not use std::random_shuffle() here because its
+  // behavior is not consistent across different platforms.
+  //
+  // The algorithm used here will pick a permutation at
+  // random where every permutation has equal probability
+  // (provided the random source is uniformly distributed).
+  template<typename RndAccessIt>
+  void Shuffle(RndAccessIt First, RndAccessIt End) {
+    typename std::iterator_traits<RndAccessIt>::difference_type Offset, N;
+    N = End - First;
+    for (Offset = 0; Offset < N; ++Offset) {
+      std::swap(First[Offset], First[Offset + (*this)(N - Offset)]);
+    }
+  }
  private:
   std::mt19937 R;
 };
Index: lib/Fuzzer/FuzzerLoop.cpp
===================================================================
--- lib/Fuzzer/FuzzerLoop.cpp
+++ lib/Fuzzer/FuzzerLoop.cpp
@@ -321,7 +321,7 @@
 }
 
 void Fuzzer::ShuffleCorpus(UnitVector *V) {
-  std::random_shuffle(V->begin(), V->end(), MD.GetRand());
+  MD.GetRand().Shuffle(V->begin(), V->end());
   if (Options.PreferSmall)
     std::stable_sort(V->begin(), V->end(), [](const Unit &A, const Unit &B) {
       return A.size() < B.size();
Index: lib/Fuzzer/FuzzerMutate.cpp
===================================================================
--- lib/Fuzzer/FuzzerMutate.cpp
+++ lib/Fuzzer/FuzzerMutate.cpp
@@ -96,8 +96,7 @@
       Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size.
   size_t ShuffleStart = Rand(Size - ShuffleAmount);
   assert(ShuffleStart + ShuffleAmount <= Size);
-  std::random_shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount,
-                      Rand);
+  Rand.Shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount);
   return Size;
 }
 
Index: lib/Fuzzer/test/FuzzerUnittest.cpp
===================================================================
--- lib/Fuzzer/test/FuzzerUnittest.cpp
+++ lib/Fuzzer/test/FuzzerUnittest.cpp
@@ -259,7 +259,7 @@
   TestShuffleBytes(&MutationDispatcher::Mutate_ShuffleBytes, 1 << 16);
 }
 TEST(FuzzerMutate, ShuffleBytes2) {
-  TestShuffleBytes(&MutationDispatcher::Mutate, 1 << 19);
+  TestShuffleBytes(&MutationDispatcher::Mutate, 566171);
 }
 
 void TestAddWordFromDictionary(Mutator M, int NumIter) {