LZ77 compression prehistory

LZ77 is a widely-used class of data compression algorithms. I'll start with a quick overview of it. Assuming you're compressing a stream of bytes (a "file"), your LZ77 compressed data, at a high level, would contain two possible kinds of instructions for the decompressor: Emit literal: {byte value=A}Copy from history: {match-offset=B, match-length=C} The match-offset may …

An obscure polyglot file: LHA/CAR

LHA is a compressed archive file format and compression utility that was, for a long time, a competitor of ZIP. It's also known as LZH format, or LHarc format, but I'll call it LHA. In the course of researching it, I came across an obscure lookalike format created by a program named CAR. CAR is …

Earth portrait photos

This is a pretty good photograph: … Though it's so ridiculously overused and cliché that it surprises me that graphic designers, etc., still seem to like using it. Maybe we've been so thoroughly conditioned by it that other photographs of the Earth just don't look like we think the Earth is supposed to look. If …

Alternative to Cantor’s diagonalization argument

How does one prove that there are more real numbers than integers? There are an infinite number of each, but the infinity of the real numbers is, in a strict sense, larger than the infinity of the integers. In math terminology, the set of reals has a larger cardinality. Roughly speaking, it's equivalent to saying …

Thoughts on timestamps of computer files

Computer files can have a number of different kinds of timestamps. Some of them are stored in the file's external metadata, alongside the file's name -- I'll call these external timestamps. Others are stored inside the file itself -- I'll call these internal timestamps. I use the term "timestamp" loosely. When something called a "timestamp" …

Win32 I/O character encoding supplement 1 – A Cygwin issue

A while back, I wrote a series of posts about using Unicode in Windows console mode programs: Part 1Part 2Part 3 In Part 2, I said that programmers should probably not be changing the console code page to UTF-8 (65001). And that if they must, they should change it back when they're done. But now …

The recent discovery of an ancient bilaterian fossil

In March 2020, researchers in Australia announced the discovery of a 555 million-year-old fossil of a bilaterian animal, which they named Ikaria wariootia. The way that journalists presented this discovery made it clear that it is significant for… something. But it seemed to be difficult for them to pin down precisely what is significant about …

The World Chess Championship is kinda not so great

As I write this, the chess Candidates Tournament is still expected to be held as scheduled, starting March 17, 2020, in Yekaterinburg, Russia. The tournament is between eight of the top chess players who aren't currently the World Champion. The winner of the tournament will earn the right to play a match against the current …

PKZIP Implode bug #3

I've already written about two PKZIP bugs related to the "Implode" compression method. Now I've come across another one, so I guess I'll investigate it as well. Here are the first two: Bug #1 (MML)Bug #2 (v1.01 literal tree issue) There's an old collection of files called the Pier 1 Shareware CDROM (#1). On it …

Notes on WinHelp format, part 3

This post is part of a series about WinHelp file format. Please read the other parts first: Part 1Part 2 With what we learned previously, we can decompress the TOPIC blocks, locate the TOPICLINKs, and stitch each TOPICLINK's fragments together to make each TOPICLINK a contiguous blob of bytes: A defragmented TOPICLINK is composed of …