{"article":{"slug":"packing-binary-is-fun-actually","title":"Packing Binary Is Fun, Actually","subtitle":null,"summary":"Pranav Desai’s hands-on tour of binary packing: why packing bits can be fun, the techniques that matter, and practical patterns for packing denser structures without losing your mind.","content_type":"blog_post","language":"en","canonical_url":"https://hereticpleb.vercel.app/blog/packing-binary-is-fun-actually","author":{"name":"Pranav Desai","url":"https://hereticpleb.vercel.app/","person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"hereticpleb","url":"https://hereticpleb.vercel.app/","listing_slug":null,"listing":null},"topics":[{"name":"Programming","slug":"programming","url":"https://listedarticles.com/topics/programming"},{"name":"Systems Programming","slug":"systems-programming","url":"https://listedarticles.com/topics/systems-programming"},{"name":"Performance","slug":"performance","url":"https://listedarticles.com/topics/performance"},{"name":"Engineering","slug":"engineering","url":"https://listedarticles.com/topics/engineering"},{"name":"Tutorials","slug":"tutorials","url":"https://listedarticles.com/topics/tutorials"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":5056,"reading_minutes":22,"published_at":"2026-09-24T00:00:00.000Z","added_at":"2026-09-28T09:14:29.303Z","updated_at":"2026-09-28T09:14:29.303Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":false},"profile_url":"https://listedarticles.com/articles/packing-binary-is-fun-actually","markdown_url":"https://listedarticles.com/articles/packing-binary-is-fun-actually.md","example":false,"citation":"Pranav Desai, hereticpleb. \"Packing Binary Is Fun, Actually.\" 24 Sept 2026. https://hereticpleb.vercel.app/blog/packing-binary-is-fun-actually (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://hereticpleb.vercel.app/blog/packing-binary-is-fun-actually"},"body_markdown":"## Why would anyone do this?\n\nI saw someone on twitter arguing that saving data in JSON was apparently not what Real™ developers do.\n\nObviously, I had to become a Real™ Developer too.\n\nTurns out, the answer was binary.\n\nNaturally, I had a brilliant idea:\n\n“How hard could it be to make my own binary format?”\n\nSurely it’s just a little `wb` . ( ˶ˆᗜˆ˵ )\n\nIt was, unfortunately, not just a `wb`.\n\nI ended up building an entire binary schema language that can shrink JSON payloads by 80%.\n\n## What is binary packing?\n\nSay we got some data\n\n`\"hello world\"`\nthen it would be translated in ascii to\n\n```\n104 101 108 108 111 32 119 111 114 108 100\n h e l l o [SPACE] w o r l d\n```\nSo h becomes 104 in ASCII.\n\nSince these ASCII values fit within 8 bits, each character takes up 1 byte.\n\n```\nh e l\n01101000 01100101 01101100 \nl o [SPACE]\n01101100 01101111 00100000 \nw o r\n01110111 01101111 01110010 \nl d\n01101100 01100100\n```\nso we can just write it using a lil bitta c:\n\n```\nFILE *f = fopen(\"file.bin\", \"wb\");\nunsigned char data[] = \"hello world\";\nfwrite(data, 1, sizeof(data) - 1, f);\nfclose(f);\n```\nSimple enough. Now let’s try writing 104.\n\nObviously, we could just write 104 as ASCII characters:\n\n`'1' '0' '4' → 49 48 52`\nBut that’s 3 bytes for a number that only needs 1 byte.\n\nSo if we want to save those 2 bytes, we need some way of telling the decoder, “hey, this is an integer, not a string.”\n\nYou 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.\n\ngreat! lets just use the first byte to represent our type and second to represent our data.\n\n`[TYPE][DATA]`\nsay 0 is int and 1 is string so 104 would be\n\n`00000000 01101000`\nand string would be..\n\n`00000001 01101000`\noh wait…..\n\nthat would only give is `h`\n\nwe 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\n\n`[TYPE][LENGTH][DATA]`\ngreat! now we can represent our string like this:\n\n```\n [TYPE] [LENGTH] [DATA]\n(STRING) (11)\n00000001 00001011 00...\nh e l\n01101000 01100101 01101100 \nl o [SPACE]\n01101100 01101111 00100000 \nw o r\n01110111 01101111 01110010 \nl d\n01101100 01100100\n```\nGREAT! now we could pack both strings and ints together!\nsay we wanted to represent `\"userid\": 123`\n\nnow you could just package it all together\n\n`[TYPE:STRING][LENGTH:6][WORD:userid][TYPE:INT][LENGTH:-][DATA:123]`\nGreat! 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?\n\nWELL… if we get rid of it, how does our binary reader know where the header ends?\n\nIt needs some way to say “okay, the header is done, start reading the actual data now.”\n\nhuh. what can we use to represent that a byte is ending.\n\nA length byte for the header, perhaps?\n\nEhh. That’s redundant. We’d be removing the length field just to add another length field.\n\nBut hey, we could use a bit in the header itself.\n\nWe could have one bit say:\n\nI am not the last byte in the header. There’s more.\n\nYou might think: why not use the LSB?\n\nWell, then we’d only be able to represent even numbers. Which is… not ideal.\n\nSo we’ll use the MSB instead.\n\nso now our tag looks something like this:\n\n`[CONTINUATION BIT][7 BITS OF DATA]`\nIf the continuation bit is 1, there’s another header byte. If it’s 0, the header is done.\n\nusing this, we can just have our 123 be\n\n`[TYPE=0][DATA=123]`\nand if its a string.\n\n`[TYPE=1][LENGTH=11][DATA=104]...`\nso its of type 1, length 11\n\nbut wait…what if the length is greater than 127? with 7 bits you can only represent up to 127!\n\nWe use the same thing! but for ints!\n\nif the first bit is 1 then the int continues. 128 can be written as:\n\n```\n10000001 00000000\n^\nMSB / continuation bit\n```\n(in big endian)\n\nwhat the binary reader will do:\n\n- Reads the first byte.\n- The MSB is 1, so there’s another byte.\n- The remaining 7 bits are 1.\n- Reads the second byte.\n- Its MSB is 0, so this is the last byte.\n- Its remaining 7 bits are 0.\n- Combines the two 7-bit values to get 128.\n\nThis is a kind of varint (variable-length integer).\n\nThe encoding we’re using here is little-endian: the least-significant 7 bits come first.\n\n`10000000 00000001`\nHey this is great, innit? You can represent different types in the same binary and your binary parser will read them all correctly\n\nBut notice, We are storing this data per field.\n\n```\n[TYPE][DATA]\n[TYPE][DATA]\n[TYPE][DATA]\n```\nAnd most data isn’t just a bunch of random values floating around. It’s usually structured.\n\nTake a C struct:\n\n```\nstruct {\n int i;\n char *s;\n int a[10];\n}\n```\nthis would be say on a 32 bit system.\n\n`[32-bit int] [32-bit pointer] [10 × 32-bit ints]`\nand we didn’t have to add headers everytime. because we know the type of the data from the struct itself.\n\nHmm. I wonder if we can do this for our binary data…\n\nAnd yes, we can.\n\nThat’s what a schema is!\n\nso for our struct our schema can just be:\n\n```\ni: int\ns: char *\na: list(int)\n```\nThe schema lets us know the type without storing the type alongside every value.\n\nnow our binary format doesn’t need to worry about the type! it only need to worry the size of the data!\n\nThat’s what protobuf does\n\nSo lets think about all the different sizes of data we can have.\n\nwe got ints, we got floats, bools, strings.\n\nWe can treat ints and bools as varints, while floats are fixed-width: f32 or f64.\n\nStrings are different. We can’t just encode their bytes as a varint, because the bytes themselves are the actual data we need to preserve.\n\nSo instead, we need to know how many bytes belong to the string before we start reading it.\n\nso now our encoding types are:\n\n- varint\n- f32\n- f64\n- delimited\n\nbut 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.\n\nAnd notice something else: we only have four possible types.\n\nFour values fit perfectly into 2 bits.\n\n```\n00 - varint \n01 - f32\n10 - f64\n11 - delimited\n```\nhey isn’t that neat. now what we could do is just encode it…*inside our field number!*\n\nwait how?\n\nsome binary trickery..not really.\n\nYou just shove them together.\n\nMove the field number left by 2 bits to make room for our 2-bit type, then OR the type into those empty bits.\n\nsay your field number is 10 and it is a delimited type.\n\n```\n00001010 (10)\nleft shift that by 2\n00101000\nOR it with our type!\n00101011\n```\nLOOK AT THAT! our 1 byte number tells us both what type it is and what its field number is!\n\nBut what if we go FURTHER.\n\nWe’ve already packed the type into the field number.\n\nWhy stop there?\n\nWhat if we could pack the length in too?\n\nWe can.\n\nnow our header can hold\n\n`[FIELD NUMBER][LENGTH][TYPE]`\nALL in a singular varint!!!! ◝(ᵔᗜᵔ)◜\n\nCool. Except for one thing\n\nits 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.\n\nPEASANTS DO THAT. Plebeians. we don’t do that.\n\nSo 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.\n\n## Building the schema syntax\n\nalright soo… we need to decide on a syntax that doesn’t suck your soul (looking at you protobuf)\n\nfield numbers.. what are they? index right. how do you index stuff in your grocery list? you write number. item why not use the same!\n\nso something like this:\n\n`1. name`\nwe need the schema to represent the types. lets just steal how other languages do it and do it like this:\n\n`1. name: type`\nneat huh. but wait. how do we indicate the end of a message(struct)\n\nwell 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.\n\n```\nmessage name:\n 1. name:type\n 2. name:type\n 3. name:type\nend\n```\nand no, indentations shouldn’t matter. its so annoying to work with languages where indentation matters. its just painful. lets just not do that.\n\nso..how will you identify the end of the line without a semicolon? new line char?\n\nI 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.\n\nwe could use the number! if we see a number and a dot we just consider it a new entry!\n\nneat huh.𐔌*ˊᵕˋ*𐦯\n\nproblem…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:\n\n `number. name: type = defaultValue`\nand that’s optional. pretty intuitive.\n\nnow that we are here anyway lets think about all the different kinds of data people could represent…\n\nwell we obviously got our entries of types.\n\noh 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..\n\noh we could just have them be function like, that’s pretty intuitive.\n\n `number. name: structure(type)`\nlike:\n\n `1. friends: list(People)`\noh wait but what is people? oh it should be a message too. something like this:\n\n```\nmessage People:\n 1. name: string\n 2. location: string\nend\n```\nhuh.. 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.\n\nhey 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:\n\n```\nmessage People:\n 1. name: string\n 2. location: string\n 3. friends: list(People)\n```\nnow 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:\n\n```\nenum Name:\n number. name \n number. name\n number. name\nend\n```\nalso 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\n\noh 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\n\n `number. name: union(type, type, type...)`\noh wait.. our default value. how would that work with unions. if we have a union like this:\n\n `number. name: union(i32, i64) = 10`\nit is ambiguous weather 10 is an i32 or an i64 so when field is not found what should we do?\n\nwe could fix this by having the default be next to the type.\n\n `number. name: union(i32 = 10, i64)`\nnow if a the field is not found it will be an i32 with value 10\n\nokay well people would wanna map stuff as well…so we add\n\n `number. name: map(key_type, value_type)`\nlets just add syntax for declaring packages and importing stuff:\n\n`package \"package name\"``import \"package\"`\nhey would you look at that we have some very neat syntax. lets just put it all together:\n\n```\npackage \"com.game.core\"\nimport \"math.jbin\"\nenum Activity:\n 1. active\n 2. inactive\nend\nmessage Player:\n 1. name: string\n 2. health: i32 = 100\n 3. weapons: list(string)\n 4. connections: list(Player)\n 5. activeStatus: Activity\n 6. inventory: map(string, i32)\n 7. balance: union(string=\"empty\", i32)\nend\n```\noh wait…we have a whole language now….\n\nanyway. this is the equivalent of it in .proto\n\n```\nsyntax = \"proto2\";\npackage com.game.core;\nimport \"math.proto\";\nenum Activity {\n ACTIVE = 1;\n INACTIVE = 2;\n}\nmessage Player {\n optional string name = 1;\n optional int32 health = 2 [default = 100];\n \n repeated string weapons = 3;\n repeated Player connections = 4;\n \n optional Activity active_status = 5;\n map inventory = 6;\n \n oneof balance {\n string empty = 7;\n int32 amount = 8;\n }\n}\n```\nlook at that. ew.\n\n## Time to actually implement this\n\nTo implement this I naturally chose C++.\n\nBy “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.\n\nOkay. Enough designing. Time to actually make the thing work.\n\nFirst, we need to encode our binary.\n\n### Encoding and Decoding our Data\n\nTo encode a varint, it’s basically just this:\n\n```\nvoid encodeVariant(std::vector &buffer, uint64_t value) {\n while (value >= 128) {\n uint8_t lower = value & 127; // 127 = 01111111\n lower |= 128;\n buffer.push_back(lower);\n value >>= 7;\n }\n uint8_t lower = value & 127;\n buffer.push_back(lower);\n}\n```\nThis 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.\n\nThen we shift the value by 7 bits and repeat.\n\nFor the final byte, we leave the MSB at 0.\n\npretty simple. and we can decode it using this:\n\n```\nuint64_t decodeVariant(const std::vector &buffer, size_t &offset) {\n uint64_t result = 0;\n int shift = 0;\n while ((buffer[offset] & 128) != 0 && offset < buffer.size()) {\n uint8_t byte = buffer[offset++];\n byte &= 127;\n const uint64_t cast = static_cast(byte) << shift;\n result |= cast;\n shift += 7;\n }\n uint8_t byte = buffer[offset++] & 127;\n const uint64_t cast = static_cast(byte) << shift;\n result |= cast;\n return result;\n}\n```\nNow that we can encode and decode our varints using LEB128 lets encode and decode some tags(our header metadata we discussed about)\n\n```\nvoid encodeTag(std::vector &buffer, uint32_t fieldNumber,\n wiretype wiretype) {\n uint64_t val = (static_cast(fieldNumber) << 2);\n val |= static_cast(wiretype);\n encodeVariant(buffer, val);\n}\nvoid decodeTag(const std::vector &buffer, size_t &offset,\n uint32_t &outFieldNumber, wiretype &outType) {\n uint64_t val = decodeVariant(buffer, offset);\n outType = static_cast(val & 3);\n outFieldNumber = val >> 2;\n}\n```\nAnd we can add a couple of helpers for strings:\n\n```\nvoid encodeString(std::vector &buffer, uint32_t fieldNumber,\n const std::string &text) {\n encodeTag(buffer, fieldNumber, wiretype::Delimited);\n encodeVariant(buffer, text.size());\n buffer.insert(buffer.end(), text.begin(), text.end());\n}\nstd::string decodeString(const std::vector &buffer, size_t &offset) {\n uint64_t size = decodeVariant(buffer, offset);\n std::string result =\n std::string(buffer.begin() + offset, buffer.begin() + offset + size);\n offset += size;\n return result;\n}\n```\nEncoding a string is now just three things: write its tag, write its length, then write its bytes.\n\nbelieve it or not, that’s basically all our core engine done! the rest is just the compiler and the json conversion stuff! ٩(^ᗜ^ )و ´-\n\nGreat! now that we have written our binary encoding… lets make a compiler should be simple…right?\n\n### Building Compiler\n\nYes it is a compiler. stop it I don’t wanna call it a transpiler it is a compiler. the definition is:\n\ncompiler is a computer program that translates source code written in one programming language (the source language) into another programming language (the target language), while preserving the exact meaning and behavior of the original code.\n\nours does that. gtfo compiler people. my program takes my schema and translates it into either a binary or code.\n\n#### The problem\n\nOur language is pretty cute. Pretty slick.\n\nUnfortunately, the computer has no idea what any of it means.\n\nIt’s just bytes.\n\nso lets assign meaning to these symbols!\n\nlets take our syntax:\n\n `1. name:string`\nso its in the structure of:\n\n`number → dot → identifier → colon → type`\nand then we can use this to build our representation of these entries. that’s what a Lexer does\n\n#### Building the Lexer\n\nYes lexer is like what you think it is. its just a big loop with a bunch of if statements. All it does is read our file and spit out these tokens.(not the ai kind)\n\n```\nenum class TokenType {\n Keyword_Message,\n Keyword_Enum,\n Keyword_Optional,\n Keyword_Map,\n Keyword_Union,\n Keyword_End,\n Keyword_Package,\n Keyword_Import,\n Identifier,\n Number,\n StringLiteral,\n Comment,\n Equals,\n Colon,\n Comma,\n Dot,\n LParen,\n RParen,\n EndOfFile\n};\n```\nso our file\n\n```\nmessage User:\n 1. name: string\n 2. id: i32\n```\nthe tokenized output would be:\n\n```\n [Keyword_Message]\n [Identifier: \"User\"]\n [Colon]\n [Number: 1]\n [Dot]\n [Identifier: \"name\"]\n [Colon]\n [Identifier: \"string\"]\n [Number: 2]\n [Dot]\n [Identifier: \"id\"]\n [Colon]\n [Identifier: \"i32\"]\n [EndOfFile]\n```\nPretty neat. Now the parser doesn’t have to decipher a bunch of raw characters. It can just work with these tokens. parser looks at these and then actually emits the AST (abstract syntax tree).\n\n#### What is AST?\n\nIts just how we represent our program data in graphLang it was a literal tree node that held all the data and all data was just a single shape. For this one we can define our schema as the root. we just have two kinds of messages rn messages and enums so our head can be defined as:\n\n```\nstruct Schema {\n std::vector enums;\n std::vector messages;\n};\n```\nso our Schema will be the root node and the tree will look like this:\n\n```\n (Schema)\n / \\\n(enums) (messages)\n```\n#### Building the AST\n\nsoo…. what is enums and messages? from the definition above you can see its a vector of structs. our messages can be defined as:\n\n```\nstruct MessageDef {\n std::string name;\n std::vector fields;\n int line = 0;\n std::string comment = \"\";\n};\n```\nand then our Field as:\n\n```\nstruct Field {\n uint32_t number;\n std::string name;\n DataType type;\n bool isOptional = false;\n std::string defaultValue = \"\";\n int line = 0;\n std::string comment = \"\";\n};\n```\nnow our AST looks like this:\n\n```\nSchema\n└── messages\n └── MessageDef\n ├── name\n ├── line\n ├── comment\n └── fields\n └── Field\n ├── number\n ├── name\n ├── type\n ├── isOptional\n ├── defaultValue\n ├── line\n └── comment\n```\nand all that’s left is our enum definition:\n\n```\nstruct EnumDef {\n std::string name;\n std::vector entries;\n int line = 0;\n std::string comment = \"\";\n};\n```\nand our enum entry:\n\n```\nstruct EnumEntry {\n uint32_t number;\n std::string name;\n int line = 0;\n std::string comment = \"\";\n};\n```\nGreat! we got all our pieces. our AST looks like this now:\n\n```\nSchema\n├── Enums\n│ └── EnumDef\n│ ├── name\n│ └── entries\n│ └── EnumEntry\n│ ├── number\n│ └── name\n│\n└── Messages\n └── MessageDef\n ├── name\n └── fields\n └── Field\n ├── number\n ├── name\n ├── type\n ├── isOptional\n └── defaultValue\n```\n#### Building the parser\n\nwe use this and build our parser. and yes. our parser is just a loop with if statements (well technically recursive decent or whatever but recursion is just a form of iteration).\n\nit is actually pretty simple the whole loop:\n\n```\nSchema Parser::parse() {\n Schema s;\n while (!isAtEnd()) {\n if (peek().type == TokenType::Comment) {\n consume();\n continue;\n }\n if (peek().type == TokenType::Keyword_Package) {\n consume();\n if (peek().type == TokenType::StringLiteral) {\n s.packageName = consume().value;\n } else {\n error(\"Expected string literal after package\");\n }\n } else if (peek().type == TokenType::Keyword_Import) {\n consume();\n if (peek().type == TokenType::StringLiteral) {\n s.imports.push_back(consume().value);\n } else {\n error(\"Expected string literal after import\");\n }\n } else if (peek().type == TokenType::Keyword_Message)\n s.messages.push_back(parseMessage());\n else if (peek().type == TokenType::Keyword_Enum)\n s.enums.push_back(parseEnum());\n else\n error(\"Unexpected token in global scope\");\n }\n return s;\n}\n```\nand for each of the types its just a bunch if conditions checking and then returning the AST node.\n`consume()` returns the current token and moves the pointer over by one and `peek()` gives you the next token data without moving the pointer\n\nGREAT! lets test it out.\n\n```\n message User:\n 1. name: adfasdfasdfasdfasd\n 2. id: 012349\n```\nlets see what our parser says:\n\n“Mighty good mate! seems excellent innit? want a cuppa?”\n\nyeah..so we need a thing that checks the user isn’t just syntactically correct but also the shit makes sense.\n\nso we need a fact checker, a twitter community note if you will.\n\nAnd that’s what our semantic analyzer does!\n\n#### Building the Semantic Analyzer\n\nSo to validate stuff we will be doing it in two passes.\n\n- First pass we build all of our symbols and put them into a table. (Basically just all the valid stuff that are identifiable)\n- Second pass we use that the table we built validate the AST.\n\n```\nvoid SemanticAnalyzer::analyze(const Schema &schema) {\n buildSymbolTable(schema);\n validateEnums(schema);\n validateMessages(schema);\n validateCyclicDependencies(schema);\n}\n```\nBecause we do this in two passes, declaration order doesn’t matter. Which is pretty neat.\n\nSo during `validateMessages` , when it looks at\n`adfasdfasdfasdfasd` , it checks our symbol table,\nrealizes that type doesn’t exist, and throws an error . It also checks\nthat you didn’t do something stupid like use field\nnumber 1 twice, or use a list as a map key.\n\nGreat! Look at what we got so far!\n\n- A Lexer that chops everything up into tokens\n- A Parser that takes the tokens and builds the AST\n- A Semantic Analyzer that validates the AST and throws errors\n- An encoder/decoder using LEB128.\n\nNow all that’s left to do is to do two things.\n\n- Convert JSON files into binary dynamically\n- Codegen from the schema so they can use them in their language natively\n\n### Dynamic Packer\n\nNow for the dynamic packer. It takes a schema, takes a JSON file, and builds our binary.\n\nFor JSON, I just used `nlohmann/json`. Parsing JSON on top of everything else would’ve been a completely unnecessary side quest.\n\nSo we have our JSON loaded in memory. We have our AST loaded in memory. Now we just walk them together.\n\nWhen the JSON parser sees the key “id”: 123 , it doesn’t know what to do. But it asks the AST! The AST says,\n\n“Oh, id ? That’s field number 2, and it’s an i32 .”\n\nSo the Packer just calls our `encodeTag()` and `encodeVariant()`\nfunctions and spits the bytes into our buffer.\n\nNotice what we didn’t do? We didn’t generate any C++ code. We didn’t compile any wrappers. We just read the JSON, read the schema, and built the binary dynamically.\n\ntake that protobuf\n\n**Lets test it out!**\n\n```\n{\n \"name\": \"Pranav\",\n \"health\": 100\n}\n```\nIf we save this as JSON, with spaces and quotes, it’s about 35 bytes\n\nlets pack it in binary.\n\nand that is…\n\n**NINE BYTES**\n\n**hell yeahh look at that!!!**\n\n74.29% REDUCTION\n\nit would be even higher if we didn’t have strings and stuff. 6 of the 9 bytes are used for the word “Pranav” but besides the point.\n\nwe have reduced our size of storage by a LOT.\n\nAnd decoding is way simpler too. The binary already tells us what each field is supposed to be, so the decoder doesn’t have to deal with JSON’s syntax and type representation.\n\nBut what if you don’t want to pay the cost of dynamically looking everything up at runtime? What if you just want normal structs in your language?\n\nThat’s where AOT code generation comes in.\n\n### Codegen\n\nHmm… how would one generate code? I mean we have our AST so we know what it looks like and what it is semantically so like its just translating that into our language..\n\nyou could write a `cCodeGen()` func and add it to our class and call.\n\nif we wanted a generator for python? oh that’s easy! i’ll just add a `pythonCodeGen`!\n\noh I need a `jsCodeGen()` okay look. too far. why are you writing javascript. but regardless.\n\nBut apparently the customer is always right in their language preferences or whatever. okay now this class is getting a wee bit too bloated for my liking.\n\nThat’s exactly why we need a visitor pattern!\n\n#### Visitor Pattern\n\nSo what is a visitor? in hindsight, design pattern cope for ones who’s language doesn not have algebraic datatypes. So why did I use it even though cpp has the `std::variant`? Idk I read it in an article once. I wanted ot learn about it.\n\nAnyway. so a visitor pattern is just a lil handshake the caller and callee do. we get type safety from it. in our implementation our caller passes itself in and becomes the visitor. the callee or the acceptor accepts the visitor and does a little func call on the visitor passing itself in triggering a double dispatch. pretty neat..but its just so much mental overhead for a simple problem.\n\nto accomplish this we will need to edit our structs in the ADT to also hold a function.\n\n`void accept(SchemaVisitor &visitor) const;`\nand we create an abstract class with a bunch of virtual methods that our generators implement:\n\n```\n#pragma once\n#include \"Schema.hpp\"\nclass SchemaVisitor {\n public:\n virtual ~SchemaVisitor() = default;\n virtual void visit(const Schema &s) = 0;\n virtual void visit(const MessageDef &m) = 0;\n virtual void visit(const EnumDef &e) = 0;\n virtual void visit(const EnumEntry &ee) = 0;\n virtual void visit(const Field &f) = 0;\n};\n```\nso our c generator for example looks like this:\n\n```\n#pragma once\n#include \"SchemaVisitor.hpp\"\n#include \n#include \nclass CGenerator : public SchemaVisitor {\n private:\n std::ostream &out;\n std::string currentEnumName;\n const Schema* currentSchema = nullptr;\n public:\n CGenerator(std::ostream &outputStream) : out(outputStream) {}\n void visit(const Schema &schema) override;\n void visit(const MessageDef &message) override;\n void visit(const EnumDef &enumDef) override;\n void visit(const EnumEntry &ee) override;\n void visit(const Field &field) override;\n};\n```\nso our C generator just overrides these funcs and in these visits it does this:\n\n```\nvoid CGenerator::visit(const EnumDef &enumDef) {\n currentEnumName = enumDef.name;\n out << \"typedef enum {\\n\";\n for (const auto &ee : enumDef.entries) {\n ee.accept(*this);\n }\n out << \"} \" << enumDef.name << \";\\n\\n\";\n}\n```\nwhen we do ee.accept(*this) it does this:\n\n`void EnumEntry::accept(SchemaVisitor &visitor) const { visitor.visit(*this); }`\nso it just calls CGenerator.visit(ee) so the visit for environment entries is called in CGenerator.\n\n```\nvoid CGenerator::visit(const EnumEntry &ee) {\n out << \" \" << currentEnumName << \"_\" << ee.name << \" = \" << ee.number << \",\\n\";\n}\n```\nand this is done for each type. and that’s how the code is generated.\n\nGREAT! lets test it out..\n\noh wait. we cant. we don’t have a way to do that. we need a cli.\n\n### Building CLI\n\nFor the CLI I used jarro2783/cxxopts cuz I didn’t want to do manual parsing. it will be a fun project both this and the json I will do them sometime else but for now I used these.\n\nAnd building the cli was pretty easy from this library you get a bunch of stuff that just works.\n\nI just wrote my options.\n\n```\noptions.add_options()(\"command\", \"Command to run (e.g. build, pack)\",\n cxxopts::value())(\n \"input\", \"Input schema file\", cxxopts::value())(\n \"o,out\",\n \"Output (target language for build, or output binary file for \"\n \"pack)\",\n cxxopts::value())(\"j,json\",\n \"Input JSON file (for pack command)\",\n cxxopts::value())(\n \"m,msg\", \"Root message name to pack (for pack command)\",\n cxxopts::value())(\"h,help\", \"Print usage\");\n options.parse_positional({\"command\", \"input\"});\n auto result = options.parse(argc, argv);\n```\nand it works. it was great. and these options were handled in a bunch of if statements(now that I think about it most of this project has just been a loop and a bunch of if statements)\n\n```\nif (command == \"build\") {\n if (!result.count(\"input\")) {\n std::cerr << \"Error: No input file specified.\" << std::endl;\n return 1;\n }\n if (!result.count(\"out\")) {\n std::cerr << \"Error: --out flag is required (e.g., --out c).\"\n << std::endl;\n return 1;\n }\n std::string inputFile = result[\"input\"].as();\n std::string targetLang = result[\"out\"].as();\n std::ifstream file(inputFile);\n if (!file.is_open()) {\n std::cerr << \"Error: Could not open file \" << inputFile\n << std::endl;\n return 1;\n }\n std::stringstream buffer;\n buffer << file.rdbuf();\n std::string schemaText = buffer.str();\n std::vector tokens = tokenize(schemaText);\n Parser parser(tokens);\n Schema schema = parser.parse();\n SemanticAnalyzer analyzer;\n analyzer.analyze(schema);\n if (targetLang == \"c\") {\n CGenerator cGen(std::cout);\n schema.accept(cGen);\n } else if (targetLang == \"py\" || targetLang == \"python\") {\n PythonGenerator pyGen(std::cout);\n schema.accept(pyGen);\n } else {\n std::cerr << \"Code generation for '\" << targetLang\n << \"' is not supported yet!\" << std::endl;\n }\n```\nanyhow. lets test it out.\n\nwe will write our schema as this:\n\n```\npackage \"com.mmo.game\"\nenum Faction:\n 1. alliance\n 2. horde\n 3. neutral\nend\nmessage Vector3:\n 1. x: i32\n 2. y: i32\n 3. z: i32\nend\nmessage InventoryItem:\n 1. itemId: i32\n 2. quantity: i32\n 3. isSoulbound: bool\nend\nmessage Character:\n 1. id: i64\n 2. name: string\n 3. level: i32\n 4. faction: Faction\n 5. position: Vector3\n 6. inventory: list(InventoryItem)\n 7. attributes: map(string, i32)\nend\n```\nand run build with output as c… and..\n\n```\n#pragma once\n#include \n#include \n#include \n#include \ntypedef struct Vector3 Vector3;\ntypedef struct InventoryItem InventoryItem;\ntypedef struct Character Character;\ntypedef struct {\n InventoryItem* data;\n size_t length;\n size_t capacity;\n} jbin_list_InventoryItem;\ntypedef struct {\n char** keys;\n int32_t* values;\n size_t length;\n size_t capacity;\n} jbin_map_char_ptr_int32;\ntypedef enum {\n Faction_alliance = 1,\n Faction_horde = 2,\n Faction_neutral = 3,\n} Faction;\nstruct Vector3 {\n int32_t x;\n int32_t y;\n int32_t z;\n};\nstruct InventoryItem {\n int32_t itemId;\n int32_t quantity;\n bool isSoulbound;\n};\nstruct Character {\n int64_t id;\n char* name;\n int32_t level;\n Faction faction;\n Vector3 position;\n jbin_list_InventoryItem inventory;\n jbin_map_char_ptr_int32 attributes;\n};\n```\nLOOK AT THAT!! zero dependency left from the program. we provide all the stuff it needs from our schema!!!\n\n(note: that isn’t the full c file that was generated. there were also a lot of pack/unpack functions for individual messages, setters and getters and encode/decode funcs)\n\nwe can also encode to binary by passing in a json file.\n\n```\n{\n \"id\": 123456789,\n \"name\": \"LeroyJenkins\",\n \"level\": 60,\n \"faction\": \"alliance\",\n \"position\": {\n \"x\": 100,\n \"y\": 200,\n \"z\": 300\n },\n \"inventory\": [\n { \"itemId\": 999, \"quantity\": 1, \"isSoulbound\": true },\n { \"itemId\": 45, \"quantity\": 100, \"isSoulbound\": false }\n ],\n \"attributes\": {\n \"strength\": 120,\n \"agility\": 45\n }\n}\n```\nand the size of this json is `401 bytes`\n\nlets pack it into binary. and the file size is..\n\n`80 bytes!`\n\nEIGHTY PERCENT REDUCTION\n\n`80.05%`\n\n## Conclusion\n\nSo yeah. I started out just wanting to save some JSON out of spite, and I accidentally built a lexer, a parser, an AST, a semantic analyzer, a dynamic binary packer, and a multi-language code generator. And honestly? Packing binary is fun, actually.\n\nanyhow, checkout the repo.","body_html":"

Why would anyone do this?

\n

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

\n

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

\n

Turns out, the answer was binary.

\n

Naturally, I had a brilliant idea:

\n

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

\n

Surely it’s just a little wb . ( ˶ˆᗜˆ˵ )

\n

It was, unfortunately, not just a wb.

\n

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

\n

What is binary packing?

\n

Say we got some data

\n

"hello world"\nthen it would be translated in ascii to

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

So h becomes 104 in ASCII.

\n

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

\n
h        e        l\n01101000 01100101 01101100 \nl        o        [SPACE]\n01101100 01101111 00100000 \nw        o        r\n01110111 01101111 01110010 \nl        d\n01101100 01100100
\n

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

\n
FILE *f = fopen("file.bin", "wb");\nunsigned char data[] = "hello world";\nfwrite(data, 1, sizeof(data) - 1, f);\nfclose(f);
\n

Simple enough. Now let’s try writing 104.

\n

Obviously, we could just write 104 as ASCII characters:

\n

'1' '0' '4' → 49 48 52\nBut that’s 3 bytes for a number that only needs 1 byte.

\n

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.”

\n

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.

\n

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

\n

[TYPE][DATA]\nsay 0 is int and 1 is string so 104 would be

\n

00000000 01101000\nand string would be..

\n

00000001 01101000\noh wait…..

\n

that would only give is h

\n

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

\n

[TYPE][LENGTH][DATA]\ngreat! now we can represent our string like this:

\n
 [TYPE]  [LENGTH] [DATA]\n(STRING)  (11)\n00000001 00001011 00...\nh        e        l\n01101000 01100101 01101100 \nl        o        [SPACE]\n01101100 01101111 00100000 \nw        o        r\n01110111 01101111 01110010 \nl        d\n01101100 01100100
\n

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

\n

now you could just package it all together

\n

[TYPE:STRING][LENGTH:6][WORD:userid][TYPE:INT][LENGTH:-][DATA:123]\nGreat! 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?

\n

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

\n

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

\n

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

\n

A length byte for the header, perhaps?

\n

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

\n

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

\n

We could have one bit say:

\n

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

\n

You might think: why not use the LSB?

\n

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

\n

So we’ll use the MSB instead.

\n

so now our tag looks something like this:

\n

[CONTINUATION BIT][7 BITS OF DATA]\nIf the continuation bit is 1, there’s another header byte. If it’s 0, the header is done.

\n

using this, we can just have our 123 be

\n

[TYPE=0][DATA=123]\nand if its a string.

\n

[TYPE=1][LENGTH=11][DATA=104]...\nso its of type 1, length 11

\n

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

\n

We use the same thing! but for ints!

\n

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

\n
10000001 00000000\n^\nMSB / continuation bit
\n

(in big endian)

\n

what the binary reader will do:

\n
  • Reads the first byte.
  • The MSB is 1, so there’s another byte.
  • The remaining 7 bits are 1.
  • Reads the second byte.
  • Its MSB is 0, so this is the last byte.
  • Its remaining 7 bits are 0.
  • Combines the two 7-bit values to get 128.
\n

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

\n

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

\n

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

\n

But notice, We are storing this data per field.

\n
[TYPE][DATA]\n[TYPE][DATA]\n[TYPE][DATA]
\n

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

\n

Take a C struct:

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

this would be say on a 32 bit system.

\n

[32-bit int] [32-bit pointer] [10 × 32-bit ints]\nand we didn’t have to add headers everytime. because we know the type of the data from the struct itself.

\n

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

\n

And yes, we can.

\n

That’s what a schema is!

\n

so for our struct our schema can just be:

\n
i: int\ns: char *\na: list(int)
\n

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

\n

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

\n

That’s what protobuf does

\n

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

\n

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

\n

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

\n

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.

\n

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

\n

so now our encoding types are:

\n
  • varint
  • f32
  • f64
  • delimited
\n

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.

\n

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

\n

Four values fit perfectly into 2 bits.

\n
00 - varint \n01 - f32\n10 - f64\n11 - delimited
\n

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

\n

wait how?

\n

some binary trickery..not really.

\n

You just shove them together.

\n

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

\n

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

\n
00001010 (10)\nleft shift that by 2\n00101000\nOR it with our type!\n00101011
\n

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

\n

But what if we go FURTHER.

\n

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

\n

Why stop there?

\n

What if we could pack the length in too?

\n

We can.

\n

now our header can hold

\n

[FIELD NUMBER][LENGTH][TYPE]\nALL in a singular varint!!!! ◝(ᵔᗜᵔ)◜

\n

Cool. Except for one thing

\n

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.

\n

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

\n

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.

\n

Building the schema syntax

\n

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

\n

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!

\n

so something like this:

\n

1. name\nwe need the schema to represent the types. lets just steal how other languages do it and do it like this:

\n

1. name: type\nneat huh. but wait. how do we indicate the end of a message(struct)

\n

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.

\n
message name:\n    1. name:type\n    2. name:type\n    3. name:type\nend
\n

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

\n

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

\n

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.

\n

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

\n

neat huh.𐔌ˊᵕˋ𐦯

\n

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:

\n
`number. name: type = defaultValue`
\n

and that’s optional. pretty intuitive.

\n

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

\n

well we obviously got our entries of types.

\n

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..

\n

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

\n
`number. name: structure(type)`
\n

like:

\n
`1. friends: list(People)`
\n

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

\n
message People:\n    1. name: string\n    2. location: string\nend
\n

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.

\n

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:

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

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:

\n
enum Name:\n    number. name \n    number. name\n    number. name\nend
\n

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

\n

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

\n
`number. name: union(type, type, type...)`
\n

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

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

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

\n

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

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

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

\n

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

\n
`number. name: map(key_type, value_type)`
\n

lets just add syntax for declaring packages and importing stuff:

\n

package "package name"import "package"\nhey would you look at that we have some very neat syntax. lets just put it all together:

\n
package "com.game.core"\nimport "math.jbin"\nenum Activity:\n    1. active\n    2. inactive\nend\nmessage Player:\n    1. name: string\n    2. health: i32 = 100\n    3. weapons: list(string)\n    4. connections: list(Player)\n    5. activeStatus: Activity\n    6. inventory: map(string, i32)\n    7. balance: union(string="empty", i32)\nend
\n

oh wait…we have a whole language now….

\n

anyway. this is the equivalent of it in .proto

\n
syntax = "proto2";\npackage com.game.core;\nimport "math.proto";\nenum Activity {\n  ACTIVE = 1;\n  INACTIVE = 2;\n}\nmessage Player {\n  optional string name = 1;\n  optional int32 health = 2 [default = 100];\n  \n  repeated string weapons = 3;\n  repeated Player connections = 4;\n  \n  optional Activity active_status = 5;\n  map<string, int32> inventory = 6;\n  \n  oneof balance {\n    string empty = 7;\n    int32 amount = 8;\n  }\n}
\n

look at that. ew.

\n

Time to actually implement this

\n

To implement this I naturally chose C++.

\n

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.

\n

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

\n

First, we need to encode our binary.

\n

Encoding and Decoding our Data

\n

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

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

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.

\n

Then we shift the value by 7 bits and repeat.

\n

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

\n

pretty simple. and we can decode it using this:

\n
uint64_t decodeVariant(const std::vector<uint8_t> &buffer, size_t &offset) {\n    uint64_t result = 0;\n    int shift = 0;\n    while ((buffer[offset] & 128) != 0 && offset < buffer.size()) {\n        uint8_t byte = buffer[offset++];\n        byte &= 127;\n        const uint64_t cast = static_cast<uint64_t>(byte) << shift;\n        result |= cast;\n        shift += 7;\n    }\n    uint8_t byte = buffer[offset++] & 127;\n    const uint64_t cast = static_cast<uint64_t>(byte) << shift;\n    result |= cast;\n    return result;\n}
\n

Now that we can encode and decode our varints using LEB128 lets encode and decode some tags(our header metadata we discussed about)

\n
void encodeTag(std::vector<uint8_t> &buffer, uint32_t fieldNumber,\n               wiretype wiretype) {\n    uint64_t val = (static_cast<uint64_t>(fieldNumber) << 2);\n    val |= static_cast<uint64_t>(wiretype);\n    encodeVariant(buffer, val);\n}\nvoid decodeTag(const std::vector<uint8_t> &buffer, size_t &offset,\n               uint32_t &outFieldNumber, wiretype &outType) {\n    uint64_t val = decodeVariant(buffer, offset);\n    outType = static_cast<wiretype>(val & 3);\n    outFieldNumber = val >> 2;\n}
\n

And we can add a couple of helpers for strings:

\n
void encodeString(std::vector<uint8_t> &buffer, uint32_t fieldNumber,\n                  const std::string &text) {\n    encodeTag(buffer, fieldNumber, wiretype::Delimited);\n    encodeVariant(buffer, text.size());\n    buffer.insert(buffer.end(), text.begin(), text.end());\n}\nstd::string decodeString(const std::vector<uint8_t> &buffer, size_t &offset) {\n    uint64_t size = decodeVariant(buffer, offset);\n    std::string result =\n        std::string(buffer.begin() + offset, buffer.begin() + offset + size);\n    offset += size;\n    return result;\n}
\n

Encoding a string is now just three things: write its tag, write its length, then write its bytes.

\n

believe it or not, that’s basically all our core engine done! the rest is just the compiler and the json conversion stuff! ٩(^ᗜ^ )و ´-

\n

Great! now that we have written our binary encoding… lets make a compiler should be simple…right?

\n

Building Compiler

\n

Yes it is a compiler. stop it I don’t wanna call it a transpiler it is a compiler. the definition is:

\n

compiler is a computer program that translates source code written in one programming language (the source language) into another programming language (the target language), while preserving the exact meaning and behavior of the original code.

\n

ours does that. gtfo compiler people. my program takes my schema and translates it into either a binary or code.

\n

The problem

\n

Our language is pretty cute. Pretty slick.

\n

Unfortunately, the computer has no idea what any of it means.

\n

It’s just bytes.

\n

so lets assign meaning to these symbols!

\n

lets take our syntax:

\n
`1. name:string`
\n

so its in the structure of:

\n

number → dot → identifier → colon → type\nand then we can use this to build our representation of these entries. that’s what a Lexer does

\n

Building the Lexer

\n

Yes lexer is like what you think it is. its just a big loop with a bunch of if statements. All it does is read our file and spit out these tokens.(not the ai kind)

\n
enum class TokenType {\n    Keyword_Message,\n    Keyword_Enum,\n    Keyword_Optional,\n    Keyword_Map,\n    Keyword_Union,\n    Keyword_End,\n    Keyword_Package,\n    Keyword_Import,\n    Identifier,\n    Number,\n    StringLiteral,\n    Comment,\n    Equals,\n    Colon,\n    Comma,\n    Dot,\n    LParen,\n    RParen,\n    EndOfFile\n};
\n

so our file

\n
message User:\n    1. name: string\n    2. id: i32
\n

the tokenized output would be:

\n
    [Keyword_Message]\n    [Identifier: "User"]\n    [Colon]\n    [Number: 1]\n    [Dot]\n    [Identifier: "name"]\n    [Colon]\n    [Identifier: "string"]\n    [Number: 2]\n    [Dot]\n    [Identifier: "id"]\n    [Colon]\n    [Identifier: "i32"]\n    [EndOfFile]
\n

Pretty neat. Now the parser doesn’t have to decipher a bunch of raw characters. It can just work with these tokens. parser looks at these and then actually emits the AST (abstract syntax tree).

\n

What is AST?

\n

Its just how we represent our program data in graphLang it was a literal tree node that held all the data and all data was just a single shape. For this one we can define our schema as the root. we just have two kinds of messages rn messages and enums so our head can be defined as:

\n
struct Schema {\n    std::vector<EnumDef> enums;\n    std::vector<MessageDef> messages;\n};
\n

so our Schema will be the root node and the tree will look like this:

\n
    (Schema)\n    /      \\\n(enums) (messages)
\n

Building the AST

\n

soo…. what is enums and messages? from the definition above you can see its a vector of structs. our messages can be defined as:

\n
struct MessageDef {\n    std::string name;\n    std::vector<Field> fields;\n    int line = 0;\n    std::string comment = "";\n};
\n

and then our Field as:

\n
struct Field {\n    uint32_t number;\n    std::string name;\n    DataType type;\n    bool isOptional = false;\n    std::string defaultValue = "";\n    int line = 0;\n    std::string comment = "";\n};
\n

now our AST looks like this:

\n
Schema\n└── messages\n    └── MessageDef\n        ├── name\n        ├── line\n        ├── comment\n        └── fields\n            └── Field\n                ├── number\n                ├── name\n                ├── type\n                ├── isOptional\n                ├── defaultValue\n                ├── line\n                └── comment
\n

and all that’s left is our enum definition:

\n
struct EnumDef {\n    std::string name;\n    std::vector<EnumEntry> entries;\n    int line = 0;\n    std::string comment = "";\n};
\n

and our enum entry:

\n
struct EnumEntry {\n    uint32_t number;\n    std::string name;\n    int line = 0;\n    std::string comment = "";\n};
\n

Great! we got all our pieces. our AST looks like this now:

\n
Schema\n├── Enums\n│   └── EnumDef\n│       ├── name\n│       └── entries\n│           └── EnumEntry\n│               ├── number\n│               └── name\n│\n└── Messages\n    └── MessageDef\n        ├── name\n        └── fields\n            └── Field\n                ├── number\n                ├── name\n                ├── type\n                ├── isOptional\n                └── defaultValue
\n

Building the parser

\n

we use this and build our parser. and yes. our parser is just a loop with if statements (well technically recursive decent or whatever but recursion is just a form of iteration).

\n

it is actually pretty simple the whole loop:

\n
Schema Parser::parse() {\n    Schema s;\n    while (!isAtEnd()) {\n        if (peek().type == TokenType::Comment) {\n            consume();\n            continue;\n        }\n        if (peek().type == TokenType::Keyword_Package) {\n            consume();\n            if (peek().type == TokenType::StringLiteral) {\n                s.packageName = consume().value;\n            } else {\n                error("Expected string literal after package");\n            }\n        } else if (peek().type == TokenType::Keyword_Import) {\n            consume();\n            if (peek().type == TokenType::StringLiteral) {\n                s.imports.push_back(consume().value);\n            } else {\n                error("Expected string literal after import");\n            }\n        } else if (peek().type == TokenType::Keyword_Message)\n            s.messages.push_back(parseMessage());\n        else if (peek().type == TokenType::Keyword_Enum)\n            s.enums.push_back(parseEnum());\n        else\n            error("Unexpected token in global scope");\n    }\n    return s;\n}
\n

and for each of the types its just a bunch if conditions checking and then returning the AST node.\nconsume() returns the current token and moves the pointer over by one and peek() gives you the next token data without moving the pointer

\n

GREAT! lets test it out.

\n
    message User:\n        1. name: adfasdfasdfasdfasd\n        2. id: 012349
\n

lets see what our parser says:

\n

“Mighty good mate! seems excellent innit? want a cuppa?”

\n

yeah..so we need a thing that checks the user isn’t just syntactically correct but also the shit makes sense.

\n

so we need a fact checker, a twitter community note if you will.

\n

And that’s what our semantic analyzer does!

\n

Building the Semantic Analyzer

\n

So to validate stuff we will be doing it in two passes.

\n
  • First pass we build all of our symbols and put them into a table. (Basically just all the valid stuff that are identifiable)
  • Second pass we use that the table we built validate the AST.
\n
void SemanticAnalyzer::analyze(const Schema &schema) {\n    buildSymbolTable(schema);\n    validateEnums(schema);\n    validateMessages(schema);\n    validateCyclicDependencies(schema);\n}
\n

Because we do this in two passes, declaration order doesn’t matter. Which is pretty neat.

\n

So during validateMessages , when it looks at\nadfasdfasdfasdfasd , it checks our symbol table,\nrealizes that type doesn’t exist, and throws an error . It also checks\nthat you didn’t do something stupid like use field\nnumber 1 twice, or use a list as a map key.

\n

Great! Look at what we got so far!

\n
  • A Lexer that chops everything up into tokens
  • A Parser that takes the tokens and builds the AST
  • A Semantic Analyzer that validates the AST and throws errors
  • An encoder/decoder using LEB128.
\n

Now all that’s left to do is to do two things.

\n
  • Convert JSON files into binary dynamically
  • Codegen from the schema so they can use them in their language natively
\n

Dynamic Packer

\n

Now for the dynamic packer. It takes a schema, takes a JSON file, and builds our binary.

\n

For JSON, I just used nlohmann/json. Parsing JSON on top of everything else would’ve been a completely unnecessary side quest.

\n

So we have our JSON loaded in memory. We have our AST loaded in memory. Now we just walk them together.

\n

When the JSON parser sees the key “id”: 123 , it doesn’t know what to do. But it asks the AST! The AST says,

\n

“Oh, id ? That’s field number 2, and it’s an i32 .”

\n

So the Packer just calls our encodeTag() and encodeVariant()\nfunctions and spits the bytes into our buffer.

\n

Notice what we didn’t do? We didn’t generate any C++ code. We didn’t compile any wrappers. We just read the JSON, read the schema, and built the binary dynamically.

\n

take that protobuf

\n

Lets test it out!

\n
{\n    "name": "Pranav",\n    "health": 100\n}
\n

If we save this as JSON, with spaces and quotes, it’s about 35 bytes

\n

lets pack it in binary.

\n

and that is…

\n

NINE BYTES

\n

hell yeahh look at that!!!

\n

74.29% REDUCTION

\n

it would be even higher if we didn’t have strings and stuff. 6 of the 9 bytes are used for the word “Pranav” but besides the point.

\n

we have reduced our size of storage by a LOT.

\n

And decoding is way simpler too. The binary already tells us what each field is supposed to be, so the decoder doesn’t have to deal with JSON’s syntax and type representation.

\n

But what if you don’t want to pay the cost of dynamically looking everything up at runtime? What if you just want normal structs in your language?

\n

That’s where AOT code generation comes in.

\n

Codegen

\n

Hmm… how would one generate code? I mean we have our AST so we know what it looks like and what it is semantically so like its just translating that into our language..

\n

you could write a cCodeGen() func and add it to our class and call.

\n

if we wanted a generator for python? oh that’s easy! i’ll just add a pythonCodeGen!

\n

oh I need a jsCodeGen() okay look. too far. why are you writing javascript. but regardless.

\n

But apparently the customer is always right in their language preferences or whatever. okay now this class is getting a wee bit too bloated for my liking.

\n

That’s exactly why we need a visitor pattern!

\n

Visitor Pattern

\n

So what is a visitor? in hindsight, design pattern cope for ones who’s language doesn not have algebraic datatypes. So why did I use it even though cpp has the std::variant? Idk I read it in an article once. I wanted ot learn about it.

\n

Anyway. so a visitor pattern is just a lil handshake the caller and callee do. we get type safety from it. in our implementation our caller passes itself in and becomes the visitor. the callee or the acceptor accepts the visitor and does a little func call on the visitor passing itself in triggering a double dispatch. pretty neat..but its just so much mental overhead for a simple problem.

\n

to accomplish this we will need to edit our structs in the ADT to also hold a function.

\n

void accept(SchemaVisitor &visitor) const;\nand we create an abstract class with a bunch of virtual methods that our generators implement:

\n
#pragma once\n#include "Schema.hpp"\nclass SchemaVisitor {\n  public:\n    virtual ~SchemaVisitor() = default;\n    virtual void visit(const Schema &s) = 0;\n    virtual void visit(const MessageDef &m) = 0;\n    virtual void visit(const EnumDef &e) = 0;\n    virtual void visit(const EnumEntry &ee) = 0;\n    virtual void visit(const Field &f) = 0;\n};
\n

so our c generator for example looks like this:

\n
#pragma once\n#include "SchemaVisitor.hpp"\n#include <ostream>\n#include <string>\nclass CGenerator : public SchemaVisitor {\n  private:\n    std::ostream &out;\n    std::string currentEnumName;\n    const Schema* currentSchema = nullptr;\n  public:\n    CGenerator(std::ostream &outputStream) : out(outputStream) {}\n    void visit(const Schema &schema) override;\n    void visit(const MessageDef &message) override;\n    void visit(const EnumDef &enumDef) override;\n    void visit(const EnumEntry &ee) override;\n    void visit(const Field &field) override;\n};
\n

so our C generator just overrides these funcs and in these visits it does this:

\n
void CGenerator::visit(const EnumDef &enumDef) {\n    currentEnumName = enumDef.name;\n    out << "typedef enum {\\n";\n    for (const auto &ee : enumDef.entries) {\n        ee.accept(*this);\n    }\n    out << "} " << enumDef.name << ";\\n\\n";\n}
\n

when we do ee.accept(*this) it does this:

\n

void EnumEntry::accept(SchemaVisitor &visitor) const { visitor.visit(*this); }\nso it just calls CGenerator.visit(ee) so the visit for environment entries is called in CGenerator.

\n
void CGenerator::visit(const EnumEntry &ee) {\n    out << "    " << currentEnumName << "_" << ee.name << " = " << ee.number << ",\\n";\n}
\n

and this is done for each type. and that’s how the code is generated.

\n

GREAT! lets test it out..

\n

oh wait. we cant. we don’t have a way to do that. we need a cli.

\n

Building CLI

\n

For the CLI I used jarro2783/cxxopts cuz I didn’t want to do manual parsing. it will be a fun project both this and the json I will do them sometime else but for now I used these.

\n

And building the cli was pretty easy from this library you get a bunch of stuff that just works.

\n

I just wrote my options.

\n
options.add_options()("command", "Command to run (e.g. build, pack)",\n                              cxxopts::value<std::string>())(\n            "input", "Input schema file", cxxopts::value<std::string>())(\n            "o,out",\n            "Output (target language for build, or output binary file for "\n            "pack)",\n            cxxopts::value<std::string>())("j,json",\n                                           "Input JSON file (for pack command)",\n                                           cxxopts::value<std::string>())(\n            "m,msg", "Root message name to pack (for pack command)",\n            cxxopts::value<std::string>())("h,help", "Print usage");\n        options.parse_positional({"command", "input"});\n        auto result = options.parse(argc, argv);
\n

and it works. it was great. and these options were handled in a bunch of if statements(now that I think about it most of this project has just been a loop and a bunch of if statements)

\n
if (command == "build") {\n            if (!result.count("input")) {\n                std::cerr << "Error: No input file specified." << std::endl;\n                return 1;\n            }\n            if (!result.count("out")) {\n                std::cerr << "Error: --out flag is required (e.g., --out c)."\n                          << std::endl;\n                return 1;\n            }\n            std::string inputFile = result["input"].as<std::string>();\n            std::string targetLang = result["out"].as<std::string>();\n            std::ifstream file(inputFile);\n            if (!file.is_open()) {\n                std::cerr << "Error: Could not open file " << inputFile\n                          << std::endl;\n                return 1;\n            }\n            std::stringstream buffer;\n            buffer << file.rdbuf();\n            std::string schemaText = buffer.str();\n            std::vector<Token> tokens = tokenize(schemaText);\n            Parser parser(tokens);\n            Schema schema = parser.parse();\n            SemanticAnalyzer analyzer;\n            analyzer.analyze(schema);\n            if (targetLang == "c") {\n                CGenerator cGen(std::cout);\n                schema.accept(cGen);\n            } else if (targetLang == "py" || targetLang == "python") {\n                PythonGenerator pyGen(std::cout);\n                schema.accept(pyGen);\n            } else {\n                std::cerr << "Code generation for '" << targetLang\n                          << "' is not supported yet!" << std::endl;\n            }
\n

anyhow. lets test it out.

\n

we will write our schema as this:

\n
package "com.mmo.game"\nenum Faction:\n    1. alliance\n    2. horde\n    3. neutral\nend\nmessage Vector3:\n    1. x: i32\n    2. y: i32\n    3. z: i32\nend\nmessage InventoryItem:\n    1. itemId: i32\n    2. quantity: i32\n    3. isSoulbound: bool\nend\nmessage Character:\n    1. id: i64\n    2. name: string\n    3. level: i32\n    4. faction: Faction\n    5. position: Vector3\n    6. inventory: list(InventoryItem)\n    7. attributes: map(string, i32)\nend
\n

and run build with output as c… and..

\n
#pragma once\n#include <stdint.h>\n#include <stdbool.h>\n#include <string.h>\n#include <stdlib.h>\ntypedef struct Vector3 Vector3;\ntypedef struct InventoryItem InventoryItem;\ntypedef struct Character Character;\ntypedef struct {\n    InventoryItem* data;\n    size_t length;\n    size_t capacity;\n} jbin_list_InventoryItem;\ntypedef struct {\n    char** keys;\n    int32_t* values;\n    size_t length;\n    size_t capacity;\n} jbin_map_char_ptr_int32;\ntypedef enum {\n    Faction_alliance = 1,\n    Faction_horde = 2,\n    Faction_neutral = 3,\n} Faction;\nstruct Vector3 {\n    int32_t x;\n    int32_t y;\n    int32_t z;\n};\nstruct InventoryItem {\n    int32_t itemId;\n    int32_t quantity;\n    bool isSoulbound;\n};\nstruct Character {\n    int64_t id;\n    char* name;\n    int32_t level;\n    Faction faction;\n    Vector3 position;\n    jbin_list_InventoryItem inventory;\n    jbin_map_char_ptr_int32 attributes;\n};
\n

LOOK AT THAT!! zero dependency left from the program. we provide all the stuff it needs from our schema!!!

\n

(note: that isn’t the full c file that was generated. there were also a lot of pack/unpack functions for individual messages, setters and getters and encode/decode funcs)

\n

we can also encode to binary by passing in a json file.

\n
{\n    "id": 123456789,\n    "name": "LeroyJenkins",\n    "level": 60,\n    "faction": "alliance",\n    "position": {\n        "x": 100,\n        "y": 200,\n        "z": 300\n    },\n    "inventory": [\n        { "itemId": 999, "quantity": 1, "isSoulbound": true },\n        { "itemId": 45, "quantity": 100, "isSoulbound": false }\n    ],\n    "attributes": {\n        "strength": 120,\n        "agility": 45\n    }\n}
\n

and the size of this json is 401 bytes

\n

lets pack it into binary. and the file size is..

\n

80 bytes!

\n

EIGHTY PERCENT REDUCTION

\n

80.05%

\n

Conclusion

\n

So yeah. I started out just wanting to save some JSON out of spite, and I accidentally built a lexer, a parser, an AST, a semantic analyzer, a dynamic binary packer, and a multi-language code generator. And honestly? Packing binary is fun, actually.

\n

anyhow, checkout the repo.

","headings":[{"level":2,"text":"Why would anyone do this?","id":"why-would-anyone-do-this"},{"level":2,"text":"What is binary packing?","id":"what-is-binary-packing"},{"level":2,"text":"Building the schema syntax","id":"building-the-schema-syntax"},{"level":2,"text":"Time to actually implement this","id":"time-to-actually-implement-this"},{"level":3,"text":"Encoding and Decoding our Data","id":"encoding-and-decoding-our-data"},{"level":3,"text":"Building Compiler","id":"building-compiler"},{"level":3,"text":"Dynamic Packer","id":"dynamic-packer"},{"level":3,"text":"Codegen","id":"codegen"},{"level":3,"text":"Building CLI","id":"building-cli"},{"level":2,"text":"Conclusion","id":"conclusion"}]}}