解碼過程
解碼是編碼的逆過程递雀，也就是將順序(flat sequence)字節(jié)轉(zhuǎn)化為嵌套樹形結(jié)構(gòu)(nested sequence)的過程形纺。在重建樹形結(jié)構(gòu)的過程中，首先庐扫，根據(jù)長度前綴(Length Prefix)瞳脓，也就是每個編碼段的第一個字節(jié)塑娇，來推斷數(shù)據(jù)的類型。然后篡殷，再讀取該編碼段的實(shí)際內(nèi)容钝吮，進(jìn)行解碼。另外板辽，由于RLP編碼中的列表是一種嵌套結(jié)構(gòu)奇瘦，如果類型是列表，則需要進(jìn)行遞歸解碼劲弦。
長度前綴的處理規(guī)則
根據(jù)長度前綴(Length Prefix)的數(shù)值范圍耳标，其對應(yīng)的類型及長度計(jì)算方法可以匯總為如下的表格。
| 長度前綴的范圍 | 對應(yīng)的類型 | 對應(yīng)的長度 |
|---|---|---|
| [0x00-0x7f] | 數(shù)組(字符串)類型邑跪，且為單字的數(shù)組 | 1字節(jié) |
| [0x80-0xb7] | 數(shù)組(字符串)類型次坡，且為短數(shù)組(字符串) | 數(shù)組長度=“長度前綴”-0x80 |
| [0xb8-0xbf] | 數(shù)組(字符串)類型，且為長數(shù)組(字符串) | 獲取數(shù)組的長度画畅，需要兩步：1) 數(shù)組長度的字節(jié)數(shù) sz=Length Prefix-0xb8砸琅； 2) 取“長度前綴”后的sz的內(nèi)容，就是數(shù)組長度的值 |
| [0xc0-0xf7] | 列表轴踱，且為短列表 | 列表長度=“長度前綴”-0xc0 |
| [0xf8-0xff] | 列表症脂，且為長列表 | 獲取列表的長度，需要兩步：1）列表長度的字節(jié)數(shù) sz=Length Prefix-0xf8淫僻；2). 取“長度前綴”后的sz的內(nèi)容诱篷，就是列表長度的值 |
舉例
以字節(jié)碼 d0c88363617483646f6781b783646f6780為例，給出通過RLP解碼的過程如下圖所示雳灵。
- 首先棕所，整體的長度前綴(Length Prefix)為D0，通過查表悯辙，可以確定出類型為“短列表”琳省，列表長度=0xD0-0xC0=0x10迎吵，即為16個字節(jié)；
- 第一個子項(xiàng)的前綴0xC8岛啸，通過查表钓觉，對應(yīng)的類型為“短列表”茴肥，列表長度=0xC8-0xC0=0x08坚踩；
a. 嵌套的第一個子項(xiàng)的前綴為0x83，對應(yīng)的類型為數(shù)組(字符串)類型瓤狐，且為短數(shù)組(字符串)瞬铸，長度為0x83-0x80=3，內(nèi)容為后續(xù)的3個字節(jié)础锐，即為[0x61, 0x61, 0x74]=[c,a,t,]嗓节；
b. 嵌套的第二個子項(xiàng)的前綴為0x83，對應(yīng)的類型為數(shù)組(字符串)類型皆警，且為短數(shù)組(字符串)拦宣，長度為0x83-0x80=3，內(nèi)容為后續(xù)的3個字節(jié)信姓，即為[0x64, 0x6f, 0x67]=[d,o,g]鸵隧； - 第二子項(xiàng)的前綴為0x81,通過查表，對應(yīng)的類型為數(shù)組(字符串)類型意推，且為短數(shù)組(字符串)豆瘫，長度為0x81-0x80=1, 內(nèi)容為0xb7；
- 第三個子項(xiàng)的前綴為0x83菊值，通過查表外驱，對應(yīng)的類型為數(shù)組(字符串)類型，且為短數(shù)組(字符串)腻窒，長度為0x83-0x80=3昵宇，內(nèi)容為后續(xù)的3個字節(jié)，即為[0x64, 0x6f, 0x67]=[d,o,g]儿子；
- 第四子項(xiàng)的前綴為0x80,通過查表瓦哎，對應(yīng)的類型為數(shù)組(字符串)類型，且為短數(shù)組(字符串)典徊，長度為0x80-0x80=0杭煎，也就是一個空數(shù)組；
- 完成對nest sequence的構(gòu)建卒落，結(jié)果為<<[cat], [dog]>, 0xb7, [dog], []>>羡铲。
代碼實(shí)現(xiàn)分析
上面給出了RLP解碼過程的圖形化分析，下面簡要地對比不同語言版本對于RLP解碼實(shí)現(xiàn)儡毕。首先是Aleth也切，Aleth是以太坊的C++客戶端扑媚，并包含了一系列的工具庫。Aleth采用了“迭代器Iterator模式”來實(shí)現(xiàn)對RLP的解碼雷恃。其優(yōu)點(diǎn)是疆股，通過迭代器可以對每個子項(xiàng)進(jìn)行動態(tài)地、迭代地的部分解碼倒槐，是一種比較高效的解碼方法旬痹。對應(yīng)的C++ class文件在libdevcore/RLP.cpp中，詳見鏈接【3】讨越。
第二種實(shí)現(xiàn)方式是ethereumj提供的RLP解碼方式两残，ethereumj是以太坊協(xié)議的JAVA實(shí)現(xiàn)。ethereumj中采用了遞歸的方法對RLP編碼實(shí)現(xiàn)全解碼把跨，也就是對于輸入的flat sequence人弓，進(jìn)行一次性解碼，生成對應(yīng)的RLP對象着逐。在ethereumj的實(shí)現(xiàn)中崔赌，首先定義了如下圖所示的RLP樹結(jié)構(gòu)。
在ethereumj耸别，進(jìn)行全解碼的遞歸函數(shù)fullTraverse的關(guān)鍵代碼如下健芭，即先按照長度前綴規(guī)則(Length Prefix)確定RLP的類型，也就是表1中各個類型的分支太雨。需要注意的是吟榴，其中對于List類型，通過對fullTraverse遞歸囊扳，實(shí)現(xiàn)對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序列化方法的討論
關(guān)于為什么以太坊需要單獨(dú)設(shè)計(jì)一種新的序列化協(xié)議，目前還沒有找到官方的描述锥咸，但與其他序列化方法相比狭瞎，可以觀察出其直接的優(yōu)點(diǎn)，
首先搏予，對于編碼效率上
- RLP使用了靈活的長度前綴來表示數(shù)據(jù)的實(shí)際長度熊锭，單字節(jié)直接編碼，短數(shù)組/短列表(short array/short list)采用短的長度前綴雪侥，長數(shù)組/短列表(long array/long list)采用長的長度前綴碗殷，可以保證高的編碼效率，提高內(nèi)存和存儲效率速缨。
- 長度前綴(Length Prefix)同時包含了對應(yīng)的"類型"和"長度信息"锌妻，提高了編碼中前綴字符的效率；
- 使用遞歸的方式旬牲，可以一次性編碼相當(dāng)大的數(shù)據(jù)內(nèi)容。
其次，對于以太坊數(shù)據(jù)的特殊性上蝴光，
- 由于以太坊對于所有節(jié)點(diǎn)的“數(shù)據(jù)共識Consensus”的要求，為了防止出現(xiàn)數(shù)據(jù)的不一致堕仔，在以太坊中，并不支持浮點(diǎn)數(shù)類型晌区，其他的序列化方法摩骨，并不能直接使用；
- 以太坊中采用的貨幣單位非常小契讲，比如Wei仿吞，并且1 ETH = 10^18 Wei滑频，所以在編碼中捡偏，需要考慮對很大的整數(shù)類型的序列化，在RLP中采用去除前導(dǎo)零(leading zero)的大端big-endian方式峡迷，可以有效處理大整數(shù)银伟。
參考鏈接
【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
