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.

6 files changed, 403 insertions, 0 deletions

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)
+	}
+}