Recursive-length prefix serialization
by Hidenori
Summary of the post by Ethereum
An item is defined to be:
- a byte array, or
- a list of items.
How to encode a byte array
- An array containing a single byte in the range of
[0x00, 0x7f]
is its own encoding.0x11
is0x11
.- Note that
0x11
is technically a shorthand for{0x11}
.
- If a byte array has $\leq 55$ elements, the first byte is
0x80 + length
and the byte array will follow.0x111111
is0x83111111
.0x111111
is technically a shorthand for the array{0x11, 0x11, 0x11}
.0x83
because0x80 + 3
where 3 is the length of the byte array.
- If the byte array has $\geq 56$ elements, the first byte is
0xb7 + length in bytes of the length
, the second byte is the length and the rest is the byte array.0x11111...11
where we have 10011
’s.- In other words, the byte array
{0x11, 0x11, ..., 0x11}
(100 bytes). - This is encoded as
0xb864
followed by 10011
’s. - The length 100 is 64 in hex decimals.
- 64 is 1-byte long.
0xb8 = 0xb7 + 1
.
How to encode a list of items
First, you must encode every item in the list.
- If the combined length of all the encoded items is $\leq 55$, then the first byte is
0xc0 + combined length
and the encoded items will follow.[0x11, 0x111111]
.- The elements are encoded as
0x11
and0x83111111
. - This is 5 bytes.
- So, the encoding is
0xc51183111111
.
- If the combined length of all the encoded items is $\geq 56$, then the first byte is
0xf7 + length in bytes of the combined lengths
, the second byte is the combined length and the encoded items will follow.[0x11, 0x111111, 0x11...11]
where the last byte array is the 100-byte array.- The total length is
1 + 4 + 102 = 107
. - 107 is
6b
in hex decimals, which is 1 byte. - Therefore, we obtain
0xf86b1183111111b86411...11
.
Subscribe via RSS