All-Purpose Mat's Blog

Answer: Yes! Here it is:

The game launches, and you can move around the 64x64x64 world with WASD. Space is used to jump. Look around with the mouse. You can left click to break a block, and right click to place dirt.

You can scan it with the following command on Linux:

zbarcam -1 --raw -Sbinary > /tmp/m4k && chmod +x /tmp/m4k  && /tmp/m4k

• -1: exit after scanning the code
• --raw: don't process it as text
• --Sbinary: use the binary configuration

The project is available on GitHub at TheSunCat/Minecraft4k

How???

Short answer: Pain, suffering, evil dark magic, compression, a couple years, some more pain, and a bit of luck.

Long answer: Well, it's a long story. If you're ready to learn about various creative game programming techniques and cursed incantations (don't worry, I will explain each concept as it becomes relevant), strap on!

NOTE: This is my first ever blog post. I'm trying it out, as I really enjoy writing! I tried my best to keep it accessible and entertaining, but I am very much open to constructive feedback on how it and future posts can be made better. Every time I describe a major change or evolution, there will be a link to the file or commit in question.

The goal

So, how big is a QR code? Truth is, they come in many sizes. The one you're probably most familiar with is “version 1”, with 21x21 pixels. This can store 25 characters of text, but only 17 8-bit bytes. The difference is because text can be more efficiently encoded than bytes can, as there are less possible values for a QR-compatible text character than the 255 values a byte can have.

The biggest existing QR code, which you can see at the top of the document, is “version 40” and fits a whopping 2953 bytes. Let's see how many max-size QR codes it would take to fit the following Villager idle sound from Minecraft:

That's, uh, 8605 bytes. It fills up (nearly) three QR codes. We have to fit playable Minecraft into a third of the Villager “hmm” sound.

Exposition

On December 2009, Markus Persson, the creator of Minecraft, released a very cut-down version of Minecraft for the Java 4k Game Programming Contest, in which contestants develop games in Java which fit under 4 kilobytes (4096 bytes). An archived version of the game is available on Archive.org. The game renders a pixelated image vaguely resembling Minecraft. All this in... 2581 bytes. Woah. That's much less than 4k. AND it already fits in a QR code. Remember, our size limit is 2953 bytes.

So the deed is done, right? Not quite! This version depends on the Java Applets framework, which was phased out by browsers starting in 2013, and is now completely unusable. Also, I think we can do better. The game suffers from bugs, poor performance, and low resolution. Not only that, but running it required a full web browser, Java installation, and the Java Applets plugin enabled. Can a standalone version of Minecraft really fit in 2953 bytes?

The Java era

To improve upon software, we need to change the source code. Unfortunately, the code for Minecraft4k was never made available, and likely never will be. All original posts about it now lead to a 404 error, and the original Minecraft4k page where you could play it now redirects to Microsoft's Minecraft homepage. Thankfully, Java code is not too hard to retrieve from JAR files! Unlike most compiled languages like C and C++, which compile to optimized assembly language, Java programs compile to an intermediary called Java bytecode (which is then interpreted into normal assembly by the Java Virtual Machine when you run the JAR file!). This bytecode still bears a strong resemblance to the original source code, and preserves a lot of information, such as the names of variables and functions. This means that using tools made by very smart people, we can “de-compile” the bytecode stored inside Minecraft4k and get back usable source code!

Let's pop the JAR file into the wonderful jd-gui decompiler, and...

float f13 = 0.0F;
float f14 = 0.0F;
f14 += (this.M[119] - this.M[115]) * 0.02F;
f13 += (this.M[100] - this.M[97]) * 0.02F;
f4 *= 0.5F;
f5 *= 0.99F;
f6 *= 0.5F;
f4 += f9 * f14 + f10 * f13;
f6 += f10 * f14 - f9 * f13;
f5 += 0.003F;
int m;
label208: for (m = 0; m < 3; m++) {
    float f16 = f1 + f4 * ((m + 0) % 3 / 2);
    float f17 = f2 + f5 * ((m + 1) % 3 / 2);
    float f19 = f3 + f6 * ((m + 2) % 3 / 2);
    for (int i12 = 0; i12 < 12; i12++) {
        int i13 = (int)(f16 + (i12 >> 0 & 0x1) * 0.6F - 0.3F) - 64;
        int i14 = (int)(f17 + ((i12 >> 2) - 1) * 0.8F + 0.65F) - 64;
        int i15 = (int)(f19 + (i12 >> 1 & 0x1) * 0.6F - 0.3F) - 64;
        if (i13 < 0 || i14 < 0 || i15 < 0 || i13 >= 64 || i14 >= 64 || i15 >= 64 || arrayOfInt2[i13 + i14 * 64 + i15 * 4096] > 0) {
            if (m != 1)
                break label208; 
            if (this.M[32] > 0 && f5 > 0.0F) {
                this.M[32] = 0;
                f5 = -0.1F;
                break label208;
            } 
            f5 = 0.0F;
            break label208;
        } 
    } 
    f1 = f16;
    f2 = f17;
    f3 = f19;
}

Uh-oh. It's true that Java usually keeps variable and function names when compiling. But Persson likely turned this feature off, as it would take up place in the JAR. We have the code, but we don't know what any of it does. It looks like we'll have to figure out what every single statement does by staring at it and poking it repeatedly: let's do some reverse engineering!

Reverse engineering

The first step is to get it running. The code still uses the Java Applet framework, so I ported everything to use the newer (but still ancient) Java Swing framework. This allows the game to open a window and display (render) pixels inside it. Great! Let's start reversing the code (on May 30, 2020). I will only go over the major parts, as it took a long while.

The most obvious things are as follows: – the 214*128 BufferedImage is clearly the screen that's drawn on the window. There's a big loop that updates every byte inside it, every frame. The dimensions also match the resolution of the pixelated game view. – the 64*64*64 array of integers is the world. It gets generated at game start, and a single value is modified when you place/destroy a block. – the game uses fixed-update physics. This means that, instead of multiplying the player's movement by the length of each frame, it assumes a constant length for each physics step, and does enough steps to catch up with the time elapsed that frame. The benefit of this is that physics calculations are much simpler, since they don't have to adapt to different step sizes.

I documented the player's position, velocity, look direction, keyboard and mouse input. My pal @JuPaHe64 (Twitter) documented how the game checks whether your movement is valid and corrects it to not let you clip inside blocks. Thanks to this, we fixed a bug which gets the player stuck in the original game if they jump into a wall.

Over the next week, JuPaHe64 and I documented the rest of the game. There's two very unusual systems operating together to keep the size of the game down.

The texture atlas

A single 16x16px texture of the side of a block in the original game takes up ~350 bytes. Minecraft4k has 6 distinct blocks, with three unique sides. That's 6 * 3 * 350 = 6300 bytes. Even compressed by the JAR format (it's just a renamed ZIP file), this would take up a huge amount of our allotted space. So how does Persson do it?

In stead of storing a bitmap of the textures, Minecraft4k opts to generate them at runtime from algorithms. Woah.

I'd never seen this before, but it's a great way to save space. Here's the texture atlas generated with the default Java Random seed:

One unexpected boon of this is that it becomes really easy to up the resolution of the textures. As they're algorithmically generated, the same patterns will hold in higher detail, which led to this cursed image:

JuPaHe64 created a really nice texture pack for it, showing that this is actually a viable method to generate some kinds of textures for games:

I am especially fond of the tree bark and stone textures.

Ray”tracing”

No, really. Well, sort of. Minecraft is a very complex game to render, despite its relatively simple graphics. The real game has to do tons of calculations to avoid rendering block faces that are hidden, turn it all into triangles, and do math to distort them from 3D space into the shapes we see on our 2D screen. This is an oversimplification of the rendering technique called rasterizing. This complexity would be too much for our size limitations, so instead Minecraft4k employs a specific variation of raytracing: voxel raymarching.

NOTE: Voxel is just a word for a 3D pixel, which the Minecraft world is made out of.

This is what happens for each pixel that needs to be drawn:

1. Calculate the direction of the ray, based on where the player is looking and the pixel's coordinates
2. Store the initial position of the ray
3. Loop until we hit a block:
   1. Step (“march”) forward by one block
   2. Check if the ray has hit a solid block
4. Color the pixel with that block's texture

As you can probably guess, this is a pretty simple algorithm to implement, and therefore saves a lot of precious bytes. Additionally, we can use the result of raymarching the pixel at the center of the screen to tell what block the player is looking at. This saves writing a separate function to get the block, and saves a considerable amount of space.

Raytracing is known nowadays for enabling more complex effects, such as lighting and reflections. With minimal modifications to the code, JuPaHe64 was able to add pixel-perfect shadows, and I added ambient light illumination. Paired with a simple world generator, it can make for some interesting shots, despite the poor performance:

However, a problem arises: even without the fancy world generation and raytraced effects, the Java game now takes up 17757 bytes. That's over 6 QR codes. The code required to make this work on contemporary systems with Java is simply too big. It's time for a change of approach.

June 2020: Porting to C++

Let's kill two birds with one stone, and rewrite the game to: 1. Use C++, which is much more familiar to me, so I can make faster progress 2. Use the GPU to run the game in real time, as raytracing on the CPU can be very slow

After a few grueling days, the new port was finally functional, and ran beautifully thanks to GPU acceleration. It used an OpenGL compute shader, which is a type of program that can run on the GPU, once per pixel, all at once. This means that, unlike on the CPU, where each pixel has to finish rendering before the next one can be rendered, on the GPU all of it happens at once.

One of my favorite changes happened when my friend @HANSHOTFIRST joined in, and we wrote the commit title “bad the shader”. Here, “bad” is used as a verb, since we pretty much rewrote the entire thing and it, uh, didn't work. The idea was to reduce the space it took up, and improve performance, by processing all three XYZ axes together. The original game does ray steps per-axis, meaning that first it does the X axis, then the Y, and finally the Z step. This seemed unnecessary to us at the time, but we clearly missed something, as you can see here:

After a small hiatus, and porting the game to Linux on March 2021, I played a bit more with the graphical effects possible with raytracing:

I then introduced the first big size improvement: executable packing. gzexe is a tool which uses gzip compression (the same that was used to deliver this page to you!) to reduce the size of an executable. I also implemented usage of a Shader Minifier, whose job it is to automatically reduce the size of the shader code by removing comments, shortening variable names, and getting rid of unneeded newlines and spaces. The reason why this is so important to do with the shader is that, unlike C++ code which is compiled into the binary, OpenGL shaders must be stored as source code, and compiled by the GPU drivers at runtime. Therefore, any single character we can save in the shader code should translate directly to a byte saved toward our goal. So, how small did this get it? Well, an impressively small, QR-code fitting... 11314 bytes. Well, peck. That's four QR codes. We need to divide the size by four. How is that even possible?

C that? It's my sanity evaporating!

Yeah. I, uh, rewrote it in C. After a long break. In June of 2022, the game is born anew, this time more broken than ever. Once I got all the basic features in by August, I was left with a very functional game, which does everything I think defines Minecraft, in 4598 bytes. Woah. That's 1645 bytes over our limit, for a total size of just over 1.5 QR codes. Suddenly this looks feasible. By this time, the build process has picked up some dirty tricks. We're far from done, but there are already a few things that make me mildly uncomfortable. Let's go through the most egregious ones:

-nostartfiles

The C compiler we'll be using is called GCC. There's a few obvious flags we can pass to it to reduce the size of the output executable (the binary). We can remove the debug information with -s, and optimize the code for size rather than performance with -Os. However, there's one different argument. We all know the ubiquitous int main function, yes? The entry point to every C and C++ program? The first code that runs? I'm here to reveal to the world that we've been lied to: the real entry point is void _start, but Big Compiler doesn't want you to know. This is part of their great ploy to sell more argc and argv. In all seriousness, C programs actually start at, well, _start. This contains code to set up the stack, global variables, the values of argc and argv, and various parts of the C runtime. Because we don't need most of this, we can elect to just skip main and use _start in stead:

void _start() {
    // set up the stack
    asm volatile("sub $8, %rsp\n");

    // Minecraft goes here

    // exit
    asm volatile(".intel_syntax noprefix");
    asm volatile("push 231"); //exit_group
    asm volatile("pop rax");
    asm volatile("xor edi, edi");
    asm volatile("syscall");
    asm volatile(".att_syntax prefix");
    __builtin_unreachable();

vondehi

Like gzexe, vondehi is a tool that allows shrinking a binary by decompressing it and then running it. It's a bit of very well-optimized assembly that can be prepended to any xzcat-compatible compressed executable, and will make it runnable on Linux. At this point, all semblance of cross-platform support is completely gone.

strip

Another GNU tool, strip allows you to remove specific sections from a Linux executable (in the Executable Linker Format—ELF). It turns out that, even with -s passed to GCC, a lot of nonessential information is still kept in the form of ELF sections. We can use strip -R to get rid of them. I simply tried each one by one until the game would no longer run.

With all this, we're at 4598 bytes. Which is pretty great, but we have a whole journey ahead to get it below 2953. There's a few obvious shader code optimizations that can be made, such as shortening the names of uniforms (variables in the shader which can't be changed by the Shader Minifier), and putting everything in the shader's main function rather than using function calls. This makes up for a total of 42 bytes. Yikes. Where are we going to get the 1k+ savings we need? That's a great question, and it's going to take a year of hiatus to answer. I left Minecraft4k at 3786 bytes on September 2022 and focused on my first year at university.

The final run (sanity--)

It's September 2, 2023. University starts in less than two weeks. I have recently rediscovered MattKC's excellent snake game in a QR code. I'm reminded of Minecraft4k, and how close I was to the finish line. It's time for one last sprint.

Embracing the dark side

One big chunk of bytes lies in my calls to C standard library functions. sin, cos, fmodf, and friends. I had tried to get around this by implementing some of them myself, where it was smaller than just calling the libc function.

// TODO tune this, or use inline x86 ASM
#define TRIG_PRECISION 20
static float my_sin(float x)
{
    float sine;

    float t = x;
    float sine = x;
    for (int a=1; a < TRIG_PRECISION; ++a)
    {
        float mult = -x*x/((2*a+1)*(2*a));
        t *= mult;
        sine += t;
    }
    return sine;
}

I'll let you guess how the TODO comment was applied.

float my_sin(float x) {
    float sine;
    asm (
        "fsin;"
        "fstps %0;"
        : "=m" (sine)
        : "t" (x)
    );
    return sine;
}

Directly using the x86 instruction fsin, I was able to save 80 whole bytes from the binary.

API Abuse

OpenGL defines a standard language to talk to the GPU in, so you can get it to do your bidding. This is great, because it will work on any machine, no matter the platform or hardware... supposedly. I've already encountered weird crashes running Minecraft4k's C++ edition on Intel GPUs, because their OpenGL implementation didn't like my way of storing the world data. Every OpenGL driver has its quirks and bugs, which make programming in OpenGL so much more fun. It adds the surprise factor that is very welcome in an otherwise consistent field. Your raytracer might work on one computer, but you'll never know whether it works on all computers, because of the fun factor that is OpenGL driver bugs.

Conversely, we can take advantage of some of these bugs to get away with removing a lot of otherwise strictly necessary code. That'll be 26 bytes, coming right up!

dlsym

Rather than asking Linux to make the OpenGL functions available to us, we can manually load and fetch them using the pair of functions dlopen and dlsym. This requires storing the plain text name of every function we need in the binary, which does take up a lot of bytes, but it ends up being just slightly shorter by 21 bytes. Whew.

This is not okay

Remember that we're compressing the binary and attaching a small decompressor to it, so any improvement to the “compressibility” of the binary directly translates to saved bytes for us. So, I opened the binary in a hex editor, and started zeroing out parts of it. Surprisingly, I found that a lot of seemingly important parts, defined in the ELF specification, are simply not necessary. The game still runs after being so heavily mutilated, although I cannot say the same about Linux ELF utilities. Check out this very disappointed readelf output, where almost everything is a zero:

apm@apg ~/D/m4k ((37570fc8)) > readelf -a Minecraft4k_prepacked.elf
ELF Header:
  Magic:   7f 45 4c 46 00 00 00 00 00 00 00 00 00 00 00 00 
  Class:                             none
  Data:                              none
  Version:                           0
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x0
  Entry point address:               0x102ca
  Start of program headers:          0 (bytes into file)
  Start of section headers:          64 (bytes into file)
  Flags:                             0x0
  Size of this header:               0 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           0 (bytes)
  Number of section headers:         0
  Section header string table index: 0
readelf: Warning: possibly corrupt ELF file header - it has a non-zero section header offset, but no section headers

There are no section groups in this file.

There are no program headers in this file.

There is no dynamic section in this file.

I also truncate the last 50 bytes of the uncompressed file, and the last 8 bytes of the compressed archive. This gives us a fun new error when running the program: /usr/bin/xzcat: (stdin): Unexpected end of input, though the game still plays fine! That's 28 more bytes for me!

Transcending sanity

After rewriting the math in the shader code more than once, drawing many pages of diagrams to figure out how the equations can be simplified, and making a few compromises (goodbye, crosshair and window resizing), Minecraft4k took up a measly 3006 bytes. Where are the remaining 53 expendable bytes?

Excluding the dlsym strings, the biggest data Minecraft4k stores is a couple floating point constants. A float takes up four uncompressed bytes, but Inigo Quilez points out that we often don't need the last two bytes, and can therefore make floats compressible down to just 2 bytes. That's a 2x reduction!

Thanks to @b0rk@jvns.ca sharing the very useful float.exposed website, which has a great interface to poke at the floating point binary format, I was able to check that clearing the last two bytes of the constants did not affect their values too much. Sure, I lost some minor precision, but will the player notice if gravity is 0.00299072265625 instead of 0.003? I don't think we can fit any analytics library to tell us, so it must be good enough. Combining this trick with some tuned compression flags, we have Minecraft4k in 2981 bytes. Just 28 more...

At this point, I was out of ideas. I asked everyone I knew for advice, and we tried a few great ideas. Porting large functions to assembly and hand-optimizing. Getting rid of the stdlib by implementing dlopen and dlsym myself. Linking against the minimal musl libc implementation instead of the GNU C library. None of these ended up working out. So, I asked a very important question:

Notice anything that looks wrong? Hopefully not.

I removed the shadow from under the grass tufts. I'm sorry. It was the only way. Thankfully nobody I asked noticed it, so it's fiiiiiine.

And with that, we're done! Minecraft4k now fits snugly into 2952 bytes, a single byte under the maximum.

---

Thanks for reading! Feel free to contact me if you have any suggestions or comments. Find me on Mastodon and Matrix.

You can follow the blog through: – ActivityPub by inputting @mat@blog.allpurposem.at – RSS/Atom: Copy this link into your reader: https://blog.allpurposem.at

My website: https://allpurposem.at