阅读 go-ethereum 源码 - 2

RLP（递归长度前缀）的目的是编码任意嵌套的二进制数据数组，RLP是以太坊中用于序列化对象的主要编码方法。 RLP的唯一目的是编码结构; 对于编码的数据的具体类型（例如字符串，浮点数）则留给高阶协议自己负责处理。（简单来说编码的二进制数据，代表的是字符串、浮点数还是其他类型。由使用该编码的高级协议定义）;RLP编码的整数必须以大端二进制形式（big endian）表示，且不包含前导零（整数值零等于空字节数组）。反序列化正整数时如发现前缀有零的必须视为无效。字符串长度的整数表示也必须以这种方式进行编码，其他部分的整数同样如此。更多信息可以在Ethereum黄皮书附录B中找到。

如果有人希望使用RLP对字典进行编码，有两个建议

按照字典顺序使用[[k1,v1],[k2,v2]...]进行编码
或者使用更高级别的Patricia Tree编码

定义（编码)

RLP编码功能需要一个项（item)。一个项（item)定义如下：

一个字符串（即字节数组）是一个item
项目列表(a list of item )也是一个项item

例如，空字符串是一个item，包含单词“cat”的字符串也是item，包含任意数量字符串的列表以及更复杂的数据结构也是item，如["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"] 。请注意，在本文其余部分的上下文中，“string”将用作“一定数量的二进制数据字节数”的同义词; 没有使用特殊的编码，也没有关于字符串内容的知识。

在Python2 和 Golang 中，string都被定义为二进制数组，数据的保存全为二进制。如需要展示为特定格式的编码字符时，需要指定编解码格式。

RLP编码定义如下：

对于其值在[0x00, 0x7f]范围内的单个字节，该字节是其自己的RLP编码。
如果一个字符串的长度为0-55字节，则RLP编码由一个值为0x80的单个字节加上
该字符串后面的字符串长度组成。第一个字节的范围是[0x80, 0xb7]（[0x80,0x80+55=0xb7]) 。
如果一个字符串长度超过55个字节，则RLP编码由一个值为0xb7的单个字节加上以二进制形式表示的字符串长度的字节长度，接着是字符串长度，后跟字符串。例如，长度为1024的字符串将被编码为\xb9\x04\x00后跟该字符串。第一个字节的范围是[0xb8, 0xbf] 。(1024如何被编码查看下方代码）
如果编码的为列表(list/array)，其长度为0-55字节（列表保存的是，所有被RLP编码的二进制数据），则RLP编码由单个字节组成，其值为0xc0加上列表的长度，然后连接项目的RLP编码。第一个字节的范围是[0xc0, 0xf7] (0xf7-0xc0 = 55) 。
如果列表的总长度超过55个字节，则RLP编码由一个值为0xf7的单个字节加上以二进制形式表示的有效长度的字节长度，接着是RLP编码的列表。第一个字节的范围是[0xf8, 0xff](表示后面最多跟随8字节表示长度的内容），列表的长度最多为2**64次方。

python代码如下：

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80: return input
        else: return encode_length(len(input), 0x80) + input
    elif isinstance(input,list):
        output = ''
        for item in input: output += rlp_encode(item)
        return encode_length(len(output), 0xc0) + output

def encode_length(L,offset):
    if L < 56:
         return chr(L + offset)
    elif L < 256**8:
         BL = to_binary(L)
         return chr(len(BL) + offset + 55) + BL
    else:
         raise Exception("input too long")

def to_binary(x):
    if x == 0:
        return ''
    else: 
        return to_binary(int(x / 256)) + chr(x % 256)

Golang 代码如下：

在commit 5db3335dce766bd679c54ea44f6df08a7ff74762 初始提交中，rlp的编码代码在serialization.go文件中。其代码暂未支持整数编码。观察代码RLP的实现与如今的RLP规范定义的不大一致。所以我们选取后续的提交。

在commit d7eca7bcc12e940f0aa80d45e6e802ba68143b5c 中，rlp编解码基本实现完整。以下代码来自 d7eca7bcc12e940f0aa80d45e6e802ba68143b5c rlp.go中。

可通过：
https://github.com/ethereum/go-ethereum/blob/d7eca7bcc12e940f0aa80d45e6e802ba68143b5c/ethutil/rlp.go 在线查看

或者在go-ethereum源码目录中，迁出到指定提交
git checkout d7eca7bcc12e940f0aa80d45e6e802ba68143b5c



func Encode(object interface{}) []byte {
    var buff bytes.Buffer

    if object != nil {
        switch t := object.(type) {
        case *Value:
            buff.Write(Encode(t.Raw()))
        // Code dup :-/
        case int:
            buff.Write(Encode(big.NewInt(int64(t))))
        case uint:
            buff.Write(Encode(big.NewInt(int64(t))))
        case int8:
            buff.Write(Encode(big.NewInt(int64(t))))
        case int16:
            buff.Write(Encode(big.NewInt(int64(t))))
        case int32:
            buff.Write(Encode(big.NewInt(int64(t))))
        case int64:
            buff.Write(Encode(big.NewInt(t)))
        case uint16:
            buff.Write(Encode(big.NewInt(int64(t))))
        case uint32:
            buff.Write(Encode(big.NewInt(int64(t))))
        case uint64:
            buff.Write(Encode(big.NewInt(int64(t))))
        case byte:
            buff.Write(Encode(big.NewInt(int64(t))))
        case *big.Int:
            buff.Write(Encode(t.Bytes()))
        case []byte:
            if len(t) == 1 && t[0] <= 0x7f {
                buff.Write(t)
            } else if len(t) < 56 {
                buff.WriteByte(byte(len(t) + 0x80))
                buff.Write(t)
            } else {
                b := big.NewInt(int64(len(t)))
                buff.WriteByte(byte(len(b.Bytes()) + 0xb7))
                buff.Write(b.Bytes())
                buff.Write(t)
            }
        case string:
            buff.Write(Encode([]byte(t)))
        case []interface{}:
            // Inline function for writing the slice header
            WriteSliceHeader := func(length int) {
                if length < 56 {
                    buff.WriteByte(byte(length + 0xc0))
                } else {
                    b := big.NewInt(int64(length))
                    buff.WriteByte(byte(len(b.Bytes()) + 0xf7))
                    buff.Write(b.Bytes())
                }
            }

            var b bytes.Buffer
            for _, val := range t {
                b.Write(Encode(val))
            }
            WriteSliceHeader(len(b.Bytes()))
            buff.Write(b.Bytes())
        }
    } else {
        // Empty list for nil
        buff.WriteByte(0xc0)
    }

    return buff.Bytes()
}

例子

字符串 "dog" 编码：

case string:
        buff.Write(Encode([]byte(t)))

case []byte:
        if len(t) == 1 && t[0] <= 0x7f {
            buff.Write(t)
        } else if len(t) < 56 {
            buff.WriteByte(byte(len(t) + 0x80))
            buff.Write(t)
        } else {
            b := big.NewInt(int64(len(t)))
            buff.WriteByte(byte(len(b.Bytes()) + 0xb7))
            buff.Write(b.Bytes())

len("dog")==3 < 56,
前缀 = byte(3+0x80) = 0x83
跟随字符串"dog" ,最终为[0x83,'d','o','g'] = [0x83,0x64,0x6f,0x67]

列表 [ "cat", "dog" ]

  [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]

关注int整数的保存。

  case *big.Int:
      buff.Write(Encode(t.Bytes()))   
  Bytes方法返回的正式是大端序的byte切片 （returns the absolute value of x as a big-endian byte slice.）

RLP 解码

根据RLP编码的规则和过程，RLP解码的输入应视为二进制数据的数组，过程如下：

根据输入数据的第一个字节（即前缀），并解码数据类型、实际数据的长度和偏移量;
根据数据的类型和偏移，相应解码数据;

继续解码其余的输入;

其中，解码数据类型和偏移的规则如下：

如果第一个字节（即前缀）的范围是[0x00，0x7f]，则该数据是一个字符串,且内容为该字节本身;
如果第一个字节的范围是[0x80，0xb7]，那么数据是一个字符串，长度等于第一个字节减去0x80,字符串跟在第一个字节后面;
如果第一个字节的范围是[0xb8，0xbf]，那么数据是一个字符串，第一个字节减去0xb7等于表示长度的字节数（跟在第一字节后），取得长度字节后得到实际字符串长度，字符串紧跟其后;
如果第一字节的范围是[0xc0，0xf7]，则数据是列表，第一字节减去0xc0后得到列表的长度;
如果第一个字节的范围是[0xf8,0xff]，那么该数据就是一个列表，第一个字节减去0xf7等于表示长度的字节数，根据长度字节数取得列表长度。列表紧跟其后;

Golang 代码如下：

// TODO Use a bytes.Buffer instead of a raw byte slice.
// Cleaner code, and use draining instead of seeking the next bytes to read
func Decode(data []byte, pos uint64) (interface{}, uint64) {
    var slice []interface{}
    char := int(data[pos])
    switch {
    case char <= 0x7f:
        return data[pos], pos + 1

    case char <= 0xb7:
        b := uint64(data[pos]) - 0x80

        return data[pos+1 : pos+1+b], pos + 1 + b

    case char <= 0xbf:
        b := uint64(data[pos]) - 0xb7

        b2 := ReadVarint(bytes.NewReader(data[pos+1 : pos+1+b]))

        return data[pos+1+b : pos+1+b+b2], pos + 1 + b + b2

    case char <= 0xf7:
        b := uint64(data[pos]) - 0xc0
        prevPos := pos
        pos++
        for i := uint64(0); i < b; {
            var obj interface{}

            // Get the next item in the data list and append it
            obj, prevPos = Decode(data, pos)
            slice = append(slice, obj)

            // Increment i by the amount bytes read in the previous
            // read
            i += (prevPos - pos)
            pos = prevPos
        }
        return slice, pos

    case char <= 0xff:
        l := uint64(data[pos]) - 0xf7
        b := ReadVarint(bytes.NewReader(data[pos+1 : pos+1+l]))

        pos = pos + l + 1

        prevPos := b
        for i := uint64(0); i < uint64(b); {
            var obj interface{}

            obj, prevPos = Decode(data, pos)
            slice = append(slice, obj)

            i += (prevPos - pos)
            pos = prevPos
        }
        return slice, pos

    default:
        panic(fmt.Sprintf("byte not supported: %q", char))
    }

    return slice, 0
}

Sort Order:

Trending

[-]

steemitboard (66) · 7 years ago

Congratulations @threej! You have completed some achievement on Steemit and have been rewarded with new badge(s) :

You made your First Vote

Click on any badge to view your own Board of Honor on SteemitBoard.
For more information about SteemitBoard, click here

If you no longer want to receive notifications, reply to this comment with the word STOP

Upvote this notification to help all Steemit users. Learn why here!

$0.00

1 vote