1 //===- FuzzerMutate.cpp - Mutate a test input -----------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 // Mutate a test input.
9 //===----------------------------------------------------------------------===//
10 
11 #include "FuzzerDefs.h"
12 #include "FuzzerExtFunctions.h"
13 #include "FuzzerIO.h"
14 #include "FuzzerMutate.h"
15 #include "FuzzerOptions.h"
16 #include "FuzzerTracePC.h"
17 
18 namespace fuzzer {
19 
20 const size_t Dictionary::kMaxDictSize;
21 static const size_t kMaxMutationsToPrint = 10;
22 
23 static void PrintASCII(const Word &W, const char *PrintAfter) {
24   PrintASCII(W.data(), W.size(), PrintAfter);
25 }
26 
27 MutationDispatcher::MutationDispatcher(Random &Rand,
28                                        const FuzzingOptions &Options)
29     : Rand(Rand), Options(Options) {
30   DefaultMutators.insert(
31       DefaultMutators.begin(),
32       {
33           {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"},
34           {&MutationDispatcher::Mutate_InsertByte, "InsertByte"},
35           {&MutationDispatcher::Mutate_InsertRepeatedBytes,
36            "InsertRepeatedBytes"},
37           {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"},
38           {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"},
39           {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"},
40           {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"},
41           {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"},
42           {&MutationDispatcher::Mutate_CopyPart, "CopyPart"},
43           {&MutationDispatcher::Mutate_CrossOver, "CrossOver"},
44           {&MutationDispatcher::Mutate_AddWordFromManualDictionary,
45            "ManualDict"},
46           {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary,
47            "PersAutoDict"},
48       });
49   if(Options.UseCmp)
50     DefaultMutators.push_back(
51         {&MutationDispatcher::Mutate_AddWordFromTORC, "CMP"});
52 
53   if (EF->LLVMFuzzerCustomMutator)
54     Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"});
55   else
56     Mutators = DefaultMutators;
57 
58   if (EF->LLVMFuzzerCustomCrossOver)
59     Mutators.push_back(
60         {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"});
61 }
62 
63 static char RandCh(Random &Rand) {
64   if (Rand.RandBool())
65     return static_cast<char>(Rand(256));
66   const char Special[] = "!*'();:@&=+$,/?%#[]012Az-`~.\xff\x00";
67   return Special[Rand(sizeof(Special) - 1)];
68 }
69 
70 size_t MutationDispatcher::Mutate_Custom(uint8_t *Data, size_t Size,
71                                          size_t MaxSize) {
72   if (EF->__msan_unpoison)
73     EF->__msan_unpoison(Data, Size);
74   if (EF->__msan_unpoison_param)
75     EF->__msan_unpoison_param(4);
76   return EF->LLVMFuzzerCustomMutator(Data, Size, MaxSize,
77                                      Rand.Rand<unsigned int>());
78 }
79 
80 size_t MutationDispatcher::Mutate_CustomCrossOver(uint8_t *Data, size_t Size,
81                                                   size_t MaxSize) {
82   if (Size == 0)
83     return 0;
84   if (!CrossOverWith) return 0;
85   const Unit &Other = *CrossOverWith;
86   if (Other.empty())
87     return 0;
88   CustomCrossOverInPlaceHere.resize(MaxSize);
89   auto &U = CustomCrossOverInPlaceHere;
90 
91   if (EF->__msan_unpoison) {
92     EF->__msan_unpoison(Data, Size);
93     EF->__msan_unpoison(Other.data(), Other.size());
94     EF->__msan_unpoison(U.data(), U.size());
95   }
96   if (EF->__msan_unpoison_param)
97     EF->__msan_unpoison_param(7);
98   size_t NewSize = EF->LLVMFuzzerCustomCrossOver(
99       Data, Size, Other.data(), Other.size(), U.data(), U.size(),
100       Rand.Rand<unsigned int>());
101 
102   if (!NewSize)
103     return 0;
104   assert(NewSize <= MaxSize && "CustomCrossOver returned overisized unit");
105   memcpy(Data, U.data(), NewSize);
106   return NewSize;
107 }
108 
109 size_t MutationDispatcher::Mutate_ShuffleBytes(uint8_t *Data, size_t Size,
110                                                size_t MaxSize) {
111   if (Size > MaxSize || Size == 0) return 0;
112   size_t ShuffleAmount =
113       Rand(std::min(Size, (size_t)8)) + 1; // [1,8] and <= Size.
114   size_t ShuffleStart = Rand(Size - ShuffleAmount);
115   assert(ShuffleStart + ShuffleAmount <= Size);
116   std::shuffle(Data + ShuffleStart, Data + ShuffleStart + ShuffleAmount, Rand);
117   return Size;
118 }
119 
120 size_t MutationDispatcher::Mutate_EraseBytes(uint8_t *Data, size_t Size,
121                                              size_t MaxSize) {
122   if (Size <= 1) return 0;
123   size_t N = Rand(Size / 2) + 1;
124   assert(N < Size);
125   size_t Idx = Rand(Size - N + 1);
126   // Erase Data[Idx:Idx+N].
127   memmove(Data + Idx, Data + Idx + N, Size - Idx - N);
128   // Printf("Erase: %zd %zd => %zd; Idx %zd\n", N, Size, Size - N, Idx);
129   return Size - N;
130 }
131 
132 size_t MutationDispatcher::Mutate_InsertByte(uint8_t *Data, size_t Size,
133                                              size_t MaxSize) {
134   if (Size >= MaxSize) return 0;
135   size_t Idx = Rand(Size + 1);
136   // Insert new value at Data[Idx].
137   memmove(Data + Idx + 1, Data + Idx, Size - Idx);
138   Data[Idx] = RandCh(Rand);
139   return Size + 1;
140 }
141 
142 size_t MutationDispatcher::Mutate_InsertRepeatedBytes(uint8_t *Data,
143                                                       size_t Size,
144                                                       size_t MaxSize) {
145   const size_t kMinBytesToInsert = 3;
146   if (Size + kMinBytesToInsert >= MaxSize) return 0;
147   size_t MaxBytesToInsert = std::min(MaxSize - Size, (size_t)128);
148   size_t N = Rand(MaxBytesToInsert - kMinBytesToInsert + 1) + kMinBytesToInsert;
149   assert(Size + N <= MaxSize && N);
150   size_t Idx = Rand(Size + 1);
151   // Insert new values at Data[Idx].
152   memmove(Data + Idx + N, Data + Idx, Size - Idx);
153   // Give preference to 0x00 and 0xff.
154   uint8_t Byte = static_cast<uint8_t>(
155       Rand.RandBool() ? Rand(256) : (Rand.RandBool() ? 0 : 255));
156   for (size_t i = 0; i < N; i++)
157     Data[Idx + i] = Byte;
158   return Size + N;
159 }
160 
161 size_t MutationDispatcher::Mutate_ChangeByte(uint8_t *Data, size_t Size,
162                                              size_t MaxSize) {
163   if (Size > MaxSize) return 0;
164   size_t Idx = Rand(Size);
165   Data[Idx] = RandCh(Rand);
166   return Size;
167 }
168 
169 size_t MutationDispatcher::Mutate_ChangeBit(uint8_t *Data, size_t Size,
170                                             size_t MaxSize) {
171   if (Size > MaxSize) return 0;
172   size_t Idx = Rand(Size);
173   Data[Idx] ^= 1 << Rand(8);
174   return Size;
175 }
176 
177 size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data,
178                                                               size_t Size,
179                                                               size_t MaxSize) {
180   return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize);
181 }
182 
183 size_t MutationDispatcher::ApplyDictionaryEntry(uint8_t *Data, size_t Size,
184                                                 size_t MaxSize,
185                                                 DictionaryEntry &DE) {
186   const Word &W = DE.GetW();
187   bool UsePositionHint = DE.HasPositionHint() &&
188                          DE.GetPositionHint() + W.size() < Size &&
189                          Rand.RandBool();
190   if (Rand.RandBool()) {  // Insert W.
191     if (Size + W.size() > MaxSize) return 0;
192     size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1);
193     memmove(Data + Idx + W.size(), Data + Idx, Size - Idx);
194     memcpy(Data + Idx, W.data(), W.size());
195     Size += W.size();
196   } else {  // Overwrite some bytes with W.
197     if (W.size() > Size) return 0;
198     size_t Idx = UsePositionHint ? DE.GetPositionHint() : Rand(Size - W.size());
199     memcpy(Data + Idx, W.data(), W.size());
200   }
201   return Size;
202 }
203 
204 // Somewhere in the past we have observed a comparison instructions
205 // with arguments Arg1 Arg2. This function tries to guess a dictionary
206 // entry that will satisfy that comparison.
207 // It first tries to find one of the arguments (possibly swapped) in the
208 // input and if it succeeds it creates a DE with a position hint.
209 // Otherwise it creates a DE with one of the arguments w/o a position hint.
210 DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
211     const void *Arg1, const void *Arg2,
212     const void *Arg1Mutation, const void *Arg2Mutation,
213     size_t ArgSize, const uint8_t *Data,
214     size_t Size) {
215   bool HandleFirst = Rand.RandBool();
216   const void *ExistingBytes, *DesiredBytes;
217   Word W;
218   const uint8_t *End = Data + Size;
219   for (int Arg = 0; Arg < 2; Arg++) {
220     ExistingBytes = HandleFirst ? Arg1 : Arg2;
221     DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation;
222     HandleFirst = !HandleFirst;
223     W.Set(reinterpret_cast<const uint8_t*>(DesiredBytes), ArgSize);
224     const size_t kMaxNumPositions = 8;
225     size_t Positions[kMaxNumPositions];
226     size_t NumPositions = 0;
227     for (const uint8_t *Cur = Data;
228          Cur < End && NumPositions < kMaxNumPositions; Cur++) {
229       Cur =
230           (const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize);
231       if (!Cur) break;
232       Positions[NumPositions++] = Cur - Data;
233     }
234     if (!NumPositions) continue;
235     return DictionaryEntry(W, Positions[Rand(NumPositions)]);
236   }
237   DictionaryEntry DE(W);
238   return DE;
239 }
240 
241 
242 template <class T>
243 DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
244     T Arg1, T Arg2, const uint8_t *Data, size_t Size) {
245   if (Rand.RandBool()) Arg1 = Bswap(Arg1);
246   if (Rand.RandBool()) Arg2 = Bswap(Arg2);
247   T Arg1Mutation = static_cast<T>(Arg1 + Rand(-1, 1));
248   T Arg2Mutation = static_cast<T>(Arg2 + Rand(-1, 1));
249   return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation,
250                                     sizeof(Arg1), Data, Size);
251 }
252 
253 DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
254     const Word &Arg1, const Word &Arg2, const uint8_t *Data, size_t Size) {
255   return MakeDictionaryEntryFromCMP(Arg1.data(), Arg2.data(), Arg1.data(),
256                                     Arg2.data(), Arg1.size(), Data, Size);
257 }
258 
259 size_t MutationDispatcher::Mutate_AddWordFromTORC(
260     uint8_t *Data, size_t Size, size_t MaxSize) {
261   Word W;
262   DictionaryEntry DE;
263   switch (Rand(4)) {
264   case 0: {
265     auto X = TPC.TORC8.Get(Rand.Rand<size_t>());
266     DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size);
267   } break;
268   case 1: {
269     auto X = TPC.TORC4.Get(Rand.Rand<size_t>());
270     if ((X.A >> 16) == 0 && (X.B >> 16) == 0 && Rand.RandBool())
271       DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, Size);
272     else
273       DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size);
274   } break;
275   case 2: {
276     auto X = TPC.TORCW.Get(Rand.Rand<size_t>());
277     DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size);
278   } break;
279   case 3: if (Options.UseMemmem) {
280       auto X = TPC.MMT.Get(Rand.Rand<size_t>());
281       DE = DictionaryEntry(X);
282   } break;
283   default:
284     assert(0);
285   }
286   if (!DE.GetW().size()) return 0;
287   Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE);
288   if (!Size) return 0;
289   DictionaryEntry &DERef =
290       CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ %
291                                 kCmpDictionaryEntriesDequeSize];
292   DERef = DE;
293   CurrentDictionaryEntrySequence.push_back(&DERef);
294   return Size;
295 }
296 
297 size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary(
298     uint8_t *Data, size_t Size, size_t MaxSize) {
299   return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize);
300 }
301 
302 size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data,
303                                                  size_t Size, size_t MaxSize) {
304   if (Size > MaxSize) return 0;
305   if (D.empty()) return 0;
306   DictionaryEntry &DE = D[Rand(D.size())];
307   Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE);
308   if (!Size) return 0;
309   DE.IncUseCount();
310   CurrentDictionaryEntrySequence.push_back(&DE);
311   return Size;
312 }
313 
314 // Overwrites part of To[0,ToSize) with a part of From[0,FromSize).
315 // Returns ToSize.
316 size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize,
317                                       uint8_t *To, size_t ToSize) {
318   // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize).
319   size_t ToBeg = Rand(ToSize);
320   size_t CopySize = Rand(ToSize - ToBeg) + 1;
321   assert(ToBeg + CopySize <= ToSize);
322   CopySize = std::min(CopySize, FromSize);
323   size_t FromBeg = Rand(FromSize - CopySize + 1);
324   assert(FromBeg + CopySize <= FromSize);
325   memmove(To + ToBeg, From + FromBeg, CopySize);
326   return ToSize;
327 }
328 
329 // Inserts part of From[0,ToSize) into To.
330 // Returns new size of To on success or 0 on failure.
331 size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize,
332                                         uint8_t *To, size_t ToSize,
333                                         size_t MaxToSize) {
334   if (ToSize >= MaxToSize) return 0;
335   size_t AvailableSpace = MaxToSize - ToSize;
336   size_t MaxCopySize = std::min(AvailableSpace, FromSize);
337   size_t CopySize = Rand(MaxCopySize) + 1;
338   size_t FromBeg = Rand(FromSize - CopySize + 1);
339   assert(FromBeg + CopySize <= FromSize);
340   size_t ToInsertPos = Rand(ToSize + 1);
341   assert(ToInsertPos + CopySize <= MaxToSize);
342   size_t TailSize = ToSize - ToInsertPos;
343   if (To == From) {
344     MutateInPlaceHere.resize(MaxToSize);
345     memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize);
346     memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
347     memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize);
348   } else {
349     memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
350     memmove(To + ToInsertPos, From + FromBeg, CopySize);
351   }
352   return ToSize + CopySize;
353 }
354 
355 size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size,
356                                            size_t MaxSize) {
357   if (Size > MaxSize || Size == 0) return 0;
358   // If Size == MaxSize, `InsertPartOf(...)` will
359   // fail so there's no point using it in this case.
360   if (Size == MaxSize || Rand.RandBool())
361     return CopyPartOf(Data, Size, Data, Size);
362   else
363     return InsertPartOf(Data, Size, Data, Size, MaxSize);
364 }
365 
366 size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size,
367                                                      size_t MaxSize) {
368   if (Size > MaxSize) return 0;
369   size_t B = Rand(Size);
370   while (B < Size && !isdigit(Data[B])) B++;
371   if (B == Size) return 0;
372   size_t E = B;
373   while (E < Size && isdigit(Data[E])) E++;
374   assert(B < E);
375   // now we have digits in [B, E).
376   // strtol and friends don't accept non-zero-teminated data, parse it manually.
377   uint64_t Val = Data[B] - '0';
378   for (size_t i = B + 1; i < E; i++)
379     Val = Val * 10 + Data[i] - '0';
380 
381   // Mutate the integer value.
382   switch(Rand(5)) {
383     case 0: Val++; break;
384     case 1: Val--; break;
385     case 2: Val /= 2; break;
386     case 3: Val *= 2; break;
387     case 4: Val = Rand(Val * Val); break;
388     default: assert(0);
389   }
390   // Just replace the bytes with the new ones, don't bother moving bytes.
391   for (size_t i = B; i < E; i++) {
392     size_t Idx = E + B - i - 1;
393     assert(Idx >= B && Idx < E);
394     Data[Idx] = (Val % 10) + '0';
395     Val /= 10;
396   }
397   return Size;
398 }
399 
400 template<class T>
401 size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) {
402   if (Size < sizeof(T)) return 0;
403   size_t Off = Rand(Size - sizeof(T) + 1);
404   assert(Off + sizeof(T) <= Size);
405   T Val;
406   if (Off < 64 && !Rand(4)) {
407     Val = static_cast<T>(Size);
408     if (Rand.RandBool())
409       Val = Bswap(Val);
410   } else {
411     memcpy(&Val, Data + Off, sizeof(Val));
412     T Add = static_cast<T>(Rand(21));
413     Add -= 10;
414     if (Rand.RandBool())
415       Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes.
416     else
417       Val = Val + Add;               // Add assuming current endiannes.
418     if (Add == 0 || Rand.RandBool()) // Maybe negate.
419       Val = -Val;
420   }
421   memcpy(Data + Off, &Val, sizeof(Val));
422   return Size;
423 }
424 
425 size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data,
426                                                       size_t Size,
427                                                       size_t MaxSize) {
428   if (Size > MaxSize) return 0;
429   switch (Rand(4)) {
430     case 3: return ChangeBinaryInteger<uint64_t>(Data, Size, Rand);
431     case 2: return ChangeBinaryInteger<uint32_t>(Data, Size, Rand);
432     case 1: return ChangeBinaryInteger<uint16_t>(Data, Size, Rand);
433     case 0: return ChangeBinaryInteger<uint8_t>(Data, Size, Rand);
434     default: assert(0);
435   }
436   return 0;
437 }
438 
439 size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size,
440                                             size_t MaxSize) {
441   if (Size > MaxSize) return 0;
442   if (Size == 0) return 0;
443   if (!CrossOverWith) return 0;
444   const Unit &O = *CrossOverWith;
445   if (O.empty()) return 0;
446   size_t NewSize = 0;
447   switch(Rand(3)) {
448     case 0:
449       MutateInPlaceHere.resize(MaxSize);
450       NewSize = CrossOver(Data, Size, O.data(), O.size(),
451                           MutateInPlaceHere.data(), MaxSize);
452       memcpy(Data, MutateInPlaceHere.data(), NewSize);
453       break;
454     case 1:
455       NewSize = InsertPartOf(O.data(), O.size(), Data, Size, MaxSize);
456       if (!NewSize)
457         NewSize = CopyPartOf(O.data(), O.size(), Data, Size);
458       break;
459     case 2:
460       NewSize = CopyPartOf(O.data(), O.size(), Data, Size);
461       break;
462     default: assert(0);
463   }
464   assert(NewSize > 0 && "CrossOver returned empty unit");
465   assert(NewSize <= MaxSize && "CrossOver returned overisized unit");
466   return NewSize;
467 }
468 
469 void MutationDispatcher::StartMutationSequence() {
470   CurrentMutatorSequence.clear();
471   CurrentDictionaryEntrySequence.clear();
472 }
473 
474 // Copy successful dictionary entries to PersistentAutoDictionary.
475 void MutationDispatcher::RecordSuccessfulMutationSequence() {
476   for (auto DE : CurrentDictionaryEntrySequence) {
477     // PersistentAutoDictionary.AddWithSuccessCountOne(DE);
478     DE->IncSuccessCount();
479     assert(DE->GetW().size());
480     // Linear search is fine here as this happens seldom.
481     if (!PersistentAutoDictionary.ContainsWord(DE->GetW()))
482       PersistentAutoDictionary.push_back({DE->GetW(), 1});
483   }
484 }
485 
486 void MutationDispatcher::PrintRecommendedDictionary() {
487   Vector<DictionaryEntry> V;
488   for (auto &DE : PersistentAutoDictionary)
489     if (!ManualDictionary.ContainsWord(DE.GetW()))
490       V.push_back(DE);
491   if (V.empty()) return;
492   Printf("###### Recommended dictionary. ######\n");
493   for (auto &DE: V) {
494     assert(DE.GetW().size());
495     Printf("\"");
496     PrintASCII(DE.GetW(), "\"");
497     Printf(" # Uses: %zd\n", DE.GetUseCount());
498   }
499   Printf("###### End of recommended dictionary. ######\n");
500 }
501 
502 void MutationDispatcher::PrintMutationSequence(bool Verbose) {
503   Printf("MS: %zd ", CurrentMutatorSequence.size());
504   size_t EntriesToPrint =
505       Verbose ? CurrentMutatorSequence.size()
506               : std::min(kMaxMutationsToPrint, CurrentMutatorSequence.size());
507   for (size_t i = 0; i < EntriesToPrint; i++)
508     Printf("%s-", CurrentMutatorSequence[i].Name);
509   if (!CurrentDictionaryEntrySequence.empty()) {
510     Printf(" DE: ");
511     EntriesToPrint = Verbose ? CurrentDictionaryEntrySequence.size()
512                              : std::min(kMaxMutationsToPrint,
513                                         CurrentDictionaryEntrySequence.size());
514     for (size_t i = 0; i < EntriesToPrint; i++) {
515       Printf("\"");
516       PrintASCII(CurrentDictionaryEntrySequence[i]->GetW(), "\"-");
517     }
518   }
519 }
520 
521 std::string MutationDispatcher::MutationSequence() {
522   std::string MS;
523   for (auto M : CurrentMutatorSequence) {
524     MS += M.Name;
525     MS += "-";
526   }
527   return MS;
528 }
529 
530 size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
531   return MutateImpl(Data, Size, MaxSize, Mutators);
532 }
533 
534 size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size,
535                                          size_t MaxSize) {
536   return MutateImpl(Data, Size, MaxSize, DefaultMutators);
537 }
538 
539 // Mutates Data in place, returns new size.
540 size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
541                                       size_t MaxSize,
542                                       Vector<Mutator> &Mutators) {
543   assert(MaxSize > 0);
544   // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
545   // in which case they will return 0.
546   // Try several times before returning un-mutated data.
547   for (int Iter = 0; Iter < 100; Iter++) {
548     auto M = Mutators[Rand(Mutators.size())];
549     size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
550     if (NewSize && NewSize <= MaxSize) {
551       if (Options.OnlyASCII)
552         ToASCII(Data, NewSize);
553       CurrentMutatorSequence.push_back(M);
554       return NewSize;
555     }
556   }
557   *Data = ' ';
558   return 1;   // Fallback, should not happen frequently.
559 }
560 
561 // Mask represents the set of Data bytes that are worth mutating.
562 size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size,
563                                           size_t MaxSize,
564                                           const Vector<uint8_t> &Mask) {
565   size_t MaskedSize = std::min(Size, Mask.size());
566   // * Copy the worthy bytes into a temporary array T
567   // * Mutate T
568   // * Copy T back.
569   // This is totally unoptimized.
570   auto &T = MutateWithMaskTemp;
571   if (T.size() < Size)
572     T.resize(Size);
573   size_t OneBits = 0;
574   for (size_t I = 0; I < MaskedSize; I++)
575     if (Mask[I])
576       T[OneBits++] = Data[I];
577 
578   if (!OneBits) return 0;
579   assert(!T.empty());
580   size_t NewSize = Mutate(T.data(), OneBits, OneBits);
581   assert(NewSize <= OneBits);
582   (void)NewSize;
583   // Even if NewSize < OneBits we still use all OneBits bytes.
584   for (size_t I = 0, J = 0; I < MaskedSize; I++)
585     if (Mask[I])
586       Data[I] = T[J++];
587   return Size;
588 }
589 
590 void MutationDispatcher::AddWordToManualDictionary(const Word &W) {
591   ManualDictionary.push_back(
592       {W, std::numeric_limits<size_t>::max()});
593 }
594 
595 }  // namespace fuzzer
596