Serialization

Noun serialization refers to a uniquely-defined technique for converting a noun into a single atom. The basic noun serialization process in Urbit, called “jamming”, includes supporting internal references so that there is a minor compression effect included.

Serialization Arms

The main tools from /sys/hoon for noun serialization are:

  • +cue, unpack a jammed noun

  • +jam, pack a jammed noun

  • +mat, length-encode a noun

  • +rub, length-decode a noun

+jam and +cue are critically important for noun communication operations, including the %lick vane, the %khan vane, and noun channels in %eyre.

+cue

It is more straightforward to see how to decode a noun than to encode it, so let's start there.

++  cue                                                 ::  unpack
  ~/  %cue
  |=  a=@
  ^-  *
  =+  b=0
  =+  m=`(map @ *)`~
  =<  q
  |-  ^-  [p=@ q=* r=(map @ *)]
  ?:  =(0 (cut 0 [b 1] a))
    =+  c=(rub +(b) a)
    [+(p.c) q.c (~(put by m) b q.c)]
  =+  c=(add 2 b)
  ?:  =(0 (cut 0 [+(b) 1] a))
    =+  u=$(b c)
    =+  v=$(b (add p.u c), m r.u)
    =+  w=[q.u q.v]
    [(add 2 (add p.u p.v)) w (~(put by r.v) b w)]
  =+  d=(rub c a)
  [(add 2 p.d) (need (~(get by m) q.d)) m]

The above gate accepts an atom .b, which is a “blob” or as-yet-undefined value. Pin a cursor to run from low to high (LSB) at 0. The empty map .m will map from cursor to noun. (All cursor-to-noun mappings will be saved here.)

The trap produces a 3-tuple where .p is the following cursor position; .q is the noun; and .r is the cache. The product itself will be .q.

A data cursor is pinned at .c, while the third bit is pinned at .a. If the first bit at .a is 0b0, then the noun is a direct atom. Pin the expansion of the second bit at .a as .c; .p is now the cursor after .c, .q is the atom from .e, and .r is an updated cache. (See +rub discussion below for the atom expansion details.)

Otherwise, we have a cell, so we have to expand the second bit at .a. If it is 0b0, then the cell needs to be decoded by decoding the noun at . If it is 0b1, then we have a saved reference and retrieve it from the cache (last branch).

If the second bit at .a is 0b1, then the noun is a saved reference. In that case, expand at .c (the head), as $(b c) and pin the cursor after as .v. +w is the cell of q.u and q.v. .p is the lengths of .u and .v plus 2. .q is +w, with .r is the cache with +w inserted.

+rub

++  rub                                                 ::  length-decode
  ~/  %rub
  |=  [a=@ b=@]
  ^-  [p=@ q=@]
  =+  ^=  c
      =+  [c=0 m=(met 0 b)]
      |-  ?<  (gth c m)
      ?.  =(0 (cut 0 [(add a c) 1] b))
        c
      $(c +(c))
  ?:  =(0 c)
    [1 0]
  =+  d=(add a +(c))
  =+  e=(add (bex (dec c)) (cut 0 [d (dec c)] b))
  [(add (add c c) e) (cut 0 [(add d (dec c)) e] b)]

+rub extracts a self-measuring atom from an atomic blob, which accepts a cell of bit position cursor .a and atomic blob .b. +rub produces a number of bits to advance the cursor .p and the encoded atom .q.

.c is a unary sequance of 0b1 bits followed by a 0b0 bit. If .c is 0b0, then the cursor advancement .p is 0b1 and the encoded atom .q is 0b0. Otherwise, .c is the number of bits needed to express the number of bits in .q.

The cursor .a is advanced to include .c and the terminator bit.

We pin .e, the number of bits in .q. This is encoded as a c-1-length sequence of bits following .a, which is added to $2^{c-1}$. .p (the number of bits consumed) is c+c+e. The packaged atom .q is the .e-length bitfield at a+c+c.

+jam

The basic idea of +jam is to produce a serial noun (in order of head/tail). This requires a recursive examination of the encoded noun:

  1. One bit marks cell or atom.

  2. Next entry marks bit length of value for atom, 0 if cell, or 1 if reference.

  3. Then the actual value (itself a cell or atom).

Some readers may prefer to examine the Python noun.py implementation to supplement the Hoon definition; see particularly mat().

Examples:

> `@ub`(jam ~)
0b10
::  start at LSB, so `0` for atom, `1` for length, `0` for value (head-trimmed
::  zero, really `0b010`)

> `@ub`(jam 1)
0b1100
::  start at LSB, so `0` for atom, `01` for length, `1` for value

> `@ub`(jam [0 0])
0b10.1001
::  start at LSB, so `01` for cell, then `0` for head atom, length `1`,
::  value `0`, repeat

> `@ub`(jam [0 1])
0b1100.1001
::  start at LSB, so `01` for cell, then `0` for head atom, length `1`,
::  value `0`, repeat with value `1`

> `@ub`(jam [1 0])
0b1011.0001

> `@ub`(jam 0b111)
0b1111.1000

> `@ub`(jam [0 1 2])
0b1.0010.0011.0001.1001

To cue a jamfile:

> =jammed-file .^(@ %cx %/jammed/jam)
> (cue jammed-file)
...

This cues as a noun, so it should be ;; or clammed to a particular mold.

+eval and newt encoding

Newt encoding is a variation of this: it is a jammed noun with a short header. Newt encoding is used by urbit eval.

The format for a newt-encoded noun is:

V.BBBB.JJJJ.JJJJ...

  • V version

  • B jam size in bytes (little endian)

  • J jammed noun (little endian)

+eval supports several options for processing Hoon nouns as input to or output from conn.c:

  • -j, --jam: output result as a jammed noun.

  • -c, --cue: read input as a jammed noun.

  • -n, --newt: write output / read input as a newt-encoded jammed noun, when paired with -j or -c respectively.

  • -k: treat the input as the jammed noun input of a %fyrd request to conn.c; if the result is a $goof, pretty-print it to stderr instead of returning it.

In the Vere runtime, these are used by vere/newt.c; see particularly:

  • u3_newt_send() transmits a jammed noun (using u3s_jam_xeno(), for instance) to a task buffer for libuv. (Recall that libuv is the main event loop driver for the king process.)

  • u3_newt_read() pulls out the jammed noun from the buffer.

Serialization is also supported by serial.c functions, prefixed u3s.

Khan and Lick both use newt.c.

PreviousSail (HTML)NextSets

Last updated