Apple Opened Up Its LZFSE Compression Library

[phoronix]

Phoronix: Apple Opened Up Its LZFSE Compression Library

Apple has open-sourced LZFSE, a lossless compression algorithm used by iOS 9 and newer and being added with OS X 10.11...

http://www.phoronix.com/scan.php?page=news_item&px=Apple-Opens-LZFSE

[hernil]

But is it middle out?

[SystemCrasher]

There is already comparable tech in zstd, it performs well and comes from far more cooperative author, who develops things open from scratch, not just dumps some stuff when it fails to be somethnig groundbreaking and game-changing. Though it could be fun to benchmart their achieved ratio vs compression/decompression speeds, but not like if someone has gained something entirely new, etc. Zstd is interesting by the fact newest versions of lib could easily beat zlib in terms of ratio, with highest levels being closer to LZMA and Brotli domain, while decompression speed is even faster than zlib. So it is improvement, obviously. But I'm not sure why apple had to reinvent this wheel.

[starshipeleven]

Cool beans, I don't understand a damn thing of what I read in the article.

But is it middle out?

wat?

[starshipeleven]

But I'm not sure why apple had to reinvent this wheel.

This is asking for a joke.

[hernil]

wat?

http://spectrum.ieee.org/view-from-the-valley/computing/software/a-madefortv-compression-algorithm

tl;dr: It's a reference to the tv-show Silicon Valley

[nemequ]

There is already comparable tech in zstd, it performs well and comes from far more cooperative author, who develops things open from scratch, not just dumps some stuff when it fails to be somethnig groundbreaking and game-changing. Though it could be fun to benchmart their achieved ratio vs compression/decompression speeds, but not like if someone has gained something entirely new, etc. Zstd is interesting by the fact newest versions of lib could easily beat zlib in terms of ratio, with highest levels being closer to LZMA and Brotli domain, while decompression speed is even faster than zlib. So it is improvement, obviously. But I'm not sure why apple had to reinvent this wheel.

In all fairness, zstd wasn't very far along yet when Apple first released LZFSE (it's in iOS 9 and OS X 10.11), and who knows when they first started development. AFAIK zstd still hasn't even committed to a format (though they are very close now, the current format will be finalized provided no issues are found). Of course, it would have been nice if Apple had contributed to zstd or at least developed LZFSE in the open, but just using zstd wasn't feasible at the time…

zstd pretty much universally outperforms LZFSE; see https://quixdb.github.io/squash-benchmark/unstable/ (disclaimer: I wrote that). More interesting, though, is that libdeflate mostly outperforms LZFSE. Also, depending on compression level, so does Brotli. All told, I don't see much reason to use LZFSE.

LZFSE also contains LZVN, which is used for short inputs. The API for it isn't exposed publicly by Apple (there is support for it in Squash, though).

[wizard69]

Why why is it that every time Apples releases some open source code we get the very ignorant posts such as the one below.

There is already comparable tech in zstd, it performs well and comes from far more cooperative author, who develops things open from scratch,

Lots of code gets fleshed out in private before being released as open source, this is nothing new. In some cases it is the rational way to approach a project. The last thing we need is a world where every developer has to conform to some bodies ideal of open source practices.

not just dumps some stuff when it fails to be somethnig groundbreaking and game-changing.

It is a compression suite what in the hell do you expect?

Though it could be fun to benchmart their achieved ratio vs compression/decompression speeds, but not like if someone has gained something entirely new, etc.

So?

Zstd is interesting by the fact newest versions of lib could easily beat zlib in terms of ratio, with highest levels being closer to LZMA and Brotli domain, while decompression speed is even faster than zlib. So it is improvement, obviously.

Who really cares? Will Zstd have a long life span, be well supported or have a team that continues to support it into the future?

But I'm not sure why apple had to reinvent this wheel.

Why is the Zstd team reinventing the wheel? Seriously?

Think about this guy, if people didn't reinvent the wheel we wouldn't be seeing new programming languages floated out into the community. For that matter improvement programs like what we have seen with C++ wouldn't be happening. Hell if it wasn't for reinventing the wheel Windows 3.1 would still be with us. Come to think of it every Intel processor since the 8086 is a result of reinventing the wheel.

Reinvention on is what progress is all about. It is what standing on the shoulders of giants is all about.

Or or in short take your crappy attitude about Apple someplace else.

[unixfan2001]

But is it middle out?

Seconded.

What's the Weissman Score on that thing? Can it compress 3D video?

[DrYak]

Inall fairness, zstd wasn't very far along yet when Apple first released LZFSE (it's in iOS 9 and OS X 10.11), and who knows when they first started development.

The time monks know. I mean unless they have access to a time-machine there's no way they have start much recently.The whole approach stems from a new concept called Assymetical Numeric System by J. Duda.
With a first publication dating back in 2009 which was way to advanced fo its time.
Followed by a new pulication, a follow up to clarify, in 2013.
That's the one which managed to take the compression world by storm.

(Up until now, close-to-Shanon-limit entropy coderlike arithmetic coder or range coders, mostly work by subdividing a space into continuous zones for symbols.
(i.e.: if there are only two symbols with .5 probability, they each take up one half of the space)
ANS works by instead tweaking the frequency of distrbution.
(i.e.: in the above example, one symbol is at each even position the other at each odd position of the space)
It mostly works like reading a range coder with the bits swapped left-to-rigth)

That opens up a lot of new possibilities, while keeping the same close-to-Shanon-limit like classical entopy coders. E.g.: instead of relying on (somewhat) costly arithmetic operations (using arithmetic computations to compute the ranges), it's possible to rely on tables. So called tANS

This inspire a couple of developpers (among other, Ryg from Farbrausch) including Y. Collet of LZ4.

Based on tANS theoretical model, he designed FSE - Finite State Entropy coder. No arithmetics at all, just walking between a given series of look-up tables and shifting/keeping a remainder.
As usual for mot work by Y.Collet, FSE is close to best performance, while being incredibly frugal on ressources.

*THAT* is the FSE implementation that was subsequently re-use by several other project, including Apple's LZFSE.
(I also know that Xiph's Dalaa / IETF' NETVC1 / AOMedia's AV1 / whatever it's going to get called next also uses tANS technology at te entropy stage.
I just haven't closely followed if it's FSE or another implemenation, though FSE was touted around on their mailing list, back when it was still just Daala on Xiph's site, before Cisco and Google combined with Thor and VP10 respectively).

Now about full enryption algorithms: as stated above, LZ4 was another brainchild of Yann Collet.
This was designed to be as fast as possible with minimal ressources. Though it was very impressive (either blazingly fast in normal mode, or for tiny bit cost of time as close as possible to the format's maximum in 'hc' mode and much faster than similar compression ratio in GZIP) and even works on 8-bit computers, this is achieved by being a pure dictionnary Lempel-Ziv compressor without any entropy state.

After LZ4, Y.Collet moved to try to achieve something still very fast / very frugal, but with a bit of entropy coding. Initial development was called LzHuff (basically, a huffman coding straped on LZ4, because although it farther from the Shanon limit than range and entropy coding, it's much less ressource intensive, and better fits the "frugal" approach typical for his work).

That's when whole J.Duda's ANS and tANS publications broke out. Y.Collet developped the above mentionned FSE implementation , and now had the perfect entropy coding scheme for his plan: as close to shanon's limit as range and arithmetic are, but as fast as huffman (yet another way to look at FSE is that it's writing out code bitsequences like huffman, while keeping a "remainder" for what's left from the entropy).
So he swapped FSE for huffman and renamed LzHuff into Zstd. With the raised goal of being now somewhere between Gzip and LZMA, thanks to the newe entropy coding.

So Zstd is litterally born *right after* FSE (like, litterally. You can actually track the post no Y.Collet's blog when he finishes one and starts integrating it in the other).
And FSE is among the first implementation of tANS after J.Duda's papers.
(Again, you can follow most of the development on Y.Collet's blog. And simultaneously on Ryg's blog and yet another one if you're interested on the 2 other implementations of tANS).

There's absolutely no way Apple could have started LZFSE before Zstd. FSE didn't exist yet. And there was no other tANS implementation before either. All 3 appeared more orless at the same time.
(And for the record, each implementation is completely different and goes into another different direction. Such is the diversity spawn by J.Duda. If Apple has somewhat managed to start their own implementation behind closed door, chances are that it wouldn't have be FSE, but probably yet another beast).

Of course, it would have been nice if Apple had contributed to zstd or at least developed LZFSE in the open, but just using zstd wasn't feasible at the time…

Given that FSE has just been invented, LZFSE wouldn't have been any better at the beginning either.
Apple could have re-invented their own wheel, like they did apparently.
Or they could have contributed to Zstd to leverage a useful technology and incorporate it into their own ecosystem (like KHTML->Webkit, like Cups, like LLVM, etc.)