initial commit

2 files changed, 344 insertions, 0 deletions

diff --git a/cover/cover.go b/cover/cover.go
new file mode 100644
index 000000000..c55f328e6
--- /dev/null
+++ b/cover/cover.go
@@ -0,0 +1,139 @@
+// Copyright 2015 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 cover implements set operations on slices (arrays of coverage PCs). */
+package cover
+
+import (
+	"sort"
+)
+
+type Cover []uint32
+
+func (a Cover) Len() int           { return len(a) }
+func (a Cover) Less(i, j int) bool { return a[i] < a[j] }
+func (a Cover) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
+
+const sent = ^uint32(0)
+
+func Copy(cov Cover) Cover {
+	return append(Cover{}, cov...)
+}
+
+/* Canonicalize sorts and removes duplicates. */
+func Canonicalize(cov []uint32) Cover {
+	sort.Sort(Cover(cov))
+	i := 0
+	last := sent
+	for _, pc := range cov {
+		if pc != last {
+			last = pc
+			cov[i] = pc
+			i++
+		}
+	}
+	return Cover(cov[:i])
+}
+
+func Difference(cov0, cov1 Cover) Cover {
+	return foreach(cov0, cov1, func(v0, v1 uint32) uint32 {
+		if v0 < v1 {
+			return v0
+		}
+		return sent
+	})
+}
+
+func SymmetricDifference(cov0, cov1 Cover) Cover {
+	return foreach(cov0, cov1, func(v0, v1 uint32) uint32 {
+		if v0 < v1 {
+			return v0
+		}
+		if v1 < v0 {
+			return v1
+		}
+		return sent
+	})
+}
+
+func Union(cov0, cov1 Cover) Cover {
+	return foreach(cov0, cov1, func(v0, v1 uint32) uint32 {
+		if v0 <= v1 {
+			return v0
+		}
+		return v1
+	})
+}
+
+func Intersection(cov0, cov1 Cover) Cover {
+	return foreach(cov0, cov1, func(v0, v1 uint32) uint32 {
+		if v0 == v1 {
+			return v0
+		}
+		return sent
+	})
+}
+
+func foreach(cov0, cov1 Cover, f func(uint32, uint32) uint32) Cover {
+	var res []uint32
+	for i0, i1 := 0, 0; i0 < len(cov0) || i1 < len(cov1); {
+		v0, v1 := sent, sent
+		if i0 < len(cov0) {
+			v0 = cov0[i0]
+		}
+		if i1 < len(cov1) {
+			v1 = cov1[i1]
+		}
+		if v0 <= v1 {
+			i0++
+		}
+		if v1 <= v0 {
+			i1++
+		}
+		if v := f(v0, v1); v != sent {
+			res = append(res, v)
+		}
+	}
+	return res
+}
+
+// Minimize returns a minimal set of inputs that give the same coverage as the full corpus.
+func Minimize(corpus []Cover) []int {
+	inputs := make([]*minInput, len(corpus))
+	for i, cov := range corpus {
+		inputs[i] = &minInput{
+			idx: i,
+			cov: cov,
+		}
+	}
+	sort.Sort(minInputArray(inputs))
+	var min []int
+	covered := make(map[uint32]struct{})
+	for _, inp := range inputs {
+		hit := false
+		for _, pc := range inp.cov {
+			if !hit {
+				if _, ok := covered[pc]; !ok {
+					hit = true
+					min = append(min, inp.idx)
+				}
+			}
+			if hit {
+				covered[pc] = struct{}{}
+			}
+		}
+	}
+	return min
+}
+
+type minInput struct {
+	idx int
+	cov Cover
+}
+
+type minInputArray []*minInput
+
+// Inputs with larger coverage come first.
+func (a minInputArray) Len() int           { return len(a) }
+func (a minInputArray) Less(i, j int) bool { return len(a[i].cov) > len(a[j].cov) }
+func (a minInputArray) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
diff --git a/cover/cover_test.go b/cover/cover_test.go
new file mode 100644
index 000000000..73dc7581b
--- /dev/null
+++ b/cover/cover_test.go
@@ -0,0 +1,205 @@
+// Copyright 2015 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 cover
+
+import (
+	"math/rand"
+	"reflect"
+	"sort"
+	"testing"
+	"time"
+)
+
+func initTest(t *testing.T) (*rand.Rand, int) {
+	iters := 1000
+	if testing.Short() {
+		iters = 100
+	}
+	seed := int64(time.Now().UnixNano())
+	rs := rand.NewSource(seed)
+	t.Logf("seed=%v", seed)
+	return rand.New(rs), iters
+}
+
+type Test struct {
+	V0 Cover
+	V1 Cover
+	R  Cover
+}
+
+func runTest(t *testing.T, f func(Cover, Cover) Cover, sorted, symmetric bool, tests []Test) {
+	if symmetric {
+		for _, test := range tests {
+			tests = append(tests, Test{test.V1, test.V0, test.R})
+		}
+	}
+	tests = append(tests, Test{Cover{}, Cover{}, Cover{}})
+	for _, test := range tests {
+		if sorted {
+			if !sort.IsSorted(test.V0) {
+				t.Fatalf("input is not sorted: %+v", test.V0)
+			}
+			if !sort.IsSorted(test.V1) {
+				t.Fatalf("input is not sorted: %+v", test.V1)
+			}
+		}
+		if !sort.IsSorted(test.R) {
+			t.Fatalf("golden is not sorted: %+v", test.R)
+		}
+		res := f(test.V0, test.V1)
+		if !sort.IsSorted(res) {
+			t.Fatalf("output is not sorted: %+v", res)
+		}
+		if (len(res) != 0 || len(test.R) != 0) && !reflect.DeepEqual(res, test.R) {
+			t.Fatalf("f(%+v, %+v) = %+v (expect: %+v)", test.V0, test.V1, res, test.R)
+		}
+	}
+}
+
+func TestCanonicalize(t *testing.T) {
+	runTest(t, func(c0, c1 Cover) Cover { return Canonicalize([]uint32(c0)) }, false, false, []Test{
+		{Cover{1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 6}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
+		{Cover{6, 2, 3, 4, 5, 1}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
+		{Cover{6, 1, 2, 6, 3, 3, 4, 5, 1}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
+	})
+}
+
+func TestDifference(t *testing.T) {
+	runTest(t, Difference, true, false, []Test{
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{3}, Cover{1, 2, 4, 5, 6}},
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{1, 6}, Cover{2, 3, 4, 5}},
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{0, 10}, Cover{1, 2, 3, 4, 5, 6}},
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{0, 3, 6}, Cover{1, 2, 4, 5}},
+	})
+}
+
+func TestSymmetricDifference(t *testing.T) {
+	runTest(t, SymmetricDifference, true, true, []Test{
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{1, 2, 3, 4, 5, 6}, Cover{}},
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{2, 4, 6}, Cover{1, 3, 5}},
+		{Cover{2, 4, 6}, Cover{1, 3, 5}, Cover{1, 2, 3, 4, 5, 6}},
+	})
+}
+
+func TestUnion(t *testing.T) {
+	runTest(t, Union, true, true, []Test{
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{1, 2, 3, 4, 5, 6}, Cover{1, 2, 3, 4, 5, 6}},
+		{Cover{1, 3, 5}, Cover{2, 4, 6}, Cover{1, 2, 3, 4, 5, 6}},
+		{Cover{1, 2, 3, 5}, Cover{2, 4, 5, 6}, Cover{1, 2, 3, 4, 5, 6}},
+	})
+}
+
+func TestIntersection(t *testing.T) {
+	runTest(t, Intersection, true, true, []Test{
+		{Cover{1, 2, 3, 4, 5, 6}, Cover{}, Cover{}},
+		{Cover{1, 2, 3}, Cover{4, 5, 6}, Cover{}},
+		{Cover{1, 2, 3}, Cover{2, 3, 5}, Cover{2, 3}},
+	})
+}
+
+func TestMinimize(t *testing.T) {
+	tests := []struct {
+		inp []Cover
+		out []int
+	}{
+		// Take all.
+		{
+			[]Cover{
+				{1, 2, 3},
+				{4, 5, 6},
+				{7, 8, 9},
+			},
+			[]int{0, 1, 2},
+		},
+		// Take one.
+		{
+			[]Cover{
+				{1, 2, 3, 4, 5, 6, 7, 8, 9},
+				{1},
+				{2, 3, 4, 5},
+				{6, 7, 8},
+			},
+			[]int{0},
+		},
+		// Take two.
+		{
+			[]Cover{
+				{1, 2, 3, 4, 5, 6, 7, 8, 9},
+				{1},
+				{2, 3, 4, 5},
+				{10},
+			},
+			[]int{0, 3},
+		},
+		// Take another two.
+		{
+			[]Cover{
+				{1, 2, 3, 4},
+				{1, 2},
+				{3, 4, 5, 6, 7},
+				{3, 7},
+			},
+			[]int{2, 0},
+		},
+		// Take the largest one.
+		{
+			[]Cover{
+				{1, 2},
+				{1, 2, 3, 4, 5},
+				{3, 4, 5},
+			},
+			[]int{1},
+		},
+	}
+	for _, test := range tests {
+		res := Minimize(test.inp)
+		if !reflect.DeepEqual(res, test.out) {
+			t.Logf("corpus:")
+			for _, in := range test.inp {
+				t.Logf("  %+v", in)
+			}
+			t.Fatalf("expect: %+v, got: %+v", test.out, res)
+		}
+	}
+}
+
+func TestMinimizeRandom(t *testing.T) {
+	rnd, iters := initTest(t)
+	for i := 0; i < iters; i++ {
+		n := rnd.Intn(20)
+		cov := make([]Cover, n)
+		for i := range cov {
+			tmp := make(Cover, rnd.Intn(10))
+			for j := range tmp {
+				tmp[j] = uint32(rnd.Intn(100))
+			}
+			cov[i] = Canonicalize(tmp)
+		}
+		var total Cover
+		for _, c := range cov {
+			total = Union(total, c)
+		}
+		mini := Minimize(cov)
+		var minimized Cover
+		for _, idx := range mini {
+			minimized = Union(minimized, cov[idx])
+		}
+		t.Logf("minimized %v -> %v", len(cov), len(mini))
+		if !reflect.DeepEqual(total, minimized) {
+			t.Logf("corpus:")
+			for _, in := range cov {
+				t.Logf("  %+v", in)
+			}
+			t.Logf("minimized:")
+			for _, in := range cov {
+				t.Logf("  %+v", in)
+			}
+
+			t.Fatalf("better luck next time")
+		}
+	}
+}