# Matthew van Eerde's web log

• #### Enumerating mixer devices, mixer lines, and mixer controls

The WinMM multimedia APIs include an API for enumerating and controlling all the paths through the audio device; things like bass boost, treble control, pass-through audio from your CD player to your headphones, etc.  This is called the "mixer" API and is the forerunner of the IDeviceTopology API.

I wrote a quick app to enumerate all the mixer devices on the system; for each mixer device, enumerate each mixer line (that is, each source and destination); for each mixer line, enumerate all the controls (volume, mute, equalization, etc.); and for each control, query the associated text (if any) and the current value.

Source and binaries attached.

Pseudocode:

mixerGetNumDevs()
for each mixer device
mixerGetDevCaps(dev)
for each destination (line) on the device
mixerGetLineInfo(dest)
mixerGetLineControls(dest)
for each control on the line
if the control supports per-item description
mixerGetControlDetails(control, MIXER_GETCONTROLDETAILSF_LISTTEXT)
log the per-item description
mixerGetControlDetails(control, MIXER_GETCONTROLDETAILSF_VALUE)
log the value(s)

Usage:

>mixerenum.exe
Mixer devices: 5
Device ID: 0
Manufacturer identifier: 1
Product identifier: 104
Driver version: 6.2
Support: 0x0
Destinations: 1
-- Destination 0: Master Volume --
Destination: 0
Source: -1
Line ID: 0xffff0000
Status: MIXERLINE_LINEF_ACTIVE (1)
User: 0x00000000
Channels: 1
Connections: 2
Controls: 2
Short name: Volume
Long name: Master Volume
-- Target:  --
Type: MIXERLINE_TARGETTYPE_UNDEFINED (0)
Device ID: 0
Manufacturer identifier: 65535
Product identifier: 65535
Driver version: 0.0
Product name:
-- Control 1: Mute --
Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Mute
Long name: Mute
-- Values --
FALSE
-- Control 2: Volume --
Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Volume
Long name: Volume
-- Values --
0xffff on a scale of 0x0 to 0xffff
-- 1: HDMI Audio (Contoso --
Device ID: 1
Manufacturer identifier: 1
Product identifier: 104
Driver version: 6.2
Product name: HDMI Audio (Contoso
Support: 0x0
Destinations: 1
-- Destination 0: Master Volume --
Destination: 0
Source: -1
Line ID: 0xffff0000
Status: MIXERLINE_LINEF_ACTIVE (1)
User: 0x00000000
Component Type: MIXERLINE_COMPONENTTYPE_DST_DIGITAL (1)
Channels: 1
Connections: 2
Controls: 2
Short name: Volume
Long name: Master Volume
-- Target:  --
Type: MIXERLINE_TARGETTYPE_UNDEFINED (0)
Device ID: 0
Manufacturer identifier: 65535
Product identifier: 65535
Driver version: 0.0
Product name:
-- Control 1: Mute --
Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Mute
Long name: Mute
-- Values --
FALSE
-- Control 2: Volume --
Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Volume
Long name: Volume
-- Values --
0xffff on a scale of 0x0 to 0xffff
-- 2: Speakers (Contoso --
Device ID: 2
Manufacturer identifier: 1
Product identifier: 104
Driver version: 6.2
Product name: Speakers (Contoso
Support: 0x0
Destinations: 1
-- Destination 0: Master Volume --
Destination: 0
Source: -1
Line ID: 0xffff0000
Status: MIXERLINE_LINEF_ACTIVE (1)
User: 0x00000000
Component Type: MIXERLINE_COMPONENTTYPE_DST_SPEAKERS (4)
Channels: 1
Connections: 2
Controls: 2
Short name: Volume
Long name: Master Volume
-- Target:  --
Type: MIXERLINE_TARGETTYPE_UNDEFINED (0)
Device ID: 0
Manufacturer identifier: 65535
Product identifier: 65535
Driver version: 0.0
Product name:
-- Control 1: Mute --
Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Mute
Long name: Mute
-- Values --
FALSE
-- Control 2: Volume --
Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Volume
Long name: Volume
-- Values --
0xffff on a scale of 0x0 to 0xffff
Device ID: 3
Manufacturer identifier: 1
Product identifier: 104
Driver version: 6.2
Support: 0x0
Destinations: 1
-- Destination 0: Master Volume --
Destination: 0
Source: -1
Line ID: 0xffff0000
Status: MIXERLINE_LINEF_ACTIVE (1)
User: 0x00000000
Component Type: MIXERLINE_COMPONENTTYPE_DST_WAVEIN (7)
Channels: 1
Connections: 1
Controls: 2
Short name: Volume
Long name: Master Volume
Type: MIXERLINE_TARGETTYPE_WAVEIN (2)
Device ID: 0
Manufacturer identifier: 1
Product identifier: 101
Driver version: 6.2
-- Control 1: Mute --
Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Mute
Long name: Mute
-- Values --
FALSE
-- Control 2: Volume --
Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Volume
Long name: Volume
-- Values --
0xf332 on a scale of 0x0 to 0xffff
-- 4: Microphone (Contoso --
Device ID: 4
Manufacturer identifier: 1
Product identifier: 104
Driver version: 6.2
Product name: Microphone (Contoso
Support: 0x0
Destinations: 1
-- Destination 0: Master Volume --
Destination: 0
Source: -1
Line ID: 0xffff0000
Status: MIXERLINE_LINEF_ACTIVE (1)
User: 0x00000000
Component Type: MIXERLINE_COMPONENTTYPE_DST_WAVEIN (7)
Channels: 1
Connections: 1
Controls: 2
Short name: Volume
Long name: Master Volume
-- Target: Microphone (Contoso --
Type: MIXERLINE_TARGETTYPE_WAVEIN (2)
Device ID: 1
Manufacturer identifier: 1
Product identifier: 101
Driver version: 6.2
Product name: Microphone (Contoso
-- Control 1: Mute --
Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Mute
Long name: Mute
-- Values --
FALSE
-- Control 2: Volume --
Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
Item count: 0
Short name: Volume
Long name: Volume
-- Values --
0xf332 on a scale of 0x0 to 0xffff

• #### Sample app for RECT functions

Riffing on Raymond Chen's post today about SubtractRect I threw together a toy app which demonstrates three rectangle functions: UnionRect, IntersectRect, and SubtractRect.

Usage:

>rects.exe
rects.exe
union     (left1 top1 right1 bottom1) (left2 top2 right2 bottom2) |
intersect (left1 top1 right1 bottom1) (left2 top2 right2 bottom2) |
subtract  (left1 top1 right1 bottom1) (left2 top2 right2 bottom2)

Sample output:

>rects.exe union (2 2 6 6) (4 4 8 8)
(left = 2; top = 2; right = 6; bottom = 6)
union (left = 4; top = 4; right = 8; bottom = 8)
= (left = 2; top = 2; right = 8; bottom = 8)

Source and binaries (amd64 and x86) attached.

Still no pictures though.

Exercise: implement BOOL SymmetricDifferenceRect(_Out_ RECT *C, const RECT *A, const RECT *B).

• #### An attempt to explain the twin prime conjecture to a five-year-old

Back in April, Zhang Yitang came up with a result that is a major step toward proving the twin prime conjecture that there are infinitely many primes p for which p + 2 is also prime.

In a reddit.com/r/math thread on the subject, I made the following comment as an attempt to explain the twin prime conjecture to a five-year-old:

ELI5 attempt at the twin prime conjecture

• by yourself (you get all the cookies)
• with two people (each person gets 50 cookies)
• with four people (each person gets 25 cookies)
• with five people (each person gets 20 cookies)
• with ten people (each person gets ten cookies)
• with 20 people (each person gets five cookies)
• with 25 people (each person gets four cookies)
• with 50 people (each person gets two cookies)
• with 100 people (each person gets one cookie)

If you're the only person at your party, it's a sad party.

If everyone at the party gets only one cookie, it's a sad party.

If someone gets more than someone else, it's a sad party.

You don't want your party to be sad, so you have to be careful to have the right number of people to share your cookies.

If you have two cookies, or three, or five, or seven, or eleven, then it's not possible to have a happy party. There's no "right number of people."

People used to wonder whether you could be sure to have a happy party if you just had enough cookies. A famous person named Euclid figured out that, no matter how many cookies you had, even if it was, like, more than a million, you might be unlucky and have a sad number of cookies.

If it's a birthday party, the birthday kid's mom might give the birthday kid an extra cookie. (Or they might get something else instead.) That would be OK.

If it's a birthday party, then, yes, you can be sure to have a happy party if you just had enough cookies. In fact, even three cookies would be enough; you could have the birthday kid, and one friend; they would each have one cookie, and the birthday kid would get the extra one.

But Sam and Jane have a problem. They're twins, and they always have the same birthday. One year they had 13 cookies, and it was a big problem. 13 is a sad number. Even if they both had an extra cookie, that would leave 11, and that is still a sad number.

(If you allow the birthday kid to have two extra cookies, that would leave nine; they could invite one more person, give everyone three cookies, and then Sam and Jane could each have two extras. But this is not a happy party because the guests will get upset that the birthday kids got two extra cookies. I mean, come on!)

Sam and Jane wondered whether they could be sure to have a happy party if they just had enough cookies.

So they asked their mom, who is, like, super smart.

But even she didn't know.

In fact, no-one knows. They don't think so. But they're not, like, super-sure.

• #### Buffer size alignment and the audio period

I got an email from someone today, paraphrased below:

Q: When I set the sampling frequency to 48 kHz, and ask Windows what the audio period is, I get exactly 10 milliseconds. When I set it to 44.1 kHz, I get very slightly over 10 milliseconds: 10.1587 milliseconds, to be precise. Why?
A: Alignment.

A while back I talked a bit about the WASAPI exclusive-mode alignment dance. Some audio drivers have a requirement that they deal in buffer sizes which are multiples of a certain byte size - for example, a common alignment restriction for HD Audio hardware is 128 bytes.

A more general audio requirement is that buffer sizes be a multiple of the size of a PCM audio frame.
For example, suppose the audio format of a stream is stereo 16-bit integer. A single PCM audio frame will be 2 * 2 = 4 bytes. The first two bytes will be the 16-bit signed integer with the sample value for the left channel; the last two bytes will be the right channel.
As another example, suppose the audio format of a stream is 5.1 32-bit floating point. A single PCM audio frame will be 6 * 4 = 24 bytes. Each of the six channels are a four-byte IEEE floating-point value; the channel order in Windows will be {Left, Right, Center, Low-Frequency Effects, Side Left, Side Right}.

The audio engine tries to run at as close to a 10 millisecond cadence as possible, subject to the two restrictions above. Given a "desired minimum interval" (in milliseconds), and a streaming format, and an "alignment requirement" in bytes, you can calculate the closest achievable interval (without going under the desired interval) as follows:

Note: this only works for uncompressed formats
aligned_buffer(desired_milliseconds, format, alignment_bytes)
desired_frames = nearest_integer(desired_milliseconds / 1000.0 * format.nSamplesPerSec)
alignment_frames = least_common_multiple(alignment_bytes, format.nBlockAlign) / format.nBlockAlign
actual_frames = ceiling(desired_frames / alignment_frames) * alignment_frames
actual_milliseconds = actual_frames / format.nSamplesPerSec * 1000.0

Here's a table of the actual buffer size (in frames and milliseconds), given a few typical inputs:

 Desired (milliseconds) Format Alignment (bytes) Desired frames Alignment (frames) Actual (frames) Actual (milliseconds) 10 44.1 kHz stereo 16-bit integer 128 441 32 448 10.16 10 48 kHz stereo 16-bit integer 128 480 32 480 10 10 44.1 kHz 5.1 16-bit integer 128 441 32 448 10.16 10 48 kHz 5.1 16-bit integer 128 480 32 480 10 10 44.1 kHz 5.1 24-bit integer 128 441 64 448 10.16 10 48 kHz 5.1 24-bit integer 128 480 64 512 10.66

So to be really precise, the buffer size is actually 640/63 = 10.158730 milliseconds.

• #### More on IAudioSessionControl and IAudioSessionControl2, plus: how to log a GUID

I decided to go back and push this a little further and see what information there was to dig out. Pseudocode:

CoCreate(IMMDeviceEnumerator)
MMDevice = IMMDeviceEnumerator::GetDefaultAudioEndpoint(...)
AudioSessionManager2 = MMDevice::Activate(...)
AudioSessionEnumerator = AudioSessionManager2::GetSessionEnumerator()

for each session in AudioSessionEnumerator {
AudioSessionControl = AudioSessionEnumerator::GetSession(...)
if (AudioSessionStateActive != AudioSessionControl::GetState()) { continue; }

AudioSessionControl::GetIconPath (usually blank)
AudioSessionControl::GetDisplayName (usually blank)
AudioSessionControl::GetGroupingParam

AudioSessionControl2 = AudioSessionControl::QueryInterface(...)
AudioSessionControl2::GetSessionIdentifier (treat this as an opaque string)
AudioSessionControl2::GetSessionInstanceIdentifier (treat this as an opaque string)
AudioSessionControl2::GetProcessId (some sessions span multiple processes)
AudioSessionControl2::IsSystemSoundsSession

AudioMeterInformation = AudioSessionControl::QueryInterface(...)
AudioMeterInformation::GetPeakValue

for each top level window in the process pointed to by AudioSessionControl2::GetProcessId {
Use WM_GETTEXTLENGTH and WM_GETTEXT to get the window text, if any
}
}

Here's the output of the new version of meters.exe.

>meters.exe
-- Active session #1 --
Icon path:
Display name:
Process ID: 11812 (single-process)
System sounds session: no
Peak value: 0.2837

-- Active session #2 --
Icon path:
Display name:
Grouping parameter: {a2e2e0f5-81bb-407e-b701-f4f3695f9dac}
Process ID: 15148 (single-process)
Session identifier: {0.0.0.00000000}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|\Device\HarddiskVolume1\Program Files (x86)\Internet Explorer\iexplore.exe%b{00000000-0000-0000-0000-000000000000}
Session instance identifier: {0.0.0.00000000}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|\Device\HarddiskVolume1\Program Files (x86)\Internet Explorer\iexplore.exe%b{00000000-0000-0000-0000-000000000000}|1%b15148
System sounds session: no
Peak value: 0.428589
HWND: 0x0000000001330B12
HWND: 0x0000000000361CA2
HWND: 0x00000000019A07A8
HWND: 0x0000000001411BF2
HWND: 0x0000000000B60706
HWND: 0x000000000231165A
HWND: 0x0000000002631472
HWND: 0x0000000000441D94

-- Active session #3 --
Icon path:
Display name:
Grouping parameter: {e191c91d-dc24-468d-b542-0d5f12ce8c48}
Process ID: 2324 (multi-process)
System sounds session: no
Peak value: 0.294137
HWND: 0x0000000002900C86 Windows Media Player

-- Active session #4 --
Icon path: @%SystemRoot%\System32\AudioSrv.Dll,-203
Display name: @%SystemRoot%\System32\AudioSrv.Dll,-202
Grouping parameter: {e7d6e107-ca03-4660-a067-1a1f3dc1619c}
Process ID: 0 (multi-process)
System sounds session: yes
Peak value: 0.0502903

-- Active session #5 --
Icon path:
Display name:
Grouping parameter: {2a3e30fb-2ded-471e-9c2f-cbd8572b2af2}
Process ID: 15948 (single-process)
Session instance identifier: {0.0.0.00000000}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|\Device\HarddiskVolume1\Program Files (x86)\VideoLAN\VLC\vlc.exe%b{00000000-0000-0000-0000-000000000000}|1%b15948
System sounds session: no
Peak value: 0.287567
HWND: 0x0000000000C8160C Opening Ceremony - VLC media player

Active sessions: 5

Part of this was logging the grouping parameter, which is a GUID. I've seen a lot of code that converts the string to a GUID and logs it using %s. Another way is to use a couple of macros:

#define GUID_FORMAT L"{%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x}"
#define GUID_VALUES(g) \
g.Data1, g.Data2, g.Data3, \
g.Data4[0], g.Data4[1], g.Data4[2], g.Data4[3], \
g.Data4[4], g.Data4[5], g.Data4[6], g.Data4[7]

...

GUID someGuid = ...;

LOG(L"The value of someGuid is " GUID_FORMAT L".", GUID_VALUES(someGuid));

Standard caveats about not using side effects inside a macro apply. For example, this would be a bug:

for (GUID *p = ...) {
LOG(L"p = " GUID_FORMAT L".", GUID_VALUES(*(p++)); // BUG!
}

Source, amd64 binaries, and x86 binaries attached.

• #### Getting the package full name of a Windows Store app, given the process ID

Last time I talked about enumerating audio sessions and showed an example which listed several Desktop apps and one Windows Store app.

It's possible to guess that this is a Windows Store app by the presence of the WWAHost.exe string in the session instance identifier. Don't rely on this, though; the session identifiers are opaque strings, and their formula can change at any time.

We were able to get some additional information on the Desktop apps by enumerating their top-level windows and reading the window text. But how do we get more information on the Windows Store app? And how do we even know it's a Windows Store app without cracking the session identifier?

By using the Application Model APIs - for example, GetPackageFullName.

Pseudocode:

... get a process ID...

OpenProcess(PROCESS_QUERY_LIMITED_USER_INFORMATION, FALSE, pid);

GetPackageFullName(...)

if APPMODEL_ERROR_NO_PACKAGE then the process has no associated package and is therefore not a Windows Store app.

Updated sample output:

-- Active session #4 --
Icon path:
Display name:
Grouping parameter: {8dbd87b0-9fce-4c27-b7ff-4b20b0dae1a3}
Process ID: 11644 (single-process)
System sounds session: no
Peak value: 0.395276
Package full name: Microsoft.ZuneMusic_2.0.132.0_x64__8wekyb3d8bbwe

Source and binaries attached.

• #### Even if someone's signaling right, they still have the right of way

I was driving to work this morning and I had an experience which vindicated my paranoia, and may even have passed it on to someone else.

I was heading East on NE 80th St approaching 140th Ave NE in Redmond. This is a two-way stop; drivers on 140th have the right of way and do not stop. Drivers on 80th (me) have to stop.

I came to a full stop and signaled right (I wanted to head South on 140th). A driver (let's call him Sam) pulled up behind me, also signaling right. There were three cars heading South on 140th, all of them signaling right (they wanted to head West on 80th).

At this point I had a conversation with myself that went something like this.

Well, Matt, you could turn right now. All those cars are turning right, so they won't hit you.
But wait, Matt. Those cars have the right of way. Sure they're signaling right. But that doesn't mean they'll actually turn right.
Yup, you're right, Matt. Better to wait to see what actually happens.

So I waited, and sure enough, all three cars actually turned right. So I suppose I could have gone. And more cars were feeding in to 140th from Redmond Way. And all of these cars were signaling right. And one was a school bus.

At this point Sam (remember Sam?) got impatient and honked his horn. This shocked me a little.

I imagine anyone who is from New York or Los Angeles is shaking their heads at me now. Not for waiting, but for being shocked. "He honked his horn? So what?"

(This is a cultural difference. In New York or Los Angeles, if you're waiting at a red light, you will get honked at as soon as the other guy's light turns yellow. But in Washington, the guy behind you will calmly wait through two full greens, then politely knock on your window and ask if everything is OK.)

I trust the school bus even less than the cars, so I let the school bus go.

The car behind the school bus is a minivan. He's signaling right, too. But I let him go as well... and he goes straight!

Behind the minivan, there's enough of a gap that I feel comfortable pulling out, so I do. And Sam pulls up to the line.

As I'm cruising down 140th, I glance in my rear-view mirror. I see a line of cars coming down 140th to the intersection I just left, all signaling right...

... and I see my friend Sam...

... patiently waiting.

May the Force be with you, Sam.

• #### Car Talk puzzler analysis - palindromic odometers

Last week's Car Talk question was again of mathematical interest - it dealt with palindromic numbers on a car's odometer. (This is not the first palindromic odometer question they've done.)

Read Car Talk's "Tommy's Drive to Work" puzzler question

Short version:

Tommy goes for a short drive (under an hour; possibly well under an hour) in his 19-year old new car. He notices that the odometer reading at the beginning and the end of the drive are both palindromes (we're given that his odometer shows six digits.) The question is, how many miles did he drive?

You're supposed to do a bunch of math, and then experience an epiphany when you realize that, against all odds, there's a single unique answer, even though the odometer readings themselves cannot be uniquely determined.

Alas, the problem is flawed. There are two perfectly good (and different) answers.

The first reading is given as a palindrome - the first three digits (let's call them a, b, c) are the same as the last three digits in reverse (c, b, a). So we can write the first number as abccba.

The second reading is also given as a palindrome, and we're given that it's a different palindrome (we infer that the odometer is not broken, and he drove at least a mile.) So we can write the second number as xyzzyx.

We want to find whether it's possible to get these two readings while driving a reasonably small distance. The distance driven is the difference between the odometer readings: xyzzyxabccba.

xyzzyxabccba
= (100001 x + 10010 y + 1100 z) – (100001 a + 10010 b + 1100 c)
= 100001 (xa) + 10010 (yb) + 1100 (zc)

Because xyzzyx > abccba, we know that xa. Also, if x = a, we know that yb. Finally, if x = a and y = b, we know that z > c (z cannot equal c in this case.) Let's look at these three cases separately.

Case 1: x = a, y = b, z > c
xyzzyxabccba
= 100001 (xa) + 10010 (yb) + 1100 (zc)
= 100001 (0) + 10010 (0) + 1100 (zc)
= 1100 (zc)

z and c can range from 0 to 9, and z > c, so (zc) can range from 1 to 9. So the smallest the distance can be is 1100 miles - for example, 250052 → 259952 (1100 miles.) This is a bit far for an hour's drive.

Case 2: x = a, y > b, no conditions imposed on z vs. c
xyzzyxabccba
= 100001 (xa) + 10010 (yb) + 1100 (zc)
= 100001 (0) + 10010 (yb) + 1100 (zc)
= 10010 (yb) + 1100 (zc)

y, b, z, and c can range from 0 to 9; y > b; and no conditions are imposed on z vs. c. (yb) can range from 1 to 9, (zc) can range from -9 to 9. So the smallest the distance can be is 100101 + 1100 (-9) = 110 miles - for example, 379973 → 380083 (110 miles.) It's certainly possible to drive 110 miles in an hour but not without attracting the attention of the local police!

Case 3: x > a, no conditions imposed on y vs. b or z vs. c
xyzzyxabccba
= 100001 (xa) + 10010 (yb) + 1100 (zc)

x, a, y, b, z, and c can range from 0 to 9; x > a; and no conditions are imposed on y vs. b, or z vs. c. (xa) can range from 1 to 9, (yb) and (zc) can range from -9 to 9. So the smallest the distance can be is 100001 (1) + 10010 (-9) + 1100 (-9) = 11 miles - for example, 499994 → 500005 (11 miles.) This is much more reasonable.

The intended answer, then, is 11 miles. There are 9 possible ways to get this distance with palindromic starting and ending readings:

099990 → 100001 (11 miles)
199991 → 200002 (11 miles)
299992 → 300003 (11 miles)
399993 → 400004 (11 miles)
499994 → 500005 (11 miles)
599995 → 600006 (11 miles)
699996 → 700007 (11 miles)
799997 → 800008 (11 miles)
899998 → 900009 (11 miles)

## Not a flaw

Do we consider numbers with unmatched leading zeros (like 001221) to be palindromes? I would say no. If we did this, it would open up a whole new field of answers such as 77 → 101 (24 miles.) The problem statement seems to imply that all six digits of the number, including leading zeros, need to participate in the palindrome. We can probably infer that Tommy's odometer is an analog odometer that actually shows leading zeros, rather than a digital odometer which hides them; this is consistent with the car being 19 years old.

## The flaw

All well and good. Alas, there's a flaw in this beautiful analysis - namely, odometers wrap. It's entirely possible for the assumption that xyzzyx > abccba to break down if Tommy started his drive with a number close to 999999, and his odometer wrapped around to 000000 during the drive.

999999 → 000000 (1 mile.)

There are other "wrapped" palindromes, but the next smallest are 998899 → 000000 (1101 miles) and 999999 → 001100 (1101 miles) which are even worse than case 1.

Could a 19-year-old car have a million miles on it?

That comes out to an average of 144.1 miles a day, which is high, but achievable (it's only 6 mph.) It's true that Tommy is unlikely to have put this many miles on a car if he lives only a mile from work, but remember that this is his new car (that is, it only recently came into his possession.)

• #### Linearity of Windows volume APIs - render session and stream volumes

We have talked about some of the volume APIs Windows exposes. We have also talked about what it means for a volume control to be linear in magnitude, linear in power, or linear in dB. We have also talked about how to read IAudioMeterInformation and how the limiter can attenuate full-scale signals.

The last post had a volume-linearity.exe which, when called with --signal, showed that IAudioMeterInformation is linear in amplitude.

Today we'll look at the --stream, --channel, and --session arguments, which explore the linearity of IAudioStreamVolume, IChannelAudioVolume, and ISimpleAudioVolume respectively. Each of these modes plays a half-scale square wave, then set the volume API to various levels, and reads the resulting IAudioMeterInformation. We use a half-scale square wave to avoid running afoul of the limiter; we expect a meter reading of 0.5 when the volume is set to 1.  The graphs below have their meter readings doubled to account for the fact that we're using a half-scale square wave rather than a full-scale.

Here's what we get for IAudioStreamVolume, graph-inated for your convenience:

And IChannelAudioVolume:

And ISimpleAudioVolume:

We already know that IAudioMeterInformation is linear in amplitude. We now know that IAudioStreamVolume, IChannelAudioVolume, and ISimpleAudioVolume have a linear effect (with slope 1 and intercept 0) on IAudioMeterInformation. We infer that IAudioStreamVolume, IChannelAudioVolume, and ISimpleAudioVolume are linear in amplitude.

• #### 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.

• #### Command-line app to set the desktop wallpaper

Working on Windows, I find myself installing Windows a lot.

I find that I like to change a lot of the settings that Windows offers to non-default values.  (That is, I'm picky.)

I have a script which automates some of these things, which I add to now and again.  Some of the bits of the script are straightforward, but once in a while the tweak itself is of interest.

One of the things I love about my work setup is the many large monitors.  So, one of the things I like to change is the desktop wallpaper image.

Changing the desktop wallpaper required some code, which makes it "of interest."  Here's the code.

// main.cpp

#include <windows.h>
#include <winuser.h>
#include <stdio.h>

int _cdecl wmain(int argc, LPCWSTR argv[]) {
if (1 != argc - 1) {
wprintf(L"expected a single argument, not %d\n", argc);
return -__LINE__;
}

if (!SystemParametersInfo(
SPI_SETDESKWALLPAPER,
0,
const_cast<LPWSTR>(argv[1]),
SPIF_SENDCHANGE
)) {
DWORD dwErr = GetLastError();
wprintf(L"SystemParametersInfo(...) failed with error %d\n", dwErr);
return -__LINE__;
}

wprintf(L"Setting the desktop wallpaper to %s succeeded.\n", argv[1]);
return 0;
}

Binaries attached.

Warning: if you pass a relative path to this tool, it won't qualify it for you, and the SystemParametersInfo call won't either - so the wallpaper you want won't be set, though all the calls will succeed.  Make sure to specify a fully-qualified path.

• #### How to create a shortcut from the command line

Working on Windows, I install Windows a lot.  This means a lot of my customizations have to be re-applied every time I install.  To save myself some time I created a script which applies some of them. Last time I showed how to set the desktop wallpaper from a command-line app.

This time, a script to create a shortcut.  The example usage creates a shortcut to Notepad and puts that in the "SendTo" folder.  I find this very useful because I often need to edit text files that have non-".txt" assocations.  (There are also other shortcuts I create with it.)

Here's the script:

>create-shortcut.vbs

If WScript.Arguments.Count < 2 Or WScript.Arguments.Count > 3 Then
WScript.Echo "Expected two or three arguments; got " & WScript.Arguments.Count
WScript.Echo "First argument is the file to create"
WScript.Echo "Second is the command to link to"
WScript.Echo "Third, if present, is the arguments to pass"
WScript.Quit
End If

Set shell = WScript.CreateObject("WScript.Shell")

If WScript.Arguments.Count = 3 Then
End If

• #### Generating primes using the Sieve of Eratosthenes plus a few optimizations

When solving Project Euler problems I frequently need to iterate over prime numbers less than a given n. A Sieve of Eratosthenes method quickly and easily finds the small prime numbers; there are more complicated methods that find larger prime numbers, but with a couple of tweaks the Sieve of Eratosthenes can get quite high.

A naive implementation for finding the set of primes below n will:

1. Allocate an array of n booleans, initialized to false.
2. Allocate an empty list
3. For each i in the range 2 to n:
1. If the boolean value at this index in the array is true, i is composite. Skip to the next value and check that.
2. If the boolean value at this index in the array is false, i is prime!
3. Add i to the list of primes
4. For each multiple of i in the range 2i to n, set the boolean value at that index in the array to true

There are a handful of simple optimizations that can be made to this naive implementation:

1. Step 3d) will have no effect until the multiple of i reaches i2, so the range can be changed to "i2 to n"
2. As a direct consequence of this, step 3d) can be skipped entirely once i2 passes n.
3. Instead of allocating an array of n booleans, an array of nbits will suffice.
4. All the even-indexed bits are set to true on the first pass. Manually recognize that 2 is prime, and only allocate bits for odd-numbered values. Change the outer loop in 3) to "in the range 3 to n", incrementing by two each time. Change the loop 3d) to increment by 2i each time.
5. Storing the list of primes takes a lot of memory - more than the sieve. Don't bother creating a list of primes, just write an enumerator that travels the sieve directly.

With these optimizations I can enumerate primes from 2 up to 5 billion (5 * 109) in about seven minutes.  Source and binaries attached.

>primes 5000000000
Will enumerate primes <= 5000000000 = 5e+009
Memory for sieve: 298.023 MB
Initialization complete: 983 milliseconds since start
Sieving to 70711
Sieving complete: 4.70292 minutes since start
Picking up the rest to 5000000000
Pickup complete: 6.12252 minutes since start
Primes: 234954223
1: 2
23495423: 442876981
46990845: 920233121
70486267: 1410555607
93981689: 1909272503
117477111: 2414236949
140972533: 2924158169
164467955: 3438252577
187963377: 3955819157
211458799: 4476550979
234954221: 4999999883
Enumerating complete: 7.43683 minutes since start
Freeing CPrimes object

There are more complicated sieves like the Sieve of Atkin which perform better but at the cost of being much more complex. So far I haven't had to resort to any of those.

• #### Programmatically grabbing a screenshot of the primary display

It's sometimes difficult to explain to people what my job actually is. "I test Windows sound." "Cool.  How does that work?"

A product like Windows has a lot of components that interact with each other.  If everything works, the user doesn't know that most of these components even exist; everything is invisible and seamless.

Most testing involves the connection ("interface") between two components.  "I test APIs."  To the uninitiated, this is just a word.  It sounds like "I test wakalixes."  "You test what, now?"

There are two interfaces which are easier to explain.  There's the software-to-hardware interface, where the driver talks to the hardware.  "I test the HD Audio, USB Audio, and Bluetooth audio class drivers."  "Huh?" "They make the speakers and the microphone work."  "Oh, cool.  So you sit around and use Skype all day?"

But the easiest of all to explain is the user interface.  "I make sure that the Sound Recorder app, the volume slider, and the Sound control panel work." "Oh, that!  I had this annoying problem once where..."

What does the test result for an invisible interface look like? A lot of logging.  "I expected this call to succeed; it returned this HRESULT."  "I poked the hardware like this and got a bluescreen."  "There seems to be an infinite loop here."  Lots of text.

Boring.

UI testing has logging too.  But with UI testing you can also... TAKE PICTURES!  A UI bug is a lot easier to understand (triage, and fix) if there's a screenshot attached (preferably with a big red rectangle highlighting the problem.)

It is therefore valuable to have an automatable utility that can take a screenshot and dump it to a file.  Here's one I cribbed together from the "Capturing an Image" sample code on http://msdn.microsoft.com/en-us/library/dd183402(v=VS.85).aspx.  Source and binaries attached.

This version only captures the main display, and not secondary monitors (if any.)

Pseudocode:

screen_dc = GetDC(nullptr);

memory_dc = CreateCompatibleDC(screen);

rect = GetClientRect(GetDesktopWindow());

hbmp = CreateCompatibleBitmap(screen_dc, rect);

SelectObject(memory_dc, hbmp);

BitBlt(memory_dc, rect, screen_dc);

bmp = GetObject(hbmp);

bytes = allocate enough memory

bytes = GetDIBits(screen_dc, bmp, hbmp)

file = CreateFile();

WriteFile(bytes);

• #### Mark your variadic logging function with __format_string to have PREfast catch format specifier errors

There are a handful of Problems (with a capital P) which occur over and over again in programming. One of them is Logging.

It is incredibly convenient to use the variadic printf function to log strings with values of common types embedded in them:

// spot the bug
LOG(L"Measurement shows %lg% deviation", 100.0 * abs(expected - actual) / expected);

However, printf is very error prone. It is very easy to use the wrong format specifier like %d instead of %Id, or to forget to escape a special character like % or \.
In particular, the above line contains a bug.

Static code analysis tools like PREfast are quite good at catching these kinds of errors. If my LOG macro was something like this, PREfast would catch the bug:

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

This works because PREfast knows that the first argument to wprintf is a format string, and can match up the format specifiers with the trailing arguments and verify that they match.

If you implement your own variadic logger function, though, PREfast doesn't necessarily know that the last explicit argument is a format specifier - you have to tell it. For example, PREfast will NOT catch format specifier issues if the LOG macro is defined like this:

// PREfast doesn't know Format is a format string
interface IMyLogger { virtual void Log(LPCWSTR Format, ...) = 0; };
extern IMyLogger *g_Logger;
#define LOG(fmt, ...) g_Logger->Log(fmt, __VA_ARGS__)

How do you tell it? Well, let's look at the declaration of wprintf. It's in (SDK)\inc\crt\stdio.h:

_CRTIMP __checkReturn_opt int __cdecl wprintf(__in_z __format_string const wchar_t * _Format, ...);

The relevant part here is __format_string. So the fixed IMyLogger declaration looks like this:

// Now PREfast can catch format specifier issues
interface IMyLogger { virtual void Log(__format_string LPCWSTR Format, ...) = 0; };
extern IMyLogger *g_Logger;
#define LOG(fmt, ...) g_Logger->Log(fmt, __VA_ARGS__)

• #### Beep sample

A question came in today about the Beep(...) API1 not being able to set the frequency of the beep that was generated. In order to confirm that it worked I whipped up a quick sample which would take the frequency (and duration) on the command line. Source and binaries attached.

For fun I added the ability to pass in the frequency using Scientific pitch notation. Note that A4 is about 431 Hz using this scale, rather than the more standard 440 Hz2.

for (int i = 1; i + 1 < argc; i += 2) {

ULONG frequency;
HRESULT hr = HertzFromScientificPitchNotation(argv[i], &frequency);
if (FAILED(hr)) { return -__LINE__; }

ULONG duration;
hr = UlongFromString(argv[i + 1], &duration);
if (FAILED(hr)) { return -__LINE__; }

if (!Beep(frequency, duration)) {
LOG(L"Beep(%u, %u) failed: GetLastError() = %u", frequency, duration, GetLastError());
return -__LINE__;
}
}

So, for example, you can play a certain well-known tune via Beep() using this command:

>beep.exe C3 2000 G3 2000 C4 4000 E4 500 Eb4 3500 C3 500 G2 500 C3 500 G2 500 C3 500 G2 500 C3 2000

1 More on the Beep(...) API:

The official Beep(...) documentation

A couple of blog posts from Larry Osterman:
Beep Beep
What’s up with the Beep driver in Windows 7?

2 If you want the more standard pitch, change this line:

double freq = 256.0;

To this:

double freq = 440.0 * pow(semitoneRatio, -9.0); // C4 is 9 semitones below A4

• #### Excruciating rhymes

I was watching How the Grinch Stole Christmas and I was struck by this rhyme (from the song  "You're a Mean One, Mr. Grinch:")

You're a nauseous super naus!
You're a dirty crooked jockey, and you drive a crooked hoss

-- Dr. Seuss, How the Grinch Stole Christmas

I tried to see what other particularly excruciating rhymes I could remember.  I came up with two:

You know, that little guy, he's got me feeling all contempt-ey:
He takes his boat out loaded up and brings it back in empty.

-- Phil Vischer, Lyle the Kindly Viking

And then of course:

In short, when I've a smattering of elemental strategy,
You'll say a better Major-General had never sat a-gee!

-- W. S. Gilbert, The Pirates of Penzance

• #### Teaching someone to fish and the AKS primality test

This morning my wife (whom I love and adore) woke me up at 3:00 AM with an urgent question.

"Hey!" she said, shaking me awake.

"Is 19 prime?"

...

Like a fool, I answered her.  "Yes.  Yes it is."  Off she went.

This is a true response, but not a correct response.  I realized shortly afterwards that a correct response would look more like:

I'm glad you asked me that. dear.  Eratosthenes, the Greek mathematician, discovered a very efficient way to list primes in about 200 BC that is still in use today.  You start by writing out all the numbers from 1 to 19: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19.  1 is a very special number (it's the multiplicative identity, or what algebraists would call a unit) so we put a square around it.  The first number we didn't consider was 2, so we circle it - that means it's prime - and then cross out every multiple of 2 after that.  Going back, the first number we didn't consider was 3... and so on until we get 1 2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19.  A common optimization is to realize that after circling a prime p, the first number you cross out (that wasn't crossed out before) is always p2, which means that after circling a number you can immediately jump to its square, and also means you can stop crossing out altogether once you hit p> N...

This would allow her to fish rather than waking me up when she wanted a fish.

An even better response would have been:

It's funny you've asked me that.  Number theorists and cryptanalysts have considered this question for thousands of years.  Eratosthenes' method (see above) is a very simple way to find all the primes below a given number, but an efficient way to determine whether a given number is prime was found only very recently.

In practice, the test that is usually used is the randomized version of the Miller-Rabin test.  Although this is nondeterministic, it is very fast indeed, and will tell you to a very high degree of certainty whether the given number is prime.  This usually suffices.

There is a deterministic version of the Miller-Rabin test too, which is guaranteed to tell you with perfect certainty whether the given number is prime.  But it only works if you believe in the generalized Riemann hypothesis.  Most mathematicians nowadays believe the hypothesis, but no-one has (yet) been able to prove it.

Amazingly, in 2002 three mathematicians named Manindra Agrawal, Neeraj Kayal, and Nitin Saxena came up with a deterministic, proven, polynomial-time (specifically, polynomial in the number of digits in the input) method for telling whether a given number is prime.   This is known as the AKS primality test.  The most striking thing about this test is its simplicity - if something this straightforward can be found after thousands of years of looking, what else out there remains to be found?

Such a response would probably prevent her from waking me again for any mathematical problem at all.  Boo-ya.

My own Perl implementation follows:

use strict;
# use bignum;

print <<USAGE and exit 0 unless @ARGV;
$0 [-v] n Use the AKS primality test to check whether n is prime -v adds verbose log spew USAGE sub is_power($$); sub ceil_log2(); sub first_r($$); sub check_gcds($$); sub check_polynomials($$$);
sub gcd($$); sub totient(); sub polypow($$\@);
sub polymult($$\@\@); sub polyeq(\@\@); my verbose = ARGV[0] eq "-v"; shift @ARGV if verbose; die "Expected only one argument" unless 1 == @ARGV; my n = shift; # step 0: restrict to integers >= 2 print "n is not an integer and so is NEITHER PRIME NOR COMPOSITE\n" and exit 0 unless int(n) == n; print "n < 2 and so is NEITHER PRIME OR COMPOSITE\n" and exit 0 unless n >= 2; # step 1: check if the number is a power of some lower number. # this can be done quickly by iterating over the exponent (2, 3, ...) # and doing a binary search on the base. # we start at the top and work down for performance reasons; # several subroutines need to know ceil(log2(n)) so we calculate it once and pass it around. my log2_n = ceil_log2(n); is_power(n, log2_n) and exit 0; print "Not a power.\n"; # step 2: find the smallest r such that o_r(n) > (log2 n)^2 # where o_r(n) is the multiplicative order of n mod r # that is, the smallest k such that n^k == 1 mod r my r = first_r(n, log2_n); print "r = r\n"; # step 3: for all a between 2 and r inclusive, check whether gcd(a, n) > 1 check_gcds(n, r) or exit 0; # step 4: if r >= n, we're done if (r >= n) { print "r >= n so n is PRIME\n"; exit 0; } # step 5: for all a between 1 and floor( sqrt(phi(r)) log2(n) ) # check whether (x + a)^n = x^n + a mod x^r - 1, n check_polynomials(n, r, log2_n) or exit 0; # step 6: if we got this far, n is prime print "n is PRIME\n"; sub is_power($$) {
my $n = shift; my$log2_n = shift; # actually ceil(log2(n))

print "Checking for power-ness...\n";

# we consider numbers of the form b^i
# we iterate over the exponent i
# starting at i = ceil(log2(n)) and working down to i = 2
#
# for each exponent we do a binary search on the base
# the lowest the base can be is 2
# and the highest the base can be (initially) is 2
#
# we set up bounds on the base that are guaranteed to
# surround the actual base
my $b_low = 1; # 1 ^ ceil(log2(n)) = 1 < n my$b_high = 3; # 3 ^ ceil(log2(n)) > 2 ^ log2(n) = n

for (my $i =$log2_n; $i >= 2;$i--) {
print "\tb^$i\n" if$verbose;

# let's check that the bounds are really correct
die "$b_low ^$i is not < $n" unless$b_low ** $i <$n;
die "$b_high ^$i is not > $n" unless$b_high ** $i >$n;

# do a binary search to find b such that b ^ i = n
while ($b_high -$b_low > 1) {
print "\t\tb^$i: b is between$b_low and $b_high\n" if$verbose;
my $b = int(($b_low + $b_high)/2); my$t = $b **$i;
if ($t ==$n) {
print "$n =$b^$i;$n is COMPOSITE\n";
return 1;
}

($t >$n ? $b_high :$b_low) = $b; } # as we pass from the exponent (say, 5) # to the exponent below (say, 4) # we need to reconsider our bounds # # b_low can remain the same because b ^ (i - 1) is even less than b ^ i # OPEN ISSUE: can we even raise b_low? # # but we need to raise b_high since b ^ i > n does NOT imply b ^ (i - 1) > n # # we'll square b_high; b ^ i > n => (b ^ 2) ^ (i - 1) = b ^ (2 i - 2) > n # since i >= 2 # # OPEN ISSUE: is there a better way to raise this higher bound? Does this help much?$b_high *= $b_high; } # nope, not a power return 0; } sub ceil_log2($) {
my $n = shift; my$i = 0;
my $t = 1; until ($t >= $n) {$i++;
$t *= 2; } return$i;
}

sub first_r($$) { my n = shift; my log2_n = shift; # actually ceil(log2(n)) my s = log2_n ** 2; print "Looking for the first r where o_r(n) > s...\n"; # for each r we want to find the smallest k such that # n^k == 1 mod r my r; for (r = 2; ; r++) { # print "\tTrying r...\n"; # find the multiplicative order of n mod r my k = 1; my t = n % r; until (1 == t or k > s) { t = (t * n) % r; k++; } if (k > s) { # print "\to_r(n) is at least k\n"; last; } else { # print "\to_r(n) = k\n"; } } return r; } sub check_gcds($$) {
my ($n,$r) = @_;

print "Checking GCD($n, a) for a = 2 to$r...\n";

for (my $a = 2;$a <= $r;$a++) {
my $g = gcd($n, $a); next if ($g == $n); # this is OK if (1 !=$g) {
print "gcd($n,$a) = $g;$n is COMPOSITE\n";
return 0;
}
}

print "All GCDs are 1 or $n\n"; return 1; } sub gcd($$) { my (x, y) = @_; (x, y) = (y, x) unless x > y; while (y) { (x, y) = (y, x % y); } return x; } sub check_polynomials($$$) {
my $n = shift; my$r = shift;
my $log2_n = shift; # actually ceil(log2(n)) # iterate over a from 1 to floor( sqrt(phi(r)) log2(n) ) # for each a, check whether the polynomial equality holds: # (x + a)^n = x^n + a mod (x^r - 1, n) # if it fails to hold, the number is composite # # first we need to evaluate phi(r) so we can determine the upper bound # OPEN ISSUE: this seems to be a potential weakness in the algorithm # because the usual way to evaluate phi(r) is to find the prime factorization of r # and then form the product r*PI(1 - 1/p) where the product ranges over all primes # which divide r my$phi = totient($r); # a < sqrt(phi(r)) * log2(n) => a^2 < phi(r) * (log2(n))^2 my$a2_max = $phi *$log2_n * $log2_n; print "Checking polynomials up to roughly ", int sqrt($a2_max), "...\n";

for (my $a = 1;$a * $a <=$a2_max; $a++) { print "\ta =$a...\n" if $verbose; # polynomials are of the form (c0, c1, c2, ..., ci, ...) # which corresponds to c0 + c1 x + c2 x^2 + ... + ci x^i + ...) my @x = (0, 1); my @x_plus_a = ($a % $n, 1); my @lhs = polypow($n, $r, @x_plus_a); # POTENTIAL OPTIMIZATION: # x^n + a mod (x^r - 1) is just x^(n % r) + a # and we know n % r != 0 my @rhs = polypow($n, $r, @x); # x^n$rhs[0] = ($rhs[0] +$a) % $n; # + a next if polyeq(@lhs, @rhs); print "(x +$a)^$n is not equal to x^$n + $a mod(x^$r - 1, $n)\n"; print "So$n is COMPOSITE\n";
return 0;
}

return 1;
}

sub totient($) { my$r = shift;

print "Finding the Euler totient of $r\n"; # we'll do a trial division to find the totient # there are faster ways that use a sieve # but we don't know how big r is my$t = $r; # by construction p will always be prime when it is used # OPEN ISSUE: this might be slow for (my$p = 2; $r > 1;$p++) {
next if $r %$p;

print "\t$p is a factor\n" if$verbose;
# decrease the totient
$t /=$p;
$t *=$p - 1;

# decrease r
$r /=$p; # we know there's at least one factor of p
$r /=$p until $r %$p; # there might be more
}

print "Totient is $t\n"; return$t;
}

sub polypow($$\@) { my n = shift; # this is both the mod and the exponent my r = shift; my @base = @{ +shift }; my exp = n; my @result = (1); # 1 # print "\t(", join(" ", @base), ")^exp mod (x^r - 1, n)\n" if verbose; # basic modpow routine, but with polynomials while (exp) { if (exp % 2) { @result = polymult(n, r, @result, @base); } exp = int (exp / 2); @base = polymult(n, r, @base, @base); } # print "\t= (", join(" ", @result), ")\n" if verbose; return @result; } sub polymult($$\@\@) {
my $n = shift; my$r = shift;
my @first = @{ +shift };
my @second = @{ +shift };

# print "\t\t(", join(" ", @first), ") * (", join(" ", @second), ") mod (x^$r - 1,$n)\n" if $verbose; my @result = (); # first do a straight multiplication first * second my$s = @second - 1;
for (my $i = @first - 1;$i >= 0; $i--) { for (my$j = $s;$j >= 0; $j--) { my$k = $i +$j;
$result[$k] += $first[$i] * $second[$j];
$result[$k] %= $n; } } # then do a straight mod x^r - 1 # consider a polynomial # c0 + ... + ck x^k # with k >= r # we can subtract ck (x^r - 1) # without changing the mod value # the net effect is to eliminate the x^k term # and add ck to the x^(k - r) term for (my$i = @result - 1; $i >=$r; $i--) { my$j = $i -$r;
$result[$j] += $result[$i];
$result[$j] %= $n; pop @result; } # eliminate any leading zero terms for (my$i = @result - 1; 0 == $result[$i]; $i--) { pop @result; } # print "\t\t= (", join(" ", @result), ")\n" if$verbose;
return @result;
}

sub polyeq(\@\@) {
my @lhs = @{ +shift };
my @rhs = @{ +shift };

# print "(", join(" ", @lhs), ") = (", join(" ", @rhs), ")?\n" if $verbose; return 0 unless @lhs == @rhs; for (my$i = @lhs - 1; $i >= 0;$i--) {
return 0 unless $lhs[$i] == $rhs[$i];
}

return 1;
}

Here's the output when I run it on 19:

>perl -w aks.pl 19
Checking for power-ness...
Not a power.
Looking for the first r where o_r(19) > 25...
r = 19
Checking GCD(19, a) for a = 2 to 19...
All GCDs are 1 or 19
19 >= 19 so 19 is PRIME

And here's the output with a bigger input:

>perl -w aks.pl 99
Checking for power-ness...
Not a power.
Looking for the first r where o_r(997) > 100...
r = 103
Checking GCD(997, a) for a = 2 to 103...
All GCDs are 1 or 997
Finding the Euler totient of 103
Totient is 102
Checking polynomials up to roughly 100...
997 is PRIME
• #### unattend.xml: turning on Remote Desktop automatically

Here are the portions of my unattend.xml file which are needed to turn on Remote Desktop automatically.

This piece flips the "no remote desktop" kill switch to "allow."

<settings pass="specialize">
...
<component name="Microsoft-Windows-TerminalServices-LocalSessionManager" ...>
<fDenyTSConnections>false</fDenyTSConnections>

That's not enough; it is also necessary to poke a hole in the firewall to allow inbound connections.  I use an indirect string for the Group name, to allow for installing localized builds.  This points to the "Remote Desktop" feature group.

<settings pass="specialize">
...
<component name="Networking-MPSSVC-Svc" ...>
<FirewallGroups>
<Active>true</Active>
<Profile>all</Profile>
<Group>@FirewallAPI.dll,-28752</Group>

If your user account is a member of the "Administrators" group, you're done:

<settings pass="oobeSystem">
<component name="Microsoft-Windows-Shell-Setup" ...>
<UserAccounts>
<LocalAccounts>
<PlainText>true</PlainText>

But if you're like me and you don't want to live in the Administrators group, you need to join the Remote Desktop Users group to be able to log in remotely:

<settings pass="oobeSystem">
<component name="Microsoft-Windows-Shell-Setup" ...>
<UserAccounts>
<DomainAccounts>
<Domain>redmond.corp.microsoft.com</Domain>
<Group>RemoteDesktopUsers</Group>
<Name>MatEer</Name>

• #### Weighing the Sun and the Moon

In an earlier post I mentioned how the Cavendish experiment allowed us to weigh the Earth - to determine the mass of the Earth mE.  Newton knew the acceleration due to gravity on the surface of the Earth and was able to use that to find the product G mE; Cavendish determined G directly, and was thus able to solve for mE.  He would also have been able to find the mass of the sun as follows:

mE aE = G mE mS / rE2

G, rE, and aE = vE2 / rE are known, so we can solve for mS.

But calculating the mass of the moon is trickier.

Once we were able to put a satellite around the moon we could measure its orbital radius and speed, deduce the acceleration, and use that plus the known G to calculate the mass of the moon.  But prior to that we were limited to techniques like:

The moon does not exactly orbit the Earth, but instead orbits the center of mass of the moon/Earth system.  By careful observation we can determine where this center of mass is.  We can then measure the distance between the center of mass and the Earth's center.  This plus the known mass of the Earth and the distance of the Earth from the Moon allows us to determine the mass of the Moon.

If we're lucky enough to see a foreign object come close to the moon, we can determine how much it is accelerated by the Moon.  This will allow us to determine the mass of the Moon using the technique above.  (We won't be able to determine the mass of the foreign object, but we don't need it.)

When the USSR launched Sputnik, American scientists really wanted to know what its mass was.  But because none of the techniques above were useful, they were unable to determine it.

• #### Programmatically rearranging displays

Most of my test machines and my laptop have a single display; but I have two dev machines which are each connected to two displays.

When I clean install Windows, I sometimes need to rearrange the displays:

Since I clean install Windows frequently, I wrote myself a little C++ app which does this programmatically using EnumDisplayDevices / EnumDisplaySettings / ChangeDisplaySettingsEx.

Source and binaries attached.

Pseudocode:

for (each device returned by EnumDisplayDevices) {

grab the position and the height/width using EnumDisplaySettings

}

calculate the desired position of the secondary monitor

Set it using ChangeDisplaySettingsEx with DM_POSITION

Call as:

>swapmonitors
Moved secondary monitor to (1920, 0)

EDIT: Oops: 0 should be CDS_GLOBAL | CDS_UPDATEREGISTRY, to make the settings apply to all users, and to persist across display resets / reboots

LONG status = ChangeDisplaySettingsEx(
nameSecondary,
&mode,
nullptr, // reserved
CDS_GLOBAL | CDS_UPDATEREGISTRY, // was 0
nullptr // no video parameter
);

• #### Windows Sound test team rowing morale event

Last Friday the Windows Sound test team went kayaking.  We went to the Agua Verde paddle club and kayaked around Union Bay for a while.

Here's the route we took:

More detail:

http://connect.garmin.com/activity/179545084

• #### Grabbing large amounts of text from STDIN in O(n) time

Last time I blogged about an O(n log n) solution to finding the longest duplicated substring in a given piece of text; I have since found an O(n) algorithm, which I linked to in the comments.

But my blog post used an O(n2) algorithm to read the text from STDIN! It looked something like this:

while (!done) {
grab 2 KB of text
allocate a new buffer which is 2 KB bigger
copy the old text and the new text together into the new buffer
free the old buffer
}

There are two better algorithms:

while (!done) {
grab an amount of text equal to the amount we've grabbed so far
allocate a new buffer which is twice as large as the last buffer
copy the old text and the new text together into the new buffer
free the old buffer
}

And:

while (!done) {
grab 2 KB of text
add this to the end of a linked list of text chunks
}

allocate a buffer whose size is the total size of all the chunks added together
walk the linked list and copy the text of each chunk into the buffer

Both "better" algorithms are O(n) but the latter wastes less space.

Here's the improved code:

struct Chunk {
WCHAR text[1024];
Chunk *next;

Chunk() : next(nullptr) { text[0] = L'\0'; }
};

class DeleteChunksOnExit {
public:
DeleteChunksOnExit() : m_p(nullptr) {}
~DeleteChunksOnExit() {
Chunk *here = m_p;
while (here) {
Chunk *next = here->next;
delete here;
here = next;
}
}
void Set(Chunk *p) { m_p = p; }

private:
Chunk *m_p;
};

...

Chunk *tail = nullptr;

DeleteChunksOnExit dcoe;

size_t total_length = 0;

bool done = false;
while (!done) {
Chunk *buffer = new Chunk();
if (nullptr == buffer) {
LOG(L"Could not allocate memory for buffer");
return nullptr;
}

// this runs on the first pass only
tail = buffer;
dcoe.Set(buffer);
} else {
tail->next = buffer;
tail = buffer;
}

if (fgetws(buffer->text, ARRAYSIZE(buffer->text), stdin)) {
total_length += wcslen(buffer->text);
} else if (feof(stdin)) {
done = true;
} else {
return nullptr;
}
}

// gather all the allocations into a single string
size_t size = total_length + 1;
WCHAR *text = new WCHAR[size];
if (nullptr == text) {
LOG(L"Could not allocate memory for text");
return nullptr;
}
DeleteArrayOnExit<WCHAR> deleteText(text);

WCHAR *temp = text;
for (Chunk *here = head; here; here = here->next) {
if (wcscpy_s(temp, size, here->text)) {
LOG(L"wcscpy_s returned an error");
return nullptr;
}

size_t len = wcslen(here->text);
temp += len;
size -= len;
}

deleteText.Cancel();
return text;
}

• #### Changing the desktop wallpaper using IDesktopWallpaper

About a year ago I wrote about how to change the desktop wallpaper using SystemParametersInfo(SPI_SETDESKWALLPAPER).

Windows 8 desktop apps (not Store apps) can use the new IDesktopWallpaper API to get a more fine level of control.  So I wrote an app which uses the new API, though I just set the background on all monitors to the same image path, and I don't exercise any of the advanced features of the API.

Pseudocode:

CoInitialize
CoCreateInstance(DesktopWallpaper)
pDesktopWallpaper->SetWallpaper(NULL, full-path-to-image-file)
pDesktopWallpaper->Release()
CoUninitialize

Usage:

>desktopwallpaper.exe "%userprofile%\pictures\theda-bara.bmp"
Setting the desktop wallpaper to C:\Users\MatEer\pictures\theda-bara.bmp succeeded.

Source and binaries attached

• #### Programmatically adding a folder to a shell library (e.g., the Music library)

I wrote a selfhost tool which allows me to add a folder (for example, C:\music) to a shell library (for example, the Music library.)

This was before I found out about the shlib shell library sample which Raymond Chen blogged about.  If you're looking for a sample on how to manipulate shell libraries, prefer that one to this.

Pseudocode:

CoInitialize
pShellLibrary->Commit()
CoUninitialize

Usage:

>shelllibrary