Unary
The unary functional type is commonly used for dynamic sizing in structures such as hml_short. Unary supports two main options:unary_zero
variation is straightforward: if the first bit is 0
, the result of the entire unary deserialization is 0
.
The unary_succ
variation, however, is more complex: it is loaded recursively and represents a value of ~(n + 1)
. This means it repeatedly calls itself until it reaches unary_zero
. In other words, the desired value will equal the number of units in a row.
For example, consider the serialization of the bitstring 110
.
The deserialization call chain is as follows:
unary_zero
is reached, the value is returned up the call stack, similar to how values are returned in a recursive function.
To better visualize the result, let’s trace the return path:
0 -> ~(0 + 1) -> ~(1 + 1) -> 2
This shows that the bitstring 110
corresponds to Unary 2
.
Hashmap
The Hashmap complex type is used to store dictionaries from FunC smart contract code, i.e.,dict
.
As a support structure we need:
HashmapE n X
that can be in one of the two possible states: either hme_empty
or hme_root
.
Hashmap parsing example
As an example, consider the following cell, represented in binary form:HashmapE
structure with an 8-bit key size, and its values are represented using the uint16
type—that is, HashmapE 8 uint16
.
The HashmapE
structure utilizes 3 distinct key types:
hme_empty
or hme_root
. This is decided by identifying the correct prefix
. The hme_empty
variation is indicated by a single bit 0
(hme_empty$0
), while the hme_root
variation is indicated by a single bit 1
(hme_root$1
). After reading the first bit, if it is 1
(1[1]
), we know it is the hme_root
variation.
Next, we can populate the structure variables with known values. The initial result is:
hme_root$1 {n:#} {X:Type} root:^(Hashmap 8 uint16) = HashmapE 8 uint16;
Here, the one-bit prefix is already read. The curly braces {}
indicate conditions that need not be read. Specifically:
{n:#}
indicates thatn
is anyuint32
number.{X:Type}
means thatX
can be any type.
root:^(Hashmap 8 uint16)
, where the ^
symbol denotes a link that must be loaded.
Initiating branch parsing
According to our schema, this is the correctHashmap 8 uint16
structure. Next, we populate it with known values, resulting in the following:
{l:#}
and {m:#}
have appeared, but both values are unknown at this stage. After reading the corresponding label
, we can deduce that n
is part of the equation {n = (~m) + l}
. This means we must calculate both l
and m
, where the sign indicates the resulting value of ~
.
To determine the value of l
, we need to load the label:(HmLabel ~l uint16)
sequence. Below, we outline the 3 basic structural options for HmLabel
:
2[00]
). Therefore, the only logical option is hml_short$0
, which starts with a prefix of 0
.
Next, let’s fill in the hml_short
structure with known values:
n
. However, since it includes a ~
character, we can calculate it. To do so, we load len:(Unary ~n)
; more about unary here.
Starting with 2[00]
, only one bit remains after defining the HmLabel
type.
We load this final bit and observe that its value is 0
, which indicates that the unary_zero$0
variation is used. This means that the n
value for the HmLabel
variation is zero.
Now, we can complete the hml_short
structure by using the calculated n
value:
HmLabel
, denoted by s = 0
, which means there is nothing to load.
Next, we complete our structure by incorporating the calculated value of l
, as follows:
l
, we can also calculate m
using the equation n = (~m) + 0
, which simplifies to m = n - 0
. Therefore, m = n = 8
.
With all unknown values determined, we can load the node:(HashmapNode 8 uint16)
.
Regarding the HashmapNode, we have several options:
n = 0
, the correct result will be either hmn_leaf
or hmn_fork
.
Since, in this example, n = 8
, we use the hmn_fork
variation. Now, we can fill in the known values as follows:
HashmapNode (n + 1) uint16
. This means that the resulting value of n
must be equal to our parameter, i.e., 8. To calculate the local value of n
, we use the following formula:
n = (n_local + 1)
-> n_local = (n - 1)
-> n_local = (8 - 1)
-> n_local = 7
.
Analyzing loaded hashmap values
Continuing the previous example, let’s examine how loading branches work for dictionary values. For instance, given the bitstring:28[1011100000000000001100001001]
.
The result is once again hm_edge
, and the next step is to fill in the sequence with the correct known values as follows:
HmLabel
response is loaded using the HmLabel
variation, as the prefix is 10
.
n:(#<= 7)
, clearly denotes a sizing value that corresponds to the number 7, which is, in fact, the log2
of the number + 1
. For simplicity, however, we can count the number of bits required to represent the number 7.
In binary, the number 7 is written as 111
, which means 3 bits are needed. Therefore, the value for n = 3
.
n
into the sequence, which results in 111
. As noted earlier, this coincidentally equals 7. Then, we load s
into the sequence, which consists of 7 bits: 0000000
. Remember, s
is part of the key.
Afterwards, we return to the top of the sequence and fill in the resulting l
:
m
: m = 7 - 7
, which gives us m = 0
.
Since m = 0
, the structure is ideally suited for use with a HashmapNode
:
uint16
type and load the value. When converted to decimal, the remaining 16 bits, 0000001100001001
, give us the value 777
.
Now, let’s restore the key. We need to combine all the parts of the key that were computed previously. Each related key part is combined with one bit depending on the branch type used. A 1
bit is added for the right branch, and a 0
bit is added for the left branch. If a full HmLabel
exists above, its bits are added to the key.
In this specific case, 7 bits are taken from the HmLabel 0000000
, and a 1
bit is added before the sequence of zeros because the value was obtained from the right branch. The final result is 8 bits, or 10000000
, which means the key value equals 128
.
Other hashmap types
Now that we have discussed Hashmaps and how to load the standardized Hashmap type, let’s explain how the additional Hashmap types function.HashmapAugE
HashmapAugE
and the regular Hashmap
is the presence of an extra:Y
field in each node (not just in leaf nodes containing values).
PfxHashmap
PfxHashmap
and the regular Hashmap
lies in its ability to store keys of varying lengths due to the inclusion of the phmn_leaf$0
and phmn_fork$1
nodes.
VarHashmap
VarHashmap
and the regular Hashmap
is its ability to accommodate different key lengths, attributed to the presence of the vhmn_leaf$00
and vhmn_fork$01
nodes. Additionally, the VarHashmap
can form a common value prefix (child map) by utilizing the vhmn_cont$1
node.
BinTree
VmTuple
[a, b, c]
. VmTuple is used internally in VmStack
for tuple serialization, which is outputted from a contract’s methods.
Let’s us consider a serialization of the following tuple: [44, Cell{00B5BD3EB0}
, -1].
When disassembled, it looks as follows:
vm_stk_tuple
, since its prefix is 0x07
. The next 2 bytes are len:(## 16)
that equals 0003 == 3
.
Next comes data:(VmTuple 3)
. There are two variants of parsing of VmTuple
: VmTuple (n + 1)
and VmTuple 0
. Since n > 0
, VmTuple (n + 1)
is used.
The first field is head:(VmTupleRef 2=(3-1))
. There are three variant of parsing: 0
, 1
, and n+2
. Our n
equals 2
, so the third variant is used.
The only field is ref:^(VmTuple (n + 2))
, i.e. ref:^(VmTuple 2)
.
Our n
equals 2
, so the variant (n + 1)
is chosen. Next read head:(VmTupleRef n)
-> head:(VmTupleRef 1=(2-1))
. In VmTupleRef 1
there is only one field: entry:^VmStackValue
.
Essentially, this field is the value,01 000000000000002C
.
We read the head
and reached the end, now we go in the opposite direction and read the tail:^VmStackValue
. Going up, the first tail is 03
with a link to the cell.
0x03
on the stack means a cell, we just read this link and save it as the value,00B5BD3EB0
. Then go up a level and read another tail
, this is 01 FFFFFFFFFFFFFFFF
, i.e. int equal to -1
.
After we have reached the end, the parsing is completed, we add all the received elements into the array in the order in which we received them.