1 files changed, 217 insertions, 0 deletions
diff --git a/vendor/github.com/google/gopacket/bytediff/bytediff.go b/vendor/github.com/google/gopacket/bytediff/bytediff.go
new file mode 100644
index 0000000..63addd9
--- /dev/null
+++ b/vendor/github.com/google/gopacket/bytediff/bytediff.go
@@ -0,0 +1,217 @@
+// Copyright 2012 Google, Inc. All rights reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the LICENSE file in the root of the source
+// tree.
+
+// Package bytediff provides a simple diff utility for looking at differences in byte
+// slices.  It's slow, clunky, and not particularly good by any measure, but
+// it does provide very useful visualizations for diffs between small byte
+// slices.
+//
+// Our diff algorithm uses a dynamic programming implementation of longest common
+// substring to find matching parts of slices, then recursively calls itself on
+// the prefix/suffix of that matching part for each packet.  This is a Bad Idea
+// (tm) for normal (especially large) input, but for packets where large portions
+// repeat frequently and we expect minor changes between results, it's actually
+// quite useful.
+package bytediff
+
+import (
+	"bytes"
+	"fmt"
+)
+
+// OutputFormat tells a Differences.String call how to format the set of
+// differences into a human-readable string.  Its internals are currently
+// unexported because we may want to change them drastically in the future.  For
+// the moment, please just use one of the provided OutputFormats that comes with
+// this library.
+type OutputFormat struct {
+	start, finish, add, remove, change, reset string
+}
+
+var (
+	// BashOutput uses bash escape sequences to color output.
+	BashOutput = &OutputFormat{
+		reset:  "\033[0m",
+		remove: "\033[32m",
+		add:    "\033[31m",
+		change: "\033[33m",
+	}
+	// HTMLOutput uses a <pre> to wrap output, and <span>s to color it.
+	// HTMLOutput is pretty experimental, so use at your own risk ;)
+	HTMLOutput = &OutputFormat{
+		start:  "<pre>",
+		finish: "</pre>",
+		reset:  "</span>",
+		remove: "<span style='color:red'>",
+		add:    "<span style='color:green'>",
+		change: "<span style='color:yellow'>",
+	}
+)
+
+// longestCommonSubstring uses a O(MN) dynamic programming approach to find the
+// longest common substring in a set of slices.  It returns the index in each
+// slice at which the substring begins, plus the length of the commonality.
+func longestCommonSubstring(strA, strB []byte) (indexA, indexB, length int) {
+	lenA, lenB := len(strA), len(strB)
+	if lenA == 0 || lenB == 0 {
+		return 0, 0, 0
+	}
+	arr := make([][]int, lenA)
+	for i := 0; i < lenA; i++ {
+		arr[i] = make([]int, lenB)
+	}
+	var maxLength int
+	var maxA, maxB int
+	for a := 0; a < lenA; a++ {
+		for b := 0; b < lenB; b++ {
+			if strA[a] == strB[b] {
+				length := 1
+				if a > 0 && b > 0 {
+					length = arr[a-1][b-1] + 1
+				}
+				arr[a][b] = length
+				if length > maxLength {
+					maxLength = length
+					maxA = a
+					maxB = b
+				}
+			}
+		}
+	}
+	a, b := maxA, maxB
+	for a >= 0 && b >= 0 && strA[a] == strB[b] {
+		indexA = a
+		indexB = b
+		a--
+		b--
+		length++
+	}
+	return
+}
+
+func intMax(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+// Difference represents a single part of the data being diffed, containing
+// information about both the original and new values.
+// From and To are the sets of bytes in the original and the new byte slice.
+//   !Replace        implies  From == To (no change)
+//   len(To) == 0    implies  From is being deleted
+//   len(From) == 0  implies  To is being inserted
+//   else            implies  From is being replaced by To
+type Difference struct {
+	Replace  bool
+	From, To []byte
+}
+
+// color returns the bash color for a given difference.
+func (c *OutputFormat) color(d Difference) string {
+	switch {
+	case !d.Replace:
+		return ""
+	case len(d.From) == 0:
+		return c.remove
+	case len(d.To) == 0:
+		return c.add
+	default:
+		return c.change
+	}
+}
+
+// Diff diffs strA and strB, returning a list of differences which
+// can be used to construct either the original or new string.
+//
+// Diff is optimized for comparing VERY SHORT slices.  It's meant for comparing
+// things like packets off the wire, not large files or the like.
+// As such, its runtime can be catastrophic if large inputs are passed in.
+// You've been warned.
+func Diff(strA, strB []byte) Differences {
+	if len(strA) == 0 && len(strB) == 0 {
+		return nil
+	}
+	ia, ib, l := longestCommonSubstring(strA, strB)
+	if l == 0 {
+		return Differences{
+			Difference{true, strA, strB},
+		}
+	}
+	beforeA, match, afterA := strA[:ia], strA[ia:ia+l], strA[ia+l:]
+	beforeB, afterB := strB[:ib], strB[ib+l:]
+	var diffs Differences
+	diffs = append(diffs, Diff(beforeA, beforeB)...)
+	diffs = append(diffs, Difference{false, match, match})
+	diffs = append(diffs, Diff(afterA, afterB)...)
+	return diffs
+}
+
+// Differences is a set of differences for a given diff'd pair of byte slices.
+type Differences []Difference
+
+// String outputs a previously diff'd set of strings, showing differences
+// between them, highlighted by colors.
+//
+// The output format of this function is NOT guaranteed consistent, and may be
+// changed at any time by the library authors.  It's meant solely for human
+// consumption.
+func (c *OutputFormat) String(diffs Differences) string {
+	var buf bytes.Buffer
+	count := 0
+	fmt.Fprintf(&buf, "%s", c.start)
+	fmt.Fprintf(&buf, "00000000 ")
+	for i := 0; i < len(diffs); i++ {
+		diff := diffs[i]
+		color := c.color(diff)
+		reset := ""
+		if color != "" {
+			reset = c.reset
+		}
+		fmt.Fprint(&buf, color)
+		for _, b := range diff.From {
+			fmt.Fprintf(&buf, " %02x", b)
+			count++
+			switch count % 16 {
+			case 0:
+				fmt.Fprintf(&buf, "%v\n%08x%v ", reset, count, color)
+			case 8:
+				fmt.Fprintf(&buf, " ")
+			}
+		}
+		fmt.Fprint(&buf, reset)
+	}
+	fmt.Fprintf(&buf, "\n\n00000000 ")
+	count = 0
+	for i := 0; i < len(diffs); i++ {
+		diff := diffs[i]
+		str := diff.From
+		if diff.Replace {
+			str = diff.To
+		}
+		color := c.color(diff)
+		reset := ""
+		if color != "" {
+			reset = c.reset
+		}
+		fmt.Fprint(&buf, color)
+		for _, b := range str {
+			fmt.Fprintf(&buf, " %02x", b)
+			count++
+			switch count % 16 {
+			case 0:
+				fmt.Fprintf(&buf, "%v\n%08x%v ", reset, count, color)
+			case 8:
+				fmt.Fprintf(&buf, " ")
+			}
+		}
+		fmt.Fprint(&buf, reset)
+	}
+	fmt.Fprint(&buf, "\n")
+	fmt.Fprintf(&buf, "%s", c.finish)
+	return string(buf.Bytes())
+}