1// Copyright 2021 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package fuzz
6
7import (
8	"reflect"
9)
10
11func isMinimizable(t reflect.Type) bool {
12	return t == reflect.TypeOf("") || t == reflect.TypeOf([]byte(nil))
13}
14
15func minimizeBytes(v []byte, try func([]byte) bool, shouldStop func() bool) {
16	tmp := make([]byte, len(v))
17	// If minimization was successful at any point during minimizeBytes,
18	// then the vals slice in (*workerServer).minimizeInput will point to
19	// tmp. Since tmp is altered while making new candidates, we need to
20	// make sure that it is equal to the correct value, v, before exiting
21	// this function.
22	defer copy(tmp, v)
23
24	// First, try to cut the tail.
25	for n := 1024; n != 0; n /= 2 {
26		for len(v) > n {
27			if shouldStop() {
28				return
29			}
30			candidate := v[:len(v)-n]
31			if !try(candidate) {
32				break
33			}
34			// Set v to the new value to continue iterating.
35			v = candidate
36		}
37	}
38
39	// Then, try to remove each individual byte.
40	for i := 0; i < len(v)-1; i++ {
41		if shouldStop() {
42			return
43		}
44		candidate := tmp[:len(v)-1]
45		copy(candidate[:i], v[:i])
46		copy(candidate[i:], v[i+1:])
47		if !try(candidate) {
48			continue
49		}
50		// Update v to delete the value at index i.
51		copy(v[i:], v[i+1:])
52		v = v[:len(candidate)]
53		// v[i] is now different, so decrement i to redo this iteration
54		// of the loop with the new value.
55		i--
56	}
57
58	// Then, try to remove each possible subset of bytes.
59	for i := 0; i < len(v)-1; i++ {
60		copy(tmp, v[:i])
61		for j := len(v); j > i+1; j-- {
62			if shouldStop() {
63				return
64			}
65			candidate := tmp[:len(v)-j+i]
66			copy(candidate[i:], v[j:])
67			if !try(candidate) {
68				continue
69			}
70			// Update v and reset the loop with the new length.
71			copy(v[i:], v[j:])
72			v = v[:len(candidate)]
73			j = len(v)
74		}
75	}
76
77	// Then, try to make it more simplified and human-readable by trying to replace each
78	// byte with a printable character.
79	printableChars := []byte("012789ABCXYZabcxyz !\"#$%&'()*+,.")
80	for i, b := range v {
81		if shouldStop() {
82			return
83		}
84
85		for _, pc := range printableChars {
86			v[i] = pc
87			if try(v) {
88				// Successful. Move on to the next byte in v.
89				break
90			}
91			// Unsuccessful. Revert v[i] back to original value.
92			v[i] = b
93		}
94	}
95}
96