解码过程
解码是编码的逆过程，也就是将顺序(flat sequence)字节转化为嵌套树形结构(nested sequence)的过程。在重建树形结构的过程中，首先，根据长度前缀(Length Prefix)，也就是每个编码段的第一个字节，来推断数据的类型。然后，再读取该编码段的实际内容，进行解码。另外，由于RLP编码中的列表是一种嵌套结构，如果类型是列表，则需要进行递归解码。
长度前缀的处理规则
根据长度前缀(Length Prefix)的数值范围，其对应的类型及长度计算方法可以汇总为如下的表格。
| 长度前缀的范围 | 对应的类型 | 对应的长度 |
|---|---|---|
| [0x00-0x7f] | 数组(字符串)类型，且为单字的数组 | 1字节 |
| [0x80-0xb7] | 数组(字符串)类型，且为短数组(字符串) | 数组长度=“长度前缀”-0x80 |
| [0xb8-0xbf] | 数组(字符串)类型，且为长数组(字符串) | 获取数组的长度，需要两步：1) 数组长度的字节数 sz=Length Prefix-0xb8； 2) 取“长度前缀”后的sz的内容，就是数组长度的值 |
| [0xc0-0xf7] | 列表，且为短列表 | 列表长度=“长度前缀”-0xc0 |
| [0xf8-0xff] | 列表，且为长列表 | 获取列表的长度，需要两步：1）列表长度的字节数 sz=Length Prefix-0xf8；2). 取“长度前缀”后的sz的内容，就是列表长度的值 |
举例
以字节码 d0c88363617483646f6781b783646f6780为例，给出通过RLP解码的过程如下图所示。
图4：解码示例.png
- 首先，整体的长度前缀(Length Prefix)为D0，通过查表，可以确定出类型为“短列表”，列表长度=0xD0-0xC0=0x10，即为16个字节；
- 第一个子项的前缀0xC8，通过查表，对应的类型为“短列表”，列表长度=0xC8-0xC0=0x08；
a. 嵌套的第一个子项的前缀为0x83，对应的类型为数组(字符串)类型，且为短数组(字符串)，长度为0x83-0x80=3，内容为后续的3个字节，即为[0x61, 0x61, 0x74]=[c,a,t,]；
b. 嵌套的第二个子项的前缀为0x83，对应的类型为数组(字符串)类型，且为短数组(字符串)，长度为0x83-0x80=3，内容为后续的3个字节，即为[0x64, 0x6f, 0x67]=[d,o,g]； - 第二子项的前缀为0x81,通过查表，对应的类型为数组(字符串)类型，且为短数组(字符串)，长度为0x81-0x80=1, 内容为0xb7；
- 第三个子项的前缀为0x83，通过查表，对应的类型为数组(字符串)类型，且为短数组(字符串)，长度为0x83-0x80=3，内容为后续的3个字节，即为[0x64, 0x6f, 0x67]=[d,o,g]；
- 第四子项的前缀为0x80,通过查表，对应的类型为数组(字符串)类型，且为短数组(字符串)，长度为0x80-0x80=0，也就是一个空数组；
- 完成对nest sequence的构建，结果为<<[cat], [dog]>, 0xb7, [dog], []>>。
代码实现分析
上面给出了RLP解码过程的图形化分析，下面简要地对比不同语言版本对于RLP解码实现。首先是Aleth，Aleth是以太坊的C++客户端，并包含了一系列的工具库。Aleth采用了“迭代器Iterator模式”来实现对RLP的解码。其优点是，通过迭代器可以对每个子项进行动态地、迭代地的部分解码，是一种比较高效的解码方法。对应的C++ class文件在libdevcore/RLP.cpp中，详见链接【3】。
第二种实现方式是ethereumj提供的RLP解码方式，ethereumj是以太坊协议的JAVA实现。ethereumj中采用了递归的方法对RLP编码实现全解码，也就是对于输入的flat sequence，进行一次性解码，生成对应的RLP对象。在ethereumj的实现中，首先定义了如下图所示的RLP树结构。
图5：RLP对象结构.png
在ethereumj，进行全解码的递归函数fullTraverse的关键代码如下，即先按照长度前缀规则(Length Prefix)确定RLP的类型，也就是表1中各个类型的分支。需要注意的是，其中对于List类型，通过对fullTraverse递归，实现对RLP的嵌套解码。
static void fullTraverse(byte[] msgData, int level, int startPos,
int endPos, RLPList rlpList, int depth) {
if (msgData == null || msgData.length == 0)
return;
int pos = startPos;
while (pos < endPos) {
// It's a list with a payload more than 55 bytes
// data[0] - 0xF7 = how many next bytes allocated
// for the length of the list
if ((msgData[pos] & 0xFF) > OFFSET_LONG_LIST) {
byte lengthOfLength = (byte) (msgData[pos] - OFFSET_LONG_LIST);
int length = calcLength(lengthOfLength, msgData, pos);
byte[] rlpData = new byte[lengthOfLength + length + 1];
System.arraycopy(msgData, pos, rlpData, 0, lengthOfLength
+ length + 1);
if (level + 1 < depth) {
RLPList newLevelList = new RLPList();
newLevelList.setRLPData(rlpData);
fullTraverse(msgData, level + 1, pos + lengthOfLength + 1,
pos + lengthOfLength + length + 1, newLevelList, depth);
rlpList.add(newLevelList);
} else {
rlpList.add(new RLPItem(rlpData));
}
pos += lengthOfLength + length + 1;
continue;
}
// It's a list with a payload less than 55 bytes
if ((msgData[pos] & 0xFF) >= OFFSET_SHORT_LIST
&& (msgData[pos] & 0xFF) <= OFFSET_LONG_LIST) {
byte length = (byte) ((msgData[pos] & 0xFF) - OFFSET_SHORT_LIST);
byte[] rlpData = new byte[length + 1];
System.arraycopy(msgData, pos, rlpData, 0, length + 1);
if (level + 1 < depth) {
RLPList newLevelList = new RLPList();
newLevelList.setRLPData(rlpData);
if (length > 0)
fullTraverse(msgData, level + 1, pos + 1, pos + length + 1, newLevelList, depth);
rlpList.add(newLevelList);
} else {
rlpList.add(new RLPItem(rlpData));
}
pos += 1 + length;
continue;
}
// It's an item with a payload more than 55 bytes
// data[0] - 0xB7 = how much next bytes allocated for
// the length of the string
if ((msgData[pos] & 0xFF) > OFFSET_LONG_ITEM
&& (msgData[pos] & 0xFF) < OFFSET_SHORT_LIST) {
byte lengthOfLength = (byte) (msgData[pos] - OFFSET_LONG_ITEM);
int length = calcLength(lengthOfLength, msgData, pos);
// now we can parse an item for data[1]..data[length]
byte[] item = new byte[length];
System.arraycopy(msgData, pos + lengthOfLength + 1, item,
0, length);
RLPItem rlpItem = new RLPItem(item);
rlpList.add(rlpItem);
pos += lengthOfLength + length + 1;
continue;
}
// It's an item less than 55 bytes long,
// data[0] - 0x80 == length of the item
if ((msgData[pos] & 0xFF) > OFFSET_SHORT_ITEM
&& (msgData[pos] & 0xFF) <= OFFSET_LONG_ITEM) {
byte length = (byte) ((msgData[pos] & 0xFF) - OFFSET_SHORT_ITEM);
byte[] item = new byte[length];
System.arraycopy(msgData, pos + 1, item, 0, length);
if (length == 1 && (item[0] & 0xFF) < OFFSET_SHORT_ITEM) {
throw new RuntimeException("Single byte has been encoded as byte string");
}
RLPItem rlpItem = new RLPItem(item);
rlpList.add(rlpItem);
pos += 1 + length;
continue;
}
// null item
if ((msgData[pos] & 0xFF) == OFFSET_SHORT_ITEM) {
byte[] item = ByteUtil.EMPTY_BYTE_ARRAY;
RLPItem rlpItem = new RLPItem(item);
rlpList.add(rlpItem);
pos += 1;
continue;
}
// single byte item
if ((msgData[pos] & 0xFF) < OFFSET_SHORT_ITEM) {
byte[] item = {(byte) (msgData[pos] & 0xFF)};
RLPItem rlpItem = new RLPItem(item);
rlpList.add(rlpItem);
pos += 1;
}
}
}
RLP序列化方法的讨论
关于为什么以太坊需要单独设计一种新的序列化协议，目前还没有找到官方的描述，但与其他序列化方法相比，可以观察出其直接的优点，
首先，对于编码效率上
- RLP使用了灵活的长度前缀来表示数据的实际长度，单字节直接编码，短数组/短列表(short array/short list)采用短的长度前缀，长数组/短列表(long array/long list)采用长的长度前缀，可以保证高的编码效率，提高内存和存储效率。
- 长度前缀(Length Prefix)同时包含了对应的"类型"和"长度信息"，提高了编码中前缀字符的效率；
- 使用递归的方式，可以一次性编码相当大的数据内容。
其次，对于以太坊数据的特殊性上，
- 由于以太坊对于所有节点的“数据共识Consensus”的要求，为了防止出现数据的不一致，在以太坊中，并不支持浮点数类型，其他的序列化方法，并不能直接使用；
- 以太坊中采用的货币单位非常小，比如Wei，并且1 ETH = 10^18 Wei，所以在编码中，需要考虑对很大的整数类型的序列化，在RLP中采用去除前导零(leading zero)的大端big-endian方式，可以有效处理大整数。
参考链接
【1】Ethereum Wiki: https://en.wikipedia.org/wiki/Ethereum
【2】Ethereum Yellow Paper: https://ethereum.github.io/yellowpaper/paper.pdf
【3】ALETH：https://github.com/ethereum/aleth
【4】Ethereumj: https://github.com/ethereum/ethereumj
