Rung 1: Basics: values, loops, functions

Everything Gestalt stores is bytes, and everything it counts is a whole number. So the first things you need are few: names for values, numbers of a fixed size, loops, and functions. By the end of this rung you will have written the first function of Gestalt's codec.

The idea #

Names and let #

let seq = 0;        // a name for a value; it cannot change
let mut total = 0;  // `mut`: this one can
total = total + 5;

A name is immutable unless you write mut. You mark change on purpose. That suits a system whose records only ever grow: nothing is quietly overwritten.

Numbers have a size #

Write numbers as 255, 0xff, 0b1111_1111 or 1_000_000. Convert with as: b as u32.

A number that leaves its range is an overflow. Rust refuses to build when it can see one, and panics at run time in a debug build. Gestalt never lets one pass silently: its arithmetic is checked, and an overflow becomes a hole (rung 3).

Bits #

A byte is 8 bits. Four operators take bytes apart and put them together:

let b: u8 = 0x4e;
let high = b >> 4;            // 0x4: the first hex digit
let low = b & 0x0f;           // 0xe: the second hex digit
let n: u32 = (0x12 << 8) | 0x34;  // 0x1234: append a byte on the right

if, for and while #

let mut zeros = 0;
for b in bytes {              // each item, in order
    if b == 0 {
        zeros += 1;
    }
}

for i in 1..seqs.len() {      // 1, 2, ... up to len - 1 (the end is left out)
    // seqs[i] and seqs[i - 1]
}

while n > 0 {                 // until the condition is false
    n >>= 8;
}

if is an expression, so it can give a value: let size = if n < 24 { 1 } else { 2 };

Functions #

fn sum_cents(amounts: Vec<u64>) -> u64 {
    let mut total = 0;
    for a in amounts {
        total += a;
    }
    total   // the last expression, with no semicolon, is the result
}

Use return to leave early once you know the answer.

Vec and String #

Vec<u8> is a list of bytes that can grow: Vec::new(), vec![1, 2, 3], .push(x), .len(), v[i], .extend_from_slice(&[a, b]).

String is text, always valid UTF-8: String::new(), .push('a'), format!("{:02x}", b).

In this rung every function takes its Vec by value: it consumes it, and the caller can't use it again. Rung 2 shows why that is wasteful and how borrowing fixes it.

Why Gestalt cares #

• Everything is bytes. An entry, a signature and a digest are all bytes: Vec<u8> or [u8; 32]. The record format is CBOR, hashed with SHA-256.
• Everything counted is a whole number. Sequence numbers start at 0. Times are milliseconds since 1970. Amounts are in the smallest unit. The kernel has no floats at all, and the determinism gate refuses them (rung 6), because two machines must always compute the same bytes.
• There is one right way to write a number. CBOR could write 5 in one byte or in nine. Gestalt allows only the shortest form; otherwise the same entry could be written two ways and get two hashes. Exercise 7 is that rule.

In Gestalt's code #

The codec writes the head of every CBOR item with this function. It is exercise 7 for all major types at once. major << 5 puts the major type in the top 3 bits, and match with ranges is a tidier if / else if (rung 3).

From engine/kernel/codec/src/cbor.rs:281:

fn head(out: &mut Vec<u8>, major: u8, n: u64) {
    let m = major << 5;
    match n {
        0..=23 => out.push(m | n as u8),
        24..=0xff => out.extend_from_slice(&[m | 24, n as u8]),
        0x100..=0xffff => {
            out.push(m | 25);
            out.extend_from_slice(&(n as u16).to_be_bytes());
        }
        0x1_0000..=0xffff_ffff => {
            out.push(m | 26);
            out.extend_from_slice(&(n as u32).to_be_bytes());
        }
        _ => {
            out.push(m | 27);
            out.extend_from_slice(&n.to_be_bytes());
        }
    }
}

A digest has a text form: a kind letter and 52 base32 letters. Here is a for, a while and the bit operators working together. Each byte goes into an accumulator; whenever 5 or more bits are waiting, one letter comes out.

From engine/kernel/codec/src/hash.rs:193:

pub fn to_text(&self, kind: char) -> String {
    let mut s = String::with_capacity(1 + TEXT_CHARS);
    s.push(kind);
    let (mut acc, mut bits) = (0u32, 0u32);
    for b in self.0 {
        acc = (acc << 8) | u32::from(b);
        bits += 8;
        while bits >= 5 {
            bits -= 5;
            s.push(BASE32[((acc >> bits) & 31) as usize] as char);
        }
    }
    // ... the last few bits

And here are real bytes. The spec's first line vector (spec/vectors/line.json) starts a7 00 01 01 58 de:

Exercise #

cd ~/Documents/gestalt-learn
./ladder 1

Open rungs/01-basics/src/lib.rs. Seven functions say todo!(). Fill them in from top to bottom and run ./ladder 1 after each one. A passing test says ok. The last one, cbor_uint_head, is the codec's own rule.

Then the two drills. Each one fails to build until you fix it:

./ladder drill 1 immutable
./ladder drill 1 overflow

Stuck? rungs/01-basics/solution/ has one way to do it. Try first. ./ladder solution 1 runs the tests against it.

Check yourself #

• Why is a name immutable unless you write mut?
• What does the CBOR byte 0x1a say?
• Why does Gestalt refuse a number that is not in its shortest form?
• Why are amounts whole numbers in the smallest unit, never floats?

The cards for this rung ask these and more.