diff options
| author | Rob Pike <r@golang.org> | 2009-06-09 09:53:44 -0700 |
|---|---|---|
| committer | Rob Pike <r@golang.org> | 2009-06-09 09:53:44 -0700 |
| commit | d90e7cbac65c5792ce312ee82fbe03a5dfc98c6f (patch) | |
| tree | 7032a11d0cac2ae4d3e90f7a189b575b5a50f848 /src/lib/hash | |
| parent | bf5c0c957c3c3ea9add6cfd51b90c463cb4814b5 (diff) | |
| download | go-d90e7cbac65c5792ce312ee82fbe03a5dfc98c6f.tar.xz | |
mv src/lib to src/pkg
tests: all.bash passes, gobuild still works, godoc still works.
R=rsc
OCL=30096
CL=30102
Diffstat (limited to 'src/lib/hash')
| -rw-r--r-- | src/lib/hash/Makefile | 60 | ||||
| -rw-r--r-- | src/lib/hash/adler32/Makefile | 60 | ||||
| -rw-r--r-- | src/lib/hash/adler32/adler32.go | 96 | ||||
| -rw-r--r-- | src/lib/hash/adler32/adler32_test.go | 65 | ||||
| -rw-r--r-- | src/lib/hash/crc32/Makefile | 60 | ||||
| -rw-r--r-- | src/lib/hash/crc32/crc32.go | 120 | ||||
| -rw-r--r-- | src/lib/hash/crc32/crc32_test.go | 64 | ||||
| -rw-r--r-- | src/lib/hash/hash.go | 24 | ||||
| -rw-r--r-- | src/lib/hash/test_cases.txt | 31 | ||||
| -rw-r--r-- | src/lib/hash/test_gen.awk | 14 |
10 files changed, 0 insertions, 594 deletions
diff --git a/src/lib/hash/Makefile b/src/lib/hash/Makefile deleted file mode 100644 index bdbb6f347e..0000000000 --- a/src/lib/hash/Makefile +++ /dev/null @@ -1,60 +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. - -# DO NOT EDIT. Automatically generated by gobuild. -# gobuild -m >Makefile - -D= - -include $(GOROOT)/src/Make.$(GOARCH) -AR=gopack - -default: packages - -clean: - rm -rf *.[$(OS)] *.a [$(OS)].out _obj - -test: packages - gotest - -coverage: packages - gotest - 6cov -g `pwd` | grep -v '_test\.go:' - -%.$O: %.go - $(GC) -I_obj $*.go - -%.$O: %.c - $(CC) $*.c - -%.$O: %.s - $(AS) $*.s - -O1=\ - hash.$O\ - - -phases: a1 -_obj$D/hash.a: phases - -a1: $(O1) - $(AR) grc _obj$D/hash.a hash.$O - rm -f $(O1) - - -newpkg: clean - mkdir -p _obj$D - $(AR) grc _obj$D/hash.a - -$(O1): newpkg -$(O2): a1 - -nuke: clean - rm -f $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D/hash.a - -packages: _obj$D/hash.a - -install: packages - test -d $(GOROOT)/pkg && mkdir -p $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D - cp _obj$D/hash.a $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D/hash.a diff --git a/src/lib/hash/adler32/Makefile b/src/lib/hash/adler32/Makefile deleted file mode 100644 index 1341312591..0000000000 --- a/src/lib/hash/adler32/Makefile +++ /dev/null @@ -1,60 +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. - -# DO NOT EDIT. Automatically generated by gobuild. -# gobuild -m >Makefile - -D=/hash/ - -include $(GOROOT)/src/Make.$(GOARCH) -AR=gopack - -default: packages - -clean: - rm -rf *.[$(OS)] *.a [$(OS)].out _obj - -test: packages - gotest - -coverage: packages - gotest - 6cov -g `pwd` | grep -v '_test\.go:' - -%.$O: %.go - $(GC) -I_obj $*.go - -%.$O: %.c - $(CC) $*.c - -%.$O: %.s - $(AS) $*.s - -O1=\ - adler32.$O\ - - -phases: a1 -_obj$D/adler32.a: phases - -a1: $(O1) - $(AR) grc _obj$D/adler32.a adler32.$O - rm -f $(O1) - - -newpkg: clean - mkdir -p _obj$D - $(AR) grc _obj$D/adler32.a - -$(O1): newpkg -$(O2): a1 - -nuke: clean - rm -f $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D/adler32.a - -packages: _obj$D/adler32.a - -install: packages - test -d $(GOROOT)/pkg && mkdir -p $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D - cp _obj$D/adler32.a $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D/adler32.a diff --git a/src/lib/hash/adler32/adler32.go b/src/lib/hash/adler32/adler32.go deleted file mode 100644 index fbf9177f89..0000000000 --- a/src/lib/hash/adler32/adler32.go +++ /dev/null @@ -1,96 +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. - -// This package 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 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 i := 0; i < len(p); i++ { - a += uint32(p[i]); - 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/lib/hash/adler32/adler32_test.go b/src/lib/hash/adler32/adler32_test.go deleted file mode 100644 index ce49a110bb..0000000000 --- a/src/lib/hash/adler32/adler32_test.go +++ /dev/null @@ -1,65 +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 ( - "hash/adler32"; - "io"; - "testing"; -) - -type _Adler32Test struct { - out uint32; - in string; -} - -var golden = []_Adler32Test { - _Adler32Test{ 0x1, "" }, - _Adler32Test{ 0x620062, "a" }, - _Adler32Test{ 0x12600c4, "ab" }, - _Adler32Test{ 0x24d0127, "abc" }, - _Adler32Test{ 0x3d8018b, "abcd" }, - _Adler32Test{ 0x5c801f0, "abcde" }, - _Adler32Test{ 0x81e0256, "abcdef" }, - _Adler32Test{ 0xadb02bd, "abcdefg" }, - _Adler32Test{ 0xe000325, "abcdefgh" }, - _Adler32Test{ 0x118e038e, "abcdefghi" }, - _Adler32Test{ 0x158603f8, "abcdefghij" }, - _Adler32Test{ 0x3f090f02, "Discard medicine more than two years old." }, - _Adler32Test{ 0x46d81477, "He who has a shady past knows that nice guys finish last." }, - _Adler32Test{ 0x40ee0ee1, "I wouldn't marry him with a ten foot pole." }, - _Adler32Test{ 0x16661315, "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave" }, - _Adler32Test{ 0x5b2e1480, "The days of the digital watch are numbered. -Tom Stoppard" }, - _Adler32Test{ 0x8c3c09ea, "Nepal premier won't resign." }, - _Adler32Test{ 0x45ac18fd, "For every action there is an equal and opposite government program." }, - _Adler32Test{ 0x53c61462, "His money is twice tainted: 'taint yours and 'taint mine." }, - _Adler32Test{ 0x7e511e63, "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977" }, - _Adler32Test{ 0xe4801a6a, "It's a tiny change to the code and not completely disgusting. - Bob Manchek" }, - _Adler32Test{ 0x61b507df, "size: a.out: bad magic" }, - _Adler32Test{ 0xb8631171, "The major problem is with sendmail. -Mark Horton" }, - _Adler32Test{ 0x8b5e1904, "Give me a rock, paper and scissors and I will move the world. CCFestoon" }, - _Adler32Test{ 0x7cc6102b, "If the enemy is within range, then so are you." }, - _Adler32Test{ 0x700318e7, "It's well we cannot hear the screams/That we create in others' dreams." }, - _Adler32Test{ 0x1e601747, "You remind me of a TV show, but that's all right: I watch it anyway." }, - _Adler32Test{ 0xb55b0b09, "C is as portable as Stonehedge!!" }, - _Adler32Test{ 0x39111dd0, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley" }, - _Adler32Test{ 0x91dd304f, "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction. Lewis-Randall Rule" }, - _Adler32Test{ 0x2e5d1316, "How can you write a big system without C++? -Paul Glick" }, - _Adler32Test{ 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(); - } - } -} - diff --git a/src/lib/hash/crc32/Makefile b/src/lib/hash/crc32/Makefile deleted file mode 100644 index 08d4f5e4e0..0000000000 --- a/src/lib/hash/crc32/Makefile +++ /dev/null @@ -1,60 +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. - -# DO NOT EDIT. Automatically generated by gobuild. -# gobuild -m >Makefile - -D=/hash/ - -include $(GOROOT)/src/Make.$(GOARCH) -AR=gopack - -default: packages - -clean: - rm -rf *.[$(OS)] *.a [$(OS)].out _obj - -test: packages - gotest - -coverage: packages - gotest - 6cov -g `pwd` | grep -v '_test\.go:' - -%.$O: %.go - $(GC) -I_obj $*.go - -%.$O: %.c - $(CC) $*.c - -%.$O: %.s - $(AS) $*.s - -O1=\ - crc32.$O\ - - -phases: a1 -_obj$D/crc32.a: phases - -a1: $(O1) - $(AR) grc _obj$D/crc32.a crc32.$O - rm -f $(O1) - - -newpkg: clean - mkdir -p _obj$D - $(AR) grc _obj$D/crc32.a - -$(O1): newpkg -$(O2): a1 - -nuke: clean - rm -f $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D/crc32.a - -packages: _obj$D/crc32.a - -install: packages - test -d $(GOROOT)/pkg && mkdir -p $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D - cp _obj$D/crc32.a $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D/crc32.a diff --git a/src/lib/hash/crc32/crc32.go b/src/lib/hash/crc32/crc32.go deleted file mode 100644 index 22a0f68f6c..0000000000 --- a/src/lib/hash/crc32/crc32.go +++ /dev/null @@ -1,120 +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. - -// 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 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 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 i := 0; i < len(p); i++ { - crc = tab[byte(crc) ^ p[i]] ^ (crc >> 8); - } - return ^crc; -} - -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/lib/hash/crc32/crc32_test.go b/src/lib/hash/crc32/crc32_test.go deleted file mode 100644 index c037da600e..0000000000 --- a/src/lib/hash/crc32/crc32_test.go +++ /dev/null @@ -1,64 +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 ( - "hash/crc32"; - "io"; - "testing"; -) - -type _Crc32Test struct { - out uint32; - in string; -} - -var golden = []_Crc32Test { - _Crc32Test{ 0x0, "" }, - _Crc32Test{ 0xe8b7be43, "a" }, - _Crc32Test{ 0x9e83486d, "ab" }, - _Crc32Test{ 0x352441c2, "abc" }, - _Crc32Test{ 0xed82cd11, "abcd" }, - _Crc32Test{ 0x8587d865, "abcde" }, - _Crc32Test{ 0x4b8e39ef, "abcdef" }, - _Crc32Test{ 0x312a6aa6, "abcdefg" }, - _Crc32Test{ 0xaeef2a50, "abcdefgh" }, - _Crc32Test{ 0x8da988af, "abcdefghi" }, - _Crc32Test{ 0x3981703a, "abcdefghij" }, - _Crc32Test{ 0x6b9cdfe7, "Discard medicine more than two years old." }, - _Crc32Test{ 0xc90ef73f, "He who has a shady past knows that nice guys finish last." }, - _Crc32Test{ 0xb902341f, "I wouldn't marry him with a ten foot pole." }, - _Crc32Test{ 0x42080e8, "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave" }, - _Crc32Test{ 0x154c6d11, "The days of the digital watch are numbered. -Tom Stoppard" }, - _Crc32Test{ 0x4c418325, "Nepal premier won't resign." }, - _Crc32Test{ 0x33955150, "For every action there is an equal and opposite government program." }, - _Crc32Test{ 0x26216a4b, "His money is twice tainted: 'taint yours and 'taint mine." }, - _Crc32Test{ 0x1abbe45e, "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977" }, - _Crc32Test{ 0xc89a94f7, "It's a tiny change to the code and not completely disgusting. - Bob Manchek" }, - _Crc32Test{ 0xab3abe14, "size: a.out: bad magic" }, - _Crc32Test{ 0xbab102b6, "The major problem is with sendmail. -Mark Horton" }, - _Crc32Test{ 0x999149d7, "Give me a rock, paper and scissors and I will move the world. CCFestoon" }, - _Crc32Test{ 0x6d52a33c, "If the enemy is within range, then so are you." }, - _Crc32Test{ 0x90631e8d, "It's well we cannot hear the screams/That we create in others' dreams." }, - _Crc32Test{ 0x78309130, "You remind me of a TV show, but that's all right: I watch it anyway." }, - _Crc32Test{ 0x7d0a377f, "C is as portable as Stonehedge!!" }, - _Crc32Test{ 0x8c79fd79, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley" }, - _Crc32Test{ 0xa20b7167, "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction. Lewis-Randall Rule" }, - _Crc32Test{ 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(); - } - } -} - diff --git a/src/lib/hash/hash.go b/src/lib/hash/hash.go deleted file mode 100644 index a7c08cfed2..0000000000 --- a/src/lib/hash/hash.go +++ /dev/null @@ -1,24 +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 - -import "io"; - -// Hash is the common interface implemented by all hash functions. -// The Write method never returns an error. -// Sum returns the bytes of integer hash codes in big-endian order. -type Hash interface { - io.Writer; - Sum() []byte; - Reset(); - Size() int; // number of bytes Sum returns -} - -// Hash32 is the common interface implemented by all 32-bit hash functions. -type Hash32 interface { - Hash; - Sum32() uint32; -} - diff --git a/src/lib/hash/test_cases.txt b/src/lib/hash/test_cases.txt deleted file mode 100644 index 26d3ccc052..0000000000 --- a/src/lib/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/lib/hash/test_gen.awk b/src/lib/hash/test_gen.awk deleted file mode 100644 index 804f786795..0000000000 --- a/src/lib/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); -} |
