Show HN: misa77 - a codec that decodes 2x faster than LZ4 (at better ratios)

It's a somewhat known tradeoff, you can streamline and make the format friendlier to do memcpy which this library targets, the more memcpys you do, the faster it is overall to decode. On highly compressible data lz4, snappy become faster. Snappy on level 2 has faster decompression speed

But you have to pay the price that you need a slower encoding, because finding matches, putting restrictions on match lengths, putting things in different streams have costs you need to pay upfront.

Anyway good work, there is probably a need for that.

// Currently own Google's snappy and do compression at Google

P.S. if you want better snappy's results, compile with clang.

P.S.S you can optimize aarch64 speed by movemasks from shrn instruction. https://developer.arm.com/community/arm-community-blogs/b/se...

Compression is so tricky.

I got really into compression experimenting while I was developing my browser game.

I was trying to compress entire human gameplay matches into a QR code, for upto 60 minutes of gameplay both single player and multiplayer.

My game is a fast paced, grid based, snake x scrabble word game.

My first compression attempt was to do run length encoding and cardinal directions, encoded into 1 byte. This was really compressible data.

The best approach was to use relative direction changes instead of cardinal directions. Compressed even better as the raw data was more consistent (for the most part you are moving forward etc).

Some other attempts were: zone based encoding, double movement pattern encoding (much smaller raw data but less compressible), triple movement pattern encoding, interrupt encoding.

I am at a point where I can fit all 30 minute single player games into a QR code, some 60 minute games, and with a special encoding scheme I can fit 15 minute N player multiplayer matches in a QR code

For reference qr code max size is about ~3000 bytes

From status in readme in github:

- misa77's format may change unexpectedly as it's still v0.x.y.

- The decoder assumes that the input is a valid misa77 stream. Invalid input is UB and I offer no guarantees for whatever misa77 does in this case.

- It's been through some local fuzzing but is not hardened, so treat it as experimental.

So, I couldn't see it in the readme, apologies if I missed it but why?

It's a very significant speedup in decompression speed (albeit with a compression speed slowdown as a trade-off), but what's the insight that makes it faster? What was the idea or approach behind it?

Almost double the decompression speed, *and* a higher compression ratio than LZ4? That's very promising.

I don't see much in your README that talks about how a developer would integrate misa into their code. I might suggest some basic code samples to help a developer integrate misa decode into their project.

Congrats, looks like a cool project.

Nice results, I will keep a watch on this! Would be interesting to see benchmarks vs Oodle compression, I think the most similar one is Selkie?

Interesting, but if you are not robust to corrupted/malicious data, it is really in a different class of algorithm and it is hard to compare speeds directly.

From memory, 2505 MB/sec also sounds on the low side for LZ4 on a modern CPU?

> It offers particularly high decompression throughput on highly compressible files.

You know, you would expect that this is commonly observed. You'd expect, say, simple RLE (run length encoding) to be like this. It's more expensive to produce output requiring the processing of a large number of RLE opcodes that produce short sequences than one opcode that produces one long sequence.

this is super interesting! im excited to give this a look this afternoon, since I specifically have wanted faster throughout for decompressing maps in a game engine.

This looks awesome for boot firmware. How large is the decompressor code?

It is slower than LZ4 on AArch64.

how does it compare to macklin71?

so whats the actual use case for this ? streaming ? games?

What's the Weissman score?