blog.oat.zone
λ
cd /dealing-with-raw-image-formatting-a-guide-to/

Dealing with raw image data - a guide to losing your mind using Figura

· by jill

Don't give Jill a Lua API and networking access. Only cursed nonsense will come out of that.


Figura is a cool mod. It's a mod that lets you customize your Minecraft skin using Blockbench models, Lua scripts and your imagination. No, really! Anything you can create in Blockbench you can embed into Figura, and the Lua API for Figura is often times bigger than you'd ever want, letting you do tasks from custom particles to applying shaders onto your skin.

The way it works is after you create your player model, you can upload it to a remote server. Anyone viewing you in Minecraft with the same mod (which is client-side) will then see your creation instead of your usual skin. This means that you can join vanilla servers just fine with it installed, and everyone will still be able to see your model. (Well, those who have the mod, of course.)

(I promise I'll get to the fun part soon!)

This, of course, raises a bit of an issue: if you were to change your model because of an action, that won't transmit to anyone else. That's where pings come in - tiny packet-likes you can send to anyone viewing your model optionally with up to 1KB of data.

They work perfectly for very tiny stuff - maybe toggling some part of the model, doing some sort of animation or pose, things like that. However, given I'm Jill "oatmealine" Monoids, I had the temptation to push this beyond just that.

Earlier when I was doing models, I realized if i made a bunch of cubes in Blockbench, laid them out in a grid pattern and then controlled their colors with setColor, I could have a very basic display. This was cool, and it worked, but it wasn't original - it was a very obvious thought for some.

My intention with this was to shove an NES emulator into it - something I had done in the past in Isaac. My lust for shoving NES emulators into anything scriptable was unsatiatable, and I think it still is, to an extent. However, Figura silently errored out when the filesize got too big and I gave up on the idea soon after.


Fast forward to a few months ago, when I see in the changelogs said issue has now been fixed. I had gained a lot more knowledge about Figura and its API by then and thought I was ready to tackle the project. So, I decided to start with the hardest part - syncing the pixel data between clients.

I thought - surely, it can't be that bad, define a palette and send that via pings, then send the palette indexes in a table. Oh, how naive I was.

Remember when I mentioned the 1KB ping limit? This actually applies to ping size per second, rather than individual pings. This wasn't ideal, but let's quickly count up how much data will be sent each second.

The NES has a framerate of around 60FPS - specifically 59.826Hz. The NES's screen is 256x240 (or 256x224 for NTSC), but I figured I could settle for 32x24. This means 768 pixels are sent per frame.

There are always 8 palettes loaded at all times - there are 4 palettes for backgrounds and 4 palettes for sprites. Each palette is made up of 4 colors. This totals to 32 colors possible per frame, which is conviniently representable with a 5bit integer.

Summing this up together, this means we have 5b * 768 pixels * 60FPS gives us 28,800B, or 28.8KB per second, w/ no compression. Yeah, we overshot our minimal goal by a lot, haven't we..

A single uncompressed frame is already 3.8KB, which is far too much to send in a ping, let alone each second. I quickly understood making an NES emulator was going to be far too cumbersome to be usable.

So, what did I do then? I figured I'm going to generalize this problem a lot first, and then figure out what I can put into the display later. So, instead I settled for a screen size of 20x12, an FPS of 1FPS and a 2bit palette for the time being.

First, I needed to figure out how to send the data. Pings can take in up to 1 Lua value, so I figured it'd be best to start with a table containing ints and then figure out something better later. Though, this didn't work; packets were randomly dropped and ended up being empty, data either didn't get sent or ended up wrong, and I decided to scratch that idea. I instead temporarily settled for a concatted string formatted something like '1.3.2.5.1.2.1.5'. Awful, I know, but hey, it worked.

Now, how am I going to actually optimize this? My initial thought was to cram the 2-bit integers into one big, 32-bit Lua integer. So, I got planning: my plan was to create a function that would take in an input:

{00000010, 00000001, 00000000, 00000011, 00000001, 00000001}

And then output that, but compressed into 1 or more integers:

{10100011, 001001}

And, surely enough, with enough bitwise operators and painful debugging, I made a function that worked! The decoding version, one that did the opposite of this, wasn't much harder either. And, testing this in multiplayer - it indeed sends the frame data correctly!

This proved to me that my concept wasn't impossible - a very good proof of concept, showing it's definitely possible to send image data over Figura.

So now, I had to figure out a better way of formatting my data. Storing it as I was at the moment was awful as there were lots of unused bits, wasted space on dots, et cetera. So, I thought of an idea: what if I were to encode data as a string directly, putting the integer as the character code of a character?

After a bit of testing, I found out the highest value string.char will allow is 255 - conviniently the highest value of an 8-bit integer. This made sense, as the Lua standard library didn't really support UTF-8, and either way, encoding my stuff through UTF-8 would only be a waste of bytes.

So, I changed the INT_SIZE value in my code from 32 to 8, wrote something that would convert a table of 8bit integers into a string and the other way round, hooked that all up to my ping system, and that solution worked! Kind of.

See, up until now, I hadn't been testing the new string encoding in an actual multiplayer server - I was just seeing if it worked locally. What I found out after testing my code with other people is it didn't work.

I was hitting weird ratelimits, things weren't showing up, strings were being converted to numberes in pings(?!), it was a nightmare to debug that I stayed up until 3AM for, with no real results.

So, the next day I found out the issue - Figura's backend didn't like some characters, specifically \00 - \04. This, was bad. This meant that I couldn't represent all possible values of an 8bit integer in a single character. So, I went back to the drawing board.

My first idea was to math.max the char code against some value like 4 to prevent it from reaching the lower character codes. After all, it should only result in very minor issues, right? (Hint: no lmao)

So, my second idea was to reduce the INT_SIZE to 7 bits and shift each character code by 1 bit. However, there was one major issue.

See, how my code worked, is if you had a sequence of 4 2-bit ints like so:

01 10 01 11

My code would fit that into an 8-bit integer like so:

11011001

This is good, but a slightly different situation happens with a 7-bit integer, which I was about to swap to:

0100111, 0000001

This, was bad. I would lose 1 bit per byte, which I considered bad enough to completely re-write all of my encoding and decoding code. The new code would encode this into:

0100111, 0000010

And, after doing this, it worked! Of course, the code wasn't without many oversights that I took a day or so to work out, but it successfully worked with any palette size and any screen size.

This worked with 4bit palettes at up to 4FPS! Not bad at all! I was even able to up the screen size to 24x24, rather than a weird 20x12 resoluition. I only had 1 more thing to tackle - compression.

Now, I want to note, I know NOTHING about compression. All I know is that things like .zip, .tar.gz, etc. use compression for their files. So, I decided it's worth looking through.

I was specifically interested in zip's DEFLATE algorithm - it's pretty old, but still decent by today's standards. Reading up the Wikipedia page on it isn't very helpful - it just throws a bunch of algorithm names and words you've never heard of at you and expects you to know what they are.

Sorry, I lost you at "deflate" - are we looking at file compression or something else??

I decided to click on the first link I saw - LZ77. And - I was greeted with...

Lots of long paragraphs. O-okay, let's just...

Bingo. Okay, let's put this in...

Hmm. Okay, that's an issue..

Sure, okay. Let's look at something else. Maybe let's generalize our search to DEFLATE implementations in general?

Perfect! Let's just skim through the source code..

Oh. Oh dear. For context, Figura will only take in 100KB max for a single avatar before discarding it during the upload process.

Okay, erm, uh, let's, maybe.. look back at the LZ77 page..

Oh! Perfect! Let me skim through LZMA's one, I've heard Python has that in its standard library..

???????????????????????????

?????????????????????????????????????????????????????????????????

Okay, maybe, maybe LZSS????

Oh, this.. looks simple enough, actually! Let's just quickly...

Oh! This is perfect, actually. Let's embed that into the code, try running it..

Oh, it's calling.. string.pack..

What's that do? Surely, it must be something really simple, right? That I just don't have access to in Lua 5.2?

Nevermind..


I think you get the point I'm getting at here. Every single attempt at compression that I tried either required something from 5.3 or 5.4, was written in C, or was way too large. Well, that's a shame then.

There was a library that ended up working, but it required me to be able to write \00, which I simply wasn't able to do because of Figura's backend limitations. It's possible to work out a solution similar to the encoding step from earlier to convert the character sequence into a 7-bit, Figura compatible character sequence, but I wasn't willing to work that out at the time.

In the end, I'm happy with what I achieved anyways. I managed to get font rendering to work aswell (by hardcoding a font by hand, mind you), and that's the most I wanted out of this to prove it truly works.

Provided here is the resulting code, as of writing. I say that because I'm not sure where I want to take this next. I might put a game in it, I might program a fake OS in it, the end goal of the project was to sync a screen across multiple clients, and I figured that out quite well. But what I'll do with it later is currently unclear.


published