link Edge of the Edge

Edge computing is an approach that runs code "close to the user, decentralized", as opposed to cloud computing which is "far from the user, centralized". The tradeoff is roughly between minimizing network traffic or maximizing compute. This tradeoff makes sense in a number of applications, like sensors, CDNs or LLM inferencing, but often even the most remote devices seek communication with a central server at some point.

The internet always introduces uncertainty, even if it makes the internet much more dynamic. Mobile data can be slow, public or even private routers can have malware. AWS outages can famously take down smart fridges or prevent people from entering their smart homes. Can we explore an edge so remote that every website on the internet being offline would not affect it?

link Entropy in the World

Code, under the Von Neumann architecture, is simply data, and data is simply information. Information does not fundamentally depend on a global internet, even if it is significantly enhanced by it. Information also does not depend on a physical device. Information does not even depend on something physical! But we’re getting ahead of ourselves.

Does their exist a physical source of information that is reliable and dense enough to store code? And can I produce it cheaply? Something that fits the bill almost as well as modern competitors is the humble QR code.

They are extremely resilient, they have redundancy built in, but QR codes are primarily designed for small amounts of data, 2953 bytes is the limit in the standard but most phones are still incapable of reading that. A custom client capable of reading a QR code as bytecode or, perhaps, bitcode could utilize this limit to its fullest potential.

link mni

mni is a bitcode standard and a client designed for QR codes. Once scanned the bitcode will execute with zero network requests required. mni negates the issue of internet reliability and replaces it with the issue of physical reliability.

My first problem was code designed for size. Similar to codegolfing I sought a way of representing code with as few bytes as possible. The first step was thinking past the idea of bytes entirely and descending into the realm of the bit. QR codes, after all, are bit matrices.

Next was finding a portable runtime, as it is supposed to run on a phone. Another perk would also be a compilation target from many different languages. I chose WASM, not an interpreted language, as the basis for the bitcode standard. A bit sized interpreted language would be the ultimate next step in this project but to get this off the ground quickly I went with a well documented standard that I could compile to from C.

link Encoding Information

I started by writing a library for bit level writing. In it I needed a way of storing fundamental datatypes in as few bits as possible:

• Bool: 1 bit
• Unsigned integer: n bits
• Signed integer: 1 sign bit + n bits (representing the absolute value)
• Float: 32 - k bits (k being the number of mantissa bits to remove, size is preferred over accuracy if possible)

To accomplish the goal of storing practical code on a QR code it is necessary to go to the extremes for size. I implemented as many exotic integer encodings as I could and the encoder will choose whatever is smallest at the end:

• Tagged signed: Encode the number of bits needed to encode the integer, in 6 bits, then the integer itself
• Tagged unsigned: Tagged signed with the sign bit shaved off
• LEB variable length integer: Encode n bits of the number and write a 1 and finish if all bits have been written and 0 otherwise, repeat. WASM uses n=7 extensively but I check multiple values of n

Next I implemented lists, as lists provide unique new ways to compress that individual values do not:

• Normal: Encode each integer fully
• Delta: Encode the first integer fully and all subsequent integers as their difference from either the first integer or the most recent integer
• Huffman coding: The proven most efficient way of storing any list of integers, ignoring the size of the header encoding the binary tree

Normal and delta encoding also have additional space savings:

• Fixed: The number of bits required for every integer can be encoded at the front
• Tagged: Use tagged integers
• LEB: Use LEB integers

Finally, a bit can be defined as whether every integer in the list is positive and if they are only the unsigned version has to be encoded.

As strings are a list of integers every standard datatype can be represented by these encodings. Ideally every permutation of settings can be checked to produce the smallest number of bits but besides being impractical it’s also not optimal. Because each setting change requires bits somewhere else a better idea to reduce the amount of bits required in a setting header is to calculate the best defaults for the runtime and check permutations only if maximal savings are necessary.

link Bitcode With No Fluff

Using this base the next task is to adapt WASM bytecode into this custom bitcode. I started by recursively finding all functions called by a set of base exports, discussed below, the runtime will call into and removing all functions not within this set. Next I ran Binaryen optimization passes. Finally I convert the WASM into my bitcode standard using context aware compression.

WASM can be split into a number of distinct "items", each of which can be compressed differently by default than LEB128, which WASM uses by default for most integers:

 1NUM
 2SIZE
 3SECTION
 4STRING
 5TYPE
 6INDEXED_TYPE
 7LIMIT
 8MEMORY_OP
 9INSTRUCTION
10INSTRUCTION32
11ATTRIBUTE
12BREAK
13FUNCTION
14TABLE
15LOCAL
16GLOBAL
17MEMORY
18TAG
19I32
20I64
21I128
22F32
23F64
24ATOMIC_ORDER
25SEGMENT
26MEMORY_IDX
27LANE
28STRUCT
29EXTERNAL
30FLAGS
31DATA

Some of these are wasted space in the WASM standard. Understandably WASM is bytecode, meaning it is written and read on byte boundaries, as it is faster and more readable, but by reading the standard I realized many of these use too many bytes:

• FLAGS: Only ever 3 bits
• ATTRIBUTE: Unused
• MEMORY_IDX: Only 0 in the current standard
• SECTION: The ID is only ever 5 bits
• STRING: If the string represents a function name defined in the runtime API it can be represented as an enum instead, otherwise represented under huffman coding
• EXTERNAL: Only ever 4 bits

For every other item the integer encoding or LEB size can be tweaked.

I made a parser that does a 2 pass sweep over the WASM module, the first pass for finding optimal settings and the huffman trees and the second pass for transforming each item, and by reading the WASM module low level and transforming each item to and from the optimized bitcode megabytes of WASM can be transformed in a millisecond, perfect for quick conversion to WASM when a QR code containing optimized bitcode is read.

The result of all of this optimization is WASM modules that are generally half the size:

link Size Savings

Size savings from optimized bitcode

link Standard Library

To eek out even more savings I implemented many functions you would normally write in your program in the standard library:

 1// Drawing
 2// Set size of window
 3void mni_set_bounds(int width, int height);
 4// Set fill style
 5void mni_set_fill(int r, int g, int b, int a);
 6// Set stroke style
 7void mni_set_stroke(int r, int g, int b, int a);
 8// Set line width
 9void mni_set_line_width(int w);
10// Draw rectangle with specified fill and stroke
11void mni_draw_rect(int x1, int y1, int x2, int y2);
12// Draw arc (ovals and circles) with specified fill and stroke
13void mni_draw_oval(
14	int center_x, int center_y, int radius_x, int radius_y, float start_angle, float sweep_angle);
15void mni_draw_circle(int center_x, int center_y, int radius, float start_angle, float sweep_angle);
16void mni_draw_full_oval(int center_x, int center_y, int radius_x, int radius_y);
17void mni_draw_full_circle(int center_x, int center_y, int radius);
18// Draw rectangle over entire screen, ignore stroke
19void mni_clear_screen();
20// Set font
21void mni_set_font(char* name);
22// Set font size
23void mni_set_font_size(int size);
24// Get text width when rendered, taking into account set font size
25int mni_get_text_width(char* text);
26// Draw text with bottom left corner being coordinates (not including bottom of y etc)
27void mni_draw_text(char* text, int x, int y);
28// Draw text with no stroke, only fill
29void mni_draw_text_fill(char* text, int x, int y);
30// Draw image RGB
31void mni_draw_rgb(uint8_t* image, int w, int h, int x, int y);
32// Draw image RGBA
33void mni_draw_rgba(uint8_t* image, int w, int h, int x, int y);
34// Load PNG from path as RGBA, returning buffer containing image and the width and height
35uint8_t* mni_load_png(char* image, int& w, int& h);
36
37// Input handling
38bool mni_has_rotation();
39int mni_get_rotation();
40bool mni_is_pressed();
41float mni_get_x_pressed();
42float mni_get_y_pressed();
43
44// Built in math stdlib functions
45float mni_sinf(float x);
46float mni_cosf(float x);
47double mni_sin(double x);
48double mni_cos(double x);

link Example program

This shows a bouncing rectangle with the text mni.codes above it:

 1#include <mni/wasm/imports.h>
 2
 3#include <stdint.h>
 4
 5extern "C" {
 6__attribute__((used)) const char* mni_name() {
 7	return "mni.codes Basic";
 8}
 9
10constexpr int width     = 500;
11constexpr int height    = 500;
12constexpr int font_size = 60;
13
14__attribute__((used)) bool mni_prepare() {
15	mni_set_bounds(width, height);
16	mni_set_font("Hack");
17	mni_set_font_size(font_size);
18	mni_set_stroke(0, 0, 0, 255);
19	return true;
20}
21
22__attribute__((used)) bool mni_render(int64_t frame) {
23	// Set fill for clearing the screen
24	mni_set_fill(255, 255, 255, 255);
25	mni_clear_screen();
26	int rect_size = mni_sin(frame / 25.0) * 200 + 200;
27
28	// Draw the box
29	mni_set_line_width(10);
30	mni_set_fill(0, 0, 255, 255);
31	mni_draw_rect(100, height - rect_size, width - 100, height);
32
33	// Draw text centered on top of moving box
34	int text_width = mni_get_text_width("mni.codes");
35	mni_set_line_width(1);
36	mni_set_fill(0, 0, 0, 255);
37	mni_draw_text("mni.codes", width / 2 - (text_width / 2), height - rect_size - font_size / 2);
38	return true;
39}
40}

link Examples Of Output

Showcase of various programs

link Security Concerns

Should a project like this go mainstream security issues would need to be addressed. In addition to issues with normal QR codes there are additional issues with allowing untrusted code from the real world to run on your device: how is code signing performed? How should sensor permissions like gyro be handled? How can jumpscares and strobe be made impossible?

link Applications

• Restaurant menus
• Floor map
• Fun games
• Surveys
• Informational documents

link Future Ideas

• Larger standard library
• New multi-color QR codes to store more data
• Multiple QR codes linked together to form one mni code
• Encrypted mni codes
• Usage in other constrained environments like the blockchain

link Questions?

Feel free to check out mni.codes or use the Contact button to the side.