hash writers: adler32, crc32, md5, sha1.

all could probably be made faster.

R=r
DELTA=929  (929 added, 0 deleted, 0 changed)
OCL=19879
CL=19911

12 files changed, 842 insertions, 0 deletions

diff --git a/src/lib/hash/Makefile b/src/lib/hash/Makefile
new file mode 100644
index 000000000..589dbe5fc
--- /dev/null
+++ b/src/lib/hash/Makefile
@@ -0,0 +1,80 @@
+# 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
+O=6
+GC=$(O)g
+CC=$(O)c -w
+AS=$(O)a
+AR=$(O)ar
+
+default: packages
+
+clean:
+	rm -f *.$O *.a $O.out
+
+test: packages
+	gotest
+
+coverage: packages
+	gotest
+	6cov -g `pwd` | grep -v '_test\.go:'
+
+%.$O: %.go
+	$(GC) $*.go
+
+%.$O: %.c
+	$(CC) $*.c
+
+%.$O: %.s
+	$(AS) $*.s
+
+O1=\
+	adler32.$O\
+	crc32.$O\
+	sha1.$O\
+	md5.$O\
+
+O2=\
+	md5block.$O\
+	sha1block.$O\
+
+adler32.a: a1 a2
+crc32.a: a1 a2
+sha1.a: a1 a2
+md5.a: a1 a2
+
+a1:	$(O1)
+	$(AR) grc adler32.a adler32.$O
+	$(AR) grc crc32.a crc32.$O
+	$(AR) grc sha1.a sha1.$O
+	$(AR) grc md5.a md5.$O
+	rm -f $(O1)
+
+a2:	$(O2)
+	$(AR) grc sha1.a sha1block.$O
+	$(AR) grc md5.a md5block.$O
+	rm -f $(O2)
+
+newpkg: clean
+	$(AR) grc adler32.a
+	$(AR) grc crc32.a
+	$(AR) grc sha1.a
+	$(AR) grc md5.a
+
+$(O1): newpkg
+$(O2): a1
+
+nuke: clean
+	rm -f $(GOROOT)/pkg/adler32.a $(GOROOT)/pkg/crc32.a $(GOROOT)/pkg/sha1.a $(GOROOT)/pkg/md5.a
+
+packages: adler32.a crc32.a sha1.a md5.a
+
+install: packages
+	cp adler32.a $(GOROOT)/pkg/adler32.a
+	cp crc32.a $(GOROOT)/pkg/crc32.a
+	cp sha1.a $(GOROOT)/pkg/sha1.a
+	cp md5.a $(GOROOT)/pkg/md5.a
+
diff --git a/src/lib/hash/adler32.go b/src/lib/hash/adler32.go
new file mode 100644
index 000000000..426f961b8
--- /dev/null
+++ b/src/lib/hash/adler32.go
@@ -0,0 +1,62 @@
+// 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.
+
+// 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 "os"
+
+export type Digest struct {
+	a, b uint32;
+	n int;
+}
+
+const Mod = 65521;
+const Maxiter = 5552;	// max mod-free iterations before would overflow uint32
+
+export func NewDigest() *Digest {
+	return &Digest{1, 0, 0};
+}
+
+func (d *Digest) Write(p *[]byte) (nn int, err *os.Error) {
+	a, b, n := d.a, d.b, d.n;
+	for i := 0; i < len(p); i++ {
+		a += uint32(p[i]);
+		b += a;
+		n++;
+		if n == Maxiter {
+			a %= Mod;
+			b %= Mod;
+			n = 0;
+		}
+	}
+	d.a, d.b, d.n = a, b, n;
+	return len(p), nil
+}
+
+func (d *Digest) Sum32() uint32 {
+	a, b := d.a, d.b;
+	if a >= Mod || b >= Mod {
+		a %= Mod;
+		b %= Mod;
+	}
+	return b<<16 | a;
+}
+
+func (d *Digest) Sum() *[]byte {
+	p := new([]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;
+}
diff --git a/src/lib/hash/adler32_test.go b/src/lib/hash/adler32_test.go
new file mode 100644
index 000000000..4b5dab929
--- /dev/null
+++ b/src/lib/hash/adler32_test.go
@@ -0,0 +1,64 @@
+// 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 (
+	"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" },
+}
+
+export func TestGolden(t *testing.T) {
+	for i := 0; i < len(golden); i++ {
+		g := golden[i];
+		c := NewDigest();
+		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.go b/src/lib/hash/crc32.go
new file mode 100644
index 000000000..f3b60dc89
--- /dev/null
+++ b/src/lib/hash/crc32.go
@@ -0,0 +1,85 @@
+// 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.
+
+// CRC-32 checksum.
+// http://en.wikipedia.org/wiki/Cyclic_redundancy_check for links
+
+package crc32
+
+import "os"
+
+export 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;
+)
+
+export type Table [256]uint32
+
+export 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;
+}
+
+export var ieee = MakeTable(IEEE);
+
+export type Digest struct {
+	crc uint32;
+	tab *Table;
+}
+
+export func NewDigest(tab *Table) *Digest {
+	return &Digest{0, tab};
+}
+
+export func NewIEEEDigest() *Digest {
+	return NewDigest(ieee);
+}
+
+func (d *Digest) Write(p *[]byte) (n int, err *os.Error) {
+	crc := d.crc ^ 0xFFFFFFFF;
+	tab := d.tab;
+	for i := 0; i < len(p); i++ {
+		crc = tab[byte(crc) ^ p[i]] ^ (crc >> 8);
+	}
+	d.crc = crc ^ 0xFFFFFFFF;
+	return len(p), nil;
+}
+
+func (d *Digest) Sum32() uint32 {
+	return d.crc
+}
+
+func (d *Digest) Sum() *[]byte {
+	p := new([]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;
+}
+
+
diff --git a/src/lib/hash/crc32_test.go b/src/lib/hash/crc32_test.go
new file mode 100644
index 000000000..c1c0b565f
--- /dev/null
+++ b/src/lib/hash/crc32_test.go
@@ -0,0 +1,64 @@
+// 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 (
+	"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" },
+}
+
+export func TestGolden(t *testing.T) {
+	for i := 0; i < len(golden); i++ {
+		g := golden[i];
+		c := NewIEEEDigest();
+		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/md5.go b/src/lib/hash/md5.go
new file mode 100644
index 000000000..c977656b6
--- /dev/null
+++ b/src/lib/hash/md5.go
@@ -0,0 +1,102 @@
+// 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.
+
+// MD5 hash algorithm.  See RFC 1321.
+
+package md5
+
+import "os"
+
+package const (
+	Chunk = 64
+)
+
+const (
+	A = 0x67452301;
+	B = 0xEFCDAB89;
+	C = 0x98BADCFE;
+	D = 0x10325476;
+)
+
+export type Digest struct {
+	s [4]uint32;
+	x [Chunk]byte;
+	nx int;
+	len uint64;
+}
+
+export func NewDigest() *Digest {
+	d := new(Digest);
+	d.s[0] = A;
+	d.s[1] = B;
+	d.s[2] = C;
+	d.s[3] = D;
+	return d;
+}
+
+package func Block(dig *Digest, p *[]byte) int
+
+func (d *Digest) Write(p *[]byte) (nn int, err *os.Error) {
+	nn = len(p);
+	d.len += uint64(nn);
+	if d.nx > 0 {
+		n := len(p);
+		if n > Chunk-d.nx {
+			n = Chunk-d.nx;
+		}
+		for i := 0; i < n; i++ {
+			d.x[d.nx+i] = p[i];
+		}
+		d.nx += n;
+		if d.nx == Chunk {
+			Block(d, &d.x);
+			d.nx = 0;
+		}
+		p = p[n:len(p)];
+	}
+	n := Block(d, p);
+	p = p[n:len(p)];
+	if len(p) > 0 {
+		for i := 0; i < len(p); i++ {
+			d.x[i] = p[i];
+		}
+		d.nx = len(p);
+	}
+	return;
+}
+
+func (d *Digest) Sum() *[]byte {
+	// Padding.  Add a 1 bit and 0 bits until 56 bytes mod 64.
+	len := d.len;
+	var tmp [64]byte;
+	tmp[0] = 0x80;
+	if len%64 < 56 {
+		d.Write((&tmp)[0:56-len%64]);
+	} else {
+		d.Write((&tmp)[0:64+56-len%64]);
+	}
+
+	// Length in bits.
+	len <<= 3;
+	for i := uint(0); i < 8; i++ {
+		tmp[i] = byte(len>>(8*i));
+	}
+	d.Write((&tmp)[0:8]);
+
+	if d.nx != 0 {
+		panicln("oops");
+	}
+
+	p := new([]byte, 16);
+	j := 0;
+	for i := 0; i < 4; i++ {
+		s := d.s[i];
+		p[j] = byte(s); j++;
+		p[j] = byte(s>>8); j++;
+		p[j] = byte(s>>16); j++;
+		p[j] = byte(s>>24); j++;
+	}
+	return p;
+}
+
diff --git a/src/lib/hash/md5_test.go b/src/lib/hash/md5_test.go
new file mode 100644
index 000000000..c0b7ffa9b
--- /dev/null
+++ b/src/lib/hash/md5_test.go
@@ -0,0 +1,74 @@
+// 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 md5
+
+import (
+	"md5";
+	"io";
+	"testing";
+)
+
+type Md5Test struct {
+	out string;
+	in string;
+}
+
+var golden = []Md5Test {
+	Md5Test{ "d41d8cd98f00b204e9800998ecf8427e", "" },
+	Md5Test{ "0cc175b9c0f1b6a831c399e269772661", "a" },
+	Md5Test{ "187ef4436122d1cc2f40dc2b92f0eba0", "ab" },
+	Md5Test{ "900150983cd24fb0d6963f7d28e17f72", "abc" },
+	Md5Test{ "e2fc714c4727ee9395f324cd2e7f331f", "abcd" },
+	Md5Test{ "ab56b4d92b40713acc5af89985d4b786", "abcde" },
+	Md5Test{ "e80b5017098950fc58aad83c8c14978e", "abcdef" },
+	Md5Test{ "7ac66c0f148de9519b8bd264312c4d64", "abcdefg" },
+	Md5Test{ "e8dc4081b13434b45189a720b77b6818", "abcdefgh" },
+	Md5Test{ "8aa99b1f439ff71293e95357bac6fd94", "abcdefghi" },
+	Md5Test{ "a925576942e94b2ef57a066101b48876", "abcdefghij" },
+	Md5Test{ "d747fc1719c7eacb84058196cfe56d57", "Discard medicine more than two years old." },
+	Md5Test{ "bff2dcb37ef3a44ba43ab144768ca837", "He who has a shady past knows that nice guys finish last." },
+	Md5Test{ "0441015ecb54a7342d017ed1bcfdbea5", "I wouldn't marry him with a ten foot pole." },
+	Md5Test{ "9e3cac8e9e9757a60c3ea391130d3689", "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave" },
+	Md5Test{ "a0f04459b031f916a59a35cc482dc039", "The days of the digital watch are numbered.  -Tom Stoppard" },
+	Md5Test{ "e7a48e0fe884faf31475d2a04b1362cc", "Nepal premier won't resign." },
+	Md5Test{ "637d2fe925c07c113800509964fb0e06", "For every action there is an equal and opposite government program." },
+	Md5Test{ "834a8d18d5c6562119cf4c7f5086cb71", "His money is twice tainted: 'taint yours and 'taint mine." },
+	Md5Test{ "de3a4d2fd6c73ec2db2abad23b444281", "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977" },
+	Md5Test{ "acf203f997e2cf74ea3aff86985aefaf", "It's a tiny change to the code and not completely disgusting. - Bob Manchek" },
+	Md5Test{ "e1c1384cb4d2221dfdd7c795a4222c9a", "size:  a.out:  bad magic" },
+	Md5Test{ "c90f3ddecc54f34228c063d7525bf644", "The major problem is with sendmail.  -Mark Horton" },
+	Md5Test{ "cdf7ab6c1fd49bd9933c43f3ea5af185", "Give me a rock, paper and scissors and I will move the world.  CCFestoon" },
+	Md5Test{ "83bc85234942fc883c063cbd7f0ad5d0", "If the enemy is within range, then so are you." },
+	Md5Test{ "277cbe255686b48dd7e8f389394d9299", "It's well we cannot hear the screams/That we create in others' dreams." },
+	Md5Test{ "fd3fb0a7ffb8af16603f3d3af98f8e1f", "You remind me of a TV show, but that's all right: I watch it anyway." },
+	Md5Test{ "469b13a78ebf297ecda64d4723655154", "C is as portable as Stonehedge!!" },
+	Md5Test{ "63eb3a2f466410104731c4b037600110", "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley" },
+	Md5Test{ "72c2ed7592debca1c90fc0100f931a2f", "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction.  Lewis-Randall Rule" },
+	Md5Test{ "132f7619d33b523b1d9e5bd8e0928355", "How can you write a big system without C++?  -Paul Glick" },
+}
+
+func Hex(p *[]byte) string {
+	s := "";
+	for i := 0; i < len(p); i++ {
+		v := p[i];
+		s += string("0123456789abcdef"[v>>4]);
+		s += string("0123456789abcdef"[v&15]);
+	}
+	return s;
+}
+
+export func TestGolden(t *testing.T) {
+	for i := 0; i < len(golden); i++ {
+		g := golden[i];
+		c := NewDigest();
+		io.WriteString(c, g.in);
+		s := Hex(c.Sum());
+		if s != g.out {
+			t.Errorf("md5(%s) = %s want %s", g.in, s, g.out);
+			t.FailNow();
+		}
+	}
+}
+
diff --git a/src/lib/hash/sha1.go b/src/lib/hash/sha1.go
new file mode 100644
index 000000000..fdd33e759
--- /dev/null
+++ b/src/lib/hash/sha1.go
@@ -0,0 +1,104 @@
+// 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.
+
+// SHA1 hash algorithm.  See RFC 3174.
+
+package sha1
+
+import "os"
+
+package const (
+	Chunk = 64;
+)
+
+const (
+	H0 = 0x67452301;
+	H1 = 0xEFCDAB89;
+	H2 = 0x98BADCFE;
+	H3 = 0x10325476;
+	H4 = 0xC3D2E1F0;
+)
+
+export type Digest struct {
+	h [5]uint32;
+	x [Chunk]byte;
+	nx int;
+	len uint64;
+}
+
+export func NewDigest() *Digest {
+	d := new(Digest);
+	d.h[0] = H0;
+	d.h[1] = H1;
+	d.h[2] = H2;
+	d.h[3] = H3;
+	d.h[4] = H4;
+	return d;
+}
+
+package func Block(dig *Digest, p *[]byte) int
+
+func (d *Digest) Write(p *[]byte) (nn int, err *os.Error) {
+	nn = len(p);
+	d.len += uint64(nn);
+	if d.nx > 0 {
+		n := len(p);
+		if n > Chunk-d.nx {
+			n = Chunk-d.nx;
+		}
+		for i := 0; i < n; i++ {
+			d.x[d.nx+i] = p[i];
+		}
+		d.nx += n;
+		if d.nx == Chunk {
+			Block(d, &d.x);
+			d.nx = 0;
+		}
+		p = p[n:len(p)];
+	}
+	n := Block(d, p);
+	p = p[n:len(p)];
+	if len(p) > 0 {
+		for i := 0; i < len(p); i++ {
+			d.x[i] = p[i];
+		}
+		d.nx = len(p);
+	}
+	return;
+}
+
+func (d *Digest) Sum() *[]byte {
+	// Padding.  Add a 1 bit and 0 bits until 56 bytes mod 64.
+	len := d.len;
+	var tmp [64]byte;
+	tmp[0] = 0x80;
+	if len%64 < 56 {
+		d.Write((&tmp)[0:56-len%64]);
+	} else {
+		d.Write((&tmp)[0:64+56-len%64]);
+	}
+
+	// Length in bits.
+	len <<= 3;
+	for i := uint(0); i < 8; i++ {
+		tmp[i] = byte(len>>(56-8*i));
+	}
+	d.Write((&tmp)[0:8]);
+
+	if d.nx != 0 {
+		panicln("oops");
+	}
+
+	p := new([]byte, 20);
+	j := 0;
+	for i := 0; i < 5; i++ {
+		s := d.h[i];
+		p[j] = byte(s>>24); j++;
+		p[j] = byte(s>>16); j++;
+		p[j] = byte(s>>8); j++;
+		p[j] = byte(s); j++;
+	}
+	return p;
+}
+
diff --git a/src/lib/hash/sha1_test.go b/src/lib/hash/sha1_test.go
new file mode 100644
index 000000000..dacce5512
--- /dev/null
+++ b/src/lib/hash/sha1_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.
+
+// SHA1 hash algorithm.  See RFC 3174.
+
+package sha1
+
+import (
+	"sha1";
+	"io";
+	"testing";
+)
+
+type Sha1Test struct {
+	out string;
+	in string;
+}
+
+var golden = []Sha1Test {
+	Sha1Test{ "da39a3ee5e6b4b0d3255bfef95601890afd80709", "" },
+	Sha1Test{ "86f7e437faa5a7fce15d1ddcb9eaeaea377667b8", "a" },
+	Sha1Test{ "da23614e02469a0d7c7bd1bdab5c9c474b1904dc", "ab" },
+	Sha1Test{ "a9993e364706816aba3e25717850c26c9cd0d89d", "abc" },
+	Sha1Test{ "81fe8bfe87576c3ecb22426f8e57847382917acf", "abcd" },
+	Sha1Test{ "03de6c570bfe24bfc328ccd7ca46b76eadaf4334", "abcde" },
+	Sha1Test{ "1f8ac10f23c5b5bc1167bda84b833e5c057a77d2", "abcdef" },
+	Sha1Test{ "2fb5e13419fc89246865e7a324f476ec624e8740", "abcdefg" },
+	Sha1Test{ "425af12a0743502b322e93a015bcf868e324d56a", "abcdefgh" },
+	Sha1Test{ "c63b19f1e4c8b5f76b25c49b8b87f57d8e4872a1", "abcdefghi" },
+	Sha1Test{ "d68c19a0a345b7eab78d5e11e991c026ec60db63", "abcdefghij" },
+	Sha1Test{ "ebf81ddcbe5bf13aaabdc4d65354fdf2044f38a7", "Discard medicine more than two years old." },
+	Sha1Test{ "e5dea09392dd886ca63531aaa00571dc07554bb6", "He who has a shady past knows that nice guys finish last." },
+	Sha1Test{ "45988f7234467b94e3e9494434c96ee3609d8f8f", "I wouldn't marry him with a ten foot pole." },
+	Sha1Test{ "55dee037eb7460d5a692d1ce11330b260e40c988", "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave" },
+	Sha1Test{ "b7bc5fb91080c7de6b582ea281f8a396d7c0aee8", "The days of the digital watch are numbered.  -Tom Stoppard" },
+	Sha1Test{ "c3aed9358f7c77f523afe86135f06b95b3999797", "Nepal premier won't resign." },
+	Sha1Test{ "6e29d302bf6e3a5e4305ff318d983197d6906bb9", "For every action there is an equal and opposite government program." },
+	Sha1Test{ "597f6a540010f94c15d71806a99a2c8710e747bd", "His money is twice tainted: 'taint yours and 'taint mine." },
+	Sha1Test{ "6859733b2590a8a091cecf50086febc5ceef1e80", "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977" },
+	Sha1Test{ "514b2630ec089b8aee18795fc0cf1f4860cdacad", "It's a tiny change to the code and not completely disgusting. - Bob Manchek" },
+	Sha1Test{ "c5ca0d4a7b6676fc7aa72caa41cc3d5df567ed69", "size:  a.out:  bad magic" },
+	Sha1Test{ "74c51fa9a04eadc8c1bbeaa7fc442f834b90a00a", "The major problem is with sendmail.  -Mark Horton" },
+	Sha1Test{ "0b4c4ce5f52c3ad2821852a8dc00217fa18b8b66", "Give me a rock, paper and scissors and I will move the world.  CCFestoon" },
+	Sha1Test{ "3ae7937dd790315beb0f48330e8642237c61550a", "If the enemy is within range, then so are you." },
+	Sha1Test{ "410a2b296df92b9a47412b13281df8f830a9f44b", "It's well we cannot hear the screams/That we create in others' dreams." },
+	Sha1Test{ "841e7c85ca1adcddbdd0187f1289acb5c642f7f5", "You remind me of a TV show, but that's all right: I watch it anyway." },
+	Sha1Test{ "163173b825d03b952601376b25212df66763e1db", "C is as portable as Stonehedge!!" },
+	Sha1Test{ "32b0377f2687eb88e22106f133c586ab314d5279", "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley" },
+	Sha1Test{ "0885aaf99b569542fd165fa44e322718f4a984e0", "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction.  Lewis-Randall Rule" },
+	Sha1Test{ "6627d6904d71420b0bf3886ab629623538689f45", "How can you write a big system without C++?  -Paul Glick" },
+}
+
+func Hex(p *[]byte) string {
+	s := "";
+	for i := 0; i < len(p); i++ {
+		v := p[i];
+		s += string("0123456789abcdef"[v>>4]);
+		s += string("0123456789abcdef"[v&15]);
+	}
+	return s;
+}
+
+export func TestGolden(t *testing.T) {
+	for i := 0; i < len(golden); i++ {
+		g := golden[i];
+		c := NewDigest();
+		io.WriteString(c, g.in);
+		s := Hex(c.Sum());
+		if s != g.out {
+			t.Errorf("sha1(%s) = %s want %s", g.in, s, g.out);
+			t.FailNow();
+		}
+	}
+}
+
diff --git a/src/lib/hash/sha1block.go b/src/lib/hash/sha1block.go
new file mode 100644
index 000000000..a81dceb69
--- /dev/null
+++ b/src/lib/hash/sha1block.go
@@ -0,0 +1,86 @@
+// 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.
+
+// SHA1 block step.
+// In its own file so that a faster assembly or C version
+// can be substituted easily.
+
+package sha1
+
+import "sha1"
+
+const (
+	K0 = 0x5A827999;
+	K1 = 0x6ED9EBA1;
+	K2 = 0x8F1BBCDC;
+	K3 = 0xCA62C1D6;
+)
+
+package func Block(dig *Digest, p *[]byte) int {
+	var w [80]uint32;
+
+	n := 0;
+	h0, h1, h2, h3, h4 := dig.h[0], dig.h[1], dig.h[2], dig.h[3], dig.h[4];
+	for len(p) >= Chunk {
+		// Can interlace the computation of w with the
+		// rounds below if needed for speed.
+		for i := 0; i < 16; i++ {
+			j := i*4;
+			w[i] = uint32(p[j])<<24 |
+				uint32(p[j+1])<<16 |
+				uint32(p[j+2])<<8 |
+				uint32(p[j+3]);
+		}
+		for i := 16; i < 80; i++ {
+			tmp := w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16];
+			w[i] = tmp<<1 | tmp>>(32-1);
+		}
+
+		a, b, c, d, e := h0, h1, h2, h3, h4;
+
+		// Each of the four 20-iteration rounds
+		// differs only in the computation of f and
+		// the choice of K (K0, K1, etc).
+		for i := 0; i < 20; i++ {
+			f := b&c | (^b)&d;
+			a5 := a<<5 | a>>(32-5);
+			b30 := b<<30 | b>>(32-30);
+			t := a5 + f + e + w[i] + K0;
+			a, b, c, d, e = t, a, b30, c, d;
+		}
+		for i := 20; i < 40; i++ {
+			f := b ^ c ^ d;
+			a5 := a<<5 | a>>(32-5);
+			b30 := b<<30 | b>>(32-30);
+			t := a5 + f + e + w[i] + K1;
+			a, b, c, d, e = t, a, b30, c, d;
+		}
+		for i := 40; i < 60; i++ {
+			f := b&c | b&d | c&d;
+			a5 := a<<5 | a>>(32-5);
+			b30 := b<<30 | b>>(32-30);
+			t := a5 + f + e + w[i] + K2;
+			a, b, c, d, e = t, a, b30, c, d;
+		}
+		for i := 60; i < 80; i++ {
+			f := b ^ c ^ d;
+			a5 := a<<5 | a>>(32-5);
+			b30 := b<<30 | b>>(32-30);
+			t := a5 + f + e + w[i] + K3;
+			a, b, c, d, e = t, a, b30, c, d;
+		}
+
+		h0 += a;
+		h1 += b;
+		h2 += c;
+		h3 += d;
+		h4 += e;
+
+		p = p[Chunk:len(p)];
+		n += Chunk;
+	}
+
+	dig.h[0], dig.h[1], dig.h[2], dig.h[3], dig.h[4] = h0, h1, h2, h3, h4;
+	return n;
+}
diff --git a/src/lib/hash/test_cases.txt b/src/lib/hash/test_cases.txt
new file mode 100644
index 000000000..26d3ccc05
--- /dev/null
+++ b/src/lib/hash/test_cases.txt
@@ -0,0 +1,31 @@
+
+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
new file mode 100644
index 000000000..804f78679
--- /dev/null
+++ b/src/lib/hash/test_gen.awk
@@ -0,0 +1,14 @@
+# 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);
+}