Packing Binary Is Fun

Packing Binary Is Fun, Actually

September 24, 2026 • 27 min read

table of contents

Why would anyone do this?

What is binary packing?

Building the schema syntax

Time to actually implement this

Encoding and Decoding our Data

Building Compiler

The problem

Building the Lexer

What is AST?

Building the AST

Building the parser

Building the Semantic Analyzer

Dynamic Packer

Codegen

Visitor Pattern

Building CLI

Conclusion

Why would anyone do this?

I saw someone on twitter arguing that saving data in JSON was apparently not what Real™ developers do.

Obviously, I had to become a Real™ Developer too.

“How hard could it be to make my own binary format?”

I ended up building an entire binary schema language that can shrink JSON payloads by 80%.

"hello world"

then it would be translated in ascii to

104 101 108 108 111 32 119 111 114 108 100 h e l l o [SPACE] w o r l d

So h becomes 104 in ASCII.

Since these ASCII values fit within 8 bits, each character takes up 1 byte.

h e l 01101000 01100101 01101100

l o [SPACE] 01101100 01101111 00100000

w o r 01110111 01101111 01110010

l d 01101100 01100100

so we can just write it using a lil bitta c:

FILE *f = fopen("file.bin", "wb");

unsigned char data[] = "hello world"; fwrite(data, 1, sizeof(data) - 1, f);

fclose(f);

Simple enough. Now let’s try writing 104.

Obviously, we could just write 104 as ASCII characters:

'1' '0' '4' → 49 48 52

But that’s 3 bytes for a number that only needs 1 byte.

So if we want to save those 2 bytes, we need some way of telling the decoder, “hey, this is an integer, not a string.”

You could add a header, you would only be adding an additional byte (well depends on how many types you got.. hopefully you don’t have more than 128 types…if you do you got bigger issues.

great! lets just use the first byte to represent our type and second to represent our data.

[TYPE][DATA]

say 0 is int and 1 is string so 104 would be

we need a way to represent different lengths of data. welp lets just get another byte. that should represent the length of our string. so now our binary becomes

[TYPE][LENGTH][DATA]

great! now we can represent our string like this:

[TYPE] [LENGTH] [DATA] (STRING) (11) 00000001 00001011 00...

h e l 01101000 01100101 01101100

l o [SPACE] 01101100 01101111 00100000

w o r 01110111 01101111 01110010

l d 01101100 01100100

GREAT! now we could pack both strings and ints together! say we wanted to represent "userid": 123

now you could just package it all together

[TYPE:STRING][LENGTH:6][WORD:userid][TYPE:INT][LENGTH:-][DATA:123]

Great! we can represent 123 as a 1 byte number with 2 bytes of header. but notice, we are not really using LENGTH field for ints? why need it then? waste of bytes eh?

WELL… if we get rid of it, how does our binary reader know where the header ends?

It needs some way to say “okay, the header is done, start reading the actual data now.”

huh. what can we use to represent that a byte is ending.

Ehh. That’s redundant. We’d be removing the length field just to add another length field.

But hey, we could use a bit in the header itself.

I am not the last byte in the header. There’s more.

Well, then we’d only be able to represent even numbers. Which is… not ideal.

so now our tag looks something like this:

[CONTINUATION BIT][7 BITS OF DATA]

If the continuation bit is 1, there’s another header byte. If it’s 0, the header is done.

[TYPE=1][LENGTH=11][DATA=104]...

so its of type 1, length 11

but wait…what if the length is greater than 127? with 7 bits you can only represent up to 127!

if the first bit is 1 then the int continues. 128 can be written as:

10000001 00000000 ^ MSB / continuation bit

(in big endian)

This is a kind of varint (variable-length integer).

The encoding we’re using here is little-endian: the least-significant 7 bits come first.

10000000 00000001

Hey this is great, innit? You can represent different types in the same binary and your binary parser will read them all correctly

But notice, We are storing this data per field.

[TYPE][DATA] [TYPE][DATA] [TYPE][DATA]

And most data isn’t just a bunch of random values floating around. It’s usually structured.

struct { int i; char *s; int a[10]; }

this would be say on a 32 bit system.

[32-bit int] [32-bit pointer] [10 × 32-bit ints]

and we didn’t have to add headers everytime. because we know the type of the data from the struct itself.

Hmm. I wonder if we can do this for our binary data…

so for our struct our schema can just be:

i: int s: char * a: list(int)

The schema lets us know the type without storing the type alongside every value.

now our binary format doesn’t need to worry about the type! it only need to worry the size of the data!

So lets think about all the different sizes of data we can have.

we got ints, we got floats, bools, strings.

We can treat ints and bools as varints, while floats are fixed-width: f32 or f64.

Strings are different. We can’t just encode their bytes as a varint, because the bytes themselves are the actual data we need to preserve.

So instead, we need to know how many bytes belong to the string before we start reading it.

but wait! how do we access our fields? like we cant just go “gimme string” we will need to spacify which one. and no problem lets just represent each one with a number. we can index them or have the user assign their own numbers to address them. this is what we need field number for.

And notice something else: we only have four possible types.

00 - varint 01 - f32 10 - f64 11 - delimited

hey isn’t that neat. now what we could do is just encode it…inside our field number!

Move the field number left by 2 bits to make room for our 2-bit type, then OR the type into those empty bits.

say your field number is 10 and it is a delimited type.

00001010 (10)

left shift that by 2

00101000

OR it with our type!

00101011

LOOK AT THAT! our 1 byte number tells us both what type it is and what its field number is!

We’ve already packed the type into the field number.

[FIELD NUMBER][LENGTH][TYPE]

ALL in a singular varint!!!! ◝(ᵔᗜᵔ)◜

its just so much tedious work. To pack a string, I have to tell it ‘this is delimited,’ give it the length, and then give it the bytes. Every. Single. Time.

PEASANTS DO THAT. Plebeians. we don’t do that.

So obviously, the solution is to write an entire schema language. We declare our data in a schema file, and let the program deal with all that tedious formatting and encoding nonsense.

alright soo… we need to decide on a syntax that doesn’t suck your soul (looking at you protobuf)

field numbers.. what are they? index right. how do you index stuff in your grocery list? you write number. item why not use the same!

1. name

we need the schema to represent the types. lets just steal how other languages do it and do it like this:

1. name: type

neat huh. but wait. how do we indicate the end of a message(struct)

well we could do {} but its not very nice is it. why over complicate stuff its a list. lists have an end. lets have an end.

message name:

1. name:type
2. name:type
3. name:type end

and no, indentations shouldn’t matter. its so annoying to work with languages where indentation matters. its just painful. lets just not do that.

so..how will you identify the end of the line without a semicolon? new line char?

I mean we could do that but what if they wanted to type it in a single line, its ugly but say they want to for whatever reason. lets not restrict that. but semicolons are ugly.

we could use the number! if we see a number and a dot we just consider it a new entry!

problem…what if the field is just not found when the compiler is reading it? we could crash…and we would for all the fields but we do want optional fields don’t we. lets just go with the obvious route and do something like this:

number. name: type = defaultValue

and that’s optional. pretty intuitive.

now that we are here anyway lets think about all the different kinds of data people could represent…

well we obviously got our entries of types.

oh we would need lists. we need some sort of way to pick between a few things so we would need an enum. great lets think about those..

oh we could just have them be function like, that’s pretty intuitive.

1. friends: list(People)

oh wait but what is people? oh it should be a message too. something like this:

message People:

1. name: string
2. location: string end

huh.. we need custom types as well… so in the language do we want to have everything be in order? ehh that’s pretty cringe later we could just do a pass and put together all of our table and just have it refer to that struct.

hey thanks to this we can have self reference as well. cuz when we pack it it will just be a pointer to the struct! so we can do something like:

message People:

1. name: string
2. location: string
3. friends: list(People)

now for enums. cuz we have two passes we can just put enums outside of message! it doesn’t matter where it is declared either! we can declare our enum something like this:

enum Name: number. name number. name number. name end

also protobuf does this thing where it forces you to have the enum start from 0 like do we REALLY need that? is the compiler so dumb it cant tell? lets just have the compiler handle that by default

oh wait…. people might need some way to represent an enum but all the types are not the same. yup. that’s a union. lets just add that no problemo

number. name: union(type, type, type...)

oh wait.. our default value. how would that work with unions. if we have a union like this:

number. name: union(i32, i64) = 10

it is ambiguous weather 10 is an i32 or an i64 so when field is not found what should we do?

we could fix this by having the default be next to the type.

number. name: union(i32 = 10, i64)

now if a the field is not found it will be an i32 with value 10

okay well people would wanna map stuff as well…so we add

number. name: map(key_type, value_type)

lets just add syntax for declaring packages and importing stuff:

package "package name"

import "package"

hey would you look at that we have some very neat syntax. lets just put it all together:

package "com.game.core" import "math.jbin"

enum Activity:

1. active
2. inactive end

message Player:

1. name: string
2. health: i32 = 100
3. weapons: list(string)
4. connections: list(Player)
5. activeStatus: Activity
6. inventory: map(string, i32)
7. balance: union(string="empty", i32) end

oh wait…we have a whole language now….

anyway. this is the equivalent of it in .proto

syntax = "proto2";

package com.game.core;

import "math.proto";

enum Activity { ACTIVE = 1; INACTIVE = 2; }

message Player { optional string name = 1; optional int32 health = 2 [default = 100];

repeated string weapons = 3; repeated Player connections = 4;

optional Activity active_status = 5; map<string, int32> inventory = 6;

oneof balance { string empty = 7; int32 amount = 8; } }

look at that. ew.

By “naturally,” I mean I wanted something I could put on a resume and wasn’t in the mood to fight the Rust borrow checker. I have aged enough.

Okay. Enough designing. Time to actually make the thing work.

To encode a varint, it’s basically just this:

void encodeVariant(std::vector<uint8_t> &buffer, uint64_t value) { while (value >= 128) { uint8_t lower = value & 127; // 127 = 01111111 lower |= 128; buffer.push_back(lower); value >>= 7; } uint8_t lower = value & 127; buffer.push_back(lower); }

This builds our varint. If the value is >= 128, we take the lowest 7 bits, set the MSB to 1 to say “there’s more,” and append it to the buffer.

Then we shift the value by 7 bits and repeat.

For the final byte, we leave the MSB at 0.

pretty simple. and we can decode it using this:

uint64_t decodeVariant(const std::vector<uint8_t> &buffer, size_t &offset) { uint64_t result = 0; int shift = 0; while ((buffer[offset] & 128) != 0 && offset < buffer.size()) { u