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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
// Copyright 2018 syzkaller project authors. All rights reserved.
// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
// Package signal provides types for working with feedback signal.
package signal
type (
elemType uint64
prioType int8
)
// Signal was hard to refactor when we enabled recvcheck.
type Signal map[elemType]prioType // nolint: recvcheck
func (s Signal) Len() int {
return len(s)
}
func (s Signal) Empty() bool {
return len(s) == 0
}
func (s Signal) Copy() Signal {
c := make(Signal, len(s))
for e, p := range s {
c[e] = p
}
return c
}
func FromRaw(raw []uint64, prio uint8) Signal {
if len(raw) == 0 {
return nil
}
s := make(Signal, len(raw))
for _, e := range raw {
s[elemType(e)] = prioType(prio)
}
return s
}
func (s Signal) DiffRaw(raw []uint64, prio uint8) Signal {
var res Signal
for _, e := range raw {
if p, ok := s[elemType(e)]; ok && p >= prioType(prio) {
continue
}
if res == nil {
res = make(Signal)
}
res[elemType(e)] = prioType(prio)
}
return res
}
func (s Signal) IntersectsWith(other Signal) bool {
for e, p := range s {
if p1, ok := other[e]; ok && p1 >= p {
return true
}
}
return false
}
func (s Signal) Intersection(s1 Signal) Signal {
if s1.Empty() {
return nil
}
res := make(Signal, len(s))
for e, p := range s {
if p1, ok := s1[e]; ok && p1 >= p {
res[e] = p
}
}
return res
}
func (s *Signal) Merge(s1 Signal) {
if s1.Empty() {
return
}
s0 := *s
if s0 == nil {
s0 = make(Signal, len(s1))
*s = s0
}
for e, p1 := range s1 {
if p, ok := s0[e]; !ok || p < p1 {
s0[e] = p1
}
}
}
func (s Signal) ToRaw() []uint64 {
var raw []uint64
for e := range s {
raw = append(raw, uint64(e))
}
return raw
}
type Context struct {
Signal Signal
Context any
}
func Minimize(corpus []Context) []any {
type ContextPrio struct {
prio prioType
idx int
}
covered := make(map[elemType]ContextPrio)
for i, inp := range corpus {
for e, p := range inp.Signal {
if prev, ok := covered[e]; !ok || p > prev.prio {
covered[e] = ContextPrio{
prio: p,
idx: i,
}
}
}
}
indices := make(map[int]struct{}, len(corpus))
for _, cp := range covered {
indices[cp.idx] = struct{}{}
}
result := make([]any, 0, len(indices))
for idx := range indices {
result = append(result, corpus[idx].Context)
}
return result
}
|
