Forem: Shaw

SIMD Opcodes Use LEB128

Shaw — Thu, 01 Jun 2023 09:00:49 +0000

Most WebAssembly opcodes use a single byte.

i32.add = 0x6A
local.tee = 0x22

Some opcodes use two bytes.

memory.copy = 0xFC + 0x0A
i32.atomic.store = 0xFE + 0x17

SIMD opcodes use Leb128

This table seems to claim the following
v128.load = 0xFD + 0x00

But it actually is: 0xFD + encode_leb128(0x00)
which expands to: 0xFD + 0x80

LEB128 stands for little endian base 128, and is basically a number of bytes <0x80 (which each are taken for literal bits `total = total * 0x80 + byte`), and a byte >=0x80 that terminates the sequence (which is taken for bits, after masking off the 0x80 total = total * 0x80 + (byte | 0x7F))

Examples of LEB128

Examples of decoding LEB128:
decode_leb([0x80]) = 0x80 - 0x80 = 0
decode_leb([0x01, 0x80]) = 0x01 * 0x80 + 0x80 - 0x80 = 127
decode_leb([0x5F, 0x42, 0xFF]) = 0x5F * 0x80 * 0x80 + 0x42 * 0x80 + 0xFF - 0x80 = 0x17E17F

That's all i got. I hope that this can save someone from headache with WASM SIMD by hand.

So... staitc is Sorta Shifty.

Shaw — Wed, 21 Dec 2022 08:46:39 +0000

In a previous post I pondered that in the C programming language static only has one meaning.

Long story short I though that it meant "translation unit local". A term that effectively means that it is owned by the .c file or .o file and not the executable produced.

This turns out to be wrong. As I dove further into the c language I came upon a puzzling piece of code

int main(int argc, char *argv[static argc]) {
    // WTF. What the Function?
}

In a state of panic I looked all over for what it meant. Google was being no help. Eventually however, I learned that it meant that there must be atleast argc elements in argv (there is argc+1).

This disproves my static theory.

That is all. Thanks!

Cosmopolitan Libc

Shaw — Sat, 11 Dec 2021 03:14:23 +0000

Portable but not Small

Java was one of the first languages to emphasize cross platform binaries. It did tis with the .jar file, which is just a piece of compiled code that is executable on any platform. This does still require a Java Virtual Machine installed.

Small but not Portable

C on the other hand has never had this luxury. One would need to build C for each platform that exists. However, it allowed for C developers to ship standalone binaries that had no dependancies other than the underlying Libc.

Solution

Cosmopolitan Libc (Cosmo for short) is an implementation of Libc that runs on almost any 64 bit x86 machine. Cosmo does all this in a single binary.

The same file that runs on Linux runs on Windows runs on MacOS. Binaries built with Cosmo, however, have the same lack of dependancies as files built with a standard Libc. Cosmo is everything I love in modern C.

Example

Start with a simple hello world

#include <stdio.h>

int main() {
    printf("Hello, World!\n");
}

Replace all standard headers with a single

#include <cosmopolitan.h>

int main() {
    printf("Hello, World!\n");
}

Get Cosmopolitan Libc.

wget https://justine.lol/cosmopolitan/cosmopolitan.zip
mkdir -p cosmo && cd cosmo && 7z x ../cosmopolitan.zip

Build the .c file into a .com

gcc main.c -O2 -static -fno-pie -mno-red-zone -nostdlib \
    -nostdinc -fno-omit-frame-pointer -o main.com.dbg \
    -Wl,--gc-sections -fuse-ld=bfd -Wl,-T,cosmo/ape.lds \
    cosmo/crt.o cosmo/ape.o cosmo/cosmopolitan.a \
    -Icosmo
objcopy -S -O binary main.com.dbg main.com

Run the .com file.

chmod +x main.com
env ./main.com

static has only one meaning

Shaw — Thu, 09 Dec 2021 18:17:54 +0000

static can be confusing with the wrong definition. Here's a simplified example:

The task is to write a counter function that takes no arguments and returns a different number each time, starting at 0 and adding 1 each time.

int current_counter = 0;
int counter(void) {
    return current_counter++;
}

Now imagine someone is using this library. They write a function called counter just for testing. But when they try to link their code, it fails, telling them that counter is being redefined. But no worry, We are C programmers and we have static at our disposal!

Many believe static to have multiple meanings in C.

static functions are not exported globally
static local variables are hidden globals
static global variables are not exported globally What could have caused this mess of keyword overloading?

The answer lies in a shift of perspective. static means compilation unit local. A compilation unit in C is just the files given to the c compiler (gcc, clang, msvc, etc) and what they #include.

Using this definition we can say the following.

static functions are owned by the compilation unit
static global variables are owned by the compilation unit
static local variables are owned by the compilation unit

Using this knowledge, we can rewrite the counter function to not leak counter into the API.

First, move current_counter into a static in counter

int counter(void) {
    static int current_counter = 0;
    return current_counter++;
}

This will make current_counter not collide with anything else named current.

Next is to make counter a static function

static int counter(void) {
    static int current_counter = 0;
    return current_counter++;
}

This will make counter not visible to files not in the same compilation unit.

Now things are fixed! The counter function and current_counter variable cannot be used in files not in the same compilation unit.

I hope this helped someone.

I wrote a Cozy Programming language

Shaw — Mon, 08 Nov 2021 22:10:39 +0000

When i started on writing Paka in March 2020 I had no idea what I was getting into.

I had only previously spent one month tops per project; Moving onto newer ideas and abandoning code was my modus operandi. I started new project, like the countless before, that was intended to be an interpreter for a new langugage called DEXT written in The D Programming Language. As time passed and the code grew to about 3000 lines before the name change to Paka.

Paka was intended to be a lisp originally, but ended up a scripting language with a 'polite' syntax.

# add two numbers
def add(x, y) {
    return x + y
}

println(add(x, y))

It translated recursion into simple array pushes and pops. This allowed for recursion to one's heart's content.

It supported freezing the entire running program, heap and all, to a JSON subset consisting of only objects and strings. Sadly this had to be removed for its performance penalty. This is a feature on the top of the list to bring back, and I have devised a system to keep performance up.

Quest (October 2020)

In order to help others' languages that looked fun, I decided to implement a new language that works alongside Paka. A free little language called Quest, made by a friend by the name of sampersand. It had more performance than the implementation they made, though had much head room to improve. It ended up not working out in the end, but it was a fun way to test my language's capability and try to improve quest as a language.

Passerine (February 2021)

Passerine was the next language i decided to try to fit onto paka, but alas this one too was eventually put aside for the time being.

MiniVM

One day in a discord call a twist of fate come. Someone asked how to implement a virtual machine in C. I, having learned much about virtual machines in the past 13 months, was asked how to write one. What was going to be a one-off example soon ballooned into a new runtime and virtual machine for Paka.

Performance was through the roof

def fib(n) {
    if n < 2 {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}

println(fib(35))

which ran in 850ms was now taking 500ms.

MiniVM was soon converted from a stack machine to a register machine. This came with another reduction, this time to 400ms, for the above program

A Dream

One of my far-off seeming goals was to get Paka to the point where it could be used to write a compiler for itself in.
This dream manifested almost out of thin air, when i made a simple Paka file to evaluate expressions like 1 + 2 + 3.

Then came the rest of the syntax to see how far i could get; It turns out it was less of an undertaking than i had expected.

The state of it all

Paka is now a cozy little language with a 30kb vm and 20kb compiler.

It builds in less than a second for most folks with a computer from the last decade...

# build minivm and paka
git clone https://github.com/shawsumma/purr --recursive
cd purr
make -C minivm
make -C ./

# run a file
./minivm/minivm bin/stage3 lang/test/echo.paka -- hello world

Call to Action

If you found any of this article interesting or helpful, it would be appreciated to give me a star over at shawsumma/purr and/or shawsumma/minivm.

And please be kind to me, this is my first time really writing about paka or minivm more than a paragraph.