pkg/corpus: upgrade corpus minimization algorithm

2 files changed, 25 insertions, 1 deletions

diff --git a/pkg/corpus/fenwik.go b/pkg/corpus/fenwik.go
index 3a49219ac..dd6bfdbef 100644
--- a/pkg/corpus/fenwik.go
+++ b/pkg/corpus/fenwik.go
@@ -43,6 +43,11 @@ func (t *fenwikTree) prefixSumTo(ind int) (sum int64) {
 	return
 }
 
+func (t *fenwikTree) reserve(cap int) {
+	t.capacity = cap
+	t.extendAndRebuild()
+}
+
 func (t *fenwikTree) extendAndRebuild() {
 	if t.capacity == 0 {
 		t.capacity = 16
diff --git a/pkg/corpus/minimize.go b/pkg/corpus/minimize.go
index d01e06f57..d3d68ee27 100644
--- a/pkg/corpus/minimize.go
+++ b/pkg/corpus/minimize.go
@@ -41,11 +41,30 @@ func (corpus *Corpus) Minimize(cover bool) {
 
 	// Overwrite the program lists.
 	corpus.ProgramsList = &ProgramsList{}
+	corpus.ProgramsList.prios.reserve(len(inputs))
 	for _, area := range corpus.focusAreas {
 		area.ProgramsList = &ProgramsList{}
 	}
-	for _, ctx := range signal.Minimize(inputs) {
+	progs := signal.Minimize(inputs)
+
+	sort.SliceStable(progs, func(i, j int) bool {
+		first := progs[i].(*Item)
+		second := progs[j].(*Item)
+		return first.ExecLast > second.ExecLast
+	})
+
+	inputs = make([]signal.Context, 0, len(progs))
+	for _, inp := range progs {
+		inputs = append(inputs, signal.Context{
+			Signal:  inp.(*Item).StableSignal,
+			Context: inp,
+		})
+	}
+	progs = signal.Minimize(inputs)
+
+	for _, ctx := range progs {
 		inp := ctx.(*Item)
+
 		corpus.progsMap[inp.Sig] = inp
 		corpus.saveProgram(inp.Prog, inp.Signal)
 		for area := range inp.areas {