The MICROCOSM pipeline: getting to 64k
Build flavours, the flags, and the tools that keep the demo under 64 KB

make code-report and make shader-report replay the packer's model over the payload and charge each coded bit to the function, array or shader it falls in (codecost.py and shadercost.py). On this build the stream divides up like this.

These are rounded model costs; the ideal code lengths total about 59,904 B, and the real stream is 59,929 B including coder overhead. A part's cost also depends on everything before it in the file, so each figure is what that part adds where it stands.

Nearly half the stream is GLSL. The costliest shaders build geometry on the GPU: the jungle's trees (jt.vert, about 2,368 B), Scene 2's seabed placement (uwplace.comp, 2,350 B), the creature kit that sculpts the animals (jr.comp, 1,796 B) and the blob ashore with what it carries (jo_blob.vert, 1,617 B). On the C side the costliest function is render_scene2 (2,490 B), then the synth's mc_synth_render (1,581 B) and uw_prepare, which sorts Scene 2's props into batches each frame (1,196 B). Add the launcher's 3,308 bytes, and 2,299 of the 65,536 are left.

A demo is a directory under demos/. Each one builds into its own build/<name>/, so two demos never write the same file, and independent demos can build in parallel with make -j all.

demos/
├── hello-world/       the reference demo (DEMO's default)
│   ├── main.c         the show: Scenes 1 and 2 and the end card
│   ├── scene3.c       Scene 3, which includes its packages, s3_*.c
│   ├── programs.def   the program manifest (it includes scene3.def and s3_*.def)
│   └── shaders/       56 shader files (*.vert / *.frag / *.comp)
└── my-intro/          your next one
    ├── main.c
    └── shaders/       (optional - omit it if your GLSL is inlined as strings)

make hello-world             # build/hello-world/{hello-world-dev.bin, hello-world.bin}
make my-intro                # build/my-intro/{my-intro-dev.bin, my-intro.bin}
make all                     # every demo under demos/

The dev build gets MC_SHADER_ROOT, the demo's shader directory, and reads its shaders from disk. The release build runs genshaders.py for every demo. It bakes the files in shaders/ and the engine's post-pass shaders into one blob in build/<name>/shaders_gen.h, in the order of the program manifest. A demo without shader files still goes through the bake, and the engine's shaders then go into mc_engine_shaders.h on their own. A tiny64 program builds as a dev binary but can't be packed into a 64k payload. The payload compile leaves out mc_window_close, mc_uniform, mc_set_f and mc_set_v3, and the facade calls all four. What a demo directory needs is in the tutorial.

make capture records the show as the release video: 1920x1080 at 60 fps with its soundtrack, every frame rendered offline. The result is media/<demo>-1080p60.mp4, and VIDEO puts it somewhere else. It sits outside build/, so make clean doesn't delete it. Nothing is shown or played while it runs.

The published video was made this way from the current demo, and the repository stills are frames taken from it (see The stills and the poster). It was rendered on a laptop's Intel UHD 620 integrated graphics using Mesa, at 3840x2160 internally and downsampled to 1920x1080. Its 60 fps is the playback rate of an offline render, not a measured real-time frame rate on that GPU.

It builds a third binary, build/<demo>/<demo>-capture. That's the demo's capture main() (-DMC_CAPTURE, surfaceless EGL), built with the release flags but linked the normal way, without fpround.py. So its pictures match the .bin's, Scene 1's collision sim included, apart from that rounding. It renders each frame and streams it to stdout as raw RGBA. With MC_CAP_AUDIO=<file> it writes the soundtrack to that file instead, as float32 stereo at 44.1 kHz.

tools/capture.sh runs it twice, once for the soundtrack and once for the frames. It makes the video in two steps, so that the slow render only happens once.

First the frames go into a near-lossless master, build/<demo>/capture/master.mkv (x264 faster at CRF 8). For the whole show that's 16,722 frames and about 2.5 GB, so leave about 3 GB free. The published version's master took about 57 minutes on the Intel UHD 620 laptop, before the two final encoding passes. If a run stops after the master is finished, the next run reuses it, as long as the binary and the settings are the same.

Then x264 encodes the master in two passes (slow, -tune film, aq-mode=3, high profile at level 4.2), at an average of 10 Mb/s with peaks held to 40 Mb/s. The soundtrack goes in as AAC at 256 kb/s, and the picture is converted to BT.709 and tagged as such. The two passes add to the master's time. When the video is written, build/<demo>/capture/ is deleted.

The published video comes to about 357 MB. Its bitrate was chosen for the video's film grain and fast reef flight. At 2.5 Mb/s, which would fit in 100 MB, the reef smears into mush with both H.264 and AV1, while the jungle needs only about 4 Mb/s at the same quality. So the video is published as a release file and .gitignore keeps it out of git (the publishing page explains why).

MC_CAP_SCALE sets the internal resolution for the whole show, from 25 to 200% of the frame. The default, 200, renders every frame from 2160 lines, as the release renders Scene 1. The TAA resolves the larger frame and the present pass filters it down, which gives a sharper video. 100 renders about twice as fast, for a preview. MC_CAP_DUR records only the first so many seconds, and BITRATE (10M) sets the average bitrate. Make passes these from its command line on to the script, so you can write make capture MC_CAP_DUR=10 MC_CAP_SCALE=100 VIDEO=start.mp4.

-std=gnu11 -Oz -fno-inline-functions-called-once -fno-inline-small-functions
-fno-caller-saves -mtune=k8 -mstringop-strategy=libcall -fno-ira-hoist-pressure -fno-if-conversion
-fno-cse-follow-jumps -fno-shrink-wrap -fno-tree-sra -fno-tree-scev-cprop
-fno-gcse-lm -fno-tree-coalesce-vars -fno-ipa-pure-const -fno-ipa-ra -fno-thread-jumps -fno-lra-remat -fno-jump-tables
-fno-schedule-insns2 -fno-peephole2 -fno-optimize-sibling-calls
-fno-tree-tail-merge -fno-move-loop-invariants -fno-tree-dse -fno-tree-pre
-ffast-math -fno-exceptions -fno-plt -fno-stack-protector
-fno-unwind-tables -fno-asynchronous-unwind-tables -fomit-frame-pointer
-fcf-protection=none -Wa,-mx86-used-note=no
-ffunction-sections -fdata-sections -fno-pic -fno-pie -fvisibility=hidden
-flto -DMC_RELEASE -Iinclude -Ibuild/<demo>

Some flags are left out because they change the output. -fno-ipa-vrp, -fno-tree-forwprop and -fno-tree-loop-im move pixels in Scenes 1-2. -fno-ipa-modref changes the audio by float noise (at most 1.8e-7, or -135 dBFS). -frounding-math, -fno-tree-reassoc, -fsignaling-nans and -fsingle-precision-constant change pixels or audio too. -mavx and -march=x86-64-v3 make the stream bigger because of the VEX encodings, and every -mtune other than k8 does worse than k8.

-no-pie -flto -flto-partition=one -Oz -fno-inline-functions-called-once -fno-inline-small-functions
  (the codegen lines 2-6 of REL_FLAGS again: with LTO, code is generated at link time)
-Wl,--gc-sections -Wl,--build-id=none
-Wl,-z,norelro -Wl,-z,noseparate-code -Wl,--hash-style=sysv -s

The link leaves out -z nosectionheader and keeps the section-header table, because textrange.py reads .text's file range from it for the packer's x86 coder. elfshrink.py then drops the table just as the flag would have, so the payload comes out byte-identical. The release link also runs twice, as described below.

Every payload compile gets -DMC_IMPORT_HASH, and the payload link gets -nostartfiles -Wl,--no-as-needed and -B$(OUT)/.release/fpround/, which points it at the assembler that rounds the float constants (below). They're kept out of REL_FLAGS because tools/verify.py reuses that for its normally linked test programs. The section on keeping libc explains them.

• The float constants are rounded. With -flto -flto-partition=one the payload's code is generated at link time as one unit of assembly, and fpround.py rewrites that assembly on its way to the assembler. Each float and double constant in the pool whose uses are all floating-point is rounded to the coarsest value within 2^-16 of it, and the pool is laid out by bit pattern. That saves about 560 B of stream, and its section has the details.
• The payload is linked twice. The first link writes a link map, which funcorder.py turns into a --section-ordering-file that lays the functions out by similarity, and the second link uses that file. Only the order of the code changes, but the packer's models prefer the new order by about 320 bytes of stream. make runs both links only when an object changed, so a no-op rebuild stays a no-op.
• textrange.py records .text's file range in .release/payload.range for the packer. Then elfshrink.py removes the section-header table and truncates the slack it leaves, keeping the program segments intact. make dist verifies a candidate before it replaces the retained payload.
• mkelf.sh hands off to pack.py, which compresses the ELF with the context-mixing coder in cm.h and builds the freestanding launcher around the stream. The coder's x86 transform and instruction models only apply inside --code-range. The launcher decodes in RAM and runs the result through memfd_create and execveat. It's static and has no dependencies at all, not even libc, though the unpacked demo does need the graphics and audio libraries.

• The launcher has two stages, each built with its own flags instead of the release flags above. They are -Oz -nostdlib -static -ffreestanding -fno-builtin -fno-tree-loop-distribute-patterns (no libc, and no calls to memset=/=memcpy that the compiler would otherwise invent), -fcf-protection=none -fno-asynchronous-unwind-tables -fno-unwind-tables (no endbr64, no .eh_frame), -malign-data=abi and --build-id=none.

  The second stage is tools/s2dec.S, the payload decoder and the memfd glue, with the cm.h model written by hand. It's only assembled, then linked by stage2.ld to run at S2_ADDR (0x800000), and it ships coded for the first stage to decode. Because it's assembly, it's written directly for its coded size under the first stage's coder, and there's no C-flag search for it. The C decoder mcstub.c is the reference model and a fallback second stage (-DMC_STAGE2), linked the same way.

  launcher.ld links the first stage (s1dec.S) as a raw image (--oformat=binary) whose first bytes are its own ELF header. The image is one RWX PT_LOAD of the whole file. Its program header is folded into the ELF header's last 8 bytes, and the entry code sits in header fields the kernel never reads. Notes, comments and unwind data are discarded, and there's no page padding and no PT_INTERP, PT_DYNAMIC or PT_NOTE. The segment's memory size covers the first stage's tables, the second stage and its .bss, and a link-time ASSERT keeps the first stage below S2_ADDR. The self-extractor's section among the tools below has the details.

The Makefile runs every tool below. A target that works on one demo takes it from DEMO, and make <demo> sets that for you.

Put them on make's command line (make dist PACK=quick, make capture MC_CAP_DUR=10), or in the environment. Make hands command-line variables on to its recipes' environment, which is how NM reaches pack.py and the capture's variables reach capture.sh and the capture binary.

It shrinks GLSL so that it compresses better. It must not change behaviour or break any identifier that the host C code looks up by name: uniforms, block names, and attributes or outputs bound by name.

python3 glslmin.py [options] INPUT.glsl [-o OUTPUT.glsl]
python3 glslmin.py --rename [options] A.vert B.frag ... --outdir DIR
  -o, --output     output file (stdout if omitted); INPUT may be "-" for stdin
  --outdir DIR     write each input to DIR/<its file name>
  --stats          print original vs minified byte counts to stderr
  --rename         one rename mapping across all inputs, declaration folding,
                   integral literals as ints
  --protect A,B    extra identifiers --rename must never touch
  --map FILE       write the --rename mapping (original new)
  --int-arith      with --rename, also integral literals inside * / + -
  --selftest       run the built-in test suite and exit

A few transforms are always on, and all of them are safe. It strips comments and cuts whitespace down to what keeps neighbouring tokens from fusing. It decides that by re-tokenizing each pair, with explicit guards so that /=+=/ never forms // and so on. It also shortens float literals (1.0 to 1., 0.5 to .5, 1.0e3 to 1.e3) but leaves exponents and integers alone. Preprocessor directives stay one per line.

--rename minifies a whole set of shaders together, and genshaders.py always runs it over the demo's and the engine's shaders in one go. It's plain alpha-renaming: each old name gets a different new one, and no new name collides with a name that stays. So it can't change behaviour as long as nothing outside the GLSL knows the old names.

• These keep their names: uniforms without layout(location) or layout(binding), every interface-block name, vertex inputs and fragment outputs without layout(location), --protect names, built-ins, keywords, reserved words, gl_*, swizzles, #version=/=#extension lines, #=/=## macros, and anything a shader uses without declaring it. The tool fails closed, so a built-in it doesn't know is never renamed.
• These are renamed: functions, parameters, locals, globals, const=s, struct types and their members, members of uniform blocks, block instances, =#define names, varyings (the same way in both stages), and uniforms that have a layout(location) or layout(binding). Located and bound uniforms are safe to rename because the C side sets them by number. The demo gives a location to every uniform it sets and a binding to every sampler that isn't on unit 0. std140 blocks are filled by offset, so never query a member by name.
• One mapping covers every file. A file-scope name gets the same short name in every file. A function's parameters and locals are numbered in order of first use inside that function, and local k has the same name in every function, so a helper copied between files stays byte-identical for the coder. Each kind of name has a family of its own: a first letter for the kind, then a running character in the order x y z w a..v X..W A..V 0..9 _. The swizzle letters come first because the coder already sees them everywhere. Locals are Vx Vy Vz Vw Va … in order, functions Ux Uy …, members Tx Ty …, and the rest of the file-scope names (globals, varyings, uniforms, struct types, macros) Sx Sy and so on. Within each family the most used names come first. So the first letter of a name says what kind of name it is, and a function's k-th local is spelled the same everywhere. The coder's word and statement contexts pick up on both. The family letters are capitals the text hardly uses otherwise, since those code best.
• Declarations are folded. Consecutive declarations with the same qualifiers and type become one list (uniform float a;uniform float b; becomes uniform float a,b;). It never folds in struct or block bodies, across directives, on layout() or array-typed prefixes, or onto a declaration that is an unbraced if body.
• Integral literals are written as ints. 2. becomes 2 wherever GLSL's implicit int-to-float conversion gives back the same float and the same arithmetic. That covers a whole constructor argument (vec3(0.,1.,0.) becomes vec3(0,1,0)) and the whole right-hand side of a float initializer or assignment. It also covers an operand of < > < >= = != whose partner sub-expression is float-family, one branch of a float ?:, and float-only parameters. Those are smoothstep, step, mix's third, mod's second, textureLod's lod, clamp, min and max after a float first argument, pow with a scalar float base, and a float parameter of a user function that's defined once. Operand types come from the declarations, per function scope. Anything it can't type keeps its dot, and it never converts both operands of one operator. Nor does it apply in return, because Mesa converts no return value. Inside * / + - it only applies with --int-arith. The value is still exact there, but Mesa then fuses a*2.+b and a*2+b into different multiply-adds and a few pixels move by a rounding step, so the build leaves it off.
• Casts are dropped the same way. An explicit float(X) of an int expression X goes wherever its int would convert to the same float (a*float(i) becomes a*i, vec2(float(i+1),0) becomes vec2(i+1,0)). That includes arithmetic, since the compiler converts X at the same point either way: it's the literals that get folded early and change the fusing. X only counts as int if it's built from int literals, int and ivec component names, int(...) and the integer operators. Its brackets go when it's one operand, or a whole argument or initializer.
• Uncalled functions go first. Before the renaming counts uses, every function that a shader never calls from main is dropped, so dead helpers don't skew the naming. genshaders' own dead-function pass still runs afterwards.
• Swizzles use one alphabet: .rgb becomes .xyz and .a becomes .w, unless some struct member is spelled like a swizzle.
• Functions are overloaded by argument count. They share a name as long as the name is nothing else anywhere and no shader has two of them with the same argument count. The int-literal pass picks a user function's signature by its argument count, and genshaders' dead-function pass counts a call only for the definition with that count. Functions with equal counts never share a name, since telling them apart by argument types would let dead helpers survive.
• Locals that are read once are inlined. A local that's read exactly once is folded into its read when nothing could tell the difference. The types must match (an expression typer works them out from the declarations), and the read must come later in the same block, in a plain statement, a declaration, a return or an if condition. Nothing it reads may be written in between, it can't have side effects, and no derivative may be carried past a return or discard. The driver is the harder part. Mesa rewrites expression trees before it builds SSA, so a moved expression can compile to different code, and each shape that did is excluded. The folded expression never holds ?:, && or ||. It takes a swizzle, an index, a unary operator or a divisor only as a single token, and it joins a * / % chain only as a product, call or name without / or %.
• Brackets the parse doesn't need are dropped.
• Source it can't follow (unbalanced brackets, anonymous or function-local structs, an unrecognised NAME {) raises an error instead of guessing.

None of these transforms should change any picture. The rules for literals and inlining leave out the expression shapes that make Mesa compile different code. Shader literals are never rounded the way fpround.py rounds the code's constants. Unlike in the C code, a shader's pixels move with its literals, and a hash's constants, once rounded, draw a different pattern altogether.

--selftest runs the built-in suite, which covers cross-file consistency, varyings, uniform/block protection, located and bound uniforms, swizzles, macros, members, shadowing, fail-closed cases and folding. It passes on this tree. tools/verify.py links every raw and every minified program pair with glslangValidator.

It minifies every *.vert=/=*.frag=/=*.comp=/=*.glsl in the demo directory, and with --engine the ones in the engine's src/shaders too, all in one glslmin run with one rename mapping. Then it drops every function a shader never calls, since the shared blocks bring in helpers that a given stage doesn't use. Before that it drops each #define that nothing expands, so that a fragment-only helper reached only through such a macro goes too. Scene 3's s3light is one, and without this its shadow chain would stay in every vertex shader. Text that several of the demo's shaders share is stored once (see below), and the output is a C header that defines the following.

static const char mc_shader_dict[];          // the shared text, NUL-separated
static const char mc_shader_blob[];          // every shader, NUL-separated, with references into it
static const char *mc_shader_at(int i);      // shader i, spelled out in full
static const unsigned char mc_program_shaders[][2];   // per program: (vs, fs) indices
static inline const char *mc_demo_shader(const char *name);   // by file name, for the tools

The minified demo shaders are cut into top-level pieces, each a run of declarations or a function. A run of pieces that recurs in several shaders, such as the jungle's common block or a helper copied between files, is kept once in mc_shader_dict. The blob holds one byte in its place, 0x80 plus the entry's index, and an entry may itself refer to earlier ones. Runs are chosen greedily by what they save. The packer's match model already makes a repeat cheap, so the selection prices a repeated byte at 0.04 B of coded stream, against about 1 B for a reference. Only long, frequent runs qualify, up to 128 of them. mc_shader_at spells the whole blob out into a .bss buffer on first use (mc_shader_spell, recursive), so what GL compiles is byte-identical to the unshared text. --emit-dir and the shader checks see the unshared text.

In MC_RELEASE builds the demo #include=s this header instead of reading files, and builds program /i/ from =mc_program_shaders[i], in programs.def order (genshaders.py reads that file and the manifests it includes). So the payload has no file names and no strcmp chain. A compute program is listed with the same file for both its stages (MC_PROGRAM(jr_mesh, "jr.comp", "jr.comp")), and mc_shader_make compiles a compute shader when it's handed the same source twice.

The blob holds the vertex and compute shaders first, then the fragment shaders, each group largest first, because the coder did best on that order. The engine's post-pass shaders go at the end of the same blob and use the same dictionary. The engine header (--engine-output) names each one after its file (post.vert gives POST_VS, bright.frag gives BRIGHT_FS). Under MC_RELEASE each name is mc_shader_at(k), and otherwise it's a plain minified string for the tools' checks. render.c includes that header in every build. Dev builds get a version with the sources as written (--raw, under build/<demo>/.dev/include), so a dev compile error points at readable GLSL.

python3 tools/genshaders.py demos/hello-world/shaders -o build/hello-world/shaders_gen.h \
    --engine src/shaders --engine-output build/hello-world/mc_engine_shaders.h
# --emit-dir DIR also writes every minified shader (verify.py links those),
# --map FILE the rename mapping, --no-rename skips renaming.

make runs it. Its stamp covers both shader directories and the demo's .def manifests, whose order the program table follows, so reordering or repointing an MC_PROGRAM remakes the header and the objects that include it. A minification failure stops the build and leaves the previous headers in place. --allow-raw makes it fall back to the raw sources instead, which is meant for diagnostics and is off by default. If the output hasn't changed, the header's modification time stays as it was.

It replays the packer's model (cm.h, in the configuration the last pack chose, read from pack.json) over the release payload bit by bit, and adds up the coded bits that land on each shader's text in the blob and on each entry of the shared dictionary. A shader's cost depends on everything before it, because the model has seen every earlier byte, so the figure is what that shader actually adds to the packed file. Shader text is about half the stream: 28.9 KB of the 59.2 KB in this build.

python3 tools/shadercost.py [BUILD_DIR] [--save FILE] [--against FILE]
make shader-report              # the same, on the current build

--save writes name<TAB>bytes for every shader and entry. --against compares with such a file and shows the changes per shader, largest first, and in total. The sums are the model's ideal code length, and the real stream adds a byte or two of coder overhead.

This is shadercost.py's replay applied to the code, with the coded bits summed per function and per named array instead of per shader. The payload is compiled with -ffunction-sections -fdata-sections, so the map of its second link (kept as .release/payload.map) gives every function and every named array an input section of its own, which maps to its bytes in payload.elf. LTO's .isra and .constprop clones appear under their own names. Whatever no name covers is summed in groups: the compiler's float constant pool (.rodata.cst4/8/16), string literals, unnamed .rodata (switch tables), alignment padding, and the ELF headers, dynamic tables and gaps. Each name is then traced to the source file that defines it, among those the payload's objects were compiled from, to give totals per file. That goes through the objects' -MMD files, because LTO's single partition hides where a function came from. scene3.c and the s3_*.c packages count as themselves, not as the main.c that includes them.

python3 tools/codecost.py [BUILD_DIR] [--top N] [--save FILE] [--against FILE]
make code-report                # the same, on the current build

In this build, of the 59.2 KB stream, the shader text and the code that spells it out (shaders_gen.h) take 29.1 KB, main.c 12.4 KB, synth.c 4.5 KB, scene3.c 2.5 KB and render.c 1.8 KB. The most expensive functions are render_scene2 (9,502 bytes of code, 2,451 packed), mc_synth_render (1,653) and uw_prepare (1,199). The compiler's float constant pool is 2,348 bytes, which code to about 999. That's 3.4 bits a byte after rounding and sorting (fpround.py, below), and still more than code costs. The import hashes next to it don't compress at all (mc_imp_hash: 166 bytes, 176 packed).

--top sets how many functions and arrays to list (40, or 0 for all). --save writes name<TAB>bytes<TAB>file for every row, and --against compares with such a file, per row and per source file. A static defined in two of the payload's sources would show up as ? (2 files), and there are none. A name it can't trace at all shows as ?, such as the 8-byte bypass.0, a static local inside a function.

It reads the MC_IMPORTS(X) list and MC_IMPORT_HASH_BITS from include/microcosm/mc_imports.h, and writes #define MC_IMPORT_HASH_BYTES and #define MC_IMPORT_HASHES for src/mc_start.c. Each hash is the low MC_IMPORT_HASH_BITS of the entry's GNU name hash, stored little-endian in as few whole bytes as that needs, and the hashes go back to back in list order. It fails on a duplicate name, or if two hashes are equal at that width. Collisions with the other names that the libraries export are left to importcheck.py, after the link.

python3 tools/genimports.py include/microcosm/mc_imports.h -o build/hello-world/mc_imports_gen.h

It runs in the payload's link rule, on the second link and its -Map file, before elfshrink.py drops the section headers. It walks the code with the packer's own x86 decoder (cm_xfield from cm.h, compiled on the fly) and collects every RIP-relative operand, since that's how GCC reaches a member of a global table. Then it checks that at least one instruction reads each slot of mcgl (MC_GL_FUNCS) and of mc_imp (MC_IMPORTS). The loaders' own indexed stores don't count, and neither does a lea. An entry that nothing calls still costs its name or hash in the packed file, so the link fails and names it.

importcheck: the payload resolves these at startup but never calls them:
  GL entry points (mc_gl.h, MC_GL_FUNCS): DeleteShader
  imports (mc_imports.h, MC_IMPORTS): strcmp
move a GL entry point into MC_GL_TOOLS(X) and drop an import's X() and #define, or build with IMPORTCHECK=warn

Next it asks the payload's own dynamic loader (its PT_INTERP, run with --list) which libraries the payload maps: the DT_NEEDED ones and their own dependencies, 10 here. It reads their dynamic symbols the way the resolver will (defined functions, indirect functions and objects, default versions), and fails if any import's hash, truncated to MC_IMPORT_HASH_BITS, equals the hash of another of those names. On this machine, at 16 bits it would list seven, getenv against rintl among them. A collision always fails the link. On success it prints one line:

importcheck: 65 GL entry points and 55 imports, every one called; no 24-bit import hash shared with another of the 7,600 names 10 libraries export

The lists belong to the engine but the check is per payload, so unused entries only fail the link for hello-world. Any other demo may use less of the engine than the reference one, so IMPORTCHECK defaults to warn there and its unused entries are only listed. IMPORTCHECK=error makes it strict, and make hello-world IMPORTCHECK=warn relaxes it for the reference demo. Both checks take under half a second, and the walk agrees with objdump -d on all 2,470 of the payload's RIP-relative operands. The second link's map stays next to the payload as payload.map, which codecost.py reads.

python3 tools/importcheck.py build/hello-world/.release/payload.elf.tmp build/hello-world/.release/payload.elf.map

A pure-Python ELF64 post-processor that does what sstrip does. After checking that the input is a 64-bit little-endian x86-64 ELF, it zeroes the e_sh* header fields and cuts off the trailing bytes the section-header table held, leaving every program segment and the program-header table intact. It refuses if the cut would take bytes that are needed, for example when the section headers aren't at the end.

python3 elfshrink.py INPUT -o OUTPUT [--verify] [--golf]

The payload's link rule runs it with --verify, which parses the output again and confirms every segment still fits. It also passes --golf, which blanks what the loaders never need in a fixed-address executable that imports nothing by name. One is the PT_PHDR entry, since the kernel passes AT_PHDR anyway and the load bias it gives ld.so is 0 for ET_EXEC. The other is the empty dynamic symbol table's hash table: DT_HASH and DT_SYMENT, along with the table's bytes. ld.so skips a map that has no hash buckets. DT_SYMTAB stays, because glibc's ld.so crashes at startup without it. The blanked bytes become zeros, which cost the packer next to nothing, and no offset moves. --golf silently skips anything that doesn't look like that payload. In the 64,365-byte version, before the current size reductions, this took the payload from 249,856 to 248,968 bytes. pack.py checks its input with the same parser.

It reads a freshly linked ELF64's section headers and prints the file range of its .text section, in the form 0x214 0x17dd3. The Makefile runs it on the payload just before elfshrink.py drops those headers, which doesn't move any file offsets. The range goes to pack.py --code-range, so that the coder applies its x86 transform and instruction models only to real code.

python3 tools/textrange.py build/hello-world/.release/payload.elf.tmp

It reads a first link of the payload and its -Map file, and prints a linker --section-ordering-file for the second link. Each function's bytes become a set of 4-byte grams, and the functions are chained greedily, starting from the largest. Each step takes the unplaced function that shares the most grams with the last one, scaled by the square root of the union so that big functions don't swallow everything. Ties go to the first name in sorted order, so the output depends only on the inputs. Related code ends up side by side, where the coder's context and match models find it, and the code itself doesn't change. On this payload, coded with the shipped configuration, the function order takes 321 B off the stream against the linker's own order.

The same file lists .rodata's input sections in the first link's order, except that the shader text (mc_shader_blob, then mc_shader_dict) moves to the end. The binary tables then follow the code that reads them, and the text runs to the end of the section, blob before dictionary, which codes better than the other way round. That takes another 63 B off this payload's stream.

python3 tools/funcorder.py FIRST_LINK.elf FIRST_LINK.map > payload.order

The C code's float and double literals, and every constant GCC folds from them (the bar lengths that BAR_S makes, 1.0f / 12.0f and so on), live in an anonymous pool: the .LC labels in .rodata.cst4/8/16. In the 64,365-byte version, before the current size reductions, that was 557 entries of 4 and 8 bytes (511 floats and 46 doubles) and two 16-byte masks. The detailed before/after counts in this section refer to that version. Most of them carry the noisy mantissa of a decimal literal (0.35f is 0x3eb33333). fpround.py rounds each one to the coarsest value within 2^-16 of it (|error| <= 2^-16 |x|), which zeroes at least the low byte of a float and 37 bits of a double. Then it lays the 4- and 8-byte entries out in ascending order of their bit patterns.

python3 tools/fpround.py [--rel N] [--double N] [--tight ROOTS:N] [--no-sort] IN.s -o OUT.s [--report FILE]
python3 tools/fpround.py --install-as DIR [--off] [POLICY] [--report FILE]    # DIR/as, for gcc -BDIR/
python3 tools/fpround.py --selftest

• It works at the link. The payload links with -flto -flto-partition=one, so all its code is generated there, as one LTRANS unit of assembly that holds the whole pool. That includes the folded constants, which a pass over the C literals would miss. -B$(OUT)/.release/fpround/ on the payload link makes gcc assemble that unit with .release/fpround/as, a two-line script that --install-as writes. The script is only rewritten when its text changes, so it doubles as the step's stamp, and a new FPROUND_POLICY relinks. The script rewrites the .s it's handed into a temporary file and runs the real assembler on that. Both links go through it, and funcorder.py, textrange.py and elfshrink.py see its output like any other. The link itself is still GCC's own. FPROUND=0 writes an as that only runs the real one, and the payload is then byte-identical to one linked without the step. .release/fpround.txt lists every pool constant, what became of it and which functions use it.
• It only rounds a constant if every use of it is floating-point. A use counts if it's an SSE scalar float or double instruction (arithmetic, a compare, a conversion) or an x87 one. So does a load into a register whose value meets nothing but those, register copies, stores of its own width, call arguments in xmm0-7 and the return value. The value is followed through the function's branches until something overwrites it. GCC gives each pool entry one mode, so 8 bytes loaded into %rax and stored away are the same double that a mulsd reads elsewhere. An entry that nothing reads as a float stays as it is. A bitwise use (the andps / xorps abs and sign masks) pins the constant as written. So do an integer use, a taken address, a packed access, a width other than the entry's and any instruction the tool doesn't know. NaN, infinities, zero and denormals are never rounded either. Five constants stay as written here: the two masks, and three doubles that are only ever copied (125.0, -1e9, and the synth's step length in samples, so that the tempo stays exact). GCC sometimes shares a pool entry: with .set .LC9,.LC141, the float -2.0 is the low half of the double near 19.35. Each side then gets its own copy when either one changes.
• The bound of 2^-16 limits every consequence without having to know what a constant means. The timeline's constants turn up in nearly every per-frame function. S3_REX is 27 bars, for instance, and the blob counts its hops in beats as j / JO_BEAT, which is folded to j * 2.0667. At 2^-16 none of them moves by more than 2 ms in Scene 3's 114 s, or 4.3 ms over the show's 278.7 s, and a beat rate moves by under 0.01 beat over the show. In the synth, midi_hz's 1/12 moves by 7.6e-6 (under 0.03 cents three octaves from A4), and the sample period 1/44100 by 4.65e-6, which raises every voice by 0.008 cents. A coarser bound packs smaller, but moves the timeline by tens of milliseconds.
• The sort only changes the entries' addresses inside .rodata.cst4 and .cst8, and the code's references follow their labels. In order of bit pattern, neighbours share sign, exponent and top mantissa bits, which the coder's sparse contexts predict. Rounding also lets the link fold together constants that became equal, and here the pool comes out 36 bytes shorter.
• On the 64,365-byte version's payload, before the current size reductions, coded with that version's shipped configuration, rounding and sorting take the stream from 61,588 to 61,026 B. 346 of the 511 floats and 36 of the 43 doubles it may round change, and the rest are already exact (1.0, 0.25, 440.0 and so on).

• --selftest, which verify runs, covers the bounds, the classification, pinning, sharing and the order. In that same comparison, linked with the same function order, the build without the step has the same 20,052 instructions. 2,194 of them differ only in a RIP-relative displacement, and 159 in an address in .data or .bss, which move with the shorter pool. Each of the 1,927 pool references reads the same bytes or a value within 2^-16 (the worst is 1.526e-5).

  In the pictures, the camera paths, the predator's path and the trees of Scenes 2 and 3 move by sub-pixel amounts. Scene 1's collision sim is chaotic, so it plays out a little differently. In the sound, the oscillators' phases drift with the sample period, and a bird call is a random draw against a float level, so the calls can come at other steps. The notes and drums land on the same samples, because the step length is exact.

• It leaves the named tables alone (S3_KEYS, S3_ROAM_KEYS, PALETTE, the synth's envelopes and others, about 200 more noisy floats), because they need their C types, which the assembly doesn't carry. A dozen float immediates in the code stay as they are too. tools/verify.py, the headless build and the capture build link without the step, so they render with the constants as written.
• The timeline stays in the code. The scenes' envelopes (about 100 mc_smoothstepf calls and the lerps on literal times) could be data, the way synth.c's RAMPS are. But the pool, sorted and rounded, already is a table of the distinct times, and its RIP-relative loads are the references. An index, an immediate or a table read costs what those loads do, plus the code that evaluates it.

mkelf.sh turns the release ELF into the shipped .bin, which is itself an ELF, not a shell script. The payload is compressed with MICROCOSM's own context-mixing coder and embedded in a small freestanding launcher, which decodes it in RAM and runs it from an anonymous in-memory file (memfd_create and execveat). The launcher needs no libc, shell, external decompressor or temporary file, and it writes nothing to disk. Its decoder (s2dec.S, the cm.h model in hand-written assembly, with mcstub.c as its C twin) is itself stored coded, behind a first stage written in assembly (s1dec.S).

tools/mkelf.sh INPUT.elf OUTPUT.bin [--budget 65536] [--quick]
  [--cache-dir DIR] [--manifest FILE] [--code-range FILE]

• cm.h holds the whole coder, both the model and the binary arithmetic coder. It's compiled into the host-side compressor (cmpack.c) and into the launcher's decoder, so the two can't diverge. It uses integers only (squash and stretch are built at start-up from an integer recurrence), so every host reproduces the launcher's predictions bit for bit.
• About 41% of the payload is x86-64 code (99,049 of its 241,936 bytes), so the coder reads it as instructions. A small table-driven length decoder (cm_xfield) walks the code range given by --code-range. It knows prefixes, REX, the one-, two- and three-byte opcode maps, ModRM/SIB, displacements and immediates. Before coding, cm_x86t rewrites every rel32 call or jump target and every RIP-relative disp32 as an absolute address, so that every call to one function and every load of one float constant look the same. Conditional jumps keep their relative targets, because those code better as they are. The decoder undoes the rewrite after decoding. The walk only reads prefixes, opcodes and ModRM/SIB, never a field it rewrites, so it sees the same instructions before and after. tools/checks/cmx86.c tests the transform on edge cases (fields straddling the end of the range, truncated instructions, runs of prefixes) and on 200,000 fuzzed buffers.

• The model is in the style of lpaq. Each bit is predicted by hashed context models and a match model. There's one context model per byte mask over the last 8 bytes, which covers the low dense orders and the sparse contexts that suit x86. There are up to four extra models: a word model, the last byte with its place in a 4-byte column, and two indirect models. Those look at what followed the last byte, and what followed the last two, the last time they were seen. And there are seven models keyed on the instruction being decoded:

  • which field the byte is;
  • field, byte index and opcode;
  • the instruction so far, with the opcodes before it;
  • field, byte index and the last byte, alone and with the previous instruction;
  • the instruction so far, with the last instruction of its opcode;
  • one that switches by field. A displacement or immediate byte reads the last two RIP-relative or call targets, with the field and byte index. These are absolute after the transform, so a run of loads from one table, or of calls to one function, predicts the next. A ModRM byte reads the opcode with the previous instruction's opcode and ModRM. Any other byte reads the instruction so far with the previous opcode.

  Past the code range, in the GLSL and the tables, the x86 models would have nothing to see, so they model the shape of the GLSL instead. At each byte the coder tracks the bracket depth, and for each depth the word before the bracket (the function called) and the commas since (the argument). It also tracks the brace depth and each statement's first word. Two contexts use the call and argument, alone and with the last byte, and one the statement's first word with the depth and the last byte. Others take both depths with the last byte, order 3 with the depth, and the classes of the last 16 bytes. The final one takes the first words of this statement and of the one before (the last one that had a first word), with the word so far and the brace depth. The depths only start over at a NUL, which comes before the text and between shaders: brackets balance, so nothing else needs to reset them.

  Each context slot is a 16-bit counter: a 12-bit probability and a 4-bit adaptation count, which counts up to the configured limit. Updates round to nearest. With truncation a counter could reach 0 but would stop 14/4096 short of 1, a bias the mixer would have to undo. The slots are grouped per nibble, 16 to a 32-byte block, in one shared table of 2^26 slots (128 MiB), and slot 0 of each block is a check. A context takes its own block or the neighbouring one, whichever already holds it, or else clears the less used of the two. That way colliding contexts don't pollute each other's statistics.

  The match model looks up the last 8 bytes, and only follows what it finds if the two agree on at least CM_MM bytes. The search picks that length, 13 in this build. A long minimum helps most in the GLSL, where short matches mislead.

  Five neural mixers combine the predictions in the logistic domain. The first selects its weights by match length, the x86 field (outside the code, the last byte's class) and the bits of the byte so far. Each of the other four selects by one of the last four bytes and the bit's position. An optional sixth (CM_NM 6, which this build uses) selects by the x86 opcode, and outside the code by the classes of the last three bytes and by whether the statement's first word is known and a bracket is open. The four leave out the bits of the byte so far, since with them each weight set would see too few bits to learn from. The first mixer keeps them, because without them the stream gets longer.

  A second-layer mixer combines their outputs. Its weights are chosen by the bits of the byte so far and the x86 field or, outside the code, the last byte's class. Two APMs refine the result, and a 32-bit carry-less arithmetic coder codes the bit.

• Two adaptive probability maps follow the second-layer mixer (CM_APM, CM_AR). One is keyed on the bits of the current byte so far (order 0), the other on those and the last whole byte (order 1). Each has 33 buckets spaced 128 apart in the stretch domain, interpolated around the mixer's output and refined toward p = (p + a₀ + 2·a₁) / 4. Both buckets around the point learn the bit. There's also a warm-up (CM_WARM): over the first 2^CM_WARM bytes the first-layer mixers learn four times as fast, and then twice as fast up to four times that, because the weights are far from settled there. Both add to the decoder, so pack.py only keeps them when they win on the whole file (see the search below). This build keeps the APMs and a short warm-up (CM_WARM 1): four times the learning rate for the first two bytes and twice the rate through the first eight.
• The configuration is fixed at compile time, so the launcher only carries what it uses, and it's chosen by a search at build time. The search covers the mask set (up to 24), the extra models, the counter limit, both mixer learning rates, the mixer count and their initial weights, the match model's shortest match, the APMs and the warm-up. PACK=full hill-climbs over it. Each step compiles cmpack.c for 8 neighbouring configurations at once, each with one knob or mask changed, and moves to the best one that shrinks the stream. It stops when a whole neighbourhood fails or 200 candidates are spent. The climb starts from DEFAULT in pack.py, the result of a long search on a recent payload with the current model. From an older DEFAULT the climb ends in a weaker optimum, so DEFAULT should be refreshed whenever the model changes. Candidate order and batch size are fixed, so the result depends only on the payload, its code range and the tools, and it's cached by their hash. This build's pack tried 203 configurations in all. PACK=quick uses DEFAULT, or a cached search result for the same payload. The winner and the code range go into payload_meta.h for the launcher. The stream goes in after the first stage's code with .incbin, so there's no array padding or terminator, and its length is a link-time constant.
• The search minimises the stream, but what has to fit is the whole file. Most knobs cost the decoder nothing, so their best value for the stream is also the best for the file. A few change the decoder's own size, because the launcher compiles in only what it uses: the APMs, the warm-up, the extra-model set (CM_XSET) and the sixth mixer. For those the smallest stream need not give the smallest file, so after the stream search pack.py settles them against the total. It builds the launcher for the search winner and for its neighbours in just those knobs, and keeps the smallest stream + launcher. Building the launcher for every search candidate would be far too slow, but doing it for this handful at the end is cheap and deterministic. This is also where the APM stage has to earn its place: it's kept only when what it takes off the stream outweighs what it adds to the decoder.

• The launcher has two stages. The second is tools/s2dec.S: the cm.h decoder and four raw system calls (memfd_create, write, execveat with AT_EMPTY_PATH, exit), written by hand, with each step matching one line of the C model. Its entry point s2_main comes first, and stage2.ld links it to run at S2_ADDR (0x800000). Without a first stage the file would have to carry this x86 raw, and it's the biggest single thing in the file, so it's coded. What counts is then its size after the first stage's coder, and the asm is written for that rather than for raw bytes.

  mcstub.c is the same decoder in C. With -DMC_DECODE_TEST it's the reference model that the pack checks against, and with -DMC_STAGE2 it's a reference or fallback second stage, linked by stage2.ld the same way as the asm. The build doesn't ship it. Once the first stage has coded them, the -Oz C and the asm aren't far apart, because the first stage's coder already compresses the decoder's repetition. So the asm wins by dropping the C's ABI overhead and register spills, not by being much smaller.

  The asm also ignores the ABI where nothing needs it. Only cm_xfield, which UP and X86T call with live registers, saves the callee-saved registers. The driver loops until the model holds all n bytes (cm_pos, which the model counts anyway) instead of counting bits in a register, and CTX and INIT end in a tail jump. cm_in8 shifts the byte it reads straight into the coder's state, which starts from .bss zeros as cm.h's initialisers say. The forms are chosen by their coded size. The first stage's coder prefers regular code, so rep stosl and memory-operand forms of the same steps would code bigger.

  The file carries the second stage coded by a much smaller coder (tools/s1.h). Each of its models is a hashed pair of counts, of zeros and of ones, over a byte mask of the last four bytes, and the other count halves on every surprise. The prediction is the weighted share of ones, with weight 2^w, doubled while a context has only seen one value. That takes one division and no logistic tables. A 32-bit carry-less binary arithmetic coder with 16-bit probabilities does the coding. s1pack.c picks the models (masks and log2 weights) with a deterministic greedy walk from a fixed start, and PACK=quick keeps the start. Every search comparison charges the compressed second-stage stream plus five bytes for each model: its four-byte mask and one-byte weight. Adding or removing a model must improve that total, so a shorter stream cannot win by adding more metadata than it saves. The reported stream length still excludes those model tables.

  The first stage, s1dec.S, is that decoder written by hand (317 bytes, each step one line of the C reference), plus the ELF header. launcher.ld links a raw image whose first 112 bytes are the ELF header, with the program header folded into its tail. The bytes of e_phnum and e_shentsize double as p_type (PT_LOAD), and those of e_shnum and e_shstrndx as p_flags (RWX). The segment sizes come from linker symbols. All of the entry code sits in three parts of the header that Linux never reads: e_shoff, e_flags and e_ehsize, then p_paddr, then the padding of e_ident, and it runs through them in that order. The entry decodes stage 2 into place and jumps there with the initial stack and the payload. The ABI promises a 16-byte aligned stack at entry, so the stack needs no realigning. Stage 2 has the payload's coded length as a constant of its own, MC_BLOB_LEN in payload_meta.h.

  A stronger first-stage coder doesn't pay for its own decoder. So the file is the 112-byte header, the first stage's 317 bytes of code, five bytes per selected model, the coded second stage and the stream. The current whole launcher and stream sizes are listed under The real numbers.

  The decoder's tables live in .bss, so they cost no file bytes. With this build's configuration the second stage's .bss comes to about 152 MiB (159 MB). The context slots take 128 MiB of it, the match model's hash table 16 MiB, the two APMs 4.1 MiB, and the mixers' weights 3.3 MiB (32,512 sets of 27 weights). The last 0.6 MB holds the decoded payload, the indirect models' tables and the smaller ones. The first stage adds 2 MiB of count pairs, and all of it is released when execveat replaces the process. The configuration has 15 masks, three extra models, seven instruction or text contexts and six mixers. Decoding the payload takes under two seconds on the UHD 620 laptop, and pack.json records the time the pack measured.

• Before shipping, pack.py compiles two decoders for the host: the reference model (mcstub.c with -DMC_DECODE_TEST, built from the same cm.h the packer compressed with) and the shipped decoder itself (the asm, s2dec.S with -DMC_S2_TEST). It times the asm, and byte-compares what each one decodes against the original ELF. So a wrong model, configuration or code range fails the build, not the compo, and the asm and the model can't disagree. The first stage gets the same treatment: s1dec.S, linked into a host test (-DMC_S1_TEST), must reproduce stage 2 byte for byte. pack.py also checks that the launcher is an x86-64 ELF64 with a single RWX PT_LOAD that covers the whole file, with the entry point inside it, and that it fits the 64 KB budget.

  tools/checks/tooling.py packs and launches a real program with its code range, so the x86 path is exercised, and runs the transform self-test. Through tools/checks/s2equiv.py it also checks that the asm decoder reproduces every input and agrees with the cm.h model, over 40 cases that cross four configurations with five inputs. The inputs are a real ELF, text, GLSL-shaped text (with brackets, commas, braces, statements, NULs and an unbalanced tail), random data and a tiny input, each with and without a code range.

  The work happens in a temporary sibling directory, and only a candidate that passes is renamed over the published binary. A failure keeps the previous binary, if there is one, and prints compiler, ELF, decode and size diagnostics. pack.json records the stream and launcher bytes, the configuration, the code range, the search size and the host decode time.

• The build-time tools are python3 and the C compiler that builds the demo, and neither ships.

It records the show as the release video: 1920x1080 at 60 fps with its soundtrack, every frame rendered offline by the demo's capture build. Nothing is shown or played. make capture builds that binary and runs the script.

tools/capture.sh CAPTURE-BIN VIDEO WORKDIR
# make capture: build/<demo>/<demo>-capture, media/<demo>-1080p60.mp4, build/<demo>/capture

There are two steps, so the slow render runs only once. First the capture binary runs with MC_CAP_AUDIO to write the soundtrack. Then it runs again and streams raw frames into x264 at CRF 8, which makes a near-lossless master in WORKDIR, about 2.5 GB for the whole show. Then the master is encoded in two passes, at BITRATE on average with peaks held to 40 Mb/s, using -tune film and aq-mode=3. The soundtrack goes in as AAC at 256 kb/s, and the picture is converted to BT.709 and tagged as such. For the whole show the video comes to about 357 MB.

A finished master is used again if the binary, MC_CAP_SCALE and MC_CAP_DUR are the same, so a failed encode doesn't render everything again. WORKDIR is deleted once the video is written, and it needs about 3 GB free until then. On the UHD 620 the published version's master, 16,722 frames, took 57 minutes to render, before final encoding. Recording the video has the capture binary and the steps by hand.