We Shipped the Mathematics

Open any 1990s codec and you find tables. Step sizes, quantiser levels, windows, twiddle factors, codebooks: thousands of numbers sitting in the binary, doing the real work. For a decoder they’re the easy part. Copy them across and you’re halfway there.

We decided not to do that, or at least not without a fight. Disk Phoenix, which is in development, is a commercial product, and we preferred not to ship other people’s numbers in it. A table lifted out of someone else’s binary is a big block of their work sitting in ours. It’s also a block we can’t explain, test or reason about, beyond “that’s what was there”.

So the rule became: if a table has mathematics behind it, find the mathematics and ship that. If it doesn’t, carry the table, label it as a fact of the format, and say so in writing.

This was one of the longest and most expensive parts of building Disk Phoenix. It was also the most satisfying.

Six numbers instead of 1,536

MACE was Apple’s audio compression for the Sound Manager, and plenty of classic QuickTime soundtracks use it. Inside Macintosh gives you the packet sizes and nothing about how it works. The decoder needs two quantiser tables, 1,536 values in all.

They look like noise until you notice that the second half of each row mirrors the first. That leaves 768 values. Each row is a step size multiplied by a handful of levels, and the step sizes rise smoothly over eight octaves. So there was clearly a rule. Fitting one turned out to be miserable.

For hours, nothing fitted. We concluded, wrongly, that no closed form existed, and said so. A second attempt, with fresh assumptions, found it. The first search had made two mistakes:

• it assumed the codec rounds, when it truncates;
• it looked for a single formula, when the table is built in two quantisation stages: an integer-rounded ladder, then a truncating multiply.

Keep the ladder as real numbers and every column fails. No single-stage fit could ever have worked.

1,536 values, or six numbers

Apple’s tables: 1,536 values

Abstract cells, not real values

→ mirror symmetry 768

What Disk Phoenix ships

Here’s what Disk Phoenix ships:

• The ladder, rising from 2⁷ to 2¹⁵ over 128 rows:
  $$L_r=\mathrm{round}(128·{256}^{r/127}),r=0,1,\dots ,127$$
• The levels: six fitted numbers, two for 2-bit codes and four for 3-bit codes:
  $$\begin{array}{ccc}{\mathrm{\lambda }}_{\text{2-bit}}& \in & \{0.50708,1.69116\}\hfill \\ {\mathrm{\lambda }}_{\text{3-bit}}& \in & \{0.294187,0.907221,1.61279,2.58252\}\hfill \end{array}$$
• The entries: ladder times level, truncated and capped at 32,767, with the upper half of each row the mirror of the lower:
  $$T_{r,c}=\min (32767,\lfloor L_r·{\mathrm{\lambda }}_c\rfloor )$$
  $$\text{and the mirror}{T}_{r,n-1-i}=-(T_{r,i}+1)$$

The six levels turn out to have exactly the shape of Joel Max’s 1960 optimal quantiser for a Gaussian signal. Scale Max’s levels by one constant per table, about 1.12 for the 2-bit codes and 1.20 for the 3-bit, and they agree to within 0.02%. We haven’t found a rule for those two constants, so the six stay fitted numbers. Even so, what our source carries is a published design principle and six numbers, not 1,536 values from Apple. Six small step-adaptation integers are still carried as transcribed facts, and they’re labelled that way.

Our acceptance test feeds in 3,072 bytes of packets we wrote ourselves, sized so that every one of the 768 derived entries is exercised. At 1,024 bytes, five entries went untouched, and a wrong derivation hiding in one of them would have passed.

The lesson cost us an afternoon and we’ve never forgotten it: a failed curve fit is weak evidence. Before declaring a search dead, check whether you ever varied its assumptions.

A palette is a recipe

Apple Animation movies at 8 bits refer to the standard System palette, 256 colours that every classic Mac knew by heart. We could have shipped 768 bytes of RGB.

But the palette is a recipe: a 6×6×6 colour cube, four ramps of ten steps (red, green, blue and grey), and black moved to the last slot. Disk Phoenix generates it, and 75,000 decoded pixels agree exactly with a reference decoder. The 256 colours every Mac knew by heart fit on an index card.

QDesign Music: the long one

QDesign Music was the high-quality audio codec of late-1990s QuickTime, and it’s why a lot of classic movies export silent from modern tools. The “mission impossible” of our commercial Phoenix apps, which are still in development, is to open, render and play long-forgotten classic Macintosh file formats on modern macOS. So silence where a movie should have sound was a very loud alarm bell for us. The gloves were off.

The QDesign Music codec was never documented. The second version, QDM2, took 53 working sessions to bring up. The first version, QDMC, is a separate decoder in a separate binary, and it was most of a second bring-up.

The method throughout was the one from Reverse Engineering, With Receipts: trace yes, transcribe no. We ran QDesign’s own decoder in an emulated Power Mac, watched what it computed, and wrote our own decoder to compute the same thing. Wherever a table turned up, the question was the same: is this data, or is it a rule?

Most of the time it was a rule:

• the sine table is $s_n=\sin (2\mathrm{\pi }n/512)$;
• the envelope is a raised cosine;
• the amplitude ladders are two seeds doubled an octave at a time, with a √2 step at the head;
• an offset table grows by a power of two that doubles every four steps, $t_0=0,t_{i+1}=t_i+2^{\lfloor i/4\rfloor }$;
• the band map is octave widths: 8, 8, 16, 32, 64 and 128 subbands;
• in QDMC, the bit-reversal tables, bit masks and FFT twiddle factors are exactly what their names say. All 156 and 324 twiddle values match bit for bit.

Each of these is computed when Disk Phoenix runs, and a test re-derives every one on every run, so “this is a closed form” is checked rather than asserted.

QDMC had a near miss worth telling. Its amplitude ladder looked like $1.1875·2^{k/2}$, which is close and elegant, and wrong by up to 2.6 parts in a thousand. The true rule is two 32-bit floating-point seeds and exact doubling, and that’s bit-exact. A formula that’s nearly right is still the wrong formula.

16,096 numbers from 32 experiments

The biggest piece was QDM2’s synthesis filterbank: a single routine, 1,155 machine instructions long, carefully scheduled for the PowerPC. Porting it by hand was the largest transcription risk left in the whole decoder, and transcribing it was exactly what we didn’t want to do.

Then we noticed it’s linear. A linear system is completely described by what it does to a single impulse. So we ran QDesign’s own code 32 times, each time on a unit impulse in a different position, and recorded the outputs.

Identify, don’t port

1. 1 1,155-instruction routine QDesign’s code, run in an emulated Power Mac. A closed box: we fed it inputs and read its outputs.
2. →
3. 2 32 unit impulses in, 32 responses out Three of the 32 runs shown
4. ↓
5. 3 One formula
   $$H[k][d][j]=D[32d+j]·\cos ((16+j+32(dmod2))(2k+1)\mathrm{\pi }/64)$$
   16,096 non-trivial coefficients rel. error 1.6 × 10⁻⁷

The formula defines 16,384 coefficients. Leaving aside the 288 that are trivially zero, one expression reproduced all 16,096 of the rest to a relative error of 1.6 × 10⁻⁷:

Five other candidate models scored between 1.005 and 1.451 on the same measure, so the test could tell a right model from a wrong one. And the answer was a familiar one: the textbook MPEG-1 polyphase synthesis filterbank, at a scale of exactly 1.0. Its 512-tap window, D, isn’t QDesign’s at all. It’s Table 3-B.3 of the published MPEG-1 Audio standard, ISO/IEC 11172-3, and we ship it from the standard’s own printed values.

So the routine we were most afraid of porting became a citation and one line of trigonometry. The full QDM2 output agrees with Apple’s own decoder to −132 dB.

Where the table is the format

Now the honest part. Not every table has mathematics behind it, and in some places the hunt for a generator ended with a proof that there isn’t one.

Huffman counts. Neither QDesign codec stores its Huffman codes at all. Each time a stream opens, the decoder builds its code trees from tables of symbol frequencies. Those frequencies almost certainly came from training on QDesign’s own music, which, as far as we know, no longer exists. Any generator would need that corpus as its input. So the counts aren’t hiding a formula: they are the format. QDM2 carries twelve of its twenty-one tables, and QDMC carries six, four of them identical to QDM2’s.

QDM2’s spreading kernel. It’s 320 values with visible structure: palindromic rows, and a 16/27 ratio between neighbouring taps in most rows. But no closed form reproduces all of them, so it’s carried as it is, and labelled. The same goes for QDMC’s band edges and a handful of noise-envelope ramps whose start and end points are a table, not a rule.

Sorenson Video. SVQ1 decodes using 23,040 bytes of vector codebooks that Sorenson’s encoder baked into every stream it ever wrote. They are almost certainly trained, and we found no rule behind them. We traced them to their home: a single resource in Apple’s QuickTime PowerPlug extension, laid out largest first, in an order that turned out to be four-by-four quadrants. Disk Phoenix carries those codebooks, and a test rebuilds every one of them from that resource on every run, so the record of where they came from is checked rather than remembered.

That’s the line we drew. A formula we found is ours. A table with no rule behind it is a fact of the format, and the decoder can’t work without it. We carry it with its origin written next to it, and we say so here, rather than let “we shipped mathematics” stand for more than it does.

Formula, standard, or format

• Derived computed from a rule
• Published standard from a cited standard
• Transcribed a fact of the format

MACE

ladder levels entries step-adaptation integers (6)

System palette

the 256 colours

QDM2

sine envelope amplitude ladders offset ladder band map synthesis window (ISO/IEC 11172-3) Huffman counts spreading kernel band-edge reflection noise-envelope ramps

QDMC

amplitude ladder sine tone window offset ladder bit masks bit reversal twiddles Huffman counts band edges geometry selector

SVQ1

codebooks (23,040 bytes)

A chip is a name, not a size: it doesn’t show how many values or bytes each table holds.

What it bought us

Shipping formulas wasn’t only about whose numbers sit in our product. Formulas turned out to be better engineering.

A formula explains itself. When a decoded sample was wrong, a derived table told us what was supposed to be there and why. A transcribed table could only say “that’s what was there”. Every derived table is re-derived on every test run, so a typo in a derivation fails loudly. A typo in a block of copied numbers can sit quietly for years.

And the search kept finding published work underneath supposedly proprietary codecs: the shape of Max’s 1960 quantiser inside MACE, and the MPEG-1 filterbank and its standard window inside QDesign.

The tables looked like secrets. Much of the time they were well-known mathematics.

What isn’t done

QDM2 refuses the 128 kb/s stream types rather than guess at them. It also refuses frames carrying two subpacket types that no movie we hold contains: we checked every QDM2 track across our disk images, 32 sound descriptions and 24,691 frames, and found none. A refusal names what it can’t do. The tables above with no rule behind them stay tables, because there’s nothing else they can be.

Everything here comes from the codec work in Disk Phoenix, which is in development. Every number above comes from our own measurements, or from the publication we cite for it.