From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- libgo/go/hash/crc32/crc32.go | 111 ++++++++++++++++++++++++++++++++++++++ libgo/go/hash/crc32/crc32_test.go | 76 ++++++++++++++++++++++++++ 2 files changed, 187 insertions(+) create mode 100644 libgo/go/hash/crc32/crc32.go create mode 100644 libgo/go/hash/crc32/crc32_test.go (limited to 'libgo/go/hash/crc32') diff --git a/libgo/go/hash/crc32/crc32.go b/libgo/go/hash/crc32/crc32.go new file mode 100644 index 000000000..2ab0c5491 --- /dev/null +++ b/libgo/go/hash/crc32/crc32.go @@ -0,0 +1,111 @@ +// 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 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" +) + +// 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 + +// 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 +} + +// IEEETable is the table for the IEEE polynomial. +var IEEETable = MakeTable(IEEE) + +// 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 { + 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/libgo/go/hash/crc32/crc32_test.go b/libgo/go/hash/crc32/crc32_test.go new file mode 100644 index 000000000..cf5743c99 --- /dev/null +++ b/libgo/go/hash/crc32/crc32_test.go @@ -0,0 +1,76 @@ +// 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 { + out uint32 + in string +} + +var golden = []test{ + {0x0, ""}, + {0xe8b7be43, "a"}, + {0x9e83486d, "ab"}, + {0x352441c2, "abc"}, + {0xed82cd11, "abcd"}, + {0x8587d865, "abcde"}, + {0x4b8e39ef, "abcdef"}, + {0x312a6aa6, "abcdefg"}, + {0xaeef2a50, "abcdefgh"}, + {0x8da988af, "abcdefghi"}, + {0x3981703a, "abcdefghij"}, + {0x6b9cdfe7, "Discard medicine more than two years old."}, + {0xc90ef73f, "He who has a shady past knows that nice guys finish last."}, + {0xb902341f, "I wouldn't marry him with a ten foot pole."}, + {0x42080e8, "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave"}, + {0x154c6d11, "The days of the digital watch are numbered. -Tom Stoppard"}, + {0x4c418325, "Nepal premier won't resign."}, + {0x33955150, "For every action there is an equal and opposite government program."}, + {0x26216a4b, "His money is twice tainted: 'taint yours and 'taint mine."}, + {0x1abbe45e, "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977"}, + {0xc89a94f7, "It's a tiny change to the code and not completely disgusting. - Bob Manchek"}, + {0xab3abe14, "size: a.out: bad magic"}, + {0xbab102b6, "The major problem is with sendmail. -Mark Horton"}, + {0x999149d7, "Give me a rock, paper and scissors and I will move the world. CCFestoon"}, + {0x6d52a33c, "If the enemy is within range, then so are you."}, + {0x90631e8d, "It's well we cannot hear the screams/That we create in others' dreams."}, + {0x78309130, "You remind me of a TV show, but that's all right: I watch it anyway."}, + {0x7d0a377f, "C is as portable as Stonehedge!!"}, + {0x8c79fd79, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley"}, + {0xa20b7167, "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction. Lewis-Randall Rule"}, + {0x8e0bb443, "How can you write a big system without C++? -Paul Glick"}, +} + +func TestGolden(t *testing.T) { + for i := 0; i < len(golden); i++ { + g := golden[i] + c := NewIEEE() + io.WriteString(c, g.in) + s := c.Sum32() + if s != g.out { + t.Errorf("crc32(%s) = 0x%x want 0x%x", g.in, s, g.out) + t.FailNow() + } + } +} + +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() + + for i := 0; i < b.N; i++ { + c.Write(data) + } +} -- cgit v1.2.3