Yes! At least in theory. And I'm not talking about just putting the URL to some online game in; you can obviously do that. I mean 100% of the game's code stored entirely on one of these. As surprising as it is to say, there theoretically is absolutely no reason you couldn't. A QR code is technically just a storage medium like any other. It's just as legitimate as a floppy disk, CD, or even hard drive. It doesn't store much data, but it is data nonetheless. Keep in mind the bar for data storage is actually pretty low. You could also manually write out binary zeros and ones or hex bytes by hand. It's not very efficient, but technically you've stored computer data. And while a QR code is most commonly used to store ASCII text, it can actually be made to store binary data as well. Which pretty much means anything you can store on a computer, you can store on a QR code - provided that it fits inside the size limitations. How limited are we? Well QR codes come in various standardized sizes, but the largest is version 40 which gives us an ABSOLUTELY LEVIATHAN 2,953... ...bytes. Yeah, slightly less than 3 KB. It's not much. If you're curious just how not much, this sound from Windows 10... [short click] A sound that lasts for 1/15th of a second, this sound... [short click] ...is 11 KB. Yeah. Or remember floppy disks? The ones I remember are these: the 3.5" high-density floppies. Remember needing like twenty of them to install Windows 95? Well, those things are 1.44 MB or 1,474,560 bytes. Which means just one of those floppy disks can store not one, not two, but almost 500 version 40 QR codes worth of data. So... can we really fit a whole game into just one? Well, while pictures, music, video, and... operating systems do take up a lot of storage space, simple code can actually be surprisingly economical. And while 3 KB is pretty small even then, people have made games with far less. Going back to floppy disks, did you know that people have managed to fit games into a floppy disk's boot sector? And if you don't know how small that is, it's only 512 bytes. Roughly a sixth of what we're dealing with with QR codes. If you can fit a game into 512 bytes, you can fit a game into 3,000. Or look at the Atari 2600. A huge amount of those cartridges could only store 4 KB, so games had to fit into that or less. So in theory, there's absolutely no reason we couldn't store a perfectly playable - if somewhat basic - game onto a QR code. So let's do it! Our first decision is what game to write, and since this is just for science, we may as well implement something that already exists. My go-to simple game is Tetris - I love Tetris. But I've already talked about how litigious the Tetris company can be. And since I'd like to make this QR code available to the public, I ain't goin' near that. I'm gonna go for the game that anyone who had one of these will undoubtedly remember fondly. That's right, the one and only... Snake. Extremely simple but still just fun enough to fend off boredom in the pre-smartphone era. Our next decision is platform, and while it seems obvious to write a smartphone app, since that's what QR codes are usually used for nowadays, I have some doubts that I'll be able to make something within the size limitations on mobile. Additionally, the more locked down nature of smartphones I think would make it a lot harder to get an executable to run from a QR code. Which is probably a good thing now that I think about it. So I'm just gonna make this a Windows app instead, with the idea being that you could read the QR code from the computer's webcam. Fitting an entire Windows executable into those 2,900-whatever bytes. Before we get to that though, I will mention a really easy way you could pull this off. You could just write it in HTML and JavaScript. In fact, just for demonstration, I did! This is Snake written in JavaScript, with some HTML and CSS to pull it all together of course. Once it's been minified, which basically means removing everything not strictly required, it fits snugly into our QR code size limit. You'll notice I was even able to fit some comfort features in, like writing extra code to draw the snake as long and thin rather than a big blob of white squares or dots, or queuing up button presses so that if you press buttons in quick succession, they'll still get recognized, and giving you one extra grace turn to move if you're just about to game over. Just like the old phones used to do. So technically we're already sort of done. But it kind of feels like cheating, right? While it is actual code and not just a website URL or something, you still need a modern browser installed which... Wait that's not a modern browser, get that out of here! So yeah, modern browsers, which - let's be honest - are kind of doing a lot of the work for us. Somehow it just didn't feel right. So we're gonna make this a native executable. At first glance, this would appear to be impossible. A super simple "Hello World" program written in C already consumes 100 KB. But most of this is actually not our code at all, it's all the runtime libraries that the compiler is linking by default. We can disable this with the /NODEFAULTLIB option, which does mean that we have to specify the libraries we do need manually, but doing this cuts the file size all the way down to 3 KB. A great start. Now we could probably get it down further with more compiler options, but what I'm actually gonna try is forgoing the C compiler entirely, and writing this thing... ...in x86 assembly. [dramatic music] Yep, as close to the raw machine code as is generally possible. I touched on this in videos like my Super Mario 64 compiler optimizations video. C code, while it may look technical to the uninitiated, is very much designed to be human friendly. For your computer to run it, it must be translated into machine code by a compiler, and while compilers are generally very good at what they do, they're still not perfect, and most importantly, they're not human. They can't really think about the best ways to translate and optimize your app. They can only really do what their developers have told them to do. As such, generally a human will always be able to write lighter and faster machine code than a compiler. Which is why most video games, up until the mid-90s or so, were almost always written in assembly. The slight inefficiencies introduced by compilers was just too detrimental to performance on the hardware of that era. Now I'm planning to write an extremely simple game and run it on modern hardware, so clearly performance isn't really an issue. But writing in assembly also gives us a lot of control over the size of the binary since we're kind of writing all the bytes ourselves. So even though I am a lot more familiar with C, this really seems like the way to go. And with absolutely no outside help at all, I soon had an assembly program that uses the Win32 API to make a window. And all within 2.5 KB. Yeah we're actually already pretty dangerously close to our limit and we haven't even written any game code yet. I trimmed a few unnecessary lines out and found the file size had jumped all the way down to 2 KB. That's way more code than I actually removed. When I put the lines back, it jumped back up to 2.5. Weird. So it turns out the Win32 PE format, which is the format of pretty much all Windows executables these days, is by default aligned to 512 bytes. And it's also listed as the minimum alignment possible. This made me a little nervous since it means we don't just have to get our code below 2.88 KB, we actually have to get it below 2.5 since anything over will round up to 3. I went ahead anyway until I had a white dot that could be moved around the screen, but I was already at 3 KB. Already over our limit with still barely any game. So... is that it then? Well not quite, 512 maybe the default and even the documented minimum, but Windows will actually accept almost any. We just need to override the default in our linker. Unlucky for me, the linker I've been using doesn't seem to have byte alignment options. I was using this one since it made it super easy to link with existing Win32 DLLs, but seeing as size is a priority, it looks like we'll have to swap out with another, which meant having to make some changes to my code. Luckily they weren't too hard and soon we were linking with MSVC. I couldn't remove the byte alignment, I could only reduce it to 16 bytes since that was the alignment of the Win32 libraries I was using. But that still got us down to 2.66 KB which is definitely an improvement. Unfortunately, it still didn't take long to reach the limits once again. 2.9 is already over and we still only barely have a game here. [exhales] You know, there comes a time when one must acknowledge their limitations. Yes, technically I can write x86 assembly, but do I really know what I'm doing? [whispers] No... Do I know all of the tricks or best practices to make the smallest binaries possible? Not really. I probably know a lot less than the developers of a C compiler do. And I'm sure I could learn them, but then we'd be here for another few months I'm sure. I decided I'd bitten off more than I could chew here, and I was curious to see if a C compiler set up the right way, would be able to write more efficient assembly code than me. So I rewrote everything in C, which was actually easier than it sounds, and yep, that pretty much says it all. So while theoretically a human being can always write better assembly code than a compiler, that doesn't necessarily mean that they will. So I decided to carry on in C. I'm much more comfortable with it and I just have more faith that I could write cleaner C code than I could assembly code. The whole time I was keeping a close eye on the executable size, which in itself was pretty nervewracking since it was now all at the mercy of the compiler. A single new line of C code could add anywhere from a few bytes to a few hundred, and I was constantly trying to find ways to do more with less code. But finally, eventually... ...I failed. I got Snake working just how I wanted it to but my executable was 3.1 KB - way more than 2.88. I did write in my comfort features - the drawing code, the button queuing, the brief bite grace period - and I did play around with compromising these things to try to get it below 3.1. But doing that always made the game feel a lot less playable. I know that is the kind of sacrifice you have to make with extreme size limitations like these, but I felt like there had to be more I could do elsewhere before I started cutting code out. Even though this whole thing is just a QR code experiment, I really hoped the game you would get would be at least kinda decent. So I started looking at other avenues of shrinking down the binary. We only need about 200 bytes or so. I looked into some pretty complicated unofficial modifications you could make to the PE header, but the all kinda went over my head. And they could also potentially break compatibility with some versions of Windows. It was at this point I started thinking about compression. It did feel a little like cheating, but seeing as I didn't want to cut functionality, it looked like it was going to be the only choice. Now I didn't want to put it in a zip, because I wanted the experience of just getting an executable and running it. No unzipping or anything else required. But luckily there are other ways to compress, particularly when it comes to executables. "Executable packing" is a means of compressing an executable and then attaching it to a small decompressor program that unpacks and runs the original program on startup. To the user, this is completely transparent and just looks like you're running an ordinary app. Compression is heavily used in the demoscene to make really tiny demos. 64 KB, 4 KB, or even 1 KB demos which I'm showing here. I look at executable packing as kind of like the Auto-Tune of the demoscene. Yes it's technically kind of cheating, but it's also really clever technology, and everyone's using it so you're kind of crippling yourself if you don't use it. First, I tried UPX since that was the only one I was already familiar with. But it didn't like my custom alignment and disabling it blew our Snake program up to 4.5 KB, which UPX could only shrink to 4. Yeah ironically this means compression has made our file larger. But soon, I discovered the program I should have been using. The same one that the demoscene uses: Crinkler. This takes the place of the linker in our compile chain so once again we're swapping linkers. This was pretty much a drop-in replacement though so I had no issues this time. With Crinkler in the toolchain, our Snake program went from 3.1 KB to just under 1.4! All that Snake in less than half the size! The QR code dream lives on! I have a feeling if we took it back to assembly, someone who knew what they were doing would be able to shrink it down with no compromise and no compression. Uhh... But instead you're watching me. But I will say I think the smaller it is the better. It means the QR code can be smaller and probably easier for the software to read. Speaking of which, how do we create a QR code you may ask? Well with some of my favorite things in the world: Unix command line utilities. First, I'll use a tool called qrencode to convert our binary data into QR. We'll have to tell it our data is binary since it will otherwise assume it is text. And it's done - doesn't even take a second. There it is. An entire Snake game inside a QR code. This is what we've been waiting for this whole time and we're finally here. And now for the ultimate test, can we get our executable back? For this, I'll be using another tool called ZBar. It reads all sorts of barcodes, including QR codes, and comes in two forms: zbarimg for images and zbarcam for webcams. I'll try zbarimg first with our original QR code picture. Once again, we'll have to tell it that our code contains binary data rather than text. Okay, looks good... And yep, it decoded perfectly! This executable that we're playing right now was just decoded from a QR code. And now it's time for the ultimate, ultimate test. The whole point of a QR code is that it can be easily scanned in from the real world with just a camera. So here I go printing it out. Now let's fire up zbarcam... Eww gross, who's that? It took a moment to recognize, but it eventually made an executable. And... Oh... Huh... It doesn't work. Maybe it just didn't read properly? It did seem to have some trouble with the paper not being flat, so I tried to use cardboard to keep it straight. No it's... still broken. What happened? It read perfectly fine from the image but not from the webcam? Something's definitely wrong. When I run it from the command line, it just says segmentation fault, so it must be getting corrupted somewhere. We were so damn close! I decided to create a new QR code with the error correction turned up. Before it was set to low, I'm setting it to Q which is the highest that can still fit. Error correction inherently requires more data so there is a limit to how much we can have. I didn't expect this to do much since QR code error correction is intended more for if the code gets scratched or damaged somehow. But I had to try it. Ehh? Nope, still not working. This is so weird. How could it decode perfectly from the original image but not now? I decided to bring out the hex editor and compare the executables side by side. From there it was immediately clear what was wrong. You see this 0A byte here in the original? In the executable retrieved from the QR code, that byte has magically become two: 0D and 0A. Now those of you who know ASCII already know what's happened here. But in case you don't, you know how we often tend to break up language into paragraphs or separate lines? Well, computers aren't made of lines, they don't really have a way of doing this internally. So usually text is stored like this. One long contiguous stream with a special character where the line breaks go so that when it draws that text on the screen for us, it knows how to split the text into the lines we made. This by the way doesn't include automatic word wrapping since the computer can calculate that on the fly. This only applies to line and paragraph breaks specifically. This special character is called a "Newline" or "Line Ending" and it's not really a dot like this, it's a control byte you never see. But what byte that is specifically is hard to pinpoint because not everyone could agree on that. Today there are only really two line endings you'll ever see. Unix-based systems, so Mac, Linux, iOS, and Android, all use a single character called a line feed, which is, in hex, byte 0A. Programmers will know this better as backslash-N. Windows, however, has historically used a two-byte sequence. They also use a line feed, but it's preceded by a carriage return. 0D in hex, or backslash-R in code. So basically Unix line endings look like this and Windows line endings look like this. While most software these days can understand both line endings, a handful still can't. Up until 2018, Windows Notepad only acknowledged Windows line endings, which is why you'd sometimes open text documents with it that would look like this. As such, it's not uncommon for some programs to automatically convert line endings to whatever system you're using. Are you starting to see what's happened? Ordinarily you wouldn't notice this since software that handles both will recognize either type, and software that doesn't will magically work now that the line endings are "correct". But our Snake game isn't text. We know this, but something somewhere doesn't and is inserting carriage returns into what's actually precise machine code. It's no wonder it just crashes on startup. We already know zbarimg can decode our executable fine, so it must be something with zbarcam. Some sort of bug maybe? Well the joys of open source software allow us to dive into the code and see what's wrong for ourselves, and I pretty quickly found that the "stdout" wasn't being set to binary mode. Which basically means zbarcam gave no indication that its output wasn't text, so Windows assumed that it was. Let's fix that up and try it again. And I've gone back to my original QR code for this. Alright, we've got our executable. And... Yes! There it is! A game that streamed in from a piece of paper through the webcam. I can even write a little script to open Snake automatically after the read. Let me try it out on my laptop which has never seen this Snake executable before. Haha it's like a magic trick! So if you ask me this is unbelievably cool. Sure, it doesn't serve much practical purpose, but just the fact that QR codes which are usually relegated to some [censored] McDonalds website or something, could sort of function like a small game cartridge. I think that's really cool! The security implications do worry me though. Obviously QR codes could always link to malicious websites, but if you can store malware directly into the code, which clearly you can, that has the potential to be even more dangerous. I can already imagine a code exploiting an Android camera bug or whatever to trigger some arbitrary code execution and steal your passwords and banking information. Uhhhh hopefully not? Anyway I hope you enjoyed this video. If you'd like to play around with this QR code, check out the link in the description. I have the code, the reader program with the fix I wrote in, and a step-by-step tutorial if you'd wanna play Snake from a QR code. As always thank you so much for watching and I'll see you all next time. Ciao!
Hey! Let's fit a game into a QR!
discovers a bug in zbarcam
When he wrote that script to auto-run his game... Whoa, that's a cool new attack vector I have never used before :O
This was fun to watch!
😆 I thought I was going to see a 2D platformer having a QR code as the level!
Here's a similar project that doesn't store x86 code, but runs a custom engine for creating games: https://github.com/kesiev/rewtro
That was fun. Reminds me of why I love being a programmer. Any idea we have, we could just code it and see what happens.