May, 2012

  • The Old New Thing

    GUIDs are designed to be unique, not random

    • 47 Comments

    A customer liaison asked, "My customer is looking for information on the GUID generation algorithm. They need to select N items randomly from a pool of M (jury selection), and their proposed algorithm is to assign each item a GUID, then sort the items by GUID and take the first N." (I've seen similar questions regarding using GUIDs for things like passwords or other situations where the programmer is looking for a way to generate a value that cannot be predicted.)

    The GUID generation algorithm was designed for uniqueness. It was not designed for randomness or for unpredictability. Indeed, if you look at an earlier discussion, you can see that so-called Algorithm 1 is non-random and totally predictable. If you use an Algorithm 1 GUID generator to assign GUIDs to candidates, you'll find that the GUIDs are assigned in numerically ascending order (because the timestamp increases). The customer's proposed algorithm would most likely end up choosing for jury duty the first N people entered into the system after a 32-bit timer rollover. Definitely not random.

    Similarly, the person who wanted to use a GUID for password generation would find that the passwords are totally predictable if you know what time the GUID was generated and which computer generated the GUID (which you can get by looking at the final six bytes from some other password-GUID). Totally-predictable passwords are probably not a good idea.

    Even the Version 4 GUID algorithm (which basically says "set the version to 4 and fill everything else with random or pseudo-random numbers") is not guaranteed to be unpredictable, because the algorithm does not specify the quality of the random number generator. The Wikipedia article for GUID contains primary research which suggests that future and previous GUIDs can be predicted based on knowledge of the random number generator state, since the generator is not cryptographically strong.

    If you want a random number generator, then use a random number generator.

    Bonus reading: Eric Lippert's GUID Guide, part 1, part 2, and part 3.

  • The Old New Thing

    The extern "C" specifier disables C++ mangling, but that doesn't mean it disables mangling

    • 18 Comments

    The MSDN documentation on dllexport contains the following enigmatic paragraph, or at least did at the time I wrote this article:

    dllexport of a C++ function will expose the function with C++ name mangling. If C++ name mangling is not desired, either use a .def file (EXPORTS keyword) or declare the function as extern "C".

    I've seen this sentence misinterpreted as follows:

    dllexport of a C++ function will expose the function with C++ name mangling. To disable name mangling either use a .def file (EXPORTS keyword) or declare the function as extern "C".

    This is an understandable misinterpretation, but it is still a misinterpretation.

    The root cause of the misinterpretation is that the author of this documentation was wearing C++-colored glasses. In the author's mind, there are only two interesting cases:

    1. C++ name mangling, where all the cool people are, and
    2. everything else, for all the lamers.

    Here is a precise formulation of the paragraph:

    dllexport of a C++ function will expose the function with C++ name mangling. If C++ name mangling is not desired, either use a .def file (EXPORTS keyword), which will expose the name without mangling, or declare the function as extern "C", which will expose the name with C mangling.

    Here's a version of the paragraph that tries to take away the C++-colored glasses.

    dllexport exposes the function as it is decorated by the compiler. For example, if the function is a C++ function, it will be exposed with C++ name mangling. If the function is a C function, or has been declared as extern "C", it will be exposed with C name mangling. To expose the function under its unmangled name (or to expose it via an alternate name), use use a .def file (EXPORTS keyword).

    Behind the scenes: To forestall nitpickers, I had to go back to my copy of the C++ standard to make sure I filled in the blank in "The extern "C" _________" correctly. Officially, extern "C" is a storage class specifier.

  • The Old New Thing

    What is the historical reason for MulDiv(1, -0x80000000, -0x80000000) returning 2?

    • 47 Comments

    Commenter rs asks, "Why does Windows (historically) return 2 for MulDiv(1, -0x80000000, -0x80000000) while Wine returns zero?"

    The MulDiv function multiplies the first two parameters and divides by the third. Therefore, the mathematically correct answer for MulDiv(1, -0x80000000, -0x80000000) is 1, because a × b ÷ b = a for all nonzero b.

    So both Windows and Wine get it wrong. I don't know why Wine gets it wrong, but I dug through the archives to figure out what happened to Windows.

    First, some background. What's the point of the MulDiv function anyway?

    Back in the days of 16-bit Windows, floating point was very expensive. Most people did not have math coprocessors, so floating point was performed via software emulation. And the software emulation was slow. First, you issued a floating point operation on the assumption that you had a float point coprocessor. If you didn't, then a coprocessor not available exception was raised. This exception handler had a lot of work to do.

    It decoded the instruction that caused the exception and then emulated the operation. For example, if the bytes at the point of the exception were d9 45 08, the exception handler would have to figure out that the instruction was fld dword ptr ds:[di][8]. It then had to simulate the operation of that instruction. In this case, it would retrieve the caller's di register, add 8 to that value, load four bytes from that address (relative to the caller's ds register), expand them from 32-bit floating point to 80-bit floating point, and push them onto a pretend floating point stack. Then it advanced the instruction pointer three bytes and resumed execution.

    This took an instruction that with a coprocessor would take around 40 cycles (already slow) and ballooned its total execution time to a few hundred, probably thousand cycles. (I didn't bother counting. Those who are offended by this horrific laziness on my part can apply for a refund.)

    It was in this sort of floating point-hostile environment that Windows was originally developed. As a result, Windows has historically avoided using floating point and preferred to use integers. And one of the things you often have to do with integers is scale them by some ratio. For example, a horizontal dialog unit is ¼ of the average character width, and a vertical dialog unit is 1/8 of the average character height. If you have a value of, say, 15 horizontal dlu, the corresponding number of pixels is 15 × average character width ÷ 4. This multiply-then-divide operation is quite common, and that's the model that the MulDiv function is designed to help out with.

    In particular, MulDiv took care of three things that a simple a × b ÷ c didn't. (And remember, we're in 16-bit Windows, so a, b and c are all 16-bit signed values.)

    • The intermediate product a × b was computed as a 32-bit value, thereby avoiding overflow.
    • The result was rounded to the nearest integer instead of truncated toward zero
    • If c = 0 or if the result did not fit in a signed 16-bit integer, it returned INT_MAX or INT_MIN as appropriate.

    The MulDiv function was written in assembly language, as was most of GDI at the time. Oh right, the MulDiv function was exported by GDI in 16-bit Windows. Why? Probably because they were the people who needed the function first, so they ended up writing it.

    Anyway, after I studied the assembly language for the function, I found the bug. A shr instruction was accidentally coded as sar. The problem manifests itself only for the denominator −0x8000, because that's the only one whose absolute value has the high bit set.

    The purpose of the sar instruction was to divide the denominator by two, so it can get the appropriate rounding behavior when there is a remainder. Reverse-compiling back into C, the function goes like this:

    int16 MulDiv(int16 a, int16 b, int16 c)
    {
     int16 sign = a ^ b ^ c; // sign of result
    
     // make everything positive; we will apply sign at the end
     if (a < 0) a = -a;
     if (b < 0) b = -b;
     if (c < 0) c = -c;
    
     //  add half the denominator to get rounding behavior
     uint32 prod = UInt16x16To32(a, b) + c / 2;
     if (HIWORD(prod) >= c) goto overflow;
     int16 result = UInt32Div16To16(prod, c);
     if (result < 0) goto overflow;
     if (sign < 0) result = -result;
     return result;
    
    overflow:
     return sign < 0 ? INT_MIN : INT_MAX;
    }
    

    Given that I've already told you where the bug is, it should be pretty easy to spot in the code above.

    Anyway, when this assembly language function was ported to Win32, it was ported as, well, an assembly language function. And the port was so successful, it even preserved (probably by accident) the sign extension bug.

    Mind you, it's a bug with amazing seniority.

  • The Old New Thing

    What was the registry like in 16-bit Windows?

    • 22 Comments

    Commenter Niels wonders when and how the registry was introduced to 16-bit Windows and how much of it carried over to Windows 95.

    The 16-bit registry was extremely simple. There were just keys, no values. The only hive was HKEY_CLASSES_ROOT. All it was used for was COM objects and file associations. The registry was stored in the REG.DAT file, and its maximum size was 64KB.

    It is my recollection that the registry was introduced in Windows 3.1, but Niels says it's not in a plain vanilla install, so I guess my memory is faulty.

    None of the 16-bit registry code was carried over to Windows 95. Windows 95 extended the registry into kernel mode, added support for values and non-string data types, increased the maximum registry size (though if some people are to be believed, not by enough), and added a bunch of other hives, like added the HKEY_CURRENT_USER, HKEY_LOCAL_MACHINE, and the HKEY_DYN_DATA, The old 16-bit registry code was woefully inadequate for all these new requirements (especially the kernel mode part), so it was all thrown out and a brand new registry written.

    In the early days of the Windows 95 registry, the in-memory signature value to identify the data structures which represent an open registry key were four bytes which corresponded to the ASCII values for the initials of the two programmers who wrote it.

  • The Old New Thing

    Charles Petzold is back with another edition of Programming Windows

    • 32 Comments

    Back in the day (and perhaps still true today), Charles Petzold's Programming Windows was the definitive source for learning to program Windows. The book is so old that even I used it to learn Windows programming, back when everything was 16-bit and uphill both ways. The most recent edition is Programming Windows, 5th Edition, which was published way back in 1998. What has he been doing since then? My guess would have been "sitting on a beach in Hawaiʻi," but apparently he's been writing books on C# and Windows Forms and WPF and Silverlight. Hey, I could still be right: Maybe he writes the books while sitting on a beach in Hawaiʻi.

    It appears that Windows 8 has brought Mr. Petzold back to the topic of Windows progarmming, and despite his earlier claims that he has no plans to write a sixth edition of Programming Windows, it turns out that he's writing a sixth edition of Programming Windows specifically for Windows 8. (Perhaps he could subtitle his book The New Old Thing.)

    Here's where it gets interesting.

    Before the book officially releases (target date November 15), there will be two pre-release versions in eBook form, one based on the Consumer Preview of Windows 8 and one based on the Release Preview.

    Now it gets really interesting: If you order the Consumer Preview eBook, it comes with free upgrades to the Release Preview eBook as well as the final eBook. (If you order the Release Preview eBook, then it comes with a free upgrade to the final eBook.)

    Can it get even more interesting than that? You bet! Because the price of getting in on the action increases the longer you wait. Act now, and you can get the Consumer Preview eBook (and all the free upgrades that come with it) for just $10. Wait a few weeks, and it'll cost you $20. Wait another few months, and it'll cost you $30; after another few weeks the price goes up to $40, and if you are a lazy bum and wait until the final eBook to be released, it'll cost you $50.

    But in order to take advantage of this offer, you have to follow the instructions on this blog entry from Microsoft Press (and read the mandatory legal mumbo-jumbo, because the lawyers always get their say).

    Bonus chatter: One publisher asked me if I wanted to write a book on programming Windows 8, but I told them that I was too busy shipping Windows 8 to have any extra time to write a book about it. And it's a good thing I turned them down, because imagine if I decided to write the book and found that Charles Petzold was coming out of retirement to write his own book. My book would have done even worse than my first book, which didn't even have any competition!

    Bonus disclaimer: Charles Petzold did not pay me to write this, nor did he offer me a cut of his royalties for shilling his book. But that doesn't mean I won't accept it! (Are you listening, Charles?)

  • The Old New Thing

    Why are the Windows 7 system notification icons colorless?

    • 41 Comments

    Mike wondered why the system notification icons went colorless in Windows 7 and why they went back to regular tooltips instead of the custom tooltips.

    I don't know either, so I asked Larry Osterman, who was in charge of the Volume icon.

    And he didn't know either. He was merely given new icons by the design team.

    But that doesn't stop me from guessing. (Which is what I do most of the time here, I just don't explicitly say that I'm guessing.)

    My guess is that the design team looked at the new Windows 7 taskbar and noticed that all the system-provided pieces were subdued and unobtrusive, with two exceptions: The Start button itself and the notification icons. The Start button kept its bright colors because, well, it's the Start button. But the notification icons? They are peripheral elements; why do they stand out on an otherwise neutral-looking taskbar? Isn't that just drawing the user's attention to something that doesn't deserve attention?

    So boom, make them monochromatic to fit with the other taskbar elements. The clock is monochromatic. The Show Desktop button is monochromatic. The taskbar itself is monochromatic. Hooray, aesthetic unity is restored.

    As for the return to standard tooltips, that's easy: The custom tooltip was a violation of the user interface guidelines.

    The old Windows Vista custom tooltip did not provide any useful information beyond the standard tooltip, so you paid the cost of developing and maintaining a custom tooltip for very little benefit. In the volume tooltip's case, the developers were spending effort fixing little bugs here and there (for example, there were painting glitches under certain accessibility conditions), effort that was detracting from other work that could be done, and switching to the standard tooltip made all the problems go away.

  • The Old New Thing

    Why is the Close button in the upper right corner?

    • 47 Comments
    Chris wants to know how the close button ended up to the right of the minimize and maximize/restore buttons. "In OS/2, it is on the left, which left the two other buttons in place."

    I don't know why the Close button went to the upper right instead of going to the left of the other buttons, but I'm going to guess. (That's what I do around here most of the time anyway; I just don't usually call it out.)

    Two words: Fitts's Law.

    The corners of the screen are very valuable, because users can target them with very little effort. You just slam the mouse in the direction you want, and the cursor goes into the corner. And since closing a window is a much more common operation than minimizing, maximizing, and restoring it, it seems a natural choice to give the close button the preferred location.

    Besides, maximizing and restoring a window already have very large targets, namely the entire caption. You can double-click the caption to maximize, and double-click again to restore. The restore even gets you a little bit of Fitt's Law action because the top of the screen makes the height of the caption bar effectively infinite.

  • The Old New Thing

    Why is there sometimes a long delay between pressing a hotkey for a shortcut and opening the shortcut?

    • 51 Comments

    Via a customer liaison, we received a problem report from a customer.

    The customer is facing issues with delayed desponses to opening a .lnk file by pressing its keyboard shortcut hotkey. This delay does not appear when the shortcut is double-clicked.

    For example, the customer has created a shortcut to Notepad and assigned it the shortcut Ctrl+Alt+X. Pressing the keyboard combination sometimes takes 5 or 6 seconds for Notepad to open. As noted above, double-clicking on the shortcut causes Notepad to open without delay.

    This issue is not consistently reproducible, but it appears to be independent of the shortcut file itself. Any shortcut with a hotkey exhibits this problem.

    All the shortcuts in question are on the desktop.

    The short answer is "There is a program running on your machine that occasionally stops responding to messages. If you press a shortcut hotkey during those moments, you will experience this problem. Identify the program that stops responding to messages and fix it."

    Okay, that sort of cuts to the chase, but the interesting part is the journey, not the destination.

    First, observe that if you associate a hotkey with a shortcut to say Notepad, and you press the hotkey twice, you do not get two copies of Notepad. The first time you press the hotkey, Notepad launches, but the second time you press the hotkey, focus is put on the existing copy of Notepad. This is one of those things that's so natural you may not even realize that it's happening.

    When you press the hotkey assigned to a shortcut, Explorer receives the hotkey and needs to decide what to do about it. Before it can launch the shortcut, it needs to see if the shortcut target already has a window open, in which case it should just switch to that window.

    Finding out whether a window has a hotkey is done by sending the window the WM_GETHOTKEY message. When you press a hotkey that is assigned to a shortcut, Explorer goes to all the windows already on the screen and asks each one, "Hey, what's your hotkey?" If any window says, "My hotkey is Ctrl+Alt+X," then Explorer says, "Oh, sorry to step on your toes. The user pressed your hotkey, so here, go ahead and take focus."

    If no window cops to having Ctrl+Alt+X as its hotkey, Explorer says, "Okay, well, then I guess I have to make one." It launches Notepad and tells it, "Oh, and your hotkey is Ctrl+Alt+X."

    If there is a window that is not responding to messages, then when Explorer asks it, "Hey, what's your hotkey?", the window just sits there and doesn't answer. After about three seconds, Explorer gives up. "Yeesh, I was just asking a question. Don't have to give me the silent treatment."

    And that petulant window is the source of the 3-second delay. It takes Explorer 3 seconds before it finally gives up and says, "Forget it. Even if that was somebody's hotkey, they're being a jerk, so I'm just going to pretend they didn't have a hotkey. Let me open a new window instead and just deal with the hotkey conflict."

  • The Old New Thing

    Cheap amusement: Searching for spelling errors in the registry

    • 34 Comments

    One source of cheap amusement is searching for spelling errors in the registry. For example, one program tried to register a new file extension, or at least they tried, except that they spelled Extension wrong.

    And they wonder why that feature never worked.

    My discovery was that my registry contained the mysterious key HKEY_CURRENT_USER\S. After some debugging, I finally found the culprit. There was a program on my computer that did the equivalent of this:

    RegCreateKeyA(HKEY_CURRENT_USER, (PCSTR)L"Software\\...", &hk);
    

    One of my colleagues remarked, "With enough force, any peg will fit in any hole."

    I suspect that the code was not that aggressively wrong. It was probably something more subtle.

  • The Old New Thing

    What happened to the Summary information created on Windows 2000 and Windows XP?

    • 32 Comments

    In Windows 2000 and Windows XP, you could add Summary information on the Details property page to files of all types. Text files, image files, some crazy file your grandmother sent you in a file format you don't know how to open. If Windows supports storing the Summary information in the file itself (for example, in EXIF tags or in Structure Storage properties), then the information gets stored there. Otherwise, Windows stashes the information in an alternate data stream. Windows Vista dropped support for storing Summary information in alternate data streams. What happened?

    Support for storing Summary information in an alternate data stream was dropped in Windows Vista because alternate data streams were found to be too fragile. If you back up the file to a CD-ROM or email it to a friend or copy it to a thumb drive or upload it to a Web site or store it in a ZIP file, the alternate data stream ends up lost. It was determined that it was better simple not to allow users to create data that was so easy to destroy accidentally.

Page 1 of 3 (25 items) 123