Skip to main content

Unary

The unary functional type is commonly used for dynamic sizing in structures such as hml_short. Unary supports two main options:
unary_zero$0 = Unary ~0;
unary_succ$1 {n:#} x:(Unary ~n) = Unary ~(n + 1);
The 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_succ$1 -> unary_succ$1 -> unary_zero$0
Once 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:
bit$_ (## 1) = Bit;
The following TL-B structures are used to serialize a Hashmap with a fixed key length:
hm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l n)
          {n = (~m) + l} node:(HashmapNode m X) = Hashmap n X;

hmn_leaf#_ {X:Type} value:X = HashmapNode 0 X;
hmn_fork#_ {n:#} {X:Type} left:^(Hashmap n X)
           right:^(Hashmap n X) = HashmapNode (n + 1) X;

hml_short$0 {m:#} {n:#} len:(Unary ~n) {n <= m} s:(n * Bit) = HmLabel ~n m;
hml_long$10 {m:#} n:(#<= m) s:(n * Bit) = HmLabel ~n m;
hml_same$11 {m:#} v:Bit n:(#<= m) = HmLabel ~n m;

unary_zero$0 = Unary ~0;
unary_succ$1 {n:#} x:(Unary ~n) = Unary ~(n + 1);

hme_empty$0 {n:#} {X:Type} = HashmapE n X;
hme_root$1 {n:#} {X:Type} root:^(Hashmap n X) = HashmapE n X;
This root structure is 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:
[1] -> {
  [00] -> {
    [1001000] -> {
      [1010000010000001100001001],
      [1010000010000000001101111]
    },
    [1011100000000000001100001001]
  }
}
This cell uses the 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:
1 = 777
17 = 111
128 = 777
To parse this Hashmap, we must first determine which structure type to use: either 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 that n is any uint32 number.
  • {X:Type} means that X can be any type.
The next portion to read is root:^(Hashmap 8 uint16), where the ^ symbol denotes a link that must be loaded.
[00] -> {
    [1001000] -> {
      [1010000010000001100001001],
      [1010000010000000001101111]
    },
    [1011100000000000001100001001]
  }

Initiating branch parsing

According to our schema, this is the correct Hashmap 8 uint16 structure. Next, we populate it with known values, resulting in the following:
hm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l 8)
          {8 = (~m) + l} node:(HashmapNode m uint16) = Hashmap 8 uint16;
As shown above, conditional variables {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:
hml_short$0 {m:#} {n:#} len:(Unary ~n) {n <= m} s:(n * Bit) = HmLabel ~n m;
hml_long$10 {m:#} n:(#<= m) s:(n * Bit) = HmLabel ~n m;
hml_same$11 {m:#} v:Bit n:(#<= m) = HmLabel ~n m;
Each option is determined by its corresponding prefix. Our root cell comprises 2 zero bits, displayed as (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:
hml_short$0 {m:#} {n:#} len:(Unary ~n) {n <= 8} s:(n * Bit) = HmLabel ~n 8
At this point, we don’t know the value of 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:
hml_short$0 {m:#} {n:#} len:0 {n <= 8} s:(0 * Bit) = HmLabel 0 8
We have an empty 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:
hm_edge#_ {n:#} {X:Type} {l:0} {m:#} label:(HmLabel 0 8)
          {8 = (~m) + 0} node:(HashmapNode m uint16) = Hashmap 8 uint16;
Now that we have calculated the value of 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:
hmn_leaf#_ {X:Type} value:X = HashmapNode 0 X;
hmn_fork#_ {n:#} {X:Type} left:^(Hashmap n X)
           right:^(Hashmap n X) = HashmapNode (n + 1) X;
In this case, we determine the option not by using the prefix but by examining the parameter. Specifically, if 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:
hmn_fork#_ {n:#} {X:uint16} left:^(Hashmap n uint16)
           right:^(Hashmap n uint16) = HashmapNode (n + 1) uint16;
After entering the known values, we must calculate the 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.
hmn_fork#_ {n:#} {X:uint16} left:^(Hashmap 7 uint16)
           right:^(Hashmap 7 uint16) = HashmapNode (7 + 1) uint16;
Now that we know the formula obtaining the final result is straightforward. Next, we load the left and right branches, and for each subsequent branch, the process is repeated.

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:
hm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l 7)
          {7 = (~m) + l} node:(HashmapNode m uint16) = Hashmap 7 uint16;
Next, the HmLabel response is loaded using the HmLabel variation, as the prefix is 10.
hml_long$10 {m:#} n:(#<= m) s:(n * Bit) = HmLabel ~n m;
Now, let’s fill in the sequence:
hml_long$10 {m:#} n:(#<= 7) s:(n * Bit) = HmLabel ~n 7;
The new construction, 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.
hml_long$10 {m:#} n:(## 3) s:(n * Bit) = HmLabel ~n 7;
Next, we load 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:
hm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel 7 7)
          {7 = (~m) + 7} node:(HashmapNode m uint16) = Hashmap 7 uint16;
Then we calculate the value of m: m = 7 - 7, which gives us m = 0. Since m = 0, the structure is ideally suited for use with a HashmapNode:
hmn_leaf#_ {X:Type} value:X = HashmapNode 0 X;
Next, we substitute our 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

ahm_edge#_ {n:#} {X:Type} {Y:Type} {l:#} {m:#}
  label:(HmLabel ~l n) {n = (~m) + l}
  node:(HashmapAugNode m X Y) = HashmapAug n X Y;

ahmn_leaf#_ {X:Type} {Y:Type} extra:Y value:X = HashmapAugNode 0 X Y;

ahmn_fork#_ {n:#} {X:Type} {Y:Type} left:^(HashmapAug n X Y)
  right:^(HashmapAug n X Y) extra:Y = HashmapAugNode (n + 1) X Y;

ahme_empty$0 {n:#} {X:Type} {Y:Type} extra:Y
          = HashmapAugE n X Y;

ahme_root$1 {n:#} {X:Type} {Y:Type} root:^(HashmapAug n X Y)
  extra:Y = HashmapAugE n X Y;
The primary distinction between the HashmapAugE and the regular Hashmap is the presence of an extra:Y field in each node (not just in leaf nodes containing values).

PfxHashmap

phm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l n)
           {n = (~m) + l} node:(PfxHashmapNode m X)
           = PfxHashmap n X;

phmn_leaf$0 {n:#} {X:Type} value:X = PfxHashmapNode n X;
phmn_fork$1 {n:#} {X:Type} left:^(PfxHashmap n X)
            right:^(PfxHashmap n X) = PfxHashmapNode (n + 1) X;

phme_empty$0 {n:#} {X:Type} = PfxHashmapE n X;
phme_root$1 {n:#} {X:Type} root:^(PfxHashmap n X)
            = PfxHashmapE n X;
The key difference between the 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

vhm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l n)
           {n = (~m) + l} node:(VarHashmapNode m X)
           = VarHashmap n X;
vhmn_leaf$00 {n:#} {X:Type} value:X = VarHashmapNode n X;
vhmn_fork$01 {n:#} {X:Type} left:^(VarHashmap n X)
             right:^(VarHashmap n X) value:(Maybe X)
             = VarHashmapNode (n + 1) X;
vhmn_cont$1 {n:#} {X:Type} branch:Bit child:^(VarHashmap n X)
            value:X = VarHashmapNode (n + 1) X;

// nothing$0 {X:Type} = Maybe X;
// just$1 {X:Type} value:X = Maybe X;

vhme_empty$0 {n:#} {X:Type} = VarHashmapE n X;
vhme_root$1 {n:#} {X:Type} root:^(VarHashmap n X)
            = VarHashmapE n X;
Similarly, the main difference between the 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

bta_leaf$0 {X:Type} {Y:Type} extra:Y leaf:X = BinTreeAug X Y;
bta_fork$1 {X:Type} {Y:Type} left:^(BinTreeAug X Y)
           right:^(BinTreeAug X Y) extra:Y = BinTreeAug X Y;
The binary tree key generation mechanism operates similarly to the standardized Hashmap framework but without using labels; instead, it relies on branch prefixes.

VmTuple

vm_tupref_nil$_ = VmTupleRef 0;
vm_tupref_single$_ entry:^VmStackValue = VmTupleRef 1;
vm_tupref_any$_ {n:#} ref:^(VmTuple (n + 2)) = VmTupleRef (n + 2);
vm_tuple_nil$_ = VmTuple 0;
vm_tuple_tcons$_ {n:#} head:(VmTupleRef n) tail:^VmStackValue = VmTuple (n + 1);
vm_stk_tuple#07 len:(## 16) data:(VmTuple len) = VmStackValue;
Tuple is an actual tuple of elements that is written in FunC as [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:
[070003] -> {
   [] -> {
      [01000000000000002C],
      [03] -> {
         [00B5BD3EB0]
      }
   },
   [01FFFFFFFFFFFFFFFF]
}
The root cell will be parsed using the constructor 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.

References

Link to the original article - Oleg Baranov.
I