Archive for August 26, 2016

Friday, August 26, 2016

The Elegance of Deflate

Richard Mitton (via Hacker News):

Deflate was invented by Phil Katz back in 1993, and forms the basis of the ZIP file format, the zlib library, gzip, PNGs, and probably a whole bunch of other stuff. At the time it was pretty cutting-edge.


So we have two compression algorithms. LZSS is reliant on finding previous data to match against, and Huffman coding is reliant on some letters being more common than others. Can we do better than picking one of those two? Can we weave them together?


Deflate is based around the idea of the unified alphabet. If an alphabet is just a set of choices, why not bring all the choices together under one umbrella? Deflate’s alphabet consists of 286 symbols. The first 256 are the ASCII codes for each letter, including all the ASCII control codes and other such. The remaining 30 symbols are used to represent lengths. That’s right, we’re storing the actual match length here.


There were a lot of encoders at the time using this general scheme (a few more values to indicate match length or distances). PKZIP won at the time because it was faster, and PK had the name recognition from his PKARC, which was a superfast implementation of SEA ARC (the dominant archiver on PCs at the time).


There’s another non-trivial thing that PKZIP had going for it - it put the directory at the end, which meant you could see the list of files in the archive without reading the entire archive! This sounds simple, but back then everyone adopted the tar-style “file header then data” appendable style, which meant that just listing the files inside a 300KB zip file (almost a whole floppy disk!) meant reading that entire floppy (30 seconds at least). PKZIP could do it in about 2 seconds.

Five Years of Tim Cook’s Apple in Charts

Jan Dawson (via John Gruber):

R&D spend was under $2.5 billion the four quarters before Tim Cook took over, but it was almost $10 billion five years later, a roughly fourfold increase. And that’s not just because Apple’s revenue has grown during that time — R&D has actually grown significantly as a percentage of revenue over the same period, going from just over 2% to just over 4%, or almost doubling as a percentage. That’s interesting, because R&D actually fell fairly consistently as a percentage of revenue during most of Steve Jobs’ second stint as Apple CEO, from a peak of 8% in 2001 and 2002 all the way down to 2% just before Cook took over. That’s largely a function of the massive iPod- and iPhone-driven revenue growth during that period — dollar R&D spend rose from around $400 million a year to over $2 billion a year during the same time period — but it’s interesting to note that Cook has reversed the trend and significantly increased R&D spend even above and beyond the rate at which revenue has grown. Interestingly, that 2 percentage point increase in R&D spend is roughly equal to the 2 percentage point drop in margins during the Tim Cook era.


Apple ended calendar Q2 2011 with a total balance of cash and investments of $76 billion, while it ended Q2 2016 with a balance of $231.5 billion. In other words, it has added over $155 billion to its coffers over this time. Meanwhile, an increasing proportion of this cash and investments has been held overseas — the percentage was 63% five years ago, but was 93% at the end of Q2 2016.

They are actually selling bonds (paying around 4% interest) here in order to finance the dividends and buybacks without using the overseas cash.

Perhaps one of the most significant contributions Tim Cook has made at Apple can’t be seen in any of these charts, because it’s about the changes to Apple’s culture that have happened under his leadership. The increased openness, best exemplified by the frequent interviews Cook and other executives now regularly grant to various publications (and even podcasters), is one element of this, though Apple’s secrecy about future products remains as tight as ever. But an increased sense of social responsibility, especially as regards the environment and contributions to social causes is another major change.

Keystroke Recognition Using Wi-Fi Signals

Kamran Ali et al. (PDF, via Paul Fenwick, Hacker News):

In this paper, we show for the first time that WiFi signals can also be exploited to recognize keystrokes. The intuition is that while typing a certain key, the hands and fingers of a user move in a unique formation and direction and thus generate a unique pattern in the time-series of Channel State Information (CSI) values, which we call CSI-waveform for that key. In this paper, we propose a WiFi signal based keystroke recognition system called WiKey. WiKey consists of two Commercial Off-The-Shelf (COTS) WiFi devices, a sender (such as a router) and a receiver (such as a laptop). The sender continuously emits signals and the receiver continuously receives signals. When a human subject types on a keyboard, WiKey recognizes the typed keys based on how the CSI values at the WiFi signal receiver end. We implemented the WiKey system using a TP-Link TL-WR1043ND WiFi router and a Lenovo X200 laptop. WiKey achieves more than 97.5% detection rate for detecting the keystroke and 96.4% recognition accuracy for classifying single keys. In real-world experiments, WiKey can recognize keystrokes in a continuously typed sentence with an accuracy of 93.5%.

Update (2016-08-30): See also: Bruce Schneier.

Whatever Happened to the Hurd?

Gavin Thomas (2012) (via Hacker News):

Richard Stallman had announced his intention to write a complete UNIX-like operating system to be known as GNU, ‘GNU’s Not Unix!’, in September 1983. The years between 1983 and the inception of the Hurd were spent writing the operating system and tools that made the development of a kernel possible, the editors and compilers, Bash, Make, Autoconf, Emacs, GCC, sed, gawk and the command-line tools.


From a user perspective, the Hurd was going to be a long time coming, and the Linux developers had slotted Linux into the space that was meant to be occupied by the Hurd at the heart of the GNU operating system. Stallman was initially [skeptical]. Early versions of Linux were exclusive to the IBM 386, and according to Stallman: “We heard that Linux was not at all portable (this may not be true today, but that’s what we heard then). And we heard that Linux was architecturally on a par with the UNIX kernel; our work was leading to something much more powerful.”


Stallman later admitted, “I take full responsibility for the technical decision to develop the GNU kernel based on Mach, a decision which seems to have been responsible for the slowness of the development. I thought using Mach would speed the work by saving us a large part of the job, but I was wrong.” In latter years the Hurd has been ported to a variety of microkernels, from L4 to Coyotos and to Viengoos, but has never had the community and resources that went the way of Linux.