Compression kit

Varint encode example

// we will generate two methods: varint_u32.encode and varint_u32.decode
fn varint_u32.encode(x: u32) ~ varint_u32.decode(bytes: [?]u8) {
    bits = x.chunk(1) // bits: Scannable[u1]
    while true {
        bits7 = bits.pop<7>()
        all_zero = bits.are_all(0) // bool == u1
        // no reassignment are allowed: `byte = byte | 0x01` is forbidden!
        bytes.push<1>((!all_zero) || bits7) // || / concat - reversible function which takes [n]u1, [m]u1 and produces [n+m]u1

        if all_zero { break }
    }
}

Shrink encode example

// (bytes: [n]u8) is a syntax sugar for (n: u32, bytes: [?]u8)
fn shrink_u32.encode(x: u32) ~ shrink_u32.decode(bytes: [n: 1..=5]u8) {
    bits = x.chunk(1)
    while true {
        bits8 = bits.pop<8>()
        bytes.push<1>(bits8)
        if bits.are_all(0) {
            break
        }
    }
}

Length prefixing

fn length_prefix.encode(b: [n: u32]u8) ~ length_prefix.decode(bytes: [?]u8) {
    varint_length = varint_u32.encode(n) // ~ 2. n = varint_u32.decode(varint_length)
    bytes.push<1>(varint_length)         // ~ 1. varint_length: [?]u8 = result.pop<1>()
    bytes.push<n>(b)                     // ~ 3. b = result.pop()
}

Length prefixing with reverse

// idempotent function: reverse(reverse(b)) == b
extern fn reverse(b: [n]u8) ~ reverse(b: [n]u8);

fn length_prefix.encode(b: [n: u32]u8) ~ length_prefix.decode(bytes: [?]u8) {
    reversed = reverse(b)                // ~ 4. b = reverse(reversed)
    varint_length = varint_u32.encode(n) // ~ 2. n = varint_u32.decode(varint_length)
    bytes.push<1>(varint_length)         // ~ 1. varint_length: [?]u8 = result.pop<1>()
    bytes.push<n>(reversed)              // ~ 3. reversed = result.pop()
}

Syntax for state definition

forward state [?]T {
    // dual method - we must call pop for every push in forward order
    // template parameter  is the external information which is common for both methods
    mut<n: u32> push(x: [n]T) ~ pop()
}

forward state BlocksLru {
    init<size: u32> forward() ~ backward()

    mut encode(offset: u32) ~ decode(encoded: u32)
    mut touch(offset: u32) ~ touch(offset: u32) // same dual method - we must call touch with same argument in dual method
}

forward state FwdBitStream {
    init forward() ~ backward()

    mut flush() ~ flush()
    mut<n: 0..=64> push(b: [n]u1) ~ pop()
}

// for backward state we must generate dual operations in reverse order
backward state BwdBitStream {
    init () ~ ()
    deinit () ~ ()

    mut flush() ~ reload()
    mut<n: 0..=64> push(b: [n]u1) ~ pop()
}

// must not compile because we .decode can't be implemented
fn invalid.encode(x: u32) ~ invalid.decode(bytes: [?]u32) {
    blocks = BlocksLru.forward(1024)
    y = blocks.encode(x) // 2. ~ x = blocks_lru.decode(y) !!! y is unknown here but we can't violate state operations order
    z = blocks.encode(y) // 3. ~ y = blocks_lru.decode(z)
    bytes.push(z)        // 1. ~ z = result.pop()
}

const RGBA = struct {
    r: u8,
    g: u8,
    b: u8,
    a: u8,
}

const Header {
    magic: "qoif"
    width: u32
    height: u32
    channels: {3, 4}
    colorspace: {0, 1}
}

const Operation = union {
    QOI_OP_RGB   = struct { r: 0..256, g: 0..256, b: 0..256 },
    QOI_OP_RGBA  = struct { r: 0..256, g: 0..256, b: 0..256, a: 0..256 },
    QOI_OP_INDEX = struct { index: 0..64 },
    QOI_OP_DIFF  = struct { dr: -2..2, dg: -2..2, db: -2..2 },
    QOI_OP_LUMA  = struct { dr: -32..32, dr_dg: -8..8, db_dg: -8..8 },
    QOI_OP_RUN   = struct { run: 0..62 },
}

fn qoi.encode({ header: Header, operations: [n]Operation }) ~ qoi.decode(bytes: [?]u8) {
    bytes.push<4>("qoif")            // 1. ~ assert!(bytes.pop<4>() == "qoif")
    bytes.push<4>(header.width)      // 2. ~ header.width = bytes.pop<4>()
    bytes.push<4>(header.height)     // 3. ~ header.height = bytes.pop<4>()
    bytes.push<4>(header.channels)   // 4. ~ header.channels = bytes.pop<4>()
    bytes.push<4>(header.colorspace) // 5. ~ header.colorspace = bytes.pop<4>()

    size = header.width * header.height
    while size > 0 {
        operation = operations.pop()
        bytes.push<1>(tag_payload)
        if operation == .QOI_OP_RGB {
            tag_payload = 0b11111110
            bytes.push<3>([operation.r, operation.g, operation.b])
            size -= 1
        } else if operation == .QOI_OP_RGBA {
            tag_payload = 0b11111111
            bytes.push<4>([operation.r, operation.g, operation.b, operation.a])
            size -= 1
        } else if operation == .QOI_OP_INDEX {
            tag_payload = 0b00 || operation.index
            size -= 1
        } else if operation == .QOI_OP_DIFF {
            tag_payload = 0b01 || operation.dr + 2 || operation.dg + 2 || operation.db + 2
            size -= 1
        } else if operation == .QOI_OP_LUMA {
            tag_payload = 0b10 || operation.dg + 32
            bytes.push<1>([operation.dr_dg + 8 || operation.db_dg + 8])
            size -= 1
        } else if operation == .QOI_OP_RUN {
            tag_payload = 0b11 || operation.run
            size -= operation.run
        } else {
            panic("unexpected operation type")
        }
    }
    bytes.push<8>([0, 0, 0, 0, 0, 0, 0, 1])
}

forward state qoi.Recent {

}

fn qoi.compress(image: [height: 0..1<<32, width: 0..1<<32]RGBA) ~ qoi.decompress({ header: Header, operations: [n]Operation }) {
    header = Header { width: width, height: height, channels: 4, colorspace: 0 }
    // how to iterate over 2d array?
    scan image ~ operations {

    }
}