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
18namespace fuzzer {
19
20const size_t Dictionary::kMaxDictSize;
21static const size_t kMaxMutationsToPrint = 10;
22
23static void PrintASCII(const Word &W, const char *PrintAfter) {
24  PrintASCII(W.data(), W.size(), PrintAfter);
25}
26
27MutationDispatcher::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
63static 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
70size_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
80size_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
109size_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
120size_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
132size_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
142size_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
161size_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
169size_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
177size_t MutationDispatcher::Mutate_AddWordFromManualDictionary(uint8_t *Data,
178                                                              size_t Size,
179                                                              size_t MaxSize) {
180  return AddWordFromDictionary(ManualDictionary, Data, Size, MaxSize);
181}
182
183size_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 =
199        UsePositionHint ? DE.GetPositionHint() : Rand(Size + 1 - W.size());
200    memcpy(Data + Idx, W.data(), W.size());
201  }
202  return Size;
203}
204
205// Somewhere in the past we have observed a comparison instructions
206// with arguments Arg1 Arg2. This function tries to guess a dictionary
207// entry that will satisfy that comparison.
208// It first tries to find one of the arguments (possibly swapped) in the
209// input and if it succeeds it creates a DE with a position hint.
210// Otherwise it creates a DE with one of the arguments w/o a position hint.
211DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
212    const void *Arg1, const void *Arg2,
213    const void *Arg1Mutation, const void *Arg2Mutation,
214    size_t ArgSize, const uint8_t *Data,
215    size_t Size) {
216  bool HandleFirst = Rand.RandBool();
217  const void *ExistingBytes, *DesiredBytes;
218  Word W;
219  const uint8_t *End = Data + Size;
220  for (int Arg = 0; Arg < 2; Arg++) {
221    ExistingBytes = HandleFirst ? Arg1 : Arg2;
222    DesiredBytes = HandleFirst ? Arg2Mutation : Arg1Mutation;
223    HandleFirst = !HandleFirst;
224    W.Set(reinterpret_cast<const uint8_t*>(DesiredBytes), ArgSize);
225    const size_t kMaxNumPositions = 8;
226    size_t Positions[kMaxNumPositions];
227    size_t NumPositions = 0;
228    for (const uint8_t *Cur = Data;
229         Cur < End && NumPositions < kMaxNumPositions; Cur++) {
230      Cur =
231          (const uint8_t *)SearchMemory(Cur, End - Cur, ExistingBytes, ArgSize);
232      if (!Cur) break;
233      Positions[NumPositions++] = Cur - Data;
234    }
235    if (!NumPositions) continue;
236    return DictionaryEntry(W, Positions[Rand(NumPositions)]);
237  }
238  DictionaryEntry DE(W);
239  return DE;
240}
241
242
243template <class T>
244DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
245    T Arg1, T Arg2, const uint8_t *Data, size_t Size) {
246  if (Rand.RandBool()) Arg1 = Bswap(Arg1);
247  if (Rand.RandBool()) Arg2 = Bswap(Arg2);
248  T Arg1Mutation = static_cast<T>(Arg1 + Rand(-1, 1));
249  T Arg2Mutation = static_cast<T>(Arg2 + Rand(-1, 1));
250  return MakeDictionaryEntryFromCMP(&Arg1, &Arg2, &Arg1Mutation, &Arg2Mutation,
251                                    sizeof(Arg1), Data, Size);
252}
253
254DictionaryEntry MutationDispatcher::MakeDictionaryEntryFromCMP(
255    const Word &Arg1, const Word &Arg2, const uint8_t *Data, size_t Size) {
256  return MakeDictionaryEntryFromCMP(Arg1.data(), Arg2.data(), Arg1.data(),
257                                    Arg2.data(), Arg1.size(), Data, Size);
258}
259
260size_t MutationDispatcher::Mutate_AddWordFromTORC(
261    uint8_t *Data, size_t Size, size_t MaxSize) {
262  Word W;
263  DictionaryEntry DE;
264  switch (Rand(4)) {
265  case 0: {
266    auto X = TPC.TORC8.Get(Rand.Rand<size_t>());
267    DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size);
268  } break;
269  case 1: {
270    auto X = TPC.TORC4.Get(Rand.Rand<size_t>());
271    if ((X.A >> 16) == 0 && (X.B >> 16) == 0 && Rand.RandBool())
272      DE = MakeDictionaryEntryFromCMP((uint16_t)X.A, (uint16_t)X.B, Data, Size);
273    else
274      DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size);
275  } break;
276  case 2: {
277    auto X = TPC.TORCW.Get(Rand.Rand<size_t>());
278    DE = MakeDictionaryEntryFromCMP(X.A, X.B, Data, Size);
279  } break;
280  case 3: if (Options.UseMemmem) {
281      auto X = TPC.MMT.Get(Rand.Rand<size_t>());
282      DE = DictionaryEntry(X);
283  } break;
284  default:
285    assert(0);
286  }
287  if (!DE.GetW().size()) return 0;
288  Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE);
289  if (!Size) return 0;
290  DictionaryEntry &DERef =
291      CmpDictionaryEntriesDeque[CmpDictionaryEntriesDequeIdx++ %
292                                kCmpDictionaryEntriesDequeSize];
293  DERef = DE;
294  CurrentDictionaryEntrySequence.push_back(&DERef);
295  return Size;
296}
297
298size_t MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary(
299    uint8_t *Data, size_t Size, size_t MaxSize) {
300  return AddWordFromDictionary(PersistentAutoDictionary, Data, Size, MaxSize);
301}
302
303size_t MutationDispatcher::AddWordFromDictionary(Dictionary &D, uint8_t *Data,
304                                                 size_t Size, size_t MaxSize) {
305  if (Size > MaxSize) return 0;
306  if (D.empty()) return 0;
307  DictionaryEntry &DE = D[Rand(D.size())];
308  Size = ApplyDictionaryEntry(Data, Size, MaxSize, DE);
309  if (!Size) return 0;
310  DE.IncUseCount();
311  CurrentDictionaryEntrySequence.push_back(&DE);
312  return Size;
313}
314
315// Overwrites part of To[0,ToSize) with a part of From[0,FromSize).
316// Returns ToSize.
317size_t MutationDispatcher::CopyPartOf(const uint8_t *From, size_t FromSize,
318                                      uint8_t *To, size_t ToSize) {
319  // Copy From[FromBeg, FromBeg + CopySize) into To[ToBeg, ToBeg + CopySize).
320  size_t ToBeg = Rand(ToSize);
321  size_t CopySize = Rand(ToSize - ToBeg) + 1;
322  assert(ToBeg + CopySize <= ToSize);
323  CopySize = std::min(CopySize, FromSize);
324  size_t FromBeg = Rand(FromSize - CopySize + 1);
325  assert(FromBeg + CopySize <= FromSize);
326  memmove(To + ToBeg, From + FromBeg, CopySize);
327  return ToSize;
328}
329
330// Inserts part of From[0,ToSize) into To.
331// Returns new size of To on success or 0 on failure.
332size_t MutationDispatcher::InsertPartOf(const uint8_t *From, size_t FromSize,
333                                        uint8_t *To, size_t ToSize,
334                                        size_t MaxToSize) {
335  if (ToSize >= MaxToSize) return 0;
336  size_t AvailableSpace = MaxToSize - ToSize;
337  size_t MaxCopySize = std::min(AvailableSpace, FromSize);
338  size_t CopySize = Rand(MaxCopySize) + 1;
339  size_t FromBeg = Rand(FromSize - CopySize + 1);
340  assert(FromBeg + CopySize <= FromSize);
341  size_t ToInsertPos = Rand(ToSize + 1);
342  assert(ToInsertPos + CopySize <= MaxToSize);
343  size_t TailSize = ToSize - ToInsertPos;
344  if (To == From) {
345    MutateInPlaceHere.resize(MaxToSize);
346    memcpy(MutateInPlaceHere.data(), From + FromBeg, CopySize);
347    memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
348    memmove(To + ToInsertPos, MutateInPlaceHere.data(), CopySize);
349  } else {
350    memmove(To + ToInsertPos + CopySize, To + ToInsertPos, TailSize);
351    memmove(To + ToInsertPos, From + FromBeg, CopySize);
352  }
353  return ToSize + CopySize;
354}
355
356size_t MutationDispatcher::Mutate_CopyPart(uint8_t *Data, size_t Size,
357                                           size_t MaxSize) {
358  if (Size > MaxSize || Size == 0) return 0;
359  // If Size == MaxSize, `InsertPartOf(...)` will
360  // fail so there's no point using it in this case.
361  if (Size == MaxSize || Rand.RandBool())
362    return CopyPartOf(Data, Size, Data, Size);
363  else
364    return InsertPartOf(Data, Size, Data, Size, MaxSize);
365}
366
367size_t MutationDispatcher::Mutate_ChangeASCIIInteger(uint8_t *Data, size_t Size,
368                                                     size_t MaxSize) {
369  if (Size > MaxSize) return 0;
370  size_t B = Rand(Size);
371  while (B < Size && !isdigit(Data[B])) B++;
372  if (B == Size) return 0;
373  size_t E = B;
374  while (E < Size && isdigit(Data[E])) E++;
375  assert(B < E);
376  // now we have digits in [B, E).
377  // strtol and friends don't accept non-zero-teminated data, parse it manually.
378  uint64_t Val = Data[B] - '0';
379  for (size_t i = B + 1; i < E; i++)
380    Val = Val * 10 + Data[i] - '0';
381
382  // Mutate the integer value.
383  switch(Rand(5)) {
384    case 0: Val++; break;
385    case 1: Val--; break;
386    case 2: Val /= 2; break;
387    case 3: Val *= 2; break;
388    case 4: Val = Rand(Val * Val); break;
389    default: assert(0);
390  }
391  // Just replace the bytes with the new ones, don't bother moving bytes.
392  for (size_t i = B; i < E; i++) {
393    size_t Idx = E + B - i - 1;
394    assert(Idx >= B && Idx < E);
395    Data[Idx] = (Val % 10) + '0';
396    Val /= 10;
397  }
398  return Size;
399}
400
401template<class T>
402size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) {
403  if (Size < sizeof(T)) return 0;
404  size_t Off = Rand(Size - sizeof(T) + 1);
405  assert(Off + sizeof(T) <= Size);
406  T Val;
407  if (Off < 64 && !Rand(4)) {
408    Val = static_cast<T>(Size);
409    if (Rand.RandBool())
410      Val = Bswap(Val);
411  } else {
412    memcpy(&Val, Data + Off, sizeof(Val));
413    T Add = static_cast<T>(Rand(21));
414    Add -= 10;
415    if (Rand.RandBool())
416      Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes.
417    else
418      Val = Val + Add;               // Add assuming current endiannes.
419    if (Add == 0 || Rand.RandBool()) // Maybe negate.
420      Val = -Val;
421  }
422  memcpy(Data + Off, &Val, sizeof(Val));
423  return Size;
424}
425
426size_t MutationDispatcher::Mutate_ChangeBinaryInteger(uint8_t *Data,
427                                                      size_t Size,
428                                                      size_t MaxSize) {
429  if (Size > MaxSize) return 0;
430  switch (Rand(4)) {
431    case 3: return ChangeBinaryInteger<uint64_t>(Data, Size, Rand);
432    case 2: return ChangeBinaryInteger<uint32_t>(Data, Size, Rand);
433    case 1: return ChangeBinaryInteger<uint16_t>(Data, Size, Rand);
434    case 0: return ChangeBinaryInteger<uint8_t>(Data, Size, Rand);
435    default: assert(0);
436  }
437  return 0;
438}
439
440size_t MutationDispatcher::Mutate_CrossOver(uint8_t *Data, size_t Size,
441                                            size_t MaxSize) {
442  if (Size > MaxSize) return 0;
443  if (Size == 0) return 0;
444  if (!CrossOverWith) return 0;
445  const Unit &O = *CrossOverWith;
446  if (O.empty()) return 0;
447  size_t NewSize = 0;
448  switch(Rand(3)) {
449    case 0:
450      MutateInPlaceHere.resize(MaxSize);
451      NewSize = CrossOver(Data, Size, O.data(), O.size(),
452                          MutateInPlaceHere.data(), MaxSize);
453      memcpy(Data, MutateInPlaceHere.data(), NewSize);
454      break;
455    case 1:
456      NewSize = InsertPartOf(O.data(), O.size(), Data, Size, MaxSize);
457      if (!NewSize)
458        NewSize = CopyPartOf(O.data(), O.size(), Data, Size);
459      break;
460    case 2:
461      NewSize = CopyPartOf(O.data(), O.size(), Data, Size);
462      break;
463    default: assert(0);
464  }
465  assert(NewSize > 0 && "CrossOver returned empty unit");
466  assert(NewSize <= MaxSize && "CrossOver returned overisized unit");
467  return NewSize;
468}
469
470void MutationDispatcher::StartMutationSequence() {
471  CurrentMutatorSequence.clear();
472  CurrentDictionaryEntrySequence.clear();
473}
474
475// Copy successful dictionary entries to PersistentAutoDictionary.
476void MutationDispatcher::RecordSuccessfulMutationSequence() {
477  for (auto DE : CurrentDictionaryEntrySequence) {
478    // PersistentAutoDictionary.AddWithSuccessCountOne(DE);
479    DE->IncSuccessCount();
480    assert(DE->GetW().size());
481    // Linear search is fine here as this happens seldom.
482    if (!PersistentAutoDictionary.ContainsWord(DE->GetW()))
483      PersistentAutoDictionary.push_back(*DE);
484  }
485}
486
487void MutationDispatcher::PrintRecommendedDictionary() {
488  std::vector<DictionaryEntry> V;
489  for (auto &DE : PersistentAutoDictionary)
490    if (!ManualDictionary.ContainsWord(DE.GetW()))
491      V.push_back(DE);
492  if (V.empty()) return;
493  Printf("###### Recommended dictionary. ######\n");
494  for (auto &DE: V) {
495    assert(DE.GetW().size());
496    Printf("\"");
497    PrintASCII(DE.GetW(), "\"");
498    Printf(" # Uses: %zd\n", DE.GetUseCount());
499  }
500  Printf("###### End of recommended dictionary. ######\n");
501}
502
503void MutationDispatcher::PrintMutationSequence(bool Verbose) {
504  Printf("MS: %zd ", CurrentMutatorSequence.size());
505  size_t EntriesToPrint =
506      Verbose ? CurrentMutatorSequence.size()
507              : std::min(kMaxMutationsToPrint, CurrentMutatorSequence.size());
508  for (size_t i = 0; i < EntriesToPrint; i++)
509    Printf("%s-", CurrentMutatorSequence[i].Name);
510  if (!CurrentDictionaryEntrySequence.empty()) {
511    Printf(" DE: ");
512    EntriesToPrint = Verbose ? CurrentDictionaryEntrySequence.size()
513                             : std::min(kMaxMutationsToPrint,
514                                        CurrentDictionaryEntrySequence.size());
515    for (size_t i = 0; i < EntriesToPrint; i++) {
516      Printf("\"");
517      PrintASCII(CurrentDictionaryEntrySequence[i]->GetW(), "\"-");
518    }
519  }
520}
521
522std::string MutationDispatcher::MutationSequence() {
523  std::string MS;
524  for (const auto &M : CurrentMutatorSequence) {
525    MS += M.Name;
526    MS += "-";
527  }
528  return MS;
529}
530
531size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
532  return MutateImpl(Data, Size, MaxSize, Mutators);
533}
534
535size_t MutationDispatcher::DefaultMutate(uint8_t *Data, size_t Size,
536                                         size_t MaxSize) {
537  return MutateImpl(Data, Size, MaxSize, DefaultMutators);
538}
539
540// Mutates Data in place, returns new size.
541size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
542                                      size_t MaxSize,
543                                      std::vector<Mutator> &Mutators) {
544  assert(MaxSize > 0);
545  // Some mutations may fail (e.g. can't insert more bytes if Size == MaxSize),
546  // in which case they will return 0.
547  // Try several times before returning un-mutated data.
548  for (int Iter = 0; Iter < 100; Iter++) {
549    auto M = Mutators[Rand(Mutators.size())];
550    size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
551    if (NewSize && NewSize <= MaxSize) {
552      if (Options.OnlyASCII)
553        ToASCII(Data, NewSize);
554      CurrentMutatorSequence.push_back(M);
555      return NewSize;
556    }
557  }
558  *Data = ' ';
559  return 1;   // Fallback, should not happen frequently.
560}
561
562// Mask represents the set of Data bytes that are worth mutating.
563size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size,
564                                          size_t MaxSize,
565                                          const std::vector<uint8_t> &Mask) {
566  size_t MaskedSize = std::min(Size, Mask.size());
567  // * Copy the worthy bytes into a temporary array T
568  // * Mutate T
569  // * Copy T back.
570  // This is totally unoptimized.
571  auto &T = MutateWithMaskTemp;
572  if (T.size() < Size)
573    T.resize(Size);
574  size_t OneBits = 0;
575  for (size_t I = 0; I < MaskedSize; I++)
576    if (Mask[I])
577      T[OneBits++] = Data[I];
578
579  if (!OneBits) return 0;
580  assert(!T.empty());
581  size_t NewSize = Mutate(T.data(), OneBits, OneBits);
582  assert(NewSize <= OneBits);
583  (void)NewSize;
584  // Even if NewSize < OneBits we still use all OneBits bytes.
585  for (size_t I = 0, J = 0; I < MaskedSize; I++)
586    if (Mask[I])
587      Data[I] = T[J++];
588  return Size;
589}
590
591void MutationDispatcher::AddWordToManualDictionary(const Word &W) {
592  ManualDictionary.push_back(
593      {W, std::numeric_limits<size_t>::max()});
594}
595
596}  // namespace fuzzer
597