1. RPL数据定义
RLP编码的定义只处理以下2类底层数据：
- 字符串（string）是指字节数组。例如，空串”“，再如单词”cat”，以及句子”Lorem ipsum dolor sit amet, consectetur adipisicing elit”等。
- 列表（list）是一个可嵌套结构，里面可包含字符串和列表。例如，空列表[]，再如一个包含两个字符串的列表[“cat”,”dog”]，再比如嵌套列表的复杂列表[“cat”, [“puppy”, “cow”], “horse”, [[]], “pig”, [“”], “sheep”]。
所有的其他数据需要转换成上面两种数据才能够进行RLP编码。可以自定义转换规则，只要你按照这个规则你就可以自己解码比如说： key-value结构可以转换为列表：[[k1,v1],[k2,v2]…] 等。
2. RLP编码规则
RLP编码的重点是给原始数据前面添加若干字节的前缀，而且这个前缀是和数据的长度相关的，并且是递归的。
RLP编码中的长度是数据的实际存储空间的字节大小，去掉首位0的正整数，用大端模式表示的二进制格式表示。
RLP编码规定数据（字符串或列表）的长度的长度不得大于8字节。因为超过8字节后，一个字节的前缀就不能存储了。
字符串走这边：
如果字符串的长度是1个字节，并且它的值在[0x00, 0x7f] 范围之间，那么其RLP编码就是字符串本身。即前缀为空，用前缀代表字符串本身；
否则，如果一个字符串的长度是0-55字节，其RLP编码是前缀跟上(拼接)字符串本身，前缀的值是0x80加上字符串的长度。由于在该规则下，字符串的最大长度是55,因此前缀的最大值是0x80+55=0xb7，所以在本规则下前缀(第一个字节)的取值范围是[0x80, 0xb7]；
如果字符串的长度大于55个字节，其RLP编码是前缀跟上字符串的长度再跟上字符串本身。前缀的值是0xb7加上字符串长度的二进制形式的字节长度（即字符串长度的存储长度）。即用额外的空间存储字符串的长度，而前缀中只存字符串的长度的长度。例如一个长度是1024的字符串，字符串长度的二进制形式是\x04\x00，因此字符串长度的长度是2个字节，所以前缀应该是0xb7+2=0xb9，由此得到该字符串的RLP编码是\xb9\x04\x00再跟上字符串本身。因为字符串长度的长度最少需要1个字节存储，因此前缀的最小值是0xb7+1=0xb8；又由于长度的最大值是8个字节，因此前缀的最大值是0xb7+8=0xbf，因此在本规则下前缀的取值范围是[0xb8, 0xbf]；
列表走这边：
- 由于列表的任意嵌套的，因此列表的编码是递归的，先编码最里层列表，再逐步往外层列表编码。如果一个列表的总长度（payload，列表的所有项经过编码后拼接在一起的字节大小）是0-55字节，其RLP编码是前缀依次跟上列表中各项的RLP编码。前缀的值是0xc0加上列表的总长度。在本规则下前缀的取值范围是[0xc0, 0xf7]。本规则与规则2类似；
- 如果一个列表的总长度大于55字节，它的RLP编码是前缀跟上列表的长度再依次跟上列表中各元素项的RLP编码。前缀的值是0xf7加上列表总长度的长度。编码的第一个字节的取值范围是[0xf8, 0xff]。本规则与规则3类似
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)
3.解码规则
根据RLP编码规则和过程，RLP解码的输入一律视为二进制字符数组，其过程如下：
根据输入首字节数据，解码数据类型、实际数据长度和位置；
根据类型和实际数据，解码不同类型的数据；
继续解码剩余的数据；
其中，解码数据类型、实际数据类型和位置的规则如下：
如果首字节(prefix)的值在[0x00, 0x7f]范围之间，那么该数据是字符串，且字符串就是首字节本身；
如果首字节的值在[0x80, 0xb7]范围之间，那么该数据是字符串，且字符串的长度等于首字节减去0x80，且字符串位于首字节之后；
如果首字节的值在[0xb8, 0xbf]范围之间，那么该数据是字符串，且字符串的长度的字节长度等于首字节减去0xb7，数据的长度位于首字节之后，且字符串位于数据的长度之后；
如果首字节的值在[0xc0, 0xf7]范围之间，那么该数据是列表，在这种情况下，需要对列表各项的数据进行递归解码。列表的总长度（列表各项编码后的长度之和）等于首字节减去0xc0，且列表各项位于首字节之后；
如果首字节的值在[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
4. 总结
与其他序列化方法相比，RLP编码的优点在于使用了灵活的长度前缀来表示数据的实际长度，并且使用递归的方式能编码相当大的数据。
当接收或者解码经过RLP编码后的数据时，根据第1个字节就能推断数据的类型、大概长度和数据本身等信息。而其他的序列化方法， 不能根据第1个字节获得如此多的信息量。
