Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

31–40 of 51 posts

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

#31

Post by cogman10 »

wolf550e wrote: post #12

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.

- Excellent of the author to call these things out.

- All 3 things are show stoppers for any real use.

An unstable format which trusts input is a CVE and data loss magnet.

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

#32

Post by nonadhocproblem »

edflsafoiewq wrote: post #30
nonadhocproblem wrote: post #20

Earlier quoted context omitted.

So it's essentially "LZ4 unshackled". I've made several modifications to the LZ4 format, most of which are in service of eliminating branches/making them more predictable, and making decompression very friendly to out-of-order cores by hiding false data dependencies behind a rarely taken branch (similar to this: https://news.ycombinator.com/item?id=48889148 ). Some concrete changes in the format are: - match length p…

What's the advantage of the separate streams? That presumably prevents a streaming encoder/decoder.

Yes, that prevents streaming for now.

What is the advantage of this? Out-of-order execution (see my decoder's hot loop: https://github.com/welcome-to-the-sunny-side/misa77/blob/3a9...).

In particular, on even moderately compressible data most blocks take the following form:

  - 1 token byte + 2 distance bytes 
  - a somewhat unpredictable number of literal bytes
If these streams are interleaved, then it's harder for the out-of-order core to process the token bytes of several blocks in advance (as the position of the next token byte depends on the unpredictable number of literal bytes in the current block). However, if you separate them (all token bytes in a prefix, and literal bytes in a suffix), the CPU can speculatively parse token bytes of a lot of blocks in advance (as most of the time, it just has to step forward by three bytes to go to the next block's token byte).

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

#33

Post by vardump »

cogman10 wrote: post #31
wolf550e wrote: post #12

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.

- Excellent of the author to call these things out. - All 3 things are show stoppers for any real use. An unstable format which trusts input is a CVE and data loss magnet.

That is a bit too harsh. Not all applications require those guarantees. It’s fine if you can trust the inputs.

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

#34

Post by nonadhocproblem »

cogman10 wrote: post #31
wolf550e wrote: post #12

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.

- Excellent of the author to call these things out. - All 3 things are show stoppers for any real use. An unstable format which trusts input is a CVE and data loss magnet.

I'll be resolving issues 2 and 3 in the next couple of weeks (adding a safe decoder and doing a lot of fuzzing).

The format, however, might continue to change for some time because I want to push performance even further.

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

#35

Post by purple-leafy »

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

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

#36

Post by cogman10 »

nonadhocproblem wrote: post #34
cogman10 wrote: post #31

Earlier quoted context omitted.

- Excellent of the author to call these things out. - All 3 things are show stoppers for any real use. An unstable format which trusts input is a CVE and data loss magnet.

I'll be resolving issues 2 and 3 in the next couple of weeks (adding a safe decoder and doing a lot of fuzzing). The format, however, might continue to change for some time because I want to push performance even further.

Which is great and please don't take this as me being critical of the approach you are taking. I think it's perfectly reasonable during early development have your compressed stream in flux.

I've been bitten in the past with other libs that weren't as explicit about their stability.

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

#38

Post by monster_truck »

vardump wrote: post #33
cogman10 wrote: post #31

Earlier quoted context omitted.

- Excellent of the author to call these things out. - All 3 things are show stoppers for any real use. An unstable format which trusts input is a CVE and data loss magnet.

That is a bit too harsh. Not all applications require those guarantees. It’s fine if you can trust the inputs.

The inputs can never be trusted

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

#40

Post by derf_ »

nonadhocproblem wrote: post #32
edflsafoiewq wrote: post #30

Earlier quoted context omitted.

What's the advantage of the separate streams? That presumably prevents a streaming encoder/decoder.

Yes, that prevents streaming for now. What is the advantage of this? Out-of-order execution (see my decoder's hot loop: https://github.com/welcome-to-the-sunny-side/misa77/blob/3a9... ). In particular, on even moderately compressible data most blocks take the following form: - 1 token byte + 2 distance bytes - a somewhat unpredictable number of literal bytes If these streams are interleaved, then it's harder for the…

I used the same "separate stream" design (one of them coded backwards from the end, to eliminate the need to send a separate offset) when working on video compression, to separate out arithmetic-coded bits from literal bits. It's a good idea. The only reason it isn't in AV1 is because hardware wanted to do DRM decryption in order.
Post reply on HN