rlp: add functions for encoding

I'm reasonably confident that the encoding matches the output of
ethutil.Encode for values that it supports. Some of the tests have been
adpated from the Ethereum testing repository.

There are still TODOs in the code.

6 files changed, 860 insertions, 17 deletions

diff --git a/rlp/decode.go b/rlp/decode.go
index a2bd04285..972e662c2 100644
--- a/rlp/decode.go
+++ b/rlp/decode.go
@@ -329,15 +329,9 @@ type field struct {
 }
 
 func makeStructDecoder(typ reflect.Type) (decoder, error) {
-	var fields []field
-	for i := 0; i < typ.NumField(); i++ {
-		if f := typ.Field(i); f.PkgPath == "" { // exported
-			info, err := cachedTypeInfo1(f.Type)
-			if err != nil {
-				return nil, err
-			}
-			fields = append(fields, field{i, info})
-		}
+	fields, err := structFields(typ)
+	if err != nil {
+		return nil, err
 	}
 	dec := func(s *Stream, val reflect.Value) (err error) {
 		if _, err = s.List(); err != nil {
diff --git a/rlp/decode_test.go b/rlp/decode_test.go
index 18ea63a09..35d8dc1fc 100644
--- a/rlp/decode_test.go
+++ b/rlp/decode_test.go
@@ -509,7 +509,7 @@ func ExampleStream() {
 }
 
 func BenchmarkDecode(b *testing.B) {
-	enc := encTest(90000)
+	enc := encodeTestSlice(90000)
 	b.SetBytes(int64(len(enc)))
 	b.ReportAllocs()
 	b.ResetTimer()
@@ -524,7 +524,7 @@ func BenchmarkDecode(b *testing.B) {
 }
 
 func BenchmarkDecodeIntSliceReuse(b *testing.B) {
-	enc := encTest(100000)
+	enc := encodeTestSlice(100000)
 	b.SetBytes(int64(len(enc)))
 	b.ReportAllocs()
 	b.ResetTimer()
@@ -538,7 +538,7 @@ func BenchmarkDecodeIntSliceReuse(b *testing.B) {
 	}
 }
 
-func encTest(n int) []byte {
+func encodeTestSlice(n int) []byte {
 	s := make([]interface{}, n)
 	for i := 0; i < n; i++ {
 		s[i] = i
diff --git a/rlp/encode.go b/rlp/encode.go
new file mode 100644
index 000000000..689d25dd8
--- /dev/null
+++ b/rlp/encode.go
@@ -0,0 +1,532 @@
+package rlp
+
+import (
+	"fmt"
+	"io"
+	"math/big"
+	"reflect"
+)
+
+// TODO: put encbufs in a sync.Pool.
+//     Doing that requires zeroing the buffers after use.
+//     encReader will need to drop it's buffer when done.
+
+var (
+	// Common encoded values.
+	// These are useful when implementing EncodeRLP.
+	EmptyString = []byte{0x80}
+	EmptyList   = []byte{0xC0}
+)
+
+// Encoder is implemented by types that require custom
+// encoding rules or want to encode private fields.
+type Encoder interface {
+	// EncodeRLP should write the RLP encoding of its receiver to w.
+	// If the implementation is a pointer method, it may also be
+	// called for nil pointers.
+	//
+	// Implementations should generate valid RLP. The data written is
+	// not verified at the moment, but a future version might. It is
+	// recommended to write only a single value but writing multiple
+	// values or no value at all is also permitted.
+	EncodeRLP(io.Writer) error
+}
+
+// Encode writes the RLP encoding of val to w. Note that Encode may
+// perform many small writes in some cases. Consider making w
+// buffered.
+//
+// Encode uses the following type-dependent encoding rules:
+//
+// If the type implements the Encoder interface, Encode calls
+// EncodeRLP. This is true even for nil pointers, please see the
+// documentation for Encoder.
+//
+// To encode a pointer, the value being pointed to is encoded. For nil
+// pointers, Encode will encode the zero value of the type. A nil
+// pointer to a struct type always encodes as an empty RLP list.
+//
+// Struct values are encoded as an RLP list of all their encoded
+// public fields. Recursive struct types are supported.
+//
+// To encode slices and arrays, the elements are encoded as an RLP
+// list of the value's elements. Note that arrays and slices with
+// element type uint8 or byte are always encoded as an RLP string.
+//
+// A Go string is encoded as an RLP string.
+//
+// An unsigned integer value is encoded as an RLP string. Zero always
+// encodes as an empty RLP string. Encode also supports *big.Int.
+//
+// An interface value encodes as the value contained in the interface.
+//
+// Boolean values are not supported, nor are signed integers, floating
+// point numbers, maps, channels and functions.
+func Encode(w io.Writer, val interface{}) error {
+	if outer, ok := w.(*encbuf); ok {
+		// Encode was called by some type's EncodeRLP.
+		// Avoid copying by writing to the outer encbuf directly.
+		return outer.encode(val)
+	}
+	eb := newencbuf()
+	if err := eb.encode(val); err != nil {
+		return err
+	}
+	return eb.toWriter(w)
+}
+
+// EncodeBytes returns the RLP encoding of val.
+// Please see the documentation of Encode for the encoding rules.
+func EncodeToBytes(val interface{}) ([]byte, error) {
+	eb := newencbuf()
+	if err := eb.encode(val); err != nil {
+		return nil, err
+	}
+	return eb.toBytes(), nil
+}
+
+// EncodeReader returns a reader from which the RLP encoding of val
+// can be read. The returned size is the total size of the encoded
+// data.
+//
+// Please see the documentation of Encode for the encoding rules.
+func EncodeToReader(val interface{}) (size int, r io.Reader, err error) {
+	eb := newencbuf()
+	if err := eb.encode(val); err != nil {
+		return 0, nil, err
+	}
+	return eb.size(), &encReader{buf: eb}, nil
+}
+
+type encbuf struct {
+	str     []byte      // string data, contains everything except list headers
+	lheads  []*listhead // all list headers
+	lhsize  int         // sum of sizes of all encoded list headers
+	sizebuf []byte      // 9-byte auxiliary buffer for uint encoding
+}
+
+type listhead struct {
+	offset int // index of this header in string data
+	size   int // total size of encoded data (including list headers)
+}
+
+// encode writes head to the given buffer, which must be at least
+// 9 bytes long. It returns the encoded bytes.
+func (head *listhead) encode(buf []byte) []byte {
+	if head.size < 56 {
+		buf[0] = 0xC0 + byte(head.size)
+		return buf[:1]
+	} else {
+		sizesize := putint(buf[1:], uint64(head.size))
+		buf[0] = 0xF7 + byte(sizesize)
+		return buf[:sizesize+1]
+	}
+}
+
+func newencbuf() *encbuf {
+	return &encbuf{sizebuf: make([]byte, 9)}
+}
+
+// encbuf implements io.Writer so it can be passed it into EncodeRLP.
+func (w *encbuf) Write(b []byte) (int, error) {
+	w.str = append(w.str, b...)
+	return len(b), nil
+}
+
+func (w *encbuf) encode(val interface{}) error {
+	rval := reflect.ValueOf(val)
+	ti, err := cachedTypeInfo(rval.Type())
+	if err != nil {
+		return err
+	}
+	return ti.writer(rval, w)
+}
+
+func (w *encbuf) encodeStringHeader(size int) {
+	if size < 56 {
+		w.str = append(w.str, 0x80+byte(size))
+	} else {
+		// TODO: encode to w.str directly
+		sizesize := putint(w.sizebuf[1:], uint64(size))
+		w.sizebuf[0] = 0xB7 + byte(sizesize)
+		w.str = append(w.str, w.sizebuf[:sizesize+1]...)
+	}
+}
+
+func (w *encbuf) encodeString(b []byte) {
+	w.encodeStringHeader(len(b))
+	w.str = append(w.str, b...)
+}
+
+func (w *encbuf) list() *listhead {
+	lh := &listhead{offset: len(w.str), size: w.lhsize}
+	w.lheads = append(w.lheads, lh)
+	return lh
+}
+
+func (w *encbuf) listEnd(lh *listhead) {
+	lh.size = w.size() - lh.offset - lh.size
+	if lh.size < 56 {
+		w.lhsize += 1 // length encoded into kind tag
+	} else {
+		w.lhsize += 1 + intsize(uint64(lh.size))
+	}
+}
+
+func (w *encbuf) size() int {
+	return len(w.str) + w.lhsize
+}
+
+func (w *encbuf) toBytes() []byte {
+	out := make([]byte, w.size())
+	strpos := 0
+	pos := 0
+	for _, head := range w.lheads {
+		// write string data before header
+		n := copy(out[pos:], w.str[strpos:head.offset])
+		pos += n
+		strpos += n
+		// write the header
+		enc := head.encode(out[pos:])
+		pos += len(enc)
+	}
+	// copy string data after the last list header
+	copy(out[pos:], w.str[strpos:])
+	return out
+}
+
+func (w *encbuf) toWriter(out io.Writer) (err error) {
+	strpos := 0
+	for _, head := range w.lheads {
+		// write string data before header
+		if head.offset-strpos > 0 {
+			n, err := out.Write(w.str[strpos:head.offset])
+			strpos += n
+			if err != nil {
+				return err
+			}
+		}
+		// write the header
+		enc := head.encode(w.sizebuf)
+		if _, err = out.Write(enc); err != nil {
+			return err
+		}
+	}
+	if strpos < len(w.str) {
+		// write string data after the last list header
+		_, err = out.Write(w.str[strpos:])
+	}
+	return err
+}
+
+// encReader is the io.Reader returned by EncodeToReader.
+// It releases its encbuf at EOF.
+type encReader struct {
+	buf    *encbuf // the buffer we're reading from. this is nil when we're at EOF.
+	lhpos  int     // index of list header that we're reading
+	strpos int     // current position in string buffer
+	piece  []byte  // next piece to be read
+}
+
+func (r *encReader) Read(b []byte) (n int, err error) {
+	for {
+		if r.piece = r.next(); r.piece == nil {
+			return n, io.EOF
+		}
+		nn := copy(b[n:], r.piece)
+		n += nn
+		if nn < len(r.piece) {
+			// piece didn't fit, see you next time.
+			r.piece = r.piece[nn:]
+			return n, nil
+		}
+		r.piece = nil
+	}
+	panic("not reached")
+}
+
+// next returns the next piece of data to be read.
+// it returns nil at EOF.
+func (r *encReader) next() []byte {
+	switch {
+	case r.piece != nil:
+		// There is still data available for reading.
+		return r.piece
+
+	case r.lhpos < len(r.buf.lheads):
+		// We're before the last list header.
+		head := r.buf.lheads[r.lhpos]
+		sizebefore := head.offset - r.strpos
+		if sizebefore > 0 {
+			// String data before header.
+			p := r.buf.str[r.strpos:head.offset]
+			r.strpos += sizebefore
+			return p
+		} else {
+			r.lhpos++
+			return head.encode(r.buf.sizebuf)
+		}
+
+	case r.strpos < len(r.buf.str):
+		// String data at the end, after all list headers.
+		p := r.buf.str[r.strpos:]
+		r.strpos = len(r.buf.str)
+		return p
+
+	default:
+		return nil
+	}
+}
+
+var (
+	encoderInterface = reflect.TypeOf(new(Encoder)).Elem()
+	emptyInterface   = reflect.TypeOf(new(interface{})).Elem()
+	big0             = big.NewInt(0)
+)
+
+// makeWriter creates a writer function for the given type.
+func makeWriter(typ reflect.Type) (writer, error) {
+	kind := typ.Kind()
+	switch {
+	case typ.Implements(encoderInterface):
+		return writeEncoder, nil
+	case kind != reflect.Ptr && reflect.PtrTo(typ).Implements(encoderInterface):
+		return writeEncoderNoPtr, nil
+	case typ == emptyInterface:
+		return writeInterface, nil
+	case typ.AssignableTo(reflect.PtrTo(bigInt)):
+		return writeBigIntPtr, nil
+	case typ.AssignableTo(bigInt):
+		return writeBigIntNoPtr, nil
+	case isUint(kind):
+		return writeUint, nil
+	case kind == reflect.String:
+		return writeString, nil
+	case kind == reflect.Slice && typ.Elem().Kind() == reflect.Uint8 && !typ.Elem().Implements(encoderInterface):
+		return writeBytes, nil
+	case kind == reflect.Slice || kind == reflect.Array:
+		return makeSliceWriter(typ)
+	case kind == reflect.Struct:
+		return makeStructWriter(typ)
+	case kind == reflect.Ptr:
+		return makePtrWriter(typ)
+	default:
+		return nil, fmt.Errorf("rlp: type %v is not RLP-serializable", typ)
+	}
+}
+
+func writeUint(val reflect.Value, w *encbuf) error {
+	i := val.Uint()
+	if i == 0 {
+		w.str = append(w.str, 0x80)
+	} else if i < 128 {
+		// fits single byte
+		w.str = append(w.str, byte(i))
+	} else {
+		// TODO: encode int to w.str directly
+		s := putint(w.sizebuf[1:], i)
+		w.sizebuf[0] = 0x80 + byte(s)
+		w.str = append(w.str, w.sizebuf[:s+1]...)
+	}
+	return nil
+}
+
+func writeBigIntPtr(val reflect.Value, w *encbuf) error {
+	return writeBigInt(val.Interface().(*big.Int), w)
+}
+
+func writeBigIntNoPtr(val reflect.Value, w *encbuf) error {
+	i := val.Interface().(big.Int)
+	return writeBigInt(&i, w)
+}
+
+func writeBigInt(i *big.Int, w *encbuf) error {
+	if cmp := i.Cmp(big0); cmp == -1 {
+		return fmt.Errorf("rlp: cannot encode negative *big.Int")
+	} else if cmp == 0 {
+		w.str = append(w.str, 0x80)
+	} else if bits := i.BitLen(); bits < 8 {
+		// fits single byte
+		w.str = append(w.str, byte(i.Uint64()))
+	} else {
+		w.encodeString(i.Bytes())
+	}
+	return nil
+}
+
+func writeBytes(val reflect.Value, w *encbuf) error {
+	w.encodeString(val.Bytes())
+	return nil
+}
+
+func writeString(val reflect.Value, w *encbuf) error {
+	s := val.String()
+	w.encodeStringHeader(len(s))
+	w.str = append(w.str, s...)
+	return nil
+}
+
+func writeEncoder(val reflect.Value, w *encbuf) error {
+	return val.Interface().(Encoder).EncodeRLP(w)
+}
+
+// writeEncoderNoPtr handles non-pointer values that implement Encoder
+// with a pointer receiver.
+func writeEncoderNoPtr(val reflect.Value, w *encbuf) error {
+	if !val.CanAddr() {
+		// We can't get the address. It would be possible make the
+		// value addressable by creating a shallow copy, but this
+		// creates other problems so we're not doing it (yet).
+		//
+		// package json simply doesn't call MarshalJSON for cases like
+		// this, but encodes the value as if it didn't implement the
+		// interface. We don't want to handle it that way.
+		return fmt.Errorf("rlp: game over: unadressable value of type %v, EncodeRLP is pointer method", val.Type())
+	}
+	return val.Addr().Interface().(Encoder).EncodeRLP(w)
+}
+
+func writeInterface(val reflect.Value, w *encbuf) error {
+	if val.IsNil() {
+		// Write empty list. This is consistent with the previous RLP
+		// encoder that we had and should therefore avoid any
+		// problems.
+		w.str = append(w.str, 0xC0)
+		return nil
+	}
+	eval := val.Elem()
+	ti, err := cachedTypeInfo(eval.Type())
+	if err != nil {
+		return err
+	}
+	return ti.writer(eval, w)
+}
+
+func makeSliceWriter(typ reflect.Type) (writer, error) {
+	etypeinfo, err := cachedTypeInfo1(typ.Elem())
+	if err != nil {
+		return nil, err
+	}
+	writer := func(val reflect.Value, w *encbuf) error {
+		lh := w.list()
+		vlen := val.Len()
+		for i := 0; i < vlen; i++ {
+			if err := etypeinfo.writer(val.Index(i), w); err != nil {
+				return err
+			}
+		}
+		w.listEnd(lh)
+		return nil
+	}
+	return writer, nil
+}
+
+func makeStructWriter(typ reflect.Type) (writer, error) {
+	fields, err := structFields(typ)
+	if err != nil {
+		return nil, err
+	}
+	writer := func(val reflect.Value, w *encbuf) error {
+		lh := w.list()
+		for _, f := range fields {
+			if err := f.info.writer(val.Field(f.index), w); err != nil {
+				return err
+			}
+		}
+		w.listEnd(lh)
+		return nil
+	}
+	return writer, nil
+}
+
+func makePtrWriter(typ reflect.Type) (writer, error) {
+	etypeinfo, err := cachedTypeInfo1(typ.Elem())
+	if err != nil {
+		return nil, err
+	}
+	zero := reflect.Zero(typ.Elem())
+	kind := typ.Elem().Kind()
+	writer := func(val reflect.Value, w *encbuf) error {
+		switch {
+		case !val.IsNil():
+			return etypeinfo.writer(val.Elem(), w)
+		case kind == reflect.Struct:
+			// encoding the zero value of a struct could trigger
+			// infinite recursion, avoid that.
+			w.listEnd(w.list())
+			return nil
+		default:
+			return etypeinfo.writer(zero, w)
+		}
+	}
+	return writer, err
+}
+
+// putint writes i to the beginning of b in with big endian byte
+// order, using the least number of bytes needed to represent i.
+func putint(b []byte, i uint64) (size int) {
+	switch {
+	case i < (1 << 8):
+		b[0] = byte(i)
+		return 1
+	case i < (1 << 16):
+		b[0] = byte(i >> 8)
+		b[1] = byte(i)
+		return 2
+	case i < (1 << 24):
+		b[0] = byte(i >> 16)
+		b[1] = byte(i >> 8)
+		b[2] = byte(i)
+		return 3
+	case i < (1 << 32):
+		b[0] = byte(i >> 24)
+		b[1] = byte(i >> 16)
+		b[2] = byte(i >> 8)
+		b[3] = byte(i)
+		return 4
+	case i < (1 << 40):
+		b[0] = byte(i >> 32)
+		b[1] = byte(i >> 24)
+		b[2] = byte(i >> 16)
+		b[3] = byte(i >> 8)
+		b[4] = byte(i)
+		return 5
+	case i < (1 << 48):
+		b[0] = byte(i >> 40)
+		b[1] = byte(i >> 32)
+		b[2] = byte(i >> 24)
+		b[3] = byte(i >> 16)
+		b[4] = byte(i >> 8)
+		b[5] = byte(i)
+		return 6
+	case i < (1 << 56):
+		b[0] = byte(i >> 48)
+		b[1] = byte(i >> 40)
+		b[2] = byte(i >> 32)
+		b[3] = byte(i >> 24)
+		b[4] = byte(i >> 16)
+		b[5] = byte(i >> 8)
+		b[6] = byte(i)
+		return 7
+	default:
+		b[0] = byte(i >> 56)
+		b[1] = byte(i >> 48)
+		b[2] = byte(i >> 40)
+		b[3] = byte(i >> 32)
+		b[4] = byte(i >> 24)
+		b[5] = byte(i >> 16)
+		b[6] = byte(i >> 8)
+		b[7] = byte(i)
+		return 8
+	}
+}
+
+// intsize computes the minimum number of bytes required to store i.
+func intsize(i uint64) (size int) {
+	for size = 1; ; size++ {
+		if i >>= 8; i == 0 {
+			return size
+		}
+	}
+	panic("not reached")
+}
diff --git a/rlp/encode_test.go b/rlp/encode_test.go
new file mode 100644
index 000000000..8dba3671b
--- /dev/null
+++ b/rlp/encode_test.go
@@ -0,0 +1,260 @@
+package rlp
+
+import (
+	"bytes"
+	"errors"
+	"fmt"
+	"io"
+	"io/ioutil"
+	"math/big"
+	"testing"
+)
+
+type testEncoder struct {
+	err error
+}
+
+func (e *testEncoder) EncodeRLP(w io.Writer) error {
+	if e == nil {
+		w.Write([]byte{0, 0, 0, 0})
+	} else if e.err != nil {
+		return e.err
+	} else {
+		w.Write([]byte{0, 1, 0, 1, 0, 1, 0, 1, 0, 1})
+	}
+	return nil
+}
+
+type byteEncoder byte
+
+func (e byteEncoder) EncodeRLP(w io.Writer) error {
+	w.Write(EmptyList)
+	return nil
+}
+
+var (
+	_ = Encoder(&testEncoder{})
+	_ = Encoder(byteEncoder(0))
+)
+
+type encTest struct {
+	val           interface{}
+	output, error string
+}
+
+var encTests = []encTest{
+	// integers
+	{val: uint32(0), output: "80"},
+	{val: uint32(127), output: "7F"},
+	{val: uint32(128), output: "8180"},
+	{val: uint32(256), output: "820100"},
+	{val: uint32(1024), output: "820400"},
+	{val: uint32(0xFFFFFF), output: "83FFFFFF"},
+	{val: uint32(0xFFFFFFFF), output: "84FFFFFFFF"},
+	{val: uint64(0xFFFFFFFF), output: "84FFFFFFFF"},
+	{val: uint64(0xFFFFFFFFFF), output: "85FFFFFFFFFF"},
+	{val: uint64(0xFFFFFFFFFFFF), output: "86FFFFFFFFFFFF"},
+	{val: uint64(0xFFFFFFFFFFFFFF), output: "87FFFFFFFFFFFFFF"},
+	{val: uint64(0xFFFFFFFFFFFFFFFF), output: "88FFFFFFFFFFFFFFFF"},
+
+	// big integers (should match uint for small values)
+	{val: big.NewInt(0), output: "80"},
+	{val: big.NewInt(1), output: "01"},
+	{val: big.NewInt(127), output: "7F"},
+	{val: big.NewInt(128), output: "8180"},
+	{val: big.NewInt(256), output: "820100"},
+	{val: big.NewInt(1024), output: "820400"},
+	{val: big.NewInt(0xFFFFFF), output: "83FFFFFF"},
+	{val: big.NewInt(0xFFFFFFFF), output: "84FFFFFFFF"},
+	{val: big.NewInt(0xFFFFFFFFFF), output: "85FFFFFFFFFF"},
+	{val: big.NewInt(0xFFFFFFFFFFFF), output: "86FFFFFFFFFFFF"},
+	{val: big.NewInt(0xFFFFFFFFFFFFFF), output: "87FFFFFFFFFFFFFF"},
+	{
+		val:    big.NewInt(0).SetBytes(unhex("102030405060708090A0B0C0D0E0F2")),
+		output: "8F102030405060708090A0B0C0D0E0F2",
+	},
+	{
+		val:    big.NewInt(0).SetBytes(unhex("0100020003000400050006000700080009000A000B000C000D000E01")),
+		output: "9C0100020003000400050006000700080009000A000B000C000D000E01",
+	},
+	{
+		val:    big.NewInt(0).SetBytes(unhex("010000000000000000000000000000000000000000000000000000000000000000")),
+		output: "A1010000000000000000000000000000000000000000000000000000000000000000",
+	},
+
+	// non-pointer big.Int
+	{val: *big.NewInt(0), output: "80"},
+	{val: *big.NewInt(0xFFFFFF), output: "83FFFFFF"},
+
+	// negative ints are not supported
+	{val: big.NewInt(-1), error: "rlp: cannot encode negative *big.Int"},
+
+	// byte slices, strings
+	{val: []byte{}, output: "80"},
+	{val: []byte{1, 2, 3}, output: "83010203"},
+	{val: "", output: "80"},
+	{val: "dog", output: "83646F67"},
+	{
+		val:    "Lorem ipsum dolor sit amet, consectetur adipisicing eli",
+		output: "B74C6F72656D20697073756D20646F6C6F722073697420616D65742C20636F6E7365637465747572206164697069736963696E6720656C69",
+	},
+	{
+		val:    "Lorem ipsum dolor sit amet, consectetur adipisicing elit",
+		output: "B8384C6F72656D20697073756D20646F6C6F722073697420616D65742C20636F6E7365637465747572206164697069736963696E6720656C6974",
+	},
+	{
+		val:    "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Curabitur mauris magna, suscipit sed vehicula non, iaculis faucibus tortor. Proin suscipit ultricies malesuada. Duis tortor elit, dictum quis tristique eu, ultrices at risus. Morbi a est imperdiet mi ullamcorper aliquet suscipit nec lorem. Aenean quis leo mollis, vulputate elit varius, consequat enim. Nulla ultrices turpis justo, et posuere urna consectetur nec. Proin non convallis metus. Donec tempor ipsum in mauris congue sollicitudin. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia Curae; Suspendisse convallis sem vel massa faucibus, eget lacinia lacus tempor. Nulla quis ultricies purus. Proin auctor rhoncus nibh condimentum mollis. Aliquam consequat enim at metus luctus, a eleifend purus egestas. Curabitur at nibh metus. Nam bibendum, neque at auctor tristique, lorem libero aliquet arcu, non interdum tellus lectus sit amet eros. Cras rhoncus, metus ac ornare cursus, dolor justo ultrices metus, at ullamcorper volutpat",
+		output: "B904004C6F72656D20697073756D20646F6C6F722073697420616D65742C20636F6E73656374657475722061646970697363696E6720656C69742E20437572616269747572206D6175726973206D61676E612C20737573636970697420736564207665686963756C61206E6F6E2C20696163756C697320666175636962757320746F72746F722E2050726F696E20737573636970697420756C74726963696573206D616C6573756164612E204475697320746F72746F7220656C69742C2064696374756D2071756973207472697374697175652065752C20756C7472696365732061742072697375732E204D6F72626920612065737420696D70657264696574206D6920756C6C616D636F7270657220616C6971756574207375736369706974206E6563206C6F72656D2E2041656E65616E2071756973206C656F206D6F6C6C69732C2076756C70757461746520656C6974207661726975732C20636F6E73657175617420656E696D2E204E756C6C6120756C74726963657320747572706973206A7573746F2C20657420706F73756572652075726E6120636F6E7365637465747572206E65632E2050726F696E206E6F6E20636F6E76616C6C6973206D657475732E20446F6E65632074656D706F7220697073756D20696E206D617572697320636F6E67756520736F6C6C696369747564696E2E20566573746962756C756D20616E746520697073756D207072696D697320696E206661756369627573206F726369206C756374757320657420756C74726963657320706F737565726520637562696C69612043757261653B2053757370656E646973736520636F6E76616C6C69732073656D2076656C206D617373612066617563696275732C2065676574206C6163696E6961206C616375732074656D706F722E204E756C6C61207175697320756C747269636965732070757275732E2050726F696E20617563746F722072686F6E637573206E69626820636F6E64696D656E74756D206D6F6C6C69732E20416C697175616D20636F6E73657175617420656E696D206174206D65747573206C75637475732C206120656C656966656E6420707572757320656765737461732E20437572616269747572206174206E696268206D657475732E204E616D20626962656E64756D2C206E6571756520617420617563746F72207472697374697175652C206C6F72656D206C696265726F20616C697175657420617263752C206E6F6E20696E74657264756D2074656C6C7573206C65637475732073697420616D65742065726F732E20437261732072686F6E6375732C206D65747573206163206F726E617265206375727375732C20646F6C6F72206A7573746F20756C747269636573206D657475732C20617420756C6C616D636F7270657220766F6C7574706174",
+	},
+
+	// slices
+	{val: []uint{}, output: "C0"},
+	{val: []uint{1, 2, 3}, output: "C3010203"},
+	{
+		// [ [], [[]], [ [], [[]] ] ]
+		val:    []interface{}{[]interface{}{}, [][]interface{}{{}}, []interface{}{[]interface{}{}, [][]interface{}{{}}}},
+		output: "C7C0C1C0C3C0C1C0",
+	},
+	{
+		val:    []string{"aaa", "bbb", "ccc", "ddd", "eee", "fff", "ggg", "hhh", "iii", "jjj", "kkk", "lll", "mmm", "nnn", "ooo"},
+		output: "F83C836161618362626283636363836464648365656583666666836767678368686883696969836A6A6A836B6B6B836C6C6C836D6D6D836E6E6E836F6F6F",
+	},
+	{
+		val:    []interface{}{uint(1), uint(0xFFFFFF), []interface{}{[]uint{4, 5, 5}}, "abc"},
+		output: "CE0183FFFFFFC4C304050583616263",
+	},
+	{
+		val: [][]string{
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+			{"asdf", "qwer", "zxcv"},
+		},
+		output: "F90200CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376CF84617364668471776572847A786376",
+	},
+
+	// structs
+	{val: simplestruct{}, output: "C28080"},
+	{val: simplestruct{A: 3, B: "foo"}, output: "C50383666F6F"},
+	{val: &recstruct{5, nil}, output: "C205C0"},
+	{val: &recstruct{5, &recstruct{4, &recstruct{3, nil}}}, output: "C605C404C203C0"},
+
+	// nil
+	{val: (*uint)(nil), output: "80"},
+	{val: (*string)(nil), output: "80"},
+	{val: (*[]byte)(nil), output: "80"},
+	{val: (*[]string)(nil), output: "C0"},
+	{val: (*[]interface{})(nil), output: "C0"},
+	{val: (*[]struct{ uint })(nil), output: "C0"},
+	{val: (*interface{})(nil), output: "C0"},
+
+	// Encoder
+	{val: (*testEncoder)(nil), output: "00000000"},
+	{val: &testEncoder{}, output: "00010001000100010001"},
+	{val: &testEncoder{errors.New("test error")}, error: "test error"},
+	// verify that pointer method testEncoder.EncodeRLP is called for
+	// addressable non-pointer values.
+	{val: &struct{ TE testEncoder }{testEncoder{}}, output: "CA00010001000100010001"},
+	{val: &struct{ TE testEncoder }{testEncoder{errors.New("test error")}}, error: "test error"},
+	// verify the error for non-addressable non-pointer Encoder
+	{val: testEncoder{}, error: "rlp: game over: unadressable value of type rlp.testEncoder, EncodeRLP is pointer method"},
+	// verify the special case for []byte
+	{val: []byteEncoder{0, 1, 2, 3, 4}, output: "C5C0C0C0C0C0"},
+}
+
+func runEncTests(t *testing.T, f func(val interface{}) ([]byte, error)) {
+	for i, test := range encTests {
+		output, err := f(test.val)
+		if err != nil && test.error == "" {
+			t.Errorf("test %d: unexpected error: %v\nvalue %#v\ntype %T",
+				i, err, test.val, test.val)
+			continue
+		}
+		if test.error != "" && fmt.Sprint(err) != test.error {
+			t.Errorf("test %d: error mismatch\ngot   %v\nwant  %v\nvalue %#v\ntype  %T",
+				i, err, test.error, test.val, test.val)
+			continue
+		}
+		if err == nil && !bytes.Equal(output, unhex(test.output)) {
+			t.Errorf("test %d: output mismatch:\ngot   %X\nwant  %s\nvalue %#v\ntype  %T",
+				i, output, test.output, test.val, test.val)
+		}
+	}
+}
+
+func TestEncode(t *testing.T) {
+	runEncTests(t, func(val interface{}) ([]byte, error) {
+		b := new(bytes.Buffer)
+		err := Encode(b, val)
+		return b.Bytes(), err
+	})
+}
+
+func TestEncodeToBytes(t *testing.T) {
+	runEncTests(t, EncodeToBytes)
+}
+
+func TestEncodeToReader(t *testing.T) {
+	runEncTests(t, func(val interface{}) ([]byte, error) {
+		_, r, err := EncodeToReader(val)
+		if err != nil {
+			return nil, err
+		}
+		return ioutil.ReadAll(r)
+	})
+}
+
+func TestEncodeToReaderPiecewise(t *testing.T) {
+	runEncTests(t, func(val interface{}) ([]byte, error) {
+		size, r, err := EncodeToReader(val)
+		if err != nil {
+			return nil, err
+		}
+
+		// read output piecewise
+		output := make([]byte, size)
+		for start, end := 0, 0; start < size; start = end {
+			if remaining := size - start; remaining < 3 {
+				end += remaining
+			} else {
+				end = start + 3
+			}
+			n, err := r.Read(output[start:end])
+			end = start + n
+			if err == io.EOF {
+				break
+			} else if err != nil {
+				return nil, err
+			}
+		}
+		return output, nil
+	})
+}
diff --git a/rlp/encoder_example_test.go b/rlp/encoder_example_test.go
new file mode 100644
index 000000000..57bad604d
--- /dev/null
+++ b/rlp/encoder_example_test.go
@@ -0,0 +1,38 @@
+package rlp
+
+import (
+	"fmt"
+	"io"
+)
+
+type MyCoolType struct {
+	Name string
+	a, b uint
+}
+
+// EncodeRLP writes x as RLP list [a, b] that omits the Name field.
+func (x *MyCoolType) EncodeRLP(w io.Writer) (err error) {
+	// Note: the receiver can be a nil pointer. This allows you to
+	// control the encoding of nil, but it also means that you have to
+	// check for a nil receiver.
+	if x == nil {
+		err = Encode(w, []uint{0, 0})
+	} else {
+		err = Encode(w, []uint{x.a, x.b})
+	}
+	return err
+}
+
+func ExampleEncoder() {
+	var t *MyCoolType // t is nil pointer to MyCoolType
+	bytes, _ := EncodeToBytes(t)
+	fmt.Printf("%v → %X\n", t, bytes)
+
+	t = &MyCoolType{Name: "foobar", a: 5, b: 6}
+	bytes, _ = EncodeToBytes(t)
+	fmt.Printf("%v → %X\n", t, bytes)
+
+	// Output:
+	// <nil> → C28080
+	// &{foobar 5 6} → C20506
+}
diff --git a/rlp/typecache.go b/rlp/typecache.go
index 52e68a3c5..398f25d90 100644
--- a/rlp/typecache.go
+++ b/rlp/typecache.go
@@ -5,16 +5,19 @@ import (
 	"sync"
 )
 
-type decoder func(*Stream, reflect.Value) error
+var (
+	typeCacheMutex sync.RWMutex
+	typeCache      = make(map[reflect.Type]*typeinfo)
+)
 
 type typeinfo struct {
 	decoder
+	writer
 }
 
-var (
-	typeCacheMutex sync.RWMutex
-	typeCache      = make(map[reflect.Type]*typeinfo)
-)
+type decoder func(*Stream, reflect.Value) error
+
+type writer func(reflect.Value, *encbuf) error
 
 func cachedTypeInfo(typ reflect.Type) (*typeinfo, error) {
 	typeCacheMutex.RLock()
@@ -49,11 +52,27 @@ func cachedTypeInfo1(typ reflect.Type) (*typeinfo, error) {
 	return typeCache[typ], err
 }
 
+func structFields(typ reflect.Type) (fields []field, err error) {
+	for i := 0; i < typ.NumField(); i++ {
+		if f := typ.Field(i); f.PkgPath == "" { // exported
+			info, err := cachedTypeInfo1(f.Type)
+			if err != nil {
+				return nil, err
+			}
+			fields = append(fields, field{i, info})
+		}
+	}
+	return fields, nil
+}
+
 func genTypeInfo(typ reflect.Type) (info *typeinfo, err error) {
 	info = new(typeinfo)
 	if info.decoder, err = makeDecoder(typ); err != nil {
 		return nil, err
 	}
+	if info.writer, err = makeWriter(typ); err != nil {
+		return nil, err
+	}
 	return info, nil
 }