摘要：，遞歸長度前綴編碼，它是以太坊序列化所采用的序列化和反序列化的主要方式。其中的編碼為的編碼為。兩個子字符串的編碼后總長度是，因此編碼結果第一位計算得出。上面就是的編碼定義，下面開始我們來看一下以太坊中的實現源碼。

RLP(Recursive Length Prefix)，遞歸長度前綴編碼，它是以太坊序列化所采用的序列化和反序列化的主要方式。區塊、交易等數據結構在 網絡傳輸和持久化時會先經過RLP編碼后再存儲到數據庫中。rlp適用于任意的二進制數據數組的編碼，在以太坊中，rpl接受的數據分為兩類：1.字節數組 2.類list數據結構。

以太坊中rlp的具體定義和規則我們可以在黃皮書中找到（Appendix B. Recursive Length Prefix）：

序列化定義

* **O** 所有byte的集合
* **B** 所有可能字節數組
* **L** 不只單一節點的樹形結構（比如結構體或者樹節點分支節點，非葉子節點）
* **T** 所有字節數組的樹形結構組合

序列化處理

通過兩個子函數定義RLP分別處理上面說的兩種數據類型

Rb(x)字節數組序列化處理規則

如果字節數組只包含一個字節（對于 [0x00, 0x7f] 范圍內的單個字節），而且這個字節的大小小于128，那么不對數據進行處理，處理結果就是原數據，比如:a的編碼是97。

如果字節數組的長度小于56，那么處理結果就等于在原始數據前面加上（128+字節數據的長度)的前綴,比如abc編碼結果是131 97 98 99，其中131=128+len("abc")，97 98 99依次是a b c。

如果不是上面兩種情況，那么處理結果就等于在原始數據前面加上原始數據長度的大端表示，然后在前面加上（183 + 原始數據大端表示的長度)，比如編碼下面這段字符串The length of this sentence is more than 55 bytes, I know it because I pre-designed it編碼結果如下184 86 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 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 100 32 105 116,其中前三個字節的計算方式如下:1. 184 = 183 + 1，因為數組長度86編碼后僅占用一個字節; 2. 86即數組長度86

關于**大端小端**的理解可以參考[《理解字節序》](http://www.ruanyifeng.com/blog/2016/11/byte-order.html)比較淺顯易懂。關于公式中的一些數學符號的解釋：
* ||x|| 代表了求x的長度
* (a).（b,c).(d,e) = (a,b,c,d,e) 代表了concat的操作，也就是字符串的相加操作。 "hello "+"world" = "hello world"
* BE(x)函數表示**去掉了前導0的大端模式**。 比如4個字節的整形0x1234用大端模式來表示是 00 00 12 34 那么用BE函數處理之后返回的其實是 12 34. 開頭的多余的00被去掉了。
* ^ 符號代表并且的含義。
* ≡ ，恒等于

Rl(x) 其他類型(樹型結構)數據序列化處理規則

* 如果連接后的字節長度小于56， 那么在連接后的結果前面加上(192 + 連接后的長度)，組成最終的結果。**比如：["abc", "def"]的編碼結果是200 131 97 98 99 131 100 101 102。其中abc的編碼為131 97 98 99,def的編碼為131 100 101 102。兩個子字符串的編碼后總長度是8，因此編碼結果第一位計算得出：192 + 8 = 200**。
* 如果連接后的字節長度大于等于56， 那么就在連接后的結果前面先加上連接后的長度的大端模式，然后在前面加上(247 + 連接后長度的大端模式的長度)**比如：`["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]`的編碼結果是:`248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 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 100 32 105 116`,其中前兩個字節的計算方式如下:1. 248 = 247 +1; 2. 88 = 86 + 2，在`Rb(x)3`示例中，長度為86，而在此例中，由于有兩個子字符串，每個子字符串本身的長度的編碼各占1字節，因此總共占2字節。第3個字節179依據`Rb(x)規則2`得出179 = 128 + 51 第55個字節163同樣`Rb(x)2`得出163 = 128 + 35**

上面是一個遞歸的定義， 在求取s(x)的過程中又調用了RLP方法，這樣使得RLP能夠處理遞歸的數據結構。通過一個復雜的例子來理解一下遞歸長度前綴：
`["abc",["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]]`
編碼后的結果：
`248 94 131 97 98 99 248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 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 100 32 105 116`
列表第一項字符串abc依據`Rb(x)規則2`，編碼結果為131 97 98 99,長度為4。
列表第二項也是一個列表項：
`["The length of this sentence is more than 55 bytes, ", "I know it because I pre-designed it"]`
根據`Rl(x)規則2`，結果為
`248 88 179 84 104 101 32 108 101 110 103 116 104 32 111 102 32 116 104 105 115 32 115 101 110 116 101 110 99 101 32 105 115 32 109 111 114 101 32 116 104 97 110 32 53 53 32 98 121 116 101 115 44 32 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 100 32 105 116`
長度為90，因此，整個列表的編碼結果第二位是90 + 4 = 94, 占用1個字節，第一位247 + 1 = 248

標量數據處理

使用RLP處理標量數據,也就是基本的數據，RLP只能夠用來處理正整數。 RLP只能處理大端模式處理后的整數。 也就是說如果是一個整數x，那么先使用BE(x)函數來把x轉換成最簡大端模式(去掉了開頭的00),然后把BE(x)的結果當成是字節數組來進行編碼。

上面就是RLP的編碼定義，下面開始我們來看一下以太坊中的實現源碼。

rlp
├── decode.go               // 解碼器
├── decode_tail_test.go     // 解碼示例
├── decode_test.go          // 解碼器測試用例
├── doc.go                  // 文檔代碼
├── encode.go               // 編碼器
├── encode_test.go          // 編碼器測試用例
├── encoder_example_test.go // 編碼器示例
├── raw.go                  // 處理編碼后rlp數據，比如計算長度、分離、值計數等
├── raw_test.go             // raw測試用例
└── typecache.go            // 類型緩存，記錄數據類型->編碼器|解碼器的映射

可以直接從示例 encoder_example_test.go 中來看，這個示例中實現了一個如何通過rlp編碼struct的調用：

type MyCoolType struct {
    Name string
    a, b uint
}

func (x *MyCoolType) EncodeRLP(w io.Writer) (err error) {
    if x == nil {
    // 結構體為空指針，編碼{0, 0}
        err = Encode(w, []uint{0, 0})
    } else {
    // 編碼指定的值
        err = Encode(w, []uint{x.a, x.b})
    }
    return err
}

func ExampleEncoder() {
    var t *MyCoolType 
    bytes, _ := EncodeToBytes(t)   // t MyCoolType為nil編碼為字節數組
    fmt.Printf("%v → %X
", t, bytes)

    t = &MyCoolType{Name: "foobar", a: 5, b: 6}
    bytes, _ = EncodeToBytes(t)    // t 為struct
    fmt.Printf("%v → %X
", t, bytes)

    // Output:
    //  → C28080
    // &{foobar 5 6} → C20506
}

通過上面的測試用例代碼，可以看到EncodeToBytes就是編碼的函數，往下走，看一下編碼器具體實現 encode.go：

var (
    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
}

首先定義了空字符串和空列表的值，定義了Encoder接口，我們可以看到上面的MyCoolType就實現了該接口的EncodeRLP方法，繼續往下看EncodeToBytes的具體實現：

// EncodeToBytes 返回RLP編碼后的值.
func EncodeToBytes(val interface{}) ([]byte, error) {
    eb := encbufPool.Get().(*encbuf)   // 從encbufPool池中獲取encbuf實例
    defer encbufPool.Put(eb)           // 調用結束以后重新放入池中
    eb.reset()                         // 初始化encbuf
    if err := eb.encode(val); err != nil { // 對數據編碼
        return nil, err
    }
    return eb.toBytes(), nil   //將編碼后的數據和頭部拼接成byte[]后返回
}

encbufPool是一個sync.Pool,可以通過一個資源池來提高編碼效率，減少資源浪費。來看下encbuf的結構定義:

type encbuf struct {
    str     []byte      // 包含了除了列表的頭部的所有的編碼的內容
    lheads  []*listhead // 所有的列表頭
    lhsize  int         // lheads的長度
    sizebuf []byte      // 9個字節大小的輔助buffer，用來處理uint的編碼
}

type listhead struct {
    offset int // 記錄了列表數據在str字段的起始位置
    size   int // 編碼數據的總長度 (包括列表頭)
}

encbuf看起來是在編碼過程的一個buffer的作用，其定義了一些encode過程中的操作方法,具體每個函數的實現不做代碼分析了，這里大略說一下每個函數的作用：

encode(val interface{}) error 編碼函數

(w *encbuf) encodeString(b []byte) 將編碼后的原始數據連接到已編碼內容之后

encodeStringHeader(size int) 將頭部結構體中新編碼后的元素和之前已經編碼的內容連接

list() *listhead 保存每個元素編碼后的頭部lheads信息

listEnd(lh *listhead) 編碼連接后的長度lhsize統計

reset() encbuf 初始化

size() int 計算編碼后內容和頭部長度之和

toBytes() []byte 將每個頭部lheads連接到對應的編碼數據后

toWriter(out io.Writer) (err error) 通過io流將編碼后頭部寫到編碼后，

Write(b []byte) (int, error) 實現io.Writer接口，以便于可以傳入EncodeRLP

繼續上面的EncodeToBytes函數，我來看一下eb.encode(val)編碼函數具體做了什么：

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)
}

首先通過reflect反射機制獲取編碼值的類型，后和tags一起傳入cachedTypeInfo，往下看cachedTypeInfo做了什么typecache.go：

var (
    typeCacheMutex sync.RWMutex    // 讀寫鎖
    typeCache      = make(map[typekey]*typeinfo)// 類型->編碼|解碼函數的映射，不同的數據類型對應不同的編碼和解碼方法
)

type typeinfo struct {
    decoder    // 解碼
    writer     // 編碼
}

type tags struct {
    nilOK bool     // 是否為空值
    tail bool      // 該字段是否含其他列表元素。它只能設置為最后一個字段，該字段必須是切片類型。
    ignored bool   // 是否忽略
}

type typekey struct {
    reflect.Type   // 數據類型
    tags   // 根據tags可能會生成不同的解碼器。
}

type decoder func(*Stream, reflect.Value) error

type writer func(reflect.Value, *encbuf) error

func cachedTypeInfo(typ reflect.Type, tags tags) (*typeinfo, error) {
    typeCacheMutex.RLock() // 加讀鎖
    info := typeCache[typekey{typ, tags}]  // 從緩存中獲取編碼解碼器
    typeCacheMutex.RUnlock()
    if info != nil {
        return info, nil
    }
    // 緩存中沒有時通過type和tags生成編碼解碼器
    typeCacheMutex.Lock()
    defer typeCacheMutex.Unlock()
    return cachedTypeInfo1(typ, tags)
}

cachedTypeInfo函數主要是從緩存中來根據數據類型來獲取編碼解碼器，如果不存在時就通過cachedTypeInfo1 來創建一個對應類型的編碼解碼器，這里需要注意的typeCacheMutex 進程鎖來避免多線程資源保護和互斥，下面繼續看下cachedTypeInfo1如何根據typekey來創建typeinfo的：

func cachedTypeInfo1(typ reflect.Type, tags tags) (*typeinfo, error) {
    key := typekey{typ, tags}
    info := typeCache[key]
    if info != nil {
        // 另外一個協程首先獲得鎖，再次驗證避免多進程并發請求
        return info, nil
    }

    typeCache[key] = new(typeinfo)
    info, err := genTypeInfo(typ, tags)
    if err != nil {
        // 生成失敗清除空間
        delete(typeCache, key)
        return nil, err
    }
    *typeCache[key] = *info
    return typeCache[key], err
}

該函數并不是實際創建緩存的函數，其中調用了genTypeInfo函數，順著往下看:

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
}

顯而易見，這里分別調用makeDecoder和makeWriter來創建解碼和編碼，我們來看下編碼器的實現encode.go:

// 通過類型和tags創建對應的具體編碼函數
func makeWriter(typ reflect.Type, ts tags) (writer, error) {
    kind := typ.Kind()
    switch {
    case typ == rawValueType:
        return writeRawValue, nil
    case typ.Implements(encoderInterface):
        return writeEncoder, nil
    case kind != reflect.Ptr && reflect.PtrTo(typ).Implements(encoderInterface):
        return writeEncoderNoPtr, nil
    case kind == reflect.Interface:
        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.Bool:
        return writeBool, nil
    case kind == reflect.String:
        return writeString, nil
    case kind == reflect.Slice && isByte(typ.Elem()):
        return writeBytes, nil
    case kind == reflect.Array && isByte(typ.Elem()):
        return writeByteArray, nil
    case kind == reflect.Slice || kind == reflect.Array:
        return makeSliceWriter(typ, ts)
    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)
    }
}

這個函數很簡單，通過type來設置對應的具體編碼器，注意一下ts也就是tags參數，只有類型為slice和array時候才會用到，具體每個類型對應的編碼器實現就不一一分析了，很值得每一個源碼看一下，加深一下對上面黃皮書定義的規則的理解。對于結構體的編碼在黃皮書中并沒有公式定義，我們來看下源碼了解一下:

type field struct {
    index int
    info  *typeinfo
}

func makeStructWriter(typ reflect.Type) (writer, error) {
    fields, err := structFields(typ) // 通過typ.NumField反射機制來解析struct結構，并獲取每個字段的解碼器
    if err != nil {
        return nil, err
    }
    writer := func(val reflect.Value, w *encbuf) error {
        lh := w.list()
        for _, f := range fields {
          //f是field結構， f.info是typeinfo的指針， 所以f.info.writer就是調用字段的編碼器方法
            if err := f.info.writer(val.Field(f.index), w); err != nil {
                return err
            }
        }
        w.listEnd(lh)
        return nil
    }
    return writer, nil
}

structFields 方法中通過reflect.Type的NumField獲取其Field，然后調用cachedTypeInfo1來獲取每個Field的編碼器，所以這是一個遞歸的調用。最后遍歷Field的數組fields，調用f.info.writer具體的編碼器來編碼。
我們繼續回到encoder_example_test.go來看下示例中

var t *MyCoolType 
bytes, _ := EncodeToBytes(t) 

這里的t是MyCoolType的一個指針，MyCoolType實現了EncodeRLP的接口，根據makeWriter中的case找到typ.Implements(encoderInterface)分支，調用了writeEncoder:

func writeEncoder(val reflect.Value, w *encbuf) error {
    return val.Interface().(Encoder).EncodeRLP(w)
}

這里直接調用了EncodeRLP(w)接口方法，從上面的示例代碼中看，那么就是調用Encode(w, []uint{0, 0}),我們上面分析過了，encbuf實現了io.Writer接口的Writer方法，這里的w就是encbuf：

func Encode(w io.Writer, val interface{}) error {
    if outer, ok := w.(*encbuf); ok {
       // 如果是*encbuf類型，則直接返回outer.encode
            return outer.encode(val)
    }
    
    eb := encbufPool.Get().(*encbuf)
    defer encbufPool.Put(eb)
    eb.reset()
    if err := eb.encode(val); err != nil {
        return err
    }
    w是io.Writer,eb.toWriter(w)流
    return eb.toWriter(w)
}

這樣一個rlp的編碼過程就解析完了，解碼就是一個逆向的過程，不繼續分析了，要理解黃皮書中的規則，還是需要看下makeWriter中的每一個類型對應的編碼的具體實現代碼。

轉載請注明： 轉載自Ryan是菜鳥 | LNMP技術棧筆記

如果覺得本篇文章對您十分有益，何不 打賞一下

本文鏈接地址: 以太坊源碼分析--RLP編碼