Matthew van Eerde's web log

  • Matthew van Eerde's web log

    Blown movie lines - Casablanca

    • 2 Comments

    Ah... Casablanca.

     

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

    The line:

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

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

    Well, for two reasons.

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

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

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

      ... and later...

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

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

    2. The song was nearly changed.

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

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

      Shame, Mr. Steiner.  Shame.

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

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



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

  • Matthew van Eerde's web log

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

    • 2 Comments

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

    The purported solution is...

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

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

    Because there's a mate in one.

  • Matthew van Eerde's web log

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

    • 2 Comments

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

     http://blogs.msdn.com/photos/matthew_van_eerde/images/9995171/original.aspx

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

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

     http://blogs.msdn.com/photos/matthew_van_eerde/images/9995183/original.aspx

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

    http://blogs.msdn.com/photos/matthew_van_eerde/images/9995183/original.aspx=http://blogs.msdn.com/photos/matthew_van_eerde/images/9995921/original.aspx+http://blogs.msdn.com/photos/matthew_van_eerde/images/9995922/original.aspx

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

     http://blogs.msdn.com/photos/matthew_van_eerde/images/9995182/original.aspx

  • Matthew van Eerde's web log

    Windows audio render volume settings, from local to global

    • 2 Comments

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

    Stream volume

    The WASAPI API for this is IAudioStreamVolume.

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

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

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

    Session volume

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

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

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

    Endpoint volume

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

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

    Ducking

    More about ducking

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

     

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

  • Matthew van Eerde's web log

    Wheel of Fortune conundrum

    • 1 Comments
    What happens if Pat gets a Bankrupt on the Final Spin?
  • Matthew van Eerde's web log

    Troubleshooting: how to install the Microsoft HD Audio class driver

    • 1 Comments

    Most on-the-motherboard audio devices support the Intel High Definition Audio standard.  Windows Vista (and later) includes a "class driver", hdaudio.sys, which should work with any such audio device.

    Usually systems come with a vendor-supplied driver installed.  This driver is designed specifically for the hardware it runs on (as opposed to being designed to the standard) and so it comes with additional functionality.

    Occasionally, for troubleshooting purposes, it is useful to switch from one driver to the other... either to get the additional functionality provided by the vendor-supplied driver, or to see what happens if the class driver is installed.

    Here's how to switch back and forth.

    Click "Start".

    Type "devmgmt.msc" (without the quotes) to launch Device Manager.

    Expand the "Sound, video and game controllers" node and note the list of audio devices.  In this case, I have one audio device, and by the "High Definition Audio Device" name I deduce that I have the class driver installed.  (If the device name included a company name, I would infer that I had a vendor driver installed.)

    Right-click the device you want to change the software on.

    Windows offers to automatically detect the driver that should be installed.  No thanks, we want to pick a particular driver:

    Windows asks where we want to look - do we have a set of driver files, or is the driver already in the list of installed drivers?  In this case, we want to look at the list of drivers for this hardware that are already installed.

    Windows shows us a list of drivers that are already installed and usable for this hardware.  At this point you would expect to see two drivers listed: the vendor driver, and "High Definition Audio Device."  (When I made this blog post, I was lazy, so I didn't bother to make a screenshot that showed two drivers.)

    To install the class driver, pick "High Definition Audio Device" and click "Next."

    "High Definition Audio Device" is a class driver, so you get this warning.  Click "Yes."

    Windows does its thing...

    ... and eventually tells you that it's done.  If your audio device was in use, you may get the "you have to restart" message.  Regardless, click "Close".

    If you got the "you will need to restart" message, Windows helpfully offers to restart right away.

    Make sure you're ready for a restart (no unsaved documents or anything) and restart either by clicking "Yes" or by using the Start menu.

    When you're done experimenting, you can go back to the vendor-supplied driver by going through the same steps and choosing the vendor-supplied driver in the list of drivers.

  • Matthew van Eerde's web log

    UI text flow of various languages

    • 1 Comments

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

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

    Left-to-right, top-down:

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

    Right-to-left, top-down:

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

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

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

    Top-down, right-to-left:

    To digress a little...

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

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

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

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

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

  • Matthew van Eerde's web log

    Downmixing stereo to mono

    • 1 Comments

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

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

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

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

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

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

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

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

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

  • Matthew van Eerde's web log

    optimal tic-tac-toe (XKCD)

    • 1 Comments

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

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

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

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

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

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

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

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

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

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

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

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

  • Matthew van Eerde's web log

    Perl script to parse MPEG audio header

    • 1 Comments

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

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

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

    Here's the source for the perl script:

    use strict;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    my %copyright = (
        "0" => "audio is not copyrighted",
        "1" => "audio is copyrighted",
    );

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

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

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

    my $header = "";

    my $header_size = 16;
    my $read = read(MPEG, $header, $header_size, 0);

    close(MPEG);

    $header_size == $read or die("Expected $header_size bytes to be read, not $read");

    my @bits = ();

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

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

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

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

  • Matthew van Eerde's web log

    Interview question: baby boys and baby girls

    • 1 Comments

    Source:

    http://www.businessinsider.com/15-google-interview-questions-that-will-make-you-feel-stupid-2009-11#in-a-country-in-which-people-only-want-boys-3

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

    Answer next week.

    EDIT 4/26: Answer.

  • Matthew van Eerde's web log

    Solution: baby boys and baby girls

    • 1 Comments

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    http://blogs.msdn.com/photos/matthew_van_eerde/images/10000339/original.aspx

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

    http://blogs.msdn.com/photos/matthew_van_eerde/images/10000345/original.aspx

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

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

    http://blogs.msdn.com/photos/matthew_van_eerde/images/10000340/original.aspx

    which comes out to... 120 miles!

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

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

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

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

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

    Student: (awed silence)

    Heh.  Gets me every time.

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

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

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

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

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

    -- How many boys are there? --

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

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

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

    http://blogs.msdn.com/photos/matthew_van_eerde/images/10000341/original.aspx

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

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

    -- How many girls are there? --

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

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

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

    ...

    The total number of girls G is thus:

    http://blogs.msdn.com/photos/matthew_van_eerde/images/10000342/original.aspx

    ... um...

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

    Let:

    http://blogs.msdn.com/photos/matthew_van_eerde/images/10000348/original.aspx
    I am assuming both |x| < 1 (for convergence) and x ≠ 0 (for convenience.)

    Differentiate (this is the trick:)

    http://blogs.msdn.com/photos/matthew_van_eerde/images/10000350/original.aspx

    Multiply both sides by x:

    http://blogs.msdn.com/photos/matthew_van_eerde/images/10000349/original.aspx

    Now substitute x = 1/2:

    http://blogs.msdn.com/photos/matthew_van_eerde/images/10000346/original.aspx

    Back to the calculation:

    http://blogs.msdn.com/photos/matthew_van_eerde/images/10000343/original.aspx

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

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

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

    QED

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

  • Matthew van Eerde's web log

    Pirates of Penzance puzzle - what year is it?

    • 1 Comments

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

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

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

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

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


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

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


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

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


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

    KING.

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

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


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

     http://blogs.msdn.com/photos/matthew_van_eerde/images/10004590/original.aspx

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

    MABEL.    Oh, horrible!  Catastrophe appalling!

    This brings us to the point.  Calculate the following:

    1. In what year was Frederic born?
    2. With as much accuracy as possible, specify the date and time of the opening scene.
  • Matthew van Eerde's web log

    Newton: combining celestial and terrestrial mechanics

    • 1 Comments

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    http://blogs.msdn.com/photos/matthew_van_eerde/images/9952568/original.aspx

    Coarse estimate time...

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

    More precisely...

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

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

    Now consider the moon case:

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

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

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

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

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

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

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

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

  • Matthew van Eerde's web log

    Blown movie lines - Torn Curtain

    • 1 Comments

    http://blogs.msdn.com/photos/matthew_van_eerde/images/9992536/original.aspx

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

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

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

    Why is this a blown line?

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

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

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

    How to turn on HDCP or SCMS in an audio playback app

    • 1 Comments

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

    Exercise: find the leak.

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

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

    Source and binaries (x86 and amd64) attached.

    >trustedaudiodrivers2
    trustedaudiodrivers2 --list-devices

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

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

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

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

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

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

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

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

    Common causes of failures:

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

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

    EDIT: 11/13/2009 10:05 AM

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

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

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

    My first instinct was to bypass the assertion like this:

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

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

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

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

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

     

  • Matthew van Eerde's web log

    Forcing Windows to install on a single partition

    • 1 Comments

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

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

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

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

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

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

    1. Boot from the Windows DVD
    2. Choose Custom (advanced) as opposed to Upgrade
    3. Go into Drive options (advanced)
    4. Delete all partitions on the drive
    5. Create a new partition - you will get the prompt above
    6. Click OK
    7. There will now be two partitions - a small (System) one and a large (Primary) one.
    8. Delete the large one.
    9. Extend the new one to fill the drive.
    10. Install Windows.
    11. Open Windows Explorer
    12. Right-click the C: drive | Properties
    13. Delete the "System Reserved" partition name
    Et voilà, Windows installs perfectly happily on the single partition (confirmed with diskpart.exe post-installation.)
  • Matthew van Eerde's web log

    The evolution of HRESULT_FROM_WIN32

    • 1 Comments

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

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

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

    Heresy.

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

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

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

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

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

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

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

    return HRESULT_FROM_WIN32(GetLastError());

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

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

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

    //
    // and the inverse
    //

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

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

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

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

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

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

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

    Much better.

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

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

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

    As of Vista RTM...

    HRESULT_FROM_WIN32 is NO LONGER a macro!

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

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

    Windows 2000 RTM:

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

    Windows XP RTM:

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

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

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

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

    Windows Vista RTM:

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

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

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

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

    People who want the macro can still use __HRESULT_FROM_WIN32.

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

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

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

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

  • Matthew van Eerde's web log

    Generating a sine wave

    • 1 Comments

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

    So the quality of the sine wave generator is important.

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

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

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

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

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

    Then

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

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

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

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

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

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

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

    And we have an implementable function

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

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

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

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

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

    Almost.

    Why almost?

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

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

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

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

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

    Almost.

    Why almost?

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

    Exercise... what is the bug?

  • Matthew van Eerde's web log

    xkcd finds East and West confusing - what about North and South?

    • 1 Comments

    Stealing from XKCD again:

    Terminology

    I have a similar problem with North and South.  On the globe, there's a clearly marked "North Pole" and a clearly marked "South Pole."

    Fine.

    Magnets also have North and South poles.  These are typically labeled N and S respectively.  Fine.

    But if you consider the Earth as a large magnet (which it is), then you have to stick the N where the penguins live (Antarctica-ish) and the S where the polar bears live (Canada-ish...)

     http://blogs.msdn.com/photos/matthew_van_eerde/images/9064687/original.aspx

    That bugs me.

  • Matthew van Eerde's web log

    Bad Perl: Russian Peasant multiplication algorithm

    • 1 Comments

    I found this programming contest interesting: here's what I've got.

    perl -e "($a,$b)=@ARGV;map{$c+=$_*$b}grep{$a&$_}map{1<<$_}(0..log($a)/log 2);print$c" 7 19

    I'm calling this a one-liner because the part between the quotes is less than 80 characters (75, to be exact.)  The full command line goes over :-(

    Requires the inputs to be positive whole numbers.

    Perfect example of Bad Perl.  Exercise: rewrite in Good Perl.

    EDIT: got the whole thing down to 80 characters (with single-digit multiplicands.)

    perl -e "($a,$b)=@ARGV;map{$c+=$b<<$_ if$a>>$_&1}(0..log($a)/log 2);print$c" 8 7

  • Matthew van Eerde's web log

    Bad Perl: Josephus problem

    • 1 Comments

    Another programming contest asks to solve the Josephus problem.

    Bad Perl solution (83 characters... so close...)

    >perl -e"@_=(1..$ARGV[0]);++$c%$ARGV[1]?$i++:splice@_,$i%=@_,1while$#_;print@_" 40 3
    28

    EDIT: got it down to 80.

    >perl -e"@_=(1..shift);++$c%$ARGV[0]?$i++:splice@_,$i%=@_,1while$#_;print@_" 40 3
    28

    EDIT2: 78 dropping the parentheses.

    >perl -e"@_=1..shift;++$c%$ARGV[0]?$i++:splice@_,$i%=@_,1while$#_;print@_" 40 3
    28

    EDIT3: 66, shamelessly cannibalizing others' ideas from the contest (though I refuse to use "say")

    >perl -e"$k=pop;@_=1..pop;@_=grep{++$i%$k}@_ while$#_;print@_" 40 3
    28

  • Matthew van Eerde's web log

    Spock's chess games from Star Trek Ishmael

    • 1 Comments

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

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

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

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

     

    ... and...

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

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

     

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

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

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

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

     

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

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

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

     

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

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

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

     

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

  • Matthew van Eerde's web log

    Daylight Saving Time and Benjamin Franklin

    • 1 Comments

    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!

    • 1 Comments

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

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

Page 3 of 6 (138 items) 12345»