引介

RLP 编码和解码

Albert   |     |   2469 次阅读

RLP编码和解码

RLP(Recursive Length Prefix,递归的长度前缀)是一种编码规则,可用于编码任意嵌套的二进制数组数据。RLP编码的结果也是二进制序列。RLP主要用来序列化/反序列化数据。

RLP数据定义

RLP编码的定义只处理以下两类数据:

  • 字符串(string)是指字节数组。例如,空串"",再如单词"cat",以及句子"Lorem ipsum dolor sit amet, consectetur adipisicing elit"等。

  • 列表(list)是一个可嵌套结构,里面可包含字符串和列表。例如,空列表[],再如一个包含两个字符串的列表["cat","dog"],在比如嵌套列表的复杂列表["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"]。

其他类型的数据需要转成以上的两类数据,才能编码。转换的规则RLP编码不统一规定,可以自定义转换规则。例如struct可以转成列表,int可以转成二进制序列(属于字符串这一类, 必须去掉首部0,必须用大端模式表示)。

从上面的数据类型定义中可以看出,RLP编码的数据是可嵌套的。从RLP编码的名字可以看出,RLP编码是递归的,这一点从下面的规则和代码可以看出。

RLP编码规则

RLP编码的重点是给数据前面添加一个字节的前缀,而这个前缀是和数据的长度相关的。

RLP编码中的长度是数据的实际存储空间的字节大小,去掉首位0的正整数,用大端模式表示的二进制格式表示。

RLP编码规定数据(字符串或列表)的长度的长度不得大于8字节。因为超过8字节后,一个字节的前缀就不能存储了。

  1. 如果字符串的长度是1个字节,并且它的值在[0x00, 0x7f] 范围之间,那么其RLP编码就是字符串本身。即前缀为空,用前缀代表字符串本身;

  2. 否则,如果一个字符串的长度是0-55字节,其RLP编码是前缀跟上(拼接)字符串本身,前缀的值是0x80加上字符串的长度。由于在该规则下,字符串的最大长度是55,因此前缀的最大值是0x80+55=0xb7,所以在本规则下前缀(第一个字节)的取值范围是[0x80, 0xb7];

  3. 如果字符串的长度大于55个字节,其RLP编码是前缀跟上字符串的长度再跟上字符串本身。前缀的值是0xb7加上字符串长度的二进制形式的字节长度(即字符串长度的存储长度)。即用额外的空间存储字符串的长度,而前缀中只存字符串的长度的长度。例如一个长度是1024的字符串,字符串长度的二进制形式是\x04\x00,因此字符串长度的长度是2个字节,所以前缀应该是0xb7+2=0xb9,由此得到该字符串的RLP编码是\xb9\x04\x00再跟上字符串本身。因为字符串长度的长度最少需要1个字节存储,因此前缀的最小值是0xb7+1=0xb8;又由于长度的最大值是8个字节,因此前缀的最大值是0xb7+8=0xbf,因此在本规则下前缀的取值范围是[0xb8, 0xbf];

  4. 以上3个规则是针对字符串的,接下来的两个规则针对列表的。由于列表的任意嵌套的,因此列表的编码是递归的,先编码最里层列表,再逐步往外层列表编码。如果一个列表的总长度(payload,列表的所有项经过编码后拼接在一起的字节大小)是0-55字节,其RLP编码是前缀依次跟上列表中各项的RLP编码。前缀的值是0xc0加上列表的总长度。在本规则下前缀的取值范围是[0xc0, 0xf7]。本规则与规则2类似;

  5. 如果一个列表的总长度大于55字节,它的RLP编码是前缀跟上列表的长度再依次跟上列表中各元素项的RLP编码。前缀的值是0xf7加上列表总长度的长度。编码的第一个字节的取值范围是[0xf8, 0xff]。本规则与规则3类似;

代码如下:

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)

RLP编码举例

  • 整数 0('\x00') = [0x00] (规则一)

  • 整数 1024('\x04\00') = [0x82, 0x04, 0x00] (规则二)

  • 空字符串('null') = 0x80 (规则二)

  • 字符串 "dog" = [0x83, 'd', 'o', 'g' ] (规则二)

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

  • 空列表 [] = [0xc0] (规则四)

  • 列表 ["cat","dog"] = [0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ] (规则四)

  • 嵌套列表 [ [], [[]], [ [], [[]] ] ] = [0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0] (规则四)

RLP解码规则

根据RLP编码规则和过程,RLP解码的输入一律视为二进制字符数组,其过程如下:

  1. 根据输入首字节数据,解码数据类型、实际数据长度和位置;

  2. 根据类型和实际数据,解码不同类型的数据;

  3. 继续解码剩余的数据;

其中,解码数据类型、实际数据类型和位置的规则如下:

  1. 如果首字节(prefix)的值在[0x00, 0x7f]范围之间,那么该数据是字符串,且字符串就是首字节本身;

  2. 如果首字节的值在[0x80, 0xb7]范围之间,那么该数据是字符串,且字符串的长度等于首字节减去0x80,且字符串位于首字节之后;

  3. 如果首字节的值在[0xb8, 0xbf]范围之间,那么该数据是字符串,且字符串的长度的字节长度等于首字节减去0xb7,数据的长度位于首字节之后,且字符串位于数据的长度之后;

  4. 如果首字节的值在[0xc0, 0xf7]范围之间,那么该数据是列表,在这种情况下,需要对列表各项的数据进行递归解码。列表的总长度(列表各项编码后的长度之和)等于首字节减去0xc0,且列表各项位于首字节之后;

  5. 如果首字节的值在[0xf8, 0xff]范围之间,那么该数据为列表,列表的总长度的字节长度等于首字节减去0xf7,列表的总长度位于首字节之后,且列表各项位于列表的总长度之后;

代码如下:

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

文章所有权归作者个人所有,转载请注明作者及来源
参考资料:https://github.com/ethereum/wiki/wiki/RLP

 
1 人喜欢