diff options
Diffstat (limited to 'src/hash/crc64')
| -rw-r--r-- | src/hash/crc64/crc64.go | 224 | ||||
| -rw-r--r-- | src/hash/crc64/crc64_test.go | 193 |
2 files changed, 417 insertions, 0 deletions
diff --git a/src/hash/crc64/crc64.go b/src/hash/crc64/crc64.go new file mode 100644 index 0000000..063c63c --- /dev/null +++ b/src/hash/crc64/crc64.go @@ -0,0 +1,224 @@ +// 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 https://en.wikipedia.org/wiki/Cyclic_redundancy_check for +// information. +package crc64 + +import ( + "errors" + "hash" + "sync" +) + +// 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 + +var ( + slicing8TablesBuildOnce sync.Once + slicing8TableISO *[8]Table + slicing8TableECMA *[8]Table +) + +func buildSlicing8TablesOnce() { + slicing8TablesBuildOnce.Do(buildSlicing8Tables) +} + +func buildSlicing8Tables() { + slicing8TableISO = makeSlicingBy8Table(makeTable(ISO)) + slicing8TableECMA = makeSlicingBy8Table(makeTable(ECMA)) +} + +// MakeTable returns a Table constructed from the specified polynomial. +// The contents of this Table must not be modified. +func MakeTable(poly uint64) *Table { + buildSlicing8TablesOnce() + switch poly { + case ISO: + return &slicing8TableISO[0] + case ECMA: + return &slicing8TableECMA[0] + default: + return makeTable(poly) + } +} + +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 +} + +func makeSlicingBy8Table(t *Table) *[8]Table { + var helperTable [8]Table + helperTable[0] = *t + for i := 0; i < 256; i++ { + crc := t[i] + for j := 1; j < 8; j++ { + crc = t[crc&0xff] ^ (crc >> 8) + helperTable[j][i] = crc + } + } + return &helperTable +} + +// 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. Its Sum method will lay the +// value out in big-endian byte order. The returned Hash64 also +// implements encoding.BinaryMarshaler and encoding.BinaryUnmarshaler to +// marshal and unmarshal the internal state of the hash. +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 } + +const ( + magic = "crc\x02" + marshaledSize = len(magic) + 8 + 8 +) + +func (d *digest) MarshalBinary() ([]byte, error) { + b := make([]byte, 0, marshaledSize) + b = append(b, magic...) + b = appendUint64(b, tableSum(d.tab)) + b = appendUint64(b, d.crc) + return b, nil +} + +func (d *digest) UnmarshalBinary(b []byte) error { + if len(b) < len(magic) || string(b[:len(magic)]) != magic { + return errors.New("hash/crc64: invalid hash state identifier") + } + if len(b) != marshaledSize { + return errors.New("hash/crc64: invalid hash state size") + } + if tableSum(d.tab) != readUint64(b[4:]) { + return errors.New("hash/crc64: tables do not match") + } + d.crc = readUint64(b[12:]) + return nil +} + +func appendUint64(b []byte, x uint64) []byte { + a := [8]byte{ + byte(x >> 56), + byte(x >> 48), + byte(x >> 40), + byte(x >> 32), + byte(x >> 24), + byte(x >> 16), + byte(x >> 8), + byte(x), + } + return append(b, a[:]...) +} + +func readUint64(b []byte) uint64 { + _ = b[7] + return uint64(b[7]) | uint64(b[6])<<8 | uint64(b[5])<<16 | uint64(b[4])<<24 | + uint64(b[3])<<32 | uint64(b[2])<<40 | uint64(b[1])<<48 | uint64(b[0])<<56 +} + +func update(crc uint64, tab *Table, p []byte) uint64 { + buildSlicing8TablesOnce() + crc = ^crc + // Table comparison is somewhat expensive, so avoid it for small sizes + for len(p) >= 64 { + var helperTable *[8]Table + if *tab == slicing8TableECMA[0] { + helperTable = slicing8TableECMA + } else if *tab == slicing8TableISO[0] { + helperTable = slicing8TableISO + // For smaller sizes creating extended table takes too much time + } else if len(p) > 16384 { + helperTable = makeSlicingBy8Table(tab) + } else { + break + } + // Update using slicing-by-8 + for len(p) > 8 { + crc ^= uint64(p[0]) | uint64(p[1])<<8 | uint64(p[2])<<16 | uint64(p[3])<<24 | + uint64(p[4])<<32 | uint64(p[5])<<40 | uint64(p[6])<<48 | uint64(p[7])<<56 + crc = helperTable[7][crc&0xff] ^ + helperTable[6][(crc>>8)&0xff] ^ + helperTable[5][(crc>>16)&0xff] ^ + helperTable[4][(crc>>24)&0xff] ^ + helperTable[3][(crc>>32)&0xff] ^ + helperTable[2][(crc>>40)&0xff] ^ + helperTable[1][(crc>>48)&0xff] ^ + helperTable[0][crc>>56] + p = p[8:] + } + } + // For reminders or small sizes + 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) } + +// tableSum returns the ISO checksum of table t. +func tableSum(t *Table) uint64 { + var a [2048]byte + b := a[:0] + if t != nil { + for _, x := range t { + b = appendUint64(b, x) + } + } + return Checksum(b, MakeTable(ISO)) +} diff --git a/src/hash/crc64/crc64_test.go b/src/hash/crc64/crc64_test.go new file mode 100644 index 0000000..9cf602c --- /dev/null +++ b/src/hash/crc64/crc64_test.go @@ -0,0 +1,193 @@ +// 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 ( + "encoding" + "io" + "testing" +) + +type test struct { + outISO uint64 + outECMA uint64 + in string + halfStateISO string // ISO marshaled hash state after first half of in written, used by TestGoldenMarshal + halfStateECMA string // ECMA marshaled hash state after first half of in written, used by TestGoldenMarshal +} + +var golden = []test{ + {0x0, 0x0, "", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\x00\x00\x00\x00\x00\x00\x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee\x00\x00\x00\x00\x00\x00\x00\x00"}, + {0x3420000000000000, 0x330284772e652b05, "a", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\x00\x00\x00\x00\x00\x00\x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee\x00\x00\x00\x00\x00\x00\x00\x00"}, + {0x36c4200000000000, 0xbc6573200e84b046, "ab", "crc\x02s\xba\x84\x84\xbb\xcd]\xef4 \x00\x00\x00\x00\x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee3\x02\x84w.e+\x05"}, + {0x3776c42000000000, 0x2cd8094a1a277627, "abc", "crc\x02s\xba\x84\x84\xbb\xcd]\xef4 \x00\x00\x00\x00\x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee3\x02\x84w.e+\x05"}, + {0x336776c420000000, 0x3c9d28596e5960ba, "abcd", "crc\x02s\xba\x84\x84\xbb\xcd]\xef6\xc4 \x00\x00\x00\x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee\xbces \x0e\x84\xb0F"}, + {0x32d36776c4200000, 0x40bdf58fb0895f2, "abcde", "crc\x02s\xba\x84\x84\xbb\xcd]\xef6\xc4 \x00\x00\x00\x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee\xbces \x0e\x84\xb0F"}, + {0x3002d36776c42000, 0xd08e9f8545a700f4, "abcdef", "crc\x02s\xba\x84\x84\xbb\xcd]\xef7v\xc4 \x00\x00\x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee,\xd8\tJ\x1a'v'"}, + {0x31b002d36776c420, 0xec20a3a8cc710e66, "abcdefg", "crc\x02s\xba\x84\x84\xbb\xcd]\xef7v\xc4 \x00\x00\x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee,\xd8\tJ\x1a'v'"}, + {0xe21b002d36776c4, 0x67b4f30a647a0c59, "abcdefgh", "crc\x02s\xba\x84\x84\xbb\xcd]\xef3gv\xc4 \x00\x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee<\x9d(YnY`\xba"}, + {0x8b6e21b002d36776, 0x9966f6c89d56ef8e, "abcdefghi", "crc\x02s\xba\x84\x84\xbb\xcd]\xef3gv\xc4 \x00\x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee<\x9d(YnY`\xba"}, + {0x7f5b6e21b002d367, 0x32093a2ecd5773f4, "abcdefghij", "crc\x02s\xba\x84\x84\xbb\xcd]\xef2\xd3gv\xc4 \x00\x00", "crc\x02`&\x9aR\xe1\xb7\xfee\x04\v\xdfX\xfb\b\x95\xf2"}, + {0x8ec0e7c835bf9cdf, 0x8a0825223ea6d221, "Discard medicine more than two years old.", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\xc6\xc0\f\xac'\x11\x12\xd5", "crc\x02`&\x9aR\xe1\xb7\xfee\xfd%\xc0&\xa0R\xef\x95"}, + {0xc7db1759e2be5ab4, 0x8562c0ac2ab9a00d, "He who has a shady past knows that nice guys finish last.", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\t\xcb\xd15X[r\t", "crc\x02`&\x9aR\xe1\xb7\xfee\a\x02\xe8|+\xc1\x06\xe3"}, + {0xfbf9d9603a6fa020, 0x3ee2a39c083f38b4, "I wouldn't marry him with a ten foot pole.", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\x19\xc8d\xbe\x84\x14\x87_", "crc\x02`&\x9aR\xe1\xb7\xfee˷\xd3\xeeG\xdcE\x8c"}, + {0xeafc4211a6daa0ef, 0x1f603830353e518a, "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\xad\x1b*\xc0\xb1\xf3i(", "crc\x02`&\x9aR\xe1\xb7\xfee\xa7\x8a\xdb\xf6\xd2R\t\x96"}, + {0x3e05b21c7a4dc4da, 0x2fd681d7b2421fd, "The days of the digital watch are numbered. -Tom Stoppard", "crc\x02s\xba\x84\x84\xbb\xcd]\xefv78\x1ak\x02\x8f\xff", "crc\x02`&\x9aR\xe1\xb7\xfeeT\xcbl\x10\xfb\x87K*"}, + {0x5255866ad6ef28a6, 0x790ef2b16a745a41, "Nepal premier won't resign.", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\xcbf\x11R\xbfh\xde\xc9", "crc\x02`&\x9aR\xe1\xb7\xfee6\x13ُ\x06_\xbd\x9a"}, + {0x8a79895be1e9c361, 0x3ef8f06daccdcddf, "For every action there is an equal and opposite government program.", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\xf3pV\x01c_Wu", "crc\x02`&\x9aR\xe1\xb7\xfee\xe7\xc6\n\b\x12FL\xa0"}, + {0x8878963a649d4916, 0x49e41b2660b106d, "His money is twice tainted: 'taint yours and 'taint mine.", "crc\x02s\xba\x84\x84\xbb\xcd]\xefñ\xff\xf1\xe0/Δ", "crc\x02`&\x9aR\xe1\xb7\xfeeOL/\xb1\xec\xa2\x14\x87"}, + {0xa7b9d53ea87eb82f, 0x561cc0cfa235ac68, "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977", "crc\x02s\xba\x84\x84\xbb\xcd]\xefݸa\xe1\xb5\xf8\xb9W", "crc\x02`&\x9aR\xe1\xb7\xfee\x87)GQ\x03\xf4K\t"}, + {0xdb6805c0966a2f9c, 0xd4fe9ef082e69f59, "It's a tiny change to the code and not completely disgusting. - Bob Manchek", "crc\x02s\xba\x84\x84\xbb\xcd]\xefV\xba\x12\x91\x81\x1fNU", "crc\x02`&\x9aR\xe1\xb7\xfee\n\xb8\x81v?\xdeL\xcb"}, + {0xf3553c65dacdadd2, 0xe3b5e46cd8d63a4d, "size: a.out: bad magic", "crc\x02s\xba\x84\x84\xbb\xcd]\xefG\xad\xbc\xb2\xa8y\xc9\xdc", "crc\x02`&\x9aR\xe1\xb7\xfee\xcc\xce\xe5\xe6\x89p\x01\xb8"}, + {0x9d5e034087a676b9, 0x865aaf6b94f2a051, "The major problem is with sendmail. -Mark Horton", "crc\x02s\xba\x84\x84\xbb\xcd]\uf8acn\x8aT;&\xd5", "crc\x02`&\x9aR\xe1\xb7\xfeeFf\x9c\x1f\xc9x\xbfa"}, + {0xa6db2d7f8da96417, 0x7eca10d2f8136eb4, "Give me a rock, paper and scissors and I will move the world. CCFestoon", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\xeb\x18\xbf\xf9}\x91\xe5|", "crc\x02`&\x9aR\xe1\xb7\xfeea\x9e\x05:\xce[\xe7\x19"}, + {0x325e00cd2fe819f9, 0xd7dd118c98e98727, "If the enemy is within range, then so are you.", "crc\x02s\xba\x84\x84\xbb\xcd]\xef^5k\xd0Aj_{", "crc\x02`&\x9aR\xe1\xb7\xfee\v#\x99\xa8r\x83YR"}, + {0x88c6600ce58ae4c6, 0x70fb33c119c29318, "It's well we cannot hear the screams/That we create in others' dreams.", "crc\x02s\xba\x84\x84\xbb\xcd]\xef|\xb5\x02\xdcw\x18/\x86", "crc\x02`&\x9aR\xe1\xb7\xfee]\x9d-\xed\x8c\xf9r9"}, + {0x28c4a3f3b769e078, 0x57c891e39a97d9b7, "You remind me of a TV show, but that's all right: I watch it anyway.", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\x03\x8bd\x1c\xb0_\x16\x98", "crc\x02`&\x9aR\xe1\xb7\xfee\xafW\x98\xaa\"\xe7\xd7|"}, + {0xa698a34c9d9f1dca, 0xa1f46ba20ad06eb7, "C is as portable as Stonehedge!!", "crc\x02s\xba\x84\x84\xbb\xcd]\xef.P\xe1I\xc6pi\xdc", "crc\x02`&\x9aR\xe1\xb7\xfee֚\x06\x01(\xc0\x1e\x8b"}, + {0xf6c1e2a8c26c5cfc, 0x7ad25fafa1710407, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\xf7\xa04\x8a\xf2o\xe0;", "crc\x02`&\x9aR\xe1\xb7\xfee<[\xd2%\x9em\x94\x04"}, + {0xd402559dfe9b70c, 0x73cef1666185c13f, "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction. Lewis-Randall Rule", "crc\x02s\xba\x84\x84\xbb\xcd]\xef\u007f\xae\xb9\xbaX=\x19v", "crc\x02`&\x9aR\xe1\xb7\xfee\xb2˦Y\xc5\xd0G\x03"}, + {0xdb6efff26aa94946, 0xb41858f73c389602, "How can you write a big system without C++? -Paul Glick", "crc\x02s\xba\x84\x84\xbb\xcd]\xefa\xed$js\xb9\xa5A", "crc\x02`&\x9aR\xe1\xb7\xfeeZm\x96\x8a\xe2\xaf\x13p"}, + {0xe7fcf1006b503b61, 0x27db187fc15bbc72, "This is a test of the emergency broadcast system.", "crc\x02s\xba\x84\x84\xbb\xcd]\xef}\xee[q\x16\xcb\xe4\x8d", "crc\x02`&\x9aR\xe1\xb7\xfee\xb1\x93] \xeb\xa9am"}, +} + +func TestGolden(t *testing.T) { + tabISO := MakeTable(ISO) + tabECMA := MakeTable(ECMA) + for i := 0; i < len(golden); i++ { + g := golden[i] + c := New(tabISO) + io.WriteString(c, g.in) + s := c.Sum64() + if s != g.outISO { + t.Fatalf("ISO crc64(%s) = 0x%x want 0x%x", g.in, s, g.outISO) + } + c = New(tabECMA) + io.WriteString(c, g.in) + s = c.Sum64() + if s != g.outECMA { + t.Fatalf("ECMA crc64(%s) = 0x%x want 0x%x", g.in, s, g.outECMA) + } + } +} + +func TestGoldenMarshal(t *testing.T) { + t.Run("ISO", func(t *testing.T) { + table := MakeTable(ISO) + for _, g := range golden { + h := New(table) + h2 := New(table) + + io.WriteString(h, g.in[:len(g.in)/2]) + + state, err := h.(encoding.BinaryMarshaler).MarshalBinary() + if err != nil { + t.Errorf("could not marshal: %v", err) + continue + } + + if string(state) != g.halfStateISO { + t.Errorf("ISO crc64(%q) state = %q, want %q", g.in, state, g.halfStateISO) + continue + } + + if err := h2.(encoding.BinaryUnmarshaler).UnmarshalBinary(state); err != nil { + t.Errorf("could not unmarshal: %v", err) + continue + } + + io.WriteString(h, g.in[len(g.in)/2:]) + io.WriteString(h2, g.in[len(g.in)/2:]) + + if h.Sum64() != h2.Sum64() { + t.Errorf("ISO crc64(%s) = 0x%x != marshaled (0x%x)", g.in, h.Sum64(), h2.Sum64()) + } + } + }) + t.Run("ECMA", func(t *testing.T) { + table := MakeTable(ECMA) + for _, g := range golden { + h := New(table) + h2 := New(table) + + io.WriteString(h, g.in[:len(g.in)/2]) + + state, err := h.(encoding.BinaryMarshaler).MarshalBinary() + if err != nil { + t.Errorf("could not marshal: %v", err) + continue + } + + if string(state) != g.halfStateECMA { + t.Errorf("ECMA crc64(%q) state = %q, want %q", g.in, state, g.halfStateECMA) + continue + } + + if err := h2.(encoding.BinaryUnmarshaler).UnmarshalBinary(state); err != nil { + t.Errorf("could not unmarshal: %v", err) + continue + } + + io.WriteString(h, g.in[len(g.in)/2:]) + io.WriteString(h2, g.in[len(g.in)/2:]) + + if h.Sum64() != h2.Sum64() { + t.Errorf("ECMA crc64(%s) = 0x%x != marshaled (0x%x)", g.in, h.Sum64(), h2.Sum64()) + } + } + }) +} + +func TestMarshalTableMismatch(t *testing.T) { + h1 := New(MakeTable(ISO)) + h2 := New(MakeTable(ECMA)) + + state1, err := h1.(encoding.BinaryMarshaler).MarshalBinary() + if err != nil { + t.Errorf("could not marshal: %v", err) + } + + if err := h2.(encoding.BinaryUnmarshaler).UnmarshalBinary(state1); err == nil { + t.Errorf("no error when one was expected") + } +} + +func bench(b *testing.B, poly uint64, size int64) { + b.SetBytes(size) + data := make([]byte, size) + for i := range data { + data[i] = byte(i) + } + h := New(MakeTable(poly)) + in := make([]byte, 0, h.Size()) + + b.ResetTimer() + for i := 0; i < b.N; i++ { + h.Reset() + h.Write(data) + h.Sum(in) + } +} + +func BenchmarkCrc64(b *testing.B) { + b.Run("ISO64KB", func(b *testing.B) { + bench(b, ISO, 64<<10) + }) + b.Run("ISO4KB", func(b *testing.B) { + bench(b, ISO, 4<<10) + }) + b.Run("ISO1KB", func(b *testing.B) { + bench(b, ISO, 1<<10) + }) + b.Run("ECMA64KB", func(b *testing.B) { + bench(b, ECMA, 64<<10) + }) + b.Run("Random64KB", func(b *testing.B) { + bench(b, 0x777, 64<<10) + }) + b.Run("Random16KB", func(b *testing.B) { + bench(b, 0x777, 16<<10) + }) +} |