aboutsummaryrefslogtreecommitdiff
path: root/src/lib/hash
diff options
context:
space:
mode:
authorRob Pike <r@golang.org>2009-06-09 09:53:44 -0700
committerRob Pike <r@golang.org>2009-06-09 09:53:44 -0700
commitd90e7cbac65c5792ce312ee82fbe03a5dfc98c6f (patch)
tree7032a11d0cac2ae4d3e90f7a189b575b5a50f848 /src/lib/hash
parentbf5c0c957c3c3ea9add6cfd51b90c463cb4814b5 (diff)
downloadgo-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/Makefile60
-rw-r--r--src/lib/hash/adler32/Makefile60
-rw-r--r--src/lib/hash/adler32/adler32.go96
-rw-r--r--src/lib/hash/adler32/adler32_test.go65
-rw-r--r--src/lib/hash/crc32/Makefile60
-rw-r--r--src/lib/hash/crc32/crc32.go120
-rw-r--r--src/lib/hash/crc32/crc32_test.go64
-rw-r--r--src/lib/hash/hash.go24
-rw-r--r--src/lib/hash/test_cases.txt31
-rw-r--r--src/lib/hash/test_gen.awk14
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);
-}