# Matthew van Eerde's web log

• #### Finding the longest substring which occurs twice in a given string

I'm reading Jon Bentley's Programming Pearls and one of the interesting exercises was to find the longest substring which occurs twice in a given string of length n.

There's a naïve solution where you look at every pair of (distinct) indexes (i, j), and calculate the length of the common prefix of the substrings starting at those locations; this is O(n2) assuming that the length of the eventual maximum substring is O(1) (that is, << n.)

Jon shows that there is an O(n log n) algorithm, which is a significant savings if n is large (e.g., War and Peace.)  This involves building an array of all substrings, then sorting them lexically, then walking the sorted array; the trick is that now we only need to check pairs of indexes that correspond to adjacent entries in the array.  That step can be done in O(n) time; the O(n log n) comes from the sorting step.

I wrote up a quick app that implements his suggested algorithm.  Source follows.

// main.cpp

#include <windows.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <search.h>

#define LOG(format, ...) wprintf(format L"\n", __VA_ARGS__)

template<typename T>
class DeleteArrayOnExit {
public:
DeleteArrayOnExit(T *p) : m_p(p), m_canceled(false) {}
~DeleteArrayOnExit() { if (!m_canceled) { delete [] m_p; } }
void Cancel() { m_canceled = true; }
void Swap(T *p) { m_p = p; }
private:
T *m_p;
bool m_canceled;
};

// caller must delete [] the buffer when done with it
int __cdecl pwcscmp(const void *pstra, const void *pstrb) {
return wcscmp(*(LPWSTR*)pstra, *(LPWSTR*)pstrb);
}

// returns length of longest common substring
// don't include the null terminator if both strings are identical
// e.g., comlen(banana, bananas) == comlen(banana, banana) == 6
int comlen(LPCWSTR a, LPCWSTR b) {
int i = 0;

// keep going while the strings are the same and not ended
while (a[i] && (a[i] == b[i])) { i++; }

return i;
}

int _cdecl wmain() {
if (nullptr == text) {
return -__LINE__;
}
DeleteArrayOnExit<WCHAR> deleteText(text);

size_t size = wcslen(text) + 1;
LPWSTR *suffixes = new LPWSTR[size];
if (nullptr == suffixes) {
LOG(L"Could not allocate memory for suffixes");
return -__LINE__;
}
DeleteArrayOnExit<LPWSTR> deleteSuffixes(suffixes);

for (size_t i = 0; i < size; i++) {
suffixes[i] = &text[i];
}

qsort(suffixes, size, sizeof(LPWSTR), pwcscmp);

// find the longest common adjacent pair
LPWSTR szMax = suffixes[0];
size_t lenMax = 0;
for (size_t i = 0; i < size - 1; i++) {
size_t len = comlen(suffixes[i], suffixes[i + 1]);
if (len > lenMax) {
lenMax = len;
szMax = suffixes[i];
}
}

WCHAR *substring = new WCHAR[lenMax + 1];
if (nullptr == substring) {
LOG(L"Could not allocate memory for substring");
return -__LINE__;
}
DeleteArrayOnExit<WCHAR> deleteSubstring(substring);
if (0 != wcsncpy_s(substring, lenMax + 1, szMax, lenMax)) {
LOG(L"wcsncpy_s failed");
return -__LINE__;
}
substring[lenMax] = L'\0';

// intentionally not using LOG to avoid trailing newline
wprintf(L"%s", substring);

return 0;
}

WCHAR *text = new WCHAR[1];
if (nullptr == text) {
LOG(L"Could not allocate memory for text");
return nullptr;
}
DeleteArrayOnExit<WCHAR> deleteText(text);
text[0] = L'\0';

// read a 2 KB chunk
const size_t buffer_size = 1024;
WCHAR *buffer = new WCHAR[buffer_size];
if (nullptr == buffer) {
LOG(L"Could not allocate memory for buffer");
return nullptr;
}
DeleteArrayOnExit<WCHAR> deleteBuffer(buffer);

bool done = false;
do {
if (fgetws(buffer, buffer_size, stdin)) {
size_t size = wcslen(text) + wcslen(buffer) + 1;
WCHAR *new_text = new WCHAR[size];
if (nullptr == new_text) {
LOG(L"Could not allocate memory for new text");
return nullptr;
}
DeleteArrayOnExit<WCHAR> deleteNewText(new_text);

WCHAR *dest = new_text;

if (0 != wcscpy_s(dest, size, text)) {
LOG(L"wcscpy_s failed");
return nullptr;
}
dest += wcslen(text);
size -= wcslen(text);

if (0 != wcscpy_s(dest, size, buffer)) {
LOG(L"wcscpy_s failed");
return nullptr;
}

// that should do it for copying
// now swap new_text => text

delete [] text;
text = new_text;

deleteText.Swap(new_text);
deleteNewText.Cancel();

} else if (feof(stdin)) {
done = true;
} else {
return nullptr;
}
} while (!done);

deleteText.Cancel();
return text;
}

• #### Car Talk puzzler analysis - Limerick equation

Car Talk's puzzler of the week has some mathematical interest. See Car Talk's transcript of the question.

In brief, we are given the equation...

(12 + 144 + 20 + 3√4) / 7 + 5(11) = 92 + 0

(which holds true, by the way)
... and asked to transcribe it as a limerick.

The last line of the limeric is given: "Is nine squared, and not a bit more."

The answer, ROT13'd for your convenience until the Car Talk folks reveal it:

N qbmra, n tebff, naq n fpber
Cyhf guerr gvzrf gur fdhner ebbg bs sbhe
Qvivqrq ol frira
Cyhf svir gvzrf ryrira
Is nine squared, and not a bit more.

This is not the only equation to be immortalized in a limerick. There's also this old chestnut. It relies on pronouncing the letter z as "zee" (rather than "zed",) as well as reading "log base e" (usually spelled "ln") for "log".

The integral z2 dz
From one to the cube root of three
All times the cosine
Of three pi over nine
Equals log of the cube root of e.

This equation also holds true.

There's also this classic from Lewis Carroll which waxes a bit philosophical:

Yet what mean all such gaieties to me
Whose life is full of indices and surds
x2 + 7x + 53
= 11/3.

Perhaps fittingly, this last equation has only imaginary solutions.

• #### Nitpicking Sam Loyd - a wheel within a wheel

In August 1878 Sam Loyd published this mate in two and dedicated it to a friend of his named Wheeler:

Mate in two; Black to move and mate in two; Selfmate in two; Black to move and selfmate in two

While the mates appear to stand up, the problem position is not legal. White has three a-pawns; this implies at least three Black pieces were captured by a White pawn. But Black has fifteen pieces on the board; only one is missing!

Looking at Black pawn captures - the b2-, c-, and d- pawns together account for three pawn captures. This seems OK at first glance since White has three pieces missing. But all the missing White pieces are pawns, and they are from the right half of the board... so they must have promoted. This implies more pawn captures to either get the Black pawns out of the way or to get the White pawns around them. (The promoted pieces could have been captured by the Black pawns, or the original pieces could have been captured in which case the promoted pieces are on the board now.)

Finally, the h-pawns on h5 and h6 could not have got into their present position without at least one pawn capture by White, or at least two pawn captures by Black.

• #### Anand vs. Gelfand world chess championship 2012 oldest pair of contenders since 1886

In 2012, World Chess Champion Viswanathan Anand will attempt to defend his title aqainst challenger Boris Gelfand. This is a very unusual match in that both players are fairly old by World Chess Champion contender standards. I decided to see just how unusual it was, and do so with some degree of rigor.

One tricky bit is that chess championships (usually) have (at least) two players, so we have to define an age metric for pairs of people. Creating a well-ordering on tuples is sometimes controversial. I chose to have the comparison routine be:
age(contenders) = min(age(contender) : contender ∈ contenders)
which is to say, the age of the youngest contender.

Another tricky bit was deciding which matches were definitively "world chess championship matches." I pulled the list of world chess championship matches from chessgames.com. For time periods where the organizational ownership of the title is in question, this includes matches sponsored by all contending organizations.

As a naïve first pass, I looked up the birth years for all the contenders and subtracted that from the year of the championship to get an estimated age. This could be off by a year if the youngest contender's birthday comes after (or during?) the match. Nevertheless, this was accurate enough to give me a short list of matches to investigate further:.

Closer investigation of each of the highlighted matches revealed that, astonishingly, in every case the youngest contender's birthday came after the match:

• 2012 Viswanathan Anand (43?) vs. Boris Gelfand: Anand's birthday (December 11) comes after the match (starts in May) so he will still be 42.
• 1993 Anatoly Karpov (42?) vs. Jan Timman (42?): Timman's birthday (December 14) came after the match (finished November 1) so he was still 41.
• 1934 Alexander Alekhine (42?) vs. Efim Bogolyubov: Alekhine's birthday (October 31) came after the match (April to June) so he was still 41.
• 1910 Emanuel Lasker (42?) vs. Dawid Janowski (42?): Janowski was born May 25; Lasker December 24. Lasker's birthday came after the match (finished December 8) so he was still 41.
• 1892 Wilhelm Steinitz vs. Mikhail Chigorin (42?): Chigorin's birthday November 12 (October 31 old style) came after the match (finished February 28) so he was still 41.
• 1886 Wilhelm Steinitz vs. Johannes Zukertort (44?): Zukertort's birthday (September 7) came after the match (finished March 29) so he was still 43.

We conclude that Anand vs. Gelfand (2012) features the oldest contenders since the very first World Chess Championship Steinitz vs. Zukertort (1886) - and is within a year of even that! If the 2014 championship is a rematch, it will set the record.

1 Topalov was the clear winner of the 2005 FIDE World Championship Tournament so there was no need for a runoff.

• #### Rotating a matrix redux

As Vincent Tan points out, there is no way to create an n x n matrix R such that RA is a rotated version of A - for example, in the 2 x 2 case:

There is no 2 x 2 matrix R such that
`R [ a b ] = [ b a ]  [ c d ]   [ c d ]`

Vincent Tan points out that such an R would entail hidden assumptions but asks for a simpler proof.

Here it is.  I'll go back to the n by n case, assuming n >= 2.  (The 0 x 0 case and the 1 x 1 case are actually trivially solvable using the identity matrix.)

Assume there is such a matrix R = (rij)i,j∈{1...n} which has the property that RA = B = (bij)i,j∈{1...n} is the rotated version of A for any n x n matrix A = (aij)i,j∈{1...n}.

To see that this is impossible, consider the matrix with a 1 in the upper-left-hand corner and zeros everywhere else; that is, a1,1 = 1, and aij = 0 for all other combinations of i and j.

To be the rotated version of this matrix, B should have bn1 = 1 and bij = 0 for all other combinations of i and j.  (My coordinates are such that bn1 is the number in the top right corner of the matrix.)

But how did that 1 get in the top right hand corner?  The rules of matrix multiplication imply that bn1 = r1,1an1 + r2,1an2 + ... + rn1ann. At first blush, this looks fine... until we realize that bn1 is 1, and all of the anj are 0... so we have the contradiction

1 = r1,10 + r2,10 + ... + rn10 = 0

QED.

But this is not how rotation matrices are applied.  Rotation matrices R are not applied as RA = B; instead, they're applied as RAR-1 = B.  Not that this helps our hapless interviewee; the operation being asked of him ("rotate a matrix") can't be done by a rotation matrix anyway.  That is, there is no magic matrix R that works under this operation either.

EDIT: A simple way to prove that RAR-1 = B doesn't work either (for n >= 2) is to think about what happens when you choose A to be the identity matrix I (the matrix with 1's on the main diagonal [i = j] and 0's everywhere else.)

RIR-1 = RR-1 = I; and for n >= 2, I is not its own "rotation."

We therefore arrive at the paradoxical result that you can't rotate a matrix via matrix rotation.

• #### Spot the Bug - IMFOutputSchema

I found a simple but nasty bug the other day in this implementation of the IMFOutputSchema interface.

The symptoms: running this code outside of a debugger caused the app to crash.  Running it under a debugger (to catch the crash) caused the app to run clean.

// outputschema.h
HRESULT CreateTrustedAudioDriversOutputSchema(
DWORD dwConfigData,
GUID guidOriginatorID,
IMFOutputSchema **ppMFOutputSchema
);

// outputschema.cpp
// ... various include files removed ...
// CMFAttributesImpl implements the IMFAttributes interface, minus the IUnknown methods
class CTrustedAudioDriversOutputSchema : public CMFAttributesImpl<IMFOutputSchema> {

friend
HRESULT CreateTrustedAudioDriversOutputSchema(
DWORD dwConfigData,
GUID guidOriginatorID,
IMFOutputSchema **ppMFOutputSchema
);

private:
CTrustedAudioDriversOutputSchema(DWORD dwConfigData, GUID guidOriginatorID);
~CTrustedAudioDriversOutputSchema();

ULONG m_cRefCount;
DWORD m_dwConfigData;
GUID m_guidOriginatorID;

public:
// IUnknown methods
HRESULT STDMETHODCALLTYPE QueryInterface(
/* [in] */ REFIID riid,
/* [out] */ LPVOID *ppvObject
);
ULONG STDMETHODCALLTYPE Release();

// IMFOutputSchema methods
HRESULT STDMETHODCALLTYPE GetConfigurationData(__out DWORD *pdwVal);
HRESULT STDMETHODCALLTYPE GetOriginatorID(__out GUID *pguidOriginatorID);
HRESULT STDMETHODCALLTYPE GetSchemaType(__out GUID *pguidSchemaType);

}; // CTrustedAudioDriversOutputSchema

HRESULT CreateTrustedAudioDriversOutputSchema(
DWORD dwConfigData,
GUID guidOriginatorID,
IMFOutputSchema **ppMFOutputSchema
) {
if (NULL == ppMFOutputSchema) {
return E_POINTER;
}

*ppMFOutputSchema = NULL;

CTrustedAudioDriversOutputSchema *pSchema =
new CTrustedAudioDriversOutputSchema(dwConfigData, guidOriginatorID);

if (NULL == pSchema) {
LOG(eError, _T("new CTrustedAudioDriversOutputSchema returned a NULL pointer"));
return E_OUTOFMEMORY;
}

*ppMFOutputSchema = static_cast<IMFOutputSchema *>(pSchema);

return S_OK;
} // CreateTrustedAudioDriversOutputSchema

// constructor
CTrustedAudioDriversOutputSchema::CTrustedAudioDriversOutputSchema(
DWORD dwConfigData, GUID guidOriginatorID
)
: m_dwConfigData(dwConfigData)
, m_guidOriginatorID(guidOriginatorID)
{}

// destructor
CTrustedAudioDriversOutputSchema::~CTrustedAudioDriversOutputSchema() {}

#define RETURN_INTERFACE(T, iid, ppOut) \
if (IsEqualIID(__uuidof(T), (iid))) { \
*(ppOut) = static_cast<T *>(this); \
return S_OK; \
} else {} (void)0

// IUnknown::QueryInterface
HRESULT STDMETHODCALLTYPE
CTrustedAudioDriversOutputSchema::QueryInterface(
/* [in] */ REFIID riid,
/* [out] */ LPVOID *ppvObject
) {

if (NULL == ppvObject) {
return E_POINTER;
}

*ppvObject = NULL;

RETURN_INTERFACE(IUnknown, riid, ppvObject);
RETURN_INTERFACE(IMFAttributes, riid, ppvObject);
RETURN_INTERFACE(IMFOutputSchema, riid, ppvObject);

return E_NOINTERFACE;
}

ULONG STDMETHODCALLTYPE

ULONG uNewRefCount = InterlockedIncrement(&m_cRefCount);

return uNewRefCount;
}

// IUnknown::Release
ULONG STDMETHODCALLTYPE
CTrustedAudioDriversOutputSchema::Release() {

ULONG uNewRefCount = InterlockedDecrement(&m_cRefCount);

if (0 == uNewRefCount) {
delete this;
}

return uNewRefCount;
}

// IMFOutputSchema::GetConfigurationData
HRESULT STDMETHODCALLTYPE
CTrustedAudioDriversOutputSchema::GetConfigurationData(__out DWORD *pdwVal) {

LOG(eInfo1, _T("IMFOutputSchema::GetConfigurationData called"));

if (NULL == pdwVal) { return E_POINTER; }

*pdwVal = m_dwConfigData;

return S_OK;
}

// IMFOutputSchema::GetOriginatorID
HRESULT STDMETHODCALLTYPE
CTrustedAudioDriversOutputSchema::GetOriginatorID(__out GUID *pguidOriginatorID) {

LOG(eInfo1, _T("IMFOutputSchema::GetOriginatorID called"));

if (NULL == pguidOriginatorID) { return E_POINTER; }

*pguidOriginatorID = m_guidOriginatorID;

return S_OK;
}

// IMFOutputSchema::GetSchemaType
HRESULT STDMETHODCALLTYPE
CTrustedAudioDriversOutputSchema::GetSchemaType(__out GUID *pguidSchemaType) {

LOG(eInfo1, _T("IMFOutputSchema::GetSchemaType called"));

if (NULL == pguidSchemaType) { return E_POINTER; }

*pguidSchemaType = MFPROTECTION_TRUSTEDAUDIODRIVERS;

return S_OK;
}

• #### Blown movie lines - Casablanca

Ah... Casablanca.

Arguably the best movie of all time.  And yet a blown line?  How could I be so bold?

The line:

Play it [As Time Goes By] again, Sam. -- Casablanca

Wow... that line, blown?  Am I way off base here?  Arguably the best line of arguably the best movie... blown?  How so?

Well, for two reasons.

1. The line does not actually appear in the movie at all.

There are two scenes where Sam is urged to play As Time Goes By to recall the Paris romance between the two major characters.  Here is the dialog from both scenes:

Ilsa: Play it once, Sam. For old times' sake.
Sam: I don't know what you mean, Miss Ilsa.
Ilsa: Play it, Sam. Play "As Time Goes By."

... and later...

Rick: You played it for her, you can play it for me!
Sam: Well, I don't think I can remember...
Rick: If she can stand it, I can! Play it!

"Play it again, Sam" has thus entered the pantheon of unforgettable movie lines... even though it was never actually said.

2. The song was nearly changed.

The film composer - a fellow named Max Steiner - did a very good job on the film.  As Time Goes By is, thanks to his score, now indelibly etched in the ears of many a classic movie buff.

But he hated the song!  He attempted to convince the producers of the film that the song was boring, and that he could write a much better song.

Shame, Mr. Steiner.  Shame.

What's worse... the producers went along with it! They agreed to allow him to write a song to replace As Time Goes By.  There were only a couple of scenes that needed to be reshot, and they started the logistical machinery to recall the cast in those scenes to do the reshooting.

Unfortunately... or rather, fortunately... Ingrid Bergman had already moved on to For Whom The Bell Tolls... and she had cut her hair...

The topic of this arguably-best-line of the arguably-best-movie was thus saved by a haircut.

• #### Basic audio volume theory

Last time we talked about the different Windows Audio Session APIs for setting volume. Let's talk a little about what volume means.

For purposes of illustration, let's take our signal to be a full-scale square wave:

Incidentally, the answer to the exercise

completely characterize the set of digital signals that achieve 0 dB FS intensity. If you have, say, 1000 samples of mono 16-bit integer audio to play with, how many distinct signals achieve 0 dB FS intensity?

is "all signals with N/2 samples having value 1 and N/2 samples having value -1". There are

such signals. For N = 1000 this is comes out to about 2.7e299.

## Linear in amplitude

If we multiply the signal by a number between 0 and 1, we reduce the volume. That's the first natural volume scale - the "linear in amplitude" scale. 0 is silence, 1 is an unchanged signal, and 1/2 is a signal with all the amplitudes divided by 2.

## Linear in power

Recalling the formula for the intensity of a signal, we realize that the power (intensity squared) of a signal depends on the square of the magnitude. This leads us to the second natural volume scale - the "linear in power" scale. 0 is still silence, and 1 is still an unchanged signal, but now 1/2 maps to a signal with half of the power of the original signal. In particular, a full-scale square wave with power 1 would drop to a square wave with power 1/2 - this has amplitude sqrt(1/2) which is significantly more than 1/2.

## Linear in dB

So far so good. However, sound is perceived in a relative fashion. Humans are not very good at determining absolute volume, but are very good at determining relative volume. If I play a sound and ask you "what is the dB SPL of the sound I just played", you would have trouble answering; but if I played two sounds and asked "which sound was louder", you would be able to tell me. You would even be able to give me an estimate such as "it's about twice as loud".

So a natural scale for volume is based on relative power - that is, a logarithmic scale dB = 10 * log10( PA / P0 ) where PA is the attenuated signal and P0 is the original. That looks something like this:

Note that the relative power scale has no bottom! It's turtles all the way down.

So how do you map an infinite volume scale onto a finite slider, while preserving the nice property that equal distances map to equal power ratios?

• #### Windows audio render volume settings, from local to global

Windows has four different volume settings for any given piece of audio; they are all applied simultaneously. For example, if one of these settings is muted, you will not hear the audio, even if the others are turned up to "full". Here they are, from local to global:

## Stream volume

The WASAPI API for this is IAudioStreamVolume.

This most local volume control is used only in rather specialized situations. If a particular app wants to play multiple audio streams to the same audio device, and in the same session (see below), but wants to control the volumes for the streams independently, this is the volume control to use. For example:

• A media playback app might want to cross fade songs n and n + 1 in a playlist; it could do this by playing the songs in different streams, gradually bringing the volume for song n down to zero, while simultaneously bringing the volume for song n + 1 up to full.
• A game might offer distinct volume controls for:
• The background music in the game
• The sound effects (gunshots, explosions, and so on)
• Voice chat in the game
The first two would likely be in the same session and would thus use stream volume controls (exposed via the game UI - Windows does not offer UI for stream volume.) The third could very well be a different session, and even use a different device - the background music and sound effects might go to the default console device (e.g., speakers) while the voice chat might go to the default communications device (e.g., a headset.)

Apps could also get these same effects by doing their own mixing and volume handling, and playing a single stream to the Windows audio engine, of course.

## Session volume

By and large, this is the volume control that apps most commonly use. The WASAPI APIs for this are ISimpleAudioVolume and the more-rarely used IChannelAudioVolume.

This is what people mean when they say "application volume" - a session is, by and large, an app (though there are exceptions in both directions.) This is the "S" in "WASAPI" - Windows Audio Session API.

The session volume shows up in the Volume Mixer - each "Application" slider is a session volume control. This is also usually (but not always) tied to a volume control in the app.

## Endpoint volume

The WASAPI API for this is IAudioEndpointVolume. Apps should generally prefer ISimpleAudioVolume to this because IAudioEndpointVolume will affect all apps on the system.

This is what people mean when they say "system volume." It is exposed in the following three places in the UI. Note if you have multiple audio devices, each has its own setting.

## Ducking

When you get a phone call or start a voice chat, Windows (starting in Windows 7) will attenuate (or "duck") all of the audio on the system (except for phone calls and voice chats.) This is the "most global" because it affects all streams on all audio devices. Note that this volume control only has three settings (four if you count "mute".)

Larry Osterman did a series of audio volume posts - one of them contains much of the information in this post, though the ducking feature was added after his post.

• #### Spot the bug - Outlook "block sender" icon, solution

Last week I posed the question, what's wrong with this Outlook icon?

The answer is simple - the slash in the "no" icon goes the wrong way.

My personal keystone for this is a street sign in a certain panel of The Calculus Affair, but the direction of the slash is part of ISO-3864: top-left to bottom-right.

Perhaps a better mnemonic is to think of the word "NO":

 = +

The Outlook team isn't the only one to get this wrong, though:

• #### Newton: combining celestial and terrestrial mechanics

For as long as there have been humans, we have looked at the skies - and around us on Earth as well.  Things move in the skies; things move on Earth.  The way things move in the skies is called "celestial mechanics"; the way things move on Earth is called "terrestrial mechanics."

The ancient Greeks thought there were five elements, corresponding to the five regular (Platonic) solids: the four terrestrial elements (air, fire, earth, and water) and the fifth celestial element which the Romans called quintessence.

All kinds of rules were discovered/proposed for how things move on Earth.  Galileo demonstrated that falling objects accelerate at the same rate regardless of their mass.  Similar rules were discovered/proposed for how things move in the heavens.  Kepler demonstrated that the planets move in ellipses around the sun, that they swept out equal areas in equal times, etc.  But everybody knew that things in the heavens were different than they were on Earth.

Then Newton, building on Hooke, came up with the crazy idea that perhaps things fall on Earth for the same reason that heavenly objects go in ellipses... that all objects, celestial or terrestrial, act on each other from a distance in a uniform fashion.  (He himself wrote that this was such a crazy idea that no-one should take it seriously.)

That one body may act upon another at a distance through a vacuum without the mediation of anything else, by and through which their action and force may be conveyed from one another, is to me so great an absurdity that, I believe, no man who has in philosophic matters a competent faculty of thinking could ever fall into it. -- Isaac Newton

But he had done some calculations and it seemed to work out... specifically, he worked out how much acceleration you would expect the Earth to exert on an object as far away as the Moon, and how much acceleration the Moon would need to stay in its orbit (and not wander off or spiral down into the Earth.)

I... compared the force requisite to keep the moon in her orb with the force of gravity at the surface of the earth and found them to answer pretty nearly. -- Isaac Newton

Note Newton's use of the word "orb" to describe the motion of the moon, a direct reference to celestial mechanics.

Let's see how compelling those calculations were, shall we?

His first idea was that there was this thing called "force" which was equal to the mass of an object multiplied by the acceleration it was undergoing.  F = m a.  Fine.

His second idea (which he stole, at least partially, from Hooke) was that any two objects have a force that attracts them, which is proportional to both of their masses, and inversely proportional to the square of the distance between them (that's the part he stole from Hooke.)  F = G m1 m2 / r2.  Fine.

His third idea was that an object that goes around a circle of radius r at a constant speed v is undergoing a constant centripetal acceleration of a = v2 / rThis follows pretty quickly from the definitions with a little geometry, trigonometry, and a dash of calculus.  Fine.

He also knew some facts.  I'm going to state them in metric because, hey, this is the twenty-first century.  He knew:

• The distance from the center of the Earth to the surface (where the apple trees are) is 3,960 miles: 6370 km.
• Falling objects on the surface of the Earth accelerate at 32.2 ft/s2: 9.81 m/s2.
• The distance from the center of the Earth to the center of the Moon is 239,000 miles: 384,000 km.
• The Moon takes 27.3 days to make a single sidereal orbit around the Earth: 236,000 s.

Coarse estimate time...

If the Moon is roughly 50 times further away from the center of the Earth than an apple is, and "gravitational" acceleration is inversely proportional to the square of the distance between two objects, then the Moon should be accelerated roughly 1/2500th as much as the apple is: 0.004 m/s2 instead of 10 m/s2,

More precisely...

Consider the apple case (mE is the mass of the Earth, mA the mass of the apple:)

FA = mA aA = G mE mA / rA2
a
A rA2 = G mE
9.81 m/s2 (6.37e6 m)2 = G mE
G
mE = 3.98e14 m3/s2

Now consider the moon case:

FM = mM aM = G mE mM / rM2
aM = G mE / rM2
aM = 3.98e14 m3/s2 / (3.84e5 m)2
aM = 0.00269 m/s2

So Newton's proposed formula predicts that the Earth's gravity causes the Moon to accelerate at 0.00269 m/s2.  This is, indeed, roughly 0.004 m/s2 so it jives with our coarse estimate.

Let's see how that compares to the necessary centripetal acceleration to achieve a closed orbit: a = v2 / r.

The distance the moon travels in its sidereal orbit is 2π * 3.84e5 m = 2.42e9 m, and it does so in 27.3 days; so its velocity is 2π * 3.84e5 m / (27.3 days * 24 (hours / day) * 60 (minutes / hour) * 60 (s / minute)) = 1020 m/s.  This is roughly Mach 3 in our atmosphere.

The centripetal acceleration is thus measured to be (1020 m/s)2 / 3.84e8 m = 0.00273 m/s2. Newton's prediction is about 1.5% off, which isn't bad, considering.

Note that although Newton knew the value of the product G mE, he didn't know either G or mE seperately.  It wasn't until Cavendish took two known masses and measured the gravitational pull between them directly that G was evaluated; we could then calculate the mass of the earth as G mE / G.

Once G was known we could also evaluate the mass of the Sun based on Earth's orbit.  However, we still could not determine the mass of the Moon... in fact, back in the 1950s, American scientists were unable to determine the mass of Sputnik (which would have been very helpful) even though we could see its orbit.

Which raises the question... how did we know the mass of the Moon?

• #### Nitpicking László Polgár's Chess: ... #1071

I was reading László Polgár's excellent book Chess: 5334 Problems, Combinations, and Games and ran across #1071, White to move and mate in 2:

The purported solution is...

1. ♘xf6+ ♚xf6
2. ♕f7#

... which, indeed, works - and there is no other mate in two that I can see - so why blog this?

Because there's a mate in one.

• #### Forcing Windows to install on a single partition

If you're installing Windows via a boot DVD, and you choose Custom, you have the option to rearrange partitions.  I like use this to have each drive be one big partition.

Windows 7 wants to set aside a 100 MB partition for something-or-other.  I'm sure there's a very good reason for this but I am too lazy to look up the team that owns this space and ask them what it is.

So I'm in the "Where do you want to install Windows?" stage, I've gone into "advanced drive setup", and I've deleted all the partitions.  Fine.  I then create a partition that fills the drive, and I get this popup:

Install Windows
To ensure that all Windows features work correctly, Windows might create additional partitions for system files.
OK | Cancel

After letting Windows finish installing, I jump into diskpart.exe and sure enough, Windows has created an additional partition.  A small one, to be sure... but an additional partition (horrors!)

Not being one to let Windows push me around, I decided to experiment, and came up with the following dance to allow me to just have one big partition thankyouverymuch:

1. Boot from the Windows DVD
3. Go into Drive options (advanced)
4. Delete all partitions on the drive
5. Create a new partition - you will get the prompt above
6. Click OK
7. There will now be two partitions - a small (System) one and a large (Primary) one.
8. Delete the large one.
9. Extend the new one to fill the drive.
10. Install Windows.
11. Open Windows Explorer
12. Right-click the C: drive | Properties
13. Delete the "System Reserved" partition name
Et voilà, Windows installs perfectly happily on the single partition (confirmed with diskpart.exe post-installation.)
• #### How to turn on HDCP or SCMS in an audio playback app

There's an MSDN sample of how to turn on HDCP or SCMS in a playback app.  The sample is loosely based on a test app I wrote, but there are still some rough edges.  For example, the CMFAttributeImpl<T> template is not part of the SDK or the DDK.  Also, there's a leak in the GetDigitalAudioEndpoint implementation.  (Using the private template was my bug.  The leak was someone else's.)

Exercise: find the leak.

There are also rough edges in the test app.  For one thing, it doesn't play audio - the way to use the app is to

1. Start playing audio using your favorite audio playback application, to the digital output on which want to turn on HDCP or SCMS.
2. Run the trustedaudiodrivers2.exe command line to do what you want it to.

Source and binaries (x86 and amd64) attached.

>trustedaudiodrivers2
trustedaudiodrivers2 --list-devices

trustedaudiodrivers2
--device [ communications | console | multimedia | <device-name>]
--copy-ok [ 0 | 1 ]
--digital-output-disable [ 0 | 1 ]
--test-certificate-enable [ 0 | 1 ]
--drm-level <drm-level>

--list-devices: displays a list of output devices.

Sets a Trusted Audio Drivers 2 output policy on a given audio endpoint.
--device
communications: set policy on default communications render endpoint.
console: set policy on default console render endpoint.
multimedia: set policy on default multimedia render endpoint.
<device-name>: set policy on the endpoint with this long name.
--copy-ok: 1 or 0. Set to 0 to turn on "copy protection" (SCMS or HDCP)
--digital-output-disable: 1 or 0. Set to 1 to disable output (or turn on HDCP.) --test-certificate-enable: 1 or 0. Set to 1 to allow the test certificate.
--drm-level: set to a number. 1100 is a good default.

Here's a sample command line which should disable the digital out (or enable HDCP, if the driver supports it.)  This is line-wrapped for readability only.

>trustedaudiodrivers2.exe
--device "Acer H213H (High Definition Audio Device)"
--copy-ok 1
--digital-output-disable 1
--test-certificate-enable 1
--drm-level 1300

If all goes well the output should look something like this:

Output Trust Authorities on this endpoint: 2
Processing Output Trust Authority #1 of 2
OTA action is PEACTION_PLAY (1)
GetOriginatorID() called
GetOriginatorID() called
GenerateRequiredSchemas() called
dwAttributes: MFOUTPUTATTRIBUTE_DIGITAL (0x00000001)
guidOutputSubType: MFCONNECTOR_HDMI ({57CD596D-CE47-11D9-92DB-000BDB28FF98})
cProtectionSchemasSupported: 1
MFPROTECTION_TRUSTEDAUDIODRIVERS ({65BDF3D2-0168-4816-A533-55D47B027101})
MFPROTECTION_TRUSTEDAUDIODRIVERS supported.
IMFOutputSchema::GetSchemaType called
IMFOutputSchema::GetConfigurationData called
IMFOutputTrustAuthority::SetPolicy returned 0x00000000
Processing Output Trust Authority #2 of 2
OTA action is PEACTION_EXTRACT (4)
Skipping as the OTA action is not PEACTION_PLAY
Policy successfully applied.  Press any key to release IMFTrustedOutput...

At that point I pressed a key, which redacted the policy, and the music started playing again.

Common causes of failures:

1. No audio is playing to that device.  Setting protection requires an active audio stream.
2. The audio device is not S/PDIF or HDMI.
3. The audio driver is not capable of enforcing the protection.
4. The audio driver is test-signed only; try --test-certificate-enable 1
5. Kernel debugging is enabled.
6. Driver verifier is enabled.

This source should compile with just publically available headers and no special voodoo on the part of the developer.

EDIT: 11/13/2009 10:05 AM

A subtle problem was called to my attention.  This line triggers an ATL ASSERT:

hr = pMFOutputTrustAuthority->SetPolicy(&pMFOutputPolicy, 1, &pbTicket, &cbTicket);

The ASSERT is in CComPtr<IMFOutputPolicy>::operator& which ASSERTs if the pointer CComPtr<IMFOutputPolicy>::p is not NULL.

My first instinct was to bypass the assertion like this:

hr = pMFOutputTrustAuthority->SetPolicy(&pMFOutputPolicy.p, 1, &pbTicket, &cbTicket);

But ASSERTs are there for a reason.  The fundamental problem here is that I'm trying to be too clever.

Despite its name, IMFOutputTrustAuthority::SetPolicy takes, not an IMFOutputPolicy *, but an array of IMFOutputPolicy *s.  A little confusing, yes.  As this is effectively a sample, I should be emphasizing this behavior, not covering it up.

So here's the fix I decided on.  Updated source and binaries attached.

// we're only setting a single policy but the API allows setting multiple policies
// (like WaitForMultipleObjects)
IMFOutputPolicy *rMFOutputPolicies[1] = { pMFOutputPolicy };
hr = pMFOutputTrustAuthority->SetPolicy(
rMFOutputPolicies,
ARRAYSIZE(rMFOutputPolicies),
&pbTicket,
&cbTicket
);

EDIT September 28 2015: moved source to https://github.com/mvaneerde/blog/tree/master/trustedaudiodrivers2

• #### Interview question: baby boys and baby girls

Source:

In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

• #### Solution: baby boys and baby girls

Last week I posed an interview question about the ratio of baby boys to girls in a hypothetical country.

In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

The correct conclusion is "probably pretty close to 50-50," but the path to the conclusion is far more interesting and important than the conclusion itself.

This question interests me (though I would never use it as an interview question) because there are many ways to get the answer.  There are many different kinds of assumptions that are entailed by the problem statement, and the mathematical rigor of the solution can vary tremendously.

First, check out Business Insider's answer, which is perfectly adequate.  The approach is to solve the more specific problem "... when there are 10 families, and they all start at once."  (This is an excellent approach, recommended [among others] by the famous mathematician George Polya.)

This one caused quite the debate, but we figured it out following these steps:

• Imagine you have 10 couples who have 10 babies. 5 will be girls. 5 will be boys. (Total babies made: 10, with 5 boys and 5 girls)
• The 5 couples who had girls will have 5 babies. Half (2.5) will be girls. Half (2.5) will be boys. Add 2.5 boys to the 5 already born and 2.5 girls to the 5 already born. (Total babies made: 15, with 7.5 boys and 7.5 girls.)
• The 2.5 couples that had girls will have 2.5 babies. Half (1.25) will be boys and half (1.25) will be girls. Add 1.25 boys to the 7.5 boys already born and 1.25 girls to the 7.5 already born. (Total babies: 17.5 with 8.75 boys and 8.75 girls).
• And so on, maintianing a 50/50 population.

This is a good back-of-the-envelope calculation, but it talks about things like "2.5 babies" which is silly and "and so on, maintaining a 50/50 population" which begs the question.  Nevertheless, it's a good answer for a short interview.

Before I get to my own solutions, a digression on another related problem:

Two trains are heading toward each other on the same track.  They are 120 miles apart (as the track is laid) at time t = 0.  Each train is moving at 30 mph.

At time t = 0 a fly takes off from the front of the first train and starts flying toward the second train, following the track, at 60 mph (yes, this fly is faster than the train.)  As soon as it reaches the second train it turns around (losing no time on the turnaround, and without being crushed on the windshield) and starts back toward the first train.  When it reaches the first train again it turns around and heads back toward the second train again, and so on, back and forth, until the trains collide and the poor creature's miserable existence is mercifully ended between them.

The question is: how many miles did the fly's odometer advance between time t = 0 and the collision?  (I know, flies don't usually have odometers. This fly does.  He's a very peculiar fly.  But you knew that already.)

There are two canonical ways to answer this question.  One way is to start calculating from the fly's point of view:

Well, the fly F starts at x = -60 and heads toward train T2 at 60 mph... but the train is heading toward the origin at 30 mph... so I solve the system of two linear equations F(t) = -60 + 60t and T2(t) = 60 - 30t and I get the point of intersection is at x = 20 (t = 1 1/3 but this is less relevant.)  So the fly goes 60 + 20 = 80 miles on the first leg.  Then he turns around and heads back toward T1, which by this time is at x = -20... so I solve the new system of two linear equations and I get the point of intersection is at x = -6 2/3.  So the fly goes 26 2/3 miles on the second leg, or 80 + 26 2/3 so far.  Now I do the third leg... hmm, it looks like the distance he goes on each leg is 1/3 the distance of the leg before, that's interesting... I wonder if I can prove it... [proof elided]... OK, it boils down to:

... and I know the geometric series formula...

for |r| < 1 (Geometric series theorem.)

... if I pull out the 80 and substitute r = 1/3 I get...

which comes out to... 120 miles!

This is absolutely correct.  But the other way is to back off a step and look at it from the director's point of view.

OK, the trains start at time t = 0 and they head toward each other at 30 miles per hour each.  So the distance between them is getting smaller at a rate of 60 miles per hour.  There's 120 miles between them at the start, so the crash will happen at time t = 2 hours.  The little fly is going at a constant 60 miles per hour throughout those two hours (poor little fella) so he'll have racked up exactly 120 miles of travel at the time of the collision.  I don't know how far he goes on any given leg (and I don't particularly care.)

Legend has it that legendary mathematician John von Neumann was asked this question during class by a student eager to show him up.  Von Neumann thought for a few moments and came up with the correct answer.

Student (somewhat embarrassed:) Darn... I was hoping you wouldn't see the shortcut, and you'd have to sum the series.

Von Neumann (puzzled:) I did sum the series.

Student: (awed silence)

Heh.  Gets me every time.

Anyway, back to boys and girls.  The "easy" way to solve this is to think of it from the point of view of the hospital maternity ward:

Every day, women come in and give birth.  The midwife doesn't know (or care) how many siblings the newborn has, and nothing in the problem statement changes the assumption that the midwife is going to see a (roughly) equal number of boys and girls being delivered.  So the ratio of boys to girls is (roughly) 50-50.

Changing the point of view from the family to the hospital reveals that almost all of the information in the problem statement was extraneous:

In a country in which people only want boys, every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

All well and good.  But let's try the summing-the-series way (I'm a glutton for punishment.)  We'll start by figuring out how many boys there are, and then figure out how many girls there are, and then calculate the ratio directly.  This way we'll actually use all the information in the problem.

-- How many boys are there? --

Well, the number of families in the country is not given.  Let's call it F, and we'll only count families that actually have children.  About half of the families would have had a boy first... that's F / 2 boys.  The remainder would have tried again.  About half of these would have gotten a boy on the second try... that's F / 4 boys.  The remainder would have tried again.  About half of these would have gotten a boy on the third try... that's F / 8 boys.

At this point we can use an inductive argument to say that for any n from 1 to infinity, there are F / 2n boys that result from the a family getting a boy on the nth try.  Key to this inductive argument are the perfectly natural assumptions that a family can support arbitrarily many children, and that a woman is capable of generating children arbitrarily quickly.

The total number of boys B can then be calculated as:

(Note the use of the geometric series formula again.)

That is to say, there are precisely as many boys as there are families.  Which makes sense because each family has one boy.  Hmm, perhaps there was an easier way to solve this part...

-- How many girls are there? --

The F / 2 families that got a boy first shot out of the box have 0 girls: 0 * F / 2.

The F / 4 families that got a boy on the second try have 1 girl each: 1 * F / 4.

The F / 8 families that got a boy on the third try have 2 girls each: 2 * F / 8.

...

The total number of girls G is thus:

... um...

It's not immediately clear how to sum the series.  An elegant way is to use a trick worth remembering:

Let:

I am assuming both |x| < 1 (for convergence) and x ≠ 0 (for convenience.)

Differentiate (this is the trick:)

Multiply both sides by x:

Now substitute x = 1/2:

Back to the calculation:

Heh.  The total number of girls is also equal to the total number of families... they're just distributed differently (F / 2 families have no girls; F / 4 have one; F / 8 have two; F / 16 have three, etc.)

-- What is the ratio of boys to girls? --

Since B = G = F, the ratio B / G = 1.

QED

All this beautiful analysis to the contrary, the answer is actually wrong.  More boys are born every year than girls (at a ratio of about 106 to 100), and this is countered gradually due to a higher mortality rate among boys than girls (there are fewer girls born every year but they have a higher life expectancy.)  The cutoff age is 36... below this age there are more men than women, above that age there are more women than men.

• #### Pirates of Penzance puzzle - what year is it?

The setting of today's blog post is The Pirates of Penzance, Gilbert and Sullivan's musical about making sure you read the fine print.

The scene opens with a birthday celebration for Frederic, who has just turned 21 and completed his pirate apprenticeship.

SAM.    For today our pirate 'prentice
Rises from indenture freed;
Strong his arm, and keen his scent is
He's a pirate now indeed!

ALL.    Here's good luck to Frederic's ventures!
Frederic's out of his indentures.

SAM.    Two and twenty, now he's rising,
And alone he's fit to fly,
Which we're bent on signalizing
With unusual revelry.
...
KING.  Yes, Frederic, from to-day you rank as a full-blown member of our band.

Frederic, however, is a fine upstanding young man with no taste for piracy; he served this long only because he was contractually obligated.

FRED.  To-day I am out of my indentures, and to-day I leave you for ever.
...
SAM.  We don't seem to make piracy pay.  I'm sure I don't know why, but we don't.
FRED.  I know why, but, alas! I mustn't tell you; it wouldn't be right.
KING.  Why not, my boy?  It's only half-past eleven, and you are one of us until the clock strikes twelve.

Reinforcement of the fact that (as of today) Fred is now twenty-one:

FRED.  Ruth, I will be quite candid with you.  You are very dear to me, as you know, but I must be circumspect. You see, you are considerably older than I. A lad of twenty-one usually looks for a wife of seventeen.

Fred is well on his way to wiping out his former employers when they track him down and point out a technicality in the contract:

KING.

For some ridiculous reason, to which, however, I've no desire to be disloyal,
Some person in authority, I don't know who, very likely the Astronomer Royal,
Has decided that, although for such a beastly month as February, twenty-eight days as a rule are plenty,
One year in every four his days shall be reckoned as nine and twenty.
Through some singular coincidence -- I shouldn't be surprised if it were owing to the agency of an ill-natured fairy --
You are the victim of this clumsy arrangement, having been born in leap-year, on the twenty-ninth of February;
And so, by a simple arithmetical process, you'll easily discover,
That though you've lived twenty-one years, yet, if we go by birthdays, you're only five and a little bit over!
...
FRED.  (more amused than any)  How quaint the ways of Paradox!
At common sense she gaily mocks!
Though counting in the usual way,
Years twenty-one I've been alive,
Yet, reckoning by my natal day,
I am a little boy of five!

RUTH and KING.    He is a little boy of five! Ha! ha! ha!
...
FRED.  Upon my word, this is most curious -- most absurdly whimsical. Five-and-a-quarter!  No one would think it to look at me!
RUTH.  You are glad now, I'll be bound, that you spared us. You would never have forgiven yourself when you discovered that you had killed two of your comrades.
KING.  (rises)  I'm afraid you don't appreciate the delicacy of your position:   You were apprenticed to us --
FRED.  Until I reached my twenty-first year.
KING.  No, until you reached your twenty-first birthday (producing document), and, going by birthdays, you are as yet only five-and-a-quarter.

Shocked, Fred goes to confess to his sweetheart Mabel, portrayed in this picture by Marion Hood:

FRED.    No, Mabel, no.  A terrible disclosure
Has just been made. Mabel, my dearly-loved one,
I bound myself to serve the pirate captain
Until I reached my one-and-twentieth birthday --
MABEL.    But you are twenty-one?
FRED.        I've just discovered
That I was born in leap-year, and that birthday
Will not be reached by me till nineteen forty!

MABEL.    Oh, horrible!  Catastrophe appalling!

This brings us to the point.  Calculate the following:

1. In what year was Frederic born?
2. With as much accuracy as possible, specify the date and time of the opening scene.
• #### Blown movie lines - Torn Curtain

In the underrated movie Torn Curtain, American scientists Michael Armstrong (Paul Newman) and Sarah Louise Sherman (Julie Andrews) meet up with East German scientist Gustav Lindt (the excellent actor Ludwig Dorath) to pump him for a secret formula (the MacGuffin.)

They're at an upscale party and a waltz is playing.  Lindt is a little tipsy and enjoying himself, and he says:

Lindt: The Vienna Waltz. Did I tell you my sister Emily was knocked down by a tram in Vienna? (sings along to the good bit - about 0:54 in the link below.)

Why is this a blown line?

Because there is no such waltz. There are various waltzes with "Vienna" in the title, but the particular waltz in question is the Emperor Waltz.  It would indeed be unfortunate if poor Emily was knocked down by the Emperor...

Hitchcock directed a film about Johann Strauss, Jr.: Waltzes from Vienna, and Ludwig Donath was himself Austrian, so this mistake is surprising.

As an aside, it was this movie (in particular the blackboard scene) that stimulated my youthful interest in mathematics.  A couple of people arguing over weird chalk symbols and one of them says "it would blow up!" - that got my attention.
• #### Wheel of Fortune conundrum

What happens if Pat gets a Bankrupt on the Final Spin?
• #### UI text flow of various languages

This point came up today in a spec review. The text had language like "put the choices 1-N in rows of three, starting with 1 in the top left corner of the screen, and in rows of three to four going down the screen."

Western Europeans and 'mericans (like me) are accustomed to text layout that looks like this, so the text makes sense to us.

Left-to-right, top-down:

But there's a significant number of people in the world (some of whom would use a product designed to the spec) that read right-to-left.  They would be much more comfortable with a text layout like this:

Right-to-left, top-down:

These people include those who read Arabic or Hebrew, for example.

There's also a third text layout that needs a little introduction.  There are two different layouts for Japanese.

The traditional way to write Japanese is in vertical columns, each of which is read/written top down, and the columns are themselves read right-to-left.  A Japanese would expect a product with a "traditional feel" to be laid out like this:

Top-down, right-to-left:

To digress a little...

If vertical space is constrained (for example, for the sign above a storefront) there might only be room for one character per column:

Top-down, right-to-left, columns are one character high:

To the casual viewer, this is easily confused with right-to-left / top-down.  Japanese is sometimes incorrectly thought of as an RTL language.  There's a similar effect in Western European languages on some hotel signs that have lots of vertical space but only enough horizontal room for one column.

Finally, I should mention that Japanese also has a modern text layout.  For products that are aiming for a modern feel as opposed to a traditional feel, it is usual to write the Japanese characters in left-to-right / top-down layout.

(Footnote: note that single-row-high Japanese text can be read either left-to-right, or right-to-left, depending on context.  There are often clues available to allow a reader to know which way to read; for example, I believe some characters are written differently depending on which layout is in effect.  Also, the font or the setting may give hints as to whether a "traditional" or "modern" feel is intended.)

• #### Downmixing stereo to mono

Suppose you have a stereo stream that you want to downmix to mono.  Why would you do this?  Maybe you're playing stereo music to a Bluetooth headset that is in a call, and thus in "headset / handsfree" mode.  Maybe you're capturing from a stereo mic and you want to show a visualization based on a mono reduction of the signal.

The basic formula to use is M = L / 2 + R / 2 but there are a couple of things to be aware of.

Consider the simplest case first where the left and right channels are identical.  Naturally, the resulting mono signal is identical to both of the channels:

In particular, downmixing a stereo signal of identical full scale sine waves (power = -3 dB FS) results in a -3 dB FS mono sine wave.  Well and good.

This, however, is a simple coincidence few could ever have counted upon.  (A similar effect is the lack of spectral leakage if your signal period exactly matches up to your FFT window period.)  As a rule, downmixing results in a loss of power.  To get a basic idea of why this is, let's take two different sine waves and downmix to a two-tone:

Note that downmixing these two totally uncorrelated signals results in a loss of power of 3 dB FS; the power of the two-tone is -6 dB FS, 3 dB FS lower than each of the individual -3 dB FS signals that went into it.

It is tempting to conclude that mixing two signals of power P gives a resultant signal of power between P - 3 dB and P, depending on the degree of correlation.  However, this conclusion is incorrect: signals can be correlated; uncorrelated; or anticorrelated.

Once in a while you get a stereo microphone which captures heavily correlated L and R channels, but (due to one reason and another) inverts one of the channels.  Instead of being heavily correlated, the L and R signals are now heavily anticorrelated. This is bad enough when you try to listen to it: but when you downmix to mono, the signal disappears!

The effect with a "real" stereo signal is somewhat less dramatic because it's receiving only very highly correlated signals (not perfectly correlated.)  So the downmix to mono only almost totally destroys the signal.

• #### optimal tic-tac-toe (XKCD)

Today's XKCD strip purports to show a complete map of tic-tac-toe including optimal moves.

I'm guessing the optimality of the move takes into account both the game-theoretic value of the move, assuming a perfect opponent:

• Good moves
• Preserves the win
• Preserves the draw
• "Preserves the loss" (every move in a lost position is of this type)
• Converts won position to drawn position
• Converts drawn position to lost position
• Converts won position to lost position

And the practical value of the move, which allows for the possibility of error either on the player's part or the opponent's part.

In particular, I'm guessing that at each level Randall eliminated all the "bad" (and "very bad") moves, then broke the "well, all these moves are 'good'" tie by looking at some aggregation of the values of all following positions.  The idea is, you want to pick the "good move" which:

• In a won position: minimizes the chance that you'll make a "bad" move (or a "very bad" move) later
• In a drawn position: maximizes the chance that your opponent will make a "bad" move
• Further ties broken by minimizing the chance that you'll make a "bad" move later
• In a lost position: maximizes the chance that your opponent will make a "bad" move (or a "very bad" move)

If there are still ties, I am guessing that Randall invoked a randomizer.  For example, X's first move (in the top left corner) is tied in every possible respect with the other three corners.

I object to this approach because humans don't always pick moves randomly.  They learn.  They make rules for themselves, some of which are fallible, and can be exploited.  For example, "move in the center if you can" is a typical rule, followed by "if you can't move in the center, move in a corner."  Also, I think information is lost by hiding the other "good" moves.

So, here's my version.  I don't go into nearly as much depth, but here is the game-theoretic value of all of X's first moves (W = win; D = draw; L = loss:)

Not very exciting... a nine-way tie.

And for each first move for X, here is the game-theoretic value of all of O's first moves (I only show three, the others can be inferred by symmetry:)

For an example of a "very bad" move, consider the position after X moves in the top left corner (a good move) and O moves in the lower left corner (a bad move, after which X has a won position:)

• #### Perl script to parse MPEG audio header

I've written a perl script (attached) which will parse MPEG audio headers and display them in a human-readable format.

For example, if you run it on ding.mpeg (also attached) you get this output:

Frame header: 11111111 111 (should be all ones)
MPEG Audio version ID: 11 (MPEG version 1 (ISO/IEC 11172-3))
Layer description: 10 (layer II)
Protection bit: 0 (protected by CRC (16-bit CRC follows header))
Bitrate index: 1011 (224 kbps)
Sample rate index: 00 (44100 Hz)
Private bit: 0 (application specific)
Channel mode: 00 (stereo)
Mode extension (if channel mode is joint stereo:) 00 (bands 4 to 31)
Original: 0 (copy of original media)
Emphasis: 00 (none)

Here's the source for the perl script:

use strict;

# based on http://www.mpgedit.org/mpgedit/mpeg_format/mpeghdr.htm
# assumes that the file you point it at starts with an MPEG audio header

unless (1 == @ARGV and \$ARGV[0] ne "/?" and \$ARGV[0] ne "-?") {
print "USAGE: perl \$0 mpeg-audio-file.mpeg";
exit(0);
};

my %version = (
"00" => "MPEG Version 2.5 (unofficial)",
"01" => "reserved",
"10" => "MPEG version 2 (ISO/IEC 13818-3)",
"11" => "MPEG version 1 (ISO/IEC 11172-3)",
);

my %layer = (
"00" => "reserved",
"01" => "layer III",
"10" => "layer II",
"11" => "layer I",
);

my %protection = (
"0" => "protected by CRC (16-bit CRC follows header)",
"1" => "not protected",
);

my %bitrate = (
# version 1
"11" => {
# layer 1
"11" => {
"0000" => "free",
"0001" => "32 kbps",
"0010" => "64 kbps",
"0011" => "96 kbps",
"0100" => "128 kbps",
"0101" => "160 kbps",
"0110" => "192 kbps",
"0111" => "224 kbps",
"1000" => "256 kbps",
"1001" => "288 kbps",
"1010" => "320 kbps",
"1011" => "352 kbps",
"1100" => "384 kbps",
"1101" => "416 kbps",
"1110" => "448 kbps",
},

# layer 2
"10" => {
"0000" => "free",
"0001" => "32 kbps",
"0010" => "48 kbps",
"0011" => "56 kbps",
"0100" => "64 kbps",
"0101" => "80 kbps",
"0110" => "96 kbps",
"0111" => "112 kbps",
"1000" => "128 kbps",
"1001" => "160 kbps",
"1010" => "192 kbps",
"1011" => "224 kbps",
"1100" => "256 kbps",
"1101" => "320 kbps",
"1110" => "384 kbps",
},

# layer 3
"01" => {
"0000" => "free",
"0001" => "32 kbps",
"0010" => "40 kbps",
"0011" => "48 kbps",
"0100" => "56 kbps",
"0101" => "64 kbps",
"0110" => "80 kbps",
"0111" => "96 kbps",
"1000" => "112 kbps",
"1001" => "128 kbps",
"1010" => "160 kbps",
"1011" => "192 kbps",
"1100" => "224 kbps",
"1101" => "256 kbps",
"1110" => "320 kbps",
},
},

# version 2
"10" => {
# layer 1
"11" => {
"0000" => "free",
"0001" => "32 kbps",
"0010" => "48 kbps",
"0011" => "56 kbps",
"0100" => "64 kbps",
"0101" => "80 kbps",
"0110" => "96 kbps",
"0111" => "112 kbps",
"1000" => "128 kbps",
"1001" => "144 kbps",
"1010" => "160 kbps",
"1011" => "176 kbps",
"1100" => "192 kbps",
"1101" => "224 kbps",
"1110" => "256 kbps",
},

# layer 2
"10" => {
"0000" => "free",
"0001" => "8 kbps",
"0010" => "16 kbps",
"0011" => "24 kbps",
"0100" => "32 kbps",
"0101" => "40 kbps",
"0110" => "48 kbps",
"0111" => "56 kbps",
"1000" => "64 kbps",
"1001" => "80 kbps",
"1010" => "96 kbps",
"1011" => "112 kbps",
"1100" => "128 kbps",
"1101" => "144 kbps",
"1110" => "160 kbps",
},

# layer 3
"01" => {
"0000" => "free",
"0001" => "8 kbps",
"0010" => "16 kbps",
"0011" => "24 kbps",
"0100" => "32 kbps",
"0101" => "40 kbps",
"0110" => "48 kbps",
"0111" => "56 kbps",
"1000" => "64 kbps",
"1001" => "80 kbps",
"1010" => "96 kbps",
"1011" => "112 kbps",
"1100" => "128 kbps",
"1101" => "144 kbps",
"1110" => "160 kbps",
},
},
);

my %samplerate = (
# version 1
"11" => {
"00" => "44100 Hz",
"01" => "48000 Hz",
"10" => "32000 Hz",
"11" => "reserved",
},

# version 2
"10" => {
"00" => "22050 Hz",
"01" => "24000 Hz",
"10" => "16000 Hz",
"11" => "reserved",
},

# version 2.5 (unofficial)
"00" => {
"00" => "11025 Hz",
"01" => "12000 Hz",
"10" => "8000 Hz",
"11" => "reserved",
},
);

"0" => "frame is not padded",
"1" => "frame is padded with one extra slot",
);

my %channelmode = (
"00" => "stereo",
"01" => "joint stereo (stereo)",
"10" => "dual channel (stereo)",
"11" => "single channel (mono)",
);

my %modeextension = (
# layer I
"11" => {
"00" => "bands 4 to 31",
"01" => "bands 8 to 31",
"10" => "bands 12 to 31",
"11" => "bands 16 to 31",
},

# layer II
"10" => {
"00" => "bands 4 to 31",
"01" => "bands 8 to 31",
"10" => "bands 12 to 31",
"11" => "bands 16 to 31",
},

# layer III
"01" => {
"00" => "intensity stereo off; m/s stereo off",
"01" => "intensity stereo on; m/s stereo off",
"10" => "intensity stereo off; m/s stereo on",
"11" => "intensity stereo on; m/s stereo on",
},
);

"0" => "audio is not copyrighted",
);

my %original = (
"0" => "copy of original media",
"1" => "original media",
);

my %emphasis = (
"00" => "none",
"01" => "50/15 microseconds", # the source incorrectly says "ms" which is milliseconds
"10" => "reserved",
"11" => "CCIT J.17",
);

open(MPEG, "<", \$ARGV[0]) or die("Could not open \$ARGV[0]: \$!");
binmode(MPEG) or die("Could not set file handle to binary mode: \$!"); # binary file

close(MPEG);

my @bits = ();

for my \$byte (map { ord( \$_ ) } split (//, \$header)) {
for my \$bit (1 .. 8) {
push @bits, ((\$byte & (1 << (8 - \$bit))) ? 1 : 0);
}
}

unless ("1" x 11 eq join("", @bits[0 .. 10])) {
printf("WARNING: the frame header is not all ones. This is not a valid MPEG audio header.\n");
# carry on regardless
}

printf(
"Frame header: %s %s (%s)\n" .
"MPEG Audio version ID: %s (%s)\n" .
"Layer description: %s (%s)\n" .
"Protection bit: %s (%s)\n" .
"Bitrate index: %s (%s)\n" .
"Sample rate index: %s (%s)\n" .
"Private bit: %s (%s)\n" .
"Channel mode: %s (%s)\n" .
"Mode extension (if channel mode is joint stereo:) %s (%s)\n" .
"Original: %s (%s)\n" .
"Emphasis: %s (%s)\n" .
""
,
join("", @bits[0 .. 7]), join("", @bits[8 .. 10]), "should be all ones",
join("", @bits[11 .. 12]), \$version{ join("", @bits[11 .. 12]) },
join("", @bits[13 .. 14]), \$layer{ join("", @bits[13 .. 14]) },
\$bits[15], \$protection{ \$bits[15] },
join("", @bits[16 .. 19]),
# bit rate depends on version, layer, and bitrate index
\$bitrate{ join("", @bits[11 .. 12]) }{ join("", @bits[13 .. 14]) }{ join("", @bits[16 .. 19]) },
join("", @bits[20 .. 21]),
# sample rate depends on version
\$samplerate{ join("", @bits[11 .. 12]) }{ join("", @bits[20 .. 21]) },
\$bits[23], "application specific",
join("", @bits[24 .. 25]), \$channelmode{ join("", @bits[24 .. 25]) },
join("", @bits[26 .. 27]),
# mode extension depends on layer
\$modeextension{ join("", @bits[13 .. 14]) }{ join("", @bits[26 .. 27]) },
\$bits[29], \$original{ \$bits[29] },
join("", @bits[30 .. 31]), \$emphasis{ join("", @bits[30 .. 31]) },
);

Note this script assumes that the very first bytes of the file are the MPEG audio header, and makes no effort to dig into the file to find the audio header.

EDIT 2015-10-31: moved script to https://github.com/mvaneerde/blog/blob/master/scripts/mpegaudioheader.pl

• #### The evolution of HRESULT_FROM_WIN32

We figured they were more actual guidelines. -- Pirates of the Caribbean

Macros are wonderful things.  I love macros.  They're exciting and dangerous.  Every time I write a macro I salivate at the power I am wielding.  It's like using a blowtorch.

It is perhaps no coincidence that many coding standards put big warning signs around macroland.  "Consider carefully before using macros", some say. "When considering using a macro, see if you can use an inline function instead," some say.  "Macros are frequent sources of bugs," some say.  "C++ has evolved to the point where, with inline functions and templates, macros are no longer necessary".

Heresy.

All absolutely true, and yet heresy nonetheless.  It is true that there are many bugs out there due to misuse of macros.  And yet only a few simple tips are necessary to prevent misuse of macros: (The problem is that the tips don't always get followed).

She generally gave herself very good advice, (though she very seldom followed it) -- Alice in Wonderland

1. By convention, name macros in ALL_CAPS.  This makes it easy to recognize them.
Without this rule it is easy to think that the following macro is a function...
#define SafeDelete(p) { delete (p); (p) = NULL; } void(0)
... and in fact it probably should be...
template<typename T> SafeDelete(T *&p) { delete p; p = NULL; }
2. Parenthesize the definition of the macro.
This prevents precedence bugs.
#define SQUARE(x) (x) * (x) // should be ((x) * (x))
int four = 16 / SQUARE(2); // BUG: four == 16
3. Parenthesize uses of the arguments of the macro unless this contravenes the purpose of the macro.
This prevents precedence bugs in the other direction.
#define SQUARE(x) (x * x) // should be ((x) * (x))
int four = SQUARE(1 + 1); // BUG: four == 3
4. Fill out optional clauses.
#define ASSERT(x) if (!(x)) { exit(__LINE__); }
// should be if (!(x)) { exit(__LINE__); } else {} (void)0
if (IsTuesday())
ASSERT(m_pGarbage);
else { // BUG: will only vacuum and check mail on tuesday (and only if m_pGarbage is set)
Vacuum();
CheckMail();
}
5. UNDER NO CIRCUMSTANCES use an expression that has side effects as an argument when calling a macro.
#define SafeDelete(p) { delete (p); (p) = NULL; } void(0) // reasonable, except for ALL_CAPS rule
// p points to the first of a null-terminated array of pointers that need to be deleted
while (p) SafeDelete(p++); // BUG: only odd-numbered pointers deleted, and AV if odd number of elements

Exceptions I happen to agree with: VERIFY(...) cries out to be an exception to this rule since it commonly textifies the condition, and a popup that says "CloseHandle(m_file) failed" is infinitely more meaningful than "bOK failed".  As a corollary, VERIFY(...) macros should only evaluate their arguments once.
Exceptions I've given up trying to convince other people are bad: SUCCEEDED(...), FAILED(...), and HRESULT_FROM_WIN32(GetLastError()) are common exceptions too.

Let's talk about the "no expressions with side effects" rule a little more.  It is OK to do things like

if (SUCCEEDED(CoInitialize(...))) { ... }

if (FAILED(CoCreateInstance(...))) { ... }

return HRESULT_FROM_WIN32(GetLastError());

... but for different reasons.  SUCCEEDED(...) and FAILED(...) only evaluate their arguments once, as can be verified from their definitions in winerror.h.  I'm using the Vista RTM version of winerror.h:

//
// Generic test for success on any status value (non-negative numbers
// indicate success).
//

#define SUCCEEDED(hr) (((HRESULT)(hr)) >= 0)

//
// and the inverse
//

#define FAILED(hr) (((HRESULT)(hr)) < 0)

Note the heavy (and correct) use of parentheses.  I still personally don't think it's a good idea to rely on this, since macros have a habit of changing... but I won't ding anyone on a code review for it.

HRESULT_FROM_WIN32(GetLastError()) is OK for a totally different reason.  HRESULT_FROM_WIN32(...), classically, does evaluate its argument multiple times... this time I'm using the Windows 2000 version of winerror.h:

#define HRESULT_FROM_WIN32(x)   (x ? ((HRESULT) (((x) & 0x0000FFFF) | (FACILITY_WIN32 << 16) | 0x80000000)) : 0 )

... so this looks like a bug... until you realize that GetLastError() is idempotent.  If you call it a bunch of times in a row on the same thread, it will (per its contract) always return the same value.

Note that the macro is not completely parenthesized!  The bold x is missing its protective parentheses.  This was fixed in a Windows 2000 service pack.  For example, here's the Win2K SP3 version:

#define HRESULT_FROM_WIN32(x) ((HRESULT)(x) <= 0 ? ((HRESULT)(x)) : ((HRESULT) (((x) & 0x0000FFFF) | (FACILITY_WIN32 << 16) | 0x80000000)))

Much better.

I'm still personally leery of using side effects in HRESULT_FROM_WIN32 though.  Why?  Because it sets a bad precedent.  It's easier to have a simple rule (no side effects in a macro call!) than to remember for an infinitude of macros and function calls which macros evaluate the arguments multiple times and which function calls really have side effects.  You also get legitimate bugs like this.

Macros, macros, macros... you deviate just a little bit from the straight-and-narrow and what happens?   You get blown out of the water.  Wonderful things, macros.

Nasty little bugs arising from harmless-looking violations of the safety tips are the cause of the dirty secret I am about to reveal...

As of Vista RTM...

HRESULT_FROM_WIN32 is NO LONGER a macro!

This is one of those annoying little facts I try so hard to forget because they complicate life unnecessarily.  From my point of view, there is no bad consequence of treating HRESULT_FROM_WIN32 as the macro it looks like (and was... and who knows, may be again.)  The inline function it has become is uniformly safer.

This has apparently been a long time in coming.  Here are some excerpts of winerror.h from various releases of Windows:

Windows 2000 RTM:

#define HRESULT_FROM_WIN32(x)   (x ? ((HRESULT) (((x) & 0x0000FFFF) | (FACILITY_WIN32 << 16) | 0x80000000)) : 0 )

Windows XP RTM:

// __HRESULT_FROM_WIN32 will always be a macro.
// The goal will be to enable INLINE_HRESULT_FROM_WIN32 all the time,
// but there's too much code to change to do that at this time.

#define __HRESULT_FROM_WIN32(x) ((HRESULT)(x) <= 0 ? ((HRESULT)(x)) : ((HRESULT) (((x) & 0x0000FFFF) | (FACILITY_WIN32 << 16) | 0x80000000)))

#ifdef INLINE_HRESULT_FROM_WIN32
#ifndef _HRESULT_DEFINED
#define _HRESULT_DEFINED
typedef long HRESULT;
#endif
#ifndef __midl
__inline HRESULT HRESULT_FROM_WIN32(long x) { return x < 0 ? (HRESULT)x : (HRESULT) (((x) & 0x0000FFFF) | (FACILITY_WIN32 << 16) | 0x80000000);}
#else
#define HRESULT_FROM_WIN32(x) __HRESULT_FROM_WIN32(x)
#endif
#else
#define HRESULT_FROM_WIN32(x) __HRESULT_FROM_WIN32(x)
#endif

Whew.  The net result is that HRESULT_FROM_WIN32 is a macro.  Oh, unless you decide to be avant-garde and #define INLINE_HRESULT_FROM_WIN32 before you #include <winerror.h>.  Which probably very few people did, except for build engineers running experiments.  So this is an "opt-in" inline function.

Windows Vista RTM:

//
// HRESULT_FROM_WIN32(x) used to be a macro, however we now run it as an inline function
// to prevent double evaluation of 'x'. If you still need the macro, you can use __HRESULT_FROM_WIN32(x)
//
#define __HRESULT_FROM_WIN32(x) ((HRESULT)(x) <= 0 ? ((HRESULT)(x)) : ((HRESULT) (((x) & 0x0000FFFF) | (FACILITY_WIN32 << 16) | 0x80000000)))

#if !defined(_HRESULT_DEFINED) && !defined(__midl)
#define _HRESULT_DEFINED
typedef __success(return >= 0) long HRESULT;
#endif

#ifndef __midl
FORCEINLINE HRESULT HRESULT_FROM_WIN32(unsigned long x) { return (HRESULT)(x) <= 0 ? (HRESULT)(x) : (HRESULT) (((x) & 0x0000FFFF) | (FACILITY_WIN32 << 16) | 0x80000000);}
#else
#define HRESULT_FROM_WIN32(x) __HRESULT_FROM_WIN32(x)
#endif

The experiments appear to have been completed.   Apparently no imaginable consequence of changing to an inline function was worse than the known consequence of bugs.

People who want the macro can still use __HRESULT_FROM_WIN32.

Why would you want to?  Hmmm... maybe you're building a switch statement.  Something like:

#define CASE_HRESULT(x) case x: return #x
#define CASE_ERR(x) case HRESULT_FROM_WIN32(x): return #x // need __HRESULT_FROM_WIN32 here?

LPCSTR FriendlyNameOf(HRESULT hr) {
switch(hr) {
CASE_HRESULT(S_OK);
CASE_HRESULT(S_FALSE);
... many more...
CASE_ERR(ERROR_SUCCESS);
CASE_ERR(ERROR_INVALID_FUNCTION);
...
}
return "Unrecognized";
}

I haven't tried it out, but I suspect the compiler will reject the attempt to squeeze the result of an inline function into the value of a case, but will accept a complicated expression involving a bunch of constants (i.e., the macro will work.)

• #### Generating a sine wave

One common task on the Windows Sound test team is taking a known-good sine wave, passing it through some chunk of code, and looking at what comes out.  Is it a sine wave?  Is it the same frequency that it should be?  Etc., etc.

So the quality of the sine wave generator is important.

There's a commonly available sine wave generator: double sin(double).   It's fairly simple to use this to generate a buffer, if you keep a few things in mind.  But there are pitfalls too.

In full generality, a sine wave can be completely described by four measurements:

1. Amplitude: half the difference between the maximum and minimum samples.
There's a mathematical reason to use half the difference instead of the whole difference.  We'll go into this later.
Yes, there were some bugs due to this "use half the difference" convention.
For our purposes, we'll consider "full scale" to be from -1.0 to 1.0; the amplitude of a full-scale sine wave is 1.0.  the amplitude of a -3 dB FS sine wave is 10-3/20, or about 0.707945...
2. Frequency or Period.  Frequency is the number of complete cycles in a fixed unit of time (usually one second.)  Period is the time length of a single complete cycle.  Frequency * Period = 1, unless one of them is zero (in which case the other is infinite.)
3. dc.  dc is the average value over a complete cycle.
4. Phase.  This tells where in the cycle the first sample is.  If you measure the angle in radians... which is usual... then the phase is a number between 0 and 2π.

These can all be linked together by a single formula which tells you the mathematical value of a sine wave with these features at any given time.  Let:

a = amplitude (0.0 to 1.0)
f = frequency (in cycles/sec)
c = dc (0.0 to 1.0; to avoid clipping, 0.0 to (1.0 - a))
ϕ = starting phase (0.0 to 2π)
t = the time of interest in seconds

Then

w(t) = a sin(2πft + ϕ) + c

Note in passing that w(0) = a sin((2πf)0 + ϕ) + c = a sin(ϕ) + c is independent of f.

So much for mathematics.  When you want to realize a sine wave in a PCM wave format, you have to discretize the time dimension and the sample dimension.  To discretize the time dimension you need a sample rate (usually 44100 samples per second) and to discretize the sample dimension you need to specify a sample format (usually 16-bit int).

Let's talk about discretizing the time dimension first.  Let s = the sample rate, and i be the sample of interest.  Now:

w(i) = a sin(2πfi / s + ϕ) + c

As a design simplification, we collect constants, and eliminate ϕ and c...

w(i) = a sin((2πf / s) i)

And we have an implementable function

// given a buffer, fills it with sine wave data
HRESULT FillBufferWithSine(
LPCWAVEFORMATEX pWfx, // includes sample rate
double lfAmplitude,
double lfFrequency,
PBYTE pBuffer,
UINT32 cbBytes
);

This would start at i = 0, loop through i = cbBytes / pWfx->nBlockAlign, and set sample values for each i.

It is often necessary to get continuous sine wave data in chunks... say, 1 KB at a time.  It is important that the phase of the sine wave match at chunk boundaries.  This suggests another parameter:

// given a buffer, fills it with sine wave data
HRESULT FillBufferWithSine(
LPCWAVEFORMATEX pWfx, // includes sample rate
double lfAmplitude,
double lfFrequency,
UINT32 ifFrameOffset,
PBYTE pBuffer,
UINT32 cbBytes
);

... where ifFrameOffset is the count of frames to skip.  Now a client can fill a 1 KB buffer with 256 frames of 16-bit int stereo sine wave, pass it off to someone else, fill another 1 KB buffer starting at frame offset 256 with 16-bit int stereo sine wave, etc., and the effect is an almost infinite continuous sine wave.  (Oh, and as a side effect, we get a kinda-sorta implementation of ϕ.)

Almost.

Why almost?

Well, because I used UINT32 as the frame offset.  Suppose you, as a client, use a WAVEFORMATEX with a nice high sample rate like 384 kHz.  A UINT32 wraps at 232.   At 384,000 samples per second, you'll burn through 232 samples in (232 / 384000) seconds... that's, um, 1184.8106666... seconds... three hours, six minutes, twenty-five seconds.  This is uncomfortably close to reasonable.

At that point, one of two things happen.  If you were clever in your chosen frequency, you will wrap back to a point in the sine wave where the phase is the same as what you want anyway... and there will be no observable artifact in the generated sine wave.  Or, if you were unlucky, you will wrap back to a point in the sine wave where the phase is different - and there will be a discontinuity.  This will probably result in an audible "pop" artifact in the signal tone.

Our test tone generator had this problem.  We knew about it - we didn't care.

But sometimes little things nag at me and I have to fix them or I can't sleep at night.  It's a fixation... a terrible disease... but there it is.

So I fixed it - almost.  Now we use a UINT64 for the sample offset.  That won't wrap until 264 samples.  Even at 384 kHz, that won't wrap until (264/384000) seconds - that's, um,  48038396025285.29 seconds... 1,521,800-odd years.  I'll let a tester from that era file a bug then. :-)

Almost.

Why almost?

Well, it turns out that fixing that bug uncovered another bug.  We know about it - we don't care.  (But sometimes little things nag at me...)

Exercise... what is the bug?

Page 3 of 6 (149 items) 12345»