• The Old New Thing

    Raymond's house rules for Easter Egg Hunts

    • 16 Comments

    One of my colleagues frustrates his family by hiding the eggs for the annual Egg Hunt way too well. "Apparently, drawers and freezers are out of bounds in the traditional egg hunt."

    Here are my house rules for Easter Egg Hunts:

    • All eggs must be hidden within the implied egg-hiding area. No sneaky outliers.
    • All eggs must be at least partially observable by egg-hunters without disturbing anything. No hiding in drawers or under flowerpots, or putting them on top of a tall piece of furniture that a shorter egg-hunter cannot see.
    • However, you may still have to work to see them. They might be behind a sofa or placed above eye level. For example, you might find an egg tucked between the slats of horizontal blinds.

    Personally, I like to hide eggs in plain sight. It's surprising how long it can take somebody to find a yellow egg resting brazenly on the lap of a yellow teddy bear.

  • The Old New Thing

    How do I set a breakpoint on a function whose name contains spaces or other special characters?

    • 2 Comments

    If you use one of the command line debuggers based on the Debugger Engine, you can set a breakpoint on a function whose name contains spaces or other special characters by quoting the symbol name. The trick here is that you do not quote the entire string; you quote only the symbol name.

    0:001> bu @!"CSimpleArray<wchar_t *>::CSimpleArray<wchar_t *>"
    

    Note that the quotation marks do not go around the @! part. They go only around the symbol. (Otherwise, the debugger thinks you are setting a breakpoint action.)

    Another trick for setting breakpoints is using tab autocompletion for symbols. If you type bp contoso!*Widget* and then hit Tab repeatedly, you will cycle through all the matches. (It takes a few seconds to build the list of matches, so be patient the first time you hit Tab.)

    Personally, I use the x command to print out all the matches, and then cherry-pick the one I want.

    0:001> x contoso!*Widget*
    00af114c contoso!CreateWidget
    009fe863 contoso!DestroyWidget
    00a2e161 contoso!MakeWidgetReadOnly
    00a93168 ...
    
    0:001> bp 00a2e161     set breakpoint on MakeWidgetReadOnly
    
  • The Old New Thing

    How can I get the Windows 8 touch keyboard to display autocomplete suggestions like the Bing app?

    • 24 Comments

    A customer observed that if you use the Windows 8 Bing app with the touch keyboard, the top of the touch keyboard includes autocomplete suggestions for quick access. They wanted to know how to enable this in their own application. In the illustration below, it's the two boxes immediately above the keyboard with the words "aol" and "amazon".

    |
    a|
    SUGGESTIONS
    aol
    amazon
    att.net
    autotrader
    ask.com
    american airlines
    aol   amazon
    q
    w
    e
    r
    t
    y
    u
    i
    o
    p
    a
    s
    d
    f
    g
    h
    j
    k
    l
    '
    Search
    z
    x
    c
    v
    b
    n
    m
    ,
    .
    ?
    &123
    Ctrl
     
    <
    >

    The answer is that it's all done with mirrors.

    The thing with the completion suggestions is not actually a part of the keyboard. The Bing app is simply drawing a black box with buttons at the very bottom edge of their window, so that it exactly abuts the touch keyboard. Touch events on those buttons go straight to the Bing app, and Bing programmatically inserts the appropriate word into the text box.

    In other words: It's a fake!

  • The Old New Thing

    There is no complete list of all notifications balloon tips in Windows

    • 33 Comments

    A customer wanted a complete list of all notifications balloon tips in Windows.

    There is no such list. Each component is responsible for its own balloon tips and is not required to submit their list of balloon tips to any central authority for cataloging. In order to create such a list, somebody would have to go contact every component team and ask them for a list of all their balloon tips, and that component team would probably undertake a search of their code base looking for balloon tips. And figuring out the text of each balloon tip can be tricky since the text may be built dynamically. (And the customer didn't ask for an explanation of the conditions under which each balloon tip may appear, but that's probably going to be their follow-up question.)

    It's like publishing instructions on how to display a message on the message board, and then somebody asking the message board manufacturer, "Please send me a list of all messages that might appear on the message board." The message board manufacturer doesn't know how its customers are using the message board. They would have to go survey their customers and ask each one to build an inventory of every message that could potentially be shown.

    In other words, this customer was asking for a research project to be spun up to answer their question.

    I suspected that this was a case of the for-if antipattern being applied to custom support questions, and I asked what the customer intended to do with this information.

    It turns out that they didn't even want this list of balloon tips. They just had a couple of balloon tips they were interested in, and they wanted to know if there were settings to disable them.

    But even though that was their stated goal, they still reiterated their request for a list of balloon tips. The customer liaison asked, "Is there a possibility is getting a list of balloon tips generated by Windows itself? Even a partial list would be helpful. Can we help with this?"

    What the customer liaison can do is contact each Windows component team and ask them, "Can you give me a list of the balloon tips your component generates? Even a partial list would be helpful." I wished him luck.

    The customer liaison replied, "I passed this information to the customer and will follow up if they have any further questions." No follow-up ever appeared.

  • The Old New Thing

    The gradual erosion of the car trip experience, part 2

    • 25 Comments

    When I learned that my nieces were heading out on a road trip, I asked, "Are you going to sing songs?"

    My eldest niece looked at me as if I were from Mars, then replied, "No, we bring electronics."

  • The Old New Thing

    Microspeak: bar check

    • 15 Comments

    A bar check sounds like the sort of thing you receive at the end of a long evening of drinking, but that's not what a bar check is.

    Among the things that happen at ship room meetings is reviewing each bug that has a proposed fix and deciding whether to accept or reject the fix.

    Another thing that happens at ship room meetings is the bar check: The person representing the bug describes the issue and what is known about it so far and asks for a preliminary assessment from the ship room as to whether this is the sort of bug they would approve if a fix were available, in other words, whether it meets the bug bar. If the answer is No, then there is no need to go to the effort of developing a fix for it right now, since you know it would get rejected anyway.

  • The Old New Thing

    The geeky thrill of discovering that two things are really the same thing, just with different labels

    • 15 Comments

    Today's post about binomial coefficients was intended to be a warm-up for Catalan numbers, but it turns out Eric Lippert already covered them, first in the context of binary trees, then in the context of arbitrary trees and forests, and then again in the context of matched parentheses. Another way of seeing the correspondence between forests and matched parentheses is simply to consider each { as an XML open-tag and each } as an XML end-tag.

    One thing to take away from the enumeration of objects controlled by Catalan numbers is that when you see multiplication in a recurrence relation, that typically corresponds to a nested loop. (We saw this ourselves when we studied Stirling numbers of the second kind.)

    The correspondence between binary trees and arbitrary forests is done by simply renaming variables: left­Child and right­Child turn into first­Child and next­Sibling.

    Renaming variables also reveals an interesting equivalence between the two algorithms for reversing a linked list. One technique is to do link rewriting:

    Node *Reverse(Node *head)
    {
     Node *prev = nullptr;
     while (head) {
      // The node we are rewriting
      Node *current = head;
    
      // Advance to next node before
      // we overwrite the outbound pointer
      head = current->next;
    
      // Repoint to previous node
      current->next = prev;
    
      // Advance the trailing pointer
      prev = current;
     }
     return prev;
    }
    

    Another technique is to pop nodes off one list while pushing them onto another.

    Node *Reverse(Node *head)
    {
     Node *result = nullptr;
     while (head) {
      // Pop
      Node *current = head;
      head = current->next;
    
      // Push
      current->next = result;
      result = current;
     }
     return result;
    }
    

    But if you look more closely at the two versions, you'll see that they are not really two algorithms. They are the same algorithm, just with different comments and variable names!

    One of my colleauges used this as an interview question and guided candidates through both algorithms, only to discover later that they were actually the same algorithm, merely viewed through different-colored glasses.

  • The Old New Thing

    Enumerating subsets with binomial coefficients

    • 1 Comments

    Inspired by the Little Program which enumerates set partitions, I decided to do the binomial coefficients this week. In other words, today's Little Program generates all subsets of size k from a set of size n.

    As before, the key is to interpret a recurrence combinatorially. In general, when a recurrence is of the form A + B, it means that at the recursive step, you should do A, followed by B. In our case, the recurrence is C(n, k) = C(n − 1, k) + C(n − 1, k − 1). The combinatorial interpretation of the recurrence is to look at how you can go from a set of size n to a set of size n − 1 by studying the effect of removing element n. If element n is not part of the subset, then what's left is a subset of size k. If it is part of the subset, then removing it leaves a subset of size k − 1.

    Therefore, our algorithm goes like this:

    • Handle base cases.
    • Otherwise,
      • Recursively call C(n − 1, k) and pass the results through.
      • Recursively call C(n − 1, k − 1) and add element n to each of the results.

    As usual, once we spelled out what we're going to do, actually doing it is pretty straightforward.

    function Subsets(n, k, f) {
     if (k == 0) { f([]); return; }
     if (n == 0) { return; }
     Subsets(n-1, k, f);
     Subsets(n-1, k-1, function(s) {
       f(s.concat(n));
     });
    };
    

    The first test catches the vacuous base case where you say, "Please show me all the zero-sized subsets of a set of size n." The answer is "There is exactly one zero-sized subset, called the empty set."

    The second test catches the other base cases where you say, "Please show me all the k-sized subsets¹ of the empty set." This can't be done if k > 0, because the only subset of the empty set is the empty set itself, and its size is not k.

    The meat of the recurrence is pretty much what we said. First, we generate all the k-sized subsets from a set of size n-1 and pass them through. Then we generate all the k-1-sized subsets from a set of size n-1 and add the element n to them.

    We can test out the function by logging the results to the console.

    Subsets(5, 3, logToConsole);
    

    For style points, we can accumulate the results in helper parameters. This records the pending work in parameters instead of closures, which makes the code easier to port to languages which don't support closures. (And probably helps the efficiency a bit too.)

    function AccumulateSubsets(n, k, f, chosen) {
     if (k == 0) { f(chosen); return; }
     if (n == 0) { return; }
     AccumulateSubsets(n-1, k, f, chosen);
     AccumulateSubsets(n-1, k-1, f, [n].concat(chosen));
    };
    
    function Subsets(n, k, f) {
     AccumulateSubsets(n, k, f, []);
    }
    

    (I prepend n to chosen for extra style points, since it causes the results to be enumerated in a prettier order.)

    As with Stirling numbers, we can use a destructive recursion to reduce memory allocation, if we can count on the callback not modifying the result. I'll leave that as an exercise, because I've got something even better up my sleeve: Getting rid of the recursion entirely!

    Let's consider the case of enumerating all the subsets of size k for a fixed k known at compile-time. Let's say k is 3. You can structure this as a series of nested loops.

    function Subsets3(n, f) {
     for (var i = 1; i <= n - 2; i++) {
      for (var j = i + 1; j <= n - 1; j++) {
       for (var k = j + 1; k <= n; k++) {
        f([i, j, k]);
       }
      }
     }
    }
    

    The outer loop chooses the first element, the middle loop chooses the second element, and the inner loop chooses the last element. This clearly generalizes to bigger subsets; you just need more loop variables.

    With this interpretation, you can see how to get from one subset to the next subset: You increment the last element, and if that's not possible without violating the loop constraint, then you back out one level and try incrementing the next-to-last element (and restarting any inner loops), and so on, backing out until you finally find an index that can be incremented (or give up).

    function NextSubsetSameSize(s, n) {
     var k = s.length;
     // look for an index that can be incremented
     for (i = k - 1; i >= 0; i--) {
      // can this index be incremented?
      if (s[i] < n - k + i + 1) {
       // increment it
       s[i]++;
       // reset all inner loops
       while (++i < k) s[i] = s[i-1] + 1;
       return true;
      }
     }
     return false;
    }
    

    The loop on i looks for the highest index that can be incremented. The loop bounds depend on which index you are studying, since lower indices need to leave enough room for higher indices, but can you figure out the formula by looking at the pattern in Subset3. Once we find an index with room, we increment it and reset all the subsequent indices to their initial values. If we can't find an index to increment, then we report failure.

    // Enumerate all subsets of size 3 from a set of size 5
    var s = [1, 2, 3]; // initial subset
    do {
     console.log(JSON.stringify(s));
    } while (NextSubsetSameSize(s, 5));
    
    Note

    ¹ In math circles, the phrase k-sized subsets is typically abbreviated as k-subsets, but I chose to spell it out here because the shorthand takes some getting used to.

  • The Old New Thing

    Windows is not a Microsoft Visual C/C++ Run-Time delivery channel

    • 113 Comments

    There's a DLL in the system directory called MSVCRT.DLL, and from its name, you might think that it is the Microsoft Visual C/C++ Run-Time library. That is a perfectly reasonable guess.

    But it would also be wrong.

    The Microsoft Visual C/C++ Run-Time libraries go by names like MSVCR71.DLL or MSVCR80.DLL or MSVCR90.DLL or MSVCR100.DLL, and the debugging versions have a D in there, too. And like MFC, these binaries might be on your machine as a side effect of the implementation of a particular Windows component, but they are not contractual. If your program requires the Visual C/C++ Run-Time library, then your program needs to install the appropriate version. (There are redistributable packages you can include with your application.)

    Okay, so what's with the DLL with the misleading name MSVCRT.DLL? The unfortunate name is a consequence of history.

    Back in Windows 95, MSVCRT.DLL was the Microsoft Visual C/C++ Run-Time library, or at least it was the runtime library for Visual C/C++ 4.2. As each new version of Visual C/C++ came out, the Windows team had to go update their copy of MSVCRT.DLL to match. And if the Windows team wanted to fix a bug in MSVCRT.DLL, they had to make sure that the Visual C/C++ team made the corresponding change in their version.

    This high degree of coördination became untenable, especially since it required the Windows team to do things like push a new version of MSVCRT.DLL to all downlevel platforms whenever a new version of Visual C/C++ came out. (Good luck doing this in the days before Windows Update!)

    And sometimes these fixes caused compatibility problems. For example, I remember there was a fix for a Y2K problem which caused one application to crash because the fix altered the stack usage in such a way that exposed an uninitialized variable bug.

    One serious problem with the MVSCRT.DLL "one runtime to rule them all" model is that multiple versions of Visual C++ would all use the same library, and keeping one DLL compatible with all versions of Visual C++ was a maintenance nightmare. For example, if a new C++ language feature required a change to the ostream class, you had to be careful to design your change so that the class was still binary-compatible with the older version of the class. This meant not changing the size of the class (because somebody may have derived from it) and not changing the offsets of any members, and being careful which virtual methods you call. This was in practice not done, and the result was that (for example) Windows 95 and Windows 98 both had DLLs called MSVCRT.DLL that were not compatible with each other.

    And of course there was the problem of some application installer unwittingly overwriting the existing copy of MSVCRT.DLL with an older one, causing the entire operating system to stop working.

    At some point, the decision was made to just give up and declare it an operating system DLL, to be used only by operating system components. All newer versions of Visual C/C++ used specifically-numbered DLLs for their runtime libraries. (Giving different names to each version of the run-time library solves the problem of trying to make one DLL service multiple versions of clients, as well as addressing the accidental downgrade problem.)

    Although MSVCRT.DLL has been an operating system DLL for a long time, and has been documented as off-limits to applications, there are still a lot of people who treat it as a C runtime delivery channel, and those programs create a lot of grief for the product team.

    I remember one change that the runtime library folks made to MSVCRT.DLL that had to be backed out and revisited because they found an application that not only linked to MSVCRT.DLL instead of the runtime library the compiler intended, but also groveled into an internal array and manipulated private members. (I was one of the people who investigated this compatibility issue, but I was not the one who solved it.)

    // Note: The issue has been simplified for expository purposes
    struct SomethingInternal
    {
        int widget;
        short widgetFlags;
        char widgetLevel;
        int needs_more_time;
    };
    
    SomethingInternal InternalArray[80];
    

    The runtime library folks added a new member to the structure:

    struct SomethingInternal
    {
        int widget;
        short widgetFlags;
        char widgetLevel;
        int needs_more_time;
        int needs_more_cowbell;
    };
    

    This change increased the size of the Something­Internal structure, which in turn meant that when the application did

    // Redeclare this internal structure in MSVCRT.DLL
    // so we can poke the needs_more_time member to get more time.
    
    struct SomethingInternal
    {
        int widget;
        short widgetFlags;
        char widgetLevel;
        int needs_more_time;
    };
    
    extern SomethingInternal InternalArray[80];
    
    ...
        InternalArray[i].needs_more_time = 1;
    ...
    

    it ended up poking the wrong byte because the structure size didn't match.

    The runtime library folks had to go back and squeeze the cowbell flag into the structure in a way that didn't alter the size of the Something­Internal structure. I don't remember exactly what the fix was, but one way they could've done it was by squeezing the flag into the one byte of padding between widgetLevel and needs_more_time.

    struct SomethingInternal
    {
        int widget;
        short widgetFlags;
        char widgetLevel;
        char needs_more_cowbell;
        int needs_more_time;
    };
    

    Bonus chatter: The application had an easy time messing with the internal array because the source code to the C runtime library is included with the compiler, So much for "All these compatibility problems would go away if you published the source code." Publishing the source code makes it easier to introduce compatibility problems, because it lays bare all the internal undocumented behaviors. Instead of trying to reverse-engineer the runtime library, you can just sit down and read it, and if you want to do something sneaky, you can just copy the declaration of the internal array and party on the needs_more_time member.

  • The Old New Thing

    Why does PrintWindow hate CS_PARENTDC? redux

    • 9 Comments

    Why does Print­Window hate CS_PARENT­DC? Because everybody hates CS_PARENT­DC!

    Commenter kero claims that it's "easy to fix" the problem with Print­Window and CS_PARENT­DC. You just remove the CS_PARENT­DC style temporarily, then do the normal Print­Window, then restore the CS_PARENT­DC style. The question is then why Print­Window simply doesn't do this.

    The question assumes that the described workaround actually works. It may work in limited situations, but it certainly doesn't work in general.

    Since the CS_PARENT­DC style is a class style, removing the style affects all windows of that class, not merely the window you are trying to print. Suppose there are two windows of the class running on different threads, and you remove the CS_PARENT­DC style in anticipation of doing a Print­Window. While that's going on, the other window gets a WM_PAINT message. Since the CS_PARENT­DC style was temporarily removed, that window will be painting with an incorrectly-clipped DC. Result: Incorrect pixels on the screen.

    The proposed workaround doesn't actually work reliably, which means that it probably shouldn't be done at all. (Random reinforcement breeds superstition.)

Page 1 of 419 (4,184 items) 12345»