build: move package sources from src/pkg to src

Preparation was in CL 134570043.
This CL contains only the effect of 'hg mv src/pkg/* src'.
For more about the move, see golang.org/s/go14nopkg.

15 files changed, 1138 insertions, 0 deletions

diff --git a/src/hash/adler32/adler32.go b/src/hash/adler32/adler32.go
new file mode 100644
index 000000000..7c80796bf
--- /dev/null
+++ b/src/hash/adler32/adler32.go
@@ -0,0 +1,78 @@
+// Copyright 2009 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 adler32 implements the Adler-32 checksum.
+//
+// It is defined in RFC 1950:
+//	Adler-32 is composed of two sums accumulated per byte: s1 is
+//	the sum of all bytes, s2 is the sum of all s1 values. Both sums
+//	are done modulo 65521. s1 is initialized to 1, s2 to zero.  The
+//	Adler-32 checksum is stored as s2*65536 + s1 in most-
+//	significant-byte first (network) order.
+package adler32
+
+import "hash"
+
+const (
+	// mod is the largest prime that is less than 65536.
+	mod = 65521
+	// nmax is the largest n such that
+	// 255 * n * (n+1) / 2 + (n+1) * (mod-1) <= 2^32-1.
+	// It is mentioned in RFC 1950 (search for "5552").
+	nmax = 5552
+)
+
+// The size of an Adler-32 checksum in bytes.
+const Size = 4
+
+// digest represents the partial evaluation of a checksum.
+// The low 16 bits are s1, the high 16 bits are s2.
+type digest uint32
+
+func (d *digest) Reset() { *d = 1 }
+
+// New returns a new hash.Hash32 computing the Adler-32 checksum.
+func New() hash.Hash32 {
+	d := new(digest)
+	d.Reset()
+	return d
+}
+
+func (d *digest) Size() int { return Size }
+
+func (d *digest) BlockSize() int { return 1 }
+
+// Add p to the running checksum d.
+func update(d digest, p []byte) digest {
+	s1, s2 := uint32(d&0xffff), uint32(d>>16)
+	for len(p) > 0 {
+		var q []byte
+		if len(p) > nmax {
+			p, q = p[:nmax], p[nmax:]
+		}
+		for _, x := range p {
+			s1 += uint32(x)
+			s2 += s1
+		}
+		s1 %= mod
+		s2 %= mod
+		p = q
+	}
+	return digest(s2<<16 | s1)
+}
+
+func (d *digest) Write(p []byte) (nn int, err error) {
+	*d = update(*d, p)
+	return len(p), nil
+}
+
+func (d *digest) Sum32() uint32 { return uint32(*d) }
+
+func (d *digest) Sum(in []byte) []byte {
+	s := uint32(*d)
+	return append(in, byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
+}
+
+// Checksum returns the Adler-32 checksum of data.
+func Checksum(data []byte) uint32 { return uint32(update(1, data)) }
diff --git a/src/hash/adler32/adler32_test.go b/src/hash/adler32/adler32_test.go
new file mode 100644
index 000000000..0e9c938d8
--- /dev/null
+++ b/src/hash/adler32/adler32_test.go
@@ -0,0 +1,105 @@
+// Copyright 2009 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 adler32
+
+import (
+	"strings"
+	"testing"
+)
+
+var golden = []struct {
+	out uint32
+	in  string
+}{
+	{0x00000001, ""},
+	{0x00620062, "a"},
+	{0x012600c4, "ab"},
+	{0x024d0127, "abc"},
+	{0x03d8018b, "abcd"},
+	{0x05c801f0, "abcde"},
+	{0x081e0256, "abcdef"},
+	{0x0adb02bd, "abcdefg"},
+	{0x0e000325, "abcdefgh"},
+	{0x118e038e, "abcdefghi"},
+	{0x158603f8, "abcdefghij"},
+	{0x3f090f02, "Discard medicine more than two years old."},
+	{0x46d81477, "He who has a shady past knows that nice guys finish last."},
+	{0x40ee0ee1, "I wouldn't marry him with a ten foot pole."},
+	{0x16661315, "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave"},
+	{0x5b2e1480, "The days of the digital watch are numbered.  -Tom Stoppard"},
+	{0x8c3c09ea, "Nepal premier won't resign."},
+	{0x45ac18fd, "For every action there is an equal and opposite government program."},
+	{0x53c61462, "His money is twice tainted: 'taint yours and 'taint mine."},
+	{0x7e511e63, "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977"},
+	{0xe4801a6a, "It's a tiny change to the code and not completely disgusting. - Bob Manchek"},
+	{0x61b507df, "size:  a.out:  bad magic"},
+	{0xb8631171, "The major problem is with sendmail.  -Mark Horton"},
+	{0x8b5e1904, "Give me a rock, paper and scissors and I will move the world.  CCFestoon"},
+	{0x7cc6102b, "If the enemy is within range, then so are you."},
+	{0x700318e7, "It's well we cannot hear the screams/That we create in others' dreams."},
+	{0x1e601747, "You remind me of a TV show, but that's all right: I watch it anyway."},
+	{0xb55b0b09, "C is as portable as Stonehedge!!"},
+	{0x39111dd0, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley"},
+	{0x91dd304f, "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction.  Lewis-Randall Rule"},
+	{0x2e5d1316, "How can you write a big system without C++?  -Paul Glick"},
+	{0xd0201df6, "'Invariant assertions' is the most elegant programming technique!  -Tom Szymanski"},
+	{0x211297c8, strings.Repeat("\xff", 5548) + "8"},
+	{0xbaa198c8, strings.Repeat("\xff", 5549) + "9"},
+	{0x553499be, strings.Repeat("\xff", 5550) + "0"},
+	{0xf0c19abe, strings.Repeat("\xff", 5551) + "1"},
+	{0x8d5c9bbe, strings.Repeat("\xff", 5552) + "2"},
+	{0x2af69cbe, strings.Repeat("\xff", 5553) + "3"},
+	{0xc9809dbe, strings.Repeat("\xff", 5554) + "4"},
+	{0x69189ebe, strings.Repeat("\xff", 5555) + "5"},
+	{0x86af0001, strings.Repeat("\x00", 1e5)},
+	{0x79660b4d, strings.Repeat("a", 1e5)},
+	{0x110588ee, strings.Repeat("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 1e4)},
+}
+
+// checksum is a slow but simple implementation of the Adler-32 checksum.
+// It is a straight port of the sample code in RFC 1950 section 9.
+func checksum(p []byte) uint32 {
+	s1, s2 := uint32(1), uint32(0)
+	for _, x := range p {
+		s1 = (s1 + uint32(x)) % mod
+		s2 = (s2 + s1) % mod
+	}
+	return s2<<16 | s1
+}
+
+func TestGolden(t *testing.T) {
+	for _, g := range golden {
+		in := g.in
+		if len(in) > 220 {
+			in = in[:100] + "..." + in[len(in)-100:]
+		}
+		p := []byte(g.in)
+		if got := checksum(p); got != g.out {
+			t.Errorf("simple implementation: checksum(%q) = 0x%x want 0x%x", in, got, g.out)
+			continue
+		}
+		if got := Checksum(p); got != g.out {
+			t.Errorf("optimized implementation: Checksum(%q) = 0x%x want 0x%x", in, got, g.out)
+			continue
+		}
+	}
+}
+
+func BenchmarkAdler32KB(b *testing.B) {
+	b.SetBytes(1024)
+	data := make([]byte, 1024)
+	for i := range data {
+		data[i] = byte(i)
+	}
+	h := New()
+	in := make([]byte, 0, h.Size())
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		h.Reset()
+		h.Write(data)
+		h.Sum(in)
+	}
+}
diff --git a/src/hash/crc32/crc32.go b/src/hash/crc32/crc32.go
new file mode 100644
index 000000000..a2a21a06f
--- /dev/null
+++ b/src/hash/crc32/crc32.go
@@ -0,0 +1,135 @@
+// Copyright 2009 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 crc32 implements the 32-bit cyclic redundancy check, or CRC-32,
+// checksum. See http://en.wikipedia.org/wiki/Cyclic_redundancy_check for
+// information.
+package crc32
+
+import (
+	"hash"
+	"sync"
+)
+
+// The size of a CRC-32 checksum in bytes.
+const Size = 4
+
+// Predefined polynomials.
+const (
+	// Far and away the most common CRC-32 polynomial.
+	// Used by ethernet (IEEE 802.3), v.42, fddi, gzip, zip, png, mpeg-2, ...
+	IEEE = 0xedb88320
+
+	// Castagnoli's polynomial, used in iSCSI.
+	// Has better error detection characteristics than IEEE.
+	// http://dx.doi.org/10.1109/26.231911
+	Castagnoli = 0x82f63b78
+
+	// Koopman's polynomial.
+	// Also has better error detection characteristics than IEEE.
+	// http://dx.doi.org/10.1109/DSN.2002.1028931
+	Koopman = 0xeb31d82e
+)
+
+// Table is a 256-word table representing the polynomial for efficient processing.
+type Table [256]uint32
+
+// castagnoliTable points to a lazily initialized Table for the Castagnoli
+// polynomial. MakeTable will always return this value when asked to make a
+// Castagnoli table so we can compare against it to find when the caller is
+// using this polynomial.
+var castagnoliTable *Table
+var castagnoliOnce sync.Once
+
+func castagnoliInit() {
+	castagnoliTable = makeTable(Castagnoli)
+}
+
+// IEEETable is the table for the IEEE polynomial.
+var IEEETable = makeTable(IEEE)
+
+// MakeTable returns the Table constructed from the specified polynomial.
+func MakeTable(poly uint32) *Table {
+	switch poly {
+	case IEEE:
+		return IEEETable
+	case Castagnoli:
+		castagnoliOnce.Do(castagnoliInit)
+		return castagnoliTable
+	}
+	return makeTable(poly)
+}
+
+// makeTable returns the Table constructed from the specified polynomial.
+func makeTable(poly uint32) *Table {
+	t := new(Table)
+	for i := 0; i < 256; i++ {
+		crc := uint32(i)
+		for j := 0; j < 8; j++ {
+			if crc&1 == 1 {
+				crc = (crc >> 1) ^ poly
+			} else {
+				crc >>= 1
+			}
+		}
+		t[i] = crc
+	}
+	return t
+}
+
+// digest represents the partial evaluation of a checksum.
+type digest struct {
+	crc uint32
+	tab *Table
+}
+
+// New creates a new hash.Hash32 computing the CRC-32 checksum
+// using the polynomial represented by the Table.
+func New(tab *Table) hash.Hash32 { return &digest{0, tab} }
+
+// NewIEEE creates a new hash.Hash32 computing the CRC-32 checksum
+// using the IEEE polynomial.
+func NewIEEE() hash.Hash32 { return New(IEEETable) }
+
+func (d *digest) Size() int { return Size }
+
+func (d *digest) BlockSize() int { return 1 }
+
+func (d *digest) Reset() { d.crc = 0 }
+
+func update(crc uint32, tab *Table, p []byte) uint32 {
+	crc = ^crc
+	for _, v := range p {
+		crc = tab[byte(crc)^v] ^ (crc >> 8)
+	}
+	return ^crc
+}
+
+// Update returns the result of adding the bytes in p to the crc.
+func Update(crc uint32, tab *Table, p []byte) uint32 {
+	if tab == castagnoliTable {
+		return updateCastagnoli(crc, p)
+	}
+	return update(crc, tab, p)
+}
+
+func (d *digest) Write(p []byte) (n int, err error) {
+	d.crc = Update(d.crc, d.tab, p)
+	return len(p), nil
+}
+
+func (d *digest) Sum32() uint32 { return d.crc }
+
+func (d *digest) Sum(in []byte) []byte {
+	s := d.Sum32()
+	return append(in, byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
+}
+
+// Checksum returns the CRC-32 checksum of data
+// using the polynomial represented by the Table.
+func Checksum(data []byte, tab *Table) uint32 { return Update(0, tab, data) }
+
+// ChecksumIEEE returns the CRC-32 checksum of data
+// using the IEEE polynomial.
+func ChecksumIEEE(data []byte) uint32 { return update(0, IEEETable, data) }
diff --git a/src/hash/crc32/crc32_amd64.s b/src/hash/crc32/crc32_amd64.s
new file mode 100644
index 000000000..30b0d0691
--- /dev/null
+++ b/src/hash/crc32/crc32_amd64.s
@@ -0,0 +1,64 @@
+// Copyright 2011 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.
+
+#include "textflag.h"
+
+// func castagnoliSSE42(crc uint32, p []byte) uint32
+TEXT ·castagnoliSSE42(SB),NOSPLIT,$0
+	MOVL crc+0(FP), AX  // CRC value
+	MOVQ p+8(FP), SI  // data pointer
+	MOVQ p_len+16(FP), CX  // len(p)
+
+	NOTL AX
+
+	/* If there's less than 8 bytes to process, we do it byte-by-byte. */
+	CMPQ CX, $8
+	JL cleanup
+
+	/* Process individual bytes until the input is 8-byte aligned. */
+startup:
+	MOVQ SI, BX
+	ANDQ $7, BX
+	JZ aligned
+
+	CRC32B (SI), AX
+	DECQ CX
+	INCQ SI
+	JMP startup
+
+aligned:
+	/* The input is now 8-byte aligned and we can process 8-byte chunks. */
+	CMPQ CX, $8
+	JL cleanup
+
+	CRC32Q (SI), AX
+	ADDQ $8, SI
+	SUBQ $8, CX
+	JMP aligned
+
+cleanup:
+	/* We may have some bytes left over that we process one at a time. */
+	CMPQ CX, $0
+	JE done
+
+	CRC32B (SI), AX
+	INCQ SI
+	DECQ CX
+	JMP cleanup
+
+done:
+	NOTL AX
+	MOVL AX, ret+32(FP)
+	RET
+
+// func haveSSE42() bool
+TEXT ·haveSSE42(SB),NOSPLIT,$0
+	XORQ AX, AX
+	INCL AX
+	CPUID
+	SHRQ $20, CX
+	ANDQ $1, CX
+	MOVB CX, ret+0(FP)
+	RET
+
diff --git a/src/hash/crc32/crc32_amd64p32.s b/src/hash/crc32/crc32_amd64p32.s
new file mode 100644
index 000000000..b6770eba3
--- /dev/null
+++ b/src/hash/crc32/crc32_amd64p32.s
@@ -0,0 +1,64 @@
+// Copyright 2011 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.
+
+#include "textflag.h"
+
+// func castagnoliSSE42(crc uint32, p []byte) uint32
+TEXT ·castagnoliSSE42(SB),NOSPLIT,$0
+	MOVL crc+0(FP), AX  // CRC value
+	MOVL p+4(FP), SI  // data pointer
+	MOVL p_len+8(FP), CX  // len(p)
+
+	NOTL AX
+
+	/* If there's less than 8 bytes to process, we do it byte-by-byte. */
+	CMPQ CX, $8
+	JL cleanup
+
+	/* Process individual bytes until the input is 8-byte aligned. */
+startup:
+	MOVQ SI, BX
+	ANDQ $7, BX
+	JZ aligned
+
+	CRC32B (SI), AX
+	DECQ CX
+	INCQ SI
+	JMP startup
+
+aligned:
+	/* The input is now 8-byte aligned and we can process 8-byte chunks. */
+	CMPQ CX, $8
+	JL cleanup
+
+	CRC32Q (SI), AX
+	ADDQ $8, SI
+	SUBQ $8, CX
+	JMP aligned
+
+cleanup:
+	/* We may have some bytes left over that we process one at a time. */
+	CMPQ CX, $0
+	JE done
+
+	CRC32B (SI), AX
+	INCQ SI
+	DECQ CX
+	JMP cleanup
+
+done:
+	NOTL AX
+	MOVL AX, ret+16(FP)
+	RET
+
+// func haveSSE42() bool
+TEXT ·haveSSE42(SB),NOSPLIT,$0
+	XORQ AX, AX
+	INCL AX
+	CPUID
+	SHRQ $20, CX
+	ANDQ $1, CX
+	MOVB CX, ret+0(FP)
+	RET
+
diff --git a/src/hash/crc32/crc32_amd64x.go b/src/hash/crc32/crc32_amd64x.go
new file mode 100644
index 000000000..b7e359930
--- /dev/null
+++ b/src/hash/crc32/crc32_amd64x.go
@@ -0,0 +1,27 @@
+// Copyright 2011 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.
+
+// +build amd64 amd64p32
+
+package crc32
+
+// This file contains the code to call the SSE 4.2 version of the Castagnoli
+// CRC.
+
+// haveSSE42 is defined in crc_amd64.s and uses CPUID to test for SSE 4.2
+// support.
+func haveSSE42() bool
+
+// castagnoliSSE42 is defined in crc_amd64.s and uses the SSE4.2 CRC32
+// instruction.
+func castagnoliSSE42(crc uint32, p []byte) uint32
+
+var sse42 = haveSSE42()
+
+func updateCastagnoli(crc uint32, p []byte) uint32 {
+	if sse42 {
+		return castagnoliSSE42(crc, p)
+	}
+	return update(crc, castagnoliTable, p)
+}
diff --git a/src/hash/crc32/crc32_generic.go b/src/hash/crc32/crc32_generic.go
new file mode 100644
index 000000000..c3fdcd685
--- /dev/null
+++ b/src/hash/crc32/crc32_generic.go
@@ -0,0 +1,14 @@
+// Copyright 2011 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.
+
+// +build 386 arm
+
+package crc32
+
+// The file contains the generic version of updateCastagnoli which just calls
+// the software implementation.
+
+func updateCastagnoli(crc uint32, p []byte) uint32 {
+	return update(crc, castagnoliTable, p)
+}
diff --git a/src/hash/crc32/crc32_test.go b/src/hash/crc32/crc32_test.go
new file mode 100644
index 000000000..75dc26e7c
--- /dev/null
+++ b/src/hash/crc32/crc32_test.go
@@ -0,0 +1,99 @@
+// Copyright 2009 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 crc32
+
+import (
+	"io"
+	"testing"
+)
+
+type test struct {
+	ieee, castagnoli uint32
+	in               string
+}
+
+var golden = []test{
+	{0x0, 0x0, ""},
+	{0xe8b7be43, 0xc1d04330, "a"},
+	{0x9e83486d, 0xe2a22936, "ab"},
+	{0x352441c2, 0x364b3fb7, "abc"},
+	{0xed82cd11, 0x92c80a31, "abcd"},
+	{0x8587d865, 0xc450d697, "abcde"},
+	{0x4b8e39ef, 0x53bceff1, "abcdef"},
+	{0x312a6aa6, 0xe627f441, "abcdefg"},
+	{0xaeef2a50, 0xa9421b7, "abcdefgh"},
+	{0x8da988af, 0x2ddc99fc, "abcdefghi"},
+	{0x3981703a, 0xe6599437, "abcdefghij"},
+	{0x6b9cdfe7, 0xb2cc01fe, "Discard medicine more than two years old."},
+	{0xc90ef73f, 0xe28207f, "He who has a shady past knows that nice guys finish last."},
+	{0xb902341f, 0xbe93f964, "I wouldn't marry him with a ten foot pole."},
+	{0x42080e8, 0x9e3be0c3, "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave"},
+	{0x154c6d11, 0xf505ef04, "The days of the digital watch are numbered.  -Tom Stoppard"},
+	{0x4c418325, 0x85d3dc82, "Nepal premier won't resign."},
+	{0x33955150, 0xc5142380, "For every action there is an equal and opposite government program."},
+	{0x26216a4b, 0x75eb77dd, "His money is twice tainted: 'taint yours and 'taint mine."},
+	{0x1abbe45e, 0x91ebe9f7, "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977"},
+	{0xc89a94f7, 0xf0b1168e, "It's a tiny change to the code and not completely disgusting. - Bob Manchek"},
+	{0xab3abe14, 0x572b74e2, "size:  a.out:  bad magic"},
+	{0xbab102b6, 0x8a58a6d5, "The major problem is with sendmail.  -Mark Horton"},
+	{0x999149d7, 0x9c426c50, "Give me a rock, paper and scissors and I will move the world.  CCFestoon"},
+	{0x6d52a33c, 0x735400a4, "If the enemy is within range, then so are you."},
+	{0x90631e8d, 0xbec49c95, "It's well we cannot hear the screams/That we create in others' dreams."},
+	{0x78309130, 0xa95a2079, "You remind me of a TV show, but that's all right: I watch it anyway."},
+	{0x7d0a377f, 0xde2e65c5, "C is as portable as Stonehedge!!"},
+	{0x8c79fd79, 0x297a88ed, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley"},
+	{0xa20b7167, 0x66ed1d8b, "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction.  Lewis-Randall Rule"},
+	{0x8e0bb443, 0xdcded527, "How can you write a big system without C++?  -Paul Glick"},
+}
+
+func TestGolden(t *testing.T) {
+	castagnoliTab := MakeTable(Castagnoli)
+
+	for _, g := range golden {
+		ieee := NewIEEE()
+		io.WriteString(ieee, g.in)
+		s := ieee.Sum32()
+		if s != g.ieee {
+			t.Errorf("IEEE(%s) = 0x%x want 0x%x", g.in, s, g.ieee)
+		}
+
+		castagnoli := New(castagnoliTab)
+		io.WriteString(castagnoli, g.in)
+		s = castagnoli.Sum32()
+		if s != g.castagnoli {
+			t.Errorf("Castagnoli(%s) = 0x%x want 0x%x", g.in, s, g.castagnoli)
+		}
+
+		if len(g.in) > 0 {
+			// The SSE4.2 implementation of this has code to deal
+			// with misaligned data so we ensure that we test that
+			// too.
+			castagnoli = New(castagnoliTab)
+			io.WriteString(castagnoli, g.in[:1])
+			io.WriteString(castagnoli, g.in[1:])
+			s = castagnoli.Sum32()
+			if s != g.castagnoli {
+				t.Errorf("Castagnoli[misaligned](%s) = 0x%x want 0x%x", g.in, s, g.castagnoli)
+			}
+		}
+	}
+}
+
+func BenchmarkCrc32KB(b *testing.B) {
+	b.SetBytes(1024)
+	data := make([]byte, 1024)
+	for i := range data {
+		data[i] = byte(i)
+	}
+	h := NewIEEE()
+	in := make([]byte, 0, h.Size())
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		h.Reset()
+		h.Write(data)
+		h.Sum(in)
+	}
+}
diff --git a/src/hash/crc64/crc64.go b/src/hash/crc64/crc64.go
new file mode 100644
index 000000000..692586798
--- /dev/null
+++ b/src/hash/crc64/crc64.go
@@ -0,0 +1,87 @@
+// Copyright 2009 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 crc64 implements the 64-bit cyclic redundancy check, or CRC-64,
+// checksum. See http://en.wikipedia.org/wiki/Cyclic_redundancy_check for
+// information.
+package crc64
+
+import "hash"
+
+// The size of a CRC-64 checksum in bytes.
+const Size = 8
+
+// Predefined polynomials.
+const (
+	// The ISO polynomial, defined in ISO 3309 and used in HDLC.
+	ISO = 0xD800000000000000
+
+	// The ECMA polynomial, defined in ECMA 182.
+	ECMA = 0xC96C5795D7870F42
+)
+
+// Table is a 256-word table representing the polynomial for efficient processing.
+type Table [256]uint64
+
+// MakeTable returns the Table constructed from the specified polynomial.
+func MakeTable(poly uint64) *Table {
+	t := new(Table)
+	for i := 0; i < 256; i++ {
+		crc := uint64(i)
+		for j := 0; j < 8; j++ {
+			if crc&1 == 1 {
+				crc = (crc >> 1) ^ poly
+			} else {
+				crc >>= 1
+			}
+		}
+		t[i] = crc
+	}
+	return t
+}
+
+// digest represents the partial evaluation of a checksum.
+type digest struct {
+	crc uint64
+	tab *Table
+}
+
+// New creates a new hash.Hash64 computing the CRC-64 checksum
+// using the polynomial represented by the Table.
+func New(tab *Table) hash.Hash64 { return &digest{0, tab} }
+
+func (d *digest) Size() int { return Size }
+
+func (d *digest) BlockSize() int { return 1 }
+
+func (d *digest) Reset() { d.crc = 0 }
+
+func update(crc uint64, tab *Table, p []byte) uint64 {
+	crc = ^crc
+	for _, v := range p {
+		crc = tab[byte(crc)^v] ^ (crc >> 8)
+	}
+	return ^crc
+}
+
+// Update returns the result of adding the bytes in p to the crc.
+func Update(crc uint64, tab *Table, p []byte) uint64 {
+	return update(crc, tab, p)
+}
+
+func (d *digest) Write(p []byte) (n int, err error) {
+	d.crc = update(d.crc, d.tab, p)
+	return len(p), nil
+}
+
+func (d *digest) Sum64() uint64 { return d.crc }
+
+func (d *digest) Sum(in []byte) []byte {
+	s := d.Sum64()
+	return append(in, byte(s>>56), byte(s>>48), byte(s>>40), byte(s>>32), byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
+}
+
+// Checksum returns the CRC-64 checksum of data
+// using the polynomial represented by the Table.
+func Checksum(data []byte, tab *Table) uint64 { return update(0, tab, data) }
diff --git a/src/hash/crc64/crc64_test.go b/src/hash/crc64/crc64_test.go
new file mode 100644
index 000000000..81a87b56e
--- /dev/null
+++ b/src/hash/crc64/crc64_test.go
@@ -0,0 +1,81 @@
+// Copyright 2009 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 crc64
+
+import (
+	"io"
+	"testing"
+)
+
+type test struct {
+	out uint64
+	in  string
+}
+
+var golden = []test{
+	{0x0, ""},
+	{0x3420000000000000, "a"},
+	{0x36c4200000000000, "ab"},
+	{0x3776c42000000000, "abc"},
+	{0x336776c420000000, "abcd"},
+	{0x32d36776c4200000, "abcde"},
+	{0x3002d36776c42000, "abcdef"},
+	{0x31b002d36776c420, "abcdefg"},
+	{0xe21b002d36776c4, "abcdefgh"},
+	{0x8b6e21b002d36776, "abcdefghi"},
+	{0x7f5b6e21b002d367, "abcdefghij"},
+	{0x8ec0e7c835bf9cdf, "Discard medicine more than two years old."},
+	{0xc7db1759e2be5ab4, "He who has a shady past knows that nice guys finish last."},
+	{0xfbf9d9603a6fa020, "I wouldn't marry him with a ten foot pole."},
+	{0xeafc4211a6daa0ef, "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave"},
+	{0x3e05b21c7a4dc4da, "The days of the digital watch are numbered.  -Tom Stoppard"},
+	{0x5255866ad6ef28a6, "Nepal premier won't resign."},
+	{0x8a79895be1e9c361, "For every action there is an equal and opposite government program."},
+	{0x8878963a649d4916, "His money is twice tainted: 'taint yours and 'taint mine."},
+	{0xa7b9d53ea87eb82f, "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977"},
+	{0xdb6805c0966a2f9c, "It's a tiny change to the code and not completely disgusting. - Bob Manchek"},
+	{0xf3553c65dacdadd2, "size:  a.out:  bad magic"},
+	{0x9d5e034087a676b9, "The major problem is with sendmail.  -Mark Horton"},
+	{0xa6db2d7f8da96417, "Give me a rock, paper and scissors and I will move the world.  CCFestoon"},
+	{0x325e00cd2fe819f9, "If the enemy is within range, then so are you."},
+	{0x88c6600ce58ae4c6, "It's well we cannot hear the screams/That we create in others' dreams."},
+	{0x28c4a3f3b769e078, "You remind me of a TV show, but that's all right: I watch it anyway."},
+	{0xa698a34c9d9f1dca, "C is as portable as Stonehedge!!"},
+	{0xf6c1e2a8c26c5cfc, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley"},
+	{0xd402559dfe9b70c, "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction.  Lewis-Randall Rule"},
+	{0xdb6efff26aa94946, "How can you write a big system without C++?  -Paul Glick"},
+}
+
+var tab = MakeTable(ISO)
+
+func TestGolden(t *testing.T) {
+	for i := 0; i < len(golden); i++ {
+		g := golden[i]
+		c := New(tab)
+		io.WriteString(c, g.in)
+		s := c.Sum64()
+		if s != g.out {
+			t.Errorf("crc64(%s) = 0x%x want 0x%x", g.in, s, g.out)
+			t.FailNow()
+		}
+	}
+}
+
+func BenchmarkCrc64KB(b *testing.B) {
+	b.SetBytes(1024)
+	data := make([]byte, 1024)
+	for i := range data {
+		data[i] = byte(i)
+	}
+	h := New(tab)
+	in := make([]byte, 0, h.Size())
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		h.Reset()
+		h.Write(data)
+		h.Sum(in)
+	}
+}
diff --git a/src/hash/fnv/fnv.go b/src/hash/fnv/fnv.go
new file mode 100644
index 000000000..c0206613a
--- /dev/null
+++ b/src/hash/fnv/fnv.go
@@ -0,0 +1,131 @@
+// Copyright 2011 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 fnv implements FNV-1 and FNV-1a, non-cryptographic hash functions
+// created by Glenn Fowler, Landon Curt Noll, and Phong Vo.
+// See
+// http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function.
+package fnv
+
+import (
+	"hash"
+)
+
+type (
+	sum32  uint32
+	sum32a uint32
+	sum64  uint64
+	sum64a uint64
+)
+
+const (
+	offset32 = 2166136261
+	offset64 = 14695981039346656037
+	prime32  = 16777619
+	prime64  = 1099511628211
+)
+
+// New32 returns a new 32-bit FNV-1 hash.Hash.
+func New32() hash.Hash32 {
+	var s sum32 = offset32
+	return &s
+}
+
+// New32a returns a new 32-bit FNV-1a hash.Hash.
+func New32a() hash.Hash32 {
+	var s sum32a = offset32
+	return &s
+}
+
+// New64 returns a new 64-bit FNV-1 hash.Hash.
+func New64() hash.Hash64 {
+	var s sum64 = offset64
+	return &s
+}
+
+// New64a returns a new 64-bit FNV-1a hash.Hash.
+func New64a() hash.Hash64 {
+	var s sum64a = offset64
+	return &s
+}
+
+func (s *sum32) Reset()  { *s = offset32 }
+func (s *sum32a) Reset() { *s = offset32 }
+func (s *sum64) Reset()  { *s = offset64 }
+func (s *sum64a) Reset() { *s = offset64 }
+
+func (s *sum32) Sum32() uint32  { return uint32(*s) }
+func (s *sum32a) Sum32() uint32 { return uint32(*s) }
+func (s *sum64) Sum64() uint64  { return uint64(*s) }
+func (s *sum64a) Sum64() uint64 { return uint64(*s) }
+
+func (s *sum32) Write(data []byte) (int, error) {
+	hash := *s
+	for _, c := range data {
+		hash *= prime32
+		hash ^= sum32(c)
+	}
+	*s = hash
+	return len(data), nil
+}
+
+func (s *sum32a) Write(data []byte) (int, error) {
+	hash := *s
+	for _, c := range data {
+		hash ^= sum32a(c)
+		hash *= prime32
+	}
+	*s = hash
+	return len(data), nil
+}
+
+func (s *sum64) Write(data []byte) (int, error) {
+	hash := *s
+	for _, c := range data {
+		hash *= prime64
+		hash ^= sum64(c)
+	}
+	*s = hash
+	return len(data), nil
+}
+
+func (s *sum64a) Write(data []byte) (int, error) {
+	hash := *s
+	for _, c := range data {
+		hash ^= sum64a(c)
+		hash *= prime64
+	}
+	*s = hash
+	return len(data), nil
+}
+
+func (s *sum32) Size() int  { return 4 }
+func (s *sum32a) Size() int { return 4 }
+func (s *sum64) Size() int  { return 8 }
+func (s *sum64a) Size() int { return 8 }
+
+func (s *sum32) BlockSize() int  { return 1 }
+func (s *sum32a) BlockSize() int { return 1 }
+func (s *sum64) BlockSize() int  { return 1 }
+func (s *sum64a) BlockSize() int { return 1 }
+
+func (s *sum32) Sum(in []byte) []byte {
+	v := uint32(*s)
+	return append(in, byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
+}
+
+func (s *sum32a) Sum(in []byte) []byte {
+	v := uint32(*s)
+	return append(in, byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
+}
+
+func (s *sum64) Sum(in []byte) []byte {
+	v := uint64(*s)
+	return append(in, byte(v>>56), byte(v>>48), byte(v>>40), byte(v>>32), byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
+}
+
+func (s *sum64a) Sum(in []byte) []byte {
+	v := uint64(*s)
+	return append(in, byte(v>>56), byte(v>>48), byte(v>>40), byte(v>>32), byte(v>>24), byte(v>>16), byte(v>>8), byte(v))
+}
diff --git a/src/hash/fnv/fnv_test.go b/src/hash/fnv/fnv_test.go
new file mode 100644
index 000000000..89d39b38a
--- /dev/null
+++ b/src/hash/fnv/fnv_test.go
@@ -0,0 +1,165 @@
+// Copyright 2011 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 fnv
+
+import (
+	"bytes"
+	"encoding/binary"
+	"hash"
+	"testing"
+)
+
+type golden struct {
+	sum  []byte
+	text string
+}
+
+var golden32 = []golden{
+	{[]byte{0x81, 0x1c, 0x9d, 0xc5}, ""},
+	{[]byte{0x05, 0x0c, 0x5d, 0x7e}, "a"},
+	{[]byte{0x70, 0x77, 0x2d, 0x38}, "ab"},
+	{[]byte{0x43, 0x9c, 0x2f, 0x4b}, "abc"},
+}
+
+var golden32a = []golden{
+	{[]byte{0x81, 0x1c, 0x9d, 0xc5}, ""},
+	{[]byte{0xe4, 0x0c, 0x29, 0x2c}, "a"},
+	{[]byte{0x4d, 0x25, 0x05, 0xca}, "ab"},
+	{[]byte{0x1a, 0x47, 0xe9, 0x0b}, "abc"},
+}
+
+var golden64 = []golden{
+	{[]byte{0xcb, 0xf2, 0x9c, 0xe4, 0x84, 0x22, 0x23, 0x25}, ""},
+	{[]byte{0xaf, 0x63, 0xbd, 0x4c, 0x86, 0x01, 0xb7, 0xbe}, "a"},
+	{[]byte{0x08, 0x32, 0x67, 0x07, 0xb4, 0xeb, 0x37, 0xb8}, "ab"},
+	{[]byte{0xd8, 0xdc, 0xca, 0x18, 0x6b, 0xaf, 0xad, 0xcb}, "abc"},
+}
+
+var golden64a = []golden{
+	{[]byte{0xcb, 0xf2, 0x9c, 0xe4, 0x84, 0x22, 0x23, 0x25}, ""},
+	{[]byte{0xaf, 0x63, 0xdc, 0x4c, 0x86, 0x01, 0xec, 0x8c}, "a"},
+	{[]byte{0x08, 0x9c, 0x44, 0x07, 0xb5, 0x45, 0x98, 0x6a}, "ab"},
+	{[]byte{0xe7, 0x1f, 0xa2, 0x19, 0x05, 0x41, 0x57, 0x4b}, "abc"},
+}
+
+func TestGolden32(t *testing.T) {
+	testGolden(t, New32(), golden32)
+}
+
+func TestGolden32a(t *testing.T) {
+	testGolden(t, New32a(), golden32a)
+}
+
+func TestGolden64(t *testing.T) {
+	testGolden(t, New64(), golden64)
+}
+
+func TestGolden64a(t *testing.T) {
+	testGolden(t, New64a(), golden64a)
+}
+
+func testGolden(t *testing.T, hash hash.Hash, gold []golden) {
+	for _, g := range gold {
+		hash.Reset()
+		done, error := hash.Write([]byte(g.text))
+		if error != nil {
+			t.Fatalf("write error: %s", error)
+		}
+		if done != len(g.text) {
+			t.Fatalf("wrote only %d out of %d bytes", done, len(g.text))
+		}
+		if actual := hash.Sum(nil); !bytes.Equal(g.sum, actual) {
+			t.Errorf("hash(%q) = 0x%x want 0x%x", g.text, actual, g.sum)
+		}
+	}
+}
+
+func TestIntegrity32(t *testing.T) {
+	testIntegrity(t, New32())
+}
+
+func TestIntegrity32a(t *testing.T) {
+	testIntegrity(t, New32a())
+}
+
+func TestIntegrity64(t *testing.T) {
+	testIntegrity(t, New64())
+}
+
+func TestIntegrity64a(t *testing.T) {
+	testIntegrity(t, New64a())
+}
+
+func testIntegrity(t *testing.T, h hash.Hash) {
+	data := []byte{'1', '2', 3, 4, 5}
+	h.Write(data)
+	sum := h.Sum(nil)
+
+	if size := h.Size(); size != len(sum) {
+		t.Fatalf("Size()=%d but len(Sum())=%d", size, len(sum))
+	}
+
+	if a := h.Sum(nil); !bytes.Equal(sum, a) {
+		t.Fatalf("first Sum()=0x%x, second Sum()=0x%x", sum, a)
+	}
+
+	h.Reset()
+	h.Write(data)
+	if a := h.Sum(nil); !bytes.Equal(sum, a) {
+		t.Fatalf("Sum()=0x%x, but after Reset() Sum()=0x%x", sum, a)
+	}
+
+	h.Reset()
+	h.Write(data[:2])
+	h.Write(data[2:])
+	if a := h.Sum(nil); !bytes.Equal(sum, a) {
+		t.Fatalf("Sum()=0x%x, but with partial writes, Sum()=0x%x", sum, a)
+	}
+
+	switch h.Size() {
+	case 4:
+		sum32 := h.(hash.Hash32).Sum32()
+		if sum32 != binary.BigEndian.Uint32(sum) {
+			t.Fatalf("Sum()=0x%x, but Sum32()=0x%x", sum, sum32)
+		}
+	case 8:
+		sum64 := h.(hash.Hash64).Sum64()
+		if sum64 != binary.BigEndian.Uint64(sum) {
+			t.Fatalf("Sum()=0x%x, but Sum64()=0x%x", sum, sum64)
+		}
+	}
+}
+
+func BenchmarkFnv32KB(b *testing.B) {
+	benchmarkKB(b, New32())
+}
+
+func BenchmarkFnv32aKB(b *testing.B) {
+	benchmarkKB(b, New32a())
+}
+
+func BenchmarkFnv64KB(b *testing.B) {
+	benchmarkKB(b, New64())
+}
+
+func BenchmarkFnv64aKB(b *testing.B) {
+	benchmarkKB(b, New64a())
+}
+
+func benchmarkKB(b *testing.B, h hash.Hash) {
+	b.SetBytes(1024)
+	data := make([]byte, 1024)
+	for i := range data {
+		data[i] = byte(i)
+	}
+	in := make([]byte, 0, h.Size())
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		h.Reset()
+		h.Write(data)
+		h.Sum(in)
+	}
+}
diff --git a/src/hash/hash.go b/src/hash/hash.go
new file mode 100644
index 000000000..8d138d07f
--- /dev/null
+++ b/src/hash/hash.go
@@ -0,0 +1,43 @@
+// Copyright 2009 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 hash provides interfaces for hash functions.
+package hash
+
+import "io"
+
+// Hash is the common interface implemented by all hash functions.
+type Hash interface {
+	// Write (via the embedded io.Writer interface) adds more data to the running hash.
+	// It never returns an error.
+	io.Writer
+
+	// Sum appends the current hash to b and returns the resulting slice.
+	// It does not change the underlying hash state.
+	Sum(b []byte) []byte
+
+	// Reset resets the Hash to its initial state.
+	Reset()
+
+	// Size returns the number of bytes Sum will return.
+	Size() int
+
+	// BlockSize returns the hash's underlying block size.
+	// The Write method must be able to accept any amount
+	// of data, but it may operate more efficiently if all writes
+	// are a multiple of the block size.
+	BlockSize() int
+}
+
+// Hash32 is the common interface implemented by all 32-bit hash functions.
+type Hash32 interface {
+	Hash
+	Sum32() uint32
+}
+
+// Hash64 is the common interface implemented by all 64-bit hash functions.
+type Hash64 interface {
+	Hash
+	Sum64() uint64
+}
diff --git a/src/hash/test_cases.txt b/src/hash/test_cases.txt
new file mode 100644
index 000000000..26d3ccc05
--- /dev/null
+++ b/src/hash/test_cases.txt
@@ -0,0 +1,31 @@
+
+a
+ab
+abc
+abcd
+abcde
+abcdef
+abcdefg
+abcdefgh
+abcdefghi
+abcdefghij
+Discard medicine more than two years old.
+He who has a shady past knows that nice guys finish last.
+I wouldn't marry him with a ten foot pole.
+Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave
+The days of the digital watch are numbered.  -Tom Stoppard
+Nepal premier won't resign.
+For every action there is an equal and opposite government program.
+His money is twice tainted: 'taint yours and 'taint mine.
+There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977
+It's a tiny change to the code and not completely disgusting. - Bob Manchek
+size:  a.out:  bad magic
+The major problem is with sendmail.  -Mark Horton
+Give me a rock, paper and scissors and I will move the world.  CCFestoon
+If the enemy is within range, then so are you.
+It's well we cannot hear the screams/That we create in others' dreams.
+You remind me of a TV show, but that's all right: I watch it anyway.
+C is as portable as Stonehedge!!
+Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley
+The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction.  Lewis-Randall Rule
+How can you write a big system without C++?  -Paul Glick
diff --git a/src/hash/test_gen.awk b/src/hash/test_gen.awk
new file mode 100644
index 000000000..804f78679
--- /dev/null
+++ b/src/hash/test_gen.awk
@@ -0,0 +1,14 @@
+# Copyright 2009 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.
+
+# awk -f test_gen.awk test_cases.txt
+# generates test case table.
+# edit next line to set particular reference implementation and name.
+BEGIN { cmd = "echo -n `9 sha1sum`"; name = "Sha1Test" }
+{
+	printf("\t%s{ \"", name);
+	printf("%s", $0) |cmd;
+	close(cmd);
+	printf("\", \"%s\" },\n", $0);
+}