RLP类源码分析 - ethereumj

RLP (递归长度前缀)提供了一种适用于任意二进制数据数组的编码，RLP已经成为以太坊中对对象进行序列化的主要编码方式。RLP的唯一目标就是解决结构体的编码问题；对原子数据类型（比如，字符串，整数型，浮点型）的编码则交给更高层的协议；以太坊中要求数字必须是一个大端字节序的、没有零占位的存储的格式（也就是说，一个整数0和一个空数组是等同的）。

如果有人希望使用RLP对字典进行编码，两个建议的规范形式，一种是通过二维数组表达键值对，比如[[k1,v1],[k2,v2]...]，并且对键进行字典序排序；或者使用更高级别的Patricia Tree编码来实现。

定义

RLP编码功能需要一个item。一个item定义如下：

将一个字符串作为一个item（比如，一个 byte 数组）
一组item列表（list）作为一个item

例如，一个空字符串可以是一个item，一个字符串"cat"也可以是一个item，一个含有多个字符串的列表也行，复杂的数据结构也行，比如这样的["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]。注意在本文后续内容中，说"字符串"的意思其实就相当于"一个确定长度的二进制字节信息数据"；而不要假设或考虑关于字符的编码问题。

RLP 编码定义如下：

对于[0x00, 0x7f] 范围内的单个字节, RLP 编码内容就是字节内容本身。
否则，如果是一个 0-55 字节长的字符串，则RLP编码有一个特别的数值 0x80 加上字符串长度，再加上字符串二进制内容。这样，第一个字节的表达范围为 [0x80, 0xb7].
如果字符串长度超过 55 个字节，RLP 编码由定值 0xb7 加上字符串长度所占用的字节数，加上字符串长度的编码，加上字符串二进制内容组成。比如，一个长度为 1024 的字符串，将被编码为\xb9\x04\x00 后面再加上字符串内容。第一字节的表达范围是[0xb8, 0xbf]。
- 很多人到这里就晕了，不知道\xb9\x04\x00怎么来的，其实就是说：第一个字节0xb7为起始，加上表示长度所需的字节数。长度为1024，需要两个字节来表示。（单字节的范围是0-255）所以0xb7+2=0xb9，然后加上字符串的长度。字符串的长度为1024，十六进制为0x400，因此接下来的两个字节为0x40和0x00，之后就是字符串本身，所以。0xb94000或\xb9\x40\x00是长度1024字符串的前缀。理解了吧：0xb7 + 字符串长度所占用的字节数 + 字符串长度 = \xb9\x40\x00。
如果列表的内容（它的所有项的组合长度）是0-55个字节长，它的RLP编码由0xC0加上所有的项的RLP编码串联起来的长度得到的单个字节，后跟所有的项的RLP编码的串联组成。第一字节的范围因此是[0xc0, 0xf7]
如果列表的内容超过55字节，它的RLP编码由0xC0加上所有的项的RLP编码串联起来的长度的长度得到的单个字节，后跟所有的项的RLP编码串联起来的长度的长度，再后跟所有的项的RLP编码的串联组成。第一字节的范围因此是[0xf8, 0xff] 。

用java代码表达以上逻辑:

 public static byte[] encodeList(byte[]... elements) {

        if (elements == null) {
            return new byte[]{(byte) OFFSET_SHORT_LIST};
        }

        int totalLength = 0;
        for (byte[] element1 : elements) {
            totalLength += element1.length;
        }

        byte[] data;
        int copyPos;
        if (totalLength < SIZE_THRESHOLD) {

            data = new byte[1 + totalLength];
            data[0] = (byte) (OFFSET_SHORT_LIST + totalLength);
            copyPos = 1;
        } else {
            // length of length = BX
            // prefix = [BX, [length]]
            int tmpLength = totalLength;
            byte byteNum = 0;
            while (tmpLength != 0) {
                ++byteNum;
                tmpLength = tmpLength >> 8;
            }
            tmpLength = totalLength;
            byte[] lenBytes = new byte[byteNum];
            for (int i = 0; i < byteNum; ++i) {
                lenBytes[byteNum - 1 - i] = (byte) ((tmpLength >> (8 * i)) & 0xFF);
            }
            // first byte = F7 + bytes.length
            data = new byte[1 + lenBytes.length + totalLength];
            data[0] = (byte) (OFFSET_LONG_LIST + byteNum);
            System.arraycopy(lenBytes, 0, data, 1, lenBytes.length);

            copyPos = lenBytes.length + 1;
        }
        for (byte[] element : elements) {
            System.arraycopy(element, 0, data, copyPos, element.length);
            copyPos += element.length;
        }
        return data;
    }

用Python代码表达以上逻辑:

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and chr(input) < 128: return input
        else: return encode_length(len(input),128) + input
    elif isinstance(input,list):
        output = ''
        for item in input: output += rlp_encode(item)
        return encode_length(len(output),192) + 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):
    return '' if x == 0 else to_binary(int(x / 256)) + chr(x % 256)

例子

字符串 "dog" = [ 0x83, 'd', 'o', 'g' ]

列表 [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]

空字符串 ('null') = [ 0x80 ]

空列表 = [ 0xc0 ]

数字15 ('\x0f') = [ 0x0f ]

数字 1024 ('\x04\x00') = [ 0x82, 0x04, 0x00 ]

The set theoretical representation of two, [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]

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

RLP分析

以上我们可以看出RLP编码的设计思想，就是通过首字节快速判断一串编码的类型，充分利用了一个字节的存储空间，将0x7f以后的值赋予了新的含义，以往我们见到的编码方式主要是对指定长度字节进行编码，比如Unicode等，在处理这些编码时一般按照指定长度进行拆分解码，最大的弊端是传统编码无法表现一个结构，就是本文说的列表，RLP最大的优点是在充分利用字节的情况下，同时支持列表结构，也就是说可以很轻易的利用RLP存储一个树状结构。

程序处理RLP编码时也非常容易，根据首字节就可以判断出这段编码的类型，同时调用不同的方法进行解码，如果您熟悉jason这种结构，会发现RLP很类似，支持嵌套的结构，通过递归调用可以将整个RLP快速还原成一颗树，或者转译成一个jason结构，便于其他程序使用。

RLP使用首字节存储长度的位数，再用后续的字节表明整体字符串的长度，根据规则二计算，RLP可以支持的单个最大字符串长度为2的64次方，这无疑是个天文数字，再加上嵌套规则，所以理论上RLP可以编码任何数据。

RLP类源码分析 - ethereumj

定义

RLP 编码定义如下：

例子

RLP分析

昵称