1// Copyright 2018 syzkaller project authors. All rights reserved.
2// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
3
4// Package signal provides types for working with feedback signal.
5package signal
6
7import (
8	"sort"
9)
10
11type (
12	elemType uint32
13	prioType int8
14)
15
16type Signal map[elemType]prioType
17
18type Serial struct {
19	Elems []elemType
20	Prios []prioType
21}
22
23func (s Signal) Len() int {
24	return len(s)
25}
26
27func (s Signal) Empty() bool {
28	return len(s) == 0
29}
30
31func (s Signal) Copy() Signal {
32	c := make(Signal, len(s))
33	for e, p := range s {
34		c[e] = p
35	}
36	return c
37}
38
39func (s *Signal) Split(n int) Signal {
40	if s.Empty() {
41		return nil
42	}
43	c := make(Signal, n)
44	for e, p := range *s {
45		delete(*s, e)
46		c[e] = p
47		n--
48		if n == 0 {
49			break
50		}
51	}
52	if len(*s) == 0 {
53		*s = nil
54	}
55	return c
56}
57
58func FromRaw(raw []uint32, prio uint8) Signal {
59	if len(raw) == 0 {
60		return nil
61	}
62	s := make(Signal, len(raw))
63	for _, e := range raw {
64		s[elemType(e)] = prioType(prio)
65	}
66	return s
67}
68
69func (s Signal) Serialize() Serial {
70	if s.Empty() {
71		return Serial{}
72	}
73	res := Serial{
74		Elems: make([]elemType, len(s)),
75		Prios: make([]prioType, len(s)),
76	}
77	i := 0
78	for e, p := range s {
79		res.Elems[i] = e
80		res.Prios[i] = p
81		i++
82	}
83	return res
84}
85
86func (ser Serial) Deserialize() Signal {
87	if len(ser.Elems) != len(ser.Prios) {
88		panic("corrupted Serial")
89	}
90	if len(ser.Elems) == 0 {
91		return nil
92	}
93	s := make(Signal, len(ser.Elems))
94	for i, e := range ser.Elems {
95		s[e] = ser.Prios[i]
96	}
97	return s
98}
99
100func (s Signal) Diff(s1 Signal) Signal {
101	if s1.Empty() {
102		return nil
103	}
104	var res Signal
105	for e, p1 := range s1 {
106		if p, ok := s[e]; ok && p >= p1 {
107			continue
108		}
109		if res == nil {
110			res = make(Signal)
111		}
112		res[e] = p1
113	}
114	return res
115}
116
117func (s Signal) DiffRaw(raw []uint32, prio uint8) Signal {
118	var res Signal
119	for _, e := range raw {
120		if p, ok := s[elemType(e)]; ok && p >= prioType(prio) {
121			continue
122		}
123		if res == nil {
124			res = make(Signal)
125		}
126		res[elemType(e)] = prioType(prio)
127	}
128	return res
129}
130
131func (s Signal) Intersection(s1 Signal) Signal {
132	if s1.Empty() {
133		return nil
134	}
135	res := make(Signal, len(s))
136	for e, p := range s {
137		if p1, ok := s1[e]; ok && p1 >= p {
138			res[e] = p
139		}
140	}
141	return res
142}
143
144func (s *Signal) Merge(s1 Signal) {
145	if s1.Empty() {
146		return
147	}
148	s0 := *s
149	if s0 == nil {
150		s0 = make(Signal, len(s1))
151		*s = s0
152	}
153	for e, p1 := range s1 {
154		if p, ok := s0[e]; !ok || p < p1 {
155			s0[e] = p1
156		}
157	}
158}
159
160type Context struct {
161	Signal  Signal
162	Context interface{}
163}
164
165func Minimize(corpus []Context) []interface{} {
166	sort.Slice(corpus, func(i, j int) bool {
167		return corpus[i].Signal.Len() > corpus[j].Signal.Len()
168	})
169	type ContextPrio struct {
170		prio prioType
171		idx  int
172	}
173	covered := make(map[elemType]ContextPrio)
174	for i, inp := range corpus {
175		for e, p := range inp.Signal {
176			if prev, ok := covered[e]; !ok || p > prev.prio {
177				covered[e] = ContextPrio{
178					prio: p,
179					idx:  i,
180				}
181			}
182		}
183	}
184	indices := make(map[int]struct{}, len(corpus))
185	for _, cp := range covered {
186		indices[cp.idx] = struct{}{}
187	}
188	result := make([]interface{}, 0, len(indices))
189	for idx := range indices {
190		result = append(result, corpus[idx].Context)
191	}
192	return result
193}
194