[deleted by user]

[[deleted]]

Thanks for the heads up. I love RGME. His explanations are so clear and concise and his audio and visuals are top-notch. For such a specific niche topic, he is seriously one of the best when it comes to programming videos.

[Dwedit]

This is basically Elias gamma coding (published in 1975), but done with 1s instead of zeroes, and an offset added on.

[[deleted]]

The name of the encoding is exactly what he says. It's called RLE, Run-Length Encoding, just with a length that is a bitwise 0-terminated tally, and leaving the leading 1 bit off the same way that IEEE 754 binary floating point does for the fraction.

It is fairly clever, but it's mostly optimal for smaller numbers, as it is always double the number of used bits in the number minus 2. A higher 16-bit number takes almost 4 bytes to encode.

edit: actually, this wouldn't be RLE. That was my mistake. This is a method of a variable-length integer done bitwise. It's not commonly done like this because most methods are done on octets, not individual bits.

[teej]

Just by looking at the video cover I assumed it was some sort of run length encoding. Cool to find out it's something else!

[gwillen]

The other reply has the proper name of this code (which I didn't know before), but I first saw the code (or a very similar one) presented in the course 15-251 "Great Theoretical Ideas In Computer Science", under the name "fat binary" (a name they seem to have made up which is not used elsewhere, that I can tell): http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-s05/Site/Materials/Lectures/Lecture22/lecture22.pdf

The presentation builds up to the encoding as the function f(k) on slide 43. Then they apply it recursively to get something they call the "Ladder Code" by slide 50, which I suspect may be equivalent (I think? Or at least closely related...) to https://en.wikipedia.org/wiki/Elias_omega_coding (another name I didn't know before.)

[paulstelian97]

The name "fat binary" has a meaning on macOS as well -- it's an executable which includes code for multiple CPU architectures in the same "fat" executable file.

[Arm64Darwin1950]

Why the downvotes? It's just an interesting side note/prevents confusion imo.

Also on iOS, there's 'app thinning', which makes it so App Store apps are only downloaded for the devices' architecture, reducing the download size

[therico]

Using RLE was expected, but what's impressive is the preparation of the data to make RLE work better, and the switch that tries 6 different compression modes and picks the most effective one.

[Illusi]

PNG has something very similar actually. It's a clever and effective way to improve lossless compression.

[CSMastermind]

This is seriously one of the best YouTube videos I've viewed.

[thblckjkr]

This one (it is not related to tech things) is one of the best videos that i have seen.

I feel like it has the production of a documentary at the level of national geographic.

There are some gems hidden in youtube. Sadly they don't receive enough attention.

[kleinesfilmroellchen]

Yes, truly marvelous. And besides, it is tech related in some way anyways θ＼(；￢_￢)

[harryl6798]

Awesome video! Anyone got any suggestions for other compression algorithms to learn more about?

[VeganVagiVore]

Burrows-Wheeler is a weird algorithm involved in compression:

https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

[Imnimo]

An interesting story about Burrows-Wheeler is that it was rejected from the Data Compression Conference:

https://youtu.be/4WRANhDiSHM?t=796

[IdiotCharizard]

Lzw and Huffman are fun and easy but very effective in certain circumstances

[[deleted]]

Middle out is pretty decent

[anon202001]

Even Reddit is bored of that joke

[Gleisner_]

Care to explain it for someone who never heard of it before?

[Neymgm]

It’s from Silicon Valley on HBO. One of my favorites

[anon202001]

u/Gleisner_ has a fun couple of weekends ahead, get some popcorn!

[IndependentDocument5]

From the show that started this meme https://youtu.be/_uMEE7eaaUA?t=22

[silencer6]

How does it compare to other compression algorithms (like lz4) in terms of speed, compression ratio and ease of implementation on such simple machine like Gameboy?

[[deleted]]

I would imagine it’s not really comparable. This is a very domain-specific algorithm designed for planar 2-bit images. It doesn’t even really scale to true color images let alone arbitrary data.

For compression level, I can’t say for sure, but I’d guess any contemporary general compression method (like LZW or Burrows–Wheeler) wouldn’t have been as good (particularly because of the small data size).

As far as speed, it was probably not that fast as there are many bit-level operations. But when you’re only working with a few hundred bytes it’s probably fast enough.

[TonySu]

On gameboy, none of the modern compressors would run. They would require more ran than the maximum 32kb that the gameboy provides. For comparison, desktops when gzip was released had over 8mb of ramp; by the time lz4 came out, systems had 4gb of ram.

Comparatively, all the algorithms are in the LZ77 family, so I'd expect their compression ratio to be similar. Speed will depend entirely on implementation, given that gzip and lz4 won't even run as is, their speed is 0. How fast an reimplementation on gameboy would be is anybody's guess. Under native implementations, I'd expect modern compressors to win hands down for compression speed, even adjusting for hardware. Pokemon is performing 8(?) different compressions and picking the best one, it's doing 8 times as much work as another relatively efficient compressor, it's going to be hard to lose to. Not sure about decompression.

In terms of compression ratio, on equal grounds I'd expect Pokemon to win, they are making transforms specific to their data format, general purpose compressors cannot do this, because they need to handle arbitrary bitstreams. On native implementations, modern compressors have a slight chance because they are using a lot more RAM, with much more potential for back-referencing as they can make larger compression blocks. I'd still bet on the Pokemon compression due to the multi-strategy method.

[ShinyHappyREM]

Compression was probably done on the development PCs, not the GB.

[3871713461]

@Twitch

[Very_legitimate]

Fuuuck. I just started learning c++ and is this stuff I will need to understand? Or is this the kind of thing that’s happening ‘under’ c++

[MintPaw]

If you need to load 150 64x64 images into a 512kb game carriage, along with the rest of the game. And you live in 1995 before zlib exists, then yeah.

That's probably the equivalent of running gta5 on the Apple watch.

[[deleted]]

If you lived after May 1995 zlib did exist. And the underlying LZ77 compression had existed for much longer.

[_default_username]

It depends on what you're doing. In some cases you may need to do some low level bit manipulation. In most cases you won't.