[Russian] RLP

Идея рекурсивного линейного префикса (РЛП) — в том, чтобы кодировать произвольно вложенные массивы бинарной информации.

Если кому-либо вздумалось бы использовать РЛП в качестве словаря, то выглядело бы это так: [[k1,v1],[k2,v2]...], где k_i расположены в лексикографическом порядке. Или также можно было бы кодировать с помощью Patricia Tree, как это происходит в Эфириум.

Определение

На вход кодирующая функция РЛП берёт элемент. Элементом может быть:

• строка (байтовый массив)
• список элементов.

К примеру, пустая строка — элемент, равно как и строка, содержащая слово "котятки", как и список, содержащий любое количество строк или более сложных структур как ["cat",["puppy","cow"],"horse",[[]],"pig",[""],"sheep"]. До конца этой статьи слово "строка" используется как синоним оборота "определённый набор байтов бинарной информации"; никакой специальной кодировки или знания содержания строки не предполагается.

Кодирование РЛП происходит следующим образом:

• Для байта, значение которого находится в диапазоне [0x00, 0x7f], результатом РЛП-кодирования будет сам этот байт.
• В противном случае, если длина строки 0-55 байтов, результатом РЛП-кодирования будет байт, значение которого равно 0x80 плюс длина следующей строки. Видно, что этот байт будет лежать в следующем диапазоне: [0x80, 0xb7].
• Если длина строки больше, чем 55 байтов, результатом РЛП-кодирования будет байт, значение которого равно 0xb7 плюс . Для примера, строка длиной 1024 байта. Таким образом, первый байт будет лежать в пределах [0xb8, 0xbf].

В коде:

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' ]

Пустая строка = [ 0x80 ]

Пустой список = [ 0xc0 ]

Закодированное число 15 ('\x0f') = [ 0x0f ]

Закодированное число 1024 ('\x04\x00') = [ 0x82, 0x04, 0x00 ]

Теоретико-множественное представление числа 2, [ [], [[]], [ [], [[]] ] ] = [ 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' ]