If you want to see some crazy C code, check out this file from the GitHub repo: https://github.com/lzfse/lzfse/blob/master/src/lzvn_encode_b...
I wonder why they use goto statements instead of just returning q1 like the statement evaluates to.
Apple Open-Sources its Compression Algorithm LZFSE
31–40 of 219 posts
Re: Apple Open-Sources its Compression Algorithm LZFSE
#32It's 2016. How can you launch a reasonably high profile open source project with code that looks like this? This fulfills all the TODO list for unreadable code. One character variable names, one character parameter names, full of magic numbers... Yes. This is very performance critical code and I completely see the need to write very optimized code. That's fine. But optimizing code for speed shouldn't imply also optim…
> To release compression code in a non-safe language is risky enough
At the moment, what's their real alternative? Rust is the only memory-safe language I can think of that could hope to meet their performance requirements, but even the Rust runtime would be a lot of overhead for this application.
That said, I agree this isn't acceptable C code for something that runs on untrusted data while using tons of pointer arithmetic.
Re: Apple Open-Sources its Compression Algorithm LZFSE
#33Earlier quoted context omitted.
Excerpt from the link : if (D == D_prev) { if (L == 0) { *q++ = 0xF0 + (x + 3); // XM! } else { *q++ = (L >8 in 0..5 *q++ = (D >> 8) + (L = (1 34) { // Long dist *q++ = (L > 2) + (L
Blows my mind that people can come up with this stuff. I'm assuming they came up with the mathematical proofs first and translated that into code, so that has something to do with it, correct? It looks a lot like some crypto algorithms which are a nearly direct translation of the mathematical formulas. It's not that it's incredibly difficult to follow, but it's just very "math like".
That is my experience. Maths people are not renowned for their ability to write readable or maintainable code.
I recently needed an implementation of the Simplex Noise algorithm (that I could port to Common Lisp). I ended up using this one, which works but the code certainly does nothing to help understanding: https://github.com/josephg/noisejs/blob/master/perlin.js
Note that the Javscript implementation is also a port from another language (whose implementation I have failed to find).
Re: Apple Open-Sources its Compression Algorithm LZFSE
#34It's 2016. How can you launch a reasonably high profile open source project with code that looks like this? This fulfills all the TODO list for unreadable code. One character variable names, one character parameter names, full of magic numbers... Yes. This is very performance critical code and I completely see the need to write very optimized code. That's fine. But optimizing code for speed shouldn't imply also optim…
> To release compression code in a non-safe language is risky enough At the moment, what's their real alternative? Rust is the only memory-safe language I can think of that could hope to meet their performance requirements, but even the Rust runtime would be a lot of overhead for this application. That said, I agree this isn't acceptable C code for something that runs on untrusted data while using tons of pointer ari…
You're right about C. C in general, I would find acceptable, because, yes, there aren't that many good alternatives around for this kind of code.
But there's nothing stopping you from writing readable C code. That's where my concerns come from.
Re: Apple Open-Sources its Compression Algorithm LZFSE
#35Earlier quoted context omitted.
> To release compression code in a non-safe language is risky enough At the moment, what's their real alternative? Rust is the only memory-safe language I can think of that could hope to meet their performance requirements, but even the Rust runtime would be a lot of overhead for this application. That said, I agree this isn't acceptable C code for something that runs on untrusted data while using tons of pointer ari…
You're right about C. C in general, I would find acceptable, because, yes, there aren't that many good alternatives around for this kind of code. But there's nothing stopping you from writing readable C code. That's where my concerns come from.
[deleted]
Re: Apple Open-Sources its Compression Algorithm LZFSE
#36If you want to see some crazy C code, check out this file from the GitHub repo: https://github.com/lzfse/lzfse/blob/master/src/lzvn_encode_b...
Excerpt from the link : if (D == D_prev) { if (L == 0) { *q++ = 0xF0 + (x + 3); // XM! } else { *q++ = (L >8 in 0..5 *q++ = (D >> 8) + (L = (1 34) { // Long dist *q++ = (L > 2) + (L
It's code like this that has an exploit several years in the future given an edge case that is hard to fathom
Re: Apple Open-Sources its Compression Algorithm LZFSE
#37If you want to see some crazy C code, check out this file from the GitHub repo: https://github.com/lzfse/lzfse/blob/master/src/lzvn_encode_b...
Excerpt from the link : if (D == D_prev) { if (L == 0) { *q++ = 0xF0 + (x + 3); // XM! } else { *q++ = (L >8 in 0..5 *q++ = (D >> 8) + (L = (1 34) { // Long dist *q++ = (L > 2) + (L
I've never seen this code base before, but this makes straightforward sense to me as I do keep my hand in with compression software, and I don't anticipate others who works with compression algorithms in general would have any trouble.
It looks just like the style of code in all the other fast LZ codebases. They are all in this style.
The "non-aligned access OK" comment litter is presumably to silence an LLVM performance sanitizer.
Re: Apple Open-Sources its Compression Algorithm LZFSE
#38Re: Apple Open-Sources its Compression Algorithm LZFSE
#39Earlier quoted context omitted.
Basically an Apple-specific reimplementation of Zstd: https://github.com/Cyan4973/zstd
So, worse than LZ4 for what Apple seems to be using it for. Why didn't they just use LZ4? Confusing company, they are.
From the infoq article https://www.infoq.com/news/2016/07/apple-lzfse-lossless-open... that contains much more detail and is linked to by the original submitted link.
"Admittedly, LZFSE does not aim to be the best or fastest algorithm out there. In fact, Apple states that LZ4 is faster than LZFSE while LZMA provides a higher compression ratio, albeit at the cost of being an order of magnitude slower than other options available in Apple SDKs. LZFSE is Apple’s suggested option when compression and speed are more or less equally important and you want reduce energy consumption."
https://developer.apple.com/library/ios/documentation/Perfor... has a section titled "Choice of Compression Algorithm"
Re: Apple Open-Sources its Compression Algorithm LZFSE
#40Earlier quoted context omitted.
Basically an Apple-specific reimplementation of Zstd: https://github.com/Cyan4973/zstd
So, worse than LZ4 for what Apple seems to be using it for. Why didn't they just use LZ4? Confusing company, they are.
It's not worse than LZ4. LZ4 is just an LZ-based compression (find common strings, reference them), while LZFSE does both LZ compression and entropy coding (like ZIP's deflate). It's comparable to zstd, which uses LZ and finite state entropy coder. They achieve better compression at lower (than just LZ-based compressor) speed. You can say they replace zlib, achieving much higher performance at pretty much the same compression ratio.
Apple's libcompression also provides LZ4 if you need it: https://developer.apple.com/library/ios/documentation/Perfor...