以太坊源码学习0x04 RLP源码分析

RLP（Recursive Length Prefix），递归长度前缀编码，这是以太坊序列化采用的编码方式。 RLP主要用于以太坊中数据的网络传输和持久化存储。

RLP理解RLP编码

RLP编码主要有两种数据类型：

令 Rc(x) 为 RLP 编码函数。

先看字节数组的几种编码规则：

1. 对于单字节b, b ∈ [0,127], Rc(b) = b

例如：Rc(a) = 97, Rc(w) = 119

2.对于字节数组bytes，length(bytes) 55，

Rc(bytes) = 183+sizeof(sizeof(bytes)) ++ Rc(sizeof(bytes)) + bytes

eg: str = "这句话的长度超过55个字节，我知道是因为我预先设计好的"

rc（str）= [184 86 84 101 32 101 110 103 116 104 32 32 32 32 116 104 105 32 115 101 110 99 101 32 101 32 105 32 109 114 104 104 104 104 97 110 32 53 53 53 53 53 53 53 53 53 53 53 32 98 121 116 101 116 101 115 44 32 73 32 73 32 73 32 73 32 32 107 110 119 32 105 116 32 99 97 117 115 101 32 112 114 101 45 1001 115 103 110 101 100 32 105 116]]]]]]]

经过计算以太坊源码解析，该字符串占用的字节数为86。显然，184 = 183 + sizeof(86)以太坊源码解析，86 = sizeof(str)，84是“T”的编码，从84开始就是str的编码本身。

以上是字节数组。 接下来，让我们看看以字节数组为元素的数组。 这称为列表的编码方法：

首先，必须明确几个概念。 对于list列表，lenL是指list中每个字节的总和，lenDl是指经过Rc(x)编码后list中每个字节的总长度。

lenL（列表）=

lenDl(列表) =

4. 对于 list[bytes0, bytes1...bytesN], lenL(list) 55,

那么，根据规则 2，可以得出：

RC [This Sentence 的长度超过 55 个字节，] = [179 84 104 101 32 108 103 116 104 32 32 116 105 115 32 110 116 101 32 105 115 32 109 111 114 101 3103 197 32 98 121 116 101 115 44 32] (179 = 128 + 51),

Rc[我知道是因为我预先设计了它]

= [163 73 32 107 110 111 119 32 105 116 32 98 101 99 97 117 115 101 32 73 32 112 114 101 45 100 101 115 105 103 110 101 102 = 13 +

现在我们知道lenDl(list) = 52 + 36 = 88，88只需要占用1个字节，所以前248就是247+1的结构，后面的88就是lenDl(list)本身的编码，和然后是列表中每个字节的 RLP 编码。

RLP解码

我们知道，哪里有编码，哪里就有解码。 编码是解码的逆过程。 我们发现在编码的时候，不同的情况有不同的字节前缀，所以解码的时候也是从这个字节前缀开始。

设 Dr(x) 为解码函数，s 为 x 的第一个字节。

subX[m,n]表示x的子串，从x的第m个开始取n个字节。

bin2Int(bytes) 表示将字节数组按照BigEndian编码转换为整数，目的是求出编码后的字符串的长度。

1. s ∈ [0, 127]，对应编码规则1单字节解码，

Dr(x) = x

2. s ∈ [128, 184)，对应编码规则2，数组长度不超过55

Dr(x) = subX[2, s-128]

3. s ∈ [184, 192]，对应编码规则3，数组长度超过55

bin2Int(subX[1, s-183]) 是编码数组的长度

Dr(x) = subX[bin2Int(subX[1, s-183]+1, bin2Int(subX[1, s-183])]

4. s ∈ [192, 247)，对应编码规则4，不超过55的列表总长度为lenDl = s-192，然后递归调用解码规则1-3

博士（x）=

5. s ∈ [247, 256]，对应编码规则5，列表总长度超过55，列表总长度lenDl = bin2Int(subX[1, s-247])，然后递归调用解码规则 1-3

博士（x）=

RLP源代码

以上大致了解了RLP的编解码方式。 接下来我们去eth源码看看RLP相关的代码是怎么写的。

上一篇主要介绍了geth源码结构，RLP源码主要在rlp目录下。

RLP源代码结构

类型缓存.go

该结构体主要实现不同类型与对应的codec之间的映射关系，通过它获取对应的codec。

核心数据结构

// 核心数据结构
var (
    typeCacheMutex sync.RWMutex    // 读写锁，用于在多线程时保护typeCache
    typeCache      = make(map[typekey]*typeinfo)  // 保存类型 -> 编码器函数的数据结构
    // Map的key是类型，value是对应的编码和解码器
)
type typeinfo struct {
    decoder    // 解码器函数
    writer     // 编码器函数
}

如何获取编码器和解码器函数

// 获取编码器和解码器的函数
func cachedTypeInfo(typ reflect.Type, tags tags) (*typeinfo, error) {
    typeCacheMutex.RLock()    // 加锁保护
    info := typeCache[typekey{typ, tags}]    // 将传入的typ和tags封装为typekey类型
    typeCacheMutex.RUnlock()  // 解锁
    if info != nil {    // 成功获取到typ对应的编解码函数
        return info, nil
    }
    // not in the cache, need to generate info for this type.
    // 编解码不在typeCache中，需要创建该typ对应的编解码函数
    typeCacheMutex.Lock()
    defer typeCacheMutex.Unlock()
    return cachedTypeInfo1(typ, tags)
}
// 新建typ对应的编解码函数
func cachedTypeInfo1(typ reflect.Type, tags tags) (*typeinfo, error) {
    key := typekey{typ, tags}
    info := typeCache[key]
    if info != nil {
        // another goroutine got the write lock first
        /// 其他线程已经成功创建
        return info, nil
    }
    // put a dummmy value into the cache before generating.
    // if the generator tries to lookup itself, it will get
    // the dummy value and won't call itself recursively.
    // 这个地方首先创建了一个值来填充这个类型的位置，避免遇到一些递归定义的数据类型形成死循环
    typeCache[key] = new(typeinfo)
    info, err := genTypeInfo(typ, tags)    // 生成对应类型的编解码器函数
    if err != nil {
        // remove the dummy value if the generator fails
        // 创建失败处理
        delete(typeCache, key)
        return nil, err
    }
    *typeCache[key] = *info
    return typeCache[key], err
}

生成对应编解码器的函数

// 生成对应编解码器的函数
func genTypeInfo(typ reflect.Type, tags tags) (info *typeinfo, err error) {
    info = new(typeinfo)
    if info.decoder, err = makeDecoder(typ, tags); err != nil {
        return nil, err
    }
    if info.writer, err = makeWriter(typ, tags); err != nil {
        return nil, err
    }
    return info, nil
}

解码.go

typeCache 定义了类型和对应的解码器之间的映射关系。 接下来我们看一下对应的编解码代码。

// 定义一些解码错误
var (
    // EOL is returned when the end of the current list
    // has been reached during streaming.
    EOL = errors.New("rlp: end of list")
    // Actual Errors
    ErrExpectedString   = errors.New("rlp: expected String or Byte")
    ErrExpectedList     = errors.New("rlp: expected List")
    ErrCanonInt         = errors.New("rlp: non-canonical integer format")
    ErrCanonSize        = errors.New("rlp: non-canonical size information")
    ErrElemTooLarge     = errors.New("rlp: element is larger than containing list")
    ErrValueTooLarge    = errors.New("rlp: value size exceeds available input length")
    ErrMoreThanOneValue = errors.New("rlp: input contains more than one value")
    // internal errors
    errNotInList     = errors.New("rlp: call of ListEnd outside of any list")
    errNotAtEOL      = errors.New("rlp: call of ListEnd not positioned at EOL")
    errUintOverflow  = errors.New("rlp: uint overflow")
    errNoPointer     = errors.New("rlp: interface given to Decode must be a pointer")
    errDecodeIntoNil = errors.New("rlp: pointer given to Decode must not be nil")
)

// 解码器  根据不同的类型返回对应的解码器函数
func makeDecoder(typ reflect.Type, tags tags) (dec decoder, err error) {
    kind := typ.Kind()
    switch {
    case typ == rawValueType:
        return decodeRawValue, nil
    case typ.Implements(decoderInterface):
        return decodeDecoder, nil
    case kind != reflect.Ptr && reflect.PtrTo(typ).Implements(decoderInterface):
        return decodeDecoderNoPtr, nil
    case typ.AssignableTo(reflect.PtrTo(bigInt)):
        return decodeBigInt, nil
    case typ.AssignableTo(bigInt):
        return decodeBigIntNoPtr, nil
    case isUint(kind):
        return decodeUint, nil
    case kind == reflect.Bool:
        return decodeBool, nil
    case kind == reflect.String:
        return decodeString, nil
    case kind == reflect.Slice || kind == reflect.Array:
        return makeListDecoder(typ, tags)
    case kind == reflect.Struct:
        return makeStructDecoder(typ)
    case kind == reflect.Ptr:
        if tags.nilOK {
            return makeOptionalPtrDecoder(typ)
        }
        return makePtrDecoder(typ)
    case kind == reflect.Interface:
        return decodeInterface, nil
    default:
        return nil, fmt.Errorf("rlp: type %v is not RLP-serializable", typ)
    }
}

按照上述切换方法，可以实现各种译码功能的转换。

编码.go

接下来我们看一下关于encoding的代码解读。 首先，定义了两种特殊情况下的编码方法。

var (
    // Common encoded values.
    // These are useful when implementing EncodeRLP.
    EmptyString = []byte{0x80}      // 针对空字符串的编码
    EmptyList   = []byte{0xC0}      // 针对空列表的编码
)

然后定义一个接口EncodeRLP用于调用，但是很多时候EncodeRLP会调用Encode方法。

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
}

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 := encbufPool.Get().(*encbuf)    // 获取一个编码缓冲区encbuf
    defer encbufPool.Put(eb)
    eb.reset()
    if err := eb.encode(val); err != nil {
        return err
    }
    return eb.toWriter(w)
}

func (w *encbuf) encode(val interface{}) error {
    rval := reflect.ValueOf(val)
    ti, err := cachedTypeInfo(rval.Type(), tags{})
    if err != nil {
        return err
    }
    return ti.writer(rval, w)
}

makeWriter和上面的makeDecoder类似，都是switch形式的编码函数。

更多以太坊源码分析请移步全球最大的同性交友网，如果觉得有用记得给个小star

.

.

.

.

互联网颠覆世界，区块链颠覆互联网！ -------------------------------------------------- ---20180911 00:21