1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
// Run fuzz tests on the package
//
// This is done with a byte heap to test and a simple reimplementation
// to check correctness against.
//
// First install go-fuzz
//
// go get -u github.com/dvyukov/go-fuzz/go-fuzz github.com/dvyukov/go-fuzz/go-fuzz-build
//
// Next build the instrumented package
//
// go-fuzz-build
//
// Finally fuzz away
//
// go-fuzz
//
// See https://github.com/dvyukov/go-fuzz for more instructions
//+build gofuzz
package deheap
import (
"fmt"
"sort"
)
// An byteHeap is a double ended heap of bytes
type byteDeheap []byte
func (h byteDeheap) Len() int { return len(h) }
func (h byteDeheap) Less(i, j int) bool { return h[i] < h[j] }
func (h byteDeheap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *byteDeheap) Push(x interface{}) {
*h = append(*h, x.(byte))
}
func (h *byteDeheap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
// sortedHeap is an inefficient reimplementation for test purposes
type sortedHeap []byte
func (h *sortedHeap) Push(x byte) {
data := *h
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
// i is the either the position of x or where it should be inserted
data = append(data, 0)
copy(data[i+1:], data[i:])
data[i] = x
*h = data
}
func (h *sortedHeap) Pop() (x byte) {
data := *h
x = data[0]
*h = data[1:]
return x
}
func (h *sortedHeap) PopMax() (x byte) {
data := *h
x = data[len(data)-1]
*h = data[:len(data)-1]
return x
}
// Fuzzer input is a string of bytes.
//
// If the byte is one of these, then the action is performed
// '<' Pop (minimum)
// '>' PopMax
// Otherwise the bytes is Pushed onto the heap
func Fuzz(data []byte) int {
h := &byteDeheap{}
Init(h)
s := sortedHeap{}
for _, c := range data {
switch c {
case '<':
if h.Len() > 0 {
got := Pop(h)
want := s.Pop()
if got != want {
panic(fmt.Sprintf("Pop: want = %d, got = %d", want, got))
}
}
case '>':
if h.Len() > 0 {
got := PopMax(h)
want := s.PopMax()
if got != want {
panic(fmt.Sprintf("PopMax: want = %d, got = %d", want, got))
}
}
default:
Push(h, c)
s.Push(c)
}
if len(s) != h.Len() {
panic("wrong length")
}
}
return 1
}
|
