• The Old New Thing

    Long Zheng interviews Hamad Darwish about those Windows Vista wallpapers

    • 2 Comments

    Long Zheng followed up on the story of where the default wallpapers in Windows Vista came from and managed to score an interview with Hamad Darwish, one of those amateur photographers.

  • The Old New Thing

    Enumerating bit strings with a specific number of bits set (binomial coefficients strike again)

    • 9 Comments

    Today's Little Program prints all bit strings of length n subject to the requirement that the string have exactly k 1-bits. For example, all bit strings of length 4 with 2 bits set are 0011, 0101, 0110, 1001, 1010, and 1100. Let's write BitString(n, k) to mean all the bit strings of length n with exactly k bits set.

    Let's look at the last bit of a typical member of BitString(n, k). If it is a zero, then removing it leaves a string one bit shorter but with the same number of bits set. Conversely every BitString(n − 1, k) string can be extended to a BitString(n, k) string by adding a zero to the end.

    If the last bit is a one, then removing it leaves a bit string of length n − 1 with exactly k − 1 bits set, and conversely every bit string of length n − 1 with exactly k − 1 bits set can be extended to a bit string of length n with exactly k bits set by adding a one to the end.

    Therefore, our algorithm goes like this:

    • Handle base cases.
    • Otherwise,
      • Recursively call BitString(n − 1, k) and add a 0 to the end.
      • Recursively call BitString(n − 1, k − 1) and add a 1 to the end.

    This algorithm may look awfully familiar. The overall recursive structure is the same as enumerating subsets with binomial coefficients; we just decorate the results differently.

    That's because this problem is the same as the problem of enumerating subsets. You can think of the set bits as selecting which elements get put into the subset.

    It's not surprising, therefore, that the resulting code is identical except for how we report the results. (Instead of generating arrays, we generate strings.)

    function repeatString(s, n) {
     return new Array(n+1).join(s);
    }
    
    function BitString(n, k, f) {
     if (k == 0) { f(repeatString("0", n)); return; }
     if (n == 0) { return; }
     BitString(n-1, k, function(s) { f(s + "0"); });
     BitString(n-1, k-1, function(s) { f(s + "1"); });
    }
    

    If k is zero, then that means we are looking for strings of length n that contain no bits set at all. There is exactly one of those, namely the string consisting of n zeroes.

    If k is nonzero but n is zero, then that means we want strings of length zero with some bits set. That's not possible, so we return without generating anything.

    Finally, we handle the recursive case by generating the shorter strings and tacking on the appropriate digits.

    Since this is the same algorithm as subset generation, we should be able to write one in terms of the other:

    function BitString(n, k, f) {
     Subsets(n, k, function(s) {
      var str = "";
      for (var i = 1; i <= n; i++) {
       str += s.indexOf(i) >= 0 ? "1" : "0";
      }
      f(str);
     });
    }
    
  • The Old New Thing

    Why was the replacement installer for recognized 16-bit installers itself a 32-bit program instead of a 64-bit program?

    • 34 Comments

    Even though 64-bit Windows does not support 16-bit applications, there is a special case for 16-bit installers for 32-bit applications. Windows detects this scenario and substitutes a 32-bit replacement installer which replicates the actions of the 16-bit installer. Commenter Karellen is horrified at the fact that the replacement installer is a 32-bit program. "You're writing a program that will run exclusively on 64-bit systems. Why not built it to run natively on the OS it's designed for? Why is this apparently not the "obvious" Right Thing(tm) to do? What am I missing?"

    Recall that a science project is a programming project that is technically impressive but ultimately impractical. For example it might be a project that nobody would actually use, or it attempts to add a Gee-Whiz feature that nobody is really clamoring for.

    But at least a science project is trying to solve a problem. This proposal doesn't even solve any problems! Indeed, this proposal creates problems. One argument in favor of doing it this way is that it is satisfies some obsessive-compulsive requirement that a 64-bit operating system have no 32-bit components beyond the 32-bit emulation environment itself.

    Because! Because you're running a 64-bit system, and running apps native to that system is just more elegant.

    Okay, it's not obsessive-compulsive behavior. It's some sort of aesthetic ideal, postulated for its own sake, devoid of practical considerations.

    Remember the problem space. We have a bunch of 32-bit applications that use a 16-bit installer. Our goal is to get those applications installed on 64-bit Windows. By making the replacement installer a 32-bit program, you get the emulator to do all the dirty work for you. Things like registry redirection, file system redirection, and 32-bit application compatibility.

    Suppose the original installer database says

    • Copy X.DLL file into the %Program­Files%\AppName directory.
    • Copy Y.DLL into the %windir%\System32 directory.
    • If the current version of C:\Program Files\Common Files\Adobe\Acrobat\ActiveX\AcroPDF.dll is 7.5 or higher, then set this registry key.

    If you write the replacement installer as a 32-bit program, then other parts of the 32-bit emulation engine do the work for you.

    • The environment manager knows that 64-bit processes get the environment variable Program­Files pointing to C:\Program Files, whereas 32-bit processes get Program­Files pointing to C:\Program Files (x86).
    • The file system redirector knows that if a 32-bit process asks for %windir%\System32, it should really get %windir%\SysWOW64.
    • The registry redirector knows that if a 32-bit process tries to access certain parts of the registry, they should be sent to the Wow­64­32­Node instead.

    If you had written the replacement installer as a 64-bit program, you would have to replicate all of these rules and make sure your copy of the rules exactly matched the rules used by the real environment manager, file system redirector, and registry redirector.

    Now you have to keep two engines in sync: the 32-bit emulation engine and the 64-bit replacement installer for 32-bit applications. This introduces fragility, because any behavior change in the 32-bit emulation engine must be accompanied by a corresponding change in the 64-bit replacement installer.

    Suppose the application compatibility folks add a rule that says, "If a 32-bit installer tries to read the version string from C:\Program Files\Common Files\Adobe\Acrobat\ActiveX\AcroPDF.dll, return the version string from C:\Program Files (x86)\Common Files\Adobe\Acrobat\ActiveX\AcroPDF.dll instead." And suppose that rule is not copied to the 64-bit replacement installer. Congratulations, your 64-bit replacement installer will incorrectly install any program that changes behavior based on the currently-installed version of AcroPDF.

    I don't know for sure, but I wouldn't be surprised if some of these installers support plug-ins, so that the application developer can run custom code during installation. It is possible for 16-bit applications to load 32-bit DLLs via a technique known as generic thunking, and the 16-bit stub installer would use a generic thunk to call into the 32-bit DLL to do whatever custom action was required. On the other hand, 64-bit applications cannot load 32-bit DLLs, so if the 64-bit replacement installer encountered a 32-bit DLL plug-in, it would have to run a 32-bit helper application to load the plug-in and call into it. So you didn't escape having a 32-bit component after all.

    And the original obsessive-compulsive reason for requiring the replacement installer to be 64-bit was flawed anyway. This is a replacement installer for a 32-bit application. Therefore, the replacement installer is part of the 32-bit emulation environment, so it is allowed to be written as a 32-bit component.

    Let's look at the other arguments given for why the replacement installer for a 32-bit application should be written as a 64-bit application.

    Because complexity is what will be our undoing in the end, and reducing it wherever we can is always a win.

    As we saw above, writing the replacement installer as a 64-bit application introduces complexity. Writing it as a 32-bit application reduces complexity. So this statement itself argues for writing the replacement installer as a 32-bit application.

    Because we can't rewrite everything from scratch at once, but we can create clean new code one small piece at a time, preventing an increase to our technical debt where we have the opportunity to do so at negligible incremental cost to just piling on more cruft.

    As noted above, the incremental cost is hardly negligible. Indeed, writing the replacement installer as a 64-bit application is not merely more complex, it creates an ongoing support obligation, because any time there is a change to the 32-bit emulation environment, that change needs to be replicated in the 64-bit replacement installer. This is a huge source of technical debt: Fragile coupling between two seemingly-unrelated components.

    And writing the replacement installer as a 32-bit application does not create a future obligation to port it to 64 bits when support for 32-bit applications is dropped in some future version of Windows. Because when support for 32-bit applications disappears (as it already has on Server Core), there will be no need to port the replacement installer to 64-bit because there's no point writing an installer for a program that cannot run!

    Writing the replacement installer as a 32-bit program was the right call.

  • The Old New Thing

    Puzzling out the upsell-o-meter

    • 21 Comments

    As I noted before, many grocery stores in the United States have a printer next to the cash register which prints out coupons customized to your purchases. Here's a purchase and the accompanying coupon. What is the story behind this pairing?

    Purchased: Diapers for newborn baby.
    Coupon: Save 75 cents on ice cream.

    Bonus chatter: While waiting in line, I read the warning label on the diapers. It went on for quite a bit, but one part triggered my "I wonder what lawsuit led to this warning" sensor: "Like most articles of clothing, XYZ brand diapers will burn if exposed to flame." Did somebody say, "Oh no, there's a fire, what will I do? I know, I'll smother the fire with my baby's diapered bottom!"

  • The Old New Thing

    Why don't all the Control Panel applications show up when you open a menu from the address bar?

    • 13 Comments

    One of the features added to the Explorer Address Bar in Windows Vista is the ability to navigate quickly to an item by clicking on its name, or navigate to a folder's children by clicking the arrow that appears next to the item and selecting your destination.

    One customer reported that there appeared to be a problem with the Control Panel: Switch to Classic View, and then click the arrow next to the words Control Panel. The result is a dropdown menu that shows some but not all of the Control Panel applications. Is this a bug?

    No, everything is behaving normally. Recall that the dropdown menu shows things that you can navigate to; in other words, it shows you a list of subfolders of the Control Panel. Since you can't navigate to non-folders, they aren't listed as options.

    Notice, for example, that when you go to your Documents folder and click the dropdown arrow, not all of your documents show up in the menu. Only things which Explorer can navigate to appear in the menu (mostly subfolders but occasionally you'll find subfolder-like items such as compressed folders).

    The customer replied with a simple, "Thanks. That makes sense."

    Obligatory link: The so-called God Mode.

  • The Old New Thing

    The conversations backstage at computer Go tournaments

    • 7 Comments

    Steve Rowe linked to an essay on why computers can't play Go well even though they've mastered other "difficult" games like chess. I was reminded of a description I received of what happens backstage at computer Go tournaments (i.e., tournaments that pit Go-playing computers against each other). ("Backstage" is a bit of a misnomer, of course; since the contestants are computers, you can talk all you want as loud as you want without worrying about distracting the players.)

    At computer Go tournaments, the programmers are like parents watching their children compete in a hockey game where they've only just barely learned how to skate. It's not so much a matter of who plays better as it is a matter of who sucks less. One programmer will lean over to the other and say something like "I hope my program realizes its left-hand-side is vulnerable before your program takes advantage of it."

  • The Old New Thing

    The management of memory for resources in 16-bit Windows, redux

    • 10 Comments

    Some time ago, I briefly ran down how 16-bit Windows managed memory for resources. But there's a detail that I neglected to mention: Ownership.

    As we saw, a resource handle HRSRC was really a pointer to the resource directory entry of the resource from the corresponding module. This could be done with a 16-bit pointer because the segment portion of the pointer could be inferred from the module the resource belonged to. In fact, since modules could be relocated in memory at run time due to compaction, you had better not try to remember the segment portion of the pointer since it could change!

    The Find­Resource function located the resource directory entry. The Load­Resource function allocated memory for the resource and loaded it from disk. The Lock­Resource function locked the memory so you could access it. If two people tried to load the same resource, the memory for the resource was re-used so there was only one copy in memory, and if both people free the resource, the resource is cached in case somebody asks for it again soon.

    Now things get interesting: When does the resource get removed from the cache? What actually controls the lifetime of the resource?

    Answer: The resource lifetime is tied to the module it came from. When the module is unloaded, all its resources are unloaded along with it. (Note that even if a resource is cached, its contents can get discarded if it is tagged as DISCARDABLE.)

    In Win32, modules are directly mapped into memory, and along with it, the resources. Therefore, accessing the resources of a module is a simple matter of figuring out where they got mapped (Find­Resource and friends will tell you), and then reading the memory directly. So despite the radical change to resources work, the basic rules haven't changed: The resources are good as long as the module is still in memory.

    But there are resources and then there are resources. So far, we've been talking about resources in the sense of Find­Resource, which I will call module resources for lack of a better term. But people often work with objects like icons and bitmaps which are not literally resources but which are derived from resources. Next time, we'll look at the relationship between module resources and resource-derived objects in 16-bit Windows.

  • The Old New Thing

    Luxurifying the camping experience in a different direction

    • 14 Comments

    Some time ago, I noted the increasing luxurification of camping, where people with more money than sense decide to go through the camping experience without building any of the character that comes with it.

    But that's not the only direction luxurification has moved. Unwilling to accept that "getting there is half the fun", some people take chartered planes to and from summer camp. Stick it out for the punch line in the final sentence of the article.

  • The Old New Thing

    Holy cow, those TechReady attendees really love their tchotchkes

    • 16 Comments

    I was at the Ask the Experts event last night at TechReady11, and if I didn't know better, I would have thought the purpose of Ask the Experts was for attendees to wander the room collecting the coolest swag they could get their hands on as quickly as possible. My table was equipped with about two dozen Windows 7 frisbees, and the moment they came out of the box, they disappeared into the hands of passers-by, most of whom didn't even bother reading the sign on the table much less make eye contact with me.

    The table next to mine started with a mountain of mugs, but it wasn't long before it was reduced to a molehill.

    To try to convince people at least to make eye contact with me, I hid the remaining frisbees under the table, handing them only to people who actually stopped to ask a question, or at least tell an interesting story.

    After the frisbees were gone, the swag fairies dropped a few dozen battery-powered light stick thingies. They didn't disappear as quickly, perhaps because the initial surge of swag-hunters had subsided.

    I was kind of surprised at how aggressively people went after the swag. This is, after all, a Microsoft internal event. You'd think these people would be jaded by now, having been surrounded by Microsoft-branded doodads for years.

  • The Old New Thing

    Hey, you look Chinese, we have a class for people like you

    • 30 Comments

    (The title is a callback to this article from a few months ago.)

    A member of my extended family grew up near the city of Nanaimo, Canada. While it's true that she's ethnically Chinese, it's also true that she's a fourth generation Canadian. The community is overwhelmingly English-speaking, and English is her first language. She grew up going to an English-language school, she watched English-language television, spoke English with her friends and family, and probably dreamed dreams in English.

    Yet when the family moved to Vancouver when she was a child (I don't know the exact age, so let's say eight years old), the school district automatically enrolled her in English as a Second Language, presumably based on her Chinese last name and the fact that Mandarin and Cantonese are the mother tongues in 30% of Vancouver homes.

    Since she was only eight years old, she didn't know that the school had tagged her as a non-native English speaker. She cheerfully went to her special class for an hour each day, enjoying her time with a new teacher and new classmates.

    It wasn't for a long time (I don't know exactly, so let's say six months) that she realized, "Wait a second, this is the class for people who don't speak English well!" Once the mistake was recognized, it wasn't long before she was transferred back to the regular class.

    Though I'm kind of surprised the school district (and the class teacher) never figured out that her English was native, or, failing that, that her English was plenty good enough that she didn't need the class any more.

Page 378 of 450 (4,494 items) «376377378379380»