Matthew van Eerde's web log

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

• Sample: how to enumerate waveIn and waveOut devices on your system

This shows how to call waveInGetNumDevs, waveInGetDevCaps, waveOutGetNumDevs, and waveOutGetDevCaps.

// main.cpp

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

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

int _cdecl wmain() {

UINT devs = waveInGetNumDevs();
LOG(L"waveIn devices: %u", devs);
for (UINT dev = 0; dev < devs; dev++) {
WAVEINCAPS caps = {};
MMRESULT mmr = waveInGetDevCaps(dev, &caps, sizeof(caps));

if (MMSYSERR_NOERROR != mmr) {
LOG(L"waveInGetDevCaps failed: mmr = 0x%08x", mmr);
return mmr;
}

LOG(
L"-- waveIn device #%u --\n"
L"Manufacturer ID: %u\n"
L"Product ID: %u\n"
L"Version: %u.%u\n"
L"Product Name: %s\n"
L"Formats: 0x%x\n"
L"Channels: %u\n"
L"Reserved: %u\n"
,
dev,
caps.wMid,
caps.wPid,
caps.vDriverVersion / 256, caps.vDriverVersion % 256,
caps.szPname,
caps.dwFormats,
caps.wChannels,
caps.wReserved1
);
}

devs = waveOutGetNumDevs();
LOG(L"waveOut devices: %u", devs);
for (UINT dev = 0; dev < devs; dev++) {
WAVEOUTCAPS caps = {};
MMRESULT mmr = waveOutGetDevCaps(dev, &caps, sizeof(caps));

if (MMSYSERR_NOERROR != mmr) {
LOG(L"waveOutGetDevCaps failed: mmr = 0x%08x", mmr);
return mmr;
}

LOG(
L"-- waveOut device #%u --\n"
L"Manufacturer ID: %u\n"
L"Product ID: %u\n"
L"Version: %u.%u\n"
L"Product Name: %s\n"
L"Formats: 0x%x\n"
L"Channels: %u\n"
L"Reserved: %u\n"
L"Support: 0x%x\n"
L"%s%s%s%s%s"
,
dev,
caps.wMid,
caps.wPid,
caps.vDriverVersion / 256, caps.vDriverVersion % 256,
caps.szPname,
caps.dwFormats,
caps.wChannels,
caps.wReserved1,
caps.dwSupport,
((caps.dwSupport & WAVECAPS_LRVOLUME) ?       L"\tWAVECAPS_LRVOLUME\n" :       L""),
((caps.dwSupport & WAVECAPS_PITCH) ?          L"\tWAVECAPS_PITCH\n" :          L""),
((caps.dwSupport & WAVECAPS_PLAYBACKRATE) ?   L"\tWAVECAPS_PLAYBACKRATE\n" :   L""),
((caps.dwSupport & WAVECAPS_VOLUME) ?         L"\tWAVECAPS_VOLUME\n" :         L""),
((caps.dwSupport & WAVECAPS_SAMPLEACCURATE) ? L"\tWAVECAPS_SAMPLEACCURATE\n" : L"")
);
}

return 0;
}

On my system this outputs:

waveIn devices: 3
-- waveIn device #0 --
Manufacturer ID: 1
Product ID: 65535
Version: 0.0
Product Name: Microphone (High Definition Aud
Formats: 0xfffff
Channels: 2
Reserved: 0

-- waveIn device #1 --
Manufacturer ID: 1
Product ID: 65535
Version: 0.0
Product Name: Digital Audio (S/PDIF) (High De
Formats: 0xfffff
Channels: 2
Reserved: 0

-- waveIn device #2 --
Manufacturer ID: 1
Product ID: 65535
Version: 0.0
Product Name: CD Audio (High Definition Audio
Formats: 0xfffff
Channels: 2
Reserved: 0

waveOut devices: 2
-- waveOut device #0 --
Manufacturer ID: 1
Product ID: 65535
Version: 0.0
Product Name: Headphones (High Definition Aud
Formats: 0xfffff
Channels: 2
Reserved: 0
Support: 0x2e
WAVECAPS_LRVOLUME
WAVECAPS_PLAYBACKRATE
WAVECAPS_VOLUME
WAVECAPS_SAMPLEACCURATE

-- waveOut device #1 --
Manufacturer ID: 1
Product ID: 65535
Version: 0.0
Product Name: Digital Audio (S/PDIF) (High De
Formats: 0xfffff
Channels: 2
Reserved: 0
Support: 0x2e
WAVECAPS_LRVOLUME
WAVECAPS_PLAYBACKRATE
WAVECAPS_VOLUME
WAVECAPS_SAMPLEACCURATE

Source and binaries attached.

• How many numbers are straights?

As many people, I have to deal with a lot of numbers all the time (bug numbers, changelist numbers, tracking numbers, ...) and as a mathematician I sometimes notice when numbers have peculiar properties.

For example, I recently ran into 152463, which is a straight (made up of consecutive digits, not necessarily in order.)  I then ran into 35426, which is also a straight.  Is this odd?

To put it another way - what proportion of numbers are straights?

We consider only non-negative integer numbers {0, 1, 2, ... }.  No duplicate digits are allowed, so the very last straight is 9,876,543,210.

Break it down by the length of the number in digits.  For example, how many four-digit numbers are there?  We can choose any number from 1-9 for the first digit, and any number from 0-9 for each of the other three digits; so there are 9 * 103 numbers of length 4.

How many of these are straights?  There are seven ways to choose a set of four consecutive digits to make up a four-digit straight: {0,1, 2, 3}, {1, 2, 3, 4}, {2, 3, 4, 5}, {3, 4, 5, 6}, {4, 5, 6, 7}, {5, 6, 7, 8}, {6, 7, 8, 9}.

Each of these seven ways can then be shuffled to make the straights themselves.  For six of these seven sets of digits, all possible shufflings are allowed; there are 4! shufflings for each set.  This gives 6 * 4! straights.

But for {0, 1, 2, 3}, we have to be careful not to end up with 0 as a leading digit.  We choose the leading digit first out of the set {1, 2, 3} (there are three ways to do this) and then we have complete freedom to shuffle the three remaining digits (including 0.)  This gives 3 * 3! straights.

So there are 6 * 4! + 3 * 3! straights which are four digits long.

Considering all possible lengths from 1 to 10 (we'll consider 0 as a number of length 1) gives the following table:

 Length Numbers Straights % Straights 1 10 10 100.000% 2 9 * 101 17 18.889% 3 9 * 102 46 5.111% 4 9 * 103 162 1.800% 5 9 * 104 696 0.773% 6 9 * 105 3480 0.387% 7 9 * 106 19,440 0.216% 8 9 * 107 115,920 0.129% 9 9 * 108 685,440 0.076% 10 9 * 109 3,265,920 0.036% Total 1010 40,91,131 0.041%

Since roughly 1% of five-digit numbers are straights, it is not surprising that I see them that often.

• My unattend.xml file

As a tester on Windows 8 I install Windows on my dev machine very frequently.

I use F12 to boot from the network into WinPE, then I run a .bat file which looks something like this:

@echo off
setlocal enabledelayedexpansion

set FANCYLANG=qps-plocm

del unattend-processed.xml
for /f "usebackq delims=" %%l in (type unattend-template.xml) do (
set line=%%l
set line=!line:#FANCY_LANG#=%FANCY_LANG%!
echo !line! >> unattend-processed.xml
)

setup.exe /unattend:unattend-processed.xml

This takes my template unattend.xml file, injects various parameters, and calls setup.exe.

The template unattend.xml follows in all of its glory.  We'll take a closer look at some of the things in future posts.

<?xml version="1.0" encoding="utf-8"?>
<unattend xmlns="urn:schemas-microsoft-com:unattend">
<settings pass="windowsPE">
<component name="Microsoft-Windows-Setup" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<UserData>
<ProductKey>
<WillShowUI>OnError</WillShowUI>
</ProductKey>
<AcceptEula>true</AcceptEula>
<FullName>Matthew van Eerde</FullName>
<Organization>Microsoft</Organization>
</UserData>
<DiskConfiguration>
<CreatePartitions>
<Order>1</Order>
<Extend>true</Extend>
<Type>Primary</Type>
</CreatePartition>
</CreatePartitions>
<WillWipeDisk>true</WillWipeDisk>
<DiskID>0</DiskID>
</Disk>
</DiskConfiguration>
<ImageInstall>
<OSImage>
<WillShowUI>OnError</WillShowUI>
<InstallToAvailablePartition>true</InstallToAvailablePartition>
</OSImage>
</ImageInstall>
</component>
<component name="Microsoft-Windows-International-Core-WinPE" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<SetupUILanguage>
<UILanguage>#FANCY_LANG#</UILanguage>
</SetupUILanguage>
<InputLocale>0409:00000409</InputLocale>
<UserLocale>en-US</UserLocale>
<SystemLocale>en-US</SystemLocale>
<UILanguage>#FANCY_LANG#</UILanguage>
</component>
</settings>
<settings pass="specialize">
<component name="Microsoft-Windows-UnattendedJoin" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<Identification>
<Credentials>
<Domain>redmond.corp.microsoft.com</Domain>
</Credentials>
<JoinDomain>ntdev.corp.microsoft.com</JoinDomain>
</Identification>
</component>
<component name="Microsoft-Windows-Shell-Setup" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<ComputerName>MATEER-Q</ComputerName>
<RegisteredOwner>Matthew van Eerde</RegisteredOwner>
<RegisteredOrganization>Microsoft</RegisteredOrganization>
</component>
<component name="Microsoft-Windows-TerminalServices-LocalSessionManager" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<fDenyTSConnections>false</fDenyTSConnections>
</component>
<component name="Networking-MPSSVC-Svc" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<FirewallGroups>
<Active>true</Active>
<Profile>all</Profile>
<Group>@FirewallAPI.dll,-28752</Group>
</FirewallGroup>
</FirewallGroups>
</component>
</settings>
<settings pass="oobeSystem">
<component name="Microsoft-Windows-Shell-Setup" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<OOBE>
<HideEULAPage>true</HideEULAPage>
<NetworkLocation>Work</NetworkLocation>
<ProtectYourPC>3</ProtectYourPC>
<HideOnlineAccountScreens>true</HideOnlineAccountScreens>
<HideLocalAccountScreen>true</HideLocalAccountScreen>
<HideWirelessSetupInOOBE>true</HideWirelessSetupInOOBE>
</OOBE>
<UserAccounts>
<LocalAccounts>
<PlainText>true</PlainText>
</LocalAccount>
</LocalAccounts>
<DomainAccounts>
<Domain>redmond.corp.microsoft.com</Domain>
<Group>RemoteDesktopUsers</Group>
<Name>MatEer</Name>
</DomainAccount>
</DomainAccountList>
</DomainAccounts>
</UserAccounts>
<TimeZone>Pacific Standard Time</TimeZone>
<AutoLogon>
<PlainText>true</PlainText>
<Domain>redmond.corp.microsoft.com</Domain>
<Enabled>true</Enabled>
<LogonCount>1</LogonCount>
</AutoLogon>
</component>
</settings>
</unattend>

• Programmatically setting a local user account to never expire its password

As a Windows tester, I install Windows on my own machines a lot (this is known internally as "selfhosting", or "dogfooding", or "ice cream-ing".)

One of my little idiosyncracies is I like to run as a non-administrative user.  That is, I don't add my domain account to the local Administrators group.

Instead, I create a local "Admin" account with a known (to me) password; every time I need to elevate, I get a prompt that asks for credentials rather than just "Yes/No".  To this prompt I pass the credentials of the local "Admin" account.

Although I usually install fresh builds regularly (on my multiple machines), sometimes one machine gets a little stale.  In fact, it happened once that my local .\Admin account got so stale that I had to change the password!  This was annoying enough that I devoted some energy into figuring out how to check the "Password never expires" box on the local account properties programmatically.

The result was the following script: call as cscript.exe never-expire-admin-password.wsf  This version hardcodes the username "Admin"; a production version would probably allow passing a username in via the command line.

' LDAP doesn't work for controlling local users
' (unless you're a domain controller, of course)
'
' have to use WinNT provider instead

' Save
End If

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

• What is a perfect score in Yahtzee?

The dice game Yahtzee takes thirteen turns. Each turn involves rolling a set of five dice (with two possible rerolls, the player having the option to reroll only a subset of the dice), then marking one of thirteen boxes and scoring points according to whether the numbers on the dice meet the rules of the box. After each box is marked, the game is over.

The thirteen boxes and their rules are:

1. ONES: score is the sum of those dice showing a one (could be zero.)
2. TWOS: score is the sum of those dice showing a two (could be zero.)
3. THREES: score is the sum of those dice showing a three (could be zero.)
4. FOURS: score is the sum of those dice showing a four (could be zero.)
5. FIVES: score is the sum of those dice showing a five (could be zero.)
6. SIXES: score is the sum of those dice showing a six (could be zero.)
7. THREE OF A KIND: if three of the dice show the same number, the score is the sum of all five dice; otherwise, zero.
8. FOUR OF A KIND: if four of the dice show the same number, the score is the sum of all five dice; otherwise, zero.
9. FULL HOUSE: if three of the dice show the same number as each other, and the other two show the same number as each other, score 25; otherwise, zero.1
10. SMALL STRAIGHT: if there are four dice which show (1 2 3 4), or (2 3 4 5), or (3 4 5 6), score 30; otherwise, zero. (There is no defined order for the rolled dice, so order is not important.)
11. LARGE STRAIGHT: if the five dice show (1 2 3 4 5), or (2 3 4 5 6), score 40; otherwise, zero. (Order is not important.)
12. CHANCE: score the total of the five dice (minimum possible score is 5.)2
13. YAHTZEE (FIVE OF A KIND:) if all five dice show the same number, score 50; otherwise, zero.

There are two bonuses possible:

1. At the end of the game, if the point total for boxes 1-6 (ONES through SIXES) is at least 63, the player gets a bonus of 35. (63 corresponds to getting three ones + three twos + three threes + ... + three sixes, but there are other possibilities. I don't know where 35 came from.)
2. At any time the player checks a box, if...
• the five dice all have the same number as each other
• AND the Yahtzee box is already checked
• AND this was not a result of "taking a zero in Yahtzee"
... then the player gets a bonus 100 points. This bonus can take effect multiple times per game.

So a perfect Yahtzee game looks like this. On the first turn...

 Roll Box Score (x x x x x) any Yahtzee YAHTZEE 50 Subtotal 50

... then on the following turns, in no particular order (but see below:)

 Roll Box Score (1 1 1 1 1) ONES 5 (2 2 2 2 2) TWOS 10 (3 3 3 3 3) THREES 15 (4 4 4 4 4) FOURS 20 (5 5 5 5 5) FIVES 25 (6 6 6 6 6) SIXES 30 (6 6 6 6 6) THREE OF A KIND 30 (6 6 6 6 6) FOUR OF A KIND 30 (x x x x x) any Yahtzee FULL HOUSE 0 or 25 (see below)1 (x x x x x) any Yahtzee SMALL STRAIGHT 0 (but see below) (x x x x x) any Yahtzee LARGE STRAIGHT 0 (but see below) (6 6 6 6 6) CHANCE 30 Subtotal 195 or 220

Now we look at the bonuses and add it all up:

 Category Score Base score 245 or 270 Bonus for scoring >= 63 in ONES through SIXES 35 Bonus for scoring twelve additional YAHTZEEs after scoring 50 in YAHTZEE 1200 Total 1480 or 1505

So a perfect score in Yahtzee is 1480 or 1505.

Well...

... not quite. There's another rule about Yahtzees (the "Joker" rule) which I didn't tell you about yet, because it's kind of complicated. If...

• You roll a Yahtzee
• AND the YAHTZEE box is already checked (a zero score is OK; you don't get the 100 point bonus, but this rule still applies)
• ... then you MUST score this in the ONES-through-SIXES box for the number you rolled (say, 3)...
• ... UNLESS that box has also already been checked (a zero score is OK), in which case...

... you can score this roll in any unchecked box and it automatically meets the scoring criterion (wow!) So you would get 30 points in SMALL STRAIGHT or 40 points in LARGE STRAIGHT. (Or 25 points in FULL HOUSE.)1

This gives an additional 70 or 95 points, bring the total to 1575. (It also creates additional order dependencies; the boxes for FULL HOUSE, SMALL STRAIGHT, and LARGE STRAIGHT must be checked after the ONES through SIXES box for the corresponding number is checked.)

1 Does five-of-a-kind count as a full house? I'm not sure. Mathematically it would make sense. It turns out not to matter for this calculation because of the Joker rule, but it may matter in an actual game. The official rules say "Score in this box only if the dice show three of one number and two of another", so I guess not, but I would be comfortable adopting a "house rule" which allowed a Yahtzee to count as a "native" full house. Normally a house rule should be agreed upon by all players before the start of the game, but I'm pretty sure it would be possible to convince the other players to let you score your (3 3 3 3 3) in FULL HOUSE while YAHTZEE was still open. ("You want to throw away 25 points?  Really?  Um, go right ahead...")

2 The lowest possible Yahtzee score is 5: get (1 1 1 1 1) and score it in Chance, then get zeros in all the other boxes.

• 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);

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

• 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

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

• Welcome Yuk Lai Suen to the blogosphere!

Please help to welcome my colleague fellow Windows Sound team test dev Yuk Lai Suen to the blogosphere!  Yuk Lai's first post discusses the utility of manual testing.

Yuk Lai Suen
http://blogs.msdn.com/b/yuk_lai_suen/

• 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

• 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__)

• How to install unsigned drivers

Most device drivers these days have signatures which allow the operating system to validate that the driver files have not been tampered with since the author sent them out into the world.

It is still possible to run into an unsigned driver. If you try to install an unsigned driver, Windows will warn you at install time:

IMPORTANT: if you see this warning, ask yourself this question - DO I TRUST THE SOURCE OF THIS DRIVER? If the answer is anything but a resounding YES, you should click "Don't install this software."

Windows XP was, by and large, a 32-bit operating system. A 64-bit version of Windows XP was developed but it was not broadly released. At that time it was still fairly common to have unsigned drivers.

Windows Vista was the first client release of Windows to have a widely deployed 64-bit release. This gave an opportunity to be more strict about enforcing driver signatures. For backwards compatibility, it was still possible to run unsigned drivers on the 32-bit version of Windows Vista (so the XP drivers would still work) but there was no such burden on Windows Vista 64-bit; so Windows Vista 64-bit was the first time that there was really a strong incentive to run with only signed drivers.

Even so, there are still workarounds provided:

• If you want to run an unsigned driver for one particular boot, you can hit F8 during boot1 and choose "Disable Driver Signature Enforcement". This allows unsigned drivers to load for this boot only.
• If you're a device driver developer, it is expected that you will want to iterate on your particular driver; it is also expected that you will probably also have a kernel debugger attached. So driver signature enforcement is disabled if you have a kernel debugger attached.

The most reliable method, however, and the one with the fewest side effects, is to... well... sign the driver!

To sign a driver:

2. Make sure the driver .inf has a CatalogFile=MyCatalogFile.cat line (specify your own value for MyCatalogFile.cat). If one is missing you can add it to the [Version] section.
3. Point inf2cat to the driver .inf file and it will make a .cat file for you. This .cat file will have an entry for every file pulled in by the .inf.
4. Use SignTool to sign the .cat file.

At this point you can see who says this driver is OK. Double-click the .cat file | View Signature | View Certificate | Certification Path and note the highest certificate in the chain:

If you're a professional driver developer and you want your driver to ship on Windows systems, your next step would very likely be to use the Windows Logo Kit to run the Microsoft logo tests, and get an official "Microsoft says this driver has passed the logo tests" signature for your .cat file. (The difference is that the top certificate in the chain will be "Microsoft Root Authority" rather than "Microsoft Test Root Authority.") A full description of this process lies outside the scope of this blog post.

But if you're just developing a driver for your personal use, you would probably skip this step. Instead of getting a "Microsoft says this driver is OK" signature, you can add the root certificate for your signing certificate to the "trusted root certificates" certificate store on the machine you want to load the driver on.

If the root certificate in question is the "Microsoft Test Root Authority", you can run "bcdedit -set testsigning on" and reboot.

If it's some other certificate (for example, if you generated a self-signed certificate) then you need to add it to the trusted certificate store by using certmgr.exe or by going to Internet Explorer | Internet Options | Content | Certificates.

If you have everything right, then installing the driver should not pop up the "driver is unsigned" warning. If you still get the warning, looking at C:\windows\inf \setupapi.dev.log can give some clues as to what is wrong... whether there is a driver file that is not listed in the catalog file, or the catalog file's signature does not lead back to a trusted root certificate, or something else.

1 In Windows 8 Developer Preview, the F8 experience has been reworked. Hit Shift-F8 instead.2
2 Some BIOSes have an issue where Shift is not sent to Windows this early. If you have Windows 8 Developer Preview installed one of these machines there's another way - hit F10 during boot to get to the "Edit Boot Options" screen. Add /DISABLE_INTEGRITY_CHECKS to the boot flags.

• How to validate and log a WAVEFORMATEX

Last time I wrote about how to query audio endpoint properties.

This time, a few words about WAVEFORMATEX structures.  WAVEFORMATEX is a variable-sized structure - it can be as small as a PCMWAVEFORMAT or larger than a WAVEFORMATEXTENSIBLE.

If the wFormatTag member (the first field) is WAVE_FORMAT_PCM, then you should assume that it is a PCMWAVEFORMAT.  In particular you should not touch the cbSize field since that may not be memory you own!

If wFormatTag is anything else, you can look at the cbSize to see how much bigger than a WAVEFORMATEX the structure is.  For example, if the wFormatTag is WAVE_FORMAT_EXTENSIBLE, you have the right to expect that cbSize be at least sizeof(WAVEFORMATEXTENSIBLE) - sizeof(WAVEFORMATEX).

I updated the attachment to the post linked above.  Here's the new output:

PKEY_AudioEngine_DeviceFormat VT_BLOB of size 40
WAVEFORMATEXTENSIBLE
Format (
wFormatTag: 65534 (WAVE_FORMAT_EXTENSIBLE)
nChannels: 4
nSamplesPerSec: 16000
nAvgBytesPerSec: 128000
nBlockAlign: 8
wBitsPerSample: 16
cbSize: 22
)
Samples (
wValidBitsPerSample / wSamplesPerBlock / wReserved: 16
)
SubFormat: {00000001-0000-0010-8000-00AA00389B71} (KSDATAFORMAT_SUBTYPE_PCM)

And here's the code that produces it:

HRESULT LogWaveFormat(LPCWAVEFORMATEX pWfx, UINT nBytes) {
if (NULL == pWfx) {
ERR(L"LogWaveFormat called with a NULL pointer");
return E_POINTER;
}

if (nBytes < sizeof(PCMWAVEFORMAT)) {
ERR(L"Wave format is only %u bytes, smaller even than a PCMWAVEFORMAT (%Iu bytes)", nBytes, sizeof(PCMWAVEFORMAT));
return E_INVALIDARG;
} else if (nBytes == sizeof(PCMWAVEFORMAT)) {
const PCMWAVEFORMAT *pPcm = reinterpret_cast<const PCMWAVEFORMAT *>(pWfx);

// PCMWAVEFORMAT must have a wFormatTag of WAVE_FORMAT_PCM
if (WAVE_FORMAT_PCM != pPcm->wf.wFormatTag) {
ERR(L"PCMWAVEFORMAT has invalid format tag %u (expected %u)", pPcm->wf.wFormatTag, WAVE_FORMAT_PCM);
return E_INVALIDARG;
}

LOG(
L"    PCMWAVEFORMAT\n"
L"        wf.wFormatTag: %u (%s)\n"
L"        wf.nChannels: %u\n"
L"        wf.nSamplesPerSec: %u\n"
L"        wf.nAvgBytesPerSec: %u\n"
L"        wf.nBlockAlign: %u\n"
L"        wBitsPerSample: %u",
pPcm->wf.wFormatTag, StringFromWaveFormatTag(pPcm->wf.wFormatTag),
pPcm->wf.nChannels,
pPcm->wf.nSamplesPerSec,
pPcm->wf.nAvgBytesPerSec,
pPcm->wf.nBlockAlign,
pPcm->wBitsPerSample
);
return S_OK;
} else if (nBytes < sizeof(WAVEFORMATEX)) {
ERR(
L"Wave format is %u bytes, "
L"bigger than a PCMWAVEFORMAT (%Iu bytes) "
L"but smaller than a WAVEFORMATEX (%Iu bytes)",
nBytes,
sizeof(PCMWAVEFORMAT),
sizeof(WAVEFORMATEX)
);
return E_INVALIDARG;
} else if (nBytes != sizeof(WAVEFORMATEX) + pWfx->cbSize) {
ERR(
L"Wave format takes up %u bytes "
L"but sizeof(WAVEFORMATEX) + pWfx->cbSize is %Iu bytes",
nBytes,
sizeof(WAVEFORMATEX) + pWfx->cbSize
);
return E_INVALIDARG;
} else {
// nBytes matches cbSize
switch (pWfx->wFormatTag) {

case WAVE_FORMAT_EXTENSIBLE:
{
if (pWfx->cbSize < sizeof(WAVEFORMATEXTENSIBLE) - sizeof(WAVEFORMATEX)) {
ERR(
L"cbSize for a WAVE_FORMAT_EXTENSIBLE format must be at least "
L"sizeof(WAVEFORMATEXTENSIBLE) - sizeof(WAVEFORMATEX) (%Iu), "
L"not %u",
sizeof(WAVEFORMATEXTENSIBLE) - sizeof(WAVEFORMATEX),
pWfx->cbSize
);
return E_INVALIDARG;
}

const WAVEFORMATEXTENSIBLE *pWfxExt = reinterpret_cast<const WAVEFORMATEXTENSIBLE *>(pWfx);

LOG(
L"    WAVEFORMATEXTENSIBLE\n"
L"    Format (\n"
L"        wFormatTag: %u (%s)\n"
L"        nChannels: %u\n"
L"        nSamplesPerSec: %u\n"
L"        nAvgBytesPerSec: %u\n"
L"        nBlockAlign: %u\n"
L"        wBitsPerSample: %u\n"
L"        cbSize: %u\n"
L"    )\n"
L"    Samples (\n"
L"        wValidBitsPerSample / wSamplesPerBlock / wReserved: %u\n"
L"    )\n"
L"    SubFormat: {%08X-%04X-%04X-%02X%02X-%02X%02X%02X%02X%02X%02X} (%s)",
pWfxExt->Format.wFormatTag, StringFromWaveFormatTag(pWfxExt->Format.wFormatTag),
pWfxExt->Format.nChannels,
pWfxExt->Format.nSamplesPerSec,
pWfxExt->Format.nAvgBytesPerSec,
pWfxExt->Format.nBlockAlign,
pWfxExt->Format.wBitsPerSample,
pWfxExt->Format.cbSize,
pWfxExt->Samples.wValidBitsPerSample,
pWfxExt->SubFormat.Data1,
pWfxExt->SubFormat.Data2,
pWfxExt->SubFormat.Data3,
pWfxExt->SubFormat.Data4[0],
pWfxExt->SubFormat.Data4[1],
pWfxExt->SubFormat.Data4[2],
pWfxExt->SubFormat.Data4[3],
pWfxExt->SubFormat.Data4[4],
pWfxExt->SubFormat.Data4[5],
pWfxExt->SubFormat.Data4[6],
pWfxExt->SubFormat.Data4[7],
StringFromSubFormat(pWfxExt->SubFormat)
);

if (pWfx->cbSize > sizeof(WAVEFORMATEXTENSIBLE) - sizeof(WAVEFORMATEX)) {
LOG(L"    Trailing bytes:\n");
return LogBytes(
reinterpret_cast<const BYTE *>(pWfx) + sizeof(WAVEFORMATEXTENSIBLE),
pWfx->cbSize - (sizeof(WAVEFORMATEXTENSIBLE) - sizeof(WAVEFORMATEX))
);
}

return S_OK;
}

case WAVE_FORMAT_PCM:
if (pWfx->cbSize > 0) {
ERR(L"cbSize for a WAVE_FORMAT_PCM format must be 0, not %u", pWfx->cbSize);
return E_INVALIDARG;
}
// intentionally fall through
default:
LOG(
L"    WAVEFORMATEX\n"
L"        wFormatTag: %u (%s)\n"
L"        nChannels: %u\n"
L"        nSamplesPerSec: %u\n"
L"        nAvgBytesPerSec: %u\n"
L"        nBlockAlign: %u\n"
L"        wBitsPerSample: %u\n"
L"        cbSize: %u",
pWfx->wFormatTag, StringFromWaveFormatTag(pWfx->wFormatTag),
pWfx->nChannels,
pWfx->nSamplesPerSec,
pWfx->nAvgBytesPerSec,
pWfx->nBlockAlign,
pWfx->wBitsPerSample,
pWfx->cbSize
);

if (pWfx->cbSize > 0) {
LOG(L"    Trailing bytes:");
return LogBytes(reinterpret_cast<const BYTE *>(pWfx) + sizeof(WAVEFORMATEX), pWfx->cbSize);
}

return S_OK;
}
}
}

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

• Disney princesses: an attempt at a complete list

Last time we examined the "Disney princess" status of Belle from Beauty and the Beast. This time I attempt to give an exhaustive list of all Disney princesses together with a very short summary of their status.

Snow White and the Seven Dwarfs (1937)

 Snow WhiteQueen's Daughter; Queen? Prince's Girlfriend; Prince's Wife?Disney Princess

Bambi (1942)

 FalinePrince's WifeDisney Princess Bambi's MotherPrince's WifeDisney Princess

Cinderella (1950)

 CinderellaPrince's WifeDisney Princess

Peter Pan (1953)

 Tiger LilyChief's DaughterDisney Princess

Sleeping Beauty (1959)

 AuroraKing's Daughter; Prince's Girlfriend; Prince's Wife?Disney Princess

Robin Hood (1973)

 Maid MarianWealthy; Prince(?)'s GirlfriendNot a princess

Nausicaä of the Valley of Wind (1984: Studio Ghibli1)

 NausicaäKing's Daughter; Queen?Disney(?) Princess KushanaRoyalty's DaughterDisney(?) Princess LastelleQueen's DaughterDisney(?) Princess

The Black Cauldron (1985)

 EilonwyQueen's Daughter; Prince(?)2's Girlfriend(?)Disney Princess

Castle in the Sky (1986: Studio Ghibli)

 SheetaQueen's Daughter; Queen?Disney(?) Princess

Oliver & Company (1988)

 JennyWealthyNot a princess

The Little Mermaid (1989)

 ArielKing's Daughter; Queen's Daughter?3 Prince's WifeDisney Princess Aquata, Andrina, Arista, Attina, Adella, AlanaKing's Daughter; Queen's Daughter?3 Queen?4Disney Princesses

Beauty and the Beast (1991)

 BellePrince's Girlfriend; Prince's Wife?5Disney Princess?

 JasmineSultan's Daughter; Prince's Girlfriend?6 Sultan's Girlfriend?7Disney Princess

The Lion King (1994)

 NalaKing's Daughter8; Prince's Girlfriend; King's Girlfriend; King's WifeDisney Princess KiaraKing's Daughter9Disney Princess?

Pocahontas (1995)

 PocahontasChief's DaughterDisney Princess

Princess Mononoke (1997: Studio Ghibli)

 San (also known as Princess Mononoke)Wolf God's Adopted DaughterDisney(?) Princess KayaPrince's SisterDisney(?) Princess

A Bug's Life (1998: Pixar)

 DotQueen's DaughterDisney(?) Princess AttaQueen's Daughter; QueenDisney(?) Princess

Atlantis: The Lost Empire (2001)

 KidaKing's Daughter; QueenDisney Princess

Tales from Earthsea (2006: Studio Ghibli)

 Therru (true name Tehanu)Prince's GirlfriendNot a princess

Ponyo (2008: Studio Ghibli)

 PonyoQueen's DaughterDisney(?) Princess

The Princess and the Frog (2009)

 TianaPrince's WifeDisney Princess CharlotteKing's Daughter10Disney Princess

Tangled (2010)

 RapunzelKing & Queen's DaughterDisney Princess

Brave (2012)

 MeridaKing & Queen's DaughterDisney Princess

Wreck-it Ralph (2012)

 Vanellope von SchweetzPrincessDisney Princess

Methodology - I started with Disney's own "50 animated features" list as present on the Tangled DVD. To this I added the list of Pixar and (somewhat more controversially) Studio Ghibli movies released under the Disney name.

1 Nausicaä of the Valley of Wind is technically not a Studio Ghibli film as the studio was not founded until after the film was released.
2 In The Black Cauldron, Taran is not yet aware that he is a prince.
3 In The Little Mermaid, Ursula briefly has a claim to being a queen. Her relationship to Triton is never made clear; if she is his ex-wife, Ariel and her sisters are potentially her daughters.
4 In The Little Mermaid, Triton is briefly incapacitated. His eldest daughter thus has a brief claim to being Queen.
5 In Beauty and the Beast, Belle's princess status hinges on whether she is married to the Beast.
6 In Aladdin, Aladdin spends a fair amount of time transformed into a prince, though it is not clear where his principality lies.
7 In Aladdin, Jafar is briefly Sultan and attempts to woo Jasmine, though there is no reciprocity in their relationship.
8 In The Lion King it is perhaps best not to inquire too closely into the precise nature of the familial relationships between members of the pride in question.
9 The Lion King ends with a shot of Simba and Nala's cub being presented, but it is not clear whether the cub is male or female; in sequels it is made clear that the cub is a girl and her name is Kiara.
10 Charlotte's father is King of Mardi Gras, so Charlotte is princess for only one day. Still, Once a Princess, Always a Princess.

• Disney princess pedigree: Belle

Is Belle a Disney princess?

The case in favor

As is clearly established in the opening monologue, the male lead is a prince. Only his outward form is temporarily changed by the nasty enchantress who entraps him into refusing shelter (as if this was a crime.) Nevertheless, he retains property rights to his castle and the surrounding dominions - even were this not the case, Once a Prince, Always a Prince.

Throughout the movie Belle handles herself with princessly aplomb:

• She evades the unwanted attentions of Gaston without overtly hurting his feelings.
• She is able to find and rescue her father.
• She keeps her word not to leave the castle even when afforded an opportunity to escape by the Beast's injury.
• She wins the hearts of the castle servants.
• She civilizes the prince, taming his notorious temper and finding a modified set of table manners that are within the physical limitations imposed by his enchantment.

The enchantress's spell serves as a litmus test for true love. The restoring of the prince's human form is proof that Belle and the prince love one another; they then kiss, and are married. Thus Belle has the clear title of Princess by Marriage.

The case against

It is granted that the male lead is a prince during the opening monologue. Granted, too, is his status as a prince in the closing scenes. One might question the practical effect of his princely status in the interim, especially since no-one outside of his castle is apparently aware of his existence. Certainly his behavior at several points during the movie is extremely unbecoming of a prince, or even a decent commoner:

• He refuses shelter to an old woman, exposing both himself and the population of the castle to the wrath of an enchantress (who was admittedly overreacting a little.)
• He withdraws from society.
• He frequently loses his temper with his servants and others.
• He imprisons Maurice, whose only crime was seeking refuge from wolves.
• He imprisons Belle, whose only crime was looking for Maurice.
• His table manners are decidedly unroyal.

Belle's achievements as a young lady, though they do her credit (with the possible exception of passing up the opportunity to escape,) are irrelevant to her claim to the title of princess. Many a commoner has virtue; their lack of a princess title in no way diminishes that virtue.

It pains me to say this, but Belle displays consistently poor social abilities throughout the movie - she is established as a withdrawn, introverted character who prefers the company of books to that of people. It is small wonder that she is easy prey for the sociopathic Beast. It is clear to me that over a prolonged period in a captor/hostage relationship, she eventually succumbs to Stockholm syndrome.

The transformation is not necessarily indicative of true love between the Beast and Belle. It is true that the transformation was coincident with Belle's profession of love to the (as she perceived it) dying Beast. But it was also coincident with the falling of the last petal from the rose. Why believe that the former, rather than the latter, ended the enchantment? We have only the enchantress's word for this, and enchantresses are not known to be women of their words. In any case, Being a Prince's Girlfriend Does Not Suffice.

One might challenge the validity of a marriage contract entered into when one of the parties was not of sound mind. But is there a marriage contract at all to challenge? There is no direct evidence that Beauty and the Beast are married at all.

The verdict

Belle has no claim to being a Princess by Birth; only to being a Princess by Marriage. It is clear that the Beast is a prince. What we have to decide is, was there a marriage?

The final scene is quite artistic in its ambiguity. The penultimate scene culminates in a fairly passionate kiss (by Disney standards.) This is followed up by a formal dance, with Belle and the prince wearing their best outfits. And yet... No Dress, No Kiss, No Wedding. It is almost as if the scene were crafted so that all the young ladies in the audience could watch the scene and come away with the firm impression that Belle and the prince were married, and all of their fathers could come away with the firm impression that there was still hope that Belle would come to her senses. Note especially Chip's question "are they going to live happily ever after, Mama?", and Ms. Potts' pat answer "of course".

In that critical final scene, Belle is wearing gloves, but the presence of a ring on the prince's finger would help Belle's case for princesshood significantly; I was unable to see one.

Verdict: Controversial

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

• How to enumerate audio endpoint (IMMDevice) properties on your system

Source and binaries (amd64 and x86) attached.

Pseudocode:

CoCreateInstance(..., &pMMDeviceEnumerator);
pMMDeviceEnumerator->EnumAudioEndpoints(..., &pMMDeviceCollection);
for (each device in the collection) {
pMMDevice->OpenPropertyStore(...,  &pPropertyStore);
for (each property in the store) {
log the property
}
}

Output on my system:

>audioendpoints.exe
ID: {0.0.0.00000000}.{6d531641-b3e3-43c5-ba56-ba165b4a9bb6}
State: 4 (DEVICE_STATE_NOTPRESENT)
-- Properties (18) --
{b3f8fa53-0004-438e-9003-51a46e139bfc},15:
VT_BLOB of size 16
db 07 06 00 03 00 01 00
17 00 3a 00 2d 00 26 03
DEVPKEY_Device_DeviceDesc:
VT_LPWSTR Internal AUX Jack
{b3f8fa53-0004-438e-9003-51a46e139bfc},6:
VT_LPWSTR High Definition Audio Device
{b3f8fa53-0004-438e-9003-51a46e139bfc},2:
VT_LPWSTR {1}.HDAUDIO\FUNC_01&VEN_8384&DEV_7690&SUBSYS_102801BD&REV_1022\4&33D044FE&0&0001
{83da6326-97a6-4088-9453-a1923f573b29},3:
VT_LPWSTR hdaudio.inf:Microsoft.ntamd64:HdAudModel:6.1.7600.16385::hdaudio\func_01
DEVPKEY_Device_BaseContainerId:
VT_CLSID {00000000-0000-0000-ffff-ffffffffffff}
DEVPKEY_Device_ContainerId:
VT_CLSID {00000000-0000-0000-ffff-ffffffffffff}
DEVPKEY_Device_EnumeratorName:
VT_LPWSTR HDAUDIO
{b3f8fa53-0004-438e-9003-51a46e139bfc},1:
VT_BLOB of size 72
a8 7f a4 d5 98 6d d1 11
a2 1a 00 a0 c9 22 31 96
9c ac 97 dc ec dd 59 4d
b6 50 3b 8b a6 7b c2 a1
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
e0 cc 13 de 04 83 e9 4e
ba ce 48 24 21 4e 3e a5
00 00 02 00 01 00 00 00
PKEY_AudioEndpoint_FormFactor:
VT_UI4 10
PKEY_AudioEndpoint_JackSubType:
DEVPKEY_DeviceClass_IconPath:
VT_LPWSTR %windir%\system32\mmres.dll,-3018
VT_BLOB of size 300
01 00 00 00 28 01 00 00
00 00 01 00 7b 00 32 00
7d 00 2e 00 5c 00 5c 00
3f 00 5c 00 68 00 64 00
61 00 75 00 64 00 69 00
6f 00 23 00 66 00 75 00
6e 00 63 00 5f 00 30 00
31 00 26 00 76 00 65 00
6e 00 5f 00 38 00 33 00
38 00 34 00 26 00 64 00
65 00 76 00 5f 00 37 00
36 00 39 00 30 00 26 00
73 00 75 00 62 00 73 00
79 00 73 00 5f 00 31 00
30 00 32 00 38 00 30 00
31 00 62 00 64 00 26 00
72 00 65 00 76 00 5f 00
31 00 30 00 32 00 32 00
23 00 34 00 26 00 33 00
33 00 64 00 30 00 34 00
34 00 66 00 65 00 26 00
30 00 26 00 30 00 30 00
30 00 31 00 23 00 7b 00
36 00 39 00 39 00 34 00
61 00 64 00 30 00 34 00
2d 00 39 00 33 00 65 00
66 00 2d 00 31 00 31 00
64 00 30 00 2d 00 61 00
33 00 63 00 63 00 2d 00
30 00 30 00 61 00 30 00
63 00 39 00 32 00 32 00
33 00 31 00 39 00 36 00
7d 00 5c 00 65 00 6d 00
69 00 63 00 69 00 6e 00
74 00 6f 00 70 00 6f 00
2f 00 30 00 30 00 30 00
31 00 30 00 30 00 30 00
30 00 00 00
PKEY_AudioEndpoint_Association:
VT_LPWSTR {00000000-0000-0000-0000-000000000000}
PKEY_AudioEndpoint_Supports_EventDriven_Mode:
VT_UI4 1
DEVPKEY_Device_FriendlyName:
VT_LPWSTR Internal AUX Jack (High Definition Audio Device)
DEVPKEY_DeviceInterface_FriendlyName:
VT_LPWSTR High Definition Audio Device
PKEY_AudioEndpoint_GUID:
VT_LPWSTR {6D531641-B3E3-43C5-BA56-BA165B4A9BB6}

ID: {0.0.0.00000000}.{ca9fa848-1e60-401c-81e6-323546335d0a}
State: 1 (DEVICE_STATE_ACTIVE)
-- Properties (26) --
{b3f8fa53-0004-438e-9003-51a46e139bfc},15:
VT_BLOB of size 16
da 07 0a 00 04 00 1c 00
16 00 3a 00 3a 00 d1 00
DEVPKEY_Device_DeviceDesc:
VT_LPWSTR Speakers
{b3f8fa53-0004-438e-9003-51a46e139bfc},6:
VT_LPWSTR High Definition Audio Device
{b3f8fa53-0004-438e-9003-51a46e139bfc},2:
VT_LPWSTR {1}.HDAUDIO\FUNC_01&VEN_8384&DEV_7690&SUBSYS_102801BD&REV_1022\4&33D044FE&0&0001
{83da6326-97a6-4088-9453-a1923f573b29},3:
VT_LPWSTR hdaudio.inf:Microsoft.ntamd64:HdAudModel:6.1.7600.16385::hdaudio\func_01
DEVPKEY_Device_BaseContainerId:
VT_CLSID {00000000-0000-0000-ffff-ffffffffffff}
DEVPKEY_Device_ContainerId:
VT_CLSID {00000000-0000-0000-ffff-ffffffffffff}
DEVPKEY_Device_EnumeratorName:
VT_LPWSTR HDAUDIO
{b3f8fa53-0004-438e-9003-51a46e139bfc},1:
VT_BLOB of size 72
a8 7f a4 d5 98 6d d1 11
a2 1a 00 a0 c9 22 31 96
9c ac 97 dc ec dd 59 4d
b6 50 3b 8b a6 7b c2 a1
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
e0 cc 13 de 04 83 e9 4e
ba ce 48 24 21 4e 3e a5
00 00 02 00 01 00 00 00
PKEY_AudioEndpoint_FormFactor:
VT_UI4 1
PKEY_AudioEndpoint_JackSubType:
VT_LPWSTR {DFF21CE1-F70F-11D0-B917-00A0C9223196}
DEVPKEY_DeviceClass_IconPath:
VT_LPWSTR %windir%\system32\mmres.dll,-3010
VT_BLOB of size 324
01 00 00 00 40 01 00 00
00 00 01 00 7b 00 32 00
7d 00 2e 00 5c 00 5c 00
3f 00 5c 00 68 00 64 00
61 00 75 00 64 00 69 00
6f 00 23 00 66 00 75 00
6e 00 63 00 5f 00 30 00
31 00 26 00 76 00 65 00
6e 00 5f 00 38 00 33 00
38 00 34 00 26 00 64 00
65 00 76 00 5f 00 37 00
36 00 39 00 30 00 26 00
73 00 75 00 62 00 73 00
79 00 73 00 5f 00 31 00
30 00 32 00 38 00 30 00
31 00 62 00 64 00 26 00
72 00 65 00 76 00 5f 00
31 00 30 00 32 00 32 00
23 00 34 00 26 00 33 00
33 00 64 00 30 00 34 00
34 00 66 00 65 00 26 00
30 00 26 00 30 00 30 00
30 00 31 00 23 00 7b 00
36 00 39 00 39 00 34 00
61 00 64 00 30 00 34 00
2d 00 39 00 33 00 65 00
66 00 2d 00 31 00 31 00
64 00 30 00 2d 00 61 00
33 00 63 00 63 00 2d 00
30 00 30 00 61 00 30 00
63 00 39 00 32 00 32 00
33 00 31 00 39 00 36 00
7d 00 5c 00 65 00 73 00
6c 00 61 00 76 00 65 00
64 00 68 00 70 00 73 00
70 00 65 00 61 00 6b 00
65 00 72 00 74 00 6f 00
70 00 6f 00 2f 00 30 00
30 00 30 00 31 00 30 00
30 00 30 00 31 00 00 00
00 00 00 00
PKEY_AudioEndpoint_Association:
VT_LPWSTR {00000000-0000-0000-0000-000000000000}
PKEY_AudioEndpoint_Supports_EventDriven_Mode:
VT_UI4 1
{9a82a7db-3ebb-41b4-83ba-18b7311718fc},1:
VT_UI4 65536
{233164c8-1b2c-4c7d-bc68-b671687a2567},1:
{5a9125b7-f367-4924-ace2-0803a4a3a471},0:
VT_UI4 1610652916
{5a9125b7-f367-4924-ace2-0803a4a3a471},2:
VT_UI4 1610644836
{b3f8fa53-0004-438e-9003-51a46e139bfc},0:
VT_UI4 1
PKEY_AudioEngine_DeviceFormat:
VT_BLOB of size 40
fe ff 02 00 44 ac 00 00
10 b1 02 00 04 00 10 00
16 00 10 00 03 00 00 00
01 00 00 00 00 00 10 00
80 00 00 aa 00 38 9b 71
{e4870e26-3cc5-4cd2-ba46-ca0a9a70ed04},0:
VT_BLOB of size 40
fe ff 02 00 44 ac 00 00
20 62 05 00 08 00 20 00
16 00 20 00 03 00 00 00
03 00 00 00 00 00 10 00
80 00 00 aa 00 38 9b 71
{e4870e26-3cc5-4cd2-ba46-ca0a9a70ed04},1:
VT_BLOB of size 8
d3 8c 01 00 00 00 00 00
DEVPKEY_Device_FriendlyName:
VT_LPWSTR Speakers (High Definition Audio Device)
DEVPKEY_DeviceInterface_FriendlyName:
VT_LPWSTR High Definition Audio Device
PKEY_AudioEndpoint_GUID:
VT_LPWSTR {CA9FA848-1E60-401C-81E6-323546335D0A}

ID: {0.0.1.00000000}.{4f5e42d9-227f-43ff-bf5b-a1ce5d0324cf}
State: 8 (DEVICE_STATE_UNPLUGGED)
-- Properties (28) --
{b3f8fa53-0004-438e-9003-51a46e139bfc},15:
VT_BLOB of size 16
da 07 0a 00 04 00 1c 00
16 00 3a 00 3a 00 0f 01
DEVPKEY_Device_DeviceDesc:
VT_LPWSTR Microphone
{b3f8fa53-0004-438e-9003-51a46e139bfc},6:
VT_LPWSTR High Definition Audio Device
{b3f8fa53-0004-438e-9003-51a46e139bfc},2:
VT_LPWSTR {1}.HDAUDIO\FUNC_01&VEN_8384&DEV_7690&SUBSYS_102801BD&REV_1022\4&33D044FE&0&0001
{83da6326-97a6-4088-9453-a1923f573b29},3:
VT_LPWSTR hdaudio.inf:Microsoft.ntamd64:HdAudModel:6.1.7600.16385::hdaudio\func_01
DEVPKEY_Device_BaseContainerId:
VT_CLSID {00000000-0000-0000-ffff-ffffffffffff}
DEVPKEY_Device_ContainerId:
VT_CLSID {00000000-0000-0000-ffff-ffffffffffff}
DEVPKEY_Device_EnumeratorName:
VT_LPWSTR HDAUDIO
{b3f8fa53-0004-438e-9003-51a46e139bfc},1:
VT_BLOB of size 72
a8 7f a4 d5 98 6d d1 11
a2 1a 00 a0 c9 22 31 96
9c ac 97 dc ec dd 59 4d
b6 50 3b 8b a6 7b c2 a1
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
e0 cc 13 de 04 83 e9 4e
ba ce 48 24 21 4e 3e a5
00 00 02 00 01 00 00 00
PKEY_AudioEndpoint_FormFactor:
VT_UI4 4
PKEY_AudioEndpoint_JackSubType:
VT_LPWSTR {DFF21BE1-F70F-11D0-B917-00A0C9223196}
DEVPKEY_DeviceClass_IconPath:
VT_LPWSTR %windir%\system32\mmres.dll,-3014
VT_BLOB of size 300
01 00 00 00 28 01 00 00
00 00 01 00 7b 00 32 00
7d 00 2e 00 5c 00 5c 00
3f 00 5c 00 68 00 64 00
61 00 75 00 64 00 69 00
6f 00 23 00 66 00 75 00
6e 00 63 00 5f 00 30 00
31 00 26 00 76 00 65 00
6e 00 5f 00 38 00 33 00
38 00 34 00 26 00 64 00
65 00 76 00 5f 00 37 00
36 00 39 00 30 00 26 00
73 00 75 00 62 00 73 00
79 00 73 00 5f 00 31 00
30 00 32 00 38 00 30 00
31 00 62 00 64 00 26 00
72 00 65 00 76 00 5f 00
31 00 30 00 32 00 32 00
23 00 34 00 26 00 33 00
33 00 64 00 30 00 34 00
34 00 66 00 65 00 26 00
30 00 26 00 30 00 30 00
30 00 31 00 23 00 7b 00
36 00 39 00 39 00 34 00
61 00 64 00 30 00 34 00
2d 00 39 00 33 00 65 00
66 00 2d 00 31 00 31 00
64 00 30 00 2d 00 61 00
33 00 63 00 63 00 2d 00
30 00 30 00 61 00 30 00
63 00 39 00 32 00 32 00
33 00 31 00 39 00 36 00
7d 00 5c 00 65 00 6d 00
69 00 63 00 69 00 6e 00
74 00 6f 00 70 00 6f 00
2f 00 30 00 30 00 30 00
31 00 30 00 30 00 30 00
31 00 00 00
PKEY_AudioEndpoint_Association:
VT_LPWSTR {00000000-0000-0000-0000-000000000000}
PKEY_AudioEndpoint_Supports_EventDriven_Mode:
VT_UI4 1
{24dbb0fc-9311-4b3d-9cf0-18ff155639d4},3:
VT_BOOL 0xffffffff
{24dbb0fc-9311-4b3d-9cf0-18ff155639d4},4:
VT_BOOL 0xffffffff
{9a82a7db-3ebb-41b4-83ba-18b7311718fc},1:
VT_UI4 65536
{233164c8-1b2c-4c7d-bc68-b671687a2567},1:
{5a9125b7-f367-4924-ace2-0803a4a3a471},0:
VT_UI4 1610712932
{5a9125b7-f367-4924-ace2-0803a4a3a471},2:
VT_UI4 1610708836
{b3f8fa53-0004-438e-9003-51a46e139bfc},0:
VT_UI4 3
PKEY_AudioEngine_DeviceFormat:
VT_BLOB of size 40
fe ff 02 00 44 ac 00 00
10 b1 02 00 04 00 10 00
16 00 10 00 03 00 00 00
01 00 00 00 00 00 10 00
80 00 00 aa 00 38 9b 71
{e4870e26-3cc5-4cd2-ba46-ca0a9a70ed04},0:
VT_BLOB of size 40
fe ff 02 00 44 ac 00 00
20 62 05 00 08 00 20 00
16 00 20 00 03 00 00 00
03 00 00 00 00 00 10 00
80 00 00 aa 00 38 9b 71
{e4870e26-3cc5-4cd2-ba46-ca0a9a70ed04},1:
VT_BLOB of size 8
d3 8c 01 00 00 00 00 00
DEVPKEY_Device_FriendlyName:
VT_LPWSTR Microphone (High Definition Audio Device)
DEVPKEY_DeviceInterface_FriendlyName:
VT_LPWSTR High Definition Audio Device
PKEY_AudioEndpoint_GUID:
VT_LPWSTR {4F5E42D9-227F-43FF-BF5B-A1CE5D0324CF}

State: 4 (DEVICE_STATE_NOTPRESENT)
-- Properties (29) --
{b3f8fa53-0004-438e-9003-51a46e139bfc},15:
VT_BLOB of size 16
db 07 03 00 01 00 15 00
10 00 3b 00 21 00 f4 00
DEVPKEY_Device_DeviceDesc:
VT_LPWSTR Microphone Array
{b3f8fa53-0004-438e-9003-51a46e139bfc},6:
VT_LPWSTR Microphone Array
{b3f8fa53-0004-438e-9003-51a46e139bfc},2:
VT_LPWSTR {1}.USB\VID_045E&PID_FFF0&MI_01\6&1474EDB6&0&0001
{83da6326-97a6-4088-9453-a1923f573b29},3:
VT_LPWSTR wdma_usb.inf:Microsoft.ntamd64:USBAudio:6.1.7600.16385:usb\class_01
DEVPKEY_Device_BaseContainerId:
VT_CLSID {9132f6ea-a152-5472-8685-61c0d297a30b}
DEVPKEY_Device_ContainerId:
VT_CLSID {9132f6ea-a152-5472-8685-61c0d297a30b}
DEVPKEY_Device_EnumeratorName:
VT_LPWSTR USB
{b3f8fa53-0004-438e-9003-51a46e139bfc},1:
VT_BLOB of size 72
30 f1 1c 4e 79 16 3b 46
a7 2f a5 bf 64 c8 6e ba
4e 5a cd ab 63 c2 3b 46
a7 2f a5 bf 64 c8 6e ba
f0 75 12 8f e9 26 64 42
ba 4d 39 ff f0 1d 94 aa
a6 54 57 fc f8 2d 3b 46
a7 2f a5 bf 64 c8 6e ba
02 00 00 00 09 00 00 00
PKEY_AudioEndpoint_FormFactor:
VT_UI4 4
PKEY_AudioEndpoint_JackSubType:
VT_LPWSTR {DFF21BE5-F70F-11D0-B917-00A0C9223196}
DEVPKEY_DeviceClass_IconPath:
VT_LPWSTR %windir%\system32\mmres.dll,-3020
VT_BLOB of size 236
01 00 00 00 e8 00 00 00
00 00 01 00 7b 00 32 00
7d 00 2e 00 5c 00 5c 00
3f 00 5c 00 75 00 73 00
62 00 23 00 76 00 69 00
64 00 5f 00 30 00 34 00
35 00 65 00 26 00 70 00
69 00 64 00 5f 00 66 00
66 00 66 00 30 00 26 00
6d 00 69 00 5f 00 30 00
31 00 23 00 36 00 26 00
31 00 34 00 37 00 34 00
65 00 64 00 62 00 36 00
26 00 30 00 26 00 30 00
30 00 30 00 31 00 23 00
7b 00 36 00 39 00 39 00
34 00 61 00 64 00 30 00
34 00 2d 00 39 00 33 00
65 00 66 00 2d 00 31 00
31 00 64 00 30 00 2d 00
61 00 33 00 63 00 63 00
2d 00 30 00 30 00 61 00
30 00 63 00 39 00 32 00
32 00 33 00 31 00 39 00
36 00 7d 00 5c 00 67 00
6c 00 6f 00 62 00 61 00
6c 00 2f 00 30 00 30 00
30 00 31 00 30 00 30 00
30 00 31 00 00 00 00 00
00 00 00 00
PKEY_AudioEndpoint_Association:
VT_LPWSTR {00000000-0000-0000-0000-000000000000}
PKEY_AudioEndpoint_Supports_EventDriven_Mode:
VT_UI4 1
{24dbb0fc-9311-4b3d-9cf0-18ff155639d4},3:
VT_BOOL 0x0
{24dbb0fc-9311-4b3d-9cf0-18ff155639d4},4:
VT_BOOL 0xffffffff
{9a82a7db-3ebb-41b4-83ba-18b7311718fc},1:
VT_UI4 65536
{233164c8-1b2c-4c7d-bc68-b671687a2567},1:
{5a9125b7-f367-4924-ace2-0803a4a3a471},0:
VT_UI4 1610713736
{5a9125b7-f367-4924-ace2-0803a4a3a471},2:
VT_UI4 1610709736
{b3f8fa53-0004-438e-9003-51a46e139bfc},0:
VT_UI4 3
PKEY_AudioEngine_DeviceFormat:
VT_BLOB of size 40
fe ff 04 00 80 3e 00 00
00 f4 01 00 08 00 10 00
16 00 10 00 00 00 00 00
01 00 00 00 00 00 10 00
80 00 00 aa 00 38 9b 71
{e4870e26-3cc5-4cd2-ba46-ca0a9a70ed04},0:
VT_BLOB of size 40
fe ff 04 00 80 3e 00 00
00 e8 03 00 10 00 20 00
16 00 20 00 00 00 00 00
03 00 00 00 00 00 10 00
80 00 00 aa 00 38 9b 71
{e4870e26-3cc5-4cd2-ba46-ca0a9a70ed04},1:
VT_BLOB of size 8
a0 86 01 00 00 00 00 00
{9855c4cd-df8c-449c-a181-8191b68bd06c},0:
VT_BLOB of size 16
00 00 f0 41 00 00 f0 41
00 00 f0 41 00 00 f0 41
DEVPKEY_Device_FriendlyName:
VT_LPWSTR Microphone Array (Microphone Array)
DEVPKEY_DeviceInterface_FriendlyName:
VT_LPWSTR Microphone Array
PKEY_AudioEndpoint_GUID:

The unrecognized properties could be private properties used by the OS, or by the audio driver, or they might be defined in some public header that I didn't bother to scour.

UPDATE 2011-09-09: added WAVEFORMATEX logging for properties known to be audio formats.

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

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

• Translating Ada Lovelace - mathematical science is an instrument

Lady Augusta Ada, Countess of Lovelace is credited with being the first computer programmer.

The short version: her associate Charles Babbage gave a lecture on his Analytical Engine in Italy; an Italian engineer wrote up a report on his lecture, in French; Lady Ada then translated the report into English, and added her own notes. Her own notes include a procedure for calculating Bernoulli numbers using the Analytical Engine; it is this procedure which is regarded as being the first computer program, making her the first computer programmer.

Her translation and notes, in full

The program (very large image)

I was skimming through this and stumbled on this sentence which immediately struck me.

Those who view mathematical science, not merely as a vast body of abstract and immutable truths, whose intrinsic beauty, symmetry and logical completeness, when regarded in their connexion together as a whole, entitle them to a prominent place in the interest of all profound and logical minds, but as possessing a yet deeper interest for the human race, when it is remembered that this science constitutes the language through which alone we can adequately express the great facts of the natural world, and those unceasing changes of mutual relationship which, visibly or invisibly, consciously or unconsciously to our immediate physical perceptions, are interminably going on in the agencies of the creation we live amidst: those who thus think on mathematical truth as the instrument through which the weak mind of man can most effectually read his Creator's works, will regard with especial interest all that can tend to facilitate the translation of its principles into explicit practical forms.

Wow, I thought.

That's a heckuva sentence.

(I'm a sucker for the "connexion" spelling.)

... I have no idea what it means, though.

I reread it a couple of times until I thought I knew what it meant. (Go ahead. I'll wait.)

I looked at the last few words: "the translation of its principles into explicit practical forms." As a test I asked myself: "What does 'it' refer to?"

I didn't immediately know, which revealed that I still didn't really understand the sentence.

Gosh darn it, I said to myself, I'm going to lick this sentence. I didn't resort to a sentence diagram, but I did a much more forceful attempt at parsing it. Here's how I rewrote it:

There are two ways to view mathematical science.

Most people are "normal". Normal people view mathematical science as merely a vast body of truths. These truths are abstract and immutable. They have intrinsic beauty, symmetry, and logical completeness. They connect together to form a whole. Normal people think that all profound and logical minds give a prominent place to these truths.

But mathematical science possess a deeper interest for the human race. The natural world has great facts. Also, the creation we live amidst has agencies. These agencies have mutual relationships which are unceasingly changing. Sometimes these changes are visible, or otherwise conscious to our immediate physical perceptions. Sometimes they are not. Only the language of mathematical science can adequately express these facts, and these changes.

Some people are "geeks". Geeks think that mathematical truth is an instrument. They think the weak mind of man can most effectually read his Creator's works through this instrument.

Sometimes a special kind of technique is discovered. These techniques tend to translate the principles of mathematical science into explicit practical forms.

Geeks are specially interested in all such techniques.