summaryrefslogtreecommitdiff
path: root/src/pkg/hash
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/hash')
-rw-r--r--src/pkg/hash/Makefile11
-rw-r--r--src/pkg/hash/adler32/Makefile11
-rw-r--r--src/pkg/hash/adler32/adler32.go88
-rw-r--r--src/pkg/hash/adler32/adler32_test.go77
-rw-r--r--src/pkg/hash/crc32/Makefile20
-rw-r--r--src/pkg/hash/crc32/crc32.go139
-rw-r--r--src/pkg/hash/crc32/crc32_amd64.go25
-rw-r--r--src/pkg/hash/crc32/crc32_amd64.s62
-rw-r--r--src/pkg/hash/crc32/crc32_generic.go12
-rw-r--r--src/pkg/hash/crc32/crc32_test.go97
-rw-r--r--src/pkg/hash/crc64/Makefile11
-rw-r--r--src/pkg/hash/crc64/crc64.go97
-rw-r--r--src/pkg/hash/crc64/crc64_test.go78
-rw-r--r--src/pkg/hash/fnv/Makefile11
-rw-r--r--src/pkg/hash/fnv/fnv.go131
-rw-r--r--src/pkg/hash/fnv/fnv_test.go167
-rw-r--r--src/pkg/hash/hash.go37
-rw-r--r--src/pkg/hash/test_cases.txt31
-rw-r--r--src/pkg/hash/test_gen.awk14
19 files changed, 1119 insertions, 0 deletions
diff --git a/src/pkg/hash/Makefile b/src/pkg/hash/Makefile
new file mode 100644
index 000000000..56071cb33
--- /dev/null
+++ b/src/pkg/hash/Makefile
@@ -0,0 +1,11 @@
+# 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.
+
+include ../../Make.inc
+
+TARG=hash
+GOFILES=\
+ hash.go\
+
+include ../../Make.pkg
diff --git a/src/pkg/hash/adler32/Makefile b/src/pkg/hash/adler32/Makefile
new file mode 100644
index 000000000..38ce537ba
--- /dev/null
+++ b/src/pkg/hash/adler32/Makefile
@@ -0,0 +1,11 @@
+# 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.
+
+include ../../../Make.inc
+
+TARG=hash/adler32
+GOFILES=\
+ adler32.go\
+
+include ../../../Make.pkg
diff --git a/src/pkg/hash/adler32/adler32.go b/src/pkg/hash/adler32/adler32.go
new file mode 100644
index 000000000..84943d9ae
--- /dev/null
+++ b/src/pkg/hash/adler32/adler32.go
@@ -0,0 +1,88 @@
+// 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.
+// 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"
+ "os"
+)
+
+const (
+ mod = 65521
+)
+
+// The size of an Adler-32 checksum in bytes.
+const Size = 4
+
+// digest represents the partial evaluation of a checksum.
+type digest struct {
+ // invariant: (a < mod && b < mod) || a <= b
+ // invariant: a + b + 255 <= 0xffffffff
+ a, b uint32
+}
+
+func (d *digest) Reset() { d.a, d.b = 1, 0 }
+
+// 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 }
+
+// Add p to the running checksum a, b.
+func update(a, b uint32, p []byte) (aa, bb uint32) {
+ for _, pi := range p {
+ a += uint32(pi)
+ b += a
+ // invariant: a <= b
+ if b > (0xffffffff-255)/2 {
+ a %= mod
+ b %= mod
+ // invariant: a < mod && b < mod
+ } else {
+ // invariant: a + b + 255 <= 2 * b + 255 <= 0xffffffff
+ }
+ }
+ return a, b
+}
+
+// Return the 32-bit checksum corresponding to a, b.
+func finish(a, b uint32) uint32 {
+ if b >= mod {
+ a %= mod
+ b %= mod
+ }
+ return b<<16 | a
+}
+
+func (d *digest) Write(p []byte) (nn int, err os.Error) {
+ d.a, d.b = update(d.a, d.b, p)
+ return len(p), nil
+}
+
+func (d *digest) Sum32() uint32 { return finish(d.a, d.b) }
+
+func (d *digest) Sum() []byte {
+ p := make([]byte, 4)
+ s := d.Sum32()
+ p[0] = byte(s >> 24)
+ p[1] = byte(s >> 16)
+ p[2] = byte(s >> 8)
+ p[3] = byte(s)
+ return p
+}
+
+// Checksum returns the Adler-32 checksum of data.
+func Checksum(data []byte) uint32 { return finish(update(1, 0, data)) }
diff --git a/src/pkg/hash/adler32/adler32_test.go b/src/pkg/hash/adler32/adler32_test.go
new file mode 100644
index 000000000..01f931c68
--- /dev/null
+++ b/src/pkg/hash/adler32/adler32_test.go
@@ -0,0 +1,77 @@
+// 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 (
+ "bytes"
+ "io"
+ "testing"
+)
+
+type _Adler32Test struct {
+ out uint32
+ in string
+}
+
+var golden = []_Adler32Test{
+ {0x1, ""},
+ {0x620062, "a"},
+ {0x12600c4, "ab"},
+ {0x24d0127, "abc"},
+ {0x3d8018b, "abcd"},
+ {0x5c801f0, "abcde"},
+ {0x81e0256, "abcdef"},
+ {0xadb02bd, "abcdefg"},
+ {0xe000325, "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"},
+}
+
+func TestGolden(t *testing.T) {
+ for i := 0; i < len(golden); i++ {
+ g := golden[i]
+ c := New()
+ io.WriteString(c, g.in)
+ s := c.Sum32()
+ if s != g.out {
+ t.Errorf("adler32(%s) = 0x%x want 0x%x", g.in, s, g.out)
+ t.FailNow()
+ }
+ }
+}
+
+func BenchmarkGolden(b *testing.B) {
+ b.StopTimer()
+ c := New()
+ var buf bytes.Buffer
+ for _, g := range golden {
+ buf.Write([]byte(g.in))
+ }
+ b.StartTimer()
+ for i := 0; i < b.N; i++ {
+ c.Write(buf.Bytes())
+ }
+}
diff --git a/src/pkg/hash/crc32/Makefile b/src/pkg/hash/crc32/Makefile
new file mode 100644
index 000000000..af8a64cf2
--- /dev/null
+++ b/src/pkg/hash/crc32/Makefile
@@ -0,0 +1,20 @@
+# 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.
+
+include ../../../Make.inc
+
+TARG=hash/crc32
+
+ifeq ($(GOARCH), amd64)
+ ARCH_GOFILES=crc32_amd64.go
+ OFILES=crc32_amd64.6
+else
+ ARCH_GOFILES=crc32_generic.go
+endif
+
+GOFILES=\
+ crc32.go\
+ $(ARCH_GOFILES)
+
+include ../../../Make.pkg
diff --git a/src/pkg/hash/crc32/crc32.go b/src/pkg/hash/crc32/crc32.go
new file mode 100644
index 000000000..0245b1ee8
--- /dev/null
+++ b/src/pkg/hash/crc32/crc32.go
@@ -0,0 +1,139 @@
+// 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"
+ "os"
+ "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) 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 os.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() []byte {
+ p := make([]byte, 4)
+ s := d.Sum32()
+ p[0] = byte(s >> 24)
+ p[1] = byte(s >> 16)
+ p[2] = byte(s >> 8)
+ p[3] = byte(s)
+ return p
+}
+
+// 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/pkg/hash/crc32/crc32_amd64.go b/src/pkg/hash/crc32/crc32_amd64.go
new file mode 100644
index 000000000..83349bc6c
--- /dev/null
+++ b/src/pkg/hash/crc32/crc32_amd64.go
@@ -0,0 +1,25 @@
+// 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 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(uint32, []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/pkg/hash/crc32/crc32_amd64.s b/src/pkg/hash/crc32/crc32_amd64.s
new file mode 100644
index 000000000..a9e5317e1
--- /dev/null
+++ b/src/pkg/hash/crc32/crc32_amd64.s
@@ -0,0 +1,62 @@
+// 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.
+
+// func castagnoliSSE42(crc uint32, p []byte) uint32
+TEXT ·castagnoliSSE42(SB),7,$0
+ MOVL crc+0(FP), AX // CRC value
+ MOVQ p+8(FP), SI // data pointer
+ MOVL p+16(FP), CX // len(p)
+
+ NOTL AX
+
+ /* If there's less than 8 bytes to process, we do it byte-by-byte. */
+ CMPL 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
+ DECL CX
+ INCQ SI
+ JMP startup
+
+aligned:
+ /* The input is now 8-byte aligned and we can process 8-byte chunks. */
+ CMPL 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. */
+ CMPL CX, $0
+ JE done
+
+ CRC32B (SI), AX
+ INCQ SI
+ DECQ CX
+ JMP cleanup
+
+done:
+ NOTL AX
+ MOVL AX, ret+24(FP)
+ RET
+
+// func haveSSE42() bool
+TEXT ·haveSSE42(SB),7,$0
+ XORQ AX, AX
+ INCL AX
+ CPUID
+ SHRQ $20, CX
+ ANDQ $1, CX
+ MOVB CX, ret+0(FP)
+ RET
+
diff --git a/src/pkg/hash/crc32/crc32_generic.go b/src/pkg/hash/crc32/crc32_generic.go
new file mode 100644
index 000000000..27aabd903
--- /dev/null
+++ b/src/pkg/hash/crc32/crc32_generic.go
@@ -0,0 +1,12 @@
+// 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 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/pkg/hash/crc32/crc32_test.go b/src/pkg/hash/crc32/crc32_test.go
new file mode 100644
index 000000000..7e82dd755
--- /dev/null
+++ b/src/pkg/hash/crc32/crc32_test.go
@@ -0,0 +1,97 @@
+// 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.StopTimer()
+ data := make([]uint8, 1024)
+ for i := 0; i < 1024; i++ {
+ data[i] = uint8(i)
+ }
+ c := NewIEEE()
+ b.StartTimer()
+ b.SetBytes(int64(len(data)))
+
+ for i := 0; i < b.N; i++ {
+ c.Write(data)
+ }
+}
diff --git a/src/pkg/hash/crc64/Makefile b/src/pkg/hash/crc64/Makefile
new file mode 100644
index 000000000..5f6c3de69
--- /dev/null
+++ b/src/pkg/hash/crc64/Makefile
@@ -0,0 +1,11 @@
+# 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.
+
+include ../../../Make.inc
+
+TARG=hash/crc64
+GOFILES=\
+ crc64.go\
+
+include ../../../Make.pkg
diff --git a/src/pkg/hash/crc64/crc64.go b/src/pkg/hash/crc64/crc64.go
new file mode 100644
index 000000000..ae37e781c
--- /dev/null
+++ b/src/pkg/hash/crc64/crc64.go
@@ -0,0 +1,97 @@
+// 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"
+ "os"
+)
+
+// 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) 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 os.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() []byte {
+ p := make([]byte, 8)
+ s := d.Sum64()
+ p[0] = byte(s >> 56)
+ p[1] = byte(s >> 48)
+ p[2] = byte(s >> 40)
+ p[3] = byte(s >> 32)
+ p[4] = byte(s >> 24)
+ p[5] = byte(s >> 16)
+ p[6] = byte(s >> 8)
+ p[7] = byte(s)
+ return p
+}
+
+// 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/pkg/hash/crc64/crc64_test.go b/src/pkg/hash/crc64/crc64_test.go
new file mode 100644
index 000000000..e932524e0
--- /dev/null
+++ b/src/pkg/hash/crc64/crc64_test.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 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.StopTimer()
+ data := make([]uint8, 1024)
+ for i := 0; i < 1024; i++ {
+ data[i] = uint8(i)
+ }
+ c := New(tab)
+ b.StartTimer()
+
+ for i := 0; i < b.N; i++ {
+ c.Write(data)
+ }
+}
diff --git a/src/pkg/hash/fnv/Makefile b/src/pkg/hash/fnv/Makefile
new file mode 100644
index 000000000..4c8a4ecf0
--- /dev/null
+++ b/src/pkg/hash/fnv/Makefile
@@ -0,0 +1,11 @@
+# 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 ../../../Make.inc
+
+TARG=hash/fnv
+GOFILES=\
+ fnv.go\
+
+include ../../../Make.pkg
diff --git a/src/pkg/hash/fnv/fnv.go b/src/pkg/hash/fnv/fnv.go
new file mode 100644
index 000000000..3ff7d7c75
--- /dev/null
+++ b/src/pkg/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://isthe.com/chongo/tech/comp/fnv/.
+package fnv
+
+import (
+ "encoding/binary"
+ "hash"
+ "os"
+)
+
+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, os.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, os.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, os.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, os.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) Sum() []byte {
+ a := make([]byte, 4)
+ binary.BigEndian.PutUint32(a, uint32(*s))
+ return a
+}
+
+func (s *sum32a) Sum() []byte {
+ a := make([]byte, 4)
+ binary.BigEndian.PutUint32(a, uint32(*s))
+ return a
+}
+
+func (s *sum64) Sum() []byte {
+ a := make([]byte, 8)
+ binary.BigEndian.PutUint64(a, uint64(*s))
+ return a
+}
+
+func (s *sum64a) Sum() []byte {
+ a := make([]byte, 8)
+ binary.BigEndian.PutUint64(a, uint64(*s))
+ return a
+}
diff --git a/src/pkg/hash/fnv/fnv_test.go b/src/pkg/hash/fnv/fnv_test.go
new file mode 100644
index 000000000..429230c80
--- /dev/null
+++ b/src/pkg/hash/fnv/fnv_test.go
@@ -0,0 +1,167 @@
+// 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"
+)
+
+const testDataSize = 40
+
+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(); !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()
+
+ if size := h.Size(); size != len(sum) {
+ t.Fatalf("Size()=%d but len(Sum())=%d", size, len(sum))
+ }
+
+ if a := h.Sum(); !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(); !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(); !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 Benchmark32(b *testing.B) {
+ benchmark(b, New32())
+}
+
+func Benchmark32a(b *testing.B) {
+ benchmark(b, New32a())
+}
+
+func Benchmark64(b *testing.B) {
+ benchmark(b, New64())
+}
+
+func Benchmark64a(b *testing.B) {
+ benchmark(b, New64a())
+}
+
+func benchmark(b *testing.B, h hash.Hash) {
+ b.ResetTimer()
+ b.SetBytes(testDataSize)
+ data := make([]byte, testDataSize)
+ for i := range data {
+ data[i] = byte(i + 'a')
+ }
+
+ b.StartTimer()
+ for todo := b.N; todo != 0; todo-- {
+ h.Reset()
+ h.Write(data)
+ h.Sum()
+ }
+}
diff --git a/src/pkg/hash/hash.go b/src/pkg/hash/hash.go
new file mode 100644
index 000000000..3536c0b6a
--- /dev/null
+++ b/src/pkg/hash/hash.go
@@ -0,0 +1,37 @@
+// 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 adds more data to the running hash.
+ // It never returns an error.
+ io.Writer
+
+ // Sum returns the current hash, without changing the
+ // underlying hash state.
+ Sum() []byte
+
+ // Reset resets the hash to one with zero bytes written.
+ Reset()
+
+ // Size returns the number of bytes Sum will return.
+ Size() 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/pkg/hash/test_cases.txt b/src/pkg/hash/test_cases.txt
new file mode 100644
index 000000000..26d3ccc05
--- /dev/null
+++ b/src/pkg/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/pkg/hash/test_gen.awk b/src/pkg/hash/test_gen.awk
new file mode 100644
index 000000000..804f78679
--- /dev/null
+++ b/src/pkg/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);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-22 22:35:13 +0000