proto/decode.go - platform/external/golang-protobuf - Gitiles

 // Go support for Protocol Buffers - Google's data interchange format
 //
 // Copyright 2010 Google Inc.  All rights reserved.
 // http://code.google.com/p/goprotobuf/
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 // copyright notice, this list of conditions and the following disclaimer
 // in the documentation and/or other materials provided with the
 // distribution.
 //     * Neither the name of Google Inc. nor the names of its
 // contributors may be used to endorse or promote products derived from
 // this software without specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 package proto

 /*
  * Routines for decoding protocol buffer data to construct in-memory representations.
  */

 import (
 	"bytes"
 	"fmt"
 	"io"
 	"os"
 	"reflect"
 	"runtime"
 	"unsafe"
 )

 // ErrWrongType occurs when the wire encoding for the field disagrees with
 // that specified in the type being decoded.  This is usually caused by attempting
 // to convert an encoded protocol buffer into a struct of the wrong type.
 var ErrWrongType = os.NewError("field/encoding mismatch: wrong type for field")

 // The fundamental decoders that interpret bytes on the wire.
 // Those that take integer types all return uint64 and are
 // therefore of type valueDecoder.

 // DecodeVarint reads a varint-encoded integer from the slice.
 // It returns the integer and the number of bytes consumed, or
 // zero if there is not enough.
 // This is the format for the
 // int32, int64, uint32, uint64, bool, and enum
 // protocol buffer types.
 func DecodeVarint(buf []byte) (x uint64, n int) {
 	// x, n already 0
 	for shift := uint(0); ; shift += 7 {
 		if n >= len(buf) {
 			return 0, 0
 		}
 		b := uint64(buf[n])
 		n++
 		x |= (b & 0x7F) << shift
 		if (b & 0x80) == 0 {
 			break
 		}
 	}
 	return x, n
 }

 // DecodeVarint reads a varint-encoded integer from the Buffer.
 // This is the format for the
 // int32, int64, uint32, uint64, bool, and enum
 // protocol buffer types.
 func (p *Buffer) DecodeVarint() (x uint64, err os.Error) {
 	// x, err already 0

 	i := p.index
 	l := len(p.buf)

 	for shift := uint(0); ; shift += 7 {
 		if i >= l {
 			err = io.ErrUnexpectedEOF
 			return
 		}
 		b := p.buf[i]
 		i++
 		x |= (uint64(b) & 0x7F) << shift
 		if b < 0x80 {
 			break
 		}
 	}
 	p.index = i
 	return
 }

 // DecodeFixed64 reads a 64-bit integer from the Buffer.
 // This is the format for the
 // fixed64, sfixed64, and double protocol buffer types.
 func (p *Buffer) DecodeFixed64() (x uint64, err os.Error) {
 	// x, err already 0
 	i := p.index + 8
 	if i > len(p.buf) {
 		err = io.ErrUnexpectedEOF
 		return
 	}
 	p.index = i

 	x = uint64(p.buf[i-8])
 	x |= uint64(p.buf[i-7]) << 8
 	x |= uint64(p.buf[i-6]) << 16
 	x |= uint64(p.buf[i-5]) << 24
 	x |= uint64(p.buf[i-4]) << 32
 	x |= uint64(p.buf[i-3]) << 40
 	x |= uint64(p.buf[i-2]) << 48
 	x |= uint64(p.buf[i-1]) << 56
 	return
 }

 // DecodeFixed32 reads a 32-bit integer from the Buffer.
 // This is the format for the
 // fixed32, sfixed32, and float protocol buffer types.
 func (p *Buffer) DecodeFixed32() (x uint64, err os.Error) {
 	// x, err already 0
 	i := p.index + 4
 	if i > len(p.buf) {
 		err = io.ErrUnexpectedEOF
 		return
 	}
 	p.index = i

 	x = uint64(p.buf[i-4])
 	x |= uint64(p.buf[i-3]) << 8
 	x |= uint64(p.buf[i-2]) << 16
 	x |= uint64(p.buf[i-1]) << 24
 	return
 }

 // DecodeZigzag64 reads a zigzag-encoded 64-bit integer
 // from the Buffer.
 // This is the format used for the sint64 protocol buffer type.
 func (p *Buffer) DecodeZigzag64() (x uint64, err os.Error) {
 	x, err = p.DecodeVarint()
 	if err != nil {
 		return
 	}
 	x = (x >> 1) ^ uint64((int64(x&1)<<63)>>63)
 	return
 }

 // DecodeZigzag32 reads a zigzag-encoded 32-bit integer
 // from  the Buffer.
 // This is the format used for the sint32 protocol buffer type.
 func (p *Buffer) DecodeZigzag32() (x uint64, err os.Error) {
 	x, err = p.DecodeVarint()
 	if err != nil {
 		return
 	}
 	x = uint64((uint32(x) >> 1) ^ uint32((int32(x&1)<<31)>>31))
 	return
 }

 // These are not ValueDecoders: they produce an array of bytes or a string.
 // bytes, embedded messages

 // DecodeRawBytes reads a count-delimited byte buffer from the Buffer.
 // This is the format used for the bytes protocol buffer
 // type and for embedded messages.
 func (p *Buffer) DecodeRawBytes(alloc bool) (buf []byte, err os.Error) {
 	n, err := p.DecodeVarint()
 	if err != nil {
 		return
 	}

 	nb := int(n)
 	if p.index+nb > len(p.buf) {
 		err = io.ErrUnexpectedEOF
 		return
 	}

 	if !alloc {
 		// todo: check if can get more uses of alloc=false
 		buf = p.buf[p.index : p.index+nb]
 		p.index += nb
 		return
 	}

 	buf = make([]byte, nb)
 	copy(buf, p.buf[p.index:])
 	p.index += nb
 	return
 }

 // DecodeStringBytes reads an encoded string from the Buffer.
 // This is the format used for the proto2 string type.
 func (p *Buffer) DecodeStringBytes() (s string, err os.Error) {
 	buf, err := p.DecodeRawBytes(false)
 	if err != nil {
 		return
 	}
 	return string(buf), nil
 }

 // Skip the next item in the buffer. Its wire type is decoded and presented as an argument.
 // If the protocol buffer has extensions, and the field matches, add it as an extension.
 // Otherwise, if the XXX_unrecognized field exists, append the skipped data there.
 func (o *Buffer) skipAndSave(t *reflect.StructType, tag, wire int, base uintptr) os.Error {

 	oi := o.index

 	err := o.skip(t, tag, wire)
 	if err != nil {
 		return err
 	}

 	x := fieldIndex(t, "XXX_unrecognized")
 	if x == nil {
 		return nil
 	}

 	p := propByIndex(t, x)
 	ptr := (*[]byte)(unsafe.Pointer(base + p.offset))

 	if *ptr == nil {
 		// This is the first skipped element,
 		// allocate a new buffer.
 		*ptr = o.bufalloc()
 	}

 	// Add the skipped field to struct field
 	obuf := o.buf

 	o.buf = *ptr
 	o.EncodeVarint(uint64(tag<<3 | wire))
 	*ptr = bytes.Add(o.buf, obuf[oi:o.index])

 	o.buf = obuf

 	return nil
 }

 // Skip the next item in the buffer. Its wire type is decoded and presented as an argument.
 func (o *Buffer) skip(t *reflect.StructType, tag, wire int) os.Error {

 	var u uint64
 	var err os.Error

 	switch wire {
 	case WireVarint:
 		_, err = o.DecodeVarint()
 	case WireFixed64:
 		_, err = o.DecodeFixed64()
 	case WireBytes:
 		_, err = o.DecodeRawBytes(false)
 	case WireFixed32:
 		_, err = o.DecodeFixed32()
 	case WireStartGroup:
 		for {
 			u, err = o.DecodeVarint()
 			if err != nil {
 				break
 			}
 			fwire := int(u & 0x7)
 			if fwire == WireEndGroup {
 				break
 			}
 			ftag := int(u >> 3)
 			err = o.skip(t, ftag, fwire)
 			if err != nil {
 				break
 			}
 		}
 	default:
 		fmt.Fprintf(os.Stderr, "proto: can't skip wire type %d for %s\n", wire, t)
 	}
 	return err
 }

 // Unmarshaler is the interface representing objects that can unmarshal themselves.
 type Unmarshaler interface {
 	Unmarshal([]byte) os.Error
 }

 // Unmarshal parses the protocol buffer representation in buf and places the
 // decoded result in pb.  If the struct underlying pb does not match
 // the data in buf, the results can be unpredictable.
 func Unmarshal(buf []byte, pb interface{}) os.Error {
 	// If the object can unmarshal itself, let it.
 	if u, ok := pb.(Unmarshaler); ok {
 		return u.Unmarshal(buf)
 	}

 	return NewBuffer(buf).Unmarshal(pb)
 }

 // Unmarshal parses the protocol buffer representation in the
 // Buffer and places the decoded result in pb.  If the struct
 // underlying pb does not match the data in the buffer, the results can be
 // unpredictable.
 func (p *Buffer) Unmarshal(pb interface{}) os.Error {
 	// If the object can unmarshal itself, let it.
 	if u, ok := pb.(Unmarshaler); ok {
 		err := u.Unmarshal(p.buf[p.index:])
 		p.index = len(p.buf)
 		return err
 	}

 	mstat := runtime.MemStats.Mallocs

 	typ, base, err := getbase(pb)
 	if err != nil {
 		return err
 	}

 	err = p.unmarshalType(typ, false, base)

 	mstat = runtime.MemStats.Mallocs - mstat
 	stats.Dmalloc += mstat
 	stats.Decode++

 	return err
 }

 // unmarshalType does the work of unmarshaling a structure.
 func (o *Buffer) unmarshalType(t *reflect.PtrType, is_group bool, base uintptr) os.Error {
 	st := t.Elem().(*reflect.StructType)
 	prop := GetProperties(st)
 	sbase := getsbase(prop) // scratch area for data items

 	var err os.Error
 	for err == nil && o.index < len(o.buf) {
 		oi := o.index
 		var u uint64
 		u, err = o.DecodeVarint()
 		if err != nil {
 			break
 		}
 		wire := int(u & 0x7)
 		if wire == WireEndGroup {
 			if is_group {
 				return nil // input is satisfied
 			}
 			return ErrWrongType
 		}
 		tag := int(u >> 3)
 		fieldnum, ok := prop.tags[tag]
 		if !ok {
 			// Maybe it's an extension?
 			o.ptr = base
 			iv := unsafe.Unreflect(t, unsafe.Pointer(&o.ptr))
 			if e, ok := iv.(extendableProto); ok && isExtensionField(e, int32(tag)) {
 				if err = o.skip(st, tag, wire); err == nil {
 					e.ExtensionMap()[int32(tag)] = bytes.Add(nil, o.buf[oi:o.index])
 				}
 				continue
 			}
 			err = o.skipAndSave(st, tag, wire, base)
 			continue
 		}
 		p := prop.Prop[fieldnum]

 		if p.dec != nil {
 			if wire != WireStartGroup && wire != p.WireType {
 				err = ErrWrongType
 				continue
 			}
 			err = p.dec(o, p, base, sbase)
 			continue
 		}

 		fmt.Fprintf(os.Stderr, "no protobuf decoder for %s.%s\n", t, st.Field(fieldnum).Name)
 	}
 	if err == nil && is_group {
 		return io.ErrUnexpectedEOF
 	}
 	return err
 }

 // Make *pslice have base address base, length 0, and capacity startSize.
 func initSlice(pslice unsafe.Pointer, base uintptr) {
 	sp := (*reflect.SliceHeader)(pslice)
 	sp.Data = base
 	sp.Len = 0
 	sp.Cap = startSize
 }

 // Individual type decoders
 // For each,
 //	u is the decoded value,
 //	v is a pointer to the field (pointer) in the struct
 //	x is a pointer to the preallocated scratch space to hold the decoded value.

 // Decode a bool.
 func (o *Buffer) dec_bool(p *Properties, base uintptr, sbase uintptr) os.Error {
 	u, err := p.valDec(o)
 	if err != nil {
 		return err
 	}
 	v := (**uint8)(unsafe.Pointer(base + p.offset))
 	x := (*uint8)(unsafe.Pointer(sbase + p.scratch))
 	*x = uint8(u)
 	*v = x
 	return nil
 }

 // Decode an int32.
 func (o *Buffer) dec_int32(p *Properties, base uintptr, sbase uintptr) os.Error {
 	u, err := p.valDec(o)
 	if err != nil {
 		return err
 	}
 	v := (**int32)(unsafe.Pointer(base + p.offset))
 	x := (*int32)(unsafe.Pointer(sbase + p.scratch))
 	*x = int32(u)
 	*v = x
 	return nil
 }

 // Decode an int64.
 func (o *Buffer) dec_int64(p *Properties, base uintptr, sbase uintptr) os.Error {
 	u, err := p.valDec(o)
 	if err != nil {
 		return err
 	}
 	v := (**int64)(unsafe.Pointer(base + p.offset))
 	x := (*int64)(unsafe.Pointer(sbase + p.scratch))
 	*x = int64(u)
 	*v = x
 	return nil
 }

 // Decode a string.
 func (o *Buffer) dec_string(p *Properties, base uintptr, sbase uintptr) os.Error {
 	s, err := o.DecodeStringBytes()
 	if err != nil {
 		return err
 	}
 	v := (**string)(unsafe.Pointer(base + p.offset))
 	x := (*string)(unsafe.Pointer(sbase + p.scratch))
 	*x = s
 	*v = x
 	return nil
 }

 // Decode a slice of bytes ([]byte).
 func (o *Buffer) dec_slice_byte(p *Properties, base uintptr, sbase uintptr) os.Error {
 	b, err := o.DecodeRawBytes(false)
 	if err != nil {
 		return err
 	}
 	lb := len(b)
 	if lb == 0 {
 		return nil
 	}
 	x := (*[]uint8)(unsafe.Pointer(base + p.offset))

 	y := *x
 	c := cap(y)
 	if c == 0 {
 		initSlice(unsafe.Pointer(x), sbase+p.scratch)
 		y = *x
 		c = cap(y)
 	}

 	l := len(y)
 	if l+lb > c {
 		// incremental growth is max(len(slice)*1.5, len(slice)+len(bytes))
 		g := l * 3 / 2
 		if l+lb > g {
 			g = l + lb
 		}
 		z := make([]uint8, l, g)
 		copy(z, y)
 		y = z
 	}

 	y = y[0 : l+lb]
 	copy(y[l:l+lb], b)

 	*x = y
 	return nil
 }

 // Decode a slice of bools ([]bool).
 func (o *Buffer) dec_slice_bool(p *Properties, base uintptr, sbase uintptr) os.Error {
 	u, err := p.valDec(o)
 	if err != nil {
 		return err
 	}
 	x := (*[]bool)(unsafe.Pointer(base + p.offset))

 	y := *x
 	c := cap(y)
 	if c == 0 {
 		initSlice(unsafe.Pointer(x), sbase+p.scratch)
 		y = *x
 		c = cap(y)
 	}
 	l := len(y)
 	if l >= c {
 		g := l * 3 / 2
 		z := make([]bool, l, g)
 		copy(z, y)
 		y = z
 	}
 	y = y[0 : l+1]
 	y[l] = u != 0
 	*x = y
 	return nil
 }

 // Decode a slice of int32s ([]int32).
 func (o *Buffer) dec_slice_int32(p *Properties, base uintptr, sbase uintptr) os.Error {
 	u, err := p.valDec(o)
 	if err != nil {
 		return err
 	}
 	x := (*[]int32)(unsafe.Pointer(base + p.offset))

 	y := *x
 	c := cap(y)
 	if c == 0 {
 		initSlice(unsafe.Pointer(x), sbase+p.scratch)
 		y = *x
 		c = cap(y)
 	}
 	l := len(y)
 	if l >= c {
 		g := l * 3 / 2
 		z := make([]int32, l, g)
 		copy(z, y)
 		y = z
 	}
 	y = y[0 : l+1]
 	y[l] = int32(u)
 	*x = y
 	return nil
 }

 // Decode a slice of int64s ([]int64).
 func (o *Buffer) dec_slice_int64(p *Properties, base uintptr, sbase uintptr) os.Error {
 	u, err := p.valDec(o)
 	if err != nil {
 		return err
 	}
 	x := (*[]int64)(unsafe.Pointer(base + p.offset))

 	y := *x
 	c := cap(y)
 	if c == 0 {
 		initSlice(unsafe.Pointer(x), sbase+p.scratch)
 		y = *x
 		c = cap(y)
 	}
 	l := len(y)
 	if l >= c {
 		g := l * 3 / 2
 		z := make([]int64, l, g)
 		copy(z, y)
 		y = z
 	}
 	y = y[0 : l+1]
 	y[l] = int64(u)
 	*x = y
 	return nil
 }

 // Decode a slice of strings ([]string).
 func (o *Buffer) dec_slice_string(p *Properties, base uintptr, sbase uintptr) os.Error {
 	s, err := o.DecodeStringBytes()
 	if err != nil {
 		return err
 	}
 	x := (*[]string)(unsafe.Pointer(base + p.offset))

 	y := *x
 	c := cap(y)
 	if c == 0 {
 		initSlice(unsafe.Pointer(x), sbase+p.scratch)
 		y = *x
 		c = cap(y)
 	}
 	l := len(y)
 	if l >= c {
 		g := l * 3 / 2
 		z := make([]string, l, g)
 		copy(z, y)
 		y = z
 	}
 	y = y[0 : l+1]
 	y[l] = s
 	*x = y
 	return nil
 }

 // Decode a slice of slice of bytes ([][]byte).
 func (o *Buffer) dec_slice_slice_byte(p *Properties, base uintptr, sbase uintptr) os.Error {
 	b, err := o.DecodeRawBytes(true)
 	if err != nil {
 		return err
 	}
 	x := (*[][]byte)(unsafe.Pointer(base + p.offset))

 	y := *x
 	c := cap(y)
 	if c == 0 {
 		initSlice(unsafe.Pointer(x), sbase+p.scratch)
 		y = *x
 		c = cap(y)
 	}
 	l := len(y)
 	if l >= c {
 		g := l * 3 / 2
 		z := make([][]byte, l, g)
 		copy(z, y)
 		y = z
 	}
 	y = y[0 : l+1]
 	y[l] = b
 	*x = y
 	return nil
 }

 // Decode a group.
 func (o *Buffer) dec_struct_group(p *Properties, base uintptr, sbase uintptr) os.Error {
 	ptr := (**struct{})(unsafe.Pointer(base + p.offset))
 	typ := p.stype.Elem().(*reflect.StructType)
 	structv := unsafe.New(typ)
 	bas := uintptr(structv)
 	*ptr = (*struct{})(structv)

 	err := o.unmarshalType(p.stype, true, bas)

 	return err
 }

 // Decode an embedded message.
 func (o *Buffer) dec_struct_message(p *Properties, base uintptr, sbase uintptr) (err os.Error) {
 	raw, e := o.DecodeRawBytes(false)
 	if e != nil {
 		return e
 	}

 	ptr := (**struct{})(unsafe.Pointer(base + p.offset))
 	typ := p.stype.Elem().(*reflect.StructType)
 	structv := unsafe.New(typ)
 	bas := uintptr(structv)
 	*ptr = (*struct{})(structv)

 	// If the object can unmarshal itself, let it.
 	iv := unsafe.Unreflect(p.stype, unsafe.Pointer(ptr))
 	if u, ok := iv.(Unmarshaler); ok {
 		return u.Unmarshal(raw)
 	}

 	obuf := o.buf
 	oi := o.index
 	o.buf = raw
 	o.index = 0

 	err = o.unmarshalType(p.stype, false, bas)
 	o.buf = obuf
 	o.index = oi

 	return err
 }

 // Decode a slice of embedded messages.
 func (o *Buffer) dec_slice_struct_message(p *Properties, base uintptr, sbase uintptr) os.Error {
 	return o.dec_slice_struct(p, false, base, sbase)
 }

 // Decode a slice of embedded groups.
 func (o *Buffer) dec_slice_struct_group(p *Properties, base uintptr, sbase uintptr) os.Error {
 	return o.dec_slice_struct(p, true, base, sbase)
 }

 // Decode a slice of structs ([]*struct).
 func (o *Buffer) dec_slice_struct(p *Properties, is_group bool, base uintptr, sbase uintptr) os.Error {

 	x := (*[]*struct{})(unsafe.Pointer(base + p.offset))
 	y := *x
 	c := cap(y)
 	if c == 0 {
 		initSlice(unsafe.Pointer(x), sbase+p.scratch)
 		y = *x
 		c = cap(y)
 	}

 	l := len(y)
 	if l >= c {
 		// Create a new slice with 1.5X the capacity.
 		g := l * 3 / 2
 		z := make([]*struct{}, l, g)
 		copy(z, y)
 		y = z
 	}
 	y = y[0 : l+1]
 	*x = y

 	typ := p.stype.Elem().(*reflect.StructType)
 	structv := unsafe.New(typ)
 	bas := uintptr(structv)
 	y[l] = (*struct{})(structv)

 	if is_group {
 		err := o.unmarshalType(p.stype, is_group, bas)
 		return err
 	}

 	raw, err := o.DecodeRawBytes(true)
 	if err != nil {
 		return err
 	}

 	// If the object can unmarshal itself, let it.
 	iv := unsafe.Unreflect(p.stype, unsafe.Pointer(&y[l]))
 	if u, ok := iv.(Unmarshaler); ok {
 		return u.Unmarshal(raw)
 	}

 	obuf := o.buf
 	oi := o.index
 	o.buf = raw
 	o.index = 0

 	err = o.unmarshalType(p.stype, is_group, bas)

 	o.buf = obuf
 	o.index = oi

 	return err
 }
	// Go support for Protocol Buffers - Google's data interchange format
	//
	// Copyright 2010 Google Inc. All rights reserved.
	// http://code.google.com/p/goprotobuf/
	//
	// Redistribution and use in source and binary forms, with or without
	// modification, are permitted provided that the following conditions are
	// met:
	//
	// * Redistributions of source code must retain the above copyright
	// notice, this list of conditions and the following disclaimer.
	// * Redistributions in binary form must reproduce the above
	// copyright notice, this list of conditions and the following disclaimer
	// in the documentation and/or other materials provided with the
	// distribution.
	// * Neither the name of Google Inc. nor the names of its
	// contributors may be used to endorse or promote products derived from
	// this software without specific prior written permission.
	//
	// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

	package proto

	/*
	* Routines for decoding protocol buffer data to construct in-memory representations.
	*/

	import (
	"bytes"
	"fmt"
	"io"
	"os"
	"reflect"
	"runtime"
	"unsafe"
	)

	// ErrWrongType occurs when the wire encoding for the field disagrees with
	// that specified in the type being decoded. This is usually caused by attempting
	// to convert an encoded protocol buffer into a struct of the wrong type.
	var ErrWrongType = os.NewError("field/encoding mismatch: wrong type for field")

	// The fundamental decoders that interpret bytes on the wire.
	// Those that take integer types all return uint64 and are
	// therefore of type valueDecoder.

	// DecodeVarint reads a varint-encoded integer from the slice.
	// It returns the integer and the number of bytes consumed, or
	// zero if there is not enough.
	// This is the format for the
	// int32, int64, uint32, uint64, bool, and enum
	// protocol buffer types.
	func DecodeVarint(buf []byte) (x uint64, n int) {
	// x, n already 0
	for shift := uint(0); ; shift += 7 {
	if n >= len(buf) {
	return 0, 0
	}
	b := uint64(buf[n])
	n++
	x \|= (b & 0x7F) << shift
	if (b & 0x80) == 0 {
	break
	}
	}
	return x, n
	}

	// DecodeVarint reads a varint-encoded integer from the Buffer.
	// This is the format for the
	// int32, int64, uint32, uint64, bool, and enum
	// protocol buffer types.
	func (p *Buffer) DecodeVarint() (x uint64, err os.Error) {
	// x, err already 0

	i := p.index
	l := len(p.buf)

	for shift := uint(0); ; shift += 7 {
	if i >= l {
	err = io.ErrUnexpectedEOF
	return
	}
	b := p.buf[i]
	i++
	x \|= (uint64(b) & 0x7F) << shift
	if b < 0x80 {
	break
	}
	}
	p.index = i
	return
	}

	// DecodeFixed64 reads a 64-bit integer from the Buffer.
	// This is the format for the
	// fixed64, sfixed64, and double protocol buffer types.
	func (p *Buffer) DecodeFixed64() (x uint64, err os.Error) {
	// x, err already 0
	i := p.index + 8
	if i > len(p.buf) {
	err = io.ErrUnexpectedEOF
	return
	}
	p.index = i

	x = uint64(p.buf[i-8])
	x \|= uint64(p.buf[i-7]) << 8
	x \|= uint64(p.buf[i-6]) << 16
	x \|= uint64(p.buf[i-5]) << 24
	x \|= uint64(p.buf[i-4]) << 32
	x \|= uint64(p.buf[i-3]) << 40
	x \|= uint64(p.buf[i-2]) << 48
	x \|= uint64(p.buf[i-1]) << 56
	return
	}

	// DecodeFixed32 reads a 32-bit integer from the Buffer.
	// This is the format for the
	// fixed32, sfixed32, and float protocol buffer types.
	func (p *Buffer) DecodeFixed32() (x uint64, err os.Error) {
	// x, err already 0
	i := p.index + 4
	if i > len(p.buf) {
	err = io.ErrUnexpectedEOF
	return
	}
	p.index = i

	x = uint64(p.buf[i-4])
	x \|= uint64(p.buf[i-3]) << 8
	x \|= uint64(p.buf[i-2]) << 16
	x \|= uint64(p.buf[i-1]) << 24
	return
	}

	// DecodeZigzag64 reads a zigzag-encoded 64-bit integer
	// from the Buffer.
	// This is the format used for the sint64 protocol buffer type.
	func (p *Buffer) DecodeZigzag64() (x uint64, err os.Error) {
	x, err = p.DecodeVarint()
	if err != nil {
	return
	}
	x = (x >> 1) ^ uint64((int64(x&1)<<63)>>63)
	return
	}

	// DecodeZigzag32 reads a zigzag-encoded 32-bit integer
	// from the Buffer.
	// This is the format used for the sint32 protocol buffer type.
	func (p *Buffer) DecodeZigzag32() (x uint64, err os.Error) {
	x, err = p.DecodeVarint()
	if err != nil {
	return
	}
	x = uint64((uint32(x) >> 1) ^ uint32((int32(x&1)<<31)>>31))
	return
	}

	// These are not ValueDecoders: they produce an array of bytes or a string.
	// bytes, embedded messages

	// DecodeRawBytes reads a count-delimited byte buffer from the Buffer.
	// This is the format used for the bytes protocol buffer
	// type and for embedded messages.
	func (p *Buffer) DecodeRawBytes(alloc bool) (buf []byte, err os.Error) {
	n, err := p.DecodeVarint()
	if err != nil {
	return
	}

	nb := int(n)
	if p.index+nb > len(p.buf) {
	err = io.ErrUnexpectedEOF
	return
	}

	if !alloc {
	// todo: check if can get more uses of alloc=false
	buf = p.buf[p.index : p.index+nb]
	p.index += nb
	return
	}

	buf = make([]byte, nb)
	copy(buf, p.buf[p.index:])
	p.index += nb
	return
	}

	// DecodeStringBytes reads an encoded string from the Buffer.
	// This is the format used for the proto2 string type.
	func (p *Buffer) DecodeStringBytes() (s string, err os.Error) {
	buf, err := p.DecodeRawBytes(false)
	if err != nil {
	return
	}
	return string(buf), nil
	}

	// Skip the next item in the buffer. Its wire type is decoded and presented as an argument.
	// If the protocol buffer has extensions, and the field matches, add it as an extension.
	// Otherwise, if the XXX_unrecognized field exists, append the skipped data there.
	func (o Buffer) skipAndSave(t reflect.StructType, tag, wire int, base uintptr) os.Error {

	oi := o.index

	err := o.skip(t, tag, wire)
	if err != nil {
	return err
	}

	x := fieldIndex(t, "XXX_unrecognized")
	if x == nil {
	return nil
	}

	p := propByIndex(t, x)
	ptr := (*[]byte)(unsafe.Pointer(base + p.offset))

	if *ptr == nil {
	// This is the first skipped element,
	// allocate a new buffer.
	*ptr = o.bufalloc()
	}

	// Add the skipped field to struct field
	obuf := o.buf

	o.buf = *ptr
	o.EncodeVarint(uint64(tag<<3 \| wire))
	*ptr = bytes.Add(o.buf, obuf[oi:o.index])

	o.buf = obuf

	return nil
	}

	// Skip the next item in the buffer. Its wire type is decoded and presented as an argument.
	func (o Buffer) skip(t reflect.StructType, tag, wire int) os.Error {

	var u uint64
	var err os.Error

	switch wire {
	case WireVarint:
	_, err = o.DecodeVarint()
	case WireFixed64:
	_, err = o.DecodeFixed64()
	case WireBytes:
	_, err = o.DecodeRawBytes(false)
	case WireFixed32:
	_, err = o.DecodeFixed32()
	case WireStartGroup:
	for {
	u, err = o.DecodeVarint()
	if err != nil {
	break
	}
	fwire := int(u & 0x7)
	if fwire == WireEndGroup {
	break
	}
	ftag := int(u >> 3)
	err = o.skip(t, ftag, fwire)
	if err != nil {
	break
	}
	}
	default:
	fmt.Fprintf(os.Stderr, "proto: can't skip wire type %d for %s\n", wire, t)
	}
	return err
	}

	// Unmarshaler is the interface representing objects that can unmarshal themselves.
	type Unmarshaler interface {
	Unmarshal([]byte) os.Error
	}

	// Unmarshal parses the protocol buffer representation in buf and places the
	// decoded result in pb. If the struct underlying pb does not match
	// the data in buf, the results can be unpredictable.
	func Unmarshal(buf []byte, pb interface{}) os.Error {
	// If the object can unmarshal itself, let it.
	if u, ok := pb.(Unmarshaler); ok {
	return u.Unmarshal(buf)
	}

	return NewBuffer(buf).Unmarshal(pb)
	}

	// Unmarshal parses the protocol buffer representation in the
	// Buffer and places the decoded result in pb. If the struct
	// underlying pb does not match the data in the buffer, the results can be
	// unpredictable.
	func (p *Buffer) Unmarshal(pb interface{}) os.Error {
	// If the object can unmarshal itself, let it.
	if u, ok := pb.(Unmarshaler); ok {
	err := u.Unmarshal(p.buf[p.index:])
	p.index = len(p.buf)
	return err
	}

	mstat := runtime.MemStats.Mallocs

	typ, base, err := getbase(pb)
	if err != nil {
	return err
	}

	err = p.unmarshalType(typ, false, base)

	mstat = runtime.MemStats.Mallocs - mstat
	stats.Dmalloc += mstat
	stats.Decode++

	return err
	}

	// unmarshalType does the work of unmarshaling a structure.
	func (o Buffer) unmarshalType(t reflect.PtrType, is_group bool, base uintptr) os.Error {
	st := t.Elem().(*reflect.StructType)
	prop := GetProperties(st)
	sbase := getsbase(prop) // scratch area for data items

	var err os.Error
	for err == nil && o.index < len(o.buf) {
	oi := o.index
	var u uint64
	u, err = o.DecodeVarint()
	if err != nil {
	break
	}
	wire := int(u & 0x7)
	if wire == WireEndGroup {
	if is_group {
	return nil // input is satisfied
	}
	return ErrWrongType
	}
	tag := int(u >> 3)
	fieldnum, ok := prop.tags[tag]
	if !ok {
	// Maybe it's an extension?
	o.ptr = base
	iv := unsafe.Unreflect(t, unsafe.Pointer(&o.ptr))
	if e, ok := iv.(extendableProto); ok && isExtensionField(e, int32(tag)) {
	if err = o.skip(st, tag, wire); err == nil {
	e.ExtensionMap()[int32(tag)] = bytes.Add(nil, o.buf[oi:o.index])
	}
	continue
	}
	err = o.skipAndSave(st, tag, wire, base)
	continue
	}
	p := prop.Prop[fieldnum]

	if p.dec != nil {
	if wire != WireStartGroup && wire != p.WireType {
	err = ErrWrongType
	continue
	}
	err = p.dec(o, p, base, sbase)
	continue
	}

	fmt.Fprintf(os.Stderr, "no protobuf decoder for %s.%s\n", t, st.Field(fieldnum).Name)
	}
	if err == nil && is_group {
	return io.ErrUnexpectedEOF
	}
	return err
	}

	// Make *pslice have base address base, length 0, and capacity startSize.
	func initSlice(pslice unsafe.Pointer, base uintptr) {
	sp := (*reflect.SliceHeader)(pslice)
	sp.Data = base
	sp.Len = 0
	sp.Cap = startSize
	}

	// Individual type decoders
	// For each,
	// u is the decoded value,
	// v is a pointer to the field (pointer) in the struct
	// x is a pointer to the preallocated scratch space to hold the decoded value.

	// Decode a bool.
	func (o Buffer) dec_bool(p Properties, base uintptr, sbase uintptr) os.Error {
	u, err := p.valDec(o)
	if err != nil {
	return err
	}
	v := (**uint8)(unsafe.Pointer(base + p.offset))
	x := (*uint8)(unsafe.Pointer(sbase + p.scratch))
	*x = uint8(u)
	*v = x
	return nil
	}

	// Decode an int32.
	func (o Buffer) dec_int32(p Properties, base uintptr, sbase uintptr) os.Error {
	u, err := p.valDec(o)
	if err != nil {
	return err
	}
	v := (**int32)(unsafe.Pointer(base + p.offset))
	x := (*int32)(unsafe.Pointer(sbase + p.scratch))
	*x = int32(u)
	*v = x
	return nil
	}

	// Decode an int64.
	func (o Buffer) dec_int64(p Properties, base uintptr, sbase uintptr) os.Error {
	u, err := p.valDec(o)
	if err != nil {
	return err
	}
	v := (**int64)(unsafe.Pointer(base + p.offset))
	x := (*int64)(unsafe.Pointer(sbase + p.scratch))
	*x = int64(u)
	*v = x
	return nil
	}

	// Decode a string.
	func (o Buffer) dec_string(p Properties, base uintptr, sbase uintptr) os.Error {
	s, err := o.DecodeStringBytes()
	if err != nil {
	return err
	}
	v := (**string)(unsafe.Pointer(base + p.offset))
	x := (*string)(unsafe.Pointer(sbase + p.scratch))
	*x = s
	*v = x
	return nil
	}

	// Decode a slice of bytes ([]byte).
	func (o Buffer) dec_slice_byte(p Properties, base uintptr, sbase uintptr) os.Error {
	b, err := o.DecodeRawBytes(false)
	if err != nil {
	return err
	}
	lb := len(b)
	if lb == 0 {
	return nil
	}
	x := (*[]uint8)(unsafe.Pointer(base + p.offset))

	y := *x
	c := cap(y)
	if c == 0 {
	initSlice(unsafe.Pointer(x), sbase+p.scratch)
	y = *x
	c = cap(y)
	}

	l := len(y)
	if l+lb > c {
	// incremental growth is max(len(slice)*1.5, len(slice)+len(bytes))
	g := l * 3 / 2
	if l+lb > g {
	g = l + lb
	}
	z := make([]uint8, l, g)
	copy(z, y)
	y = z
	}

	y = y[0 : l+lb]
	copy(y[l:l+lb], b)

	*x = y
	return nil
	}

	// Decode a slice of bools ([]bool).
	func (o Buffer) dec_slice_bool(p Properties, base uintptr, sbase uintptr) os.Error {
	u, err := p.valDec(o)
	if err != nil {
	return err
	}
	x := (*[]bool)(unsafe.Pointer(base + p.offset))

	y := *x
	c := cap(y)
	if c == 0 {
	initSlice(unsafe.Pointer(x), sbase+p.scratch)
	y = *x
	c = cap(y)
	}
	l := len(y)
	if l >= c {
	g := l * 3 / 2
	z := make([]bool, l, g)
	copy(z, y)
	y = z
	}
	y = y[0 : l+1]
	y[l] = u != 0
	*x = y
	return nil
	}

	// Decode a slice of int32s ([]int32).
	func (o Buffer) dec_slice_int32(p Properties, base uintptr, sbase uintptr) os.Error {
	u, err := p.valDec(o)
	if err != nil {
	return err
	}
	x := (*[]int32)(unsafe.Pointer(base + p.offset))

	y := *x
	c := cap(y)
	if c == 0 {
	initSlice(unsafe.Pointer(x), sbase+p.scratch)
	y = *x
	c = cap(y)
	}
	l := len(y)
	if l >= c {
	g := l * 3 / 2
	z := make([]int32, l, g)
	copy(z, y)
	y = z
	}
	y = y[0 : l+1]
	y[l] = int32(u)
	*x = y
	return nil
	}

	// Decode a slice of int64s ([]int64).
	func (o Buffer) dec_slice_int64(p Properties, base uintptr, sbase uintptr) os.Error {
	u, err := p.valDec(o)
	if err != nil {
	return err
	}
	x := (*[]int64)(unsafe.Pointer(base + p.offset))

	y := *x
	c := cap(y)
	if c == 0 {
	initSlice(unsafe.Pointer(x), sbase+p.scratch)
	y = *x
	c = cap(y)
	}
	l := len(y)
	if l >= c {
	g := l * 3 / 2
	z := make([]int64, l, g)
	copy(z, y)
	y = z
	}
	y = y[0 : l+1]
	y[l] = int64(u)
	*x = y
	return nil
	}

	// Decode a slice of strings ([]string).
	func (o Buffer) dec_slice_string(p Properties, base uintptr, sbase uintptr) os.Error {
	s, err := o.DecodeStringBytes()
	if err != nil {
	return err
	}
	x := (*[]string)(unsafe.Pointer(base + p.offset))

	y := *x
	c := cap(y)
	if c == 0 {
	initSlice(unsafe.Pointer(x), sbase+p.scratch)
	y = *x
	c = cap(y)
	}
	l := len(y)
	if l >= c {
	g := l * 3 / 2
	z := make([]string, l, g)
	copy(z, y)
	y = z
	}
	y = y[0 : l+1]
	y[l] = s
	*x = y
	return nil
	}

	// Decode a slice of slice of bytes ([][]byte).
	func (o Buffer) dec_slice_slice_byte(p Properties, base uintptr, sbase uintptr) os.Error {
	b, err := o.DecodeRawBytes(true)
	if err != nil {
	return err
	}
	x := (*[][]byte)(unsafe.Pointer(base + p.offset))

	y := *x
	c := cap(y)
	if c == 0 {
	initSlice(unsafe.Pointer(x), sbase+p.scratch)
	y = *x
	c = cap(y)
	}
	l := len(y)
	if l >= c {
	g := l * 3 / 2
	z := make([][]byte, l, g)
	copy(z, y)
	y = z
	}
	y = y[0 : l+1]
	y[l] = b
	*x = y
	return nil
	}

	// Decode a group.
	func (o Buffer) dec_struct_group(p Properties, base uintptr, sbase uintptr) os.Error {
	ptr := (**struct{})(unsafe.Pointer(base + p.offset))
	typ := p.stype.Elem().(*reflect.StructType)
	structv := unsafe.New(typ)
	bas := uintptr(structv)
	ptr = (struct{})(structv)

	err := o.unmarshalType(p.stype, true, bas)

	return err
	}

	// Decode an embedded message.
	func (o Buffer) dec_struct_message(p Properties, base uintptr, sbase uintptr) (err os.Error) {
	raw, e := o.DecodeRawBytes(false)
	if e != nil {
	return e
	}

	ptr := (**struct{})(unsafe.Pointer(base + p.offset))
	typ := p.stype.Elem().(*reflect.StructType)
	structv := unsafe.New(typ)
	bas := uintptr(structv)
	ptr = (struct{})(structv)

	// If the object can unmarshal itself, let it.
	iv := unsafe.Unreflect(p.stype, unsafe.Pointer(ptr))
	if u, ok := iv.(Unmarshaler); ok {
	return u.Unmarshal(raw)
	}

	obuf := o.buf
	oi := o.index
	o.buf = raw
	o.index = 0

	err = o.unmarshalType(p.stype, false, bas)
	o.buf = obuf
	o.index = oi

	return err
	}

	// Decode a slice of embedded messages.
	func (o Buffer) dec_slice_struct_message(p Properties, base uintptr, sbase uintptr) os.Error {
	return o.dec_slice_struct(p, false, base, sbase)
	}

	// Decode a slice of embedded groups.
	func (o Buffer) dec_slice_struct_group(p Properties, base uintptr, sbase uintptr) os.Error {
	return o.dec_slice_struct(p, true, base, sbase)
	}

	// Decode a slice of structs ([]*struct).
	func (o Buffer) dec_slice_struct(p Properties, is_group bool, base uintptr, sbase uintptr) os.Error {

	x := ([]struct{})(unsafe.Pointer(base + p.offset))
	y := *x
	c := cap(y)
	if c == 0 {
	initSlice(unsafe.Pointer(x), sbase+p.scratch)
	y = *x
	c = cap(y)
	}

	l := len(y)
	if l >= c {
	// Create a new slice with 1.5X the capacity.
	g := l * 3 / 2
	z := make([]*struct{}, l, g)
	copy(z, y)
	y = z
	}
	y = y[0 : l+1]
	*x = y

	typ := p.stype.Elem().(*reflect.StructType)
	structv := unsafe.New(typ)
	bas := uintptr(structv)
	y[l] = (*struct{})(structv)

	if is_group {
	err := o.unmarshalType(p.stype, is_group, bas)
	return err
	}

	raw, err := o.DecodeRawBytes(true)
	if err != nil {
	return err
	}

	// If the object can unmarshal itself, let it.
	iv := unsafe.Unreflect(p.stype, unsafe.Pointer(&y[l]))
	if u, ok := iv.(Unmarshaler); ok {
	return u.Unmarshal(raw)
	}

	obuf := o.buf
	oi := o.index
	o.buf = raw
	o.index = 0

	err = o.unmarshalType(p.stype, is_group, bas)

	o.buf = obuf
	o.index = oi

	return err
	}