diff options
Diffstat (limited to 'src/pkg/hash')
| -rw-r--r-- | src/pkg/hash/adler32/adler32.go | 78 | ||||
| -rw-r--r-- | src/pkg/hash/adler32/adler32_test.go | 105 | ||||
| -rw-r--r-- | src/pkg/hash/crc32/crc32.go | 135 | ||||
| -rw-r--r-- | src/pkg/hash/crc32/crc32_amd64.s | 64 | ||||
| -rw-r--r-- | src/pkg/hash/crc32/crc32_amd64p32.s | 64 | ||||
| -rw-r--r-- | src/pkg/hash/crc32/crc32_amd64x.go | 27 | ||||
| -rw-r--r-- | src/pkg/hash/crc32/crc32_generic.go | 14 | ||||
| -rw-r--r-- | src/pkg/hash/crc32/crc32_test.go | 99 | ||||
| -rw-r--r-- | src/pkg/hash/crc64/crc64.go | 87 | ||||
| -rw-r--r-- | src/pkg/hash/crc64/crc64_test.go | 81 | ||||
| -rw-r--r-- | src/pkg/hash/fnv/fnv.go | 131 | ||||
| -rw-r--r-- | src/pkg/hash/fnv/fnv_test.go | 165 | ||||
| -rw-r--r-- | src/pkg/hash/hash.go | 43 | ||||
| -rw-r--r-- | src/pkg/hash/test_cases.txt | 31 | ||||
| -rw-r--r-- | src/pkg/hash/test_gen.awk | 14 |
15 files changed, 0 insertions, 1138 deletions
diff --git a/src/pkg/hash/adler32/adler32.go b/src/pkg/hash/adler32/adler32.go deleted file mode 100644 index 7c80796bf..000000000 --- a/src/pkg/hash/adler32/adler32.go +++ /dev/null @@ -1,78 +0,0 @@ -// 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/pkg/hash/adler32/adler32_test.go b/src/pkg/hash/adler32/adler32_test.go deleted file mode 100644 index 0e9c938d8..000000000 --- a/src/pkg/hash/adler32/adler32_test.go +++ /dev/null @@ -1,105 +0,0 @@ -// 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/pkg/hash/crc32/crc32.go b/src/pkg/hash/crc32/crc32.go deleted file mode 100644 index a2a21a06f..000000000 --- a/src/pkg/hash/crc32/crc32.go +++ /dev/null @@ -1,135 +0,0 @@ -// 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/pkg/hash/crc32/crc32_amd64.s b/src/pkg/hash/crc32/crc32_amd64.s deleted file mode 100644 index 95dc8bf41..000000000 --- a/src/pkg/hash/crc32/crc32_amd64.s +++ /dev/null @@ -1,64 +0,0 @@ -// 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 "../../../cmd/ld/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/pkg/hash/crc32/crc32_amd64p32.s b/src/pkg/hash/crc32/crc32_amd64p32.s deleted file mode 100644 index e34f20867..000000000 --- a/src/pkg/hash/crc32/crc32_amd64p32.s +++ /dev/null @@ -1,64 +0,0 @@ -// 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 "../../../cmd/ld/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/pkg/hash/crc32/crc32_amd64x.go b/src/pkg/hash/crc32/crc32_amd64x.go deleted file mode 100644 index b7e359930..000000000 --- a/src/pkg/hash/crc32/crc32_amd64x.go +++ /dev/null @@ -1,27 +0,0 @@ -// 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/pkg/hash/crc32/crc32_generic.go b/src/pkg/hash/crc32/crc32_generic.go deleted file mode 100644 index c3fdcd685..000000000 --- a/src/pkg/hash/crc32/crc32_generic.go +++ /dev/null @@ -1,14 +0,0 @@ -// 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/pkg/hash/crc32/crc32_test.go b/src/pkg/hash/crc32/crc32_test.go deleted file mode 100644 index 75dc26e7c..000000000 --- a/src/pkg/hash/crc32/crc32_test.go +++ /dev/null @@ -1,99 +0,0 @@ -// 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/pkg/hash/crc64/crc64.go b/src/pkg/hash/crc64/crc64.go deleted file mode 100644 index 692586798..000000000 --- a/src/pkg/hash/crc64/crc64.go +++ /dev/null @@ -1,87 +0,0 @@ -// 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/pkg/hash/crc64/crc64_test.go b/src/pkg/hash/crc64/crc64_test.go deleted file mode 100644 index 81a87b56e..000000000 --- a/src/pkg/hash/crc64/crc64_test.go +++ /dev/null @@ -1,81 +0,0 @@ -// 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/pkg/hash/fnv/fnv.go b/src/pkg/hash/fnv/fnv.go deleted file mode 100644 index c0206613a..000000000 --- a/src/pkg/hash/fnv/fnv.go +++ /dev/null @@ -1,131 +0,0 @@ -// 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/pkg/hash/fnv/fnv_test.go b/src/pkg/hash/fnv/fnv_test.go deleted file mode 100644 index 89d39b38a..000000000 --- a/src/pkg/hash/fnv/fnv_test.go +++ /dev/null @@ -1,165 +0,0 @@ -// 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/pkg/hash/hash.go b/src/pkg/hash/hash.go deleted file mode 100644 index 8d138d07f..000000000 --- a/src/pkg/hash/hash.go +++ /dev/null @@ -1,43 +0,0 @@ -// 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/pkg/hash/test_cases.txt b/src/pkg/hash/test_cases.txt deleted file mode 100644 index 26d3ccc05..000000000 --- a/src/pkg/hash/test_cases.txt +++ /dev/null @@ -1,31 +0,0 @@ - -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 deleted file mode 100644 index 804f78679..000000000 --- a/src/pkg/hash/test_gen.awk +++ /dev/null @@ -1,14 +0,0 @@ -# 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); -} |