GitHub上介紹(解碼部分為本人編輯): https://github.com/ethereum/wiki/wiki/RLP

本文同時(shí)在個(gè)人CSDN博客發(fā)布: RLP編碼和解碼

RLP(Recursive Length Prefix，遞歸的長(zhǎng)度前綴)是一種編碼規(guī)則，可用于編碼任意嵌套的二進(jìn)制數(shù)組數(shù)據(jù)。RLP編碼的結(jié)果也是二進(jìn)制序列。RLP主要用來(lái)序列化/反序列化數(shù)據(jù)。

1. RLP數(shù)據(jù)定義

RLP編碼的定義只處理以下兩類(lèi)數(shù)據(jù)：

• 字符串（string）是指字節(jié)數(shù)組。例如，空串""，再如單詞"cat"，以及句子"Lorem ipsum dolor sit amet, consectetur adipisicing elit"等。

• 列表（list）是一個(gè)可嵌套結(jié)構(gòu)，里面可包含字符串和列表。例如，空列表[]，再如一個(gè)包含兩個(gè)字符串的列表["cat","dog"]，在比如嵌套列表的復(fù)雜列表["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"]。

其他類(lèi)型的數(shù)據(jù)需要轉(zhuǎn)成以上的兩類(lèi)數(shù)據(jù)，才能編碼。轉(zhuǎn)換的規(guī)則RLP編碼不統(tǒng)一規(guī)定，可以自定義轉(zhuǎn)換規(guī)則。例如struct可以轉(zhuǎn)成列表，int可以轉(zhuǎn)成二進(jìn)制序列（屬于字符串這一類(lèi), 必須去掉首部0，必須用大端模式表示）。

從上面的數(shù)據(jù)類(lèi)型定義中可以看出，RLP編碼的數(shù)據(jù)是可嵌套的。從RLP編碼的名字可以看出，RLP編碼是遞歸的，這一點(diǎn)從下面的規(guī)則和代碼可以看出。

2. RLP編碼規(guī)則

RLP編碼的重點(diǎn)是給數(shù)據(jù)前面添加一個(gè)字節(jié)的前綴，而這個(gè)前綴是和數(shù)據(jù)的長(zhǎng)度相關(guān)的。

RLP編碼中的長(zhǎng)度是數(shù)據(jù)的實(shí)際存儲(chǔ)空間的字節(jié)大小，去掉首位0的正整數(shù)，用大端模式表示的二進(jìn)制格式表示。

RLP編碼規(guī)定數(shù)據(jù)（字符串或列表）的長(zhǎng)度的長(zhǎng)度不得大于8字節(jié)。因?yàn)槌^(guò)8字節(jié)后，一個(gè)字節(jié)的前綴就不能存儲(chǔ)了。

1. 如果字符串的長(zhǎng)度是1個(gè)字節(jié)，并且它的值在[0x00, 0x7f] 范圍之間，那么其RLP編碼就是字符串本身。即前綴為空，用前綴代表字符串本身；

2. 否則，如果一個(gè)字符串的長(zhǎng)度是0-55字節(jié)，其RLP編碼是前綴跟上(拼接)字符串本身，前綴的值是0x80加上字符串的長(zhǎng)度。由于在該規(guī)則下，字符串的最大長(zhǎng)度是55,因此前綴的最大值是0x80+55=0xb7，所以在本規(guī)則下前綴(第一個(gè)字節(jié))的取值范圍是[0x80, 0xb7]；

3. 如果字符串的長(zhǎng)度大于55個(gè)字節(jié)，其RLP編碼是前綴跟上字符串的長(zhǎng)度再跟上字符串本身。前綴的值是0xb7加上字符串長(zhǎng)度的二進(jìn)制形式的字節(jié)長(zhǎng)度（即字符串長(zhǎng)度的存儲(chǔ)長(zhǎng)度）。即用額外的空間存儲(chǔ)字符串的長(zhǎng)度，而前綴中只存字符串的長(zhǎng)度的長(zhǎng)度。例如一個(gè)長(zhǎng)度是1024的字符串，字符串長(zhǎng)度的二進(jìn)制形式是\x04\x00，因此字符串長(zhǎng)度的長(zhǎng)度是2個(gè)字節(jié)，所以前綴應(yīng)該是0xb7+2=0xb9，由此得到該字符串的RLP編碼是\xb9\x04\x00再跟上字符串本身。因?yàn)樽址L(zhǎng)度的長(zhǎng)度最少需要1個(gè)字節(jié)存儲(chǔ)，因此前綴的最小值是0xb7+1=0xb8；又由于長(zhǎng)度的最大值是8個(gè)字節(jié)，因此前綴的最大值是0xb7+8=0xbf，因此在本規(guī)則下前綴的取值范圍是[0xb8, 0xbf]；

4. 以上3個(gè)規(guī)則是針對(duì)字符串的，接下來(lái)的兩個(gè)規(guī)則針對(duì)列表的。由于列表的任意嵌套的，因此列表的編碼是遞歸的，先編碼最里層列表，再逐步往外層列表編碼。如果一個(gè)列表的總長(zhǎng)度（payload，列表的所有項(xiàng)經(jīng)過(guò)編碼后拼接在一起的字節(jié)大?。┦?-55字節(jié)，其RLP編碼是前綴依次跟上列表中各項(xiàng)的RLP編碼。前綴的值是0xc0加上列表的總長(zhǎng)度。在本規(guī)則下前綴的取值范圍是[0xc0, 0xf7]。本規(guī)則與規(guī)則2類(lèi)似；

5. 如果一個(gè)列表的總長(zhǎng)度大于55字節(jié)，它的RLP編碼是前綴跟上列表的長(zhǎng)度再依次跟上列表中各元素項(xiàng)的RLP編碼。前綴的值是0xf7加上列表總長(zhǎng)度的長(zhǎng)度。編碼的第一個(gè)字節(jié)的取值范圍是[0xf8, 0xff]。本規(guī)則與規(guī)則3類(lèi)似；

代碼如下：

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) <= 0x7f: 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)

3. RLP編碼舉例

• 整數(shù) 0('\x00') = [0x00] （規(guī)則一）

• 整數(shù) 1024('\x04\00') = [0x82, 0x04, 0x00] （規(guī)則二）

• 空字符串('null') = 0x80 （規(guī)則二）

• 字符串 "dog" = [0x83, 'd', 'o', 'g' ] （規(guī)則二）

• 字符串 "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't'] （規(guī)則三）

• 空列表 [] = [0xc0] （規(guī)則四）

• 列表 ["cat","dog"] = [0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ] （規(guī)則四）

• 嵌套列表 [ [], [[]], [ [], [[]] ] ] = [0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0] （規(guī)則四）

4. RLP解碼規(guī)則

根據(jù)RLP編碼規(guī)則和過(guò)程，RLP解碼的輸入一律視為二進(jìn)制字符數(shù)組，其過(guò)程如下：

1. 根據(jù)輸入首字節(jié)數(shù)據(jù)，解碼數(shù)據(jù)類(lèi)型、實(shí)際數(shù)據(jù)長(zhǎng)度和位置；

2. 根據(jù)類(lèi)型和實(shí)際數(shù)據(jù)，解碼不同類(lèi)型的數(shù)據(jù)；

3. 繼續(xù)解碼剩余的數(shù)據(jù)；

其中，解碼數(shù)據(jù)類(lèi)型、實(shí)際數(shù)據(jù)類(lèi)型和位置的規(guī)則如下：

1. 如果首字節(jié)(prefix)的值在[0x00, 0x7f]范圍之間，那么該數(shù)據(jù)是字符串，且字符串就是首字節(jié)本身；

2. 如果首字節(jié)的值在[0x80, 0xb7]范圍之間，那么該數(shù)據(jù)是字符串，且字符串的長(zhǎng)度等于首字節(jié)減去0x80，且字符串位于首字節(jié)之后；

3. 如果首字節(jié)的值在[0xb8, 0xbf]范圍之間，那么該數(shù)據(jù)是字符串，且字符串的長(zhǎng)度的字節(jié)長(zhǎng)度等于首字節(jié)減去0xb7，數(shù)據(jù)的長(zhǎng)度位于首字節(jié)之后，且字符串位于數(shù)據(jù)的長(zhǎng)度之后；

4. 如果首字節(jié)的值在[0xc0, 0xf7]范圍之間，那么該數(shù)據(jù)是列表，在這種情況下，需要對(duì)列表各項(xiàng)的數(shù)據(jù)進(jìn)行遞歸解碼。列表的總長(zhǎng)度（列表各項(xiàng)編碼后的長(zhǎng)度之和）等于首字節(jié)減去0xc0，且列表各項(xiàng)位于首字節(jié)之后；

5. 如果首字節(jié)的值在[0xf8, 0xff]范圍之間，那么該數(shù)據(jù)為列表，列表的總長(zhǎng)度的字節(jié)長(zhǎng)度等于首字節(jié)減去0xf7，列表的總長(zhǎng)度位于首字節(jié)之后，且列表各項(xiàng)位于列表的總長(zhǎng)度之后；

代碼如下：

def rlp_decode(input):
    if len(input) == 0:
        return
    output = ''
    (offset, dataLen, type) = decode_length(input)
    if type is str:
        output = instantiate_str(substr(input, offset, dataLen))
    elif type is list:
        output = instantiate_list(substr(input, offset, dataLen))
    output + rlp_decode(substr(input, offset + dataLen))
    return output

def decode_length(input):
    length = len(input)
    if length == 0:
        raise Exception("input is null")
    prefix = ord(input[0])
    if prefix <= 0x7f:
        return (0, 1, str)
    elif prefix <= 0xb7 and length > prefix - 0x80:
        strLen = prefix - 0x80
        return (1, strLen, str)
    elif prefix <= 0xbf and length > prefix - 0xb7 and length > prefix - 0xb7 + to_integer(substr(input, 1, prefix - 0xb7)):
        lenOfStrLen = prefix - 0xb7
        strLen = to_integer(substr(input, 1, lenOfStrLen))
        return (1 + lenOfStrLen, strLen, str)
    elif prefix <= 0xf7 and length > prefix - 0xc0:
        listLen = prefix - 0xc0;
        return (1, listLen, list)
    elif prefix <= 0xff and length > prefix - 0xf7 and length > prefix - 0xf7 + to_integer(substr(input, 1, prefix - 0xf7)):
        lenOfListLen = prefix - 0xf7
        listLen = to_integer(substr(input, 1, lenOfListLen))
        return (1 + lenOfListLen, listLen, list)
    else:
        raise Exception("input don't conform RLP encoding form")

def to_integer(b)
    length = len(b)
    if length == 0:
        raise Exception("input is null")
    elif length == 1:
        return ord(b[0])
    else:
        return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256

5. 總結(jié)

與其他序列化方法相比，RLP編碼的優(yōu)點(diǎn)在于，當(dāng)接收或者解碼經(jīng)過(guò)RLP編碼后的數(shù)據(jù)時(shí)，根據(jù)第1個(gè)字節(jié)就能推斷數(shù)據(jù)的類(lèi)型、大概長(zhǎng)度和數(shù)據(jù)本身等信息。并且能編碼相當(dāng)大的數(shù)據(jù)。而其他的序列化方法， 不能根據(jù)第1個(gè)字節(jié)獲得如此多的信息量。