<|start_filename|>cmd/internal/cdflags/bytes.go<|end_filename|>
// Copyright 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package cdflags

import (
	"flag"
	"fmt"
)

// Bytes is a byte size.
//
// Bytes implements flag.Value.
type Bytes int64

var si = []string{"", "k", "M", "G", "T", "P", "E", "Z", "Y"}

// String pretty-prints b using an SI prefix.
func (b Bytes) String() string {
	f := float64(b)
	for i, s := range si {
		if f < 1024 || i == len(si)-1 {
			return fmt.Sprintf("%g%s", f, s)
		}
		f /= 1024
	}
	panic("not reached")
}

// Set parses s into bytes, accepting SI prefixes.
func (b *Bytes) Set(s string) error {
	var num float64
	var unit string
	_, err := fmt.Sscanf(s, "%g%s", &num, &unit)
	if err == nil {
		for _, s := range si {
			if unit == s || unit == s+"B" || unit == s+"iB" {
				*b = Bytes(num)
				return nil
			}
			num *= 1024
		}
	}
	return fmt.Errorf("expected <num> or <num>[%s]", si)
}

// FlagBytes defines a Bytes flag and returns a pointer to the
// variable where the value of the flag will be stored.
func FlagBytes(name string, value Bytes, usage string) *Bytes {
	flag.Var(&value, name, usage)
	return &value
}

// FlagBytesVar defines a Bytes flag. The argument p points to a Bytes
// variable in which to sore the value of the flag.
func FlagBytesVar(p *Bytes, name string, value Bytes, usage string) {
	flag.Var(p, name, usage)
	*p = value
}


<|start_filename|>rabin/poly_test.go<|end_filename|>
// Copyright 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package rabin

import "testing"

func TestPolyMod(t *testing.T) {
	var p polyGF2
	for _, test := range [][3]uint64{
		{0x3e75, 0x3e75, 0x0},      // a(x) mod a(x) = 0
		{0x3e75 << 1, 0x3e75, 0x0}, // a(x)*x mod a(x) = 0
		{0x3e74, 0x3e75, 0x1},      // a(x) + 1 mod a(x) = 1
		{0x7337, 0xe39b, 0x7337},   // degree(a) < degree(b)
		// Random polynomials, checked with Wolfram Alpha.
		{0x3e75, 0x201b, 0x1e6e},
		{0xd10b, 0x35f7, 0x6d7},
		{0xe5a2, 0x8c83, 0x6921},
		{0x9a4a, 0xa8c7, 0x328d},
	} {
		a, b := newPolyGF2(test[0]), newPolyGF2(test[1])
		p.Mod(a, b)
		if p.coeff.Uint64() != test[2] {
			t.Errorf("%s mod %s = %s (%#x), want %s", a, b, &p, p.coeff.Uint64(), newPolyGF2(test[2]))
		}
	}
}


<|start_filename|>rabin/rabin_test.go<|end_filename|>
// Copyright 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package rabin

import (
	"fmt"
	"math/rand"
	"testing"
)

var testPolys = []uint64{
	0x11d,              // Degree 8 (smallest supported)
	0xbfe6b8a5bf378d83, // Degree 63 (largest supported)
}

func TestRabin(t *testing.T) {
	nTests := 100
	if testing.Short() {
		nTests = 5
	}

	for _, poly := range testPolys {
		tab := NewTable(poly, 0)
		t.Run("poly="+newPolyGF2(poly).String(), func(t *testing.T) {
			rg := rand.New(rand.NewSource(42))
			data := make([]byte, 64)
			for i := 0; i < nTests; i++ {
				rg.Read(data)
				h1 := rabinSlow(poly, data)
				h2 := New(tab)
				h2.Write(data)
				if h1 != h2.Sum64() {
					t.Errorf("want hash %#x (%s), got %#x (%s) for %x", h1, newPolyGF2(h1), h2.Sum64(), newPolyGF2(h2.Sum64()), data)
				}
			}
		})
	}
}

// rabinSlow is a slow, very literal implementation of Rabin
// fingerprinting that doesn't support streaming.
func rabinSlow(poly uint64, data []byte) uint64 {
	var mpoly polyGF2
	mpoly.coeff.SetBytes(data)
	return mpoly.Mod(&mpoly, newPolyGF2(poly)).coeff.Uint64()
}

func TestWindow(t *testing.T) {
	rg := rand.New(rand.NewSource(42))
	data := make([]byte, 1024)
	rg.Read(data)

	for _, poly := range testPolys {
		hNoWin := New(NewTable(poly, 0))
		for _, window := range []int{1, 4, 64, 65} {
			hWin := New(NewTable(poly, window))
			t.Run(fmt.Sprintf("poly=%s/window=%d", newPolyGF2(poly), window), func(t *testing.T) {
				for _, blockSize := range []int{1, 2, 5, 100} {
					hWin.Reset()
					for i := 0; i < len(data); i += blockSize {
						block := data[i:]
						if len(block) > blockSize {
							block = block[:blockSize]
						}

						hWin.Write(block)

						dataWin := data[:i+len(block)]
						if len(dataWin) > window {
							dataWin = dataWin[len(dataWin)-window:]
						}
						hNoWin.Reset()
						hNoWin.Write(dataWin)

						// Check the hash.
						if hNoWin.Sum64() != hWin.Sum64() {
							t.Errorf("want hash %#x, got %#x at byte %d with %d byte blocks", hNoWin.Sum64(), hWin.Sum64(), i, blockSize)
						}
					}
				}
			})
		}
	}
}

func BenchmarkRabin(b *testing.B) {
	rg := rand.New(rand.NewSource(42))
	data := make([]byte, 1<<20)
	rg.Read(data)
	b.SetBytes(int64(len(data)))
	h := New(NewTable(Poly64, 0))
	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		h.Reset()
		h.Write(data)
	}
}

func BenchmarkRabinWindowed64(b *testing.B) {
	const window = 64
	rg := rand.New(rand.NewSource(42))
	data := make([]byte, 1<<20)
	rg.Read(data)
	b.SetBytes(int64(len(data)))
	h := New(NewTable(Poly64, window))
	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		h.Reset()
		// Feed it smaller blocks or it will just reset and
		// hash the end.
		for j := 0; j < len(data); j += window / 2 {
			h.Write(data[j : j+window/2])
		}
	}
}
