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?

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 build it, 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.

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.

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.

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:

NUM
SIZE
SECTION
STRING
TYPE
INDEXED_TYPE
LIMIT
MEMORY_OP
INSTRUCTION
INSTRUCTION32
ATTRIBUTE
BREAK
FUNCTION
TABLE
LOCAL
GLOBAL
MEMORY
TAG
I32
I64
I128
F32
F64
ATOMIC_ORDER
SEGMENT
MEMORY_IDX
LANE
STRUCT
EXTERNAL
FLAGS
DATA

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:

Size Savings

Size savings from optimized bitcode

Standard Library

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

// Drawing
// Set size of window
void mni_set_bounds(int width, int height);
// Set fill style
void mni_set_fill(int r, int g, int b, int a);
// Set stroke style
void mni_set_stroke(int r, int g, int b, int a);
// Set line width
void mni_set_line_width(int w);
// Draw rectangle with specified fill and stroke
void mni_draw_rect(int x1, int y1, int x2, int y2);
// Draw arc (ovals and circles) with specified fill and stroke
void mni_draw_oval(
	int center_x, int center_y, int radius_x, int radius_y, float start_angle, float sweep_angle);
void mni_draw_circle(int center_x, int center_y, int radius, float start_angle, float sweep_angle);
void mni_draw_full_oval(int center_x, int center_y, int radius_x, int radius_y);
void mni_draw_full_circle(int center_x, int center_y, int radius);
// Draw rectangle over entire screen, ignore stroke
void mni_clear_screen();
// Set font
void mni_set_font(char* name);
// Set font size
void mni_set_font_size(int size);
// Get text width when rendered, taking into account set font size
int mni_get_text_width(char* text);
// Draw text with bottom left corner being coordinates (not including bottom of y etc)
void mni_draw_text(char* text, int x, int y);
// Draw text with no stroke, only fill
void mni_draw_text_fill(char* text, int x, int y);
// Draw image RGB
void mni_draw_rgb(uint8_t* image, int w, int h, int x, int y);
// Draw image RGBA
void mni_draw_rgba(uint8_t* image, int w, int h, int x, int y);
// Load PNG from path as RGBA, returning buffer containing image and the width and height
uint8_t* mni_load_png(char* image, int& w, int& h);

// Input handling
bool mni_has_rotation();
int mni_get_rotation();
bool mni_is_pressed();
float mni_get_x_pressed();
float mni_get_y_pressed();

// Built in math stdlib functions
float mni_sinf(float x);
float mni_cosf(float x);
double mni_sin(double x);
double mni_cos(double x);

Example program

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

#include <mni/wasm/imports.h>

#include <stdint.h>

extern "C" {
__attribute__((used)) const char* mni_name() {
	return "mni.codes Basic";
}

constexpr int width     = 500;
constexpr int height    = 500;
constexpr int font_size = 60;

__attribute__((used)) bool mni_prepare() {
	mni_set_bounds(width, height);
	mni_set_font("Hack");
	mni_set_font_size(font_size);
	mni_set_stroke(0, 0, 0, 255);
	return true;
}

__attribute__((used)) bool mni_render(int64_t frame) {
	// Set fill for clearing the screen
	mni_set_fill(255, 255, 255, 255);
	mni_clear_screen();
	int rect_size = mni_sin(frame / 25.0) * 200 + 200;

	// Draw the box
	mni_set_line_width(10);
	mni_set_fill(0, 0, 255, 255);
	mni_draw_rect(100, height - rect_size, width - 100, height);

	// Draw text centered on top of moving box
	int text_width = mni_get_text_width("mni.codes");
	mni_set_line_width(1);
	mni_set_fill(0, 0, 0, 255);
	mni_draw_text("mni.codes", width / 2 - (text_width / 2), height - rect_size - font_size / 2);
	return true;
}
}

Examples Of Output

Showcase of various programs

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?

Applications

Restaurant menus
Floor map
Fun games
Surveys
Informational documents

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

Questions?

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