OSDN Git Service

Update to current version of Go library (revision 94d654be2064).
authorian <ian@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 16 Mar 2011 23:05:44 +0000 (23:05 +0000)
committerian <ian@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 16 Mar 2011 23:05:44 +0000 (23:05 +0000)
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@171076 138bc75d-0d04-0410-961f-82ee72b054a4

293 files changed:
gcc/go/gofrontend/types.cc
libgo/MERGE
libgo/Makefile.am
libgo/Makefile.in
libgo/go/archive/zip/reader.go
libgo/go/archive/zip/reader_test.go
libgo/go/archive/zip/struct.go
libgo/go/asn1/marshal.go
libgo/go/bufio/bufio.go
libgo/go/bytes/buffer.go
libgo/go/bytes/buffer_test.go
libgo/go/compress/bzip2/bit_reader.go [new file with mode: 0644]
libgo/go/compress/bzip2/bzip2.go [new file with mode: 0644]
libgo/go/compress/bzip2/bzip2_test.go [new file with mode: 0644]
libgo/go/compress/bzip2/huffman.go [new file with mode: 0644]
libgo/go/compress/bzip2/move_to_front.go [new file with mode: 0644]
libgo/go/compress/flate/deflate_test.go
libgo/go/compress/lzw/reader.go [new file with mode: 0644]
libgo/go/compress/lzw/reader_test.go [new file with mode: 0644]
libgo/go/compress/lzw/writer.go [new file with mode: 0644]
libgo/go/compress/lzw/writer_test.go [new file with mode: 0644]
libgo/go/compress/testdata/e.txt [new file with mode: 0644]
libgo/go/compress/testdata/pi.txt [new file with mode: 0644]
libgo/go/compress/zlib/writer_test.go
libgo/go/container/ring/ring.go
libgo/go/container/ring/ring_test.go
libgo/go/crypto/cipher/ocfb.go
libgo/go/crypto/cipher/ocfb_test.go
libgo/go/crypto/crypto.go [new file with mode: 0644]
libgo/go/crypto/dsa/dsa.go [new file with mode: 0644]
libgo/go/crypto/dsa/dsa_test.go [new file with mode: 0644]
libgo/go/crypto/md4/md4.go
libgo/go/crypto/md5/md5.go
libgo/go/crypto/ocsp/ocsp.go
libgo/go/crypto/openpgp/armor/armor.go
libgo/go/crypto/openpgp/armor/armor_test.go
libgo/go/crypto/openpgp/armor/encode.go
libgo/go/crypto/openpgp/canonical_text.go [new file with mode: 0644]
libgo/go/crypto/openpgp/canonical_text_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/error/error.go
libgo/go/crypto/openpgp/keys.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/compressed.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/compressed_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/encrypted_key.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/encrypted_key_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/literal.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/one_pass_signature.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/packet.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/packet_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/private_key.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/private_key_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/public_key.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/public_key_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/reader.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/signature.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/signature_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/symmetric_key_encrypted.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/symmetric_key_encrypted_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/symmetrically_encrypted.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/symmetrically_encrypted_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/userid.go [new file with mode: 0644]
libgo/go/crypto/openpgp/packet/userid_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/read.go [new file with mode: 0644]
libgo/go/crypto/openpgp/read_test.go [new file with mode: 0644]
libgo/go/crypto/openpgp/s2k/s2k.go
libgo/go/crypto/openpgp/write.go [new file with mode: 0644]
libgo/go/crypto/openpgp/write_test.go [new file with mode: 0644]
libgo/go/crypto/rand/rand_unix.go
libgo/go/crypto/rand/rand_windows.go
libgo/go/crypto/ripemd160/ripemd160.go
libgo/go/crypto/rsa/pkcs1v15.go
libgo/go/crypto/rsa/pkcs1v15_test.go
libgo/go/crypto/rsa/rsa.go
libgo/go/crypto/rsa/rsa_test.go
libgo/go/crypto/sha1/sha1.go
libgo/go/crypto/sha256/sha256.go
libgo/go/crypto/sha512/sha512.go
libgo/go/crypto/tls/handshake_client.go
libgo/go/crypto/tls/handshake_client_test.go
libgo/go/crypto/tls/handshake_server.go
libgo/go/crypto/tls/handshake_server_test.go
libgo/go/crypto/tls/key_agreement.go
libgo/go/crypto/tls/tls.go
libgo/go/crypto/x509/x509.go
libgo/go/crypto/x509/x509_test.go
libgo/go/debug/pe/file.go
libgo/go/ebnf/ebnf_test.go
libgo/go/encoding/binary/binary.go
libgo/go/encoding/line/line.go
libgo/go/encoding/line/line_test.go
libgo/go/exec/exec.go
libgo/go/exec/lp_test.go [new file with mode: 0644]
libgo/go/exec/lp_unix.go
libgo/go/exec/lp_windows.go
libgo/go/exp/draw/x11/conn.go
libgo/go/exp/eval/stmt.go
libgo/go/exp/eval/stmt_test.go
libgo/go/exp/wingui/gui.go [new file with mode: 0644]
libgo/go/exp/wingui/winapi.go [new file with mode: 0644]
libgo/go/exp/wingui/zwinapi.go [new file with mode: 0644]
libgo/go/flag/flag.go
libgo/go/flag/flag_test.go
libgo/go/fmt/doc.go
libgo/go/fmt/fmt_test.go
libgo/go/fmt/print.go
libgo/go/fmt/scan.go
libgo/go/fmt/scan_test.go
libgo/go/go/ast/ast.go
libgo/go/go/ast/walk.go
libgo/go/go/parser/parser.go
libgo/go/go/parser/parser_test.go
libgo/go/go/printer/nodes.go
libgo/go/go/printer/printer.go
libgo/go/go/printer/printer_test.go
libgo/go/go/printer/testdata/expressions.golden
libgo/go/go/printer/testdata/expressions.input
libgo/go/go/printer/testdata/expressions.raw
libgo/go/go/printer/testdata/statements.golden
libgo/go/go/printer/testdata/statements.input
libgo/go/go/scanner/scanner.go
libgo/go/go/scanner/scanner_test.go
libgo/go/go/token/position.go
libgo/go/go/token/position_test.go
libgo/go/go/token/token.go
libgo/go/gob/codec_test.go
libgo/go/gob/decode.go
libgo/go/gob/decoder.go
libgo/go/gob/doc.go
libgo/go/gob/encode.go
libgo/go/gob/encoder.go
libgo/go/gob/encoder_test.go
libgo/go/gob/type.go
libgo/go/html/doc.go
libgo/go/html/token.go
libgo/go/html/token_test.go
libgo/go/http/client.go
libgo/go/http/client_test.go
libgo/go/http/fs.go
libgo/go/http/fs_test.go
libgo/go/http/header.go [new file with mode: 0644]
libgo/go/http/persist.go
libgo/go/http/proxy_test.go [new file with mode: 0644]
libgo/go/http/readrequest_test.go
libgo/go/http/request.go
libgo/go/http/request_test.go
libgo/go/http/requestwrite_test.go
libgo/go/http/response.go
libgo/go/http/response_test.go
libgo/go/http/responsewrite_test.go
libgo/go/http/serve_test.go
libgo/go/http/server.go
libgo/go/http/transfer.go
libgo/go/http/transport.go [new file with mode: 0644]
libgo/go/image/decode_test.go [new file with mode: 0644]
libgo/go/image/png/reader.go
libgo/go/image/png/reader_test.go
libgo/go/image/png/testdata/pngsuite/README
libgo/go/image/png/testdata/pngsuite/basn0g01-30.sng [new file with mode: 0644]
libgo/go/image/png/testdata/pngsuite/basn0g01.sng
libgo/go/image/png/testdata/pngsuite/basn0g02-29.sng [new file with mode: 0644]
libgo/go/image/png/testdata/pngsuite/basn0g02.sng
libgo/go/image/png/testdata/pngsuite/basn0g04-31.sng [new file with mode: 0644]
libgo/go/image/png/testdata/pngsuite/basn0g04.sng
libgo/go/image/png/testdata/pngsuite/basn3p02.sng
libgo/go/image/png/testdata/pngsuite/basn3p04.sng
libgo/go/image/png/testdata/pngsuite/basn4a08.sng
libgo/go/index/suffixarray/qsufsort.go
libgo/go/index/suffixarray/suffixarray.go
libgo/go/index/suffixarray/suffixarray_test.go
libgo/go/io/io.go
libgo/go/io/ioutil/tempfile.go
libgo/go/io/ioutil/tempfile_test.go
libgo/go/json/decode.go
libgo/go/json/decode_test.go
libgo/go/json/encode.go
libgo/go/json/scanner.go
libgo/go/log/log.go
libgo/go/net/dial.go
libgo/go/net/dnsclient.go
libgo/go/net/fd.go
libgo/go/net/fd_windows.go
libgo/go/net/iprawsock.go
libgo/go/net/ipsock.go
libgo/go/net/multicast_test.go [new file with mode: 0644]
libgo/go/net/net.go
libgo/go/net/parse.go
libgo/go/net/server_test.go
libgo/go/net/textproto/header.go [new file with mode: 0644]
libgo/go/net/textproto/reader.go
libgo/go/net/textproto/reader_test.go
libgo/go/net/udpsock.go
libgo/go/netchan/common.go
libgo/go/netchan/export.go
libgo/go/netchan/import.go
libgo/go/netchan/netchan_test.go
libgo/go/os/env_windows.go
libgo/go/os/error.go
libgo/go/os/exec.go
libgo/go/os/exec_unix.go [new file with mode: 0644]
libgo/go/os/exec_windows.go [new file with mode: 0644]
libgo/go/os/inotify/inotify_linux.go
libgo/go/os/os_test.go
libgo/go/path/path_test.go
libgo/go/reflect/all_test.go
libgo/go/reflect/deepequal.go
libgo/go/reflect/type.go
libgo/go/reflect/value.go
libgo/go/regexp/all_test.go
libgo/go/regexp/find_test.go
libgo/go/regexp/regexp.go
libgo/go/rpc/client.go
libgo/go/rpc/debug.go
libgo/go/rpc/jsonrpc/client.go
libgo/go/rpc/jsonrpc/server.go
libgo/go/rpc/server.go
libgo/go/rpc/server_test.go
libgo/go/runtime/chan_defs.go [deleted file]
libgo/go/runtime/debug.go
libgo/go/runtime/extern.go
libgo/go/runtime/hashmap_defs.go [deleted file]
libgo/go/runtime/iface_defs.go [deleted file]
libgo/go/runtime/malloc_defs.go [deleted file]
libgo/go/runtime/mheapmap32_defs.go [deleted file]
libgo/go/runtime/mheapmap64_defs.go [deleted file]
libgo/go/runtime/pprof/pprof.go
libgo/go/runtime/runtime_defs.go [deleted file]
libgo/go/runtime/type.go
libgo/go/scanner/scanner.go
libgo/go/scanner/scanner_test.go
libgo/go/strconv/atof_test.go
libgo/go/strconv/ftoa.go
libgo/go/strconv/ftoa_test.go
libgo/go/sync/atomic/atomic.c [new file with mode: 0644]
libgo/go/sync/atomic/atomic_test.go [new file with mode: 0644]
libgo/go/sync/atomic/doc.go [new file with mode: 0644]
libgo/go/sync/cond.go [new file with mode: 0644]
libgo/go/sync/cond_test.go [new file with mode: 0644]
libgo/go/sync/mutex.go
libgo/go/sync/mutex_test.go
libgo/go/sync/once.go
libgo/go/sync/rwmutex.go
libgo/go/sync/rwmutex_test.go
libgo/go/sync/waitgroup.go [new file with mode: 0644]
libgo/go/sync/waitgroup_test.go [new file with mode: 0644]
libgo/go/sync/xadd_test.go [deleted file]
libgo/go/syslog/syslog_test.go
libgo/go/template/template.go
libgo/go/template/template_test.go
libgo/go/testing/benchmark.go
libgo/go/testing/testing.go
libgo/go/time/sleep.go
libgo/go/time/sleep_test.go
libgo/go/time/tick.go
libgo/go/time/tick_test.go
libgo/go/unicode/letter_test.go
libgo/go/unicode/script_test.go
libgo/go/unicode/tables.go
libgo/go/websocket/client.go
libgo/go/websocket/server.go
libgo/go/websocket/websocket_test.go
libgo/go/xml/read_test.go
libgo/go/xml/xml.go
libgo/go/xml/xml_test.go
libgo/mksysinfo.sh
libgo/runtime/go-byte-array-to-string.c
libgo/runtime/go-int-array-to-string.c
libgo/runtime/go-int-to-string.c
libgo/runtime/go-new.c
libgo/runtime/go-panic.c
libgo/runtime/go-string-to-byte-array.c
libgo/runtime/go-string-to-int-array.c
libgo/runtime/go-strplus.c
libgo/runtime/go-type.h
libgo/runtime/go-unsafe-pointer.c
libgo/runtime/malloc.goc
libgo/runtime/malloc.h
libgo/runtime/mcentral.c
libgo/runtime/mem.c
libgo/runtime/mem_posix_memalign.c
libgo/runtime/mfinal.c
libgo/runtime/mgc0.c
libgo/runtime/mheap.c
libgo/runtime/mheapmap32.c [deleted file]
libgo/runtime/mheapmap32.h [deleted file]
libgo/runtime/mheapmap64.c [deleted file]
libgo/runtime/mheapmap64.h [deleted file]
libgo/runtime/mprof.goc
libgo/runtime/msize.c
libgo/runtime/runtime.h
libgo/runtime/sigqueue.goc
libgo/syscalls/exec.go
libgo/syscalls/socket.go
libgo/testsuite/gotest

index 0db5994..2eecafd 100644 (file)
@@ -1078,7 +1078,7 @@ Type::make_type_descriptor_type()
                                                    bloc);
 
       Struct_type* type_descriptor_type =
-       Type::make_builtin_struct_type(9,
+       Type::make_builtin_struct_type(10,
                                       "Kind", uint8_type,
                                       "align", uint8_type,
                                       "fieldAlign", uint8_type,
@@ -1087,7 +1087,9 @@ Type::make_type_descriptor_type()
                                       "hashfn", hashfn_type,
                                       "equalfn", equalfn_type,
                                       "string", pointer_string_type,
-                                      "", pointer_uncommon_type);
+                                      "", pointer_uncommon_type,
+                                      "ptrToThis",
+                                      pointer_type_descriptor_type);
 
       Named_type* named = Type::make_builtin_named_type("commonType",
                                                        type_descriptor_type);
@@ -1260,6 +1262,16 @@ Type::type_descriptor_constructor(Gogo* gogo, int runtime_type_kind,
     }
 
   ++p;
+  gcc_assert(p->field_name() == "ptrToThis");
+  if (name == NULL)
+    vals->push_back(Expression::make_nil(bloc));
+  else
+    {
+      Type* pt = Type::make_pointer_type(name);
+      vals->push_back(Expression::make_type_descriptor(pt, bloc));
+    }
+
+  ++p;
   gcc_assert(p == fields->end());
 
   mpz_clear(iv);
index 97e6655..e572b23 100644 (file)
@@ -1,4 +1,4 @@
-559f12e8fcd5
+94d654be2064
 
 The first line of this file holds the Mercurial revision number of the
 last merge done from the master library sources.
index e19d229..0715a99 100644 (file)
@@ -105,6 +105,7 @@ toolexeclibgo_DATA = \
        bufio.gox \
        bytes.gox \
        cmath.gox \
+       crypto.gox \
        ebnf.gox \
        exec.gox \
        expvar.gox \
@@ -158,8 +159,10 @@ toolexeclibgoarchive_DATA = \
 toolexeclibgocompressdir = $(toolexeclibgodir)/compress
 
 toolexeclibgocompress_DATA = \
+       compress/bzip2.gox \
        compress/flate.gox \
        compress/gzip.gox \
+       compress/lzw.gox \
        compress/zlib.gox
 
 toolexeclibgocontainerdir = $(toolexeclibgodir)/container
@@ -178,11 +181,13 @@ toolexeclibgocrypto_DATA = \
        crypto/blowfish.gox \
        crypto/cast5.gox \
        crypto/cipher.gox \
+       crypto/dsa.gox \
        crypto/elliptic.gox \
        crypto/hmac.gox \
        crypto/md4.gox \
        crypto/md5.gox \
        crypto/ocsp.gox \
+       crypto/openpgp.gox \
        crypto/rand.gox \
        crypto/rc4.gox \
        crypto/ripemd160.gox \
@@ -201,6 +206,7 @@ toolexeclibgocryptoopenpgpdir = $(toolexeclibgocryptodir)/openpgp
 toolexeclibgocryptoopenpgp_DATA = \
        crypto/openpgp/armor.gox \
        crypto/openpgp/error.gox \
+       crypto/openpgp/packet.gox \
        crypto/openpgp/s2k.gox
 
 toolexeclibgodebugdir = $(toolexeclibgodir)/debug
@@ -306,6 +312,11 @@ toolexeclibgoruntime_DATA = \
        runtime/debug.gox \
        runtime/pprof.gox
 
+toolexeclibgosyncdir = $(toolexeclibgodir)/sync
+
+toolexeclibgosync_DATA = \
+       sync/atomic.gox
+
 toolexeclibgotestingdir = $(toolexeclibgodir)/testing
 
 toolexeclibgotesting_DATA = \
@@ -411,8 +422,6 @@ runtime_files = \
        runtime/mfixalloc.c \
        runtime/mgc0.c \
        runtime/mheap.c \
-       runtime/mheapmap32.c \
-       runtime/mheapmap64.c \
        runtime/msize.c \
        runtime/proc.c \
        runtime/thread.c \
@@ -489,6 +498,9 @@ go_cmath_files = \
        go/cmath/sqrt.go \
        go/cmath/tan.go
 
+go_crypto_files = \
+       go/crypto/crypto.go
+
 go_ebnf_files = \
        go/ebnf/ebnf.go \
        go/ebnf/parser.go
@@ -533,6 +545,7 @@ go_http_files = \
        go/http/client.go \
        go/http/dump.go \
        go/http/fs.go \
+       go/http/header.go \
        go/http/lex.go \
        go/http/persist.go \
        go/http/request.go \
@@ -540,6 +553,7 @@ go_http_files = \
        go/http/server.go \
        go/http/status.go \
        go/http/transfer.go \
+       go/http/transport.go \
        go/http/url.go
 
 go_image_files = \
@@ -693,6 +707,7 @@ go_os_files = \
        go/os/env_unix.go \
        go/os/error.go \
        go/os/exec.go \
+       go/os/exec_unix.go \
        go/os/file.go \
        go/os/file_unix.go \
        go/os/getwd.go \
@@ -738,8 +753,6 @@ go_runtime_files = \
        go/runtime/debug.go \
        go/runtime/error.go \
        go/runtime/extern.go \
-       go/runtime/malloc_defs.go \
-       go/runtime/runtime_defs.go \
        go/runtime/sig.go \
        go/runtime/softfloat64.go \
        go/runtime/type.go \
@@ -781,11 +794,11 @@ go_strings_files = \
        go/strings/strings.go
 
 go_sync_files = \
+       go/sync/cond.go \
        go/sync/mutex.go \
        go/sync/once.go \
-       go/sync/rwmutex.go
-go_sync_c_files = \
-       go/sync/cas.c
+       go/sync/rwmutex.go \
+       go/sync/waitgroup.go
 
 if LIBGO_IS_SOLARIS
 go_syslog_file = go/syslog/syslog_solaris.go
@@ -851,6 +864,12 @@ go_archive_zip_files = \
        go/archive/zip/reader.go \
        go/archive/zip/struct.go
 
+go_compress_bzip2_files = \
+       go/compress/bzip2/bit_reader.go \
+       go/compress/bzip2/bzip2.go \
+       go/compress/bzip2/huffman.go \
+       go/compress/bzip2/move_to_front.go
+
 go_compress_flate_files = \
        go/compress/flate/deflate.go \
        go/compress/flate/huffman_bit_writer.go \
@@ -864,6 +883,10 @@ go_compress_gzip_files = \
        go/compress/gzip/gzip.go \
        go/compress/gzip/gunzip.go
 
+go_compress_lzw_files = \
+       go/compress/lzw/reader.go \
+       go/compress/lzw/writer.go
+
 go_compress_zlib_files = \
        go/compress/zlib/reader.go \
        go/compress/zlib/writer.go
@@ -911,6 +934,8 @@ go_crypto_cipher_files = \
        go/crypto/cipher/io.go \
        go/crypto/cipher/ocfb.go \
        go/crypto/cipher/ofb.go
+go_crypto_dsa_files = \
+       go/crypto/dsa/dsa.go
 go_crypto_elliptic_files = \
        go/crypto/elliptic/elliptic.go
 go_crypto_hmac_files = \
@@ -923,6 +948,11 @@ go_crypto_md5_files = \
        go/crypto/md5/md5block.go
 go_crypto_ocsp_files = \
        go/crypto/ocsp/ocsp.go
+go_crypto_openpgp_files = \
+       go/crypto/openpgp/canonical_text.go \
+       go/crypto/openpgp/keys.go \
+       go/crypto/openpgp/read.go \
+       go/crypto/openpgp/write.go
 go_crypto_rand_files = \
        go/crypto/rand/rand.go \
        go/crypto/rand/rand_unix.go
@@ -970,6 +1000,19 @@ go_crypto_openpgp_armor_files = \
        go/crypto/openpgp/armor/encode.go
 go_crypto_openpgp_error_files = \
        go/crypto/openpgp/error/error.go
+go_crypto_openpgp_packet_files = \
+       go/crypto/openpgp/packet/compressed.go \
+       go/crypto/openpgp/packet/encrypted_key.go \
+       go/crypto/openpgp/packet/literal.go \
+       go/crypto/openpgp/packet/one_pass_signature.go \
+       go/crypto/openpgp/packet/packet.go \
+       go/crypto/openpgp/packet/private_key.go \
+       go/crypto/openpgp/packet/public_key.go \
+       go/crypto/openpgp/packet/reader.go \
+       go/crypto/openpgp/packet/signature.go \
+       go/crypto/openpgp/packet/symmetric_key_encrypted.go \
+       go/crypto/openpgp/packet/symmetrically_encrypted.go \
+       go/crypto/openpgp/packet/userid.go
 go_crypto_openpgp_s2k_files = \
        go/crypto/openpgp/s2k/s2k.go
 
@@ -1095,6 +1138,7 @@ go_net_dict_files = \
        go/net/dict/dict.go
 
 go_net_textproto_files = \
+       go/net/textproto/header.go \
        go/net/textproto/pipeline.go \
        go/net/textproto/reader.go \
        go/net/textproto/textproto.go \
@@ -1116,6 +1160,11 @@ go_runtime_debug_files = \
 go_runtime_pprof_files = \
        go/runtime/pprof/pprof.go
 
+go_sync_atomic_files = \
+       go/sync/atomic/doc.go
+go_sync_atomic_c_files = \
+       go/sync/atomic/atomic.c
+
 go_testing_iotest_files = \
        go/testing/iotest/logger.go \
        go/testing/iotest/reader.go \
@@ -1268,6 +1317,7 @@ libgo_go_objs = \
        bytes/bytes.lo \
        bytes/index.lo \
        cmath/cmath.lo \
+       crypto/crypto.lo \
        ebnf/ebnf.lo \
        exec/exec.lo \
        expvar/expvar.lo \
@@ -1298,8 +1348,7 @@ libgo_go_objs = \
        sort/sort.lo \
        strconv/strconv.lo \
        strings/strings.lo \
-       sync/mutex.lo \
-       sync/cas.lo \
+       sync/sync.lo \
        syslog/syslog.lo \
        syslog/syslog_c.lo \
        tabwriter/tabwriter.lo \
@@ -1313,8 +1362,10 @@ libgo_go_objs = \
        xml/xml.lo \
        archive/tar.lo \
        archive/zip.lo \
+       compress/bzip2.lo \
        compress/flate.lo \
        compress/gzip.lo \
+       compress/lzw.lo \
        compress/zlib.lo \
        container/heap.lo \
        container/list.lo \
@@ -1325,11 +1376,13 @@ libgo_go_objs = \
        crypto/blowfish.lo \
        crypto/cast5.lo \
        crypto/cipher.lo \
+       crypto/dsa.lo \
        crypto/elliptic.lo \
        crypto/hmac.lo \
        crypto/md4.lo \
        crypto/md5.lo \
        crypto/ocsp.lo \
+       crypto/openpgp.lo \
        crypto/rand.lo \
        crypto/rc4.lo \
        crypto/ripemd160.lo \
@@ -1344,6 +1397,7 @@ libgo_go_objs = \
        crypto/xtea.lo \
        crypto/openpgp/armor.lo \
        crypto/openpgp/error.lo \
+       crypto/openpgp/packet.lo \
        crypto/openpgp/s2k.lo \
        debug/dwarf.lo \
        debug/elf.lo \
@@ -1385,6 +1439,8 @@ libgo_go_objs = \
        rpc/jsonrpc.lo \
        runtime/debug.lo \
        runtime/pprof.lo \
+       sync/atomic.lo \
+       sync/atomic_c.lo \
        syscalls/syscall.lo \
        syscalls/errno.lo \
        testing/testing.lo \
@@ -1500,6 +1556,12 @@ cmath/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: cmath/check
 
+crypto/crypto.lo: $(go_crypto_files) hash.gox
+       $(BUILDPACKAGE)
+crypto/check: $(CHECK_DEPS)
+       $(CHECK)
+.PHONY: crypto/check
+
 ebnf/ebnf.lo: $(go_ebnf_files) container/vector.gox go/scanner.gox \
                go/token.gox os.gox strconv.gox unicode.gox utf8.gox
        $(BUILDPACKAGE)
@@ -1507,7 +1569,7 @@ ebnf/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: ebnf/check
 
-exec/exec.lo: $(go_exec_files) os.gox strings.gox
+exec/exec.lo: $(go_exec_files) os.gox strconv.gox strings.gox
        $(BUILDPACKAGE)
 exec/check: $(CHECK_DEPS)
        $(CHECK)
@@ -1526,8 +1588,8 @@ flag/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: flag/check
 
-fmt/fmt.lo: $(go_fmt_files) bytes.gox io.gox os.gox reflect.gox strconv.gox \
-               strings.gox unicode.gox utf8.gox
+fmt/fmt.lo: $(go_fmt_files) bytes.gox io.gox math.gox os.gox reflect.gox \
+               strconv.gox strings.gox unicode.gox utf8.gox
        $(BUILDPACKAGE)
 fmt/check: $(CHECK_DEPS)
        $(CHECK)
@@ -1554,10 +1616,10 @@ html/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: html/check
 
-http/http.lo: $(go_http_files) bufio.gox bytes.gox container/list.gox \
-               container/vector.gox crypto/rand.gox crypto/tls.gox \
-               encoding/base64.gox fmt.gox io.gox io/ioutil.gox log.gox \
-               mime.gox mime/multipart.gox net.gox os.gox path.gox sort.gox \
+http/http.lo: $(go_http_files) bufio.gox bytes.gox container/vector.gox \
+               crypto/rand.gox crypto/tls.gox encoding/base64.gox fmt.gox \
+               io.gox io/ioutil.gox log.gox mime.gox mime/multipart.gox \
+               net.gox net/textproto.gox os.gox path.gox sort.gox \
                strconv.gox strings.gox sync.gox time.gox utf8.gox
        $(BUILDPACKAGE)
 http/check: $(CHECK_DEPS)
@@ -1576,9 +1638,10 @@ io/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: io/check
 
-json/json.lo: $(go_json_files) bytes.gox container/vector.gox fmt.gox io.gox \
-               math.gox os.gox reflect.gox runtime.gox strconv.gox \
-               strings.gox unicode.gox utf16.gox utf8.gox
+json/json.lo: $(go_json_files) bytes.gox container/vector.gox \
+               encoding/base64.gox fmt.gox io.gox math.gox os.gox \
+               reflect.gox runtime.gox strconv.gox strings.gox unicode.gox \
+               utf16.gox utf8.gox
        $(BUILDPACKAGE)
 json/check: $(CHECK_DEPS)
        $(CHECK)
@@ -1611,14 +1674,14 @@ net/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: net/check
 
-netchan/netchan.lo: $(go_netchan_files) gob.gox log.gox net.gox os.gox \
+netchan/netchan.lo: $(go_netchan_files) gob.gox io.gox log.gox net.gox os.gox \
                reflect.gox strconv.gox sync.gox time.gox
        $(BUILDPACKAGE)
 netchan/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: netchan/check
 
-os/os.lo: $(go_os_files) sync.gox syscall.gox
+os/os.lo: $(go_os_files) runtime.gox sync.gox syscall.gox
        $(BUILDPACKAGE)
 os/check: $(CHECK_DEPS)
        $(CHECK)
@@ -1706,10 +1769,8 @@ strings/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: strings/check
 
-sync/mutex.lo: $(go_sync_files) runtime.gox
+sync/sync.lo: $(go_sync_files) runtime.gox sync/atomic.gox
        $(BUILDPACKAGE)
-sync/cas.lo: $(go_sync_c_files) sync/mutex.lo
-       $(LTCOMPILE) -c -o sync/cas.lo $(srcdir)/go/sync/cas.c
 sync/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: sync/check
@@ -1806,6 +1867,13 @@ archive/zip/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: archive/zip/check
 
+compress/bzip2.lo: $(go_compress_bzip2_files) bufio.gox io.gox os.gox sort.gox
+       $(BUILDPACKAGE)
+compress/bzip2/check: $(CHECK_DEPS)
+       @$(MKDIR_P) compress/bzip2
+       $(CHECK)
+.PHONY: compress/bzip2/check
+
 compress/flate.lo: $(go_compress_flate_files) bufio.gox io.gox math.gox \
                os.gox sort.gox strconv.gox
        $(BUILDPACKAGE)
@@ -1822,6 +1890,13 @@ compress/gzip/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: compress/gzip/check
 
+compress/lzw.lo: $(go_compress_lzw_files) bufio.gox fmt.gox io.gox os.gox
+       $(BUILDPACKAGE)
+compress/lzw/check: $(CHECK_DEPS)
+       @$(MKDIR_P) compress/lzw
+       $(CHECK)
+.PHONY: compress/lzw/check
+
 compress/zlib.lo: $(go_compress_zlib_files) bufio.gox compress/flate.gox \
                hash.gox hash/adler32.gox io.gox os.gox
        $(BUILDPACKAGE)
@@ -1893,6 +1968,13 @@ crypto/cipher/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/cipher/check
 
+crypto/dsa.lo: $(go_crypto_dsa_files) big.gox io.gox os.gox
+       $(BUILDPACKAGE)
+crypto/dsa/check: $(CHECK_DEPS)
+       @$(MKDIR_P) crypto/dsa
+       $(CHECK)
+.PHONY: crypto/dsa/check
+
 crypto/elliptic.lo: $(go_crypto_elliptic_files) big.gox io.gox os.gox sync.gox
        $(BUILDPACKAGE)
 crypto/elliptic/check: $(CHECK_DEPS)
@@ -1908,21 +1990,21 @@ crypto/hmac/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/hmac/check
 
-crypto/md4.lo: $(go_crypto_md4_files) hash.gox os.gox
+crypto/md4.lo: $(go_crypto_md4_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/md4/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/md4
        $(CHECK)
 .PHONY: crypto/md4/check
 
-crypto/md5.lo: $(go_crypto_md5_files) hash.gox os.gox
+crypto/md5.lo: $(go_crypto_md5_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/md5/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/md5
        $(CHECK)
 .PHONY: crypto/md5/check
 
-crypto/ocsp.lo: $(go_crypto_ocsp_files) asn1.gox crypto/rsa.gox \
+crypto/ocsp.lo: $(go_crypto_ocsp_files) asn1.gox crypto.gox crypto/rsa.gox \
                crypto/sha1.gox crypto/x509.gox os.gox time.gox
        $(BUILDPACKAGE)
 crypto/ocsp/check: $(CHECK_DEPS)
@@ -1930,8 +2012,18 @@ crypto/ocsp/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/ocsp/check
 
-crypto/rand.lo: $(go_crypto_rand_files) crypto/aes.gox io.gox os.gox sync.gox \
-               time.gox
+crypto/openpgp.lo: $(go_crypto_openpgp_files) crypto.gox \
+                crypto/openpgp/armor.gox crypto/openpgp/error.gox \
+               crypto/openpgp/packet.gox crypto/rsa.gox crypto/sha256.gox \
+               hash.gox io.gox os.gox strconv.gox time.gox
+       $(BUILDPACKAGE)
+crypto/openpgp/check: $(CHECK_DEPS)
+       @$(MKDIR_P) crypto/openpgp
+       $(CHECK)
+.PHONY: crypto/openpgp/check
+
+crypto/rand.lo: $(go_crypto_rand_files) bufio.gox crypto/aes.gox io.gox \
+               os.gox sync.gox time.gox
        $(BUILDPACKAGE)
 crypto/rand/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/rand
@@ -1945,14 +2037,14 @@ crypto/rc4/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/rc4/check
 
-crypto/ripemd160.lo: $(go_crypto_ripemd160_files) hash.gox os.gox
+crypto/ripemd160.lo: $(go_crypto_ripemd160_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/ripemd160/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/ripemd160
        $(CHECK)
 .PHONY: crypto/ripemd160/check
 
-crypto/rsa.lo: $(go_crypto_rsa_files) big.gox crypto/sha1.gox \
+crypto/rsa.lo: $(go_crypto_rsa_files) big.gox crypto.gox crypto/sha1.gox \
                crypto/subtle.gox encoding/hex.gox hash.gox io.gox os.gox
        $(BUILDPACKAGE)
 crypto/rsa/check: $(CHECK_DEPS)
@@ -1960,21 +2052,21 @@ crypto/rsa/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/rsa/check
 
-crypto/sha1.lo: $(go_crypto_sha1_files) hash.gox os.gox
+crypto/sha1.lo: $(go_crypto_sha1_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/sha1/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/sha1
        $(CHECK)
 .PHONY: crypto/sha1/check
 
-crypto/sha256.lo: $(go_crypto_sha256_files) hash.gox os.gox
+crypto/sha256.lo: $(go_crypto_sha256_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/sha256/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/sha256
        $(CHECK)
 .PHONY: crypto/sha256/check
 
-crypto/sha512.lo: $(go_crypto_sha512_files) hash.gox os.gox
+crypto/sha512.lo: $(go_crypto_sha512_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/sha512/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/sha512
@@ -1989,7 +2081,7 @@ crypto/subtle/check: $(CHECK_DEPS)
 .PHONY: crypto/subtle/check
 
 crypto/tls.lo: $(go_crypto_tls_files) big.gox bufio.gox bytes.gox \
-               container/list.gox crypto/aes.gox crypto/cipher.gox \
+               container/list.gox crypto.gox crypto/aes.gox crypto/cipher.gox \
                crypto/elliptic.gox crypto/hmac.gox crypto/md5.gox \
                crypto/rc4.gox crypto/rand.gox crypto/rsa.gox crypto/sha1.gox \
                crypto/subtle.gox crypto/rsa.gox crypto/sha1.gox \
@@ -2009,8 +2101,8 @@ crypto/twofish/check: $(CHECK_DEPS)
 .PHONY: crypto/twofish/check
 
 crypto/x509.lo: $(go_crypto_x509_files) asn1.gox big.gox container/vector.gox \
-               crypto/rsa.gox crypto/sha1.gox hash.gox os.gox strings.gox \
-               time.gox
+               crypto.gox crypto/rsa.gox crypto/sha1.gox hash.gox os.gox \
+               strings.gox time.gox
        $(BUILDPACKAGE)
 crypto/x509/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/x509
@@ -2033,16 +2125,30 @@ crypto/openpgp/armor/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/openpgp/armor/check
 
-crypto/openpgp/error.lo: $(go_crypto_openpgp_error_files)
+crypto/openpgp/error.lo: $(go_crypto_openpgp_error_files) strconv.gox
        $(BUILDPACKAGE)
 crypto/openpgp/error/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/openpgp/error
        $(CHECK)
 .PHONY: crypto/openpgp/error/check
 
-crypto/openpgp/s2k.lo: $(go_crypto_openpgp_s2k_files) crypto/md5.gox \
-               crypto/openpgp/error.gox crypto/ripemd160.gox crypto/sha1.gox \
-               crypto/sha256.gox crypto/sha512.gox hash.gox io.gox os.gox
+crypto/openpgp/packet.lo: $(go_crypto_openpgp_packet_files) big.gox bytes.gox \
+               compress/flate.gox compress/zlib.gox crypto.gox \
+               crypto/aes.gox crypto/cast5.gox crypto/cipher.gox \
+               crypto/openpgp/error.gox crypto/openpgp/s2k.gox \
+               crypto/rand.gox crypto/rsa.gox crypto/sha1.gox \
+               crypto/subtle.gox encoding/binary.gox hash.gox io.gox \
+               io/ioutil.gox os.gox strconv.gox strings.gox
+       $(BUILDPACKAGE)
+crypto/openpgp/packet/check: $(CHECK_DEPS)
+       @$(MKDIR_P) crypto/openpgp/packet
+       $(CHECK)
+.PHONY: crypto/openpgp/packet/check
+
+crypto/openpgp/s2k.lo: $(go_crypto_openpgp_s2k_files) crypto.gox \
+               crypto/md5.gox crypto/openpgp/error.gox crypto/ripemd160.gox \
+               crypto/sha1.gox crypto/sha256.gox crypto/sha512.gox hash.gox \
+               io.gox os.gox
        $(BUILDPACKAGE)
 crypto/openpgp/s2k/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/openpgp/s2k
@@ -2361,6 +2467,15 @@ runtime/pprof/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: runtime/pprof/check
 
+sync/atomic.lo: $(go_sync_atomic_files)
+       $(BUILDPACKAGE)
+sync/atomic_c.lo: $(go_sync_atomic_c_files) sync/atomic.lo
+       $(LTCOMPILE) -c -o $@ $(srcdir)/go/sync/atomic/atomic.c
+sync/atomic/check: $(CHECK_DEPS)
+       @$(MKDIR_P) sync/atomic
+       $(CHECK)
+.PHONY: sync/atomic/check
+
 testing/iotest.lo: $(go_testing_iotest_files) io.gox log.gox os.gox
        $(BUILDPACKAGE)
 testing/iotest/check: $(CHECK_DEPS)
@@ -2410,6 +2525,8 @@ bytes.gox: bytes/bytes.lo
        $(BUILDGOX)
 cmath.gox: cmath/cmath.lo
        $(BUILDGOX)
+crypto.gox: crypto/crypto.lo
+       $(BUILDGOX)
 ebnf.gox: ebnf/ebnf.lo
        $(BUILDGOX)
 exec.gox: exec/exec.lo
@@ -2470,7 +2587,7 @@ strconv.gox: strconv/strconv.lo
        $(BUILDGOX)
 strings.gox: strings/strings.lo
        $(BUILDGOX)
-sync.gox: sync/mutex.lo
+sync.gox: sync/sync.lo
        $(BUILDGOX)
 syslog.gox: syslog/syslog.lo
        $(BUILDGOX)
@@ -2502,10 +2619,14 @@ archive/tar.gox: archive/tar.lo
 archive/zip.gox: archive/zip.lo
        $(BUILDGOX)
 
+compress/bzip2.gox: compress/bzip2.lo
+       $(BUILDGOX)
 compress/flate.gox: compress/flate.lo
        $(BUILDGOX)
 compress/gzip.gox: compress/gzip.lo
        $(BUILDGOX)
+compress/lzw.gox: compress/lzw.lo
+       $(BUILDGOX)
 compress/zlib.gox: compress/zlib.lo
        $(BUILDGOX)
 
@@ -2528,6 +2649,8 @@ crypto/cast5.gox: crypto/cast5.lo
        $(BUILDGOX)
 crypto/cipher.gox: crypto/cipher.lo
        $(BUILDGOX)
+crypto/dsa.gox: crypto/dsa.lo
+       $(BUILDGOX)
 crypto/elliptic.gox: crypto/elliptic.lo
        $(BUILDGOX)
 crypto/hmac.gox: crypto/hmac.lo
@@ -2538,6 +2661,8 @@ crypto/md5.gox: crypto/md5.lo
        $(BUILDGOX)
 crypto/ocsp.gox: crypto/ocsp.lo
        $(BUILDGOX)
+crypto/openpgp.gox: crypto/openpgp.lo
+       $(BUILDGOX)
 crypto/rand.gox: crypto/rand.lo
        $(BUILDGOX)
 crypto/rc4.gox: crypto/rc4.lo
@@ -2567,6 +2692,8 @@ crypto/openpgp/armor.gox: crypto/openpgp/armor.lo
        $(BUILDGOX)
 crypto/openpgp/error.gox: crypto/openpgp/error.lo
        $(BUILDGOX)
+crypto/openpgp/packet.gox: crypto/openpgp/packet.lo
+       $(BUILDGOX)
 crypto/openpgp/s2k.gox: crypto/openpgp/s2k.lo
        $(BUILDGOX)
 
@@ -2664,6 +2791,9 @@ runtime/debug.gox: runtime/debug.lo
 runtime/pprof.gox: runtime/pprof.lo
        $(BUILDGOX)
 
+sync/atomic.gox: sync/atomic.lo
+       $(BUILDGOX)
+
 testing/iotest.gox: testing/iotest.lo
        $(BUILDGOX)
 testing/quick.gox: testing/quick.lo
@@ -2725,8 +2855,10 @@ TEST_PACKAGES = \
        xml/check \
        archive/tar/check \
        archive/zip/check \
+       compress/bzip2/check \
        compress/flate/check \
        compress/gzip/check \
+       compress/lzw/check \
        compress/zlib/check \
        container/heap/check \
        container/list/check \
@@ -2737,11 +2869,13 @@ TEST_PACKAGES = \
        crypto/blowfish/check \
        crypto/cast5/check \
        crypto/cipher/check \
+       crypto/dsa/check \
        crypto/elliptic/check \
        crypto/hmac/check \
        crypto/md4/check \
        crypto/md5/check \
        crypto/ocsp/check \
+       crypto/openpgp/check \
        crypto/rand/check \
        crypto/rc4/check \
        crypto/ripemd160/check \
@@ -2755,6 +2889,7 @@ TEST_PACKAGES = \
        crypto/x509/check \
        crypto/xtea/check \
        crypto/openpgp/armor/check \
+       crypto/openpgp/packet/check \
        crypto/openpgp/s2k/check \
        debug/dwarf/check \
        debug/elf/check \
@@ -2787,6 +2922,7 @@ TEST_PACKAGES = \
        $(os_inotify_check) \
        os/signal/check \
        rpc/jsonrpc/check \
+       sync/atomic/check \
        testing/quick/check \
        testing/script/check
 
index 452c608..c9f0187 100644 (file)
@@ -112,6 +112,7 @@ am__installdirs = "$(DESTDIR)$(toolexeclibdir)" \
        "$(DESTDIR)$(toolexeclibgoosdir)" \
        "$(DESTDIR)$(toolexeclibgorpcdir)" \
        "$(DESTDIR)$(toolexeclibgoruntimedir)" \
+       "$(DESTDIR)$(toolexeclibgosyncdir)" \
        "$(DESTDIR)$(toolexeclibgotestingdir)"
 LIBRARIES = $(toolexeclib_LIBRARIES)
 ARFLAGS = cru
@@ -122,43 +123,45 @@ libgobegin_a_OBJECTS = $(am_libgobegin_a_OBJECTS)
 LTLIBRARIES = $(toolexeclib_LTLIBRARIES)
 am__DEPENDENCIES_1 =
 am__DEPENDENCIES_2 = asn1/asn1.lo big/big.lo bufio/bufio.lo \
-       bytes/bytes.lo bytes/index.lo cmath/cmath.lo ebnf/ebnf.lo \
-       exec/exec.lo expvar/expvar.lo flag/flag.lo fmt/fmt.lo \
-       gob/gob.lo hash/hash.lo html/html.lo http/http.lo \
+       bytes/bytes.lo bytes/index.lo cmath/cmath.lo crypto/crypto.lo \
+       ebnf/ebnf.lo exec/exec.lo expvar/expvar.lo flag/flag.lo \
+       fmt/fmt.lo gob/gob.lo hash/hash.lo html/html.lo http/http.lo \
        image/image.lo io/io.lo json/json.lo log/log.lo math/math.lo \
        mime/mime.lo net/net.lo netchan/netchan.lo os/os.lo \
        patch/patch.lo path/path.lo rand/rand.lo reflect/reflect.lo \
        regexp/regexp.lo rpc/rpc.lo runtime/runtime.lo \
        scanner/scanner.lo smtp/smtp.lo sort/sort.lo \
-       strconv/strconv.lo strings/strings.lo sync/mutex.lo \
-       sync/cas.lo syslog/syslog.lo syslog/syslog_c.lo \
-       tabwriter/tabwriter.lo template/template.lo time/time.lo \
-       try/try.lo unicode/unicode.lo utf16/utf16.lo utf8/utf8.lo \
+       strconv/strconv.lo strings/strings.lo sync/sync.lo \
+       syslog/syslog.lo syslog/syslog_c.lo tabwriter/tabwriter.lo \
+       template/template.lo time/time.lo try/try.lo \
+       unicode/unicode.lo utf16/utf16.lo utf8/utf8.lo \
        websocket/websocket.lo xml/xml.lo archive/tar.lo \
-       archive/zip.lo compress/flate.lo compress/gzip.lo \
-       compress/zlib.lo container/heap.lo container/list.lo \
-       container/ring.lo container/vector.lo crypto/aes.lo \
-       crypto/block.lo crypto/blowfish.lo crypto/cast5.lo \
-       crypto/cipher.lo crypto/elliptic.lo crypto/hmac.lo \
-       crypto/md4.lo crypto/md5.lo crypto/ocsp.lo crypto/rand.lo \
+       archive/zip.lo compress/bzip2.lo compress/flate.lo \
+       compress/gzip.lo compress/lzw.lo compress/zlib.lo \
+       container/heap.lo container/list.lo container/ring.lo \
+       container/vector.lo crypto/aes.lo crypto/block.lo \
+       crypto/blowfish.lo crypto/cast5.lo crypto/cipher.lo \
+       crypto/dsa.lo crypto/elliptic.lo crypto/hmac.lo crypto/md4.lo \
+       crypto/md5.lo crypto/ocsp.lo crypto/openpgp.lo crypto/rand.lo \
        crypto/rc4.lo crypto/ripemd160.lo crypto/rsa.lo crypto/sha1.lo \
        crypto/sha256.lo crypto/sha512.lo crypto/subtle.lo \
        crypto/tls.lo crypto/twofish.lo crypto/x509.lo crypto/xtea.lo \
        crypto/openpgp/armor.lo crypto/openpgp/error.lo \
-       crypto/openpgp/s2k.lo debug/dwarf.lo debug/elf.lo \
-       debug/gosym.lo debug/macho.lo debug/pe.lo debug/proc.lo \
-       encoding/ascii85.lo encoding/base32.lo encoding/base64.lo \
-       encoding/binary.lo encoding/git85.lo encoding/hex.lo \
-       encoding/line.lo encoding/pem.lo exp/datafmt.lo exp/draw.lo \
-       exp/eval.lo go/ast.lo go/doc.lo go/parser.lo go/printer.lo \
-       go/scanner.lo go/token.lo go/typechecker.lo hash/adler32.lo \
-       hash/crc32.lo hash/crc64.lo http/pprof.lo image/jpeg.lo \
-       image/png.lo index/suffixarray.lo io/ioutil.lo \
-       mime/multipart.lo net/dict.lo net/textproto.lo \
+       crypto/openpgp/packet.lo crypto/openpgp/s2k.lo debug/dwarf.lo \
+       debug/elf.lo debug/gosym.lo debug/macho.lo debug/pe.lo \
+       debug/proc.lo encoding/ascii85.lo encoding/base32.lo \
+       encoding/base64.lo encoding/binary.lo encoding/git85.lo \
+       encoding/hex.lo encoding/line.lo encoding/pem.lo \
+       exp/datafmt.lo exp/draw.lo exp/eval.lo go/ast.lo go/doc.lo \
+       go/parser.lo go/printer.lo go/scanner.lo go/token.lo \
+       go/typechecker.lo hash/adler32.lo hash/crc32.lo hash/crc64.lo \
+       http/pprof.lo image/jpeg.lo image/png.lo index/suffixarray.lo \
+       io/ioutil.lo mime/multipart.lo net/dict.lo net/textproto.lo \
        $(am__DEPENDENCIES_1) os/signal.lo rpc/jsonrpc.lo \
-       runtime/debug.lo runtime/pprof.lo syscalls/syscall.lo \
-       syscalls/errno.lo testing/testing.lo testing/iotest.lo \
-       testing/quick.lo testing/script.lo
+       runtime/debug.lo runtime/pprof.lo sync/atomic.lo \
+       sync/atomic_c.lo syscalls/syscall.lo syscalls/errno.lo \
+       testing/testing.lo testing/iotest.lo testing/quick.lo \
+       testing/script.lo
 libgo_la_DEPENDENCIES = $(am__DEPENDENCIES_2) $(am__DEPENDENCIES_1) \
        $(am__DEPENDENCIES_1) $(am__DEPENDENCIES_1) \
        $(am__DEPENDENCIES_1)
@@ -204,8 +207,7 @@ am__libgo_la_SOURCES_DIST = runtime/go-append.c runtime/go-assert.c \
        runtime/mcache.c runtime/mcentral.c \
        runtime/mem_posix_memalign.c runtime/mem.c runtime/mfinal.c \
        runtime/mfixalloc.c runtime/mgc0.c runtime/mheap.c \
-       runtime/mheapmap32.c runtime/mheapmap64.c runtime/msize.c \
-       runtime/proc.c runtime/thread.c \
+       runtime/msize.c runtime/proc.c runtime/thread.c \
        runtime/rtems-task-variable-add.c chan.c iface.c malloc.c \
        map.c mprof.c reflect.c sigqueue.c string.c
 @HAVE_SYS_MMAN_H_FALSE@am__objects_1 = mem_posix_memalign.lo
@@ -237,9 +239,8 @@ am__objects_3 = go-append.lo go-assert.lo go-assert-interface.lo \
        go-unreflect.lo go-unsafe-new.lo go-unsafe-newarray.lo \
        go-unsafe-pointer.lo go-unwind.lo mcache.lo mcentral.lo \
        $(am__objects_1) mfinal.lo mfixalloc.lo mgc0.lo mheap.lo \
-       mheapmap32.lo mheapmap64.lo msize.lo proc.lo thread.lo \
-       $(am__objects_2) chan.lo iface.lo malloc.lo map.lo mprof.lo \
-       reflect.lo sigqueue.lo string.lo
+       msize.lo proc.lo thread.lo $(am__objects_2) chan.lo iface.lo \
+       malloc.lo map.lo mprof.lo reflect.lo sigqueue.lo string.lo
 am_libgo_la_OBJECTS = $(am__objects_3)
 libgo_la_OBJECTS = $(am_libgo_la_OBJECTS)
 DEFAULT_INCLUDES = -I.@am__isrc@
@@ -280,7 +281,7 @@ DATA = $(toolexeclibgo_DATA) $(toolexeclibgoarchive_DATA) \
        $(toolexeclibgoio_DATA) $(toolexeclibgomime_DATA) \
        $(toolexeclibgonet_DATA) $(toolexeclibgoos_DATA) \
        $(toolexeclibgorpc_DATA) $(toolexeclibgoruntime_DATA) \
-       $(toolexeclibgotesting_DATA)
+       $(toolexeclibgosync_DATA) $(toolexeclibgotesting_DATA)
 RECURSIVE_CLEAN_TARGETS = mostlyclean-recursive clean-recursive        \
   distclean-recursive maintainer-clean-recursive
 AM_RECURSIVE_TARGETS = $(RECURSIVE_TARGETS:-recursive=) \
@@ -546,6 +547,7 @@ toolexeclibgo_DATA = \
        bufio.gox \
        bytes.gox \
        cmath.gox \
+       crypto.gox \
        ebnf.gox \
        exec.gox \
        expvar.gox \
@@ -597,8 +599,10 @@ toolexeclibgoarchive_DATA = \
 
 toolexeclibgocompressdir = $(toolexeclibgodir)/compress
 toolexeclibgocompress_DATA = \
+       compress/bzip2.gox \
        compress/flate.gox \
        compress/gzip.gox \
+       compress/lzw.gox \
        compress/zlib.gox
 
 toolexeclibgocontainerdir = $(toolexeclibgodir)/container
@@ -615,11 +619,13 @@ toolexeclibgocrypto_DATA = \
        crypto/blowfish.gox \
        crypto/cast5.gox \
        crypto/cipher.gox \
+       crypto/dsa.gox \
        crypto/elliptic.gox \
        crypto/hmac.gox \
        crypto/md4.gox \
        crypto/md5.gox \
        crypto/ocsp.gox \
+       crypto/openpgp.gox \
        crypto/rand.gox \
        crypto/rc4.gox \
        crypto/ripemd160.gox \
@@ -637,6 +643,7 @@ toolexeclibgocryptoopenpgpdir = $(toolexeclibgocryptodir)/openpgp
 toolexeclibgocryptoopenpgp_DATA = \
        crypto/openpgp/armor.gox \
        crypto/openpgp/error.gox \
+       crypto/openpgp/packet.gox \
        crypto/openpgp/s2k.gox
 
 toolexeclibgodebugdir = $(toolexeclibgodir)/debug
@@ -725,6 +732,10 @@ toolexeclibgoruntime_DATA = \
        runtime/debug.gox \
        runtime/pprof.gox
 
+toolexeclibgosyncdir = $(toolexeclibgodir)/sync
+toolexeclibgosync_DATA = \
+       sync/atomic.gox
+
 toolexeclibgotestingdir = $(toolexeclibgodir)/testing
 toolexeclibgotesting_DATA = \
        testing/iotest.gox \
@@ -821,8 +832,6 @@ runtime_files = \
        runtime/mfixalloc.c \
        runtime/mgc0.c \
        runtime/mheap.c \
-       runtime/mheapmap32.c \
-       runtime/mheapmap64.c \
        runtime/msize.c \
        runtime/proc.c \
        runtime/thread.c \
@@ -874,6 +883,9 @@ go_cmath_files = \
        go/cmath/sqrt.go \
        go/cmath/tan.go
 
+go_crypto_files = \
+       go/crypto/crypto.go
+
 go_ebnf_files = \
        go/ebnf/ebnf.go \
        go/ebnf/parser.go
@@ -918,6 +930,7 @@ go_http_files = \
        go/http/client.go \
        go/http/dump.go \
        go/http/fs.go \
+       go/http/header.go \
        go/http/lex.go \
        go/http/persist.go \
        go/http/request.go \
@@ -925,6 +938,7 @@ go_http_files = \
        go/http/server.go \
        go/http/status.go \
        go/http/transfer.go \
+       go/http/transport.go \
        go/http/url.go
 
 go_image_files = \
@@ -1051,6 +1065,7 @@ go_os_files = \
        go/os/env_unix.go \
        go/os/error.go \
        go/os/exec.go \
+       go/os/exec_unix.go \
        go/os/file.go \
        go/os/file_unix.go \
        go/os/getwd.go \
@@ -1096,8 +1111,6 @@ go_runtime_files = \
        go/runtime/debug.go \
        go/runtime/error.go \
        go/runtime/extern.go \
-       go/runtime/malloc_defs.go \
-       go/runtime/runtime_defs.go \
        go/runtime/sig.go \
        go/runtime/softfloat64.go \
        go/runtime/type.go \
@@ -1128,12 +1141,11 @@ go_strings_files = \
        go/strings/strings.go
 
 go_sync_files = \
+       go/sync/cond.go \
        go/sync/mutex.go \
        go/sync/once.go \
-       go/sync/rwmutex.go
-
-go_sync_c_files = \
-       go/sync/cas.c
+       go/sync/rwmutex.go \
+       go/sync/waitgroup.go
 
 @LIBGO_IS_SOLARIS_FALSE@go_syslog_file = go/syslog/syslog_unix.go
 @LIBGO_IS_SOLARIS_TRUE@go_syslog_file = go/syslog/syslog_solaris.go
@@ -1196,6 +1208,12 @@ go_archive_zip_files = \
        go/archive/zip/reader.go \
        go/archive/zip/struct.go
 
+go_compress_bzip2_files = \
+       go/compress/bzip2/bit_reader.go \
+       go/compress/bzip2/bzip2.go \
+       go/compress/bzip2/huffman.go \
+       go/compress/bzip2/move_to_front.go
+
 go_compress_flate_files = \
        go/compress/flate/deflate.go \
        go/compress/flate/huffman_bit_writer.go \
@@ -1209,6 +1227,10 @@ go_compress_gzip_files = \
        go/compress/gzip/gzip.go \
        go/compress/gzip/gunzip.go
 
+go_compress_lzw_files = \
+       go/compress/lzw/reader.go \
+       go/compress/lzw/writer.go
+
 go_compress_zlib_files = \
        go/compress/zlib/reader.go \
        go/compress/zlib/writer.go
@@ -1261,6 +1283,9 @@ go_crypto_cipher_files = \
        go/crypto/cipher/ocfb.go \
        go/crypto/cipher/ofb.go
 
+go_crypto_dsa_files = \
+       go/crypto/dsa/dsa.go
+
 go_crypto_elliptic_files = \
        go/crypto/elliptic/elliptic.go
 
@@ -1278,6 +1303,12 @@ go_crypto_md5_files = \
 go_crypto_ocsp_files = \
        go/crypto/ocsp/ocsp.go
 
+go_crypto_openpgp_files = \
+       go/crypto/openpgp/canonical_text.go \
+       go/crypto/openpgp/keys.go \
+       go/crypto/openpgp/read.go \
+       go/crypto/openpgp/write.go
+
 go_crypto_rand_files = \
        go/crypto/rand/rand.go \
        go/crypto/rand/rand_unix.go
@@ -1338,6 +1369,20 @@ go_crypto_openpgp_armor_files = \
 go_crypto_openpgp_error_files = \
        go/crypto/openpgp/error/error.go
 
+go_crypto_openpgp_packet_files = \
+       go/crypto/openpgp/packet/compressed.go \
+       go/crypto/openpgp/packet/encrypted_key.go \
+       go/crypto/openpgp/packet/literal.go \
+       go/crypto/openpgp/packet/one_pass_signature.go \
+       go/crypto/openpgp/packet/packet.go \
+       go/crypto/openpgp/packet/private_key.go \
+       go/crypto/openpgp/packet/public_key.go \
+       go/crypto/openpgp/packet/reader.go \
+       go/crypto/openpgp/packet/signature.go \
+       go/crypto/openpgp/packet/symmetric_key_encrypted.go \
+       go/crypto/openpgp/packet/symmetrically_encrypted.go \
+       go/crypto/openpgp/packet/userid.go
+
 go_crypto_openpgp_s2k_files = \
        go/crypto/openpgp/s2k/s2k.go
 
@@ -1484,6 +1529,7 @@ go_net_dict_files = \
        go/net/dict/dict.go
 
 go_net_textproto_files = \
+       go/net/textproto/header.go \
        go/net/textproto/pipeline.go \
        go/net/textproto/reader.go \
        go/net/textproto/textproto.go \
@@ -1506,6 +1552,12 @@ go_runtime_debug_files = \
 go_runtime_pprof_files = \
        go/runtime/pprof/pprof.go
 
+go_sync_atomic_files = \
+       go/sync/atomic/doc.go
+
+go_sync_atomic_c_files = \
+       go/sync/atomic/atomic.c
+
 go_testing_iotest_files = \
        go/testing/iotest/logger.go \
        go/testing/iotest/reader.go \
@@ -1606,6 +1658,7 @@ libgo_go_objs = \
        bytes/bytes.lo \
        bytes/index.lo \
        cmath/cmath.lo \
+       crypto/crypto.lo \
        ebnf/ebnf.lo \
        exec/exec.lo \
        expvar/expvar.lo \
@@ -1636,8 +1689,7 @@ libgo_go_objs = \
        sort/sort.lo \
        strconv/strconv.lo \
        strings/strings.lo \
-       sync/mutex.lo \
-       sync/cas.lo \
+       sync/sync.lo \
        syslog/syslog.lo \
        syslog/syslog_c.lo \
        tabwriter/tabwriter.lo \
@@ -1651,8 +1703,10 @@ libgo_go_objs = \
        xml/xml.lo \
        archive/tar.lo \
        archive/zip.lo \
+       compress/bzip2.lo \
        compress/flate.lo \
        compress/gzip.lo \
+       compress/lzw.lo \
        compress/zlib.lo \
        container/heap.lo \
        container/list.lo \
@@ -1663,11 +1717,13 @@ libgo_go_objs = \
        crypto/blowfish.lo \
        crypto/cast5.lo \
        crypto/cipher.lo \
+       crypto/dsa.lo \
        crypto/elliptic.lo \
        crypto/hmac.lo \
        crypto/md4.lo \
        crypto/md5.lo \
        crypto/ocsp.lo \
+       crypto/openpgp.lo \
        crypto/rand.lo \
        crypto/rc4.lo \
        crypto/ripemd160.lo \
@@ -1682,6 +1738,7 @@ libgo_go_objs = \
        crypto/xtea.lo \
        crypto/openpgp/armor.lo \
        crypto/openpgp/error.lo \
+       crypto/openpgp/packet.lo \
        crypto/openpgp/s2k.lo \
        debug/dwarf.lo \
        debug/elf.lo \
@@ -1723,6 +1780,8 @@ libgo_go_objs = \
        rpc/jsonrpc.lo \
        runtime/debug.lo \
        runtime/pprof.lo \
+       sync/atomic.lo \
+       sync/atomic_c.lo \
        syscalls/syscall.lo \
        syscalls/errno.lo \
        testing/testing.lo \
@@ -1857,8 +1916,10 @@ TEST_PACKAGES = \
        xml/check \
        archive/tar/check \
        archive/zip/check \
+       compress/bzip2/check \
        compress/flate/check \
        compress/gzip/check \
+       compress/lzw/check \
        compress/zlib/check \
        container/heap/check \
        container/list/check \
@@ -1869,11 +1930,13 @@ TEST_PACKAGES = \
        crypto/blowfish/check \
        crypto/cast5/check \
        crypto/cipher/check \
+       crypto/dsa/check \
        crypto/elliptic/check \
        crypto/hmac/check \
        crypto/md4/check \
        crypto/md5/check \
        crypto/ocsp/check \
+       crypto/openpgp/check \
        crypto/rand/check \
        crypto/rc4/check \
        crypto/ripemd160/check \
@@ -1887,6 +1950,7 @@ TEST_PACKAGES = \
        crypto/x509/check \
        crypto/xtea/check \
        crypto/openpgp/armor/check \
+       crypto/openpgp/packet/check \
        crypto/openpgp/s2k/check \
        debug/dwarf/check \
        debug/elf/check \
@@ -1919,6 +1983,7 @@ TEST_PACKAGES = \
        $(os_inotify_check) \
        os/signal/check \
        rpc/jsonrpc/check \
+       sync/atomic/check \
        testing/quick/check \
        testing/script/check
 
@@ -2146,8 +2211,6 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/mfixalloc.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/mgc0.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/mheap.Plo@am__quote@
-@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/mheapmap32.Plo@am__quote@
-@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/mheapmap64.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/mprof.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/msize.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/proc.Plo@am__quote@
@@ -2794,20 +2857,6 @@ mheap.lo: runtime/mheap.c
 @AMDEP_TRUE@@am__fastdepCC_FALSE@      DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCC_FALSE@  $(LIBTOOL)  --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o mheap.lo `test -f 'runtime/mheap.c' || echo '$(srcdir)/'`runtime/mheap.c
 
-mheapmap32.lo: runtime/mheapmap32.c
-@am__fastdepCC_TRUE@   $(LIBTOOL)  --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT mheapmap32.lo -MD -MP -MF $(DEPDIR)/mheapmap32.Tpo -c -o mheapmap32.lo `test -f 'runtime/mheapmap32.c' || echo '$(srcdir)/'`runtime/mheapmap32.c
-@am__fastdepCC_TRUE@   $(am__mv) $(DEPDIR)/mheapmap32.Tpo $(DEPDIR)/mheapmap32.Plo
-@AMDEP_TRUE@@am__fastdepCC_FALSE@      source='runtime/mheapmap32.c' object='mheapmap32.lo' libtool=yes @AMDEPBACKSLASH@
-@AMDEP_TRUE@@am__fastdepCC_FALSE@      DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
-@am__fastdepCC_FALSE@  $(LIBTOOL)  --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o mheapmap32.lo `test -f 'runtime/mheapmap32.c' || echo '$(srcdir)/'`runtime/mheapmap32.c
-
-mheapmap64.lo: runtime/mheapmap64.c
-@am__fastdepCC_TRUE@   $(LIBTOOL)  --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT mheapmap64.lo -MD -MP -MF $(DEPDIR)/mheapmap64.Tpo -c -o mheapmap64.lo `test -f 'runtime/mheapmap64.c' || echo '$(srcdir)/'`runtime/mheapmap64.c
-@am__fastdepCC_TRUE@   $(am__mv) $(DEPDIR)/mheapmap64.Tpo $(DEPDIR)/mheapmap64.Plo
-@AMDEP_TRUE@@am__fastdepCC_FALSE@      source='runtime/mheapmap64.c' object='mheapmap64.lo' libtool=yes @AMDEPBACKSLASH@
-@AMDEP_TRUE@@am__fastdepCC_FALSE@      DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
-@am__fastdepCC_FALSE@  $(LIBTOOL)  --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o mheapmap64.lo `test -f 'runtime/mheapmap64.c' || echo '$(srcdir)/'`runtime/mheapmap64.c
-
 msize.lo: runtime/msize.c
 @am__fastdepCC_TRUE@   $(LIBTOOL)  --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT msize.lo -MD -MP -MF $(DEPDIR)/msize.Tpo -c -o msize.lo `test -f 'runtime/msize.c' || echo '$(srcdir)/'`runtime/msize.c
 @am__fastdepCC_TRUE@   $(am__mv) $(DEPDIR)/msize.Tpo $(DEPDIR)/msize.Plo
@@ -3261,6 +3310,26 @@ uninstall-toolexeclibgoruntimeDATA:
        test -n "$$files" || exit 0; \
        echo " ( cd '$(DESTDIR)$(toolexeclibgoruntimedir)' && rm -f" $$files ")"; \
        cd "$(DESTDIR)$(toolexeclibgoruntimedir)" && rm -f $$files
+install-toolexeclibgosyncDATA: $(toolexeclibgosync_DATA)
+       @$(NORMAL_INSTALL)
+       test -z "$(toolexeclibgosyncdir)" || $(MKDIR_P) "$(DESTDIR)$(toolexeclibgosyncdir)"
+       @list='$(toolexeclibgosync_DATA)'; test -n "$(toolexeclibgosyncdir)" || list=; \
+       for p in $$list; do \
+         if test -f "$$p"; then d=; else d="$(srcdir)/"; fi; \
+         echo "$$d$$p"; \
+       done | $(am__base_list) | \
+       while read files; do \
+         echo " $(INSTALL_DATA) $$files '$(DESTDIR)$(toolexeclibgosyncdir)'"; \
+         $(INSTALL_DATA) $$files "$(DESTDIR)$(toolexeclibgosyncdir)" || exit $$?; \
+       done
+
+uninstall-toolexeclibgosyncDATA:
+       @$(NORMAL_UNINSTALL)
+       @list='$(toolexeclibgosync_DATA)'; test -n "$(toolexeclibgosyncdir)" || list=; \
+       files=`for p in $$list; do echo $$p; done | sed -e 's|^.*/||'`; \
+       test -n "$$files" || exit 0; \
+       echo " ( cd '$(DESTDIR)$(toolexeclibgosyncdir)' && rm -f" $$files ")"; \
+       cd "$(DESTDIR)$(toolexeclibgosyncdir)" && rm -f $$files
 install-toolexeclibgotestingDATA: $(toolexeclibgotesting_DATA)
        @$(NORMAL_INSTALL)
        test -z "$(toolexeclibgotestingdir)" || $(MKDIR_P) "$(DESTDIR)$(toolexeclibgotestingdir)"
@@ -3598,7 +3667,7 @@ all-am: Makefile $(LIBRARIES) $(LTLIBRARIES) all-multi $(DATA) \
                config.h
 installdirs: installdirs-recursive
 installdirs-am:
-       for dir in "$(DESTDIR)$(toolexeclibdir)" "$(DESTDIR)$(toolexeclibdir)" "$(DESTDIR)$(toolexeclibgodir)" "$(DESTDIR)$(toolexeclibgoarchivedir)" "$(DESTDIR)$(toolexeclibgocompressdir)" "$(DESTDIR)$(toolexeclibgocontainerdir)" "$(DESTDIR)$(toolexeclibgocryptodir)" "$(DESTDIR)$(toolexeclibgocryptoopenpgpdir)" "$(DESTDIR)$(toolexeclibgodebugdir)" "$(DESTDIR)$(toolexeclibgoencodingdir)" "$(DESTDIR)$(toolexeclibgoexpdir)" "$(DESTDIR)$(toolexeclibgogodir)" "$(DESTDIR)$(toolexeclibgohashdir)" "$(DESTDIR)$(toolexeclibgohttpdir)" "$(DESTDIR)$(toolexeclibgoimagedir)" "$(DESTDIR)$(toolexeclibgoindexdir)" "$(DESTDIR)$(toolexeclibgoiodir)" "$(DESTDIR)$(toolexeclibgomimedir)" "$(DESTDIR)$(toolexeclibgonetdir)" "$(DESTDIR)$(toolexeclibgoosdir)" "$(DESTDIR)$(toolexeclibgorpcdir)" "$(DESTDIR)$(toolexeclibgoruntimedir)" "$(DESTDIR)$(toolexeclibgotestingdir)"; do \
+       for dir in "$(DESTDIR)$(toolexeclibdir)" "$(DESTDIR)$(toolexeclibdir)" "$(DESTDIR)$(toolexeclibgodir)" "$(DESTDIR)$(toolexeclibgoarchivedir)" "$(DESTDIR)$(toolexeclibgocompressdir)" "$(DESTDIR)$(toolexeclibgocontainerdir)" "$(DESTDIR)$(toolexeclibgocryptodir)" "$(DESTDIR)$(toolexeclibgocryptoopenpgpdir)" "$(DESTDIR)$(toolexeclibgodebugdir)" "$(DESTDIR)$(toolexeclibgoencodingdir)" "$(DESTDIR)$(toolexeclibgoexpdir)" "$(DESTDIR)$(toolexeclibgogodir)" "$(DESTDIR)$(toolexeclibgohashdir)" "$(DESTDIR)$(toolexeclibgohttpdir)" "$(DESTDIR)$(toolexeclibgoimagedir)" "$(DESTDIR)$(toolexeclibgoindexdir)" "$(DESTDIR)$(toolexeclibgoiodir)" "$(DESTDIR)$(toolexeclibgomimedir)" "$(DESTDIR)$(toolexeclibgonetdir)" "$(DESTDIR)$(toolexeclibgoosdir)" "$(DESTDIR)$(toolexeclibgorpcdir)" "$(DESTDIR)$(toolexeclibgoruntimedir)" "$(DESTDIR)$(toolexeclibgosyncdir)" "$(DESTDIR)$(toolexeclibgotestingdir)"; do \
          test -z "$$dir" || $(MKDIR_P) "$$dir"; \
        done
 install: install-recursive
@@ -3672,7 +3741,7 @@ install-exec-am: install-multi install-toolexeclibLIBRARIES \
        install-toolexeclibgoindexDATA install-toolexeclibgoioDATA \
        install-toolexeclibgomimeDATA install-toolexeclibgonetDATA \
        install-toolexeclibgoosDATA install-toolexeclibgorpcDATA \
-       install-toolexeclibgoruntimeDATA \
+       install-toolexeclibgoruntimeDATA install-toolexeclibgosyncDATA \
        install-toolexeclibgotestingDATA
 
 install-html: install-html-recursive
@@ -3732,6 +3801,7 @@ uninstall-am: uninstall-toolexeclibLIBRARIES \
        uninstall-toolexeclibgomimeDATA uninstall-toolexeclibgonetDATA \
        uninstall-toolexeclibgoosDATA uninstall-toolexeclibgorpcDATA \
        uninstall-toolexeclibgoruntimeDATA \
+       uninstall-toolexeclibgosyncDATA \
        uninstall-toolexeclibgotestingDATA
 
 .MAKE: $(RECURSIVE_CLEAN_TARGETS) $(RECURSIVE_TARGETS) all all-multi \
@@ -3766,7 +3836,7 @@ uninstall-am: uninstall-toolexeclibLIBRARIES \
        install-toolexeclibgoindexDATA install-toolexeclibgoioDATA \
        install-toolexeclibgomimeDATA install-toolexeclibgonetDATA \
        install-toolexeclibgoosDATA install-toolexeclibgorpcDATA \
-       install-toolexeclibgoruntimeDATA \
+       install-toolexeclibgoruntimeDATA install-toolexeclibgosyncDATA \
        install-toolexeclibgotestingDATA installcheck installcheck-am \
        installdirs installdirs-am maintainer-clean \
        maintainer-clean-generic maintainer-clean-multi mostlyclean \
@@ -3790,6 +3860,7 @@ uninstall-am: uninstall-toolexeclibLIBRARIES \
        uninstall-toolexeclibgomimeDATA uninstall-toolexeclibgonetDATA \
        uninstall-toolexeclibgoosDATA uninstall-toolexeclibgorpcDATA \
        uninstall-toolexeclibgoruntimeDATA \
+       uninstall-toolexeclibgosyncDATA \
        uninstall-toolexeclibgotestingDATA
 
 
@@ -3872,6 +3943,12 @@ cmath/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: cmath/check
 
+crypto/crypto.lo: $(go_crypto_files) hash.gox
+       $(BUILDPACKAGE)
+crypto/check: $(CHECK_DEPS)
+       $(CHECK)
+.PHONY: crypto/check
+
 ebnf/ebnf.lo: $(go_ebnf_files) container/vector.gox go/scanner.gox \
                go/token.gox os.gox strconv.gox unicode.gox utf8.gox
        $(BUILDPACKAGE)
@@ -3879,7 +3956,7 @@ ebnf/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: ebnf/check
 
-exec/exec.lo: $(go_exec_files) os.gox strings.gox
+exec/exec.lo: $(go_exec_files) os.gox strconv.gox strings.gox
        $(BUILDPACKAGE)
 exec/check: $(CHECK_DEPS)
        $(CHECK)
@@ -3898,8 +3975,8 @@ flag/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: flag/check
 
-fmt/fmt.lo: $(go_fmt_files) bytes.gox io.gox os.gox reflect.gox strconv.gox \
-               strings.gox unicode.gox utf8.gox
+fmt/fmt.lo: $(go_fmt_files) bytes.gox io.gox math.gox os.gox reflect.gox \
+               strconv.gox strings.gox unicode.gox utf8.gox
        $(BUILDPACKAGE)
 fmt/check: $(CHECK_DEPS)
        $(CHECK)
@@ -3926,10 +4003,10 @@ html/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: html/check
 
-http/http.lo: $(go_http_files) bufio.gox bytes.gox container/list.gox \
-               container/vector.gox crypto/rand.gox crypto/tls.gox \
-               encoding/base64.gox fmt.gox io.gox io/ioutil.gox log.gox \
-               mime.gox mime/multipart.gox net.gox os.gox path.gox sort.gox \
+http/http.lo: $(go_http_files) bufio.gox bytes.gox container/vector.gox \
+               crypto/rand.gox crypto/tls.gox encoding/base64.gox fmt.gox \
+               io.gox io/ioutil.gox log.gox mime.gox mime/multipart.gox \
+               net.gox net/textproto.gox os.gox path.gox sort.gox \
                strconv.gox strings.gox sync.gox time.gox utf8.gox
        $(BUILDPACKAGE)
 http/check: $(CHECK_DEPS)
@@ -3948,9 +4025,10 @@ io/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: io/check
 
-json/json.lo: $(go_json_files) bytes.gox container/vector.gox fmt.gox io.gox \
-               math.gox os.gox reflect.gox runtime.gox strconv.gox \
-               strings.gox unicode.gox utf16.gox utf8.gox
+json/json.lo: $(go_json_files) bytes.gox container/vector.gox \
+               encoding/base64.gox fmt.gox io.gox math.gox os.gox \
+               reflect.gox runtime.gox strconv.gox strings.gox unicode.gox \
+               utf16.gox utf8.gox
        $(BUILDPACKAGE)
 json/check: $(CHECK_DEPS)
        $(CHECK)
@@ -3983,14 +4061,14 @@ net/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: net/check
 
-netchan/netchan.lo: $(go_netchan_files) gob.gox log.gox net.gox os.gox \
+netchan/netchan.lo: $(go_netchan_files) gob.gox io.gox log.gox net.gox os.gox \
                reflect.gox strconv.gox sync.gox time.gox
        $(BUILDPACKAGE)
 netchan/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: netchan/check
 
-os/os.lo: $(go_os_files) sync.gox syscall.gox
+os/os.lo: $(go_os_files) runtime.gox sync.gox syscall.gox
        $(BUILDPACKAGE)
 os/check: $(CHECK_DEPS)
        $(CHECK)
@@ -4078,10 +4156,8 @@ strings/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: strings/check
 
-sync/mutex.lo: $(go_sync_files) runtime.gox
+sync/sync.lo: $(go_sync_files) runtime.gox sync/atomic.gox
        $(BUILDPACKAGE)
-sync/cas.lo: $(go_sync_c_files) sync/mutex.lo
-       $(LTCOMPILE) -c -o sync/cas.lo $(srcdir)/go/sync/cas.c
 sync/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: sync/check
@@ -4178,6 +4254,13 @@ archive/zip/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: archive/zip/check
 
+compress/bzip2.lo: $(go_compress_bzip2_files) bufio.gox io.gox os.gox sort.gox
+       $(BUILDPACKAGE)
+compress/bzip2/check: $(CHECK_DEPS)
+       @$(MKDIR_P) compress/bzip2
+       $(CHECK)
+.PHONY: compress/bzip2/check
+
 compress/flate.lo: $(go_compress_flate_files) bufio.gox io.gox math.gox \
                os.gox sort.gox strconv.gox
        $(BUILDPACKAGE)
@@ -4194,6 +4277,13 @@ compress/gzip/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: compress/gzip/check
 
+compress/lzw.lo: $(go_compress_lzw_files) bufio.gox fmt.gox io.gox os.gox
+       $(BUILDPACKAGE)
+compress/lzw/check: $(CHECK_DEPS)
+       @$(MKDIR_P) compress/lzw
+       $(CHECK)
+.PHONY: compress/lzw/check
+
 compress/zlib.lo: $(go_compress_zlib_files) bufio.gox compress/flate.gox \
                hash.gox hash/adler32.gox io.gox os.gox
        $(BUILDPACKAGE)
@@ -4265,6 +4355,13 @@ crypto/cipher/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/cipher/check
 
+crypto/dsa.lo: $(go_crypto_dsa_files) big.gox io.gox os.gox
+       $(BUILDPACKAGE)
+crypto/dsa/check: $(CHECK_DEPS)
+       @$(MKDIR_P) crypto/dsa
+       $(CHECK)
+.PHONY: crypto/dsa/check
+
 crypto/elliptic.lo: $(go_crypto_elliptic_files) big.gox io.gox os.gox sync.gox
        $(BUILDPACKAGE)
 crypto/elliptic/check: $(CHECK_DEPS)
@@ -4280,21 +4377,21 @@ crypto/hmac/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/hmac/check
 
-crypto/md4.lo: $(go_crypto_md4_files) hash.gox os.gox
+crypto/md4.lo: $(go_crypto_md4_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/md4/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/md4
        $(CHECK)
 .PHONY: crypto/md4/check
 
-crypto/md5.lo: $(go_crypto_md5_files) hash.gox os.gox
+crypto/md5.lo: $(go_crypto_md5_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/md5/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/md5
        $(CHECK)
 .PHONY: crypto/md5/check
 
-crypto/ocsp.lo: $(go_crypto_ocsp_files) asn1.gox crypto/rsa.gox \
+crypto/ocsp.lo: $(go_crypto_ocsp_files) asn1.gox crypto.gox crypto/rsa.gox \
                crypto/sha1.gox crypto/x509.gox os.gox time.gox
        $(BUILDPACKAGE)
 crypto/ocsp/check: $(CHECK_DEPS)
@@ -4302,8 +4399,18 @@ crypto/ocsp/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/ocsp/check
 
-crypto/rand.lo: $(go_crypto_rand_files) crypto/aes.gox io.gox os.gox sync.gox \
-               time.gox
+crypto/openpgp.lo: $(go_crypto_openpgp_files) crypto.gox \
+                crypto/openpgp/armor.gox crypto/openpgp/error.gox \
+               crypto/openpgp/packet.gox crypto/rsa.gox crypto/sha256.gox \
+               hash.gox io.gox os.gox strconv.gox time.gox
+       $(BUILDPACKAGE)
+crypto/openpgp/check: $(CHECK_DEPS)
+       @$(MKDIR_P) crypto/openpgp
+       $(CHECK)
+.PHONY: crypto/openpgp/check
+
+crypto/rand.lo: $(go_crypto_rand_files) bufio.gox crypto/aes.gox io.gox \
+               os.gox sync.gox time.gox
        $(BUILDPACKAGE)
 crypto/rand/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/rand
@@ -4317,14 +4424,14 @@ crypto/rc4/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/rc4/check
 
-crypto/ripemd160.lo: $(go_crypto_ripemd160_files) hash.gox os.gox
+crypto/ripemd160.lo: $(go_crypto_ripemd160_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/ripemd160/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/ripemd160
        $(CHECK)
 .PHONY: crypto/ripemd160/check
 
-crypto/rsa.lo: $(go_crypto_rsa_files) big.gox crypto/sha1.gox \
+crypto/rsa.lo: $(go_crypto_rsa_files) big.gox crypto.gox crypto/sha1.gox \
                crypto/subtle.gox encoding/hex.gox hash.gox io.gox os.gox
        $(BUILDPACKAGE)
 crypto/rsa/check: $(CHECK_DEPS)
@@ -4332,21 +4439,21 @@ crypto/rsa/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/rsa/check
 
-crypto/sha1.lo: $(go_crypto_sha1_files) hash.gox os.gox
+crypto/sha1.lo: $(go_crypto_sha1_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/sha1/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/sha1
        $(CHECK)
 .PHONY: crypto/sha1/check
 
-crypto/sha256.lo: $(go_crypto_sha256_files) hash.gox os.gox
+crypto/sha256.lo: $(go_crypto_sha256_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/sha256/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/sha256
        $(CHECK)
 .PHONY: crypto/sha256/check
 
-crypto/sha512.lo: $(go_crypto_sha512_files) hash.gox os.gox
+crypto/sha512.lo: $(go_crypto_sha512_files) crypto.gox hash.gox os.gox
        $(BUILDPACKAGE)
 crypto/sha512/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/sha512
@@ -4361,7 +4468,7 @@ crypto/subtle/check: $(CHECK_DEPS)
 .PHONY: crypto/subtle/check
 
 crypto/tls.lo: $(go_crypto_tls_files) big.gox bufio.gox bytes.gox \
-               container/list.gox crypto/aes.gox crypto/cipher.gox \
+               container/list.gox crypto.gox crypto/aes.gox crypto/cipher.gox \
                crypto/elliptic.gox crypto/hmac.gox crypto/md5.gox \
                crypto/rc4.gox crypto/rand.gox crypto/rsa.gox crypto/sha1.gox \
                crypto/subtle.gox crypto/rsa.gox crypto/sha1.gox \
@@ -4381,8 +4488,8 @@ crypto/twofish/check: $(CHECK_DEPS)
 .PHONY: crypto/twofish/check
 
 crypto/x509.lo: $(go_crypto_x509_files) asn1.gox big.gox container/vector.gox \
-               crypto/rsa.gox crypto/sha1.gox hash.gox os.gox strings.gox \
-               time.gox
+               crypto.gox crypto/rsa.gox crypto/sha1.gox hash.gox os.gox \
+               strings.gox time.gox
        $(BUILDPACKAGE)
 crypto/x509/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/x509
@@ -4405,16 +4512,30 @@ crypto/openpgp/armor/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: crypto/openpgp/armor/check
 
-crypto/openpgp/error.lo: $(go_crypto_openpgp_error_files)
+crypto/openpgp/error.lo: $(go_crypto_openpgp_error_files) strconv.gox
        $(BUILDPACKAGE)
 crypto/openpgp/error/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/openpgp/error
        $(CHECK)
 .PHONY: crypto/openpgp/error/check
 
-crypto/openpgp/s2k.lo: $(go_crypto_openpgp_s2k_files) crypto/md5.gox \
-               crypto/openpgp/error.gox crypto/ripemd160.gox crypto/sha1.gox \
-               crypto/sha256.gox crypto/sha512.gox hash.gox io.gox os.gox
+crypto/openpgp/packet.lo: $(go_crypto_openpgp_packet_files) big.gox bytes.gox \
+               compress/flate.gox compress/zlib.gox crypto.gox \
+               crypto/aes.gox crypto/cast5.gox crypto/cipher.gox \
+               crypto/openpgp/error.gox crypto/openpgp/s2k.gox \
+               crypto/rand.gox crypto/rsa.gox crypto/sha1.gox \
+               crypto/subtle.gox encoding/binary.gox hash.gox io.gox \
+               io/ioutil.gox os.gox strconv.gox strings.gox
+       $(BUILDPACKAGE)
+crypto/openpgp/packet/check: $(CHECK_DEPS)
+       @$(MKDIR_P) crypto/openpgp/packet
+       $(CHECK)
+.PHONY: crypto/openpgp/packet/check
+
+crypto/openpgp/s2k.lo: $(go_crypto_openpgp_s2k_files) crypto.gox \
+               crypto/md5.gox crypto/openpgp/error.gox crypto/ripemd160.gox \
+               crypto/sha1.gox crypto/sha256.gox crypto/sha512.gox hash.gox \
+               io.gox os.gox
        $(BUILDPACKAGE)
 crypto/openpgp/s2k/check: $(CHECK_DEPS)
        @$(MKDIR_P) crypto/openpgp/s2k
@@ -4733,6 +4854,15 @@ runtime/pprof/check: $(CHECK_DEPS)
        $(CHECK)
 .PHONY: runtime/pprof/check
 
+sync/atomic.lo: $(go_sync_atomic_files)
+       $(BUILDPACKAGE)
+sync/atomic_c.lo: $(go_sync_atomic_c_files) sync/atomic.lo
+       $(LTCOMPILE) -c -o $@ $(srcdir)/go/sync/atomic/atomic.c
+sync/atomic/check: $(CHECK_DEPS)
+       @$(MKDIR_P) sync/atomic
+       $(CHECK)
+.PHONY: sync/atomic/check
+
 testing/iotest.lo: $(go_testing_iotest_files) io.gox log.gox os.gox
        $(BUILDPACKAGE)
 testing/iotest/check: $(CHECK_DEPS)
@@ -4777,6 +4907,8 @@ bytes.gox: bytes/bytes.lo
        $(BUILDGOX)
 cmath.gox: cmath/cmath.lo
        $(BUILDGOX)
+crypto.gox: crypto/crypto.lo
+       $(BUILDGOX)
 ebnf.gox: ebnf/ebnf.lo
        $(BUILDGOX)
 exec.gox: exec/exec.lo
@@ -4837,7 +4969,7 @@ strconv.gox: strconv/strconv.lo
        $(BUILDGOX)
 strings.gox: strings/strings.lo
        $(BUILDGOX)
-sync.gox: sync/mutex.lo
+sync.gox: sync/sync.lo
        $(BUILDGOX)
 syslog.gox: syslog/syslog.lo
        $(BUILDGOX)
@@ -4869,10 +5001,14 @@ archive/tar.gox: archive/tar.lo
 archive/zip.gox: archive/zip.lo
        $(BUILDGOX)
 
+compress/bzip2.gox: compress/bzip2.lo
+       $(BUILDGOX)
 compress/flate.gox: compress/flate.lo
        $(BUILDGOX)
 compress/gzip.gox: compress/gzip.lo
        $(BUILDGOX)
+compress/lzw.gox: compress/lzw.lo
+       $(BUILDGOX)
 compress/zlib.gox: compress/zlib.lo
        $(BUILDGOX)
 
@@ -4895,6 +5031,8 @@ crypto/cast5.gox: crypto/cast5.lo
        $(BUILDGOX)
 crypto/cipher.gox: crypto/cipher.lo
        $(BUILDGOX)
+crypto/dsa.gox: crypto/dsa.lo
+       $(BUILDGOX)
 crypto/elliptic.gox: crypto/elliptic.lo
        $(BUILDGOX)
 crypto/hmac.gox: crypto/hmac.lo
@@ -4905,6 +5043,8 @@ crypto/md5.gox: crypto/md5.lo
        $(BUILDGOX)
 crypto/ocsp.gox: crypto/ocsp.lo
        $(BUILDGOX)
+crypto/openpgp.gox: crypto/openpgp.lo
+       $(BUILDGOX)
 crypto/rand.gox: crypto/rand.lo
        $(BUILDGOX)
 crypto/rc4.gox: crypto/rc4.lo
@@ -4934,6 +5074,8 @@ crypto/openpgp/armor.gox: crypto/openpgp/armor.lo
        $(BUILDGOX)
 crypto/openpgp/error.gox: crypto/openpgp/error.lo
        $(BUILDGOX)
+crypto/openpgp/packet.gox: crypto/openpgp/packet.lo
+       $(BUILDGOX)
 crypto/openpgp/s2k.gox: crypto/openpgp/s2k.lo
        $(BUILDGOX)
 
@@ -5031,6 +5173,9 @@ runtime/debug.gox: runtime/debug.lo
 runtime/pprof.gox: runtime/pprof.lo
        $(BUILDGOX)
 
+sync/atomic.gox: sync/atomic.lo
+       $(BUILDGOX)
+
 testing/iotest.gox: testing/iotest.lo
        $(BUILDGOX)
 testing/quick.gox: testing/quick.lo
index 579ba16..d8d9bba 100644 (file)
@@ -42,6 +42,10 @@ type File struct {
        bodyOffset   int64
 }
 
+func (f *File) hasDataDescriptor() bool {
+       return f.Flags&0x8 != 0
+}
+
 // OpenReader will open the Zip file specified by name and return a Reader.
 func OpenReader(name string) (*Reader, os.Error) {
        f, err := os.Open(name, os.O_RDONLY, 0644)
@@ -93,7 +97,16 @@ func (f *File) Open() (rc io.ReadCloser, err os.Error) {
                        return
                }
        }
-       r := io.NewSectionReader(f.zipr, off+f.bodyOffset, int64(f.CompressedSize))
+       size := int64(f.CompressedSize)
+       if f.hasDataDescriptor() {
+               if size == 0 {
+                       // permit SectionReader to see the rest of the file
+                       size = f.zipsize - (off + f.bodyOffset)
+               } else {
+                       size += dataDescriptorLen
+               }
+       }
+       r := io.NewSectionReader(f.zipr, off+f.bodyOffset, size)
        switch f.Method {
        case 0: // store (no compression)
                rc = nopCloser{r}
@@ -103,7 +116,7 @@ func (f *File) Open() (rc io.ReadCloser, err os.Error) {
                err = UnsupportedMethod
        }
        if rc != nil {
-               rc = &checksumReader{rc, crc32.NewIEEE(), f.CRC32}
+               rc = &checksumReader{rc, crc32.NewIEEE(), f, r}
        }
        return
 }
@@ -111,7 +124,8 @@ func (f *File) Open() (rc io.ReadCloser, err os.Error) {
 type checksumReader struct {
        rc   io.ReadCloser
        hash hash.Hash32
-       sum  uint32
+       f    *File
+       zipr io.Reader // for reading the data descriptor
 }
 
 func (r *checksumReader) Read(b []byte) (n int, err os.Error) {
@@ -120,7 +134,12 @@ func (r *checksumReader) Read(b []byte) (n int, err os.Error) {
        if err != os.EOF {
                return
        }
-       if r.hash.Sum32() != r.sum {
+       if r.f.hasDataDescriptor() {
+               if err = readDataDescriptor(r.zipr, r.f); err != nil {
+                       return
+               }
+       }
+       if r.hash.Sum32() != r.f.CRC32 {
                err = ChecksumError
        }
        return
@@ -205,6 +224,18 @@ func readDirectoryHeader(f *File, r io.Reader) (err os.Error) {
        return
 }
 
+func readDataDescriptor(r io.Reader, f *File) (err os.Error) {
+       defer func() {
+               if rerr, ok := recover().(os.Error); ok {
+                       err = rerr
+               }
+       }()
+       read(r, &f.CRC32)
+       read(r, &f.CompressedSize)
+       read(r, &f.UncompressedSize)
+       return
+}
+
 func readDirectoryEnd(r io.ReaderAt, size int64) (d *directoryEnd, err os.Error) {
        // look for directoryEndSignature in the last 1k, then in the last 65k
        var b []byte
index 3c24f14..72e8ccc 100644 (file)
@@ -52,6 +52,15 @@ var tests = []ZipTest{
        },
        {Name: "readme.zip"},
        {Name: "readme.notzip", Error: FormatError},
+       {
+               Name: "dd.zip",
+               File: []ZipTestFile{
+                       {
+                               Name:    "filename",
+                               Content: []byte("This is a test textfile.\n"),
+                       },
+               },
+       },
 }
 
 func TestReader(t *testing.T) {
@@ -102,16 +111,18 @@ func readTestZip(t *testing.T, zt ZipTest) {
        }
 
        // test invalid checksum
-       z.File[0].CRC32++ // invalidate
-       r, err := z.File[0].Open()
-       if err != nil {
-               t.Error(err)
-               return
-       }
-       var b bytes.Buffer
-       _, err = io.Copy(&b, r)
-       if err != ChecksumError {
-               t.Errorf("%s: copy error=%v, want %v", z.File[0].Name, err, ChecksumError)
+       if !z.File[0].hasDataDescriptor() { // skip test when crc32 in dd
+               z.File[0].CRC32++ // invalidate
+               r, err := z.File[0].Open()
+               if err != nil {
+                       t.Error(err)
+                       return
+               }
+               var b bytes.Buffer
+               _, err = io.Copy(&b, r)
+               if err != ChecksumError {
+                       t.Errorf("%s: copy error=%v, want %v", z.File[0].Name, err, ChecksumError)
+               }
        }
 }
 
index 8a8c727..bfe0aae 100644 (file)
@@ -4,6 +4,7 @@ const (
        fileHeaderSignature      = 0x04034b50
        directoryHeaderSignature = 0x02014b50
        directoryEndSignature    = 0x06054b50
+       dataDescriptorLen        = 12
 )
 
 type FileHeader struct {
index 2454871..57b8f20 100644 (file)
@@ -317,7 +317,7 @@ func marshalBody(out *forkableWriter, value reflect.Value, params fieldParameter
        switch v := value.(type) {
        case *reflect.BoolValue:
                if v.Get() {
-                       return out.WriteByte(1)
+                       return out.WriteByte(255)
                } else {
                        return out.WriteByte(0)
                }
index c13456a..eae5c5c 100644 (file)
@@ -286,7 +286,8 @@ func (b *Reader) ReadSlice(delim byte) (line []byte, err os.Error) {
 // returning a slice containing the data up to and including the delimiter.
 // If ReadBytes encounters an error before finding a delimiter,
 // it returns the data read before the error and the error itself (often os.EOF).
-// ReadBytes returns err != nil if and only if line does not end in delim.
+// ReadBytes returns err != nil if and only if the returned data does not end in
+// delim.
 func (b *Reader) ReadBytes(delim byte) (line []byte, err os.Error) {
        // Use ReadSlice to look for array,
        // accumulating full buffers.
@@ -332,7 +333,8 @@ func (b *Reader) ReadBytes(delim byte) (line []byte, err os.Error) {
 // returning a string containing the data up to and including the delimiter.
 // If ReadString encounters an error before finding a delimiter,
 // it returns the data read before the error and the error itself (often os.EOF).
-// ReadString returns err != nil if and only if line does not end in delim.
+// ReadString returns err != nil if and only if the returned data does not end in
+// delim.
 func (b *Reader) ReadString(delim byte) (line string, err os.Error) {
        bytes, e := b.ReadBytes(delim)
        return string(bytes), e
@@ -383,6 +385,9 @@ func (b *Writer) Flush() os.Error {
        if b.err != nil {
                return b.err
        }
+       if b.n == 0 {
+               return nil
+       }
        n, e := b.wr.Write(b.buf[0:b.n])
        if n < b.n && e == nil {
                e = io.ErrShortWrite
index 62cf828..1acd4e0 100644 (file)
@@ -154,17 +154,20 @@ func (b *Buffer) ReadFrom(r io.Reader) (n int64, err os.Error) {
 }
 
 // WriteTo writes data to w until the buffer is drained or an error
-// occurs. The return value n is the number of bytes written.
+// occurs. The return value n is the number of bytes written; it always
+// fits into an int, but it is int64 to match the io.WriterTo interface.
 // Any error encountered during the write is also returned.
 func (b *Buffer) WriteTo(w io.Writer) (n int64, err os.Error) {
        b.lastRead = opInvalid
-       for b.off < len(b.buf) {
+       if b.off < len(b.buf) {
                m, e := w.Write(b.buf[b.off:])
-               n += int64(m)
                b.off += m
+               n = int64(m)
                if e != nil {
                        return n, e
                }
+               // otherwise all bytes were written, by definition of
+               // Write method in io.Writer
        }
        // Buffer is now empty; reset.
        b.Truncate(0)
@@ -301,6 +304,36 @@ func (b *Buffer) UnreadByte() os.Error {
        return nil
 }
 
+// ReadBytes reads until the first occurrence of delim in the input,
+// returning a slice containing the data up to and including the delimiter.
+// If ReadBytes encounters an error before finding a delimiter,
+// it returns the data read before the error and the error itself (often os.EOF).
+// ReadBytes returns err != nil if and only if the returned data does not end in
+// delim.
+func (b *Buffer) ReadBytes(delim byte) (line []byte, err os.Error) {
+       i := IndexByte(b.buf[b.off:], delim)
+       size := i + 1
+       if i < 0 {
+               size = len(b.buf) - b.off
+               err = os.EOF
+       }
+       line = make([]byte, size)
+       copy(line, b.buf[b.off:])
+       b.off += size
+       return
+}
+
+// ReadString reads until the first occurrence of delim in the input,
+// returning a string containing the data up to and including the delimiter.
+// If ReadString encounters an error before finding a delimiter,
+// it returns the data read before the error and the error itself (often os.EOF).
+// ReadString returns err != nil if and only if the returned data does not end
+// in delim.
+func (b *Buffer) ReadString(delim byte) (line string, err os.Error) {
+       bytes, err := b.ReadBytes(delim)
+       return string(bytes), err
+}
+
 // NewBuffer creates and initializes a new Buffer using buf as its initial
 // contents.  It is intended to prepare a Buffer to read existing data.  It
 // can also be used to size the internal buffer for writing.  To do that,
index 509793d..56a2d92 100644 (file)
@@ -6,6 +6,7 @@ package bytes_test
 
 import (
        . "bytes"
+       "os"
        "rand"
        "testing"
        "utf8"
@@ -238,7 +239,7 @@ func TestMixedReadsAndWrites(t *testing.T) {
 func TestNil(t *testing.T) {
        var b *Buffer
        if b.String() != "<nil>" {
-               t.Errorf("expcted <nil>; got %q", b.String())
+               t.Errorf("expected <nil>; got %q", b.String())
        }
 }
 
@@ -347,3 +348,38 @@ func TestNext(t *testing.T) {
                }
        }
 }
+
+var readBytesTests = []struct {
+       buffer   string
+       delim    byte
+       expected []string
+       err      os.Error
+}{
+       {"", 0, []string{""}, os.EOF},
+       {"a\x00", 0, []string{"a\x00"}, nil},
+       {"abbbaaaba", 'b', []string{"ab", "b", "b", "aaab"}, nil},
+       {"hello\x01world", 1, []string{"hello\x01"}, nil},
+       {"foo\nbar", 0, []string{"foo\nbar"}, os.EOF},
+       {"alpha\nbeta\ngamma\n", '\n', []string{"alpha\n", "beta\n", "gamma\n"}, nil},
+       {"alpha\nbeta\ngamma", '\n', []string{"alpha\n", "beta\n", "gamma"}, os.EOF},
+}
+
+func TestReadBytes(t *testing.T) {
+       for _, test := range readBytesTests {
+               buf := NewBufferString(test.buffer)
+               var err os.Error
+               for _, expected := range test.expected {
+                       var bytes []byte
+                       bytes, err = buf.ReadBytes(test.delim)
+                       if string(bytes) != expected {
+                               t.Errorf("expected %q, got %q", expected, bytes)
+                       }
+                       if err != nil {
+                               break
+                       }
+               }
+               if err != test.err {
+                       t.Errorf("expected error %v, got %v", test.err, err)
+               }
+       }
+}
diff --git a/libgo/go/compress/bzip2/bit_reader.go b/libgo/go/compress/bzip2/bit_reader.go
new file mode 100644 (file)
index 0000000..50f0ec8
--- /dev/null
@@ -0,0 +1,88 @@
+// Copyright 2011 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 bzip2
+
+import (
+       "bufio"
+       "io"
+       "os"
+)
+
+// bitReader wraps an io.Reader and provides the ability to read values,
+// bit-by-bit, from it. Its Read* methods don't return the usual os.Error
+// because the error handling was verbose. Instead, any error is kept and can
+// be checked afterwards.
+type bitReader struct {
+       r    byteReader
+       n    uint64
+       bits uint
+       err  os.Error
+}
+
+// bitReader needs to read bytes from an io.Reader. We attempt to cast the
+// given io.Reader to this interface and, if it doesn't already fit, we wrap in
+// a bufio.Reader.
+type byteReader interface {
+       ReadByte() (byte, os.Error)
+}
+
+func newBitReader(r io.Reader) bitReader {
+       byter, ok := r.(byteReader)
+       if !ok {
+               byter = bufio.NewReader(r)
+       }
+       return bitReader{r: byter}
+}
+
+// ReadBits64 reads the given number of bits and returns them in the
+// least-significant part of a uint64. In the event of an error, it returns 0
+// and the error can be obtained by calling Error().
+func (br *bitReader) ReadBits64(bits uint) (n uint64) {
+       for bits > br.bits {
+               b, err := br.r.ReadByte()
+               if err == os.EOF {
+                       err = io.ErrUnexpectedEOF
+               }
+               if err != nil {
+                       br.err = err
+                       return 0
+               }
+               br.n <<= 8
+               br.n |= uint64(b)
+               br.bits += 8
+       }
+
+       // br.n looks like this (assuming that br.bits = 14 and bits = 6):
+       // Bit: 111111
+       //      5432109876543210
+       //
+       //         (6 bits, the desired output)
+       //        |-----|
+       //        V     V
+       //      0101101101001110
+       //        ^            ^
+       //        |------------|
+       //           br.bits (num valid bits)
+       //
+       // This the next line right shifts the desired bits into the
+       // least-significant places and masks off anything above.
+       n = (br.n >> (br.bits - bits)) & ((1 << bits) - 1)
+       br.bits -= bits
+       return
+}
+
+func (br *bitReader) ReadBits(bits uint) (n int) {
+       n64 := br.ReadBits64(bits)
+       return int(n64)
+}
+
+func (br *bitReader) ReadBit() bool {
+       n := br.ReadBits(1)
+       return n != 0
+}
+
+func (br *bitReader) Error() os.Error {
+       return br.err
+}
diff --git a/libgo/go/compress/bzip2/bzip2.go b/libgo/go/compress/bzip2/bzip2.go
new file mode 100644 (file)
index 0000000..9e97ede
--- /dev/null
@@ -0,0 +1,390 @@
+// Copyright 2011 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 bzip2 implements bzip2 decompression.
+package bzip2
+
+import (
+       "io"
+       "os"
+)
+
+// There's no RFC for bzip2. I used the Wikipedia page for reference and a lot
+// of guessing: http://en.wikipedia.org/wiki/Bzip2
+// The source code to pyflate was useful for debugging:
+// http://www.paul.sladen.org/projects/pyflate
+
+// A StructuralError is returned when the bzip2 data is found to be
+// syntactically invalid.
+type StructuralError string
+
+func (s StructuralError) String() string {
+       return "bzip2 data invalid: " + string(s)
+}
+
+// A reader decompresses bzip2 compressed data.
+type reader struct {
+       br        bitReader
+       setupDone bool // true if we have parsed the bzip2 header.
+       blockSize int  // blockSize in bytes, i.e. 900 * 1024.
+       eof       bool
+       buf       []byte    // stores Burrows-Wheeler transformed data.
+       c         [256]uint // the `C' array for the inverse BWT.
+       tt        []uint32  // mirrors the `tt' array in the bzip2 source and contains the P array in the upper 24 bits.
+       tPos      uint32    // Index of the next output byte in tt.
+
+       preRLE      []uint32 // contains the RLE data still to be processed.
+       preRLEUsed  int      // number of entries of preRLE used.
+       lastByte    int      // the last byte value seen.
+       byteRepeats uint     // the number of repeats of lastByte seen.
+       repeats     uint     // the number of copies of lastByte to output.
+}
+
+// NewReader returns an io.Reader which decompresses bzip2 data from r.
+func NewReader(r io.Reader) io.Reader {
+       bz2 := new(reader)
+       bz2.br = newBitReader(r)
+       return bz2
+}
+
+const bzip2FileMagic = 0x425a // "BZ"
+const bzip2BlockMagic = 0x314159265359
+const bzip2FinalMagic = 0x177245385090
+
+// setup parses the bzip2 header.
+func (bz2 *reader) setup() os.Error {
+       br := &bz2.br
+
+       magic := br.ReadBits(16)
+       if magic != bzip2FileMagic {
+               return StructuralError("bad magic value")
+       }
+
+       t := br.ReadBits(8)
+       if t != 'h' {
+               return StructuralError("non-Huffman entropy encoding")
+       }
+
+       level := br.ReadBits(8)
+       if level < '1' || level > '9' {
+               return StructuralError("invalid compression level")
+       }
+
+       bz2.blockSize = 100 * 1024 * (int(level) - '0')
+       bz2.tt = make([]uint32, bz2.blockSize)
+       return nil
+}
+
+func (bz2 *reader) Read(buf []byte) (n int, err os.Error) {
+       if bz2.eof {
+               return 0, os.EOF
+       }
+
+       if !bz2.setupDone {
+               err = bz2.setup()
+               brErr := bz2.br.Error()
+               if brErr != nil {
+                       err = brErr
+               }
+               if err != nil {
+                       return 0, err
+               }
+               bz2.setupDone = true
+       }
+
+       n, err = bz2.read(buf)
+       brErr := bz2.br.Error()
+       if brErr != nil {
+               err = brErr
+       }
+       return
+}
+
+func (bz2 *reader) read(buf []byte) (n int, err os.Error) {
+       // bzip2 is a block based compressor, except that it has a run-length
+       // preprocessing step. The block based nature means that we can
+       // preallocate fixed-size buffers and reuse them. However, the RLE
+       // preprocessing would require allocating huge buffers to store the
+       // maximum expansion. Thus we process blocks all at once, except for
+       // the RLE which we decompress as required.
+
+       for (bz2.repeats > 0 || bz2.preRLEUsed < len(bz2.preRLE)) && n < len(buf) {
+               // We have RLE data pending.
+
+               // The run-length encoding works like this:
+               // Any sequence of four equal bytes is followed by a length
+               // byte which contains the number of repeats of that byte to
+               // include. (The number of repeats can be zero.) Because we are
+               // decompressing on-demand our state is kept in the reader
+               // object.
+
+               if bz2.repeats > 0 {
+                       buf[n] = byte(bz2.lastByte)
+                       n++
+                       bz2.repeats--
+                       if bz2.repeats == 0 {
+                               bz2.lastByte = -1
+                       }
+                       continue
+               }
+
+               bz2.tPos = bz2.preRLE[bz2.tPos]
+               b := byte(bz2.tPos)
+               bz2.tPos >>= 8
+               bz2.preRLEUsed++
+
+               if bz2.byteRepeats == 3 {
+                       bz2.repeats = uint(b)
+                       bz2.byteRepeats = 0
+                       continue
+               }
+
+               if bz2.lastByte == int(b) {
+                       bz2.byteRepeats++
+               } else {
+                       bz2.byteRepeats = 0
+               }
+               bz2.lastByte = int(b)
+
+               buf[n] = b
+               n++
+       }
+
+       if n > 0 {
+               return
+       }
+
+       // No RLE data is pending so we need to read a block.
+
+       br := &bz2.br
+       magic := br.ReadBits64(48)
+       if magic == bzip2FinalMagic {
+               br.ReadBits64(32) // ignored CRC
+               bz2.eof = true
+               return 0, os.EOF
+       } else if magic != bzip2BlockMagic {
+               return 0, StructuralError("bad magic value found")
+       }
+
+       err = bz2.readBlock()
+       if err != nil {
+               return 0, err
+       }
+
+       return bz2.read(buf)
+}
+
+// readBlock reads a bzip2 block. The magic number should already have been consumed.
+func (bz2 *reader) readBlock() (err os.Error) {
+       br := &bz2.br
+       br.ReadBits64(32) // skip checksum. TODO: check it if we can figure out what it is.
+       randomized := br.ReadBits(1)
+       if randomized != 0 {
+               return StructuralError("deprecated randomized files")
+       }
+       origPtr := uint(br.ReadBits(24))
+
+       // If not every byte value is used in the block (i.e., it's text) then
+       // the symbol set is reduced. The symbols used are stored as a
+       // two-level, 16x16 bitmap.
+       symbolRangeUsedBitmap := br.ReadBits(16)
+       symbolPresent := make([]bool, 256)
+       numSymbols := 0
+       for symRange := uint(0); symRange < 16; symRange++ {
+               if symbolRangeUsedBitmap&(1<<(15-symRange)) != 0 {
+                       bits := br.ReadBits(16)
+                       for symbol := uint(0); symbol < 16; symbol++ {
+                               if bits&(1<<(15-symbol)) != 0 {
+                                       symbolPresent[16*symRange+symbol] = true
+                                       numSymbols++
+                               }
+                       }
+               }
+       }
+
+       // A block uses between two and six different Huffman trees.
+       numHuffmanTrees := br.ReadBits(3)
+       if numHuffmanTrees < 2 || numHuffmanTrees > 6 {
+               return StructuralError("invalid number of Huffman trees")
+       }
+
+       // The Huffman tree can switch every 50 symbols so there's a list of
+       // tree indexes telling us which tree to use for each 50 symbol block.
+       numSelectors := br.ReadBits(15)
+       treeIndexes := make([]uint8, numSelectors)
+
+       // The tree indexes are move-to-front transformed and stored as unary
+       // numbers.
+       mtfTreeDecoder := newMTFDecoderWithRange(numHuffmanTrees)
+       for i := range treeIndexes {
+               c := 0
+               for {
+                       inc := br.ReadBits(1)
+                       if inc == 0 {
+                               break
+                       }
+                       c++
+               }
+               if c >= numHuffmanTrees {
+                       return StructuralError("tree index too large")
+               }
+               treeIndexes[i] = uint8(mtfTreeDecoder.Decode(c))
+       }
+
+       // The list of symbols for the move-to-front transform is taken from
+       // the previously decoded symbol bitmap.
+       symbols := make([]byte, numSymbols)
+       nextSymbol := 0
+       for i := 0; i < 256; i++ {
+               if symbolPresent[i] {
+                       symbols[nextSymbol] = byte(i)
+                       nextSymbol++
+               }
+       }
+       mtf := newMTFDecoder(symbols)
+
+       numSymbols += 2 // to account for RUNA and RUNB symbols
+       huffmanTrees := make([]huffmanTree, numHuffmanTrees)
+
+       // Now we decode the arrays of code-lengths for each tree.
+       lengths := make([]uint8, numSymbols)
+       for i := 0; i < numHuffmanTrees; i++ {
+               // The code lengths are delta encoded from a 5-bit base value.
+               length := br.ReadBits(5)
+               for j := 0; j < numSymbols; j++ {
+                       for {
+                               if !br.ReadBit() {
+                                       break
+                               }
+                               if br.ReadBit() {
+                                       length--
+                               } else {
+                                       length++
+                               }
+                       }
+                       if length < 0 || length > 20 {
+                               return StructuralError("Huffman length out of range")
+                       }
+                       lengths[j] = uint8(length)
+               }
+               huffmanTrees[i], err = newHuffmanTree(lengths)
+               if err != nil {
+                       return err
+               }
+       }
+
+       selectorIndex := 1 // the next tree index to use
+       currentHuffmanTree := huffmanTrees[treeIndexes[0]]
+       bufIndex := 0 // indexes bz2.buf, the output buffer.
+       // The output of the move-to-front transform is run-length encoded and
+       // we merge the decoding into the Huffman parsing loop. These two
+       // variables accumulate the repeat count. See the Wikipedia page for
+       // details.
+       repeat := 0
+       repeat_power := 0
+
+       // The `C' array (used by the inverse BWT) needs to be zero initialised.
+       for i := range bz2.c {
+               bz2.c[i] = 0
+       }
+
+       decoded := 0 // counts the number of symbols decoded by the current tree.
+       for {
+               if decoded == 50 {
+                       currentHuffmanTree = huffmanTrees[treeIndexes[selectorIndex]]
+                       selectorIndex++
+                       decoded = 0
+               }
+
+               v := currentHuffmanTree.Decode(br)
+               decoded++
+
+               if v < 2 {
+                       // This is either the RUNA or RUNB symbol.
+                       if repeat == 0 {
+                               repeat_power = 1
+                       }
+                       repeat += repeat_power << v
+                       repeat_power <<= 1
+
+                       // This limit of 2 million comes from the bzip2 source
+                       // code. It prevents repeat from overflowing.
+                       if repeat > 2*1024*1024 {
+                               return StructuralError("repeat count too large")
+                       }
+                       continue
+               }
+
+               if repeat > 0 {
+                       // We have decoded a complete run-length so we need to
+                       // replicate the last output symbol.
+                       for i := 0; i < repeat; i++ {
+                               b := byte(mtf.First())
+                               bz2.tt[bufIndex] = uint32(b)
+                               bz2.c[b]++
+                               bufIndex++
+                       }
+                       repeat = 0
+               }
+
+               if int(v) == numSymbols-1 {
+                       // This is the EOF symbol. Because it's always at the
+                       // end of the move-to-front list, and nevers gets moved
+                       // to the front, it has this unique value.
+                       break
+               }
+
+               // Since two metasymbols (RUNA and RUNB) have values 0 and 1,
+               // one would expect |v-2| to be passed to the MTF decoder.
+               // However, the front of the MTF list is never referenced as 0,
+               // it's always referenced with a run-length of 1. Thus 0
+               // doesn't need to be encoded and we have |v-1| in the next
+               // line.
+               b := byte(mtf.Decode(int(v - 1)))
+               bz2.tt[bufIndex] = uint32(b)
+               bz2.c[b]++
+               bufIndex++
+       }
+
+       if origPtr >= uint(bufIndex) {
+               return StructuralError("origPtr out of bounds")
+       }
+
+       // We have completed the entropy decoding. Now we can perform the
+       // inverse BWT and setup the RLE buffer.
+       bz2.preRLE = bz2.tt[:bufIndex]
+       bz2.preRLEUsed = 0
+       bz2.tPos = inverseBWT(bz2.preRLE, origPtr, bz2.c[:])
+       bz2.lastByte = -1
+       bz2.byteRepeats = 0
+       bz2.repeats = 0
+
+       return nil
+}
+
+// inverseBWT implements the inverse Burrows-Wheeler transform as described in
+// http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf, section 4.2.
+// In that document, origPtr is called `I' and c is the `C' array after the
+// first pass over the data. It's an argument here because we merge the first
+// pass with the Huffman decoding.
+//
+// This also implements the `single array' method from the bzip2 source code
+// which leaves the output, still shuffled, in the bottom 8 bits of tt with the
+// index of the next byte in the top 24-bits. The index of the first byte is
+// returned.
+func inverseBWT(tt []uint32, origPtr uint, c []uint) uint32 {
+       sum := uint(0)
+       for i := 0; i < 256; i++ {
+               sum += c[i]
+               c[i] = sum - c[i]
+       }
+
+       for i := range tt {
+               b := tt[i] & 0xff
+               tt[c[b]] |= uint32(i) << 8
+               c[b]++
+       }
+
+       return tt[origPtr] >> 8
+}
diff --git a/libgo/go/compress/bzip2/bzip2_test.go b/libgo/go/compress/bzip2/bzip2_test.go
new file mode 100644 (file)
index 0000000..156eea8
--- /dev/null
@@ -0,0 +1,158 @@
+// Copyright 2011 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 bzip2
+
+import (
+       "bytes"
+       "encoding/hex"
+       "io"
+       "io/ioutil"
+       "os"
+       "testing"
+)
+
+func TestBitReader(t *testing.T) {
+       buf := bytes.NewBuffer([]byte{0xaa})
+       br := newBitReader(buf)
+       if n := br.ReadBits(1); n != 1 {
+               t.Errorf("read 1 wrong")
+       }
+       if n := br.ReadBits(1); n != 0 {
+               t.Errorf("read 2 wrong")
+       }
+       if n := br.ReadBits(1); n != 1 {
+               t.Errorf("read 3 wrong")
+       }
+       if n := br.ReadBits(1); n != 0 {
+               t.Errorf("read 4 wrong")
+       }
+}
+
+func TestBitReaderLarge(t *testing.T) {
+       buf := bytes.NewBuffer([]byte{0x12, 0x34, 0x56, 0x78})
+       br := newBitReader(buf)
+       if n := br.ReadBits(32); n != 0x12345678 {
+               t.Errorf("got: %x want: %x", n, 0x12345678)
+       }
+}
+
+func readerFromHex(s string) io.Reader {
+       data, err := hex.DecodeString(s)
+       if err != nil {
+               panic("readerFromHex: bad input")
+       }
+       return bytes.NewBuffer(data)
+}
+
+func decompressHex(s string) (out []byte, err os.Error) {
+       r := NewReader(readerFromHex(s))
+       return ioutil.ReadAll(r)
+}
+
+func TestHelloWorldBZ2(t *testing.T) {
+       out, err := decompressHex(helloWorldBZ2Hex)
+       if err != nil {
+               t.Errorf("error from Read: %s", err)
+               return
+       }
+
+       if !bytes.Equal(helloWorld, out) {
+               t.Errorf("got %x, want %x", out, helloWorld)
+       }
+}
+
+func testZeros(t *testing.T, inHex string, n int) {
+       out, err := decompressHex(inHex)
+       if err != nil {
+               t.Errorf("error from Read: %s", err)
+               return
+       }
+
+       expected := make([]byte, n)
+
+       if !bytes.Equal(expected, out) {
+               allZeros := true
+               for _, b := range out {
+                       if b != 0 {
+                               allZeros = false
+                               break
+                       }
+               }
+               t.Errorf("incorrect result, got %d bytes (allZeros: %t)", len(out), allZeros)
+       }
+}
+
+func Test32Zeros(t *testing.T) {
+       testZeros(t, thirtyTwoZerosBZ2Hex, 32)
+}
+
+func Test1MBZeros(t *testing.T) {
+       testZeros(t, oneMBZerosBZ2Hex, 1024*1024)
+}
+
+func testRandomData(t *testing.T, compressedHex, uncompressedHex string) {
+       out, err := decompressHex(compressedHex)
+       if err != nil {
+               t.Errorf("error from Read: %s", err)
+               return
+       }
+
+       expected, _ := hex.DecodeString(uncompressedHex)
+
+       if !bytes.Equal(out, expected) {
+               t.Errorf("incorrect result\ngot:  %x\nwant: %x", out, expected)
+       }
+}
+
+func TestRandomData1(t *testing.T) {
+       testRandomData(t, randBZ2Hex, randHex)
+}
+
+func TestRandomData2(t *testing.T) {
+       // This test involves several repeated bytes in the output, but they
+       // should trigger RLE decoding.
+       testRandomData(t, rand2BZ2Hex, rand2Hex)
+}
+
+func TestRandomData3(t *testing.T) {
+       // This test uses the full range of symbols.
+       testRandomData(t, rand3BZ2Hex, rand3Hex)
+}
+
+func Test1MBSawtooth(t *testing.T) {
+       out, err := decompressHex(oneMBSawtoothBZ2Hex)
+       if err != nil {
+               t.Errorf("error from Read: %s", err)
+               return
+       }
+
+       expected := make([]byte, 1024*1024)
+
+       for i := range expected {
+               expected[i] = byte(i)
+       }
+
+       if !bytes.Equal(out, expected) {
+               t.Error("incorrect result")
+       }
+}
+
+const helloWorldBZ2Hex = "425a68393141592653594eece83600000251800010400006449080200031064c4101a7a9a580bb9431f8bb9229c28482776741b0"
+
+var helloWorld = []byte("hello world\n")
+
+const thirtyTwoZerosBZ2Hex = "425a6839314159265359b5aa5098000000600040000004200021008283177245385090b5aa5098"
+const oneMBZerosBZ2Hex = "425a683931415926535938571ce50008084000c0040008200030cc0529a60806c4201e2ee48a70a12070ae39ca"
+
+const randBZ2Hex = "425a6839314159265359905d990d0001957fffffffffffafffffffffffffffffbfff6fffdfffffffffffffffffffffffffffffc002b6dd75676ed5b77720098320d11a64626981323d4da47a83131a13d09e8040f534cd4f4d27a464d193008cd09804601347a980026350c9886234d36864193d1351b44c136919e90340d26127a4cd264c32023009898981310c0344c340027a8303427a99a04c00003534c230d034f5006468d268cf54d36a3009a69a62626261311b40026013d34201a6934c9a604c98ca6c8460989fa9346234d30d3469a2604fd4131a7aa6d0046043d4c62098479269e89e835190d018d4c046001a11e801a0264792321932308c43a130688c260d46686804cd01a9e80981193684c6a68c00000004c4c20c04627a4c0000260003400d04c0681a01334026009a6f48041466132581ec5212b081d96b0effc16543e2228b052fcd30f2567ee8d970e0f10aabca68dd8270591c376cfc1baae0dba00aaff2d6caf6b211322c997cc18eaee5927f75185336bf907021324c71626c1dd20e22b9b0977f05d0f901eaa51db9fbaf7c603b4c87bc82890e6dd7e61d0079e27ec050dd788fd958152061cd01e222f9547cb9efc465d775b6fc98bac7d387bffd151ae09dadf19494f7a638e2eae58e550faba5fe6820ea520eb986096de4e527d80def3ba625e71fbefdcf7e7844e0a25d29b52dcd1344fca083737d42692aab38d230485f3c8ed54c2ed31f15cf0270c8143765b10b92157233fa1dfe0d7ce8ffe70b8b8f7250071701dfe9f1c94de362c9031455951c93eb098a6b50ee45c6131fefc3b6f9643e21f4adc59497138e246f5c57d834aa67c4f10d8bd8b3908d8130dd7388409c299a268eab3664fa4907c5c31574874bd8d388a4ab22b339660804e53e1b8d05867d40e3082560608d35d5d2c6054e8bab23da28f61f83efd41d25529ad6ea15fb50505cacfabb0902166427354ca3830a2c8415f21b19e592690fbe447020d685a4bcd16ecc4ff1a1c0e572627d0ef6265c008a43fc243240541061ed7840606be466d1c0dac2c53250ed567507d926c844154560d631960c65e15157829b2c7f16859f111a3a8cb72bf24ffa57a680c3be67b1be67c8dd8aea73ac2437a78df5b686d427080ebc01bd30b71a49f6ea31dc0f08e4849e38face96717690239538bc08b6cc5aa8d467cb9c36aa83d40ac7e58bddbfa185b22065e89a86c0145569d9e23726651aec49e31588d70f40fe9a4449dcf4f89eac220171e9c938e803dc195679651004b79ad33cc0c13aeeba5941b33ffeeb8fbe16e76c7811445c67b4269c90479433ddf9e8ed1d00c166b6c17217fb22c3ef1b0c1c7e28e185446a111c37f1ea6c07a59fbcc6546ecc6968d36ba58bc5489a5640647e426b0c39350cb6f07d5dc7a717648c4ec7f841467597ae1f65f408fd2d9940a4b1b860b3c9ae351dcae0b4425f7e8538710f2e40b7f70d13b51ac05ccc6ecda8264a88cad2d721d18132a9b9110a9e759c2483c77dcefc7e464ec88588174cb0c9abff93230ea0bed8decdd8ed8bfe2b5df0a253803678df04fab44c03b9ab7cc97d6e6d6fd0c4c840ce0efc498436f453bbb181603459471f2b588724592b222ec990614db530e10cadd84705621cfdd9261fa44a5f5806a2d74b575056b3c915255c65678f9c16e6dc00a99180fef1a840aff0e842ac02731080cc92782538360a60a727991013984da4fad95f79d5030677b7528d076b2483685fca4429edf804682fdc110dfc2f7c30e23e20a72e039108a0ad6fdee2f76985a4b4be4f5afc6101bf9d5042b657a05dc914e1424241766434"
+const randHex = "c95138082bdf2b9bfa5b1072b23f729735d42c785eeb94320fb14c265b9c2ca421d01a3db986df1ac2acde5a0e6bf955d6f95e61261540905928e195f1a66644cc7f37281744fff4dc6df35566a494c41a8167151950eb74f5fc45f85ad0e5ed28b49adfe218aa7ec1707e8e1d55825f61f72beda3b4c006b8c9188d7336a5d875329b1b58c27cc4e89ecbae02c7712400c39dd131d2c6de82e2863da51d472bdfb21ecce62cc9cf769ed28aedc7583d755da45a0d90874bda269dd53283a9bdfd05f95fc8e9a304bb338ea1a2111894678c18134f17d31a15d9bfc1237894650f3e715e2548639ecbddb845cfe4a46a7b3a3c540f48629488e8c869f1e9f3f4c552243a8105b20eb8e264994214349dae83b165fd6c2a5b8e83fce09fc0a80d3281c8d53a9a08095bd19cbc1388df23975646ed259e003d39261ee68cbece8bcf32971f7fe7e588e8ba8f5e8597909abaea693836a79a1964050ed910a45a0f13a58cd2d3ae18992c5b23082407fd920d0bf01e33118a017bb5e39f44931346845af52128f7965206759433a346034ea481671f501280067567619f5ecef6cded077f92ed7f3b3ce8e308c80f34ba06939e9303f91b4318c8c1dd4cc223c1f057ac0c91211c629cd30e46ee9ec1d9fd493086b7bc2bc83e33f08749a5d430b0ed4f79d70f481940c9b0930b16321886a0df4fa5a1465d5208c7d3494a7987d9a5e42aa256f0c9523947f8318d0ef0af3d59a45cfc2418d0785c9a548b32b81e7de18be7d55a69a4c156bbb3d7579c0ac8e9c72b24646e54b0d0e8725f8f49fb44ae3c6b9d0287be118586255a90a4a83483ed0328518037e52aa959c5748ed83e13023e532306be98b8288da306bbb040bcf5d92176f84a9306dc6b274b040370b61d71fde58dd6d20e6fee348eae0c54bd0a5a487b2d005f329794f2a902c296af0a4c1f638f63292a1fa18e006c1b1838636f4de71c73635b25660d32e88a0917e1a5677f6a02ca65585b82cbd99fb4badbfa97a585da1e6cadf6737b4ec6ca33f245d66ee6a9fae6785d69b003c17b9fc6ec34fe5824ab8caae5e8e14dc6f9e116e7bf4a60c04388783c8ae929e1b46b3ef3bbe81b38f2fa6da771bf39dfba2374d3d2ed356b8e2c42081d885a91a3afb2f31986d2f9873354c48cf5448492c32e62385af423aa4f83db6d1b2669650379a1134b0a04cbca0862d6f9743c791cbb527d36cd5d1f0fc7f503831c8bd1b7a0ef8ae1a5ed1155dfdd9e32b6bb33138112d3d476b802179cb85a2a6c354ccfed2f31604fbd8d6ec4baf9f1c8454f72c6588c06a7df3178c43a6970bfa02dd6f74cb5ec3b63f9eddaa17db5cbf27fac6de8e57c384afd0954179f7b5690c3bee42abc4fa79b4b12101a9cf5f0b9aecdda945def0bd04163237247d3539850e123fe18139f316fa0256d5bd2faa8"
+
+const oneMBSawtoothBZ2Hex = "425a683931415926535971931ea00006ddffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe007de00000000000000024c00130001300000000000000000000000000000000000000000000000000000000126000980009800000000000000000000000000000000000000000000000000000000930004c0004c000000000000000000000000000000000000000000000000000000004980026000260000000000000000000000000000000000000000000000000000000009aaaaa0000000000000000000000000000000000000000000000000000000000000000498002600026000000000000000000000000000000000000000000000000000000007fc42271980d044c0a822607411304a08982d044c1a82260f411308a08984d044c2a82261741130ca08986d044c3a82261f411310a08988d044c4a822627411314a0898ad044c5a82262f411318a0898cd044c6a82263741131ca0898ed044c7a82263f411320a08990d044c8a822647411324a08992d044c9a82264f411328a08994d044caa82265741132ca08996d044cba82265f411330a08998d044cca822667411334a0899ad044cda82266f411338a0899cd044cea82267741133ca0899ed044cfa82267f411340a089a0d044d0a822687411344a089a2d044d1a82268f411348a089a4d044d2a82269741134ca089a6d044d3a82269f411350a089a8d044d4a8226a7411354a089aad044d5a8226af411358a089acd044d6a8226b741135ca089aed044d7a8226bf411360a089b0d044d8a8226c7411364a089b2d044d9a8226cf411368a089b4d044daa8226d741136ca089b6d044dba8226df411370a089b8d044dca8226e7411374a089bad044dda8226ef411378a089bcd044dea8226f741137ca089bed044dfa8226ff411380a089c0d044e0a822707411384a089c2d044e1a82270f411388a089c4d044e2a82271741138ca089c59089c69089c71089c79089c81089c89089c91089c99089ca1089ca9089cb1089cb9089cc1089cc9089cd1089cd9089ce1089ce9089cf1089cf9089d01089d09089d11089d19089d21089d29089d31089d39089d41089d49089d51089d59089d61089d69089d71089d79089d81089d89089d91089d99089da1089da9089db1089db9089dc1089dc9089dd1089dd9089de1089de9089df1089df9089e01089e09089e11089e19089e21089e29089e31089e39089e41089e49089e51089e59089e61089e69089e71089e79089e81089e89089e91089e99089ea1089ea9089eb1089eb9089ec1089ec9089ed1089ed9089ee1089ee9089ef1089ef9089f01089f09089f11089f19089f21089f29089f31089f39089f41089f49089f51089f59089f61089f69089f71089f79089f81089f89089f91089f99089fa1089fa9089fb1089fb9089fc1089fc9089fd1089fd9089fe1089fe9089ff1089ff98a0ac9329acf23ba884804fdd3ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff0034f800000000000024c00130001300000000000000000000000000000000000000000000000000000000126000980009800000000000000000000000000000000000000000000000000000000930004c0004c000000000000000000000000000000000000000000000000000000004980026000260000000000000000000000000000000000000000000000000000000024c0013000130000000000000000000000000000000000000000000000000000000002955540000000000000000000000000000000000000000000000000000000000000001ff108c00846024230221181908c108460a4230621183908c20846124230a21185908c308461a4230e21187908c40846224231221189908c508462a423162118b908c60846324231a2118d908c708463a4231e2118f908c80846424232221191908c908464a4232621193908ca0846524232a21195908cb08465a4232e21197908cc0846624233221199908cd08466a423362119b908ce0846724233a2119d908cf08467a4233e2119f908d008468242342211a1908d108468a42346211a3908d20846924234a211a5908d308469a4234e211a7908d40846a242352211a9908d50846aa42356211ab908d60846b24235a211ad908d70846ba4235e211af908d80846c242362211b1908d90846ca42366211b3908da0846d24236a211b5908db0846da4236e211b7908dc0846e242372211b9908dd0846ea42376211bb908de0846f24237a211bd908df0846fa4237e211bf908e008470242382211c1908e108470a42386211c3908e20847124238a211c5908e2f8c211c6c8471d211c7c84721211c8c84725211c9c84729211cac8472d211cbc84731211ccc84735211cdc84739211cec8473d211cfc84741211d0c84745211d1c84749211d2c8474d211d3c84751211d4c84755211d5c84759211d6c8475d211d7c84761211d8c84765211d9c84769211dac8476d211dbc84771211dcc84775211ddc84779211dec8477d211dfc84781211e0c84785211e1c84789211e2c8478d211e3c84791211e4c84795211e5c84799211e6c8479d211e7c847a1211e8c847a5211e9c847a9211eac847ad211ebc847b1211ecc847b5211edc847b9211eec847bd211efc847c1211f0c847c5211f1c847c9211f2c847cd211f3c847d1211f4c847d5211f5c847d9211f6c847dd211f7c847e1211f8c847e5211f9c847e9211fac847ed211fbc847f1211fcc847f5211fdc847f9211fec847fd211ff8bb9229c284803a8b6248"
+
+const rand2BZ2Hex = "425a6839314159265359d992d0f60000137dfe84020310091c1e280e100e042801099210094806c0110002e70806402000546034000034000000f2830000032000d3403264049270eb7a9280d308ca06ad28f6981bee1bf8160727c7364510d73a1e123083421b63f031f63993a0f40051fbf177245385090d992d0f60"
+const rand2Hex = "92d5652616ac444a4a04af1a8a3964aca0450d43d6cf233bd03233f4ba92f8719e6c2a2bd4f5f88db07ecd0da3a33b263483db9b2c158786ad6363be35d17335ba"
+
+const rand3BZ2Hex = "425a68393141592653593be669d00000327ffffffffffffffffffffffffffffffffffff7ffffffffffffffffffffffffffffffc002b3b2b1b6e2bae400004c00132300004c0d268c004c08c0130026001a008683234c0684c34008c230261a04c0260064d07a8d00034000d27a1268c9931a8d327a3427a41faa69ea0da264c1a34219326869b51b49a6469a3268c689fa53269a62794687a9a68f5189994c9e487a8f534fd49a3d34043629e8c93d04da4f4648d30d4f44d3234c4d3023d0840680984d309934c234d3131a000640984f536a6132601300130130c8d00d04d1841ea7a8d31a02609b40023460010c01a34d4c1a0d04d3069306810034d0d0d4c0046130d034d0131a9a64d321804c68003400098344c13000991808c0001a00000000098004d3d4da4604c47a13012140aadf8d673c922c607ef6212a8c0403adea4b28aee578900e653b9cdeb8d11e6b838815f3ebaad5a01c5408d84a332170aff8734d4e06612d3c2889f31925fb89e33561f5100ae89b1f7047102e729373d3667e58d73aaa80fa7be368a1cc2dadd81d81ec8e1b504bd772ca31d03649269b01ceddaca07bf3d4eba24de141be3f86f93601e03714c0f64654671684f9f9528626fd4e1b76753dc0c54b842486b8d59d8ab314e86ca818e7a1f079463cbbd70d9b79b283c7edc419406311022e4be98c2c1374df9cdde2d008ce1d00e5f06ad1024baf555631f70831fc1023034e62be7c4bcb648caf276963ffa20e96bb50377fe1c113da0db4625b50741c35a058edb009c6ee5dbf93b8a6b060eec568180e8db791b82aab96cbf4326ca98361461379425ba8dcc347be670bdba7641883e5526ae3d833f6e9cb9bac9557747c79e206151072f7f0071dff3880411846f66bf4075c7462f302b53cb3400a74cf35652ad5641ed33572fd54e7ed7f85f58a0acba89327e7c6be5c58cb71528b99df2431f1d0358f8d28d81d95292da631fb06701decabb205fac59ff0fb1df536afc681eece6ea658c4d9eaa45f1342aa1ff70bdaff2ddaf25ec88c22f12829a0553db1ec2505554cb17d7b282e213a5a2aa30431ded2bce665bb199d023840832fedb2c0c350a27291407ff77440792872137df281592e82076a05c64c345ffb058c64f7f7c207ef78420b7010520610f17e302cc4dfcfaef72a0ed091aab4b541eb0531bbe941ca2f792bf7b31ca6162882b68054a8470115bc2c19f2df2023f7800432b39b04d3a304e8085ba3f1f0ca5b1ba4d38d339e6084de979cdea6d0e244c6c9fa0366bd890621e3d30846f5e8497e21597b8f29bbf52c961a485dfbea647600da0fc1f25ce4d203a8352ece310c39073525044e7ac46acf2ed9120bae1b4f6f02364abfe343f80b290983160c103557af1c68416480d024cc31b6c06cfec011456f1e95c420a12b48b1c3fe220c2879a982fb099948ac440db844b9a112a5188c7783fd3b19593290785f908d95c9db4b280bafe89c1313aeec24772046d9bc089645f0d182a21184e143823c5f52de50e5d7e98d3d7ab56f5413bbccd1415c9bcff707def475b643fb7f29842582104d4cc1dbaaca8f10a2f44273c339e0984f2b1e06ab2f0771db01fafa8142298345f3196f23e5847bda024034b6f59b11c29e981c881456e40d211929fd4f766200258aad8212016322bd5c605790dcfdf1bd2a93d99c9b8f498722d311d7eae7ff420496a31804c55f4759a7b13aaaf5f7ce006c3a8a998897d5e0a504398c2b627852545baf440798bcc5cc049357cf3f17d9771e4528a1af3d77dc794a11346e1bdf5efe37a405b127b4c43b616d61fbc5dc914e14240ef99a7400"
+const rand3Hex = "1744b384d68c042371244e13500d4bfb98c6244e3d71a5b700224420b59c593553f33bd786e3d0ce31626f511bc985f59d1a88aa38ba8ad6218d306abee60dd9172540232b95be1af146c69e72e5fde667a090dc3f93bdc5c5af0ab80acdbaa7a505f628c59dc0247b31a439cacf5010a94376d71521df08c178b02fb96fdb1809144ea38c68536187c53201fea8631fb0a880b4451ccdca7cc61f6aafca21cc7449d920599db61789ac3b1e164b3390124f95022aeea39ccca3ec1053f4fa10de2978e2861ea58e477085c2220021a0927aa94c5d0006b5055abba340e4f9eba22e969978dfd18e278a8b89d877328ae34268bc0174cfe211954c0036f078025217d1269fac1932a03b05a0b616012271bbe1fb554171c7a59b196d8a4479f45a77931b5d97aaf6c0c673cbe597b79b96e2a0c1eae2e66e46ccc8c85798e23ffe972ebdaa3f6caea243c004e60321eb47cd79137d78fd0613be606feacc5b3637bdc96a89c13746db8cad886f3ccf912b2178c823bcac395f06d28080269bdca2debf3419c66c690fd1adcfbd53e32e79443d7a42511a84cb22ca94fffad9149275a075b2f8ae0b021dcde9bf62b102db920733b897560518b06e1ad7f4b03458493ddaa7f4fa2c1609f7a1735aeeb1b3e2cea3ab45fc376323cc91873b7e9c90d07c192e38d3f5dfc9bfab1fd821c854da9e607ea596c391c7ec4161c6c4493929a8176badaa5a5af7211c623f29643a937677d3df0da9266181b7c4da5dd40376db677fe8f4a1dc456adf6f33c1e37cec471dd318c2647644fe52f93707a77da7d1702380a80e14cc0fdce7bf2eed48a529090bae0388ee277ce6c7018c5fb00b88362554362205c641f0d0fab94fd5b8357b5ff08b207fee023709bc126ec90cfb17c006754638f8186aaeb1265e80be0c1189ec07d01d5f6f96cb9ce82744147d18490de7dc72862f42f024a16968891a356f5e7e0e695d8c933ba5b5e43ad4c4ade5399bc2cae9bb6189b7870d7f22956194d277f28b10e01c10c6ffe3e065f7e2d6d056aa790db5649ca84dc64c35566c0af1b68c32b5b7874aaa66467afa44f40e9a0846a07ae75360a641dd2acc69d93219b2891f190621511e62a27f5e4fbe641ece1fa234fc7e9a74f48d2a760d82160d9540f649256b169d1fed6fbefdc491126530f3cbad7913e19fbd7aa53b1e243fbf28d5f38c10ebd77c8b986775975cc1d619efb27cdcd733fa1ca36cffe9c0a33cc9f02463c91a886601fd349efee85ef1462065ef9bd2c8f533220ad93138b8382d5938103ab25b2d9af8ae106e1211eb9b18793fba033900c809c02cd6d17e2f3e6fc84dae873411f8e87c3f0a8f1765b7825d185ce3730f299c3028d4a62da9ee95c2b870fb70c79370d485f9d5d9acb78926d20444033d960524d2776dc31988ec7c0dbf23b9905d"
diff --git a/libgo/go/compress/bzip2/huffman.go b/libgo/go/compress/bzip2/huffman.go
new file mode 100644 (file)
index 0000000..732bc4a
--- /dev/null
@@ -0,0 +1,223 @@
+// Copyright 2011 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 bzip2
+
+import (
+       "os"
+       "sort"
+)
+
+// A huffmanTree is a binary tree which is navigated, bit-by-bit to reach a
+// symbol.
+type huffmanTree struct {
+       // nodes contains all the non-leaf nodes in the tree. nodes[0] is the
+       // root of the tree and nextNode contains the index of the next element
+       // of nodes to use when the tree is being constructed.
+       nodes    []huffmanNode
+       nextNode int
+}
+
+// A huffmanNode is a node in the tree. left and right contain indexes into the
+// nodes slice of the tree. If left or right is invalidNodeValue then the child
+// is a left node and its value is in leftValue/rightValue.
+//
+// The symbols are uint16s because bzip2 encodes not only MTF indexes in the
+// tree, but also two magic values for run-length encoding and an EOF symbol.
+// Thus there are more than 256 possible symbols.
+type huffmanNode struct {
+       left, right           uint16
+       leftValue, rightValue uint16
+}
+
+// invalidNodeValue is an invalid index which marks a leaf node in the tree.
+const invalidNodeValue = 0xffff
+
+// Decode reads bits from the given bitReader and navigates the tree until a
+// symbol is found.
+func (t huffmanTree) Decode(br *bitReader) (v uint16) {
+       nodeIndex := uint16(0) // node 0 is the root of the tree.
+
+       for {
+               node := &t.nodes[nodeIndex]
+               bit := br.ReadBit()
+               // bzip2 encodes left as a true bit.
+               if bit {
+                       // left
+                       if node.left == invalidNodeValue {
+                               return node.leftValue
+                       }
+                       nodeIndex = node.left
+               } else {
+                       // right
+                       if node.right == invalidNodeValue {
+                               return node.rightValue
+                       }
+                       nodeIndex = node.right
+               }
+       }
+
+       panic("unreachable")
+}
+
+// newHuffmanTree builds a Huffman tree from a slice containing the code
+// lengths of each symbol. The maximum code length is 32 bits.
+func newHuffmanTree(lengths []uint8) (huffmanTree, os.Error) {
+       // There are many possible trees that assign the same code length to
+       // each symbol (consider reflecting a tree down the middle, for
+       // example). Since the code length assignments determine the
+       // efficiency of the tree, each of these trees is equally good. In
+       // order to minimise the amount of information needed to build a tree
+       // bzip2 uses a canonical tree so that it can be reconstructed given
+       // only the code length assignments.
+
+       if len(lengths) < 2 {
+               panic("newHuffmanTree: too few symbols")
+       }
+
+       var t huffmanTree
+
+       // First we sort the code length assignments by ascending code length,
+       // using the symbol value to break ties.
+       pairs := huffmanSymbolLengthPairs(make([]huffmanSymbolLengthPair, len(lengths)))
+       for i, length := range lengths {
+               pairs[i].value = uint16(i)
+               pairs[i].length = length
+       }
+
+       sort.Sort(pairs)
+
+       // Now we assign codes to the symbols, starting with the longest code.
+       // We keep the codes packed into a uint32, at the most-significant end.
+       // So branches are taken from the MSB downwards. This makes it easy to
+       // sort them later.
+       code := uint32(0)
+       length := uint8(32)
+
+       codes := huffmanCodes(make([]huffmanCode, len(lengths)))
+       for i := len(pairs) - 1; i >= 0; i-- {
+               if length > pairs[i].length {
+                       // If the code length decreases we shift in order to
+                       // zero any bits beyond the end of the code.
+                       length >>= 32 - pairs[i].length
+                       length <<= 32 - pairs[i].length
+                       length = pairs[i].length
+               }
+               codes[i].code = code
+               codes[i].codeLen = length
+               codes[i].value = pairs[i].value
+               // We need to 'increment' the code, which means treating |code|
+               // like a |length| bit number.
+               code += 1 << (32 - length)
+       }
+
+       // Now we can sort by the code so that the left half of each branch are
+       // grouped together, recursively.
+       sort.Sort(codes)
+
+       t.nodes = make([]huffmanNode, len(codes))
+       _, err := buildHuffmanNode(&t, codes, 0)
+       return t, err
+}
+
+// huffmanSymbolLengthPair contains a symbol and its code length.
+type huffmanSymbolLengthPair struct {
+       value  uint16
+       length uint8
+}
+
+// huffmanSymbolLengthPair is used to provide an interface for sorting.
+type huffmanSymbolLengthPairs []huffmanSymbolLengthPair
+
+func (h huffmanSymbolLengthPairs) Len() int {
+       return len(h)
+}
+
+func (h huffmanSymbolLengthPairs) Less(i, j int) bool {
+       if h[i].length < h[j].length {
+               return true
+       }
+       if h[i].length > h[j].length {
+               return false
+       }
+       if h[i].value < h[j].value {
+               return true
+       }
+       return false
+}
+
+func (h huffmanSymbolLengthPairs) Swap(i, j int) {
+       h[i], h[j] = h[j], h[i]
+}
+
+// huffmanCode contains a symbol, its code and code length.
+type huffmanCode struct {
+       code    uint32
+       codeLen uint8
+       value   uint16
+}
+
+// huffmanCodes is used to provide an interface for sorting.
+type huffmanCodes []huffmanCode
+
+func (n huffmanCodes) Len() int {
+       return len(n)
+}
+
+func (n huffmanCodes) Less(i, j int) bool {
+       return n[i].code < n[j].code
+}
+
+func (n huffmanCodes) Swap(i, j int) {
+       n[i], n[j] = n[j], n[i]
+}
+
+// buildHuffmanNode takes a slice of sorted huffmanCodes and builds a node in
+// the Huffman tree at the given level. It returns the index of the newly
+// constructed node.
+func buildHuffmanNode(t *huffmanTree, codes []huffmanCode, level uint32) (nodeIndex uint16, err os.Error) {
+       test := uint32(1) << (31 - level)
+
+       // We have to search the list of codes to find the divide between the left and right sides.
+       firstRightIndex := len(codes)
+       for i, code := range codes {
+               if code.code&test != 0 {
+                       firstRightIndex = i
+                       break
+               }
+       }
+
+       left := codes[:firstRightIndex]
+       right := codes[firstRightIndex:]
+
+       if len(left) == 0 || len(right) == 0 {
+               return 0, StructuralError("superfluous level in Huffman tree")
+       }
+
+       nodeIndex = uint16(t.nextNode)
+       node := &t.nodes[t.nextNode]
+       t.nextNode++
+
+       if len(left) == 1 {
+               // leaf node
+               node.left = invalidNodeValue
+               node.leftValue = left[0].value
+       } else {
+               node.left, err = buildHuffmanNode(t, left, level+1)
+       }
+
+       if err != nil {
+               return
+       }
+
+       if len(right) == 1 {
+               // leaf node
+               node.right = invalidNodeValue
+               node.rightValue = right[0].value
+       } else {
+               node.right, err = buildHuffmanNode(t, right, level+1)
+       }
+
+       return
+}
diff --git a/libgo/go/compress/bzip2/move_to_front.go b/libgo/go/compress/bzip2/move_to_front.go
new file mode 100644 (file)
index 0000000..0ed19de
--- /dev/null
@@ -0,0 +1,105 @@
+// Copyright 2011 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 bzip2
+
+// moveToFrontDecoder implements a move-to-front list. Such a list is an
+// efficient way to transform a string with repeating elements into one with
+// many small valued numbers, which is suitable for entropy encoding. It works
+// by starting with an initial list of symbols and references symbols by their
+// index into that list. When a symbol is referenced, it's moved to the front
+// of the list. Thus, a repeated symbol ends up being encoded with many zeros,
+// as the symbol will be at the front of the list after the first access.
+type moveToFrontDecoder struct {
+       // Rather than actually keep the list in memory, the symbols are stored
+       // as a circular, double linked list with the symbol indexed by head
+       // at the front of the list.
+       symbols []byte
+       next    []uint8
+       prev    []uint8
+       head    uint8
+}
+
+// newMTFDecoder creates a move-to-front decoder with an explicit initial list
+// of symbols.
+func newMTFDecoder(symbols []byte) *moveToFrontDecoder {
+       if len(symbols) > 256 {
+               panic("too many symbols")
+       }
+
+       m := &moveToFrontDecoder{
+               symbols: symbols,
+               next:    make([]uint8, len(symbols)),
+               prev:    make([]uint8, len(symbols)),
+       }
+
+       m.threadLinkedList()
+       return m
+}
+
+// newMTFDecoderWithRange creates a move-to-front decoder with an initial
+// symbol list of 0...n-1.
+func newMTFDecoderWithRange(n int) *moveToFrontDecoder {
+       if n > 256 {
+               panic("newMTFDecoderWithRange: cannot have > 256 symbols")
+       }
+
+       m := &moveToFrontDecoder{
+               symbols: make([]uint8, n),
+               next:    make([]uint8, n),
+               prev:    make([]uint8, n),
+       }
+
+       for i := 0; i < n; i++ {
+               m.symbols[i] = byte(i)
+       }
+
+       m.threadLinkedList()
+       return m
+}
+
+// threadLinkedList creates the initial linked-list pointers.
+func (m *moveToFrontDecoder) threadLinkedList() {
+       if len(m.symbols) == 0 {
+               return
+       }
+
+       m.prev[0] = uint8(len(m.symbols) - 1)
+
+       for i := 0; i < len(m.symbols)-1; i++ {
+               m.next[i] = uint8(i + 1)
+               m.prev[i+1] = uint8(i)
+       }
+
+       m.next[len(m.symbols)-1] = 0
+}
+
+func (m *moveToFrontDecoder) Decode(n int) (b byte) {
+       // Most of the time, n will be zero so it's worth dealing with this
+       // simple case.
+       if n == 0 {
+               return m.symbols[m.head]
+       }
+
+       i := m.head
+       for j := 0; j < n; j++ {
+               i = m.next[i]
+       }
+       b = m.symbols[i]
+
+       m.next[m.prev[i]] = m.next[i]
+       m.prev[m.next[i]] = m.prev[i]
+       m.next[i] = m.head
+       m.prev[i] = m.prev[m.head]
+       m.next[m.prev[m.head]] = i
+       m.prev[m.head] = i
+       m.head = i
+
+       return
+}
+
+// First returns the symbol at the front of the list.
+func (m *moveToFrontDecoder) First() byte {
+       return m.symbols[m.head]
+}
index 3db9556..ff54164 100644 (file)
@@ -116,9 +116,16 @@ func (b *syncBuffer) Read(p []byte) (n int, err os.Error) {
        panic("unreachable")
 }
 
+func (b *syncBuffer) signal() {
+       select {
+       case b.ready <- true:
+       default:
+       }
+}
+
 func (b *syncBuffer) Write(p []byte) (n int, err os.Error) {
        n, err = b.buf.Write(p)
-       _ = b.ready <- true
+       b.signal()
        return
 }
 
@@ -128,12 +135,12 @@ func (b *syncBuffer) WriteMode() {
 
 func (b *syncBuffer) ReadMode() {
        b.mu.Unlock()
-       _ = b.ready <- true
+       b.signal()
 }
 
 func (b *syncBuffer) Close() os.Error {
        b.closed = true
-       _ = b.ready <- true
+       b.signal()
        return nil
 }
 
@@ -255,135 +262,9 @@ func TestReverseBits(t *testing.T) {
 }
 
 func TestDeflateInflateString(t *testing.T) {
-       gold := bytes.NewBufferString(getEdata()).Bytes()
+       gold, err := ioutil.ReadFile("../testdata/e.txt")
+       if err != nil {
+               t.Error(err)
+       }
        testToFromWithLevel(t, 1, gold, "2.718281828...")
 }
-
-func getEdata() string {
-       return "2.718281828459045235360287471352662497757247093699959574966967627724076630353547" +
-               "59457138217852516642742746639193200305992181741359662904357290033429526059563073" +
-               "81323286279434907632338298807531952510190115738341879307021540891499348841675092" +
-               "44761460668082264800168477411853742345442437107539077744992069551702761838606261" +
-               "33138458300075204493382656029760673711320070932870912744374704723069697720931014" +
-               "16928368190255151086574637721112523897844250569536967707854499699679468644549059" +
-               "87931636889230098793127736178215424999229576351482208269895193668033182528869398" +
-               "49646510582093923982948879332036250944311730123819706841614039701983767932068328" +
-               "23764648042953118023287825098194558153017567173613320698112509961818815930416903" +
-               "51598888519345807273866738589422879228499892086805825749279610484198444363463244" +
-               "96848756023362482704197862320900216099023530436994184914631409343173814364054625" +
-               "31520961836908887070167683964243781405927145635490613031072085103837505101157477" +
-               "04171898610687396965521267154688957035035402123407849819334321068170121005627880" +
-               "23519303322474501585390473041995777709350366041699732972508868769664035557071622" +
-               "68447162560798826517871341951246652010305921236677194325278675398558944896970964" +
-               "09754591856956380236370162112047742722836489613422516445078182442352948636372141" +
-               "74023889344124796357437026375529444833799801612549227850925778256209262264832627" +
-               "79333865664816277251640191059004916449982893150566047258027786318641551956532442" +
-               "58698294695930801915298721172556347546396447910145904090586298496791287406870504" +
-               "89585867174798546677575732056812884592054133405392200011378630094556068816674001" +
-               "69842055804033637953764520304024322566135278369511778838638744396625322498506549" +
-               "95886234281899707733276171783928034946501434558897071942586398772754710962953741" +
-               "52111513683506275260232648472870392076431005958411661205452970302364725492966693" +
-               "81151373227536450988890313602057248176585118063036442812314965507047510254465011" +
-               "72721155519486685080036853228183152196003735625279449515828418829478761085263981" +
-               "39559900673764829224437528718462457803619298197139914756448826260390338144182326" +
-               "25150974827987779964373089970388867782271383605772978824125611907176639465070633" +
-               "04527954661855096666185664709711344474016070462621568071748187784437143698821855" +
-               "96709591025968620023537185887485696522000503117343920732113908032936344797273559" +
-               "55277349071783793421637012050054513263835440001863239914907054797780566978533580" +
-               "48966906295119432473099587655236812859041383241160722602998330535370876138939639" +
-               "17795745401613722361878936526053815584158718692553860616477983402543512843961294" +
-               "60352913325942794904337299085731580290958631382683291477116396337092400316894586" +
-               "36060645845925126994655724839186564209752685082307544254599376917041977780085362" +
-               "73094171016343490769642372229435236612557250881477922315197477806056967253801718" +
-               "07763603462459278778465850656050780844211529697521890874019660906651803516501792" +
-               "50461950136658543663271254963990854914420001457476081930221206602433009641270489" +
-               "43903971771951806990869986066365832322787093765022601492910115171776359446020232" +
-               "49300280401867723910288097866605651183260043688508817157238669842242201024950551" +
-               "88169480322100251542649463981287367765892768816359831247788652014117411091360116" +
-               "49950766290779436460058519419985601626479076153210387275571269925182756879893027" +
-               "61761146162549356495903798045838182323368612016243736569846703785853305275833337" +
-               "93990752166069238053369887956513728559388349989470741618155012539706464817194670" +
-               "83481972144888987906765037959036696724949925452790337296361626589760394985767413" +
-               "97359441023744329709355477982629614591442936451428617158587339746791897571211956" +
-               "18738578364475844842355558105002561149239151889309946342841393608038309166281881" +
-               "15037152849670597416256282360921680751501777253874025642534708790891372917228286" +
-               "11515915683725241630772254406337875931059826760944203261924285317018781772960235" +
-               "41306067213604600038966109364709514141718577701418060644363681546444005331608778" +
-               "31431744408119494229755993140118886833148328027065538330046932901157441475631399" +
-               "97221703804617092894579096271662260740718749975359212756084414737823303270330168" +
-               "23719364800217328573493594756433412994302485023573221459784328264142168487872167" +
-               "33670106150942434569844018733128101079451272237378861260581656680537143961278887" +
-               "32527373890392890506865324138062796025930387727697783792868409325365880733988457" +
-               "21874602100531148335132385004782716937621800490479559795929059165547050577751430" +
-               "81751126989851884087185640260353055837378324229241856256442550226721559802740126" +
-               "17971928047139600689163828665277009752767069777036439260224372841840883251848770" +
-               "47263844037953016690546593746161932384036389313136432713768884102681121989127522" +
-               "30562567562547017250863497653672886059667527408686274079128565769963137897530346" +
-               "60616669804218267724560530660773899624218340859882071864682623215080288286359746" +
-               "83965435885668550377313129658797581050121491620765676995065971534476347032085321" +
-               "56036748286083786568030730626576334697742956346437167093971930608769634953288468" +
-               "33613038829431040800296873869117066666146800015121143442256023874474325250769387" +
-               "07777519329994213727721125884360871583483562696166198057252661220679754062106208" +
-               "06498829184543953015299820925030054982570433905535701686531205264956148572492573" +
-               "86206917403695213533732531666345466588597286659451136441370331393672118569553952" +
-               "10845840724432383558606310680696492485123263269951460359603729725319836842336390" +
-               "46321367101161928217111502828016044880588023820319814930963695967358327420249882" +
-               "45684941273860566491352526706046234450549227581151709314921879592718001940968866" +
-               "98683703730220047531433818109270803001720593553052070070607223399946399057131158" +
-               "70996357773590271962850611465148375262095653467132900259943976631145459026858989" +
-               "79115837093419370441155121920117164880566945938131183843765620627846310490346293" +
-               "95002945834116482411496975832601180073169943739350696629571241027323913874175492" +
-               "30718624545432220395527352952402459038057445028922468862853365422138157221311632" +
-               "88112052146489805180092024719391710555390113943316681515828843687606961102505171" +
-               "00739276238555338627255353883096067164466237092264680967125406186950214317621166" +
-               "81400975952814939072226011126811531083873176173232352636058381731510345957365382" +
-               "23534992935822836851007810884634349983518404451704270189381994243410090575376257" +
-               "76757111809008816418331920196262341628816652137471732547772778348877436651882875" +
-               "21566857195063719365653903894493664217640031215278702223664636357555035655769488" +
-               "86549500270853923617105502131147413744106134445544192101336172996285694899193369" +
-               "18472947858072915608851039678195942983318648075608367955149663644896559294818785" +
-               "17840387733262470519450504198477420141839477312028158868457072905440575106012852" +
-               "58056594703046836344592652552137008068752009593453607316226118728173928074623094" +
-               "68536782310609792159936001994623799343421068781349734695924646975250624695861690" +
-               "91785739765951993929939955675427146549104568607020990126068187049841780791739240" +
-               "71945996323060254707901774527513186809982284730860766536866855516467702911336827" +
-               "56310722334672611370549079536583453863719623585631261838715677411873852772292259" +
-               "47433737856955384562468010139057278710165129666367644518724656537304024436841408" +
-               "14488732957847348490003019477888020460324660842875351848364959195082888323206522" +
-               "12810419044804724794929134228495197002260131043006241071797150279343326340799596" +
-               "05314460532304885289729176598760166678119379323724538572096075822771784833616135" +
-               "82612896226118129455927462767137794487586753657544861407611931125958512655759734" +
-               "57301533364263076798544338576171533346232527057200530398828949903425956623297578" +
-               "24887350292591668258944568946559926584547626945287805165017206747854178879822768" +
-               "06536650641910973434528878338621726156269582654478205672987756426325321594294418" +
-               "03994321700009054265076309558846589517170914760743713689331946909098190450129030" +
-               "70995662266203031826493657336984195557769637876249188528656866076005660256054457" +
-               "11337286840205574416030837052312242587223438854123179481388550075689381124935386" +
-               "31863528708379984569261998179452336408742959118074745341955142035172618420084550" +
-               "91708456823682008977394558426792142734775608796442792027083121501564063413416171" +
-               "66448069815483764491573900121217041547872591998943825364950514771379399147205219" +
-               "52907939613762110723849429061635760459623125350606853765142311534966568371511660" +
-               "42207963944666211632551577290709784731562782775987881364919512574833287937715714" +
-               "59091064841642678309949723674420175862269402159407924480541255360431317992696739" +
-               "15754241929660731239376354213923061787675395871143610408940996608947141834069836" +
-               "29936753626215452472984642137528910798843813060955526227208375186298370667872244" +
-               "30195793793786072107254277289071732854874374355781966511716618330881129120245204" +
-               "04868220007234403502544820283425418788465360259150644527165770004452109773558589" +
-               "76226554849416217149895323834216001140629507184904277892585527430352213968356790" +
-               "18076406042138307308774460170842688272261177180842664333651780002171903449234264" +
-               "26629226145600433738386833555534345300426481847398921562708609565062934040526494" +
-               "32442614456659212912256488935696550091543064261342526684725949143142393988454324" +
-               "86327461842846655985332312210466259890141712103446084271616619001257195870793217" +
-               "56969854401339762209674945418540711844643394699016269835160784892451405894094639" +
-               "52678073545797003070511636825194877011897640028276484141605872061841852971891540" +
-               "19688253289309149665345753571427318482016384644832499037886069008072709327673127" +
-               "58196656394114896171683298045513972950668760474091542042842999354102582911350224" +
-               "16907694316685742425225090269390348148564513030699251995904363840284292674125734" +
-               "22447765584177886171737265462085498294498946787350929581652632072258992368768457" +
-               "01782303809656788311228930580914057261086588484587310165815116753332767488701482" +
-               "91674197015125597825727074064318086014281490241467804723275976842696339357735429" +
-               "30186739439716388611764209004068663398856841681003872389214483176070116684503887" +
-               "21236436704331409115573328018297798873659091665961240202177855885487617616198937" +
-               "07943800566633648843650891448055710397652146960276625835990519870423001794655367" +
-               "9"
-}
diff --git a/libgo/go/compress/lzw/reader.go b/libgo/go/compress/lzw/reader.go
new file mode 100644 (file)
index 0000000..8a540cb
--- /dev/null
@@ -0,0 +1,210 @@
+// Copyright 2011 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.
+
+// The lzw package implements the Lempel-Ziv-Welch compressed data format,
+// described in T. A. Welch, ``A Technique for High-Performance Data
+// Compression'', Computer, 17(6) (June 1984), pp 8-19.
+//
+// In particular, it implements LZW as used by the GIF, TIFF and PDF file
+// formats, which means variable-width codes up to 12 bits and the first
+// two non-literal codes are a clear code and an EOF code.
+package lzw
+
+// TODO(nigeltao): check that TIFF and PDF use LZW in the same way as GIF,
+// modulo LSB/MSB packing order.
+
+import (
+       "bufio"
+       "fmt"
+       "io"
+       "os"
+)
+
+// Order specifies the bit ordering in an LZW data stream.
+type Order int
+
+const (
+       // LSB means Least Significant Bits first, as used in the GIF file format.
+       LSB Order = iota
+       // MSB means Most Significant Bits first, as used in the TIFF and PDF
+       // file formats.
+       MSB
+)
+
+// decoder is the state from which the readXxx method converts a byte
+// stream into a code stream.
+type decoder struct {
+       r     io.ByteReader
+       bits  uint32
+       nBits uint
+       width uint
+}
+
+// readLSB returns the next code for "Least Significant Bits first" data.
+func (d *decoder) readLSB() (uint16, os.Error) {
+       for d.nBits < d.width {
+               x, err := d.r.ReadByte()
+               if err != nil {
+                       return 0, err
+               }
+               d.bits |= uint32(x) << d.nBits
+               d.nBits += 8
+       }
+       code := uint16(d.bits & (1<<d.width - 1))
+       d.bits >>= d.width
+       d.nBits -= d.width
+       return code, nil
+}
+
+// readMSB returns the next code for "Most Significant Bits first" data.
+func (d *decoder) readMSB() (uint16, os.Error) {
+       for d.nBits < d.width {
+               x, err := d.r.ReadByte()
+               if err != nil {
+                       return 0, err
+               }
+               d.bits |= uint32(x) << (24 - d.nBits)
+               d.nBits += 8
+       }
+       code := uint16(d.bits >> (32 - d.width))
+       d.bits <<= d.width
+       d.nBits -= d.width
+       return code, nil
+}
+
+// decode decompresses bytes from r and writes them to pw.
+// read specifies how to decode bytes into codes.
+// litWidth is the width in bits of literal codes.
+func decode(r io.Reader, read func(*decoder) (uint16, os.Error), litWidth int, pw *io.PipeWriter) {
+       br, ok := r.(io.ByteReader)
+       if !ok {
+               br = bufio.NewReader(r)
+       }
+       pw.CloseWithError(decode1(pw, br, read, uint(litWidth)))
+}
+
+func decode1(pw *io.PipeWriter, r io.ByteReader, read func(*decoder) (uint16, os.Error), litWidth uint) os.Error {
+       const (
+               maxWidth    = 12
+               invalidCode = 0xffff
+       )
+       d := decoder{r, 0, 0, 1 + litWidth}
+       w := bufio.NewWriter(pw)
+       // The first 1<<litWidth codes are literal codes.
+       // The next two codes mean clear and EOF.
+       // Other valid codes are in the range [lo, hi] where lo := clear + 2,
+       // with the upper bound incrementing on each code seen.
+       clear := uint16(1) << litWidth
+       eof, hi := clear+1, clear+1
+       // overflow is the code at which hi overflows the code width.
+       overflow := uint16(1) << d.width
+       var (
+               // Each code c in [lo, hi] expands to two or more bytes. For c != hi:
+               //   suffix[c] is the last of these bytes.
+               //   prefix[c] is the code for all but the last byte.
+               //   This code can either be a literal code or another code in [lo, c).
+               // The c == hi case is a special case.
+               suffix [1 << maxWidth]uint8
+               prefix [1 << maxWidth]uint16
+               // buf is a scratch buffer for reconstituting the bytes that a code expands to.
+               // Code suffixes are written right-to-left from the end of the buffer.
+               buf [1 << maxWidth]byte
+       )
+
+       // Loop over the code stream, converting codes into decompressed bytes.
+       last := uint16(invalidCode)
+       for {
+               code, err := read(&d)
+               if err != nil {
+                       if err == os.EOF {
+                               err = io.ErrUnexpectedEOF
+                       }
+                       return err
+               }
+               switch {
+               case code < clear:
+                       // We have a literal code.
+                       if err := w.WriteByte(uint8(code)); err != nil {
+                               return err
+                       }
+                       if last != invalidCode {
+                               // Save what the hi code expands to.
+                               suffix[hi] = uint8(code)
+                               prefix[hi] = last
+                       }
+               case code == clear:
+                       d.width = 1 + litWidth
+                       hi = eof
+                       overflow = 1 << d.width
+                       last = invalidCode
+                       continue
+               case code == eof:
+                       return w.Flush()
+               case code <= hi:
+                       c, i := code, len(buf)-1
+                       if code == hi {
+                               // code == hi is a special case which expands to the last expansion
+                               // followed by the head of the last expansion. To find the head, we walk
+                               // the prefix chain until we find a literal code.
+                               c = last
+                               for c >= clear {
+                                       c = prefix[c]
+                               }
+                               buf[i] = uint8(c)
+                               i--
+                               c = last
+                       }
+                       // Copy the suffix chain into buf and then write that to w.
+                       for c >= clear {
+                               buf[i] = suffix[c]
+                               i--
+                               c = prefix[c]
+                       }
+                       buf[i] = uint8(c)
+                       if _, err := w.Write(buf[i:]); err != nil {
+                               return err
+                       }
+                       // Save what the hi code expands to.
+                       suffix[hi] = uint8(c)
+                       prefix[hi] = last
+               default:
+                       return os.NewError("lzw: invalid code")
+               }
+               last, hi = code, hi+1
+               if hi == overflow {
+                       if d.width == maxWidth {
+                               return os.NewError("lzw: missing clear code")
+                       }
+                       d.width++
+                       overflow <<= 1
+               }
+       }
+       panic("unreachable")
+}
+
+// NewReader creates a new io.ReadCloser that satisfies reads by decompressing
+// the data read from r.
+// It is the caller's responsibility to call Close on the ReadCloser when
+// finished reading.
+// The number of bits to use for literal codes, litWidth, must be in the
+// range [2,8] and is typically 8.
+func NewReader(r io.Reader, order Order, litWidth int) io.ReadCloser {
+       pr, pw := io.Pipe()
+       var read func(*decoder) (uint16, os.Error)
+       switch order {
+       case LSB:
+               read = (*decoder).readLSB
+       case MSB:
+               read = (*decoder).readMSB
+       default:
+               pw.CloseWithError(os.NewError("lzw: unknown order"))
+               return pr
+       }
+       if litWidth < 2 || 8 < litWidth {
+               pw.CloseWithError(fmt.Errorf("lzw: litWidth %d out of range", litWidth))
+               return pr
+       }
+       go decode(r, read, litWidth, pw)
+       return pr
+}
diff --git a/libgo/go/compress/lzw/reader_test.go b/libgo/go/compress/lzw/reader_test.go
new file mode 100644 (file)
index 0000000..7795a4c
--- /dev/null
@@ -0,0 +1,132 @@
+// Copyright 2011 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 lzw
+
+import (
+       "bytes"
+       "io"
+       "io/ioutil"
+       "os"
+       "strconv"
+       "strings"
+       "testing"
+)
+
+type lzwTest struct {
+       desc       string
+       raw        string
+       compressed string
+       err        os.Error
+}
+
+var lzwTests = []lzwTest{
+       {
+               "empty;LSB;8",
+               "",
+               "\x01\x01",
+               nil,
+       },
+       {
+               "empty;MSB;8",
+               "",
+               "\x80\x80",
+               nil,
+       },
+       {
+               "tobe;LSB;7",
+               "TOBEORNOTTOBEORTOBEORNOT",
+               "\x54\x4f\x42\x45\x4f\x52\x4e\x4f\x54\x82\x84\x86\x8b\x85\x87\x89\x81",
+               nil,
+       },
+       {
+               "tobe;LSB;8",
+               "TOBEORNOTTOBEORTOBEORNOT",
+               "\x54\x9e\x08\x29\xf2\x44\x8a\x93\x27\x54\x04\x12\x34\xb8\xb0\xe0\xc1\x84\x01\x01",
+               nil,
+       },
+       {
+               "tobe;MSB;7",
+               "TOBEORNOTTOBEORTOBEORNOT",
+               "\x54\x4f\x42\x45\x4f\x52\x4e\x4f\x54\x82\x84\x86\x8b\x85\x87\x89\x81",
+               nil,
+       },
+       {
+               "tobe;MSB;8",
+               "TOBEORNOTTOBEORTOBEORNOT",
+               "\x2a\x13\xc8\x44\x52\x79\x48\x9c\x4f\x2a\x40\xa0\x90\x68\x5c\x16\x0f\x09\x80\x80",
+               nil,
+       },
+       {
+               "tobe-truncated;LSB;8",
+               "TOBEORNOTTOBEORTOBEORNOT",
+               "\x54\x9e\x08\x29\xf2\x44\x8a\x93\x27\x54\x04",
+               io.ErrUnexpectedEOF,
+       },
+       // This example comes from http://en.wikipedia.org/wiki/Graphics_Interchange_Format.
+       {
+               "gif;LSB;8",
+               "\x28\xff\xff\xff\x28\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff",
+               "\x00\x51\xfc\x1b\x28\x70\xa0\xc1\x83\x01\x01",
+               nil,
+       },
+       // This example comes from http://compgroups.net/comp.lang.ruby/Decompressing-LZW-compression-from-PDF-file
+       {
+               "pdf;MSB;8",
+               "-----A---B",
+               "\x80\x0b\x60\x50\x22\x0c\x0c\x85\x01",
+               nil,
+       },
+}
+
+func TestReader(t *testing.T) {
+       b := bytes.NewBuffer(nil)
+       for _, tt := range lzwTests {
+               d := strings.Split(tt.desc, ";", -1)
+               var order Order
+               switch d[1] {
+               case "LSB":
+                       order = LSB
+               case "MSB":
+                       order = MSB
+               default:
+                       t.Errorf("%s: bad order %q", tt.desc, d[1])
+               }
+               litWidth, _ := strconv.Atoi(d[2])
+               rc := NewReader(strings.NewReader(tt.compressed), order, litWidth)
+               defer rc.Close()
+               b.Reset()
+               n, err := io.Copy(b, rc)
+               if err != nil {
+                       if err != tt.err {
+                               t.Errorf("%s: io.Copy: %v want %v", tt.desc, err, tt.err)
+                       }
+                       continue
+               }
+               s := b.String()
+               if s != tt.raw {
+                       t.Errorf("%s: got %d-byte %q want %d-byte %q", tt.desc, n, s, len(tt.raw), tt.raw)
+               }
+       }
+}
+
+type devNull struct{}
+
+func (devNull) Write(p []byte) (int, os.Error) {
+       return len(p), nil
+}
+
+func BenchmarkDecoder(b *testing.B) {
+       b.StopTimer()
+       buf0, _ := ioutil.ReadFile("../testdata/e.txt")
+       compressed := bytes.NewBuffer(nil)
+       w := NewWriter(compressed, LSB, 8)
+       io.Copy(w, bytes.NewBuffer(buf0))
+       w.Close()
+       buf1 := compressed.Bytes()
+       b.StartTimer()
+       for i := 0; i < b.N; i++ {
+               io.Copy(devNull{}, NewReader(bytes.NewBuffer(buf1), LSB, 8))
+       }
+}
diff --git a/libgo/go/compress/lzw/writer.go b/libgo/go/compress/lzw/writer.go
new file mode 100644 (file)
index 0000000..87143b7
--- /dev/null
@@ -0,0 +1,259 @@
+// Copyright 2011 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 lzw
+
+import (
+       "bufio"
+       "fmt"
+       "io"
+       "os"
+)
+
+// A writer is a buffered, flushable writer.
+type writer interface {
+       WriteByte(byte) os.Error
+       Flush() os.Error
+}
+
+// An errWriteCloser is an io.WriteCloser that always returns a given error.
+type errWriteCloser struct {
+       err os.Error
+}
+
+func (e *errWriteCloser) Write([]byte) (int, os.Error) {
+       return 0, e.err
+}
+
+func (e *errWriteCloser) Close() os.Error {
+       return e.err
+}
+
+const (
+       // A code is a 12 bit value, stored as a uint32 when encoding to avoid
+       // type conversions when shifting bits.
+       maxCode     = 1<<12 - 1
+       invalidCode = 1<<32 - 1
+       // There are 1<<12 possible codes, which is an upper bound on the number of
+       // valid hash table entries at any given point in time. tableSize is 4x that.
+       tableSize = 4 * 1 << 12
+       tableMask = tableSize - 1
+       // A hash table entry is a uint32. Zero is an invalid entry since the
+       // lower 12 bits of a valid entry must be a non-literal code.
+       invalidEntry = 0
+)
+
+// encoder is LZW compressor.
+type encoder struct {
+       // w is the writer that compressed bytes are written to.
+       w writer
+       // write, bits, nBits and width are the state for converting a code stream
+       // into a byte stream.
+       write func(*encoder, uint32) os.Error
+       bits  uint32
+       nBits uint
+       width uint
+       // litWidth is the width in bits of literal codes.
+       litWidth uint
+       // hi is the code implied by the next code emission.
+       // overflow is the code at which hi overflows the code width.
+       hi, overflow uint32
+       // savedCode is the accumulated code at the end of the most recent Write
+       // call. It is equal to invalidCode if there was no such call.
+       savedCode uint32
+       // err is the first error encountered during writing. Closing the encoder
+       // will make any future Write calls return os.EINVAL.
+       err os.Error
+       // table is the hash table from 20-bit keys to 12-bit values. Each table
+       // entry contains key<<12|val and collisions resolve by linear probing.
+       // The keys consist of a 12-bit code prefix and an 8-bit byte suffix.
+       // The values are a 12-bit code.
+       table [tableSize]uint32
+}
+
+// writeLSB writes the code c for "Least Significant Bits first" data.
+func (e *encoder) writeLSB(c uint32) os.Error {
+       e.bits |= c << e.nBits
+       e.nBits += e.width
+       for e.nBits >= 8 {
+               if err := e.w.WriteByte(uint8(e.bits)); err != nil {
+                       return err
+               }
+               e.bits >>= 8
+               e.nBits -= 8
+       }
+       return nil
+}
+
+// writeMSB writes the code c for "Most Significant Bits first" data.
+func (e *encoder) writeMSB(c uint32) os.Error {
+       e.bits |= c << (32 - e.width - e.nBits)
+       e.nBits += e.width
+       for e.nBits >= 8 {
+               if err := e.w.WriteByte(uint8(e.bits >> 24)); err != nil {
+                       return err
+               }
+               e.bits <<= 8
+               e.nBits -= 8
+       }
+       return nil
+}
+
+// errOutOfCodes is an internal error that means that the encoder has run out
+// of unused codes and a clear code needs to be sent next.
+var errOutOfCodes = os.NewError("lzw: out of codes")
+
+// incHi increments e.hi and checks for both overflow and running out of
+// unused codes. In the latter case, incHi sends a clear code, resets the
+// encoder state and returns errOutOfCodes.
+func (e *encoder) incHi() os.Error {
+       e.hi++
+       if e.hi == e.overflow {
+               e.width++
+               e.overflow <<= 1
+       }
+       if e.hi == maxCode {
+               clear := uint32(1) << e.litWidth
+               if err := e.write(e, clear); err != nil {
+                       return err
+               }
+               e.width = uint(e.litWidth) + 1
+               e.hi = clear + 1
+               e.overflow = clear << 1
+               for i := range e.table {
+                       e.table[i] = invalidEntry
+               }
+               return errOutOfCodes
+       }
+       return nil
+}
+
+// Write writes a compressed representation of p to e's underlying writer.
+func (e *encoder) Write(p []byte) (int, os.Error) {
+       if e.err != nil {
+               return 0, e.err
+       }
+       if len(p) == 0 {
+               return 0, nil
+       }
+       litMask := uint32(1<<e.litWidth - 1)
+       code := e.savedCode
+       if code == invalidCode {
+               // The first code sent is always a literal code.
+               code, p = uint32(p[0])&litMask, p[1:]
+       }
+loop:
+       for _, x := range p {
+               literal := uint32(x) & litMask
+               key := code<<8 | literal
+               // If there is a hash table hit for this key then we continue the loop
+               // and do not emit a code yet.
+               hash := (key>>12 ^ key) & tableMask
+               for h, t := hash, e.table[hash]; t != invalidEntry; {
+                       if key == t>>12 {
+                               code = t & maxCode
+                               continue loop
+                       }
+                       h = (h + 1) & tableMask
+                       t = e.table[h]
+               }
+               // Otherwise, write the current code, and literal becomes the start of
+               // the next emitted code.
+               if e.err = e.write(e, code); e.err != nil {
+                       return 0, e.err
+               }
+               code = literal
+               // Increment e.hi, the next implied code. If we run out of codes, reset
+               // the encoder state (including clearing the hash table) and continue.
+               if err := e.incHi(); err != nil {
+                       if err == errOutOfCodes {
+                               continue
+                       }
+                       e.err = err
+                       return 0, e.err
+               }
+               // Otherwise, insert key -> e.hi into the map that e.table represents.
+               for {
+                       if e.table[hash] == invalidEntry {
+                               e.table[hash] = (key << 12) | e.hi
+                               break
+                       }
+                       hash = (hash + 1) & tableMask
+               }
+       }
+       e.savedCode = code
+       return len(p), nil
+}
+
+// Close closes the encoder, flushing any pending output. It does not close or
+// flush e's underlying writer.
+func (e *encoder) Close() os.Error {
+       if e.err != nil {
+               if e.err == os.EINVAL {
+                       return nil
+               }
+               return e.err
+       }
+       // Make any future calls to Write return os.EINVAL.
+       e.err = os.EINVAL
+       // Write the savedCode if valid.
+       if e.savedCode != invalidCode {
+               if err := e.write(e, e.savedCode); err != nil {
+                       return err
+               }
+               if err := e.incHi(); err != nil && err != errOutOfCodes {
+                       return err
+               }
+       }
+       // Write the eof code.
+       eof := uint32(1)<<e.litWidth + 1
+       if err := e.write(e, eof); err != nil {
+               return err
+       }
+       // Write the final bits.
+       if e.nBits > 0 {
+               if e.write == (*encoder).writeMSB {
+                       e.bits >>= 24
+               }
+               if err := e.w.WriteByte(uint8(e.bits)); err != nil {
+                       return err
+               }
+       }
+       return e.w.Flush()
+}
+
+// NewWriter creates a new io.WriteCloser that satisfies writes by compressing
+// the data and writing it to w.
+// It is the caller's responsibility to call Close on the WriteCloser when
+// finished writing.
+// The number of bits to use for literal codes, litWidth, must be in the
+// range [2,8] and is typically 8.
+func NewWriter(w io.Writer, order Order, litWidth int) io.WriteCloser {
+       var write func(*encoder, uint32) os.Error
+       switch order {
+       case LSB:
+               write = (*encoder).writeLSB
+       case MSB:
+               write = (*encoder).writeMSB
+       default:
+               return &errWriteCloser{os.NewError("lzw: unknown order")}
+       }
+       if litWidth < 2 || 8 < litWidth {
+               return &errWriteCloser{fmt.Errorf("lzw: litWidth %d out of range", litWidth)}
+       }
+       bw, ok := w.(writer)
+       if !ok {
+               bw = bufio.NewWriter(w)
+       }
+       lw := uint(litWidth)
+       return &encoder{
+               w:         bw,
+               write:     write,
+               width:     1 + lw,
+               litWidth:  lw,
+               hi:        1<<lw + 1,
+               overflow:  1 << (lw + 1),
+               savedCode: invalidCode,
+       }
+}
diff --git a/libgo/go/compress/lzw/writer_test.go b/libgo/go/compress/lzw/writer_test.go
new file mode 100644 (file)
index 0000000..715b974
--- /dev/null
@@ -0,0 +1,111 @@
+// Copyright 2011 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 lzw
+
+import (
+       "io"
+       "io/ioutil"
+       "os"
+       "testing"
+)
+
+var filenames = []string{
+       "../testdata/e.txt",
+       "../testdata/pi.txt",
+}
+
+// testFile tests that compressing and then decompressing the given file with
+// the given options yields equivalent bytes to the original file.
+func testFile(t *testing.T, fn string, order Order, litWidth int) {
+       // Read the file, as golden output.
+       golden, err := os.Open(fn, os.O_RDONLY, 0400)
+       if err != nil {
+               t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err)
+               return
+       }
+       defer golden.Close()
+
+       // Read the file again, and push it through a pipe that compresses at the write end, and decompresses at the read end.
+       raw, err := os.Open(fn, os.O_RDONLY, 0400)
+       if err != nil {
+               t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err)
+               return
+       }
+
+       piper, pipew := io.Pipe()
+       defer piper.Close()
+       go func() {
+               defer raw.Close()
+               defer pipew.Close()
+               lzww := NewWriter(pipew, order, litWidth)
+               defer lzww.Close()
+               var b [4096]byte
+               for {
+                       n, err0 := raw.Read(b[:])
+                       if err0 != nil && err0 != os.EOF {
+                               t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err0)
+                               return
+                       }
+                       _, err1 := lzww.Write(b[:n])
+                       if err1 == os.EPIPE {
+                               // Fail, but do not report the error, as some other (presumably reportable) error broke the pipe.
+                               return
+                       }
+                       if err1 != nil {
+                               t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err1)
+                               return
+                       }
+                       if err0 == os.EOF {
+                               break
+                       }
+               }
+       }()
+       lzwr := NewReader(piper, order, litWidth)
+       defer lzwr.Close()
+
+       // Compare the two.
+       b0, err0 := ioutil.ReadAll(golden)
+       b1, err1 := ioutil.ReadAll(lzwr)
+       if err0 != nil {
+               t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err0)
+               return
+       }
+       if err1 != nil {
+               t.Errorf("%s (order=%d litWidth=%d): %v", fn, order, litWidth, err1)
+               return
+       }
+       if len(b0) != len(b1) {
+               t.Errorf("%s (order=%d litWidth=%d): length mismatch %d versus %d", fn, order, litWidth, len(b0), len(b1))
+               return
+       }
+       for i := 0; i < len(b0); i++ {
+               if b0[i] != b1[i] {
+                       t.Errorf("%s (order=%d litWidth=%d): mismatch at %d, 0x%02x versus 0x%02x\n", fn, order, litWidth, i, b0[i], b1[i])
+                       return
+               }
+       }
+}
+
+func TestWriter(t *testing.T) {
+       for _, filename := range filenames {
+               for _, order := range [...]Order{LSB, MSB} {
+                       // The test data "2.71828 etcetera" is ASCII text requiring at least 6 bits.
+                       for _, litWidth := range [...]int{6, 7, 8} {
+                               testFile(t, filename, order, litWidth)
+                       }
+               }
+       }
+}
+
+func BenchmarkEncoder(b *testing.B) {
+       b.StopTimer()
+       buf, _ := ioutil.ReadFile("../testdata/e.txt")
+       b.StartTimer()
+       for i := 0; i < b.N; i++ {
+               w := NewWriter(devNull{}, LSB, 8)
+               w.Write(buf)
+               w.Close()
+       }
+}
diff --git a/libgo/go/compress/testdata/e.txt b/libgo/go/compress/testdata/e.txt
new file mode 100644 (file)
index 0000000..76cf2a7
--- /dev/null
@@ -0,0 +1 @@
+2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190115738341879307021540891499348841675092447614606680822648001684774118537423454424371075390777449920695517027618386062613313845830007520449338265602976067371132007093287091274437470472306969772093101416928368190255151086574637721112523897844250569536967707854499699679468644549059879316368892300987931277361782154249992295763514822082698951936680331825288693984964651058209392398294887933203625094431173012381970684161403970198376793206832823764648042953118023287825098194558153017567173613320698112509961818815930416903515988885193458072738667385894228792284998920868058257492796104841984443634632449684875602336248270419786232090021609902353043699418491463140934317381436405462531520961836908887070167683964243781405927145635490613031072085103837505101157477041718986106873969655212671546889570350354021234078498193343210681701210056278802351930332247450158539047304199577770935036604169973297250886876966403555707162268447162560798826517871341951246652010305921236677194325278675398558944896970964097545918569563802363701621120477427228364896134225164450781824423529486363721417402388934412479635743702637552944483379980161254922785092577825620926226483262779333865664816277251640191059004916449982893150566047258027786318641551956532442586982946959308019152987211725563475463964479101459040905862984967912874068705048958586717479854667757573205681288459205413340539220001137863009455606881667400169842055804033637953764520304024322566135278369511778838638744396625322498506549958862342818997077332761717839280349465014345588970719425863987727547109629537415211151368350627526023264847287039207643100595841166120545297030236472549296669381151373227536450988890313602057248176585118063036442812314965507047510254465011727211555194866850800368532281831521960037356252794495158284188294787610852639813955990067376482922443752871846245780361929819713991475644882626039033814418232625150974827987779964373089970388867782271383605772978824125611907176639465070633045279546618550966661856647097113444740160704626215680717481877844371436988218559670959102596862002353718588748569652200050311734392073211390803293634479727355955277349071783793421637012050054513263835440001863239914907054797780566978533580489669062951194324730995876552368128590413832411607226029983305353708761389396391779574540161372236187893652605381558415871869255386061647798340254351284396129460352913325942794904337299085731580290958631382683291477116396337092400316894586360606458459251269946557248391865642097526850823075442545993769170419777800853627309417101634349076964237222943523661255725088147792231519747780605696725380171807763603462459278778465850656050780844211529697521890874019660906651803516501792504619501366585436632712549639908549144200014574760819302212066024330096412704894390397177195180699086998606636583232278709376502260149291011517177635944602023249300280401867723910288097866605651183260043688508817157238669842242201024950551881694803221002515426494639812873677658927688163598312477886520141174110913601164995076629077943646005851941998560162647907615321038727557126992518275687989302761761146162549356495903798045838182323368612016243736569846703785853305275833337939907521660692380533698879565137285593883499894707416181550125397064648171946708348197214488898790676503795903669672494992545279033729636162658976039498576741397359441023744329709355477982629614591442936451428617158587339746791897571211956187385783644758448423555581050025611492391518893099463428413936080383091662818811503715284967059741625628236092168075150177725387402564253470879089137291722828611515915683725241630772254406337875931059826760944203261924285317018781772960235413060672136046000389661093647095141417185777014180606443636815464440053316087783143174440811949422975599314011888683314832802706553833004693290115744147563139997221703804617092894579096271662260740718749975359212756084414737823303270330168237193648002173285734935947564334129943024850235732214597843282641421684878721673367010615094243456984401873312810107945127223737886126058165668053714396127888732527373890392890506865324138062796025930387727697783792868409325365880733988457218746021005311483351323850047827169376218004904795597959290591655470505777514308175112698985188408718564026035305583737832422924185625644255022672155980274012617971928047139600689163828665277009752767069777036439260224372841840883251848770472638440379530166905465937461619323840363893131364327137688841026811219891275223056256756254701725086349765367288605966752740868627407912856576996313789753034660616669804218267724560530660773899624218340859882071864682623215080288286359746839654358856685503773131296587975810501214916207656769950659715344763470320853215603674828608378656803073062657633469774295634643716709397193060876963495328846833613038829431040800296873869117066666146800015121143442256023874474325250769387077775193299942137277211258843608715834835626961661980572526612206797540621062080649882918454395301529982092503005498257043390553570168653120526495614857249257386206917403695213533732531666345466588597286659451136441370331393672118569553952108458407244323835586063106806964924851232632699514603596037297253198368423363904632136710116192821711150282801604488058802382031981493096369596735832742024988245684941273860566491352526706046234450549227581151709314921879592718001940968866986837037302200475314338181092708030017205935530520700706072233999463990571311587099635777359027196285061146514837526209565346713290025994397663114545902685898979115837093419370441155121920117164880566945938131183843765620627846310490346293950029458341164824114969758326011800731699437393506966295712410273239138741754923071862454543222039552735295240245903805744502892246886285336542213815722131163288112052146489805180092024719391710555390113943316681515828843687606961102505171007392762385553386272553538830960671644662370922646809671254061869502143176211668140097595281493907222601112681153108387317617323235263605838173151034595736538223534992935822836851007810884634349983518404451704270189381994243410090575376257767571118090088164183319201962623416288166521374717325477727783488774366518828752156685719506371936565390389449366421764003121527870222366463635755503565576948886549500270853923617105502131147413744106134445544192101336172996285694899193369184729478580729156088510396781959429833186480756083679551496636448965592948187851784038773326247051945050419847742014183947731202815886845707290544057510601285258056594703046836344592652552137008068752009593453607316226118728173928074623094685367823106097921599360019946237993434210687813497346959246469752506246958616909178573976595199392993995567542714654910456860702099012606818704984178079173924071945996323060254707901774527513186809982284730860766536866855516467702911336827563107223346726113705490795365834538637196235856312618387156774118738527722922594743373785695538456246801013905727871016512966636764451872465653730402443684140814488732957847348490003019477888020460324660842875351848364959195082888323206522128104190448047247949291342284951970022601310430062410717971502793433263407995960531446053230488528972917659876016667811937932372453857209607582277178483361613582612896226118129455927462767137794487586753657544861407611931125958512655759734573015333642630767985443385761715333462325270572005303988289499034259566232975782488735029259166825894456894655992658454762694528780516501720674785417887982276806536650641910973434528878338621726156269582654478205672987756426325321594294418039943217000090542650763095588465895171709147607437136893319469090981904501290307099566226620303182649365733698419555776963787624918852865686607600566025605445711337286840205574416030837052312242587223438854123179481388550075689381124935386318635287083799845692619981794523364087429591180747453419551420351726184200845509170845682368200897739455842679214273477560879644279202708312150156406341341617166448069815483764491573900121217041547872591998943825364950514771379399147205219529079396137621107238494290616357604596231253506068537651423115349665683715116604220796394466621163255157729070978473156278277598788136491951257483328793771571459091064841642678309949723674420175862269402159407924480541255360431317992696739157542419296607312393763542139230617876753958711436104089409966089471418340698362993675362621545247298464213752891079884381306095552622720837518629837066787224430195793793786072107254277289071732854874374355781966511716618330881129120245204048682200072344035025448202834254187884653602591506445271657700044521097735585897622655484941621714989532383421600114062950718490427789258552743035221396835679018076406042138307308774460170842688272261177180842664333651780002171903449234264266292261456004337383868335555343453004264818473989215627086095650629340405264943244261445665921291225648893569655009154306426134252668472594914314239398845432486327461842846655985332312210466259890141712103446084271616619001257195870793217569698544013397622096749454185407118446433946990162698351607848924514058940946395267807354579700307051163682519487701189764002827648414160587206184185297189154019688253289309149665345753571427318482016384644832499037886069008072709327673127581966563941148961716832980455139729506687604740915420428429993541025829113502241690769431668574242522509026939034814856451303069925199590436384028429267412573422447765584177886171737265462085498294498946787350929581652632072258992368768457017823038096567883112289305809140572610865884845873101658151167533327674887014829167419701512559782572707406431808601428149024146780472327597684269633935773542930186739439716388611764209004068663398856841681003872389214483176070116684503887212364367043314091155733280182977988736590916659612402021778558854876176161989370794380056663364884365089144805571039765214696027662583599051987042300179465536788
diff --git a/libgo/go/compress/testdata/pi.txt b/libgo/go/compress/testdata/pi.txt
new file mode 100644 (file)
index 0000000..58d8f3b
--- /dev/null
@@ -0,0 +1 @@
+3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989380952572010654858632788659361533818279682303019520353018529689957736225994138912497217752834791315155748572424541506959508295331168617278558890750983817546374649393192550604009277016711390098488240128583616035637076601047101819429555961989467678374494482553797747268471040475346462080466842590694912933136770289891521047521620569660240580381501935112533824300355876402474964732639141992726042699227967823547816360093417216412199245863150302861829745557067498385054945885869269956909272107975093029553211653449872027559602364806654991198818347977535663698074265425278625518184175746728909777727938000816470600161452491921732172147723501414419735685481613611573525521334757418494684385233239073941433345477624168625189835694855620992192221842725502542568876717904946016534668049886272327917860857843838279679766814541009538837863609506800642251252051173929848960841284886269456042419652850222106611863067442786220391949450471237137869609563643719172874677646575739624138908658326459958133904780275900994657640789512694683983525957098258226205224894077267194782684826014769909026401363944374553050682034962524517493996514314298091906592509372216964615157098583874105978859597729754989301617539284681382686838689427741559918559252459539594310499725246808459872736446958486538367362226260991246080512438843904512441365497627807977156914359977001296160894416948685558484063534220722258284886481584560285060168427394522674676788952521385225499546667278239864565961163548862305774564980355936345681743241125150760694794510965960940252288797108931456691368672287489405601015033086179286809208747609178249385890097149096759852613655497818931297848216829989487226588048575640142704775551323796414515237462343645428584447952658678210511413547357395231134271661021359695362314429524849371871101457654035902799344037420073105785390621983874478084784896833214457138687519435064302184531910484810053706146806749192781911979399520614196634287544406437451237181921799983910159195618146751426912397489409071864942319615679452080951465502252316038819301420937621378559566389377870830390697920773467221825625996615014215030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539057962685610055081066587969981635747363840525714591028970641401109712062804390397595156771577004203378699360072305587631763594218731251471205329281918261861258673215791984148488291644706095752706957220917567116722910981690915280173506712748583222871835209353965725121083579151369882091444210067510334671103141267111369908658516398315019701651511685171437657618351556508849099898599823873455283316355076479185358932261854896321329330898570642046752590709154814165498594616371802709819943099244889575712828905923233260972997120844335732654893823911932597463667305836041428138830320382490375898524374417029132765618093773444030707469211201913020330380197621101100449293215160842444859637669838952286847831235526582131449576857262433441893039686426243410773226978028073189154411010446823252716201052652272111660396665573092547110557853763466820653109896526918620564769312570586356620185581007293606598764861179104533488503461136576867532494416680396265797877185560845529654126654085306143444318586769751456614068007002378776591344017127494704205622305389945613140711270004078547332699390814546646458807972708266830634328587856983052358089330657574067954571637752542021149557615814002501262285941302164715509792592309907965473761255176567513575178296664547791745011299614890304639947132962107340437518957359614589019389713111790429782856475032031986915140287080859904801094121472213179476477726224142548545403321571853061422881375850430633217518297986622371721591607716692547487389866549494501146540628433663937900397692656721463853067360965712091807638327166416274888800786925602902284721040317211860820419000422966171196377921337575114959501566049631862947265473642523081770367515906735023507283540567040386743513622224771589150495309844489333096340878076932599397805419341447377441842631298608099888687413260472156951623965864573021631598193195167353812974167729478672422924654366800980676928238280689964004824354037014163149658979409243237896907069779422362508221688957383798623001593776471651228935786015881617557829735233446042815126272037343146531977774160319906655418763979293344195215413418994854447345673831624993419131814809277771038638773431772075456545322077709212019051660962804909263601975988281613323166636528619326686336062735676303544776280350450777235547105859548702790814356240145171806246436267945612753181340783303362542327839449753824372058353114771199260638133467768796959703098339130771098704085913374641442822772634659470474587847787201927715280731767907707157213444730605700733492436931138350493163128404251219256517980694113528013147013047816437885185290928545201165839341965621349143415956258658655705526904965209858033850722426482939728584783163057777560688876446248246857926039535277348030480290058760758251047470916439613626760449256274204208320856611906254543372131535958450687724602901618766795240616342522577195429162991930645537799140373404328752628889639958794757291746426357455254079091451357111369410911939325191076020825202618798531887705842972591677813149699009019211697173727847684726860849003377024242916513005005168323364350389517029893922334517220138128069650117844087451960121228599371623130171144484640903890644954440061986907548516026327505298349187407866808818338510228334508504860825039302133219715518430635455007668282949304137765527939751754613953984683393638304746119966538581538420568533862186725233402830871123282789212507712629463229563989898935821167456270102183564622013496715188190973038119800497340723961036854066431939509790190699639552453005450580685501956730229219139339185680344903982059551002263535361920419947455385938102343955449597783779023742161727111723643435439478221818528624085140066604433258885698670543154706965747458550332323342107301545940516553790686627333799585115625784322988273723198987571415957811196358330059408730681216028764962867446047746491599505497374256269010490377819868359381465741268049256487985561453723478673303904688383436346553794986419270563872931748723320837601123029911367938627089438799362016295154133714248928307220126901475466847653576164773794675200490757155527819653621323926406160136358155907422020203187277605277219005561484255518792530343513984425322341576233610642506390497500865627109535919465897514131034822769306247435363256916078154781811528436679570611086153315044521274739245449454236828860613408414863776700961207151249140430272538607648236341433462351897576645216413767969031495019108575984423919862916421939949072362346468441173940326591840443780513338945257423995082965912285085558215725031071257012668302402929525220118726767562204154205161841634847565169998116141010029960783869092916030288400269104140792886215078424516709087000699282120660418371806535567252532567532861291042487761825829765157959847035622262934860034158722980534989650226291748788202734209222245339856264766914905562842503912757710284027998066365825488926488025456610172967026640765590429099456815065265305371829412703369313785178609040708667114965583434347693385781711386455873678123014587687126603489139095620099393610310291616152881384379099042317473363948045759314931405297634757481193567091101377517210080315590248530906692037671922033229094334676851422144773793937517034436619910403375111735471918550464490263655128162288244625759163330391072253837421821408835086573917715096828874782656995995744906617583441375223970968340800535598491754173818839994469748676265516582765848358845314277568790029095170283529716344562129640435231176006651012412006597558512761785838292041974844236080071930457618932349229279650198751872127267507981255470958904556357921221033346697499235630254947802490114195212382815309114079073860251522742995818072471625916685451333123948049470791191532673430282441860414263639548000448002670496248201792896476697583183271314251702969234889627668440323260927524960357996469256504936818360900323809293459588970695365349406034021665443755890045632882250545255640564482465151875471196218443965825337543885690941130315095261793780029741207665147939425902989695946995565761218656196733786236256125216320862869222103274889218654364802296780705765615144632046927906821207388377814233562823608963208068222468012248261177185896381409183903673672220888321513755600372798394004152970028783076670944474560134556417254370906979396122571429894671543578468788614445812314593571984922528471605049221242470141214780573455105008019086996033027634787081081754501193071412233908663938339529425786905076431006383519834389341596131854347546495569781038293097164651438407007073604112373599843452251610507027056235266012764848308407611830130527932054274628654036036745328651057065874882256981579367897669742205750596834408697350201410206723585020072452256326513410559240190274216248439140359989535394590944070469120914093870012645600162374288021092764579310657922955249887275846101264836999892256959688159205600101655256375678
index fa9e78e..5a13ba8 100644 (file)
@@ -12,8 +12,8 @@ import (
 )
 
 var filenames = []string{
-       "testdata/e.txt",
-       "testdata/pi.txt",
+       "../testdata/e.txt",
+       "../testdata/pi.txt",
 }
 
 // Tests that compressing and then decompressing the given file at the given compression level
index 335afbc..5925164 100644 (file)
@@ -138,16 +138,13 @@ func (r *Ring) Len() int {
 }
 
 
-func (r *Ring) Iter() <-chan interface{} {
-       c := make(chan interface{})
-       go func() {
-               if r != nil {
-                       c <- r.Value
-                       for p := r.Next(); p != r; p = p.next {
-                               c <- p.Value
-                       }
+// Do calls function f on each element of the ring, in forward order.
+// The behavior of Do is undefined if f changes *r.
+func (r *Ring) Do(f func(interface{})) {
+       if r != nil {
+               f(r.Value)
+               for p := r.Next(); p != r; p = p.next {
+                       f(p.Value)
                }
-               close(c)
-       }()
-       return c
+       }
 }
index ee3c411..778c083 100644 (file)
@@ -35,12 +35,12 @@ func verify(t *testing.T, r *Ring, N int, sum int) {
        // iteration
        n = 0
        s := 0
-       for p := range r.Iter() {
+       r.Do(func(p interface{}) {
                n++
                if p != nil {
                        s += p.(int)
                }
-       }
+       })
        if n != N {
                t.Errorf("number of forward iterations == %d; expected %d", n, N)
        }
@@ -128,16 +128,6 @@ func makeN(n int) *Ring {
        return r
 }
 
-
-func sum(r *Ring) int {
-       s := 0
-       for p := range r.Iter() {
-               s += p.(int)
-       }
-       return s
-}
-
-
 func sumN(n int) int { return (n*n + n) / 2 }
 
 
index 43cb5a5..b2d8775 100644 (file)
@@ -12,11 +12,21 @@ type ocfbEncrypter struct {
        outUsed int
 }
 
+// An OCFBResyncOption determines if the "resynchronization step" of OCFB is
+// performed.
+type OCFBResyncOption bool
+
+const (
+       OCFBResync   OCFBResyncOption = true
+       OCFBNoResync OCFBResyncOption = false
+)
+
 // NewOCFBEncrypter returns a Stream which encrypts data with OpenPGP's cipher
 // feedback mode using the given Block, and an initial amount of ciphertext.
 // randData must be random bytes and be the same length as the Block's block
-// size.
-func NewOCFBEncrypter(block Block, randData []byte) (Stream, []byte) {
+// size. Resync determines if the "resynchronization step" from RFC 4880, 13.9
+// step 7 is performed. Different parts of OpenPGP vary on this point.
+func NewOCFBEncrypter(block Block, randData []byte, resync OCFBResyncOption) (Stream, []byte) {
        blockSize := block.BlockSize()
        if len(randData) != blockSize {
                return nil, nil
@@ -38,7 +48,13 @@ func NewOCFBEncrypter(block Block, randData []byte) (Stream, []byte) {
        prefix[blockSize] = x.fre[0] ^ randData[blockSize-2]
        prefix[blockSize+1] = x.fre[1] ^ randData[blockSize-1]
 
-       block.Encrypt(x.fre, prefix[2:])
+       if resync {
+               block.Encrypt(x.fre, prefix[2:])
+       } else {
+               x.fre[0] = prefix[blockSize]
+               x.fre[1] = prefix[blockSize+1]
+               x.outUsed = 2
+       }
        return x, prefix
 }
 
@@ -64,8 +80,10 @@ type ocfbDecrypter struct {
 // NewOCFBDecrypter returns a Stream which decrypts data with OpenPGP's cipher
 // feedback mode using the given Block. Prefix must be the first blockSize + 2
 // bytes of the ciphertext, where blockSize is the Block's block size. If an
-// incorrect key is detected then nil is returned.
-func NewOCFBDecrypter(block Block, prefix []byte) Stream {
+// incorrect key is detected then nil is returned. Resync determines if the
+// "resynchronization step" from RFC 4880, 13.9 step 7 is performed. Different
+// parts of OpenPGP vary on this point.
+func NewOCFBDecrypter(block Block, prefix []byte, resync OCFBResyncOption) Stream {
        blockSize := block.BlockSize()
        if len(prefix) != blockSize+2 {
                return nil
@@ -93,7 +111,13 @@ func NewOCFBDecrypter(block Block, prefix []byte) Stream {
                return nil
        }
 
-       block.Encrypt(x.fre, prefix[2:])
+       if resync {
+               block.Encrypt(x.fre, prefix[2:])
+       } else {
+               x.fre[0] = prefix[blockSize]
+               x.fre[1] = prefix[blockSize+1]
+               x.outUsed = 2
+       }
        return x
 }
 
index 289bb7c..40938b5 100644 (file)
@@ -11,29 +11,34 @@ import (
        "testing"
 )
 
-func TestOCFB(t *testing.T) {
+func testOCFB(t *testing.T, resync OCFBResyncOption) {
        block, err := aes.NewCipher(commonKey128)
        if err != nil {
                t.Error(err)
                return
        }
 
-       plaintext := []byte("this is the plaintext")
+       plaintext := []byte("this is the plaintext, which is long enough to span several blocks.")
        randData := make([]byte, block.BlockSize())
        rand.Reader.Read(randData)
-       ocfb, prefix := NewOCFBEncrypter(block, randData)
+       ocfb, prefix := NewOCFBEncrypter(block, randData, resync)
        ciphertext := make([]byte, len(plaintext))
        ocfb.XORKeyStream(ciphertext, plaintext)
 
-       ocfbdec := NewOCFBDecrypter(block, prefix)
+       ocfbdec := NewOCFBDecrypter(block, prefix, resync)
        if ocfbdec == nil {
-               t.Error("NewOCFBDecrypter failed")
+               t.Errorf("NewOCFBDecrypter failed (resync: %t)", resync)
                return
        }
        plaintextCopy := make([]byte, len(plaintext))
        ocfbdec.XORKeyStream(plaintextCopy, ciphertext)
 
        if !bytes.Equal(plaintextCopy, plaintext) {
-               t.Errorf("got: %x, want: %x", plaintextCopy, plaintext)
+               t.Errorf("got: %x, want: %x (resync: %t)", plaintextCopy, plaintext, resync)
        }
 }
+
+func TestOCFB(t *testing.T) {
+       testOCFB(t, OCFBNoResync)
+       testOCFB(t, OCFBResync)
+}
diff --git a/libgo/go/crypto/crypto.go b/libgo/go/crypto/crypto.go
new file mode 100644 (file)
index 0000000..be6b34a
--- /dev/null
@@ -0,0 +1,73 @@
+// Copyright 2011 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.
+
+// The crypto package collects common cryptographic constants.
+package crypto
+
+import (
+       "hash"
+)
+
+// Hash identifies a cryptographic hash function that is implemented in another
+// package.
+type Hash uint
+
+const (
+       MD4       Hash = 1 + iota // in package crypto/md4
+       MD5                       // in package crypto/md5
+       SHA1                      // in package crypto/sha1
+       SHA224                    // in package crypto/sha256
+       SHA256                    // in package crypto/sha256
+       SHA384                    // in package crypto/sha512
+       SHA512                    // in package crypto/sha512
+       MD5SHA1                   // no implementation; MD5+SHA1 used for TLS RSA
+       RIPEMD160                 // in package crypto/ripemd160
+       maxHash
+)
+
+var digestSizes = []uint8{
+       MD4:       16,
+       MD5:       16,
+       SHA1:      20,
+       SHA224:    28,
+       SHA256:    32,
+       SHA384:    48,
+       SHA512:    64,
+       MD5SHA1:   36,
+       RIPEMD160: 20,
+}
+
+// Size returns the length, in bytes, of a digest resulting from the given hash
+// function. It doesn't require that the hash function in question be linked
+// into the program.
+func (h Hash) Size() int {
+       if h > 0 && h < maxHash {
+               return int(digestSizes[h])
+       }
+       panic("crypto: Size of unknown hash function")
+}
+
+var hashes = make([]func() hash.Hash, maxHash)
+
+// New returns a new hash.Hash calculating the given hash function. If the
+// hash function is not linked into the binary, New returns nil.
+func (h Hash) New() hash.Hash {
+       if h > 0 && h < maxHash {
+               f := hashes[h]
+               if f != nil {
+                       return f()
+               }
+       }
+       return nil
+}
+
+// RegisterHash registers a function that returns a new instance of the given
+// hash function. This is intended to be called from the init function in
+// packages that implement hash functions.
+func RegisterHash(h Hash, f func() hash.Hash) {
+       if h >= maxHash {
+               panic("crypto: RegisterHash of unknown hash function")
+       }
+       hashes[h] = f
+}
diff --git a/libgo/go/crypto/dsa/dsa.go b/libgo/go/crypto/dsa/dsa.go
new file mode 100644 (file)
index 0000000..f0af8bb
--- /dev/null
@@ -0,0 +1,276 @@
+// Copyright 2011 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 dsa implements the Digital Signature Algorithm, as defined in FIPS 186-3
+package dsa
+
+import (
+       "big"
+       "io"
+       "os"
+)
+
+// Parameters represents the domain parameters for a key. These parameters can
+// be shared across many keys. The bit length of Q must be a multiple of 8.
+type Parameters struct {
+       P, Q, G *big.Int
+}
+
+// PublicKey represents a DSA public key.
+type PublicKey struct {
+       Parameters
+       Y *big.Int
+}
+
+// PrivateKey represents a DSA private key.
+type PrivateKey struct {
+       PublicKey
+       X *big.Int
+}
+
+type invalidPublicKeyError int
+
+func (invalidPublicKeyError) String() string {
+       return "crypto/dsa: invalid public key"
+}
+
+// InvalidPublicKeyError results when a public key is not usable by this code.
+// FIPS is quite strict about the format of DSA keys, but other code may be
+// less so. Thus, when using keys which may have been generated by other code,
+// this error must be handled.
+var InvalidPublicKeyError = invalidPublicKeyError(0)
+
+// ParameterSizes is a enumeration of the acceptable bit lengths of the primes
+// in a set of DSA parameters. See FIPS 186-3, section 4.2.
+type ParameterSizes int
+
+const (
+       L1024N160 ParameterSizes = iota
+       L2048N224
+       L2048N256
+       L3072N256
+)
+
+// numMRTests is the number of Miller-Rabin primality tests that we perform. We
+// pick the largest recommended number from table C.1 of FIPS 186-3.
+const numMRTests = 64
+
+// GenerateParameters puts a random, valid set of DSA parameters into params.
+// This function takes many seconds, even on fast machines.
+func GenerateParameters(params *Parameters, rand io.Reader, sizes ParameterSizes) (err os.Error) {
+       // This function doesn't follow FIPS 186-3 exactly in that it doesn't
+       // use a verification seed to generate the primes. The verification
+       // seed doesn't appear to be exported or used by other code and
+       // omitting it makes the code cleaner.
+
+       var L, N int
+       switch sizes {
+       case L1024N160:
+               L = 1024
+               N = 160
+       case L2048N224:
+               L = 2048
+               N = 224
+       case L2048N256:
+               L = 2048
+               N = 256
+       case L3072N256:
+               L = 3072
+               N = 256
+       default:
+               return os.ErrorString("crypto/dsa: invalid ParameterSizes")
+       }
+
+       qBytes := make([]byte, N/8)
+       pBytes := make([]byte, L/8)
+
+       q := new(big.Int)
+       p := new(big.Int)
+       rem := new(big.Int)
+       one := new(big.Int)
+       one.SetInt64(1)
+
+GeneratePrimes:
+       for {
+               _, err = io.ReadFull(rand, qBytes)
+               if err != nil {
+                       return
+               }
+
+               qBytes[len(qBytes)-1] |= 1
+               qBytes[0] |= 0x80
+               q.SetBytes(qBytes)
+
+               if !big.ProbablyPrime(q, numMRTests) {
+                       continue
+               }
+
+               for i := 0; i < 4*L; i++ {
+                       _, err = io.ReadFull(rand, pBytes)
+                       if err != nil {
+                               return
+                       }
+
+                       pBytes[len(pBytes)-1] |= 1
+                       pBytes[0] |= 0x80
+
+                       p.SetBytes(pBytes)
+                       rem.Mod(p, q)
+                       rem.Sub(rem, one)
+                       p.Sub(p, rem)
+                       if p.BitLen() < L {
+                               continue
+                       }
+
+                       if !big.ProbablyPrime(p, numMRTests) {
+                               continue
+                       }
+
+                       params.P = p
+                       params.Q = q
+                       break GeneratePrimes
+               }
+       }
+
+       h := new(big.Int)
+       h.SetInt64(2)
+       g := new(big.Int)
+
+       pm1 := new(big.Int).Sub(p, one)
+       e := new(big.Int).Div(pm1, q)
+
+       for {
+               g.Exp(h, e, p)
+               if g.Cmp(one) == 0 {
+                       h.Add(h, one)
+                       continue
+               }
+
+               params.G = g
+               return
+       }
+
+       panic("unreachable")
+}
+
+// GenerateKey generates a public&private key pair. The Parameters of the
+// PrivateKey must already be valid (see GenerateParameters).
+func GenerateKey(priv *PrivateKey, rand io.Reader) os.Error {
+       if priv.P == nil || priv.Q == nil || priv.G == nil {
+               return os.ErrorString("crypto/dsa: parameters not set up before generating key")
+       }
+
+       x := new(big.Int)
+       xBytes := make([]byte, priv.Q.BitLen()/8)
+
+       for {
+               _, err := io.ReadFull(rand, xBytes)
+               if err != nil {
+                       return err
+               }
+               x.SetBytes(xBytes)
+               if x.Sign() != 0 && x.Cmp(priv.Q) < 0 {
+                       break
+               }
+       }
+
+       priv.X = x
+       priv.Y = new(big.Int)
+       priv.Y.Exp(priv.G, x, priv.P)
+       return nil
+}
+
+// Sign signs an arbitrary length hash (which should be the result of hashing a
+// larger message) using the private key, priv. It returns the signature as a
+// pair of integers. The security of the private key depends on the entropy of
+// rand.
+func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err os.Error) {
+       // FIPS 186-3, section 4.6
+
+       n := priv.Q.BitLen()
+       if n&7 != 0 {
+               err = InvalidPublicKeyError
+               return
+       }
+       n >>= 3
+
+       for {
+               k := new(big.Int)
+               buf := make([]byte, n)
+               for {
+                       _, err = io.ReadFull(rand, buf)
+                       if err != nil {
+                               return
+                       }
+                       k.SetBytes(buf)
+                       if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
+                               break
+                       }
+               }
+
+               kInv := new(big.Int).ModInverse(k, priv.Q)
+
+               r = new(big.Int).Exp(priv.G, k, priv.P)
+               r.Mod(r, priv.Q)
+
+               if r.Sign() == 0 {
+                       continue
+               }
+
+               if n > len(hash) {
+                       n = len(hash)
+               }
+               z := k.SetBytes(hash[:n])
+
+               s = new(big.Int).Mul(priv.X, r)
+               s.Add(s, z)
+               s.Mod(s, priv.Q)
+               s.Mul(s, kInv)
+               s.Mod(s, priv.Q)
+
+               if s.Sign() != 0 {
+                       break
+               }
+       }
+
+       return
+}
+
+// Verify verifies the signature in r, s of hash using the public key, pub. It
+// returns true iff the signature is valid.
+func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
+       // FIPS 186-3, section 4.7
+
+       if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
+               return false
+       }
+       if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
+               return false
+       }
+
+       w := new(big.Int).ModInverse(s, pub.Q)
+
+       n := pub.Q.BitLen()
+       if n&7 != 0 {
+               return false
+       }
+       n >>= 3
+
+       if n > len(hash) {
+               n = len(hash)
+       }
+       z := new(big.Int).SetBytes(hash[:n])
+
+       u1 := new(big.Int).Mul(z, w)
+       u1.Mod(u1, pub.Q)
+       u2 := w.Mul(r, w)
+       u2.Mod(u2, pub.Q)
+       v := u1.Exp(pub.G, u1, pub.P)
+       u2.Exp(pub.Y, u2, pub.P)
+       v.Mul(v, u2)
+       v.Mod(v, pub.P)
+       v.Mod(v, pub.Q)
+
+       return v.Cmp(r) == 0
+}
diff --git a/libgo/go/crypto/dsa/dsa_test.go b/libgo/go/crypto/dsa/dsa_test.go
new file mode 100644 (file)
index 0000000..deec08d
--- /dev/null
@@ -0,0 +1,84 @@
+// Copyright 2011 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 dsa
+
+import (
+       "big"
+       "crypto/rand"
+       "testing"
+)
+
+func testSignAndVerify(t *testing.T, i int, priv *PrivateKey) {
+       hashed := []byte("testing")
+       r, s, err := Sign(rand.Reader, priv, hashed)
+       if err != nil {
+               t.Errorf("%d: error signing: %s", i, err)
+               return
+       }
+
+       if !Verify(&priv.PublicKey, hashed, r, s) {
+               t.Errorf("%d: Verify failed", i)
+       }
+}
+
+func testParameterGeneration(t *testing.T, sizes ParameterSizes, L, N int) {
+       var priv PrivateKey
+       params := &priv.Parameters
+
+       err := GenerateParameters(params, rand.Reader, sizes)
+       if err != nil {
+               t.Errorf("%d: %s", int(sizes), err)
+               return
+       }
+
+       if params.P.BitLen() != L {
+               t.Errorf("%d: params.BitLen got:%d want:%d", int(sizes), params.P.BitLen(), L)
+       }
+
+       if params.Q.BitLen() != N {
+               t.Errorf("%d: q.BitLen got:%d want:%d", int(sizes), params.Q.BitLen(), L)
+       }
+
+       one := new(big.Int)
+       one.SetInt64(1)
+       pm1 := new(big.Int).Sub(params.P, one)
+       quo, rem := new(big.Int).DivMod(pm1, params.Q, new(big.Int))
+       if rem.Sign() != 0 {
+               t.Errorf("%d: p-1 mod q != 0", int(sizes))
+       }
+       x := new(big.Int).Exp(params.G, quo, params.P)
+       if x.Cmp(one) == 0 {
+               t.Errorf("%d: invalid generator", int(sizes))
+       }
+
+       err = GenerateKey(&priv, rand.Reader)
+       if err != nil {
+               t.Errorf("error generating key: %s", err)
+               return
+       }
+
+       testSignAndVerify(t, int(sizes), &priv)
+}
+
+func TestParameterGeneration(t *testing.T) {
+       // This test is too slow to run all the time.
+       return
+
+       testParameterGeneration(t, L1024N160, 1024, 160)
+       testParameterGeneration(t, L2048N224, 2048, 224)
+       testParameterGeneration(t, L2048N256, 2048, 256)
+       testParameterGeneration(t, L3072N256, 3072, 256)
+}
+
+func TestSignAndVerify(t *testing.T) {
+       var priv PrivateKey
+       priv.P, _ = new(big.Int).SetString("A9B5B793FB4785793D246BAE77E8FF63CA52F442DA763C440259919FE1BC1D6065A9350637A04F75A2F039401D49F08E066C4D275A5A65DA5684BC563C14289D7AB8A67163BFBF79D85972619AD2CFF55AB0EE77A9002B0EF96293BDD0F42685EBB2C66C327079F6C98000FBCB79AACDE1BC6F9D5C7B1A97E3D9D54ED7951FEF", 16)
+       priv.Q, _ = new(big.Int).SetString("E1D3391245933D68A0714ED34BBCB7A1F422B9C1", 16)
+       priv.G, _ = new(big.Int).SetString("634364FC25248933D01D1993ECABD0657CC0CB2CEED7ED2E3E8AECDFCDC4A25C3B15E9E3B163ACA2984B5539181F3EFF1A5E8903D71D5B95DA4F27202B77D2C44B430BB53741A8D59A8F86887525C9F2A6A5980A195EAA7F2FF910064301DEF89D3AA213E1FAC7768D89365318E370AF54A112EFBA9246D9158386BA1B4EEFDA", 16)
+       priv.Y, _ = new(big.Int).SetString("32969E5780CFE1C849A1C276D7AEB4F38A23B591739AA2FE197349AEEBD31366AEE5EB7E6C6DDB7C57D02432B30DB5AA66D9884299FAA72568944E4EEDC92EA3FBC6F39F53412FBCC563208F7C15B737AC8910DBC2D9C9B8C001E72FDC40EB694AB1F06A5A2DBD18D9E36C66F31F566742F11EC0A52E9F7B89355C02FB5D32D2", 16)
+       priv.X, _ = new(big.Int).SetString("5078D4D29795CBE76D3AACFE48C9AF0BCDBEE91A", 16)
+
+       testSignAndVerify(t, 0, &priv)
+}
index e13c986..ee46544 100644 (file)
@@ -6,10 +6,15 @@
 package md4
 
 import (
+       "crypto"
        "hash"
        "os"
 )
 
+func init() {
+       crypto.RegisterHash(crypto.MD4, New)
+}
+
 // The size of an MD4 checksum in bytes.
 const Size = 16
 
index 54fddb6..8f93fc4 100644 (file)
@@ -6,10 +6,15 @@
 package md5
 
 import (
+       "crypto"
        "hash"
        "os"
 )
 
+func init() {
+       crypto.RegisterHash(crypto.MD5, New)
+}
+
 // The size of an MD5 checksum in bytes.
 const Size = 16
 
index f3fa3bc..f42d808 100644 (file)
@@ -9,8 +9,9 @@ package ocsp
 
 import (
        "asn1"
+       "crypto"
        "crypto/rsa"
-       "crypto/sha1"
+       "crypto/sha1"
        "crypto/x509"
        "os"
        "time"
@@ -168,8 +169,8 @@ func ParseResponse(bytes []byte) (*Response, os.Error) {
                return nil, x509.UnsupportedAlgorithmError{}
        }
 
-       h := sha1.New()
-       hashType := rsa.HashSHA1
+       hashType := crypto.SHA1
+       h := hashType.New()
 
        pub := ret.Certificate.PublicKey.(*rsa.PublicKey)
        h.Write(basicResp.TBSResponseData.Raw)
index 97080f6..0c5ae9d 100644 (file)
@@ -112,7 +112,7 @@ func (l *lineReader) Read(p []byte) (n int, err os.Error) {
                return 0, os.EOF
        }
 
-       if len(line) != 64 {
+       if len(line) > 64 {
                return 0, ArmorCorrupt
        }
 
index e4ffd41..9334e94 100644 (file)
@@ -34,7 +34,7 @@ func TestDecodeEncode(t *testing.T) {
                t.Error(err)
        }
 
-       if adler32.Checksum(contents) != 0x789d7f00 {
+       if adler32.Checksum(contents) != 0x27b144be {
                t.Errorf("contents: got: %x", contents)
        }
 
@@ -73,13 +73,11 @@ func TestLongHeader(t *testing.T) {
 const armorExample1 = `-----BEGIN PGP SIGNATURE-----
 Version: GnuPG v1.4.10 (GNU/Linux)
 
-iQEcBAABAgAGBQJMtFESAAoJEKsQXJGvOPsVj40H/1WW6jaMXv4BW+1ueDSMDwM8
-kx1fLOXbVM5/Kn5LStZNt1jWWnpxdz7eq3uiqeCQjmqUoRde3YbB2EMnnwRbAhpp
-cacnAvy9ZQ78OTxUdNW1mhX5bS6q1MTEJnl+DcyigD70HG/yNNQD7sOPMdYQw0TA
-byQBwmLwmTsuZsrYqB68QyLHI+DUugn+kX6Hd2WDB62DKa2suoIUIHQQCd/ofwB3
-WfCYInXQKKOSxu2YOg2Eb4kLNhSMc1i9uKUWAH+sdgJh7NBgdoE4MaNtBFkHXRvv
-okWuf3+xA9ksp1npSY/mDvgHijmjvtpRDe6iUeqfCn8N9u9CBg8geANgaG8+QA4=
-=wfQG
+iJwEAAECAAYFAk1Fv/0ACgkQo01+GMIMMbsYTwQAiAw+QAaNfY6WBdplZ/uMAccm
+4g+81QPmTSGHnetSb6WBiY13kVzK4HQiZH8JSkmmroMLuGeJwsRTEL4wbjRyUKEt
+p1xwUZDECs234F1xiG5enc5SGlRtP7foLBz9lOsjx+LEcA4sTl5/2eZR9zyFZqWW
+TxRjs+fJCIFuo71xb1g=
+=/teI
 -----END PGP SIGNATURE-----`
 
 const armorLongLine = `-----BEGIN PGP SIGNATURE-----
index 410e734..0f7de02 100644 (file)
@@ -116,6 +116,7 @@ func (e *encoding) Close() (err os.Error) {
        if err != nil {
                return
        }
+       e.breaker.Close()
 
        var checksumBytes [3]byte
        checksumBytes[0] = byte(e.crc >> 16)
@@ -144,11 +145,9 @@ func Encode(out io.Writer, blockType string, headers map[string]string) (w io.Wr
                }
        }
 
-       if len(headers) > 0 {
-               _, err := out.Write(newline)
-               if err != nil {
-                       return
-               }
+       _, err = out.Write(newline)
+       if err != nil {
+               return
        }
 
        e := &encoding{
diff --git a/libgo/go/crypto/openpgp/canonical_text.go b/libgo/go/crypto/openpgp/canonical_text.go
new file mode 100644 (file)
index 0000000..293eff3
--- /dev/null
@@ -0,0 +1,58 @@
+// Copyright 2011 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 openpgp
+
+import (
+       "hash"
+       "os"
+)
+
+// NewCanonicalTextHash reformats text written to it into the canonical
+// form and then applies the hash h.  See RFC 4880, section 5.2.1.
+func NewCanonicalTextHash(h hash.Hash) hash.Hash {
+       return &canonicalTextHash{h, 0}
+}
+
+type canonicalTextHash struct {
+       h hash.Hash
+       s int
+}
+
+var newline = []byte{'\r', '\n'}
+
+func (cth *canonicalTextHash) Write(buf []byte) (int, os.Error) {
+       start := 0
+
+       for i, c := range buf {
+               switch cth.s {
+               case 0:
+                       if c == '\r' {
+                               cth.s = 1
+                       } else if c == '\n' {
+                               cth.h.Write(buf[start:i])
+                               cth.h.Write(newline)
+                               start = i + 1
+                       }
+               case 1:
+                       cth.s = 0
+               }
+       }
+
+       cth.h.Write(buf[start:])
+       return len(buf), nil
+}
+
+func (cth *canonicalTextHash) Sum() []byte {
+       return cth.h.Sum()
+}
+
+func (cth *canonicalTextHash) Reset() {
+       cth.h.Reset()
+       cth.s = 0
+}
+
+func (cth *canonicalTextHash) Size() int {
+       return cth.h.Size()
+}
diff --git a/libgo/go/crypto/openpgp/canonical_text_test.go b/libgo/go/crypto/openpgp/canonical_text_test.go
new file mode 100644 (file)
index 0000000..69ecf91
--- /dev/null
@@ -0,0 +1,50 @@
+// Copyright 2011 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 openpgp
+
+import (
+       "bytes"
+       "os"
+       "testing"
+)
+
+type recordingHash struct {
+       buf *bytes.Buffer
+}
+
+func (r recordingHash) Write(b []byte) (n int, err os.Error) {
+       return r.buf.Write(b)
+}
+
+func (r recordingHash) Sum() []byte {
+       return r.buf.Bytes()
+}
+
+func (r recordingHash) Reset() {
+       panic("shouldn't be called")
+}
+
+func (r recordingHash) Size() int {
+       panic("shouldn't be called")
+}
+
+
+func testCanonicalText(t *testing.T, input, expected string) {
+       r := recordingHash{bytes.NewBuffer(nil)}
+       c := NewCanonicalTextHash(r)
+       c.Write([]byte(input))
+       result := c.Sum()
+       if expected != string(result) {
+               t.Errorf("input: %x got: %x want: %x", input, result, expected)
+       }
+}
+
+func TestCanonicalText(t *testing.T) {
+       testCanonicalText(t, "foo\n", "foo\r\n")
+       testCanonicalText(t, "foo", "foo")
+       testCanonicalText(t, "foo\r\n", "foo\r\n")
+       testCanonicalText(t, "foo\r\nbar", "foo\r\nbar")
+       testCanonicalText(t, "foo\r\nbar\n\n", "foo\r\nbar\r\n\r\n")
+}
index 2d80ce3..053d159 100644 (file)
@@ -5,6 +5,10 @@
 // This package contains common error types for the OpenPGP packages.
 package error
 
+import (
+       "strconv"
+)
+
 // A StructuralError is returned when OpenPGP data is found to be syntactically
 // invalid.
 type StructuralError string
@@ -44,3 +48,17 @@ func (ki keyIncorrect) String() string {
 }
 
 var KeyIncorrectError = keyIncorrect(0)
+
+type unknownIssuer int
+
+func (unknownIssuer) String() string {
+       return "signature make by unknown entity"
+}
+
+var UnknownIssuerError = unknownIssuer(0)
+
+type UnknownPacketTypeError uint8
+
+func (upte UnknownPacketTypeError) String() string {
+       return "unknown OpenPGP packet type: " + strconv.Itoa(int(upte))
+}
diff --git a/libgo/go/crypto/openpgp/keys.go b/libgo/go/crypto/openpgp/keys.go
new file mode 100644 (file)
index 0000000..ecaa86f
--- /dev/null
@@ -0,0 +1,280 @@
+// Copyright 2011 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 openpgp
+
+import (
+       "crypto/openpgp/error"
+       "crypto/openpgp/packet"
+       "io"
+       "os"
+)
+
+// PublicKeyType is the armor type for a PGP public key.
+var PublicKeyType = "PGP PUBLIC KEY BLOCK"
+
+// An Entity represents the components of an OpenPGP key: a primary public key
+// (which must be a signing key), one or more identities claimed by that key,
+// and zero or more subkeys, which may be encryption keys.
+type Entity struct {
+       PrimaryKey *packet.PublicKey
+       PrivateKey *packet.PrivateKey
+       Identities map[string]*Identity // indexed by Identity.Name
+       Subkeys    []Subkey
+}
+
+// An Identity represents an identity claimed by an Entity and zero or more
+// assertions by other entities about that claim.
+type Identity struct {
+       Name          string // by convention, has the form "Full Name (comment) <email@example.com>"
+       UserId        *packet.UserId
+       SelfSignature *packet.Signature
+       Signatures    []*packet.Signature
+}
+
+// A Subkey is an additional public key in an Entity. Subkeys can be used for
+// encryption.
+type Subkey struct {
+       PublicKey  *packet.PublicKey
+       PrivateKey *packet.PrivateKey
+       Sig        *packet.Signature
+}
+
+// A Key identifies a specific public key in an Entity. This is either the
+// Entity's primary key or a subkey.
+type Key struct {
+       Entity        *Entity
+       PublicKey     *packet.PublicKey
+       PrivateKey    *packet.PrivateKey
+       SelfSignature *packet.Signature
+}
+
+// A KeyRing provides access to public and private keys.
+type KeyRing interface {
+       // KeysById returns the set of keys that have the given key id.
+       KeysById(id uint64) []Key
+       // DecryptionKeys returns all private keys that are valid for
+       // decryption.
+       DecryptionKeys() []Key
+}
+
+// An EntityList contains one or more Entities.
+type EntityList []*Entity
+
+// KeysById returns the set of keys that have the given key id.
+func (el EntityList) KeysById(id uint64) (keys []Key) {
+       for _, e := range el {
+               if e.PrimaryKey.KeyId == id {
+                       var selfSig *packet.Signature
+                       for _, ident := range e.Identities {
+                               if selfSig == nil {
+                                       selfSig = ident.SelfSignature
+                               } else if ident.SelfSignature.IsPrimaryId != nil && *ident.SelfSignature.IsPrimaryId {
+                                       selfSig = ident.SelfSignature
+                                       break
+                               }
+                       }
+                       keys = append(keys, Key{e, e.PrimaryKey, e.PrivateKey, selfSig})
+               }
+
+               for _, subKey := range e.Subkeys {
+                       if subKey.PublicKey.KeyId == id {
+                               keys = append(keys, Key{e, subKey.PublicKey, subKey.PrivateKey, subKey.Sig})
+                       }
+               }
+       }
+       return
+}
+
+// DecryptionKeys returns all private keys that are valid for decryption.
+func (el EntityList) DecryptionKeys() (keys []Key) {
+       for _, e := range el {
+               for _, subKey := range e.Subkeys {
+                       if subKey.PrivateKey != nil && (!subKey.Sig.FlagsValid || subKey.Sig.FlagEncryptStorage || subKey.Sig.FlagEncryptCommunications) {
+                               keys = append(keys, Key{e, subKey.PublicKey, subKey.PrivateKey, subKey.Sig})
+                       }
+               }
+       }
+       return
+}
+
+// ReadArmoredKeyRing reads one or more public/private keys from an armor keyring file.
+func ReadArmoredKeyRing(r io.Reader) (EntityList, os.Error) {
+       body, err := readArmored(r, PublicKeyType)
+       if err != nil {
+               return nil, err
+       }
+
+       return ReadKeyRing(body)
+}
+
+// ReadKeyRing reads one or more public/private keys, ignoring unsupported keys.
+func ReadKeyRing(r io.Reader) (el EntityList, err os.Error) {
+       packets := packet.NewReader(r)
+
+       for {
+               var e *Entity
+               e, err = readEntity(packets)
+               if err != nil {
+                       if _, ok := err.(error.UnsupportedError); ok {
+                               err = readToNextPublicKey(packets)
+                       }
+                       if err == os.EOF {
+                               err = nil
+                               return
+                       }
+                       if err != nil {
+                               el = nil
+                               return
+                       }
+               } else {
+                       el = append(el, e)
+               }
+       }
+       return
+}
+
+// readToNextPublicKey reads packets until the start of the entity and leaves
+// the first packet of the new entity in the Reader.
+func readToNextPublicKey(packets *packet.Reader) (err os.Error) {
+       var p packet.Packet
+       for {
+               p, err = packets.Next()
+               if err == os.EOF {
+                       return
+               } else if err != nil {
+                       if _, ok := err.(error.UnsupportedError); ok {
+                               err = nil
+                               continue
+                       }
+                       return
+               }
+
+               if pk, ok := p.(*packet.PublicKey); ok && !pk.IsSubkey {
+                       packets.Unread(p)
+                       return
+               }
+       }
+
+       panic("unreachable")
+}
+
+// readEntity reads an entity (public key, identities, subkeys etc) from the
+// given Reader.
+func readEntity(packets *packet.Reader) (*Entity, os.Error) {
+       e := new(Entity)
+       e.Identities = make(map[string]*Identity)
+
+       p, err := packets.Next()
+       if err != nil {
+               return nil, err
+       }
+
+       var ok bool
+       if e.PrimaryKey, ok = p.(*packet.PublicKey); !ok {
+               if e.PrivateKey, ok = p.(*packet.PrivateKey); !ok {
+                       packets.Unread(p)
+                       return nil, error.StructuralError("first packet was not a public/private key")
+               } else {
+                       e.PrimaryKey = &e.PrivateKey.PublicKey
+               }
+       }
+
+       var current *Identity
+EachPacket:
+       for {
+               p, err := packets.Next()
+               if err == os.EOF {
+                       break
+               } else if err != nil {
+                       return nil, err
+               }
+
+               switch pkt := p.(type) {
+               case *packet.UserId:
+                       current = new(Identity)
+                       current.Name = pkt.Id
+                       current.UserId = pkt
+                       e.Identities[pkt.Id] = current
+                       p, err = packets.Next()
+                       if err == os.EOF {
+                               err = io.ErrUnexpectedEOF
+                       }
+                       if err != nil {
+                               if _, ok := err.(error.UnsupportedError); ok {
+                                       return nil, err
+                               }
+                               return nil, error.StructuralError("identity self-signature invalid: " + err.String())
+                       }
+                       current.SelfSignature, ok = p.(*packet.Signature)
+                       if !ok {
+                               return nil, error.StructuralError("user ID packet not followed by self signature")
+                       }
+                       if current.SelfSignature.SigType != packet.SigTypePositiveCert {
+                               return nil, error.StructuralError("user ID self-signature with wrong type")
+                       }
+                       if err = e.PrimaryKey.VerifyUserIdSignature(pkt.Id, current.SelfSignature); err != nil {
+                               return nil, error.StructuralError("user ID self-signature invalid: " + err.String())
+                       }
+               case *packet.Signature:
+                       if current == nil {
+                               return nil, error.StructuralError("signature packet found before user id packet")
+                       }
+                       current.Signatures = append(current.Signatures, pkt)
+               case *packet.PrivateKey:
+                       if pkt.IsSubkey == false {
+                               packets.Unread(p)
+                               break EachPacket
+                       }
+                       err = addSubkey(e, packets, &pkt.PublicKey, pkt)
+                       if err != nil {
+                               return nil, err
+                       }
+               case *packet.PublicKey:
+                       if pkt.IsSubkey == false {
+                               packets.Unread(p)
+                               break EachPacket
+                       }
+                       err = addSubkey(e, packets, pkt, nil)
+                       if err != nil {
+                               return nil, err
+                       }
+               default:
+                       // we ignore unknown packets
+               }
+       }
+
+       if len(e.Identities) == 0 {
+               return nil, error.StructuralError("entity without any identities")
+       }
+
+       return e, nil
+}
+
+func addSubkey(e *Entity, packets *packet.Reader, pub *packet.PublicKey, priv *packet.PrivateKey) os.Error {
+       var subKey Subkey
+       subKey.PublicKey = pub
+       subKey.PrivateKey = priv
+       p, err := packets.Next()
+       if err == os.EOF {
+               return io.ErrUnexpectedEOF
+       }
+       if err != nil {
+               return error.StructuralError("subkey signature invalid: " + err.String())
+       }
+       var ok bool
+       subKey.Sig, ok = p.(*packet.Signature)
+       if !ok {
+               return error.StructuralError("subkey packet not followed by signature")
+       }
+       if subKey.Sig.SigType != packet.SigTypeSubkeyBinding {
+               return error.StructuralError("subkey signature with wrong type")
+       }
+       err = e.PrimaryKey.VerifyKeySignature(subKey.PublicKey, subKey.Sig)
+       if err != nil {
+               return error.StructuralError("subkey signature invalid: " + err.String())
+       }
+       e.Subkeys = append(e.Subkeys, subKey)
+       return nil
+}
diff --git a/libgo/go/crypto/openpgp/packet/compressed.go b/libgo/go/crypto/openpgp/packet/compressed.go
new file mode 100644 (file)
index 0000000..1c15c24
--- /dev/null
@@ -0,0 +1,39 @@
+// Copyright 2011 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 packet
+
+import (
+       "compress/flate"
+       "compress/zlib"
+       "crypto/openpgp/error"
+       "io"
+       "os"
+       "strconv"
+)
+
+// Compressed represents a compressed OpenPGP packet. The decompressed contents
+// will contain more OpenPGP packets. See RFC 4880, section 5.6.
+type Compressed struct {
+       Body io.Reader
+}
+
+func (c *Compressed) parse(r io.Reader) os.Error {
+       var buf [1]byte
+       _, err := readFull(r, buf[:])
+       if err != nil {
+               return err
+       }
+
+       switch buf[0] {
+       case 1:
+               c.Body = flate.NewReader(r)
+       case 2:
+               c.Body, err = zlib.NewReader(r)
+       default:
+               err = error.UnsupportedError("unknown compression algorithm: " + strconv.Itoa(int(buf[0])))
+       }
+
+       return err
+}
diff --git a/libgo/go/crypto/openpgp/packet/compressed_test.go b/libgo/go/crypto/openpgp/packet/compressed_test.go
new file mode 100644 (file)
index 0000000..24fe501
--- /dev/null
@@ -0,0 +1,41 @@
+// Copyright 2011 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 packet
+
+import (
+       "bytes"
+       "encoding/hex"
+       "os"
+       "io/ioutil"
+       "testing"
+)
+
+func TestCompressed(t *testing.T) {
+       packet, err := Read(readerFromHex(compressedHex))
+       if err != nil {
+               t.Errorf("failed to read Compressed: %s", err)
+               return
+       }
+
+       c, ok := packet.(*Compressed)
+       if !ok {
+               t.Error("didn't find Compressed packet")
+               return
+       }
+
+       contents, err := ioutil.ReadAll(c.Body)
+       if err != nil && err != os.EOF {
+               t.Error(err)
+               return
+       }
+
+       expected, _ := hex.DecodeString(compressedExpectedHex)
+       if !bytes.Equal(expected, contents) {
+               t.Errorf("got:%x want:%x", contents, expected)
+       }
+}
+
+const compressedHex = "a3013b2d90c4e02b72e25f727e5e496a5e49b11e1700"
+const compressedExpectedHex = "cb1062004d14c8fe636f6e74656e74732e0a"
diff --git a/libgo/go/crypto/openpgp/packet/encrypted_key.go b/libgo/go/crypto/openpgp/packet/encrypted_key.go
new file mode 100644 (file)
index 0000000..b11a9b8
--- /dev/null
@@ -0,0 +1,66 @@
+// Copyright 2011 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 packet
+
+import (
+       "crypto/openpgp/error"
+       "crypto/rand"
+       "crypto/rsa"
+       "encoding/binary"
+       "io"
+       "os"
+       "strconv"
+)
+
+// EncryptedKey represents a public-key encrypted session key. See RFC 4880,
+// section 5.1.
+type EncryptedKey struct {
+       KeyId      uint64
+       Algo       PublicKeyAlgorithm
+       Encrypted  []byte
+       CipherFunc CipherFunction // only valid after a successful Decrypt
+       Key        []byte         // only valid after a successful Decrypt
+}
+
+func (e *EncryptedKey) parse(r io.Reader) (err os.Error) {
+       var buf [10]byte
+       _, err = readFull(r, buf[:])
+       if err != nil {
+               return
+       }
+       if buf[0] != 3 {
+               return error.UnsupportedError("unknown EncryptedKey version " + strconv.Itoa(int(buf[0])))
+       }
+       e.KeyId = binary.BigEndian.Uint64(buf[1:9])
+       e.Algo = PublicKeyAlgorithm(buf[9])
+       if e.Algo == PubKeyAlgoRSA || e.Algo == PubKeyAlgoRSAEncryptOnly {
+               e.Encrypted, _, err = readMPI(r)
+       }
+       _, err = consumeAll(r)
+       return
+}
+
+// DecryptRSA decrypts an RSA encrypted session key with the given private key.
+func (e *EncryptedKey) DecryptRSA(priv *rsa.PrivateKey) (err os.Error) {
+       if e.Algo != PubKeyAlgoRSA && e.Algo != PubKeyAlgoRSAEncryptOnly {
+               return error.InvalidArgumentError("EncryptedKey not RSA encrypted")
+       }
+       b, err := rsa.DecryptPKCS1v15(rand.Reader, priv, e.Encrypted)
+       if err != nil {
+               return
+       }
+       e.CipherFunc = CipherFunction(b[0])
+       e.Key = b[1 : len(b)-2]
+       expectedChecksum := uint16(b[len(b)-2])<<8 | uint16(b[len(b)-1])
+       var checksum uint16
+       for _, v := range e.Key {
+               checksum += uint16(v)
+       }
+       if checksum != expectedChecksum {
+               return error.StructuralError("EncryptedKey checksum incorrect")
+       }
+
+       return
+}
diff --git a/libgo/go/crypto/openpgp/packet/encrypted_key_test.go b/libgo/go/crypto/openpgp/packet/encrypted_key_test.go
new file mode 100644 (file)
index 0000000..755ae7a
--- /dev/null
@@ -0,0 +1,67 @@
+// Copyright 2011 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 packet
+
+import (
+       "big"
+       "crypto/rsa"
+       "fmt"
+       "testing"
+)
+
+func bigFromBase10(s string) *big.Int {
+       b, ok := new(big.Int).SetString(s, 10)
+       if !ok {
+               panic("bigFromBase10 failed")
+       }
+       return b
+}
+
+func TestEncryptedKey(t *testing.T) {
+       p, err := Read(readerFromHex(encryptedKeyHex))
+       if err != nil {
+               t.Errorf("error from Read: %s", err)
+               return
+       }
+       ek, ok := p.(*EncryptedKey)
+       if !ok {
+               t.Errorf("didn't parse an EncryptedKey, got %#v", p)
+               return
+       }
+
+       if ek.KeyId != 0x2a67d68660df41c7 || ek.Algo != PubKeyAlgoRSA {
+               t.Errorf("unexpected EncryptedKey contents: %#v", ek)
+               return
+       }
+
+       pub := rsa.PublicKey{
+               E: 65537,
+               N: bigFromBase10("115804063926007623305902631768113868327816898845124614648849934718568541074358183759250136204762053879858102352159854352727097033322663029387610959884180306668628526686121021235757016368038585212410610742029286439607686208110250133174279811431933746643015923132833417396844716207301518956640020862630546868823"),
+       }
+
+       priv := &rsa.PrivateKey{
+               PublicKey: pub,
+               D:         bigFromBase10("32355588668219869544751561565313228297765464314098552250409557267371233892496951383426602439009993875125222579159850054973310859166139474359774543943714622292329487391199285040721944491839695981199720170366763547754915493640685849961780092241140181198779299712578774460837139360803883139311171713302987058393"),
+       }
+
+       err = ek.DecryptRSA(priv)
+       if err != nil {
+               t.Errorf("error from DecryptRSA: %s", err)
+               return
+       }
+
+       if ek.CipherFunc != CipherAES256 {
+               t.Errorf("unexpected EncryptedKey contents: %#v", ek)
+               return
+       }
+
+       keyHex := fmt.Sprintf("%x", ek.Key)
+       if keyHex != expectedKeyHex {
+               t.Errorf("bad key, got %s want %x", keyHex, expectedKeyHex)
+       }
+}
+
+const encryptedKeyHex = "c18c032a67d68660df41c70104005789d0de26b6a50c985a02a13131ca829c413a35d0e6fa8d6842599252162808ac7439c72151c8c6183e76923fe3299301414d0c25a2f06a2257db3839e7df0ec964773f6e4c4ac7ff3b48c444237166dd46ba8ff443a5410dc670cb486672fdbe7c9dfafb75b4fea83af3a204fe2a7dfa86bd20122b4f3d2646cbeecb8f7be8"
+const expectedKeyHex = "d930363f7e0308c333b9618617ea728963d8df993665ae7be1092d4926fd864b"
diff --git a/libgo/go/crypto/openpgp/packet/literal.go b/libgo/go/crypto/openpgp/packet/literal.go
new file mode 100644 (file)
index 0000000..04f50e5
--- /dev/null
@@ -0,0 +1,53 @@
+// Copyright 2011 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 packet
+
+import (
+       "encoding/binary"
+       "io"
+       "os"
+)
+
+// LiteralData represents an encrypted file. See RFC 4880, section 5.9.
+type LiteralData struct {
+       IsBinary bool
+       FileName string
+       Time     uint32 // Unix epoch time. Either creation time or modification time. 0 means undefined.
+       Body     io.Reader
+}
+
+// ForEyesOnly returns whether the contents of the LiteralData have been marked
+// as especially sensitive.
+func (l *LiteralData) ForEyesOnly() bool {
+       return l.FileName == "_CONSOLE"
+}
+
+func (l *LiteralData) parse(r io.Reader) (err os.Error) {
+       var buf [256]byte
+
+       _, err = readFull(r, buf[:2])
+       if err != nil {
+               return
+       }
+
+       l.IsBinary = buf[0] == 'b'
+       fileNameLen := int(buf[1])
+
+       _, err = readFull(r, buf[:fileNameLen])
+       if err != nil {
+               return
+       }
+
+       l.FileName = string(buf[:fileNameLen])
+
+       _, err = readFull(r, buf[:4])
+       if err != nil {
+               return
+       }
+
+       l.Time = binary.BigEndian.Uint32(buf[:4])
+       l.Body = r
+       return
+}
diff --git a/libgo/go/crypto/openpgp/packet/one_pass_signature.go b/libgo/go/crypto/openpgp/packet/one_pass_signature.go
new file mode 100644 (file)
index 0000000..acbf58b
--- /dev/null
@@ -0,0 +1,49 @@
+// Copyright 2011 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 packet
+
+import (
+       "crypto"
+       "crypto/openpgp/error"
+       "crypto/openpgp/s2k"
+       "encoding/binary"
+       "io"
+       "os"
+       "strconv"
+)
+
+// OnePassSignature represents a one-pass signature packet. See RFC 4880,
+// section 5.4.
+type OnePassSignature struct {
+       SigType    SignatureType
+       Hash       crypto.Hash
+       PubKeyAlgo PublicKeyAlgorithm
+       KeyId      uint64
+       IsLast     bool
+}
+
+func (ops *OnePassSignature) parse(r io.Reader) (err os.Error) {
+       var buf [13]byte
+
+       _, err = readFull(r, buf[:])
+       if err != nil {
+               return
+       }
+       if buf[0] != 3 {
+               err = error.UnsupportedError("one-pass-signature packet version " + strconv.Itoa(int(buf[0])))
+       }
+
+       var ok bool
+       ops.Hash, ok = s2k.HashIdToHash(buf[2])
+       if !ok {
+               return error.UnsupportedError("hash function: " + strconv.Itoa(int(buf[2])))
+       }
+
+       ops.SigType = SignatureType(buf[1])
+       ops.PubKeyAlgo = PublicKeyAlgorithm(buf[3])
+       ops.KeyId = binary.BigEndian.Uint64(buf[4:12])
+       ops.IsLast = buf[12] != 0
+       return
+}
diff --git a/libgo/go/crypto/openpgp/packet/packet.go b/libgo/go/crypto/openpgp/packet/packet.go
new file mode 100644 (file)
index 0000000..269603b
--- /dev/null
@@ -0,0 +1,395 @@
+// Copyright 2011 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 parsing and serialisation of OpenPGP packets, as
+// specified in RFC 4880.
+package packet
+
+import (
+       "crypto/aes"
+       "crypto/cast5"
+       "crypto/cipher"
+       "crypto/openpgp/error"
+       "io"
+       "os"
+)
+
+// readFull is the same as io.ReadFull except that reading zero bytes returns
+// ErrUnexpectedEOF rather than EOF.
+func readFull(r io.Reader, buf []byte) (n int, err os.Error) {
+       n, err = io.ReadFull(r, buf)
+       if err == os.EOF {
+               err = io.ErrUnexpectedEOF
+       }
+       return
+}
+
+// readLength reads an OpenPGP length from r. See RFC 4880, section 4.2.2.
+func readLength(r io.Reader) (length int64, isPartial bool, err os.Error) {
+       var buf [4]byte
+       _, err = readFull(r, buf[:1])
+       if err != nil {
+               return
+       }
+       switch {
+       case buf[0] < 192:
+               length = int64(buf[0])
+       case buf[0] < 224:
+               length = int64(buf[0]-192) << 8
+               _, err = readFull(r, buf[0:1])
+               if err != nil {
+                       return
+               }
+               length += int64(buf[0]) + 192
+       case buf[0] < 255:
+               length = int64(1) << (buf[0] & 0x1f)
+               isPartial = true
+       default:
+               _, err = readFull(r, buf[0:4])
+               if err != nil {
+                       return
+               }
+               length = int64(buf[0])<<24 |
+                       int64(buf[1])<<16 |
+                       int64(buf[2])<<8 |
+                       int64(buf[3])
+       }
+       return
+}
+
+// partialLengthReader wraps an io.Reader and handles OpenPGP partial lengths.
+// The continuation lengths are parsed and removed from the stream and EOF is
+// returned at the end of the packet. See RFC 4880, section 4.2.2.4.
+type partialLengthReader struct {
+       r         io.Reader
+       remaining int64
+       isPartial bool
+}
+
+func (r *partialLengthReader) Read(p []byte) (n int, err os.Error) {
+       for r.remaining == 0 {
+               if !r.isPartial {
+                       return 0, os.EOF
+               }
+               r.remaining, r.isPartial, err = readLength(r.r)
+               if err != nil {
+                       return 0, err
+               }
+       }
+
+       toRead := int64(len(p))
+       if toRead > r.remaining {
+               toRead = r.remaining
+       }
+
+       n, err = r.r.Read(p[:int(toRead)])
+       r.remaining -= int64(n)
+       if n < int(toRead) && err == os.EOF {
+               err = io.ErrUnexpectedEOF
+       }
+       return
+}
+
+// A spanReader is an io.LimitReader, but it returns ErrUnexpectedEOF if the
+// underlying Reader returns EOF before the limit has been reached.
+type spanReader struct {
+       r io.Reader
+       n int64
+}
+
+func (l *spanReader) Read(p []byte) (n int, err os.Error) {
+       if l.n <= 0 {
+               return 0, os.EOF
+       }
+       if int64(len(p)) > l.n {
+               p = p[0:l.n]
+       }
+       n, err = l.r.Read(p)
+       l.n -= int64(n)
+       if l.n > 0 && err == os.EOF {
+               err = io.ErrUnexpectedEOF
+       }
+       return
+}
+
+// readHeader parses a packet header and returns an io.Reader which will return
+// the contents of the packet. See RFC 4880, section 4.2.
+func readHeader(r io.Reader) (tag packetType, length int64, contents io.Reader, err os.Error) {
+       var buf [4]byte
+       _, err = io.ReadFull(r, buf[:1])
+       if err != nil {
+               return
+       }
+       if buf[0]&0x80 == 0 {
+               err = error.StructuralError("tag byte does not have MSB set")
+               return
+       }
+       if buf[0]&0x40 == 0 {
+               // Old format packet
+               tag = packetType((buf[0] & 0x3f) >> 2)
+               lengthType := buf[0] & 3
+               if lengthType == 3 {
+                       length = -1
+                       contents = r
+                       return
+               }
+               lengthBytes := 1 << lengthType
+               _, err = readFull(r, buf[0:lengthBytes])
+               if err != nil {
+                       return
+               }
+               for i := 0; i < lengthBytes; i++ {
+                       length <<= 8
+                       length |= int64(buf[i])
+               }
+               contents = &spanReader{r, length}
+               return
+       }
+
+       // New format packet
+       tag = packetType(buf[0] & 0x3f)
+       length, isPartial, err := readLength(r)
+       if err != nil {
+               return
+       }
+       if isPartial {
+               contents = &partialLengthReader{
+                       remaining: length,
+                       isPartial: true,
+                       r:         r,
+               }
+               length = -1
+       } else {
+               contents = &spanReader{r, length}
+       }
+       return
+}
+
+// serialiseHeader writes an OpenPGP packet header to w. See RFC 4880, section
+// 4.2.
+func serialiseHeader(w io.Writer, ptype packetType, length int) (err os.Error) {
+       var buf [5]byte
+       var n int
+
+       buf[0] = 0x80 | 0x40 | byte(ptype)
+       if length < 192 {
+               buf[1] = byte(length)
+               n = 2
+       } else if length < 8384 {
+               length -= 192
+               buf[1] = byte(length >> 8)
+               buf[2] = byte(length)
+               n = 3
+       } else {
+               buf[0] = 255
+               buf[1] = byte(length >> 24)
+               buf[2] = byte(length >> 16)
+               buf[3] = byte(length >> 8)
+               buf[4] = byte(length)
+               n = 5
+       }
+
+       _, err = w.Write(buf[:n])
+       return
+}
+
+// Packet represents an OpenPGP packet. Users are expected to try casting
+// instances of this interface to specific packet types.
+type Packet interface {
+       parse(io.Reader) os.Error
+}
+
+// consumeAll reads from the given Reader until error, returning the number of
+// bytes read.
+func consumeAll(r io.Reader) (n int64, err os.Error) {
+       var m int
+       var buf [1024]byte
+
+       for {
+               m, err = r.Read(buf[:])
+               n += int64(m)
+               if err == os.EOF {
+                       err = nil
+                       return
+               }
+               if err != nil {
+                       return
+               }
+       }
+
+       panic("unreachable")
+}
+
+// packetType represents the numeric ids of the different OpenPGP packet types. See
+// http://www.iana.org/assignments/pgp-parameters/pgp-parameters.xhtml#pgp-parameters-2
+type packetType uint8
+
+const (
+       packetTypeEncryptedKey              packetType = 1
+       packetTypeSignature                 packetType = 2
+       packetTypeSymmetricKeyEncrypted     packetType = 3
+       packetTypeOnePassSignature          packetType = 4
+       packetTypePrivateKey                packetType = 5
+       packetTypePublicKey                 packetType = 6
+       packetTypePrivateSubkey             packetType = 7
+       packetTypeCompressed                packetType = 8
+       packetTypeSymmetricallyEncrypted    packetType = 9
+       packetTypeLiteralData               packetType = 11
+       packetTypeUserId                    packetType = 13
+       packetTypePublicSubkey              packetType = 14
+       packetTypeSymmetricallyEncryptedMDC packetType = 18
+)
+
+// Read reads a single OpenPGP packet from the given io.Reader. If there is an
+// error parsing a packet, the whole packet is consumed from the input.
+func Read(r io.Reader) (p Packet, err os.Error) {
+       tag, _, contents, err := readHeader(r)
+       if err != nil {
+               return
+       }
+
+       switch tag {
+       case packetTypeEncryptedKey:
+               p = new(EncryptedKey)
+       case packetTypeSignature:
+               p = new(Signature)
+       case packetTypeSymmetricKeyEncrypted:
+               p = new(SymmetricKeyEncrypted)
+       case packetTypeOnePassSignature:
+               p = new(OnePassSignature)
+       case packetTypePrivateKey, packetTypePrivateSubkey:
+               pk := new(PrivateKey)
+               if tag == packetTypePrivateSubkey {
+                       pk.IsSubkey = true
+               }
+               p = pk
+       case packetTypePublicKey, packetTypePublicSubkey:
+               pk := new(PublicKey)
+               if tag == packetTypePublicSubkey {
+                       pk.IsSubkey = true
+               }
+               p = pk
+       case packetTypeCompressed:
+               p = new(Compressed)
+       case packetTypeSymmetricallyEncrypted:
+               p = new(SymmetricallyEncrypted)
+       case packetTypeLiteralData:
+               p = new(LiteralData)
+       case packetTypeUserId:
+               p = new(UserId)
+       case packetTypeSymmetricallyEncryptedMDC:
+               se := new(SymmetricallyEncrypted)
+               se.MDC = true
+               p = se
+       default:
+               err = error.UnknownPacketTypeError(tag)
+       }
+       if p != nil {
+               err = p.parse(contents)
+       }
+       if err != nil {
+               consumeAll(contents)
+       }
+       return
+}
+
+// SignatureType represents the different semantic meanings of an OpenPGP
+// signature. See RFC 4880, section 5.2.1.
+type SignatureType uint8
+
+const (
+       SigTypeBinary        SignatureType = 0
+       SigTypeText          = 1
+       SigTypeGenericCert   = 0x10
+       SigTypePersonaCert   = 0x11
+       SigTypeCasualCert    = 0x12
+       SigTypePositiveCert  = 0x13
+       SigTypeSubkeyBinding = 0x18
+)
+
+// PublicKeyAlgorithm represents the different public key system specified for
+// OpenPGP. See
+// http://www.iana.org/assignments/pgp-parameters/pgp-parameters.xhtml#pgp-parameters-12
+type PublicKeyAlgorithm uint8
+
+const (
+       PubKeyAlgoRSA            PublicKeyAlgorithm = 1
+       PubKeyAlgoRSAEncryptOnly PublicKeyAlgorithm = 2
+       PubKeyAlgoRSASignOnly    PublicKeyAlgorithm = 3
+       PubKeyAlgoElgamal        PublicKeyAlgorithm = 16
+       PubKeyAlgoDSA            PublicKeyAlgorithm = 17
+)
+
+// CipherFunction represents the different block ciphers specified for OpenPGP. See
+// http://www.iana.org/assignments/pgp-parameters/pgp-parameters.xhtml#pgp-parameters-13
+type CipherFunction uint8
+
+const (
+       CipherCAST5  = 3
+       CipherAES128 = 7
+       CipherAES192 = 8
+       CipherAES256 = 9
+)
+
+// keySize returns the key size, in bytes, of cipher.
+func (cipher CipherFunction) keySize() int {
+       switch cipher {
+       case CipherCAST5:
+               return cast5.KeySize
+       case CipherAES128:
+               return 16
+       case CipherAES192:
+               return 24
+       case CipherAES256:
+               return 32
+       }
+       return 0
+}
+
+// blockSize returns the block size, in bytes, of cipher.
+func (cipher CipherFunction) blockSize() int {
+       switch cipher {
+       case CipherCAST5:
+               return 8
+       case CipherAES128, CipherAES192, CipherAES256:
+               return 16
+       }
+       return 0
+}
+
+// new returns a fresh instance of the given cipher.
+func (cipher CipherFunction) new(key []byte) (block cipher.Block) {
+       switch cipher {
+       case CipherCAST5:
+               block, _ = cast5.NewCipher(key)
+       case CipherAES128, CipherAES192, CipherAES256:
+               block, _ = aes.NewCipher(key)
+       }
+       return
+}
+
+// readMPI reads a big integer from r. The bit length returned is the bit
+// length that was specified in r. This is preserved so that the integer can be
+// reserialised exactly.
+func readMPI(r io.Reader) (mpi []byte, bitLength uint16, err os.Error) {
+       var buf [2]byte
+       _, err = readFull(r, buf[0:])
+       if err != nil {
+               return
+       }
+       bitLength = uint16(buf[0])<<8 | uint16(buf[1])
+       numBytes := (int(bitLength) + 7) / 8
+       mpi = make([]byte, numBytes)
+       _, err = readFull(r, mpi)
+       return
+}
+
+// writeMPI serialises a big integer to r.
+func writeMPI(w io.Writer, bitLength uint16, mpiBytes []byte) (err os.Error) {
+       _, err = w.Write([]byte{byte(bitLength >> 8), byte(bitLength)})
+       if err == nil {
+               _, err = w.Write(mpiBytes)
+       }
+       return
+}
diff --git a/libgo/go/crypto/openpgp/packet/packet_test.go b/libgo/go/crypto/openpgp/packet/packet_test.go
new file mode 100644 (file)
index 0000000..6789d2a
--- /dev/null
@@ -0,0 +1,192 @@
+// Copyright 2011 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 packet
+
+import (
+       "bytes"
+       "crypto/openpgp/error"
+       "encoding/hex"
+       "fmt"
+       "io"
+       "io/ioutil"
+       "os"
+       "testing"
+)
+
+func TestReadFull(t *testing.T) {
+       var out [4]byte
+
+       b := bytes.NewBufferString("foo")
+       n, err := readFull(b, out[:3])
+       if n != 3 || err != nil {
+               t.Errorf("full read failed n:%d err:%s", n, err)
+       }
+
+       b = bytes.NewBufferString("foo")
+       n, err = readFull(b, out[:4])
+       if n != 3 || err != io.ErrUnexpectedEOF {
+               t.Errorf("partial read failed n:%d err:%s", n, err)
+       }
+
+       b = bytes.NewBuffer(nil)
+       n, err = readFull(b, out[:3])
+       if n != 0 || err != io.ErrUnexpectedEOF {
+               t.Errorf("empty read failed n:%d err:%s", n, err)
+       }
+}
+
+func readerFromHex(s string) io.Reader {
+       data, err := hex.DecodeString(s)
+       if err != nil {
+               panic("readerFromHex: bad input")
+       }
+       return bytes.NewBuffer(data)
+}
+
+var readLengthTests = []struct {
+       hexInput  string
+       length    int64
+       isPartial bool
+       err       os.Error
+}{
+       {"", 0, false, io.ErrUnexpectedEOF},
+       {"1f", 31, false, nil},
+       {"c0", 0, false, io.ErrUnexpectedEOF},
+       {"c101", 256 + 1 + 192, false, nil},
+       {"e0", 1, true, nil},
+       {"e1", 2, true, nil},
+       {"e2", 4, true, nil},
+       {"ff", 0, false, io.ErrUnexpectedEOF},
+       {"ff00", 0, false, io.ErrUnexpectedEOF},
+       {"ff0000", 0, false, io.ErrUnexpectedEOF},
+       {"ff000000", 0, false, io.ErrUnexpectedEOF},
+       {"ff00000000", 0, false, nil},
+       {"ff01020304", 16909060, false, nil},
+}
+
+func TestReadLength(t *testing.T) {
+       for i, test := range readLengthTests {
+               length, isPartial, err := readLength(readerFromHex(test.hexInput))
+               if test.err != nil {
+                       if err != test.err {
+                               t.Errorf("%d: expected different error got:%s want:%s", i, err, test.err)
+                       }
+                       continue
+               }
+               if err != nil {
+                       t.Errorf("%d: unexpected error: %s", i, err)
+                       continue
+               }
+               if length != test.length || isPartial != test.isPartial {
+                       t.Errorf("%d: bad result got:(%d,%t) want:(%d,%t)", i, length, isPartial, test.length, test.isPartial)
+               }
+       }
+}
+
+var partialLengthReaderTests = []struct {
+       hexInput  string
+       err       os.Error
+       hexOutput string
+}{
+       {"e0", io.ErrUnexpectedEOF, ""},
+       {"e001", io.ErrUnexpectedEOF, ""},
+       {"e0010102", nil, "0102"},
+       {"ff00000000", nil, ""},
+       {"e10102e1030400", nil, "01020304"},
+       {"e101", io.ErrUnexpectedEOF, ""},
+}
+
+func TestPartialLengthReader(t *testing.T) {
+       for i, test := range partialLengthReaderTests {
+               r := &partialLengthReader{readerFromHex(test.hexInput), 0, true}
+               out, err := ioutil.ReadAll(r)
+               if test.err != nil {
+                       if err != test.err {
+                               t.Errorf("%d: expected different error got:%s want:%s", i, err, test.err)
+                       }
+                       continue
+               }
+               if err != nil {
+                       t.Errorf("%d: unexpected error: %s", i, err)
+                       continue
+               }
+
+               got := fmt.Sprintf("%x", out)
+               if got != test.hexOutput {
+                       t.Errorf("%d: got:%s want:%s", i, test.hexOutput, got)
+               }
+       }
+}
+
+var readHeaderTests = []struct {
+       hexInput        string
+       structuralError bool
+       unexpectedEOF   bool
+       tag             int
+       length          int64
+       hexOutput       string
+}{
+       {"", false, false, 0, 0, ""},
+       {"7f", true, false, 0, 0, ""},
+
+       // Old format headers
+       {"80", false, true, 0, 0, ""},
+       {"8001", false, true, 0, 1, ""},
+       {"800102", false, false, 0, 1, "02"},
+       {"81000102", false, false, 0, 1, "02"},
+       {"820000000102", false, false, 0, 1, "02"},
+       {"860000000102", false, false, 1, 1, "02"},
+       {"83010203", false, false, 0, -1, "010203"},
+
+       // New format headers
+       {"c0", false, true, 0, 0, ""},
+       {"c000", false, false, 0, 0, ""},
+       {"c00102", false, false, 0, 1, "02"},
+       {"c0020203", false, false, 0, 2, "0203"},
+       {"c00202", false, true, 0, 2, ""},
+       {"c3020203", false, false, 3, 2, "0203"},
+}
+
+func TestReadHeader(t *testing.T) {
+       for i, test := range readHeaderTests {
+               tag, length, contents, err := readHeader(readerFromHex(test.hexInput))
+               if test.structuralError {
+                       if _, ok := err.(error.StructuralError); ok {
+                               continue
+                       }
+                       t.Errorf("%d: expected StructuralError, got:%s", i, err)
+                       continue
+               }
+               if err != nil {
+                       if len(test.hexInput) == 0 && e