1 files changed, 317 insertions, 0 deletions
diff --git a/src/internal/fuzz/mutator.go b/src/internal/fuzz/mutator.go
new file mode 100644
index 0000000000..9aa56782b0
--- /dev/null
+++ b/src/internal/fuzz/mutator.go
@@ -0,0 +1,317 @@
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fuzz
+
+import (
+	"encoding/binary"
+	"fmt"
+	"math"
+	"reflect"
+	"unsafe"
+)
+
+type mutator struct {
+	r       mutatorRand
+	scratch []byte // scratch slice to avoid additional allocations
+}
+
+func newMutator() *mutator {
+	return &mutator{r: newPcgRand()}
+}
+
+func (m *mutator) rand(n int) int {
+	return m.r.intn(n)
+}
+
+func (m *mutator) randByteOrder() binary.ByteOrder {
+	if m.r.bool() {
+		return binary.LittleEndian
+	}
+	return binary.BigEndian
+}
+
+// chooseLen chooses length of range mutation in range [1,n]. It gives
+// preference to shorter ranges.
+func (m *mutator) chooseLen(n int) int {
+	switch x := m.rand(100); {
+	case x < 90:
+		return m.rand(min(8, n)) + 1
+	case x < 99:
+		return m.rand(min(32, n)) + 1
+	default:
+		return m.rand(n) + 1
+	}
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}
+
+// mutate performs several mutations on the provided values.
+func (m *mutator) mutate(vals []interface{}, maxBytes int) {
+	// TODO(katiehockman): pull some of these functions into helper methods and
+	// test that each case is working as expected.
+	// TODO(katiehockman): perform more types of mutations for []byte.
+
+	// maxPerVal will represent the maximum number of bytes that each value be
+	// allowed after mutating, giving an equal amount of capacity to each line.
+	// Allow a little wiggle room for the encoding.
+	maxPerVal := maxBytes/len(vals) - 100
+
+	// Pick a random value to mutate.
+	// TODO: consider mutating more than one value at a time.
+	i := m.rand(len(vals))
+	switch v := vals[i].(type) {
+	case int:
+		vals[i] = int(m.mutateInt(int64(v), maxInt))
+	case int8:
+		vals[i] = int8(m.mutateInt(int64(v), math.MaxInt8))
+	case int16:
+		vals[i] = int16(m.mutateInt(int64(v), math.MaxInt16))
+	case int64:
+		vals[i] = m.mutateInt(v, maxInt)
+	case uint:
+		vals[i] = uint(m.mutateUInt(uint64(v), maxUint))
+	case uint16:
+		vals[i] = uint16(m.mutateUInt(uint64(v), math.MaxUint16))
+	case uint32:
+		vals[i] = uint32(m.mutateUInt(uint64(v), math.MaxUint32))
+	case uint64:
+		vals[i] = m.mutateUInt(uint64(v), maxUint)
+	case float32:
+		vals[i] = float32(m.mutateFloat(float64(v), math.MaxFloat32))
+	case float64:
+		vals[i] = m.mutateFloat(v, math.MaxFloat64)
+	case bool:
+		if m.rand(2) == 1 {
+			vals[i] = !v // 50% chance of flipping the bool
+		}
+	case rune: // int32
+		vals[i] = rune(m.mutateInt(int64(v), math.MaxInt32))
+	case byte: // uint8
+		vals[i] = byte(m.mutateUInt(uint64(v), math.MaxUint8))
+	case string:
+		if len(v) > maxPerVal {
+			panic(fmt.Sprintf("cannot mutate bytes of length %d", len(v)))
+		}
+		if cap(m.scratch) < maxPerVal {
+			m.scratch = append(make([]byte, 0, maxPerVal), v...)
+		} else {
+			m.scratch = m.scratch[:len(v)]
+			copy(m.scratch, v)
+		}
+		m.mutateBytes(&m.scratch)
+		var s string
+		shdr := (*reflect.StringHeader)(unsafe.Pointer(&s))
+		bhdr := (*reflect.SliceHeader)(unsafe.Pointer(&m.scratch))
+		shdr.Data = bhdr.Data
+		shdr.Len = bhdr.Len
+		vals[i] = s
+	case []byte:
+		if len(v) > maxPerVal {
+			panic(fmt.Sprintf("cannot mutate bytes of length %d", len(v)))
+		}
+		if cap(m.scratch) < maxPerVal {
+			m.scratch = append(make([]byte, 0, maxPerVal), v...)
+		} else {
+			m.scratch = m.scratch[:len(v)]
+			copy(m.scratch, v)
+		}
+		m.mutateBytes(&m.scratch)
+		vals[i] = m.scratch
+	default:
+		panic(fmt.Sprintf("type not supported for mutating: %T", vals[i]))
+	}
+}
+
+func (m *mutator) mutateInt(v, maxValue int64) int64 {
+	numIters := 1 + m.r.exp2()
+	var max int64
+	for iter := 0; iter < numIters; iter++ {
+		max = 100
+		switch m.rand(2) {
+		case 0:
+			// Add a random number
+			if v >= maxValue {
+				iter--
+				continue
+			}
+			if v > 0 && maxValue-v < max {
+				// Don't let v exceed maxValue
+				max = maxValue - v
+			}
+			v += int64(1 + m.rand(int(max)))
+		case 1:
+			// Subtract a random number
+			if v <= -maxValue {
+				iter--
+				continue
+			}
+			if v < 0 && maxValue+v < max {
+				// Don't let v drop below -maxValue
+				max = maxValue + v
+			}
+			v -= int64(1 + m.rand(int(max)))
+		}
+	}
+	return v
+}
+
+func (m *mutator) mutateUInt(v, maxValue uint64) uint64 {
+	numIters := 1 + m.r.exp2()
+	var max uint64
+	for iter := 0; iter < numIters; iter++ {
+		max = 100
+		switch m.rand(2) {
+		case 0:
+			// Add a random number
+			if v >= maxValue {
+				iter--
+				continue
+			}
+			if v > 0 && maxValue-v < max {
+				// Don't let v exceed maxValue
+				max = maxValue - v
+			}
+
+			v += uint64(1 + m.rand(int(max)))
+		case 1:
+			// Subtract a random number
+			if v <= 0 {
+				iter--
+				continue
+			}
+			if v < max {
+				// Don't let v drop below 0
+				max = v
+			}
+			v -= uint64(1 + m.rand(int(max)))
+		}
+	}
+	return v
+}
+
+func (m *mutator) mutateFloat(v, maxValue float64) float64 {
+	numIters := 1 + m.r.exp2()
+	var max float64
+	for iter := 0; iter < numIters; iter++ {
+		switch m.rand(4) {
+		case 0:
+			// Add a random number
+			if v >= maxValue {
+				iter--
+				continue
+			}
+			max = 100
+			if v > 0 && maxValue-v < max {
+				// Don't let v exceed maxValue
+				max = maxValue - v
+			}
+			v += float64(1 + m.rand(int(max)))
+		case 1:
+			// Subtract a random number
+			if v <= -maxValue {
+				iter--
+				continue
+			}
+			max = 100
+			if v < 0 && maxValue+v < max {
+				// Don't let v drop below -maxValue
+				max = maxValue + v
+			}
+			v -= float64(1 + m.rand(int(max)))
+		case 2:
+			// Multiply by a random number
+			absV := math.Abs(v)
+			if v == 0 || absV >= maxValue {
+				iter--
+				continue
+			}
+			max = 10
+			if maxValue/absV < max {
+				// Don't let v go beyond the minimum or maximum value
+				max = maxValue / absV
+			}
+			v *= float64(1 + m.rand(int(max)))
+		case 3:
+			// Divide by a random number
+			if v == 0 {
+				iter--
+				continue
+			}
+			v /= float64(1 + m.rand(10))
+		}
+	}
+	return v
+}
+
+type byteSliceMutator func(*mutator, []byte) []byte
+
+var byteSliceMutators = []byteSliceMutator{
+	byteSliceRemoveBytes,
+	byteSliceInsertRandomBytes,
+	byteSliceDuplicateBytes,
+	byteSliceOverwriteBytes,
+	byteSliceBitFlip,
+	byteSliceXORByte,
+	byteSliceSwapByte,
+	byteSliceArithmeticUint8,
+	byteSliceArithmeticUint16,
+	byteSliceArithmeticUint32,
+	byteSliceArithmeticUint64,
+	byteSliceOverwriteInterestingUint8,
+	byteSliceOverwriteInterestingUint16,
+	byteSliceOverwriteInterestingUint32,
+	byteSliceInsertConstantBytes,
+	byteSliceOverwriteConstantBytes,
+	byteSliceShuffleBytes,
+	byteSliceSwapBytes,
+}
+
+func (m *mutator) mutateBytes(ptrB *[]byte) {
+	b := *ptrB
+	defer func() {
+		oldHdr := (*reflect.SliceHeader)(unsafe.Pointer(ptrB))
+		newHdr := (*reflect.SliceHeader)(unsafe.Pointer(&b))
+		if oldHdr.Data != newHdr.Data {
+			panic("data moved to new address")
+		}
+		*ptrB = b
+	}()
+
+	numIters := 1 + m.r.exp2()
+	for iter := 0; iter < numIters; iter++ {
+		mut := byteSliceMutators[m.rand(len(byteSliceMutators))]
+		mutated := mut(m, b)
+		if mutated == nil {
+			iter--
+			continue
+		}
+		b = mutated
+	}
+}
+
+var (
+	interesting8  = []int8{-128, -1, 0, 1, 16, 32, 64, 100, 127}
+	interesting16 = []int16{-32768, -129, 128, 255, 256, 512, 1000, 1024, 4096, 32767}
+	interesting32 = []int32{-2147483648, -100663046, -32769, 32768, 65535, 65536, 100663045, 2147483647}
+)
+
+const (
+	maxUint = uint64(^uint(0))
+	maxInt  = int64(maxUint >> 1)
+)
+
+func init() {
+	for _, v := range interesting8 {
+		interesting16 = append(interesting16, int16(v))
+	}
+	for _, v := range interesting16 {
+		interesting32 = append(interesting32, int32(v))
+	}
+}