lz4_flex 0.7.2 reaches parity with cpp reference implementation on speed and ratio

Speed Comparison:

https://github.com/PSeitz/lz4_flex#results-v072-18-01-2021-safe-decode-and-safe-encode-off

Changes Improving Compression Speed:

Improve Compression Ratio:

24 comments · 96% upvoted · other discussions

comments

Shnatsel

Following this change count_same_bytes is unsound - it offsets the pointer by the value of candidate without any bounds checks, which may result in out-of-bounds access.

At present this function should be marked an unsafe fn, since it's up to the caller to validate that the offset passed to this function is in bounds. For more info on the contracts a function not marked unsafe fn has to uphold, see the Rustonomicon.

vlmutolo

How do you go about finding all these bugs

Shnatsel

I tend to rg unsafe and go from there, or even type unsafe in github search box.

In this case I looked up the commit message because I was curious how they sped that up, and realized they don't actually validate the value before adding it to the pointer.

https://doc.rust-lang.org/nomicon/ is a good resource for understanding what kind of unsafe code is OK and what isn't.

Fuzzing is also helpful for larger or more complex codebases.

Pascalius [OP]

In this case candidate is a pointer into input and can never be out-of-bounds.

The issue currently is, if I mark the function as unsafe, the caller needs to wrap the call with unsafe. There is a normalization layer between safe code and unsafe code, where the call looks the same. So instead:

let duplicate_length = count_same_bytes(input, candidate as usize + MINMATCH, &mut cur);

I would need:

let mut duplicate_length = 0;
#[cfg(not(feature = "safe-encode"))]
{
    duplicate_length = unsafe{count_same_bytes(input, candidate as usize + MINMATCH, &mut cur)};
}
#[cfg(feature = "safe-encode")]
{
    duplicate_length = count_same_bytes(input, candidate as usize + MINMATCH, &mut cur);
}

Which seems pretty verbose. In that case it probably would make sense to split the unsafe and safe version in two seperate files. As I understand it this is an api convention to signal the programmer unsafe code and does not cause UB itself, by missing it.

[deleted]

As I understand it this is an api convention to signal the programmer unsafe code and does not cause UB itself, by missing it.

For private APIs, practically yes. However, it is still considered good style to mark even those functions as unsafe if they rely on a safety invariant that has to be upheld by the caller.

Lej77

I'm not saying you should but you could have a macro like:

#[cfg(not(feature = "safe-encode"))]
macro_rules! maybe_unsafe {
    ($inner:expr) => {
        unsafe { $inner }
    };
}
#[cfg(feature = "safe-encode")]
macro_rules! maybe_unsafe {
    ($inner:expr) => {
        { $inner }
    };
}

that would allow you to write it as:

let duplicate_length = maybe_unsafe!(count_same_bytes(input, candidate as usize + MINMATCH, &mut cur));

Note that currently rustfmt will format code inside macros that are invoked with parenthesis ( (not brackets [ or {), so formatting should still work.

Plasma_000

I think it boils down to “should private unsafe functions be marked as such even if they can’t be used unsafy by the public API” - which I don’t think there is a consensus on...

I would err on the side of marking unsafe just because a future dev might work on the project and use the function in an unsound way.

Shnatsel

The Nomicon explicitly states:

No matter what, Safe Rust can't cause Undefined Behavior.

It does not make a distinction between public and private.

backtickbot

Fixed formatting.

Hello, Pascalius: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

You can opt out by replying with backtickopt6 to this comment.

coolreader18

Nice work! It's impressive how consistently this library's been improving :)

Something I've been wondering though, does non-safe decode/encode have any sort of buffer overflow issues due to not checking input? Or is it purely if a user of the crate doesn't trust that you wrote the unsafe implementation correctly, they can opt out of using it?

Pascalius [OP]

Thanks :)

Non-safe encode should have not any buffer overflow issues. Any input should be safe.

For non-safe decode, if you don't trust your input, you should use the checked-decode feature flag. If the data is corrupted, it could be that the expected decompressed output size is incorrect. Without checked-decode an out of bounds write could occur, because the unsafe version assumes the pre-allocated vector has the correct size.

A1oso

if you don't trust your input

You should never trust your input.

If you aren't confident that the unsafe version is correct, please consider adding a disclaimer to the README.

You might already know this, but you can use cargo-fuzz, valgrind and miri to detect some problems.

Pascalius [OP]

You should never trust your input.

That's generally correct, but if you have a checksum you should be able trust your input. (Or in rare cases, where the data is not coming from an external source). I could add a checksum, but the convention, if the block format is used on its own (without frames) is to prepend the size of the output followed but its compressed data. So it would be not compatible anymore.

If you aren't confident that the unsafe version is correct, please consider adding a disclaimer to the README.

The default is currently that everything is safe, and checked-decode is already documented to avoid out-of-bounds checks, but only in the rust docs and not in the README. I'll update it.

You might already know this, but you can use cargo-fuzz, valgrind and miri to detect some problems.

Yes, I'm already using cargo-fuzz and miri, really awesome tools. Fuzzing is currenlty used for compression/decompression roundtrips. I should also add fuzz tests to generate corrupted data.

Icarium-Lifestealer

I don't see how checksums matter here, since they're just as untrusted as the compressed data.

Pascalius [OP]

If you consider internal data that is not coming from the user, the data could be corrupted, but the checksum would avoid memory corruption in your application.

For data coming from the user, the checksum cannot be trusted, because it is an attack vector.

Ar-Curunir

checksums (unless they're a cryptographic hash) are not secure against adversarial input.

Icarium-Lifestealer

Without checked-decode an out of bounds write could occur

Does that mean that your public API is marked as unsafe when not using checked-decode?

Pascalius [OP]

Currently not, I should change this

Icarium-Lifestealer

If you really want to offer this, I'd use a separate public function, instead of changing the behaviour of the existing function.

zSync1

I'm using LZ4 for data compression in my WebAssembly games, so it's really exciting that the compression ratio might be better with this implementation.

soontorap

It seems to be the compression ratio of the fast mode.

If you are cooking your game data before sending it to your users, you are likely using a more asymetric solution, LZ4_HC, which is likely providing a _way_ better compression ratio already.

fulmicoton

That's awesome!

soontorap

The comparison is apparently done with `lz4_cpp`.

Which version are you using ? Is that the reference implementation at github.com/lz4/lz4 ?

In which case, note that it's using `C90` (pure C) coding convention, not C++.

Pascalius [OP]

I'm using lz4-rs, which uses 1.8.1.

It's hard to tell, how much since the latest lz4 1.9 has been improved, because the (benchmarks)[https://github.com/lz4/lz4/commit/31763c59fca9a38bc697cd37f591d6ba385f7614#diff-b335630551682c19a781afebcf4d07bf978fb1f8ac04c6bf87428ed5106870f5] are executed with different processors

I'm currently improving decompression speeds, it should be up to 20% faster in the next version.