// 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 import ( "sort" ) type ( elemType uint32 prioType int8 ) type Signal map[elemType]prioType type Serial struct { Elems []elemType Prios []prioType } 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 (s *Signal) Split(n int) Signal { if s.Empty() { return nil } c := make(Signal, n) for e, p := range *s { delete(*s, e) c[e] = p n-- if n == 0 { break } } if len(*s) == 0 { *s = nil } return c } func FromRaw(raw []uint32, 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) Serialize() Serial { if s.Empty() { return Serial{} } res := Serial{ Elems: make([]elemType, len(s)), Prios: make([]prioType, len(s)), } i := 0 for e, p := range s { res.Elems[i] = e res.Prios[i] = p i++ } return res } func (ser Serial) Deserialize() Signal { if len(ser.Elems) != len(ser.Prios) { panic("corrupted Serial") } if len(ser.Elems) == 0 { return nil } s := make(Signal, len(ser.Elems)) for i, e := range ser.Elems { s[e] = ser.Prios[i] } return s } func (s Signal) Diff(s1 Signal) Signal { if s1.Empty() { return nil } var res Signal for e, p1 := range s1 { if p, ok := s[e]; ok && p >= p1 { continue } if res == nil { res = make(Signal) } res[e] = p1 } return res } func (s Signal) DiffRaw(raw []uint32, 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) 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 } } } type Context struct { Signal Signal Context interface{} } func Minimize(corpus []Context) []interface{} { sort.Slice(corpus, func(i, j int) bool { return corpus[i].Signal.Len() > corpus[j].Signal.Len() }) 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([]interface{}, 0, len(indices)) for idx := range indices { result = append(result, corpus[idx].Context) } return result }