diff options
Diffstat (limited to 'libgo/go/hash/crc64')
| -rw-r--r-- | libgo/go/hash/crc64/crc64.go | 96 | ||||
| -rw-r--r-- | libgo/go/hash/crc64/crc64_test.go | 78 |
2 files changed, 174 insertions, 0 deletions
diff --git a/libgo/go/hash/crc64/crc64.go b/libgo/go/hash/crc64/crc64.go new file mode 100644 index 000000000..844386564 --- /dev/null +++ b/libgo/go/hash/crc64/crc64.go @@ -0,0 +1,96 @@ +// 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. + +// This package 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/libgo/go/hash/crc64/crc64_test.go b/libgo/go/hash/crc64/crc64_test.go new file mode 100644 index 000000000..e932524e0 --- /dev/null +++ b/libgo/go/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) + } +} |