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,因此接下来的两个字节为0x400x00,之后就是字符串本身,所以。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可以编码任何数据。






发表于: 9月前   最后更新时间: 2月前   游览量:855
上一条: ethereumj项目启动类加载步骤
下一条: Block类源码分析 - ethereumj

评论…


  • 评论…
    • in this conversation