# Matthew van Eerde's web log

• #### Spock's chess games from Star Trek Ishmael

In his post "A chess problem begging for a solution", Michael Kaplan quotes Barbara Hambly's Star Trek novel Ishmael.  In the quoted scene, Spock (AKA Ishmael) plays a couple of chess games against a stranger - rather unusual chess games.  The problem alluded to is to determine the moves of the games given certain information.

Let's take the second game first.  There are two effective possibilities that meet the "Reverse Fool's mate" and "three moves" criteria:

Reverse Fool's mate, even material: \$200 in 2½ moves

 # Ishmael Stranger 1. e3 f6 2. a3 g5 3. Qh5#

... and...

Reverse Fool's mate plus a pawn: \$220 in 2½ moves

 # Ishmael Stranger 1. e4 f5 2. exf5 g5 3. Qh5#

The task for the first game, then, is to win either \$400 or \$380 in seven moves.  Assuming the game ends in mate (this is reasonable) gives us a difference of either \$200 or \$180.  The first move can not be a capture, so we really only have six moves to capture \$200 worth of material - going after the queen is obvious, but the rooks are quite well tucked away, and it is hard to go after them and simultaneously set up the ending mate.

I believe that the solution that Barbara Hambly had in mind is the following variation of the "other" mate that every chess student learns (Scholar's Mate).  This particular setup is gated by White's need to move his Bishop out of the way, and this nicely satisfies the common convention that players alternate colors in successive games.  Naturally Spock, being a gentleman, would let the stranger take White first.

Mate, a queen, and four pawns: \$380 in 7 moves

 # Stranger Ishmael 1. c4 e6 2. c5 Bxc5 3. d4 Bxd4 4. e3 Bxe3 5. Qf3 Qf6 6. Bc4 Qxf3 7. Kf1 Qxf2#

However, from a "chess problem" point of view, there's a cook.  It is, in fact, possible to get mate plus a queen plus four pawns in a mere five and a half moves, rather than the seven full moves above:

Mate, a queen, and four pawns: \$380 in 5½ moves

 # Ishmael Stranger 1. e3 h5 2. Qxh5 d5 3. Qxd5 Bf5 4. Qxb7 Bh7 5. Qxc7 Qc8 6. Qxc8#

Even worse, there is a way to get \$400 in a mere four and a half moves.

Mate, a queen, a bishop, and a knight: \$400 in 4½ moves

 # Ishmael Stranger 1. d4 Nh6 2. Bxh6 b7 3. Qd3 Ba6 4. Qxa6 Qc8 5. Qxc8#

The problem, as it stands, is therefore underdetermined... Spock and the stranger had a full two and a half moves to play around with in the first game, either to exchange material or perhaps to allow the stranger to pick up a free pawn (and return it in the second game.)

• #### Daylight Saving Time and Benjamin Franklin

Daylight Saving Time is a thorn in my side.

Politician: What time is it?
Scientist: What time would you like it to be?

It is my firm belief that

1. Daylight Saving Time doesn't do any real good.
2. Daylight Saving Time does real harm.
3. Politicians love Daylight Saving Time because it's easy and at least it looks good.
One of the points that my congresswoman brought up is that Daylight Saving Time was originally proposed by a founding father of the US, and that therefore it must be a good idea.  (Exercise: what logical fallacy is this?)

Today I decided to actually look up the original proposal and found it quite enlightening.

Benjamin Franklin's 1784 letter to the Journal de Paris (English translation)

The full article is well worth reading, but this quote will illustrate my point:

I believe all who have common sense, as soon as they have learnt... that it is daylight when the sun rises, will contrive to rise with him; and, to compel the rest, I would propose the following regulations...

let a tax be laid... on every window that is provided with shutters...

[let] no family be permitted to be supplied with more than one pound of candles per week...

Let guards also be posted to stop all the coaches, &c. that would pass the streets after sunset...

Every morning, as soon as the sun rises, let all the bells in every church be set ringing; and if that is not sufficient?, let cannon be fired in every street, to wake the sluggards effectually, and make them open their eyes to see their true interest.

Yes, Benjamin Franklin was the first to propose a law encouraging people to get up early.

But he was joking.

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

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

• #### 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.
-- Augusta Ada Lovelace

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.

-- Augusta Ada Lovelace, paraphrased
• #### Microsoft etiquette: calendar appointments when going out of office

A common convention within Microsoft when going out of office is to create two calendar appointments in Outlook:

1. An appointment which allows people who are trying to schedule a meeting with you to know that you're out of office at the time
1. Attendees: just you
2. Show As: Out of Office
2. An informational appointment which allows people who work closely with you to know when you're going to be out of office
1. Attendees: people who work closely with you (e.g., your immediate team)
2. Show As: Free
3. Request Responses: Off
4. Allow New Time Proposals: Off
5. Reminder: None

I'm always forgetting one of the steps under 2., so I'm creating this blog post. Next time I go out of office I'll remember to check this post.

• #### Troubleshooting default audio device heuristics

In Windows 7 we published a white paper which shows how Windows chooses which audio device should be the default. This remains true for Windows 8 and Windows 8.1.

The six factors that are considered for each device are:

1. Jack detection capability
1. Whether KSJACK_DESCRIPTION2.JackCapabilities has the JACKDESC2_PRESENCE_DETECT_CAPABILITY flag set
2. USB audio devices have jack detection capability grandfathered in
2. Form factor: PKEY_AudioEndpoint_FormFactor
3. Kernel Streaming node type: PKEY_AudioEndpoint_JackSubType (this comes from KSPIN_DESCRIPTOR.Category field set by the driver)
4. Bus type: HD Audio, Bluetooth, USB, etc.
5. General location: IKsJackDescription's KSJACK_DESCRIPTION.GenLocation
6. Geometric location: IKsJackDescrption's KSJACK_DESCRIPTION.GeoLocation

Each factor has an associated preference list and a weight. Generally speaking, items that appear higher in the list above have priority over items that appear lower.

I wrote a tool that uses public APIs to query each of these six factors for all devices on the system. Source and binaries are attached.

Here's what it outputs on my system that has a built-in HD Audio device and an external USB device plugged in:

>defaultaudiodevice.exe
Render devices: 4
Speakers (High Definition Audio Device)
Id: {0.0.0.00000000}.{2089b0a1-893b-45fa-b6e8-ec84ee827c06}
KSJACK_DESCRIPTION2.JackCapabilities: presence detection not supported
PKEY_AudioEndpoint_FormFactor: 1 (Speakers)
PKEY_AudioEndpoint_JackSubType: {DFF21CE1-F70F-11D0-B917-00A0C9223196} (KSNODETYPE_SPEAKER)
PKEY_Device_EnumeratorName: HDAUDIO
KSJACK_DESCRIPTION.GenLocation: 0 (eGenLocPrimaryBox)
KSJACK_DESCRIPTION.GeoLocation: 13 (eGeoLocATAPI)

Speakers (USB Audio)
Id: {0.0.0.00000000}.{4bf6c88a-9b54-46cc-9eb0-91c5fa468ed6}
IKsJackDescription2 not supported
PKEY_AudioEndpoint_FormFactor: 1 (Speakers)
PKEY_AudioEndpoint_JackSubType: {DFF21CE1-F70F-11D0-B917-00A0C9223196} (KSNODETYPE_SPEAKER)
PKEY_Device_EnumeratorName: USB
IKsJackDescription not supported

Speakers (High Definition Audio Device)
Id: {0.0.0.00000000}.{89482885-856d-4b7b-88ed-3ffa4944f14b}
KSJACK_DESCRIPTION2.JackCapabilities: presence detection supported
PKEY_AudioEndpoint_FormFactor: 1 (Speakers)
PKEY_AudioEndpoint_JackSubType: {DFF21CE1-F70F-11D0-B917-00A0C9223196} (KSNODETYPE_SPEAKER)
PKEY_Device_EnumeratorName: HDAUDIO
KSJACK_DESCRIPTION.GenLocation: 0 (eGenLocPrimaryBox)
KSJACK_DESCRIPTION.GeoLocation: 1 (eGeoLocRear)

SPDIF Interface (USB Audio)
Id: {0.0.0.00000000}.{c2c47ae1-abe1-43fa-825a-871bab831cf4}
IKsJackDescription2 not supported
PKEY_AudioEndpoint_FormFactor: 8 (SPDIF)
PKEY_AudioEndpoint_JackSubType: {DFF21FE5-F70F-11D0-B917-00A0C9223196} (KSNODETYPE_SPDIF_INTERFACE)
PKEY_Device_EnumeratorName: USB
IKsJackDescription not supported

Capture devices: 3
Microphone (USB Audio)
Id: {0.0.1.00000000}.{139b7b57-28d2-46de-9fce-702c0944c03f}
IKsJackDescription2 not supported
PKEY_AudioEndpoint_FormFactor: 4 (Microphone)
PKEY_AudioEndpoint_JackSubType: {DFF21BE1-F70F-11D0-B917-00A0C9223196} (KSNODETYPE_MICROPHONE)
PKEY_Device_EnumeratorName: USB
IKsJackDescription not supported

Line (USB Audio)
Id: {0.0.1.00000000}.{67982570-bdea-4524-82ac-3d15d2b5ae89}
IKsJackDescription2 not supported
PKEY_AudioEndpoint_FormFactor: 2 (LineLevel)
PKEY_AudioEndpoint_JackSubType: {DFF21FE3-F70F-11D0-B917-00A0C9223196} (KSNODETYPE_LINE_CONNECTOR)
PKEY_Device_EnumeratorName: USB
IKsJackDescription not supported

SPDIF Interface (USB Audio)
Id: {0.0.1.00000000}.{72b7efb6-c21a-4415-84e5-292d8a5b2b11}
IKsJackDescription2 not supported
PKEY_AudioEndpoint_FormFactor: 8 (SPDIF)
PKEY_AudioEndpoint_JackSubType: {DFF21FE5-F70F-11D0-B917-00A0C9223196} (KSNODETYPE_SPDIF_INTERFACE)
PKEY_Device_EnumeratorName: USB
IKsJackDescription not supported

Jack Detection Capability

The first render device does not have jack presence detection, and the other three do. (Note the USB audio devices have grandfathered-in jack presence detection, even though the USB audio class driver does not support IKsJackDescription2.) This puts the first render device out of the running.

Form Factor

The fourth render device has form factor SPDIF, and the second and third have form factor Speakers. This puts the fourth render device out of the running, since the heuristics consider Speakers more attractive than SPDIF.

Kernel Streaming node type

The two remaining render devices both have form factor KSNODETYPE_SPEAKER, so they are tied.

Bus type

The second render device has bus type USB, and the third render device has bus type HD Audio. The default device heuristics prefer USB to HD Audio, so the second render device becomes the default audio render device.

• #### Sieving irreducible monic polynomials over a finite field

Last time we talked about the addition and multiplication tables for GF(2²); GF(28) is relevant for the Rijndael encryption scheme.

Joan Daemen and Vincent Rijmen use a representation of GF(28) where each element is a polynomial of the form b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x + b0, with the bi being bits. A polynomial is represented by a single byte. Addition is component-wise (modulo 2); two polynomials can be added with a single XOR operation. Multiplication is a little more complicated.

Rijndael defines multiplication as normal polynomial multiplication, followed by taking a modulus using the reduction polynomial mx8 + x4 + x3 + x + 1. Last time we showed that, in GF(2²), x2 + x + 1 was used to reduce polynomial multiplication, and also that a necessary quality for a reduction polynomial is that it be irreducible/prime.

Last time I hinted at the question: how do we show that m is irreducible? Well, one way is to do trial division of all polynomials up to degree 4.

But that's no fun. Instead, let's write a script to generate all irreducible polynomials, and see if m is on it! The approach is very similar to the Sieve of Eratosthenes: generate a list of all the polynomials, then traverse it from the low end to the high end; circle each element that hasn't been crossed out, then cross out all multiples of that element.

The first argument q is the modulus of the coefficients (in this case, 2) and the second argument d (in this case, 8) is how high the degree can go. Here is the output of the script:

>perl polynomial-sieve.pl 2 8
Finding monic irreducible polynomials of degree up to 8 and coefficients mod 2
Generating all monic polynomials...
Sieving out all reducible polynomials...
1
x
x + 1
x^2 + x + 1
x^3 + x + 1
x^3 + x^2 + 1
x^4 + x + 1
x^4 + x^3 + 1
x^4 + x^3 + x^2 + x + 1
x^5 + x^2 + 1
x^5 + x^3 + 1
x^5 + x^3 + x^2 + x + 1
x^5 + x^4 + x^2 + x + 1
x^5 + x^4 + x^3 + x + 1
x^5 + x^4 + x^3 + x^2 + 1
x^6 + x + 1
x^6 + x^3 + 1
x^6 + x^4 + x^2 + x + 1
x^6 + x^4 + x^3 + x + 1
x^6 + x^5 + 1
x^6 + x^5 + x^2 + x + 1
x^6 + x^5 + x^3 + x^2 + 1
x^6 + x^5 + x^4 + x + 1
x^6 + x^5 + x^4 + x^2 + 1
x^7 + x + 1
x^7 + x^3 + 1
x^7 + x^3 + x^2 + x + 1
x^7 + x^4 + 1
x^7 + x^4 + x^3 + x^2 + 1
x^7 + x^5 + x^2 + x + 1
x^7 + x^5 + x^3 + x + 1
x^7 + x^5 + x^4 + x^3 + 1
x^7 + x^5 + x^4 + x^3 + x^2 + x + 1
x^7 + x^6 + 1
x^7 + x^6 + x^3 + x + 1
x^7 + x^6 + x^4 + x + 1
x^7 + x^6 + x^4 + x^2 + 1
x^7 + x^6 + x^5 + x^2 + 1
x^7 + x^6 + x^5 + x^3 + x^2 + x + 1
x^7 + x^6 + x^5 + x^4 + 1
x^7 + x^6 + x^5 + x^4 + x^2 + x + 1
x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1
x^8 + x^4 + x^3 + x + 1
x^8 + x^4 + x^3 + x^2 + 1
x^8 + x^5 + x^3 + x + 1
x^8 + x^5 + x^3 + x^2 + 1
x^8 + x^5 + x^4 + x^3 + 1
x^8 + x^5 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^3 + x^2 + 1
x^8 + x^6 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^5 + x + 1
x^8 + x^6 + x^5 + x^2 + 1
x^8 + x^6 + x^5 + x^3 + 1
x^8 + x^6 + x^5 + x^4 + 1
x^8 + x^6 + x^5 + x^4 + x^2 + x + 1
x^8 + x^6 + x^5 + x^4 + x^3 + x + 1
x^8 + x^7 + x^2 + x + 1
x^8 + x^7 + x^3 + x + 1
x^8 + x^7 + x^3 + x^2 + 1
x^8 + x^7 + x^4 + x^3 + x^2 + x + 1
x^8 + x^7 + x^5 + x + 1
x^8 + x^7 + x^5 + x^3 + 1
x^8 + x^7 + x^5 + x^4 + 1
x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x + 1
x^8 + x^7 + x^6 + x^3 + x^2 + x + 1
x^8 + x^7 + x^6 + x^4 + x^2 + x + 1
x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^2 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
Done!

Note that m is not just prime, it is the lowest of the monic 8-degree polynomials with coefficients mod 2.

The script itself (in Perl) is attached. It makes no claims to being pretty or efficient.

N(q, n) = (Σd|n μ(d) qn/d)/n

where μ(x) is the Möbius function.

In particular:

N(2, 1) = ((1)21/1)/1 = 2
N(2, 2) = ((1)22/1 - (1)22/2)/2 = 1
N(2, 3) = ((1)23/1 - (1)23/3)/3 = 2
N(2, 4) = ((1)24/1 - (1)24/2 + (0)24/4)/4 = 3
N(2, 5) = ((1)25/1 - (1)25/5)/5 = 6
N(2, 6) = ((1)26/1 - (1)26/2 - (1)26/3 + (1)26/6)/6 = 9
N(2, 7) = ((1)27/1 - (1)27/7)/7 = 18
N(2, 8) = ((1)28/1 - (1)28/2 + (0)28/4 + (0)28/8)/8 = 30

This checks out with the script.

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

If the Admin password already has the box checked, this script does nothing.

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

Const ADS_UF_DONT_EXPIRE_PASSWD = &H10000

WScript.Echo "Admin's userFlags are 0x" & Hex(admin.userFlags)

WScript.Echo "Setting local admin account to never expire password"

' Save
End If

• #### shellproperty.exe v2: read all properties on a file; set properties of certain non-VT_LPWSTR types

1. Read all the properties from a given file in one go.
2. Recognize properties by their canonical name (if they have one.)
3. Set a property to VT_EMPTY (removing it), or "VT_VECTOR | VT_LPWSTR", or VT_UI4, in addition to VT_LPWSTR.

Usage:

>shellproperty.exe
shellproperty read [ <key> | all ] from <filename>
shellproperty set <key> on <filename> to <vartype> <vartype-specific-arguments>

<vartype>: VT_EMPTY | VT_LPWSTR | "VT_VECTOR | VT_LPWSTR" | VT_UI4

Example of reading all properties from a file:

>shellproperty read all from "I 01 Track 1.mp3" | sort
{9E5E05AC-1936-4A75-94F7-4704B8B01923} 0: VT_BSTR I 01 Track 1.mp3
{CFA31B45-525D-4998-BB44-3F7D81542FA4} 1: VT_LPWSTR MP3
System.AppUserModel.ID:
System.AppUserModel.ParentID:
System.Audio.ChannelCount: 2 (stereo)
System.Audio.EncodingBitrate: 320kbps
System.Audio.Format: {00000055-0000-0010-8000-00AA00389B71}
System.Audio.IsVariableBitRate: No
System.Audio.PeakValue: 23841
System.Audio.SampleRate: 44 kHz
System.Audio.SampleSize: 16 bit
System.Audio.StreamNumber: 0
System.Author: Unknown artist
System.ComputerName: MATEER-D (this PC)
System.ContentType: audio/mpeg
System.DateAccessed: 9/3/2013 5:55 PM
System.DateCreated: 9/3/2013 5:55 PM
System.DateImported: 9/3/2013 5:55 PM
System.DateModified: 9/24/2013 3:21 PM
System.Document.DateCreated: 9/3/2013 5:55 PM
System.Document.DateSaved: 9/24/2013 3:21 PM
System.DRM.IsProtected: No
System.ExpandoProperties:
System.FileAttributes: A
System.FileAttributesDisplay:
System.FileExtension: .mp3
System.FileName: I 01 Track 1.mp3
System.FileOwner: REDMOND\mateer
System.FilePlaceholderStatus: 7
System.IsFolder: Files
System.IsShared: No
System.ItemAuthors: Unknown artist
System.ItemDate: 9/3/2013 5:55 PM
System.ItemFolderNameDisplay: Les Misérables (concept album)
System.ItemFolderPathDisplay: C:\music\Claude-Michel Schönberg & Alain Boublil\Les Misérables (concept album)
System.ItemFolderPathDisplayNarrow: Les Misérables (concept album) (C:\music\Claude-Michel Schönberg & Alain Boublil)
System.ItemName: I 01 Track 1.mp3
System.ItemNameDisplay: I 01 Track 1.mp3
System.ItemNameDisplayWithoutExtension: I 01 Track 1
System.ItemParticipants: Unknown artist
System.ItemPathDisplay: C:\music\Claude-Michel Schönberg & Alain Boublil\Les Misérables (concept album)\I 01 Track 1.mp3
System.ItemPathDisplayNarrow: I 01 Track 1 (C:\music\Claude-Michel Schönberg & Alain Boublil\Les Misérables (concept album))
System.ItemType: MP3 File
System.ItemTypeText: MP3 File
System.Kind: Music
System.KindText: Music
System.Media.AverageLevel: 4219
System.Media.ClassPrimaryID: {D1607DBC-E323-4BE2-86A1-48A42A28441E}
System.Media.ClassSecondaryID: {00000000-0000-0000-0000-000000000000}
System.Media.CollectionGroupID: {3B02CC9D-BE3E-43A4-81AA-DC23DFD20083}
System.Media.CollectionID: {3B02CC9D-BE3E-43A4-81AA-DC23DFD20083}
System.Media.ContentID: {3780156C-B516-4897-B6AC-CB632A0CA4A5}
System.Media.DlnaProfileID: MP3
System.Media.Duration: 00:04:47
System.Media.Publisher: Colosseum
System.Media.UniqueFileIdentifier: AMGt_id=T 987037;AMGp_id=P 1857378;AMGa_id=R 189777;X_id={9D0F0F00-0500-11DB-89CA-0019B92A3933};XA_id={51E50200-0400-11DB-89CA-0019B92A3933};XAP_id={6357088C-778C-11DC-9403-0019B9B20868}
System.Media.Year: 1989
System.MIMEType: audio/mpeg
System.Music.AlbumArtist: Various Artists
System.Music.AlbumID: Various Artists - Les Miserables - French Concept Album: 1 of 2
System.Music.AlbumTitle: Les Miserables - French Concept Album: 1 of 2
System.Music.Artist: Unknown artist
System.Music.Composer: Alain Boublil; Claude-Michel Schönberg
System.Music.DisplayArtist: Various Artists
System.Music.Genre: Unknown genre
System.Music.PartOfSet: 1/1
System.Music.TrackNumber: 1
System.NetworkLocation:
System.NotUserContent: No
System.OfflineAvailability: Available offline
System.OfflineStatus:
System.ParsingName: I 01 Track 1.mp3
System.ParsingPath: C:\music\Claude-Michel Schönberg & Alain Boublil\Les Misérables (concept album)\I 01 Track 1.mp3
System.PerceivedType: Audio
System.SFGAOFlags: 1077936503
System.SharedWith:
System.ShareScope: music\Claude-Michel Schönberg & Alain Boublil\Les Misérables (concept album)
System.SharingStatus: Not shared
System.Shell.SFGAOFlagsStrings: filesys; stream
System.Size: 10.9 MB
System.ThumbnailCacheId: 16520045390528741485
System.Title: Track 1
System.VolumeId: {14FF6E9D-14F5-11E3-824C-806E6F6E6963}
System.ZoneIdentifier: 0

Example of updating a file:

>type _fixup.bat
@echo off

for /f "usebackq delims=" %%f in (`dir /s /b "I *.mp3"`) do (
shellproperty set System.Music.AlbumTitle on "%%f" to VT_LPWSTR "Madama Butterfly - Sinopoli / Freni: 1 of 3"
)

for /f "usebackq delims=" %%f in (`dir /s /b "II *.mp3"`) do (
shellproperty set System.Music.AlbumTitle on "%%f" to VT_LPWSTR "Madama Butterfly - Sinopoli / Freni: 2 of 3"
)

for /f "usebackq delims=" %%f in (`dir /s /b "III *.mp3"`) do (
shellproperty set System.Music.AlbumTitle on "%%f" to VT_LPWSTR "Madama Butterfly - Sinopoli / Freni: 3 of 3"
)

Source and binaries (x86 and amd64) attached.

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

Think of cookie parties.

If you have 100 cookies, you could have a cookie party:

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

• #### 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 = SHLoadLibraryFromKnownFolder(library GUID)
pShellLibrary->Commit()
CoUninitialize

Usage:

>shelllibrary
shelllibrary add <path> to <library>
<path> must already exist
<library> must be one of:
documents
music
pictures
videos
recorded tv
>shelllibrary add C:\music to Music
Added C:\music to Music library

Source and binaries attached.

• #### Generating sample first names

I had a need to write a script that would give me a random first name.  I grabbed the top 200 first names for baby boys in the US from 2000-2009, and the same list for baby girls:

 Boys Girls Jacob Emily Michael Madison ... ...

My initial implementation just printed out the name, but I quickly realized I needed to print out the gender if I wanted to talk about what the (fictitious) person did.  So I updated it to print out the gender as well.

In the course of this I realized that some names appeared on both lists.  In particular they are:

• Alexis
• Angel
• Jordan
• Peyton
• Riley

The script is called like this:

>perl -w name.pl
Wesley (male)

And here's the source:

use strict;

# prints a randomly chosen name

my @words = read_words();
print \$words[ rand(@words) ];

my @words = <DATA>;

chomp @words;

return @words;
}
__DATA__
Aaliyah (female)
Aaron (male)
Abby (female)
Abigail (female)
Abraham (male)
Aidan (male)
Aiden (male)
Alan (male)
Alana (female)
Alejandro (male)
Alex (male)
Alexa (female)
Alexander (male)
Alexandra (female)
Alexandria (female)
Alexia (female)
Alexis (female)
Alexis (male)
Alicia (female)
Allison (female)
Alondra (female)
Alyssa (female)
Amanda (female)
Amber (female)
Amelia (female)
Amy (female)
Ana (female)
Andrea (female)
Andres (male)
Andrew (male)
Angel (female)
Angel (male)
Angela (female)
Angelica (female)
Angelina (female)
Anna (female)
Anthony (male)
Antonio (male)
Ariana (female)
Arianna (female)
Ashley (female)
Ashlyn (female)
Ashton (male)
Aubrey (female)
Audrey (female)
Austin (male)
Autumn (female)
Ava (female)
Avery (female)
Ayden (male)
Bailey (female)
Benjamin (male)
Bianca (female)
Blake (male)
Brandon (male)
Brayden (male)
Breanna (female)
Brendan (male)
Brian (male)
Briana (female)
Brianna (female)
Brittany (female)
Brody (male)
Brooke (female)
Brooklyn (female)
Bryan (male)
Bryce (male)
Bryson (male)
Caitlin (female)
Caitlyn (female)
Caleb (male)
Cameron (male)
Camila (female)
Carlos (male)
Caroline (female)
Carson (male)
Carter (male)
Cassandra (female)
Cassidy (female)
Catherine (female)
Cesar (male)
Charles (male)
Charlotte (female)
Chase (male)
Chelsea (female)
Cheyenne (female)
Chloe (female)
Christian (male)
Christina (female)
Christopher (male)
Claire (female)
Cody (male)
Colby (male)
Cole (male)
Colin (male)
Collin (male)
Colton (male)
Conner (male)
Connor (male)
Cooper (male)
Courtney (female)
Cristian (male)
Crystal (female)
Daisy (female)
Dakota (male)
Dalton (male)
Damian (male)
Daniel (male)
Daniela (female)
Danielle (female)
David (male)
Delaney (female)
Derek (male)
Destiny (female)
Devin (male)
Devon (male)
Diana (female)
Diego (male)
Dominic (male)
Donovan (male)
Dylan (male)
Edgar (male)
Eduardo (male)
Edward (male)
Edwin (male)
Eli (male)
Elias (male)
Elijah (male)
Elizabeth (female)
Ella (female)
Ellie (female)
Emily (female)
Emma (female)
Emmanuel (male)
Eric (male)
Erica (female)
Erick (male)
Erik (male)
Erin (female)
Ethan (male)
Eva (female)
Evan (male)
Evelyn (female)
Faith (female)
Fernando (male)
Francisco (male)
Gabriel (male)
Gabriela (female)
Gabriella (female)
Gabrielle (female)
Gage (male)
Garrett (male)
Gavin (male)
Genesis (female)
George (male)
Gianna (female)
Giovanni (male)
Giselle (female)
Grace (female)
Gracie (female)
Grant (male)
Gregory (male)
Hailey (female)
Haley (female)
Hannah (female)
Hayden (male)
Hector (male)
Henry (male)
Hope (female)
Hunter (male)
Ian (male)
Isaac (male)
Isabel (female)
Isabella (female)
Isabelle (female)
Isaiah (male)
Ivan (male)
Jack (male)
Jackson (male)
Jacob (male)
Jacqueline (female)
Jake (male)
Jalen (male)
James (male)
Jared (male)
Jasmin (female)
Jasmine (female)
Jason (male)
Javier (male)
Jayden (male)
Jayla (female)
Jazmin (female)
Jeffrey (male)
Jenna (female)
Jennifer (female)
Jeremiah (male)
Jeremy (male)
Jesse (male)
Jessica (female)
Jesus (male)
Jillian (female)
Jocelyn (female)
Joel (male)
John (male)
Johnathan (male)
Jonah (male)
Jonathan (male)
Jordan (female)
Jordan (male)
Jordyn (female)
Jorge (male)
Jose (male)
Joseph (male)
Joshua (male)
Josiah (male)
Juan (male)
Julia (female)
Julian (male)
Juliana (female)
Justin (male)
Kaitlyn (female)
Kaleb (male)
Karen (female)
Karina (female)
Kate (female)
Katelyn (female)
Katherine (female)
Kathryn (female)
Katie (female)
Kayla (female)
Kaylee (female)
Kelly (female)
Kelsey (female)
Kendall (female)
Kennedy (female)
Kenneth (male)
Kevin (male)
Kiara (female)
Kimberly (female)
Kyle (male)
Kylee (female)
Kylie (female)
Landon (male)
Laura (female)
Lauren (female)
Layla (female)
Leah (female)
Leonardo (male)
Leslie (female)
Levi (male)
Liam (male)
Liliana (female)
Lillian (female)
Lilly (female)
Lily (female)
Lindsey (female)
Logan (male)
Lucas (male)
Lucy (female)
Luis (male)
Luke (male)
Lydia (female)
Mackenzie (female)
Makayla (female)
Makenzie (female)
Malachi (male)
Manuel (male)
Marco (male)
Marcus (male)
Margaret (female)
Maria (female)
Mariah (female)
Mario (male)
Marissa (female)
Mark (male)
Martin (male)
Mary (female)
Mason (male)
Matthew (male)
Max (male)
Maxwell (male)
Maya (female)
Mckenzie (female)
Megan (female)
Melanie (female)
Melissa (female)
Mia (female)
Micah (male)
Michael (male)
Michelle (female)
Miguel (male)
Mikayla (female)
Miranda (female)
Molly (female)
Morgan (female)
Mya (female)
Naomi (female)
Natalia (female)
Natalie (female)
Nathan (male)
Nathaniel (male)
Nevaeh (female)
Nicholas (male)
Nicolas (male)
Nicole (female)
Noah (male)
Nolan (male)
Oliver (male)
Olivia (female)
Omar (male)
Oscar (male)
Owen (male)
Paige (female)
Parker (male)
Patrick (male)
Paul (male)
Payton (female)
Peter (male)
Peyton (female)
Peyton (male)
Preston (male)
Rachel (female)
Raymond (male)
Reagan (female)
Rebecca (female)
Ricardo (male)
Richard (male)
Riley (female)
Riley (male)
Robert (male)
Ruby (female)
Ryan (male)
Rylee (female)
Sabrina (female)
Samantha (female)
Samuel (male)
Sara (female)
Sarah (female)
Savannah (female)
Sean (male)
Sebastian (male)
Serenity (female)
Sergio (male)
Seth (male)
Shane (male)
Shawn (male)
Shelby (female)
Sierra (female)
Skylar (female)
Sofia (female)
Sophia (female)
Sophie (female)
Spencer (male)
Stephanie (female)
Stephen (male)
Steven (male)
Summer (female)
Sydney (female)
Tanner (male)
Taylor (female)
Thomas (male)
Tiffany (female)
Timothy (male)
Travis (male)
Trenton (male)
Trevor (male)
Trinity (female)
Tristan (male)
Tyler (male)
Valeria (female)
Valerie (female)
Vanessa (female)
Veronica (female)
Victor (male)
Victoria (female)
Vincent (male)
Wesley (male)
William (male)
Wyatt (male)
Xavier (male)
Zachary (male)
Zoe (female)
Zoey (female)

• #### How to dump Speech API object properties

Stamatis Pap asked in a forum thread how to use a Speech API ISpVoice with a non-default audio deviceThis MSDN article shows how to use SpEnumTokens to list all the currently active audio outputs, but the number and order of audio outputs is subject to change as things come and go, or as the default audio device changes.

I spent some time poking around the Speech API documentation and discovered that each audio output object has a DeviceId string value which is the WASAPI endpoint ID; this is the way to recognize a given audio output rather than relying on enumeration order.

As part of figuring this out, as a side effect I created a command-line tool to dump all the speech objects and all of their properties.

Source and binaries attached.

Pseudocode:

for each object category in
(audio outputs; audio inputs; voices; recognizers; etc.)
SpEnumTokens(category)
ISpEnumTokens::GetCount();

for each token
ISpEnumTokens::Next(1);

SpGetDescription(ISpObjectToken);
Log the description

the ISpObjectToken is also an ISpDataKey
the ISpDataKey may also contain subkeys
log all subkeys and their values recursively
using ISpDataKey::EnumKeys and ISpDataKey::OpenKey
for each subkey including this one
log all values in the ISpDataKey
using ISpDataKey::EnumValues and ISpDataKey::GetStringValue

Here's the output on my system.  Note the audio output has a DeviceId string value which matches the WASAPI endpoint ID.

>speech-attributes.exe

-- SPCAT_AUDIOOUT --
#1: [[Speakers] ([High Definition Audio Device])]
Attributes
Vendor = Microsoft
Technology = MMSys
(default) = [[Speakers] ([High Definition Audio Device])]
CLSID = {A8C680EB-3D32-11D2-9EE7-00C04F797396}
DeviceName = [[Speakers] ([High Definition Audio Device])]
DeviceId = {0.0.0.00000000}.{c2cbdacb-a70d-4629-8368-542a00f5a4b0}

-- SPCAT_AUDIOIN --

-- SPCAT_VOICES --
#1: Microsoft Zira Desktop - English (United States)
Attributes
Version = 10.4
Language = 409
Gender = Female
SharedPronunciation =
Name = Microsoft Zira Desktop
Vendor = Microsoft
(default) = Microsoft Zira Desktop - English (United States)
LangDataPath = C:\Windows\Speech\Engines\TTS\en-US\MSTTSLocEnUS.dat
VoicePath = C:\Windows\Speech\Engines\TTS\en-US\M1033ZIR
409 = Microsoft Zira Desktop - English (United States)
CLSID = {C64501F6-E6E6-451f-A150-25D0839BC510}

-- SPCAT_RECOGNIZERS --

-- SPCAT_APPLEXICONS --

-- SPCAT_PHONECONVERTERS --
#1: Simplified Chinese Phone Converter
Attributes
Language = 804
(default) = Simplified Chinese Phone Converter
PhoneMap = (lengthy value redacted)
CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
#2: English Phone Converter
Attributes
Language = 409
(default) = English Phone Converter
PhoneMap = (lengthy value redacted)
CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
#3: French Phone Converter
Attributes
Language = 40C
(default) = French Phone Converter
PhoneMap = (lengthy value redacted)
CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
#4: German Phone Converter
Attributes
Language = 407
(default) = German Phone Converter
PhoneMap = (lengthy value redacted)
CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
#5: Japanese Phone Converter
Attributes
Language = 411
NumericPhones =
NoDelimiter =
(default) = Japanese Phone Converter
PhoneMap = (lengthy value redacted)
CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
#6: Spanish Phone Converter
Attributes
Language = 40A;C0A
(default) = Spanish Phone Converter
PhoneMap = (lengthy value redacted)
CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
#7: Traditional Chinese Phone Converter
Attributes
Language = 404
NumericPhones =
NoDelimiter =
(default) = Traditional Chinese Phone Converter
PhoneMap = (lengthy value redacted)
CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
#8: Universal Phone Converter
Attributes
Language = (lengthy value redacted)
(default) = Universal Phone Converter
PhoneMap = (lengthy value redacted)
CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}

-- SPCAT_RECOPROFILES --
None found.

• #### 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 *head = nullptr;
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;
}

if (nullptr == head) {
// 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 {
LOG(L"Error reading from STDIN");
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;
}

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

• #### 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)
Session instance identifier: {0.0.0.00000000}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|\Device\HarddiskVolume1\Windows\System32\WWAHost.exe%b{00000000-0000-0000-0000-000000000000}|1%b11812
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)
Session instance identifier: {0.0.0.00000000}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|#%b{48FF2ED2-2CE8-40FB-AEF7-31FEFDBA7EF2}|1%b#
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)
Session instance identifier: {0.0.0.00000000}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|#%b{A9EF3FD9-4240-455E-A4D5-F2B3301887B2}|1%b#
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 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}
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 GUID to a string and logs it using %s. Another way is to use a couple of macros and let the format string do the conversion for you:

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

Session instance identifier: {0.0.0.00000000}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|\Device\HarddiskVolume1\Windows\System32\WWAHost.exe%b{00000000-0000-0000-0000-000000000000}|1%b11812

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)
Session instance identifier: {0.0.0.00000000}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|\Device\HarddiskVolume1\Windows\System32\WWAHost.exe%b{00000000-0000-0000-0000-000000000000}|1%b11644
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.

• #### A mental model for the Windows Phone AudioRoutingManager API

The Windows Phone SDK includes a Windows.Phone.Media.Devices.AudioRoutingManager API which I had occasion to use.

The API allows apps that have communication audio streams (e.g., Voice over IP calls) to control whether the audio goes out over the earpiece, over the speakerphone, or over the Bluetooth headset. This might be done automatically, or might be used to power "Speakerphone" and "Bluetooth" buttons in the app UI.

The starting point is a GetDefault() method which gives you the singleton AudioRoutingManager object.

There are three ways to get information out of this object:

1. A read-only AvailableAudioEndpoints property tells you the list of currently available audio outputs.
2. A GetAudioEndpoint method tells you what the current audio output is.
3. An AudioEndpointChanged callback tells you when either of the previous two things change.

You can also tell the object to change something:

1. SetAudioEndpoint(…) lets you tell Windows Phone where audio should come out, subject to some restrictions.

There are two enumerated types used by these methods:

1. AvailableAudioRoutingEndpoints, which is the type of the AvailableAudioEndpoints property. This is a "flags"-style (multi-valued) enum with the following values:
• None
• Earpiece
• Speakerphone
• Bluetooth
2. AudioRoutingEndpoint, which is returned by GetAudioEndpoint and is the sole argument for SetAudioEndpoint. This is a single-valued enum with the following values:
• Default
• Earpiece
• Speakerphone
• Bluetooth
• BluetoothWithNoiseAndEchoCancellation

At first I found this very confusing. SetAudioEndpoint takes an AudioRoutingEndpoint type, but what do I pass to it? And why does GetAudioEndpoint always tell me "Speakerphone?"

After experimenting and chatting with the folks who own the API I was able to construct an internal mental model which made more sense to me.

1. While communications audio is playing, the Phone has an audio routing policy. Imagine an AudioRoutingPolicy write-only property with the following values:
• I'm flexible: play to the first available of { wired headset, Bluetooth device, earpiece }
• Gimme Bluetooth: play to the first available of { Bluetooth device, wired headset, earpiece }
• No Bluetooth: play to the first available of { wired headset, earpiece }
• Speakerphone: play to the built-in speaker
2. If you want to change this policy, the app needs to have either the ID_CAP_VOIP or ID_CAP_VOICEMAIL capability. (The documentation refers to an ID_CAP_AUDIOROUTING capability, but this does not exist.)
Do:
var audioRoutingManager = Windows.Phone.Media.Devices.AudioRoutingManager.GetDefault();
audioRoutingManager.SetAudioEndpoint(x);

where xis as follows:
• x = AudioRoutingEndpoint.Bluetooth sets the policy to Gimme Bluetooth
• x = AudioRoutingEndpoint.Earpiece sets the policy to No Bluetooth
• x = AudioRoutingEndpoint.Speakerphone sets the policy to Speakerphone
3. There is no direct way to set the policy to I'm flexible.
4. There is no direct way to tell what the current value of the AudioRoutingPolicy is. You can sometimes guess, though, based on the value of GetAudioEndpoint and/or AvailableAudioEndpoints.
• If GetAudioEndpoint is AudioRoutingEndpoint.Speakerphone, then the current policy must be Speakerphone.
• If GetAudioEndpoint is AudioRoutingEndpoint.Earpiece and AvailableAudioEndpoints & AvailableAudioRoutingEndpoints.Bluetooth is set, then the current policy must be No Bluetooth.
• If GetAudioEndpoint is AudioRoutingEndpoint.WiredHeadset and AvailableAudioEndpoints & AvailableAudioRoutingEndpoints.Bluetooth is set, then the current policy must be either I'm flexible or No Bluetooth.
• If GetAudioEndpoint is AudioRoutingEndpoint.Bluetooth or AudioRoutingEndpoint.BluetoothWithNoiseAndEchoCancelation, then AvailableAudioEndpoints & AvailableAudioRoutingEndpoints.Bluetooth must be set, and the current policy must be either I'm flexible or Gimme Bluetooth.
5. When there are no audio communications streams, the policy is undefined.
6. When the number of audio communications streams goes from zero to one (perhaps as the result of a phone call or VoIP call), the policy is reset/defaulted to I'm flexible or No Bluetooth depending on the details. This means you shouldn't bother setting a policy until after your phone call starts playing audio.
7. When a device is connected (a Bluetooth device is connected, or a wired headset is plugged in) the policy is reset to I'm flexible. This (usually) results in audio switching to the new device, which is usually what the user wants.
(If a device is removed, on the other hand, the policy is not reset.)

Here's a chart I put together on how the different states and policies interact:

 If a Bluetooth Hands-Free HF device is: Connected AvailableAudioEndpoints =   Speakerphone | Earpiece | Bluetooth Not connected AvailableAudioEndpoints =   Speakerphone | Earpiece I'm flexible audio routing policy is: This policy may be automatically invoked when:   a call starts, or   a device connects WiredHeadset or WiredHeadsetSpeakerOnly or Bluetooth or BluetoothWith... Depending on what is plugged in, and the capabilities of the device WiredHeadset or WiredHeadsetSpeakerOnly or Earpiece Depending on what is plugged in Gimme Bluetooth audio routing policy is: This policy may be automatically invoked when a call starts You can manually invoke it with:   SetAudioEndpoint(Bluetooth) Bluetooth or BluetoothWith... Depending on the capabilities of the device WiredHeadset or WiredHeadsetSpeakerOnly or Earpiece Depending on what is plugged in No Bluetooth audio routing policy is: You can manually invoke this policy with:   SetAudioEndpoint(Earpiece) or   SetAudioEndpoint(Default) WiredHeadset or WiredHeadsetSpeakerOnly or Earpiece Depending on what is plugged in Speakerphone audio routing policy is: You can manually invoke this policy with:   SetAudioEndpoint(Speakerphone) Speakerphone Invalid audio routing policies: The following calls are all errors:   SetAudioEndpoint(WiredHeadset)   SetAudioEndpoint(WiredHeadsetSpeakerOnly)   SetAudioEndpoint(BluetoothWith...) N/A SetAudioEndpoint throws an exception

Note that if a wired headset is plugged in, the app has no way to make audio come out of the earpiece. This is true regardless of whether Bluetooth is connected.

It seems like much of my confusion resulted from a single enumerated type (AudioRoutingEndpoint) serving three purposes:

1. Tell the app where audio is coming out (WiredHeadset vs. Earpiece)
2. Tell the app what the capabilities of the current output are (Bluetooth vs. BluetoothWithNoiseAndEchoCancellation)
3. Allow the app to control the audio routing policy (Default vs. Speakerphone)

I think it would have been clearer to make the audio routing policy a different enumerated type from the current audio output or the available audio outputs. But with the "audio routing policy" mental model, it's not too bad.

• #### Efficient multiplication and division in GF(2⁸)

I talked about Rijndael in a couple of previous posts: Sieving irreducible monic polynomials over a finite field, Addition and multiplication table for GF(2²)

I'm going to talk some more about it today.

Rijndael does a lot of arithmetic operations (addition and multiplication) on elements of GF(28)4.

These are represented as polynomials b0 + b1 x + b2 x2 + b3 x3.

The individual coefficients bi are elements of GF(28).

These are themselves polynomials a0 + a1 x + ... + a7 x7 where the individual coefficients ai are bits (0 or 1).

Multiplication bi bj is made into a closed operation by taking the modulus of the product under the reduction polynomial m = x8 + x4 + x3 + x + 1.

The reduction polynomial is prime, which is important in establishing that this representation of the Galois field really is a field.

For convenience we will represent the elements of GF(28) as hexadecimal numbers 0x00, 0x01, ... 0xfe, 0xff.

By contrast, we will represent the elements of GF(28)4 as vectors (b0 b1 b2 b3); for example, (0x00 0x01 0x02 0x03).

Multiplying vectors in GF(28)4 induces a bunch of multiplications in GF(28). It would be good to come up with a way to make this fast. Doing a polynomial reduction every time is not fast.

Of course, one way to do this is to create a multiplication table with 256 rows and 256 columns, do each multiplication the slow way once, and compile in the results. This would require on the order of 64 kB. But there's a better way.

The trick that is used in Daemen and Rijmen's implementation is to find a primitive element e in GF(28) so that the orbit of e (that is to say, the set {e0, e1, ..., e254}) spans all of GF(28) - {0x00}.

If we find such an e, then we can save a cheat sheet which is almost as fast as the multiplication table, but requires storing only on the order of 256 bytes.

Well, let's calculate the orbits of all the elements in order until we find a primitive element.

Orbit(0x00) = { 0x000, 0x001, 0x002, ... } = { 0x01, 0x00, 0x00, ... } = { 0x00, 0x01 }. Nope.
Orbit(0x01) = { 0x010, 0x011, 0x012, ... } = { 0x01, 0x01, 0x01, ... } = { 0x01 }. Even worse.
Orbit(0x02) = { 0x020, 0x021, 0x022, ... } = { 0x01, 0x02, 0x04, ..., 0x8d }. This looks promising at first but we end up with an orbit of only 51 out of the necessary 255 elements (note that 51 divides 255:)

0x020 = 0x01
0x021 = 0x02
0x022 = 0x04
0x023 = 0x08
0x024 = 0x10
0x025 = 0x20
0x026 = 0x40
0x027 = 0x80
0x028 = 0x1b
0x029 = 0x36
0x0210 = 0x6c
0x0211 = 0xd8
0x0212 = 0xab
0x0213 = 0x4d
0x0214 = 0x9a
0x0215 = 0x2f
0x0216 = 0x5e
0x0217 = 0xbc
0x0218 = 0x63
0x0219 = 0xc6
0x0220 = 0x97
0x0221 = 0x35
0x0222 = 0x6a
0x0223 = 0xd4
0x0224 = 0xb3
0x0225 = 0x7d
0x0226 = 0xfa
0x0227 = 0xef
0x0228 = 0xc5
0x0229 = 0x91
0x0230 = 0x39
0x0231 = 0x72
0x0232 = 0xe4
0x0233 = 0xd3
0x0234 = 0xbd
0x0235 = 0x61
0x0236 = 0xc2
0x0237 = 0x9f
0x0238 = 0x25
0x0239 = 0x4a
0x0240 = 0x94
0x0241 = 0x33
0x0242 = 0x66
0x0243 = 0xcc
0x0244 = 0x83
0x0245 = 0x1d
0x0246 = 0x3a
0x0247 = 0x74
0x0248 = 0xe8
0x0249 = 0xcb
0x0250 = 0x8d
And then we circle back around to...
0x0251 = 0x01

Well, let's keep looking. What about 0x03?

Orbit(0x03) = { 0x030, 0x031, 0x032, ... } = { 0x01, 0x03, 0x05, ..., 0xf6 }. Bingo, we hit all 255 non-0x00 elements!

0x030 = 0x01
0x031 = 0x03
0x032 = 0x05
0x033 = 0x0f
0x034 = 0x11
0x035 = 0x33
0x036 = 0x55
0x037 = 0xff
0x038 = 0x1a
0x039 = 0x2e
0x0310 = 0x72
0x0311 = 0x96
0x0312 = 0xa1
0x0313 = 0xf8
0x0314 = 0x13
0x0315 = 0x35
0x0316 = 0x5f
0x0317 = 0xe1
0x0318 = 0x38
0x0319 = 0x48
0x0320 = 0xd8
0x0321 = 0x73
0x0322 = 0x95
0x0323 = 0xa4
0x0324 = 0xf7
0x0325 = 0x02
0x0326 = 0x06
0x0327 = 0x0a
0x0328 = 0x1e
0x0329 = 0x22
0x0330 = 0x66
0x0331 = 0xaa
0x0332 = 0xe5
0x0333 = 0x34
0x0334 = 0x5c
0x0335 = 0xe4
0x0336 = 0x37
0x0337 = 0x59
0x0338 = 0xeb
0x0339 = 0x26
0x0340 = 0x6a
0x0341 = 0xbe
0x0342 = 0xd9
0x0343 = 0x70
0x0344 = 0x90
0x0345 = 0xab
0x0346 = 0xe6
0x0347 = 0x31
0x0348 = 0x53
0x0349 = 0xf5
0x0350 = 0x04
0x0351 = 0x0c
0x0352 = 0x14
0x0353 = 0x3c
0x0354 = 0x44
0x0355 = 0xcc
0x0356 = 0x4f
0x0357 = 0xd1
0x0358 = 0x68
0x0359 = 0xb8
0x0360 = 0xd3
0x0361 = 0x6e
0x0362 = 0xb2
0x0363 = 0xcd
0x0364 = 0x4c
0x0365 = 0xd4
0x0366 = 0x67
0x0367 = 0xa9
0x0368 = 0xe0
0x0369 = 0x3b
0x0370 = 0x4d
0x0371 = 0xd7
0x0372 = 0x62
0x0373 = 0xa6
0x0374 = 0xf1
0x0375 = 0x08
0x0376 = 0x18
0x0377 = 0x28
0x0378 = 0x78
0x0379 = 0x88
0x0380 = 0x83
0x0381 = 0x9e
0x0382 = 0xb9
0x0383 = 0xd0
0x0384 = 0x6b
0x0385 = 0xbd
0x0386 = 0xdc
0x0387 = 0x7f
0x0388 = 0x81
0x0389 = 0x98
0x0390 = 0xb3
0x0391 = 0xce
0x0392 = 0x49
0x0393 = 0xdb
0x0394 = 0x76
0x0395 = 0x9a
0x0396 = 0xb5
0x0397 = 0xc4
0x0398 = 0x57
0x0399 = 0xf9
0x03100 = 0x10
0x03101 = 0x30
0x03102 = 0x50
0x03103 = 0xf0
0x03104 = 0x0b
0x03105 = 0x1d
0x03106 = 0x27
0x03107 = 0x69
0x03108 = 0xbb
0x03109 = 0xd6
0x03110 = 0x61
0x03111 = 0xa3
0x03112 = 0xfe
0x03113 = 0x19
0x03114 = 0x2b
0x03115 = 0x7d
0x03116 = 0x87
0x03117 = 0x92
0x03119 = 0xec
0x03120 = 0x2f
0x03121 = 0x71
0x03122 = 0x93
0x03123 = 0xae
0x03124 = 0xe9
0x03125 = 0x20
0x03126 = 0x60
0x03127 = 0xa0
0x03128 = 0xfb
0x03129 = 0x16
0x03130 = 0x3a
0x03131 = 0x4e
0x03132 = 0xd2
0x03133 = 0x6d
0x03134 = 0xb7
0x03135 = 0xc2
0x03136 = 0x5d
0x03137 = 0xe7
0x03138 = 0x32
0x03139 = 0x56
0x03140 = 0xfa
0x03141 = 0x15
0x03142 = 0x3f
0x03143 = 0x41
0x03144 = 0xc3
0x03145 = 0x5e
0x03146 = 0xe2
0x03147 = 0x3d
0x03148 = 0x47
0x03149 = 0xc9
0x03150 = 0x40
0x03151 = 0xc0
0x03152 = 0x5b
0x03153 = 0xed
0x03154 = 0x2c
0x03155 = 0x74
0x03156 = 0x9c
0x03157 = 0xbf
0x03158 = 0xda
0x03159 = 0x75
0x03160 = 0x9f
0x03161 = 0xba
0x03162 = 0xd5
0x03163 = 0x64
0x03164 = 0xac
0x03165 = 0xef
0x03166 = 0x2a
0x03167 = 0x7e
0x03168 = 0x82
0x03169 = 0x9d
0x03170 = 0xbc
0x03171 = 0xdf
0x03172 = 0x7a
0x03173 = 0x8e
0x03174 = 0x89
0x03175 = 0x80
0x03176 = 0x9b
0x03177 = 0xb6
0x03178 = 0xc1
0x03179 = 0x58
0x03180 = 0xe8
0x03181 = 0x23
0x03182 = 0x65
0x03183 = 0xaf
0x03184 = 0xea
0x03185 = 0x25
0x03186 = 0x6f
0x03187 = 0xb1
0x03188 = 0xc8
0x03189 = 0x43
0x03190 = 0xc5
0x03191 = 0x54
0x03192 = 0xfc
0x03193 = 0x1f
0x03194 = 0x21
0x03195 = 0x63
0x03196 = 0xa5
0x03197 = 0xf4
0x03198 = 0x07
0x03199 = 0x09
0x03200 = 0x1b
0x03201 = 0x2d
0x03202 = 0x77
0x03203 = 0x99
0x03204 = 0xb0
0x03205 = 0xcb
0x03206 = 0x46
0x03207 = 0xca
0x03208 = 0x45
0x03209 = 0xcf
0x03210 = 0x4a
0x03211 = 0xde
0x03212 = 0x79
0x03213 = 0x8b
0x03214 = 0x86
0x03215 = 0x91
0x03216 = 0xa8
0x03217 = 0xe3
0x03218 = 0x3e
0x03219 = 0x42
0x03220 = 0xc6
0x03221 = 0x51
0x03222 = 0xf3
0x03223 = 0x0e
0x03224 = 0x12
0x03225 = 0x36
0x03226 = 0x5a
0x03227 = 0xee
0x03228 = 0x29
0x03229 = 0x7b
0x03230 = 0x8d
0x03231 = 0x8c
0x03232 = 0x8f
0x03233 = 0x8a
0x03234 = 0x85
0x03235 = 0x94
0x03236 = 0xa7
0x03237 = 0xf2
0x03238 = 0x0d
0x03239 = 0x17
0x03240 = 0x39
0x03241 = 0x4b
0x03242 = 0xdd
0x03243 = 0x7c
0x03244 = 0x84
0x03245 = 0x97
0x03246 = 0xa2
0x03247 = 0xfd
0x03248 = 0x1c
0x03249 = 0x24
0x03250 = 0x6c
0x03251 = 0xb4
0x03252 = 0xc7
0x03253 = 0x52
0x03254 = 0xf6
... and only now do we circle around to...
0x03255 = 0x01

This gives us a one-to-one mapping between the 255 powers 0 through 254 and the 255 non-zero bytes 0x01 through 0xff.

Here are the perl scripts I used to generate these:

use strict;

my \$m = 0x11b;

my \$a = 1;
for (my \$i = 0; ; \$i++) {
printf("0x02^%2d = 0x%02x\n", \$i, \$a);
if (\$i > 0 and \$a == 1) { last; }
\$a <<= 1; # * 0x02
if (\$a > 0xff) { \$a ^= \$m; }
}

print "\n";

\$a = 1;
for (my \$i = 0; ; \$i++) {
printf("0x03^%3d = 0x%02x\n", \$i, \$a);
if (\$i > 0 and \$a == 1) { last; }
\$a = (\$a << 1) ^ \$a; # * 0x03
if (\$a > 0xff) { \$a ^= \$m; }
}

Now that we have this orbit, we use it to construct two lookup tables:

// 255 entries xPlusOne_ToThe[0] = 0x01 to xPlusOne_ToThe[254] = 0xf6
xPlusOne_ToThe[] = { 0x01, 0x03, 0x05, ..., 0x52, 0xf6 };

And the inverse mapping:

// 255 entries logXPlusOne_Of[0x01] = 0 to logXPlusOne_Of[0xff] = 7
logXPlusOne_Of[] = { UNDEFINED, 0, 25, 1, 50, ..., 112, 7 };

Now that we have paid for these 512-ish bytes, we can do multiplication very cheaply:

multiply(b1, b2) {
if (0x00 == b1 || 0x00 == b2) { return 0x00; }

logAns = logXPlusOne_Of[b1] + logXPlusOne_Of[b2];
if (logAns >= 255) { logAns -= 255; }
return xPlusOne_ToThe[logAns];
}

• #### Generating the Rijndael S-box

I talked about Rijndael in a couple of previous posts: Efficient multiplication and division in GF(28), Sieving irreducible monic polynomials over a finite field, Addition and multiplication table for GF(22).

I'm going to talk some more about it today.

One of the more interesting steps used in the Rijndael transformation is the non-linear S-box. This is a function S(a) that takes an element of GF(28) (which could be represented as a byte) and returns another one. It is invertible but non-linear.

The spec defines S(a) in terms of two other invertible functions g(a) and f(a). In particular S(a) = f(g(a)). It follows that S-1(a) = g-1(f-1(a)).

g(a) is the non-linear piece, and is quite simple:
g(00) is defined as 00.
g(a) = a-1 for all other a in GF(28). In particular, if a = 03b, then g(a) = 03255 - b.
This is clearly invertible; in fact, it is its own inverse.

Daemen and Rijmen seem to have been almost embarrassed by the simplicity of g so they introduced f. To quote from section 3.4.1:

By definition, g has a very simple algebraic expression. This could allow algebraic manipulations that can be used to mount attacks such as interpolation attacks. Therefore, we built the S-box as the sequence of g and an invertible affine transformation f.

I don't know if I buy the "simplicity" argument. It seems to me that if Rijndael, without f, is robust, then it's robust. And if you add f to a non-robust scheme, I don't understand how that makes it robust; I do see that it complicates analysis, but that seems like a drawback rather than an advantage.

But I'll play along for now. What is f?

b = f(a) is defined using the following matrix multiplication over GF(2) (each entry can be represented as a bit; a row or column as a byte.) Multiplication can be implemented as bitwise AND, and addition by bitwise XOR.

In particular, note that f(00) = 63. So S(00) = f(g(00)) = f(00) = 63. So S-1(63) = 00.

The reference implementation in the book uses hardcoded 256-byte lookup tables for S(a) and S-1(a). I wrote a Perl script which generates these lookup tables and prints them out. This script is attached.

Here's its output, which matches the listing in the book:

>perl -w s-box.pl
S(xy)
| x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xa xb xc xd xe xf
---+------------------------------------------------
0y | 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
1y | ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
2y | b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
3y | 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
4y | 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
5y | 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
6y | d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
7y | 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
8y | cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
9y | 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
ay | e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
by | e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
cy | ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
dy | 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
ey | e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
fy | 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

S^(-1)(xy)
| x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xa xb xc xd xe xf
---+------------------------------------------------
0y | 52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
1y | 7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
2y | 54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e
3y | 08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
4y | 72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
5y | 6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
6y | 90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06
7y | d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b
8y | 3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
9y | 96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
ay | 47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b
by | fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
cy | 1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f
dy | 60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef
ey | a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
fy | 17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d

And here's the interesting part, the implementation of g(a) and f(a):

sub g(\$) {
my (\$a) = shift;

# g(0) we define to be 0
return 0 unless \$a;

# otherwise g(a) = a^(-1)
# a = (x + 1)^loga
# so a^(-1) = (x + 1)^(-loga) = (x + 1)^(255 - loga)
my \$loga = \$log_xplusone_of[\$a];
my \$logb = 255 - \$loga;
\$logb -= 255 if \$logb >= 255;

return \$xplusone_to[\$logb];
}

# f(a) = b is defined as follows:
#
# [ b7 ]   ( [ 1 1 1 1 1 0 0 0 ] [ a7 ] )   [ 0 ]
# [ b6 ]   ( [ 0 1 1 1 1 1 0 0 ] [ a6 ] )   [ 1 ]
# [ b5 ]   ( [ 0 0 1 1 1 1 1 0 ] [ a5 ] )   [ 1 ]
# [ b4 ] = ( [ 0 0 0 1 1 1 1 1 ] [ a4 ] ) + [ 0 ]
# [ b3 ]   ( [ 1 0 0 0 1 1 1 1 ] [ a3 ] )   [ 0 ]
# [ b2 ]   ( [ 1 1 0 0 0 1 1 1 ] [ a2 ] )   [ 0 ]
# [ b1 ]   ( [ 1 1 1 0 0 0 1 1 ] [ a1 ] )   [ 1 ]
# [ b0 ]   ( [ 1 1 1 1 0 0 0 1 ] [ a0 ] )   [ 1 ]
#
# where the + is XOR
sub f(\$) {
my (\$a) = @_;

my \$b = 0x63; # 0b01100011;

# do the matrix multiplication
# one matrix column at a time
for (
my (\$c, \$i) = (0x8f, 0x80); # 0b10001111, 0b10000000
\$i;
\$c = rotate_byte_right(\$c), \$i >>= 1
) {
# i is used to select a bit out of the a column
# c is the matrix column which is multiplied by that bit
# the resulting product influences the eventual b column

# printf("%02x %02x\n", \$c, \$i);

# if this bit in the a column is 0, all of the products are 0, so don't bother
next unless \$a & \$i;

# this bit in the a column is 1
# so XOR b with the matrix column
\$b ^= \$c;
}

return \$b;
}
• #### Expressing a function f: GF(2⁸) → GF(2⁸) as a polynomial using a Lagrange polynomial

I talked about Rijndael in a couple of previous posts: Generating the Rijndael S-box, Efficient multiplication and division in GF(28), Sieving irreducible monic polynomials over a finite field, Addition and multiplication table for GF(22).

I'm going to talk some more about it today.

The Rijndael non-linear S-box S(x) is a composition of two invertible functions f(g(x)). Last time we showed how to generate these, and their inverses, as 256-entry tables.

As Daemen and Rijmen point out, any function from a finite field to itself can be expressed as a polynomial. In fact, given a tabular form of the function, it is possible to generate the Lagrange polynomial and then simplify.

They also give the polynomial for S(x):

SRD[x] = 05·x255 + 09·x253 + F9·x251 + 25·x247 + F4·x239 + 01·x223 + B5·x191 + 8F·x127 + 63

Well, let's check this.
And while we're at it, let's find the polynomials for g(x), f(x) and even S-1(x) too.
First of all, let's start with the Lagrange polynomial.

Given a table of entries { (00, y00), (01, y01), ..., (ff, yff) }, there is a polynomial L(x) which gives the same output, namely:

L(x) = Σi ∈ { 00, 01, ..., ff } yi pi(x)
where pi(x) = Πj ∈ { 00, 01, ..., ff }, ji (x - j) / (i - j)

Can we simplify this?
Yes. Note that (i - j)-1 term varies over all the non-zero elements of the finite field. Since this is a field, every non-zero element has an inverse, which might or might not be itself.
If the inverse is not itself, we can pair the two inverse elements together, and we get 01, which is the multiplicative identity, so we can ignore it.
What are we left with? The product of those non-zero elements which are their own inverses.
In the case of GF(28), there is only one such element, namely 01.
Great! We can ignore the (i - j)-1 terms altogether:

L(x) = Σi ∈ { 00, 01, ..., ff } yi Πj ∈ { 00, 01, ..., ff }, ji (x - j)

What is this? A sum of 256 different polynomials.
Each of these summands is a product of 255 polynomials of degree 1, and so is a polynomial of degree 255.
But in GF(28), x255 = 01 for all x. So each of the summands is actually a polynomial of degree 254, or less.
So the sum is also a polynomial of degree 254, or less; terms with an exponent >= 255 go away and just contribute to lower-order terms.

Great. We have { (00, y00), (01, y01), ..., (ff, yff) } for f, g, S, and S-1. Let's plug them in and see what happens!

I wrote a Perl script to do this; the script is attached. Here's the output. (It's quite slow; it takes about two and a half minutes to run.)

g(x) = 01 x^254

f(x) =
63 + 05 x + 09 x^2 + f9 x^4 + 25 x^8 + f4 x^16 + 01 x^32 + b5 x^64 +
8f x^128

S(x) =
63 + 8f x^127 + b5 x^191 + 01 x^223 + f4 x^239 + 25 x^247 + f9 x^251 + 09 x^253 +
05 x^254

S^(-1)(x) =
52 + f3 x + 7e x^2 + 1e x^3 + 90 x^4 + bb x^5 + 2c x^6 + 8a x^7 +
1c x^8 + 85 x^9 + 6d x^10 + c0 x^11 + b2 x^12 + 1b x^13 + 40 x^14 + 23 x^15 +
f6 x^16 + 73 x^17 + 29 x^18 + d9 x^19 + 39 x^20 + 21 x^21 + cf x^22 + 3d x^23 +
9a x^24 + 8a x^25 + 2f x^26 + cf x^27 + 7b x^28 + 04 x^29 + e8 x^30 + c8 x^31 +
85 x^32 + 7b x^33 + 7c x^34 + af x^35 + 86 x^36 + 2f x^37 + 13 x^38 + 65 x^39 +
75 x^40 + d3 x^41 + 6d x^42 + d4 x^43 + 89 x^44 + 8e x^45 + 65 x^46 + 05 x^47 +
ea x^48 + 77 x^49 + 50 x^50 + a3 x^51 + c5 x^52 + 01 x^53 + 0b x^54 + 46 x^55 +
bf x^56 + a7 x^57 + 0c x^58 + c7 x^59 + 8e x^60 + f2 x^61 + b1 x^62 + cb x^63 +
e5 x^64 + e2 x^65 + 10 x^66 + d1 x^67 + 05 x^68 + b0 x^69 + f5 x^70 + 86 x^71 +
e4 x^72 + 03 x^73 + 71 x^74 + a6 x^75 + 56 x^76 + 03 x^77 + 9e x^78 + 3e x^79 +
19 x^80 + 18 x^81 + 52 x^82 + 16 x^83 + b9 x^84 + d3 x^85 + 38 x^86 + d9 x^87 +
04 x^88 + e3 x^89 + 72 x^90 + 6b x^91 + ba x^92 + e8 x^93 + bf x^94 + 9d x^95 +
1d x^96 + 5a x^97 + 55 x^98 + ff x^99 + 71 x^100 + e1 x^101 + a8 x^102 + 8e x^103 +
fe x^104 + a2 x^105 + a7 x^106 + 1f x^107 + df x^108 + b0 x^109 + 03 x^110 + cb x^111 +
08 x^112 + 53 x^113 + 6f x^114 + b0 x^115 + 7f x^116 + 87 x^117 + 8b x^118 + 02 x^119 +
b1 x^120 + 92 x^121 + 81 x^122 + 27 x^123 + 40 x^124 + 2e x^125 + 1a x^126 + ee x^127 +
10 x^128 + ca x^129 + 82 x^130 + 4f x^131 + 09 x^132 + aa x^133 + c7 x^134 + 55 x^135 +
24 x^136 + 6c x^137 + e2 x^138 + 58 x^139 + bc x^140 + e0 x^141 + 26 x^142 + 37 x^143 +
ed x^144 + 8d x^145 + 2a x^146 + d5 x^147 + ed x^148 + 45 x^149 + c3 x^150 + ec x^151 +
1c x^152 + 3e x^153 + 2a x^154 + b3 x^155 + 9e x^156 + b7 x^157 + 38 x^158 + 82 x^159 +
23 x^160 + 2d x^161 + 87 x^162 + ea x^163 + da x^164 + 45 x^165 + 24 x^166 + 03 x^167 +
e7 x^168 + 19 x^169 + e3 x^170 + d3 x^171 + 4e x^172 + dd x^173 + 11 x^174 + 4e x^175 +
81 x^176 + 91 x^177 + 91 x^178 + 59 x^179 + a3 x^180 + 80 x^181 + 92 x^182 + 7e x^183 +
db x^184 + c4 x^185 + 20 x^186 + ec x^187 + db x^188 + 55 x^189 + 7f x^190 + a8 x^191 +
c1 x^192 + 64 x^193 + ab x^194 + 1b x^195 + fd x^196 + 60 x^197 + 05 x^198 + 13 x^199 +
2c x^200 + a9 x^201 + 76 x^202 + a5 x^203 + 1d x^204 + 32 x^205 + 8e x^206 + 1e x^207 +
c0 x^208 + 65 x^209 + cb x^210 + 8b x^211 + 93 x^212 + e4 x^213 + ae x^214 + be x^215 +
5f x^216 + 2c x^217 + 3b x^218 + d2 x^219 + 0f x^220 + 9f x^221 + 42 x^222 + cc x^223 +
6c x^224 + 80 x^225 + 68 x^226 + 43 x^227 + 09 x^228 + 23 x^229 + c5 x^230 + 6d x^231 +
1d x^232 + 18 x^233 + bd x^234 + 5e x^235 + 1b x^236 + b4 x^237 + 85 x^238 + 49 x^239 +
bc x^240 + 0d x^241 + 1f x^242 + a6 x^243 + 6b x^244 + d8 x^245 + 22 x^246 + 01 x^247 +
7a x^248 + c0 x^249 + 55 x^250 + 16 x^251 + b3 x^252 + cf x^253 + 05 x^254

Daemen and Rijmen's polynomial rendition of S(x) is confirmed.

Also note how simple g(x) is, and how complex S-1(x) is.

Finally, I must confess that none of this is actually useful. The tabular form is much more convenient for applications. This is just a fun theoretical exercise.

(Well, I had fun.)