I found the post SIMD in Pure Python by retr0id about optimizing Game of Life and thought it’s a good opportunity to yap about SWAR. Make sure to read that post before continuing here! Or at least skim it.

About two months ago, I found the Teal programming language, which describes itself as a statically-typed dialect of Lua. It transpiles to Lua and runs typecheck on the developer’s machine, so it fills roughly the same niche as TypeScript. It’s used by quite a few projects, including LuaRocks and inspect. For better...

If a>b>1 and x>1, you can prove that loga⁡x<logb⁡x. (As a reminder, loga⁡x denotes the value t such that x=at.) This is very intuitive if you think about it: for “normal” numbers, the greater a, the smaller t you will need to get the same x. Yet if you ask PHP what it thinks, it will tell you you’re wrong in a...

If a>b>1 and x>1, you can prove that loga⁡x<logb⁡x. (As a reminder, loga⁡x denotes the value t such that x=at.) This is very intuitive if you think about it: for “normal” numbers, the greater a, the smaller t you will need to get the same x. Yet if you ask PHP what it thinks, it will tell you you’re wrong in a...

I need a place to describe this algorithm, since it seems to be undocumented on the 'net, so here it is. SRC is a replacement for MTF in BWT-based compressors. According to OpenBWT, it’s the best known MTF replacement measured by compression ratio, if you don’t want to use context modeling.

So I was optimizing a domain-specific compressor the other day, as one does. One important problem was chunking the input string and optimally choosing the most compact encoding for each chunk (different encodings compress different characters better, so where to split is not immediately obvious). The previous post...

So I was optimizing a domain-specific compressor the other day, as one does. One important problem was chunking the input string and optimally choosing the most compact encoding for each chunk (different encodings compress different characters better, so where to split is not immediately obvious). The previous post...

This problem arose when I was writing a specialized data compressor. Say you want to encode a byte stream, and bytes can be encoded in different formats, e.g. optimized for ASCII, numbers, raw binary, etc. These formats prioritize better compression of a specific type of data. Realistic byte streams may contain all...

I blog because I want to share knowledge. That’s how I have fun. It feels rewarding to sit down and formulate your thoughts after spending a week researching a topic for a side project. Oftentimes, such topics are largely unexplored: with the basics being too obvious and other topics laid out clearly, the remains...

Intended audience: data compression geeks. The Burrows-Wheeler transform takes a string as an input and rearranges its characters, grouping them by context. It is invertible with 𝒪(1) additional input, and together these properties give it a place in data compression and genome alignment. What Wikipedia doesn’t tell...

This is a guest post by Yuki about some tricks we use for Lua code compression in our shared ComputerCraft pet project. I’ve written about how we adapted bzip2 for this purpose earlier; this story is an installment that takes place in the same context. If you want to read more stuff from her, here’s an Atom feed and...

This post assumes basic familiarity with arithmetic coding. I’ve written an arithmetic coder, like, three times in my life, so the mistake I want to highlight is likely amateurish. But since I didn’t have a clue that my understanding was incomplete, I figured I needed to write a post about it.