Matthew van Eerde's web log

  • 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
    1. c4 e6
    2. c5
    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
    1. e3
    2. Qxh5
    3. Qxd5
    4. Qxb7
    5. Qxc7
    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
    1. d4
    2. Bxh6
    3. Qd3
    4. Qxa6
    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.)

  • Matthew van Eerde's web log

    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.

  • Matthew van Eerde's web log

    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

  • Matthew van Eerde's web log

    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

  • Matthew van Eerde's web log

    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
  • Matthew van Eerde's web log

    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.

  • Matthew van Eerde's web log

    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:

    Render devices: 4
        Speakers (High Definition Audio Device)
        Id: {}.{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: {}.{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: {}.{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: {}.{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: {}.{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: {}.{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: {}.{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.

  • Matthew van Eerde's web log

    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 2 8
    Finding monic irreducible polynomials of degree up to 8 and coefficients mod 2
    Generating all monic polynomials...
    Sieving out all reducible polynomials...
    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

    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.

    As a check, there is an elegant formula for the number of irreducible monic polynomials with coefficients in a finite field:

    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.

  • Matthew van Eerde's web log

    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


    ' hardcoding "Admin" username
    Dim admin: Set admin = GetObject("WinNT://localhost/Admin,user")

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

    If Not admin.userFlags And ADS_UF_DONT_EXPIRE_PASSWD Then
        WScript.Echo "Setting local admin account to never expire password"
        admin.userFlags = (admin.userFlags Or ADS_UF_DONT_EXPIRE_PASSWD)

        ' Save
    End If

  • Matthew van Eerde's web log

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


    I updated my toy app to set/read shell properties from the command line. New features:

    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.


    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.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.FileAttributes: A
    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.MCDI: E+96+54E9+98AD+A23C+DBD5+F62C+11889+15B50+170F9+1C1EC+1E01E+221A7+2916C+2C6EB+2F21A
    System.Media.MetadataContentProvider: AMG
    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.NotUserContent: No
    System.OfflineAvailability: Available offline
    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.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.

  • Matthew van Eerde's web log

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

  • Matthew van Eerde's web log

    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.


    pDesktopWallpaper->SetWallpaper(NULL, full-path-to-image-file)


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

    Source and binaries attached

  • Matthew van Eerde's web log

    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.


    pShellLibrary = SHLoadLibraryFromKnownFolder(library GUID)
    SHAddFolderPathToLibrary(pShellLibrary, path)


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

    Source and binaries attached.

  • Matthew van Eerde's web log

    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
    Wesley (male)

    And here's the source:

    use strict;

    # prints a randomly chosen name

    sub read_words();

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

    sub read_words() {
        my @words = <DATA>;

        chomp @words;

        return @words;
    Aaliyah (female)
    Aaron (male)
    Abby (female)
    Abigail (female)
    Abraham (male)
    Adam (male)
    Addison (female)
    Adrian (male)
    Adriana (female)
    Adrianna (female)
    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)
    Braden (male)
    Bradley (male)
    Brady (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)
    Caden (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)
    Jada (female)
    Jade (female)
    Jaden (male)
    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)
    Kaden (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)
    Madeline (female)
    Madelyn (female)
    Madison (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)
    Sadie (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)

  • Matthew van Eerde's web log

    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.


    for each object category in
        (audio outputs; audio inputs; voices; recognizers; etc.)

        for each token

            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.


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


    -- SPCAT_VOICES --
      #1: Microsoft Zira Desktop - English (United States)
          Version = 10.4
          Language = 409
          Gender = Female
          Age = Adult
          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}



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

      None found.


  • Matthew van Eerde's web log

    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


    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 {
        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; }
        Chunk *m_p;


    LPWSTR ReadFromStdIn() {
        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
                head = buffer;
                tail = 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;
        return text;

  • Matthew van Eerde's web log

    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.


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

  • Matthew van Eerde's web log

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


    A while back I blogged about using IAudioSessionControl and IAudioSessionControl2 to get a list of active sessions, and then using IAudioMeterInformation to see what the amplitude level of the audio being played from each session was.

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

    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)

        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)

        AudioMeterInformation = AudioSessionControl::QueryInterface(...)

        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.

    -- Active session #1 --
        Icon path:
        Display name:
        Grouping parameter: {a204c0ad-03c4-4754-8e8f-92843aacb1fa}
        Process ID: 11812 (single-process)
        Session identifier: {}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|\Device\HarddiskVolume1\Windows\System32\WWAHost.exe%b{00000000-0000-0000-0000-000000000000}
        Session instance identifier: {}.{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: {}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|\Device\HarddiskVolume1\Program Files (x86)\Internet Explorer\iexplore.exe%b{00000000-0000-0000-0000-000000000000}
        Session instance identifier: {}.{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 identifier: {}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|#%b{48FF2ED2-2CE8-40FB-AEF7-31FEFDBA7EF2}
        Session instance identifier: {}.{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 identifier: {}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|#%b{A9EF3FD9-4240-455E-A4D5-F2B3301887B2}
        Session instance identifier: {}.{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: {}.{125eeed2-3cd2-48cf-aac9-8ae0157564ad}|\Device\HarddiskVolume1\Program Files (x86)\VideoLAN\VLC\vlc.exe%b{00000000-0000-0000-0000-000000000000}
        Session instance identifier: {}.{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.


  • Matthew van Eerde's web log

    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: {}.{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.


    ... get a process ID...



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

  • Matthew van Eerde's web log

    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.

  • Matthew van Eerde's web log

    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
      • WiredHeadset
      • WiredHeadsetSpeakerOnly
      • 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.)
          var audioRoutingManager = Windows.Phone.Media.Devices.AudioRoutingManager.GetDefault();

      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
    Depending on what is plugged in, and the capabilities of the device
    WiredHeadset or
    WiredHeadsetSpeakerOnly or
    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:
    Bluetooth or
    Depending on the capabilities of the device
    WiredHeadset or
    WiredHeadsetSpeakerOnly or
    Depending on what is plugged in
    No Bluetooth audio routing policy is:
    You can manually invoke this policy with:
      SetAudioEndpoint(Earpiece) or
    WiredHeadset or
    WiredHeadsetSpeakerOnly or
    Depending on what is plugged in
    Speakerphone audio routing policy is:
    You can manually invoke this policy with:
    Invalid audio routing policies:
    The following calls are all errors:
    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.

  • Matthew van Eerde's web log

    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
    0x03118 = 0xad
    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];

  • Matthew van Eerde's web log

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

       | 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) = @_;

        # start with the addition
        my $b = 0x63; # 0b01100011;

        # do the matrix multiplication
        # one matrix column at a time
        for (
            my ($c, $i) = (0x8f, 0x80); # 0b10001111, 0b10000000
            $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;
  • Matthew van Eerde's web log

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

  • Matthew van Eerde's web log

    Arbitrary HTML and JavaScript injection

    1. Inject arbitrary HTML into this page:
      Any HTML you want

    2. Run arbitrary JavaScript on this page:

Page 4 of 6 (144 items) «23456