July, 2009

  • The Old New Thing

    Separating the metadata from the DIB pixels: Changing the raster operation

    • 4 Comments

    For a few days now, we've used the SetDIBitsToDevice function in conjunction with a precomputed BITMAPINFO to draw a DIB with an alternate color table without modifying the HBITMAP.

    The SetDIBitsToDevice function operates like a BitBlt with raster operation SRCCOPY. If you want another raster operation, you can use StretchDIBits, which has a final raster operation parameter. Despite its name, you don't have to stretch with StretchDIBits. Just pass a source and destination of equal size, and you've performed a NOP stretch, but you get the benefit of the raster operation.

    void
    PaintContent(HWND hwnd, PAINTSTRUCT *pps)
    {
     if (g_pvBits) {
        StretchDIBits(pps->hdc, 0, 0,
                          g_bmiGray.bmiHeader.biWidth,
                          g_bmiGray.bmiHeader.biHeight, 0, 0,
                          g_bmiGray.bmiHeader.biWidth,
                          g_bmiGray.bmiHeader.biHeight,
                          g_pvBits,
                         (BITMAPINFO*)&g_bmiGray, DIB_RGB_COLORS,
                          NOTSRCCOPY);
     }
    }
    

    I changed the call from SetDIBitsToDevice to StretchDIBits, setting the source and destination rectangles to the same size (so no actual stretching occurs), and specifying a raster operation of NOTSRCCOPY so the result on screen is a negative grayscale.

    Some people may object to performing a stretch operation and requesting no stretching, but that's perfectly fine. At least in this case, GDI is not stupid. If you ask it to perform a stretch operation but pass parameters that don't do any stretching, it will optimize this to a non-stretching operation. You don't need to hand-optimize it. Instead of writing

    if (cxSrc == cxDst && cySrc == cyDst) {
     BitBlt(hdc, xDst, yDst, cxDst, cyDst,
            hdcSrc, xSrc, ySrc, dwRop);
    } else {
     StretchBlt(hdc, xDst, yDst, cxDst, cyDst,
                hdcSrc, xSrc, ySrc, cxSrc, cySrc, dwRop);
    }
    

    ... just go straight to the StretchBlt:

    StretchBlt(hdc, xDst, yDst, cxDst, cyDst,
               hdcSrc, xSrc, ySrc, cxSrc, cySrc, dwRop);
    

    The StretchBlt function will convert the operation to a BitBlt if cxSrc == cxDst and cySrc == cyDst. You don't have to hand-optimize it. The GDI folks hand-optimized it for you.

    (In fact, for a long time, the SetDIBitsToDevice function simply called StretchDIBits, saying that the input and output rectangles were the same size, and StretchDIBits detected the absence of stretching and used an optimized code path. Consequently, "optimizating" the code by calling SetDIBitsToDevice was actually a pessimization.)

    Back to StretchDIBits. So far, we've been drawing the entire bitmap at the upper left corner of the destination device context. The last remaining feature of BitBlt is the ability to draw a rectangular chunk of a source bitmap at a destination location, so let's do that. We'll draw the bottom right corner of the bitmap in the bottom right corner of the window, with negative colors, and just to show we can, we'll also stretch it.

    void
    PaintContent(HWND hwnd, PAINTSTRUCT *pps)
    {
     if (g_pvBits) {
      RECT rc;
      GetClientRect(hwnd, &rc);
      int cxChunk = g_bmiGray.bmiHeader.biWidth / 2;
      int cyChunk = g_bmiGray.bmiHeader.biHeight / 2;
      StretchDIBits(pps->hdc, rc.right - cxChunk * 2,
                    rc.bottom - cxChunk * 2,
                    cxChunk * 2, cyChunk * 2,
                    g_bmiGray.bmiHeader.biWidth - cxChunk,
                    g_bmiGray.bmiHeader.biHeight - cyChunk,
                    cxChunk, cyChunk,
                    g_pvBits, (BITMAPINFO*)&g_bmiGray,
                    DIB_RGB_COLORS, NOTSRCCOPY);
     }
    }
    

    So far, we've been operating on DIB pixels that are held inside a DIB section. But there's no requirement that the bits passed to StretchDIBits come from an actual DIB section. We'll look at the total disembodiment of DIBs next time, as well as looking at some unexpected consequences of all our game-playing.

  • The Old New Thing

    On gender differences in expectations of thinness, and the impact on guys who live in their parents' basement

    • 16 Comments

    At dinner a few years ago, one of my friends brought up a study (which I can't find, so who knows if it's actually true, but let's assume it's true for the sake of the story) that examined the effect of gender differences in expectations of thinness. One of the factors that the study considered was sexual orientation, and they found that homosexual men were, on average, thinner than their heterosexual brethren, and conversely that heterosexual women were thinner on average than their homosexual um, what's the female counterpart to "brethren"?

    In other words, the conclusion of the study was that the pressure to be thin depends not so much on your own gender but rather on the gender of the person you're trying to attract. If you want to attract a man, you are more likely to be thin.

    Like I said, whether what is now a thirdhand report of the study's conclusions is true isn't important to the story. It just served as a catalyst for this snippet of conversation that ensued.

    Deborah: "I can see that. My friend Eleanor [not her real name] is a tall, beautiful Asian woman, and she says she won't date guys unless they have a bit of a pot belly."

    Me: "You do realize that you just instilled hope into the hearts of thousands of guys who live in their parents' basement?"

    Sorry guys, I didn't ask for Eleanor's number.

  • The Old New Thing

    Separating the metadata from the DIB pixels: Precalculating the BITMAPINFO

    • 4 Comments

    Last time, we saw that you can use the SetDIBitsToDevice function to draw a DIB with an alternate color table without having to modify the HBITMAP. In that version of the function, we selected the HBITMAP into a device context in preparation for drawing from it, but in fact that step isn't necessary for drawing. It was merely necessary to get the original color table so we could build our grayscale color table. If you don't care what the original colors are, then you can skip that step. And even if you care what the old colors are, and if you assume that the colors don't change, then you only need to ask once.

    To demonstrate, that all the work of building the BITMAPINFO structure could have been done ahead of time, let's use this alternate version of our program:

    HBITMAP g_hbm;
    struct BITMAPINFO256 {
     BITMAPINFOHEADER bmiHeader;
       RGBQUAD bmiColors[256];
    } g_bmiGray;
    void *g_pvBits;
    
    BOOL
    OnCreate(HWND hwnd, LPCREATESTRUCT lpcs)
    {
     // change path as appropriate
     g_hbm = (HBITMAP)LoadImage(g_hinst,
                          TEXT("C:\\Windows\\Gone Fishing.bmp"),
                          IMAGE_BITMAP, 0, 0,
                          LR_CREATEDIBSECTION | LR_LOADFROMFILE);
     if (g_hbm) {
      BITMAP bm;
      if (GetObject(g_hbm, sizeof(bm), &bm) == sizeof(bm) &&
                    bm.bmBits != NULL &&
                    bm.bmPlanes * bm.bmBitsPixel <= 8) {
       ZeroMemory(&g_bmiGray, sizeof(g_bmiGray));
       HDC hdc = CreateCompatibleDC(NULL);
       if (hdc) {
        HBITMAP hbmPrev = SelectBitmap(hdc, g_hbm);
        UINT cColors = GetDIBColorTable(hdc, 0, 256, g_bmiGray.bmiColors);
        for (UINT iColor = 0; iColor < cColors; iColor++) {
         BYTE b = (BYTE)((30 * g_bmiGray.bmiColors[iColor].rgbRed +
                          59 * g_bmiGray.bmiColors[iColor].rgbGreen +
                          11 * g_bmiGray.bmiColors[iColor].rgbBlue) / 100);
         g_bmiGray.bmiColors[iColor].rgbRed   = b;
         g_bmiGray.bmiColors[iColor].rgbGreen = b;
         g_bmiGray.bmiColors[iColor].rgbBlue  = b;
        }
        g_bmiGray.bmiHeader.biSize        = sizeof(g_bmiGray.bmiHeader);
        g_bmiGray.bmiHeader.biWidth       = bm.bmWidth;
        g_bmiGray.bmiHeader.biHeight      = bm.bmHeight;
        g_bmiGray.bmiHeader.biPlanes      = bm.bmPlanes;
        g_bmiGray.bmiHeader.biBitCount    = bm.bmBitsPixel;
        g_bmiGray.bmiHeader.biCompression = BI_RGB;
        g_bmiGray.bmiHeader.biClrUsed     = cColors;
        g_pvBits                          = bm.bmBits;
        DeleteDC(hdc);
       }
     }
     return TRUE;
    }
    
    void
    PaintContent(HWND hwnd, PAINTSTRUCT *pps)
    {
     if (g_pvBits) {
        SetDIBitsToDevice(pps->hdc, 0, 0,
                      g_bmiGray.bmiHeader.biWidth,
                      g_bmiGray.bmiHeader.biHeight, 0, 0,
                      0, g_bmiGray.bmiHeader.biHeight,
                      g_pvBits,
                      (BITMAPINFO*)&g_bmiGray, DIB_RGB_COLORS);
     }
    }
    

    I moved the blue code from PaintContent to OnCreate to demonstrate that pretty much all of the work we used to do in PaintContent could have been done ahead of time. The only other thing we had to do was save the pointer to the bits so we could pass them to SetDIBitsToDevice. (Of course, that pointer becomes invalid once the controlling HBITMAP is destroyed, so be careful! In practice, you probably would be better off calling GetObject immediately before drawing to protect against the case that somebody deleted the bitmap out from under you.)

    Next time, we'll look at another operation we can perform when we have a BITMAPINFO and a collection of pixels.

    (Note that there are issues with this technique which will be taken up on Friday.)

  • The Old New Thing

    What happens to your restaurant tip?

    • 37 Comments

    Some time ago, the Seattle Times ran an article on how your restaurant tip gets divided up among the staff. A week later, they ran an entire article of responses to the original article, some from customers, but many from restaurant staff (both cooks and servers). And, now on a roll, the next week's food section looked at the sociology of splitting the bill with a sidebar looking at how hard it is for different types of restaurants.

  • The Old New Thing

    The fun and profit of manipulating the DIB color table can be done without having to modify it

    • 11 Comments

    If I were Michael Kaplan, I'd have a more clever title like I'm not touching you! or Look but don't touch or maybe Looking at a DIB through BITMAPINFO-colored glasses.

    We saw some time ago that you can manipulate the DIB color table to perform wholesale color remapping. But in fact you can do this even without modifying the DIB color table, which is a handy trick if you want to do color remapping but you don't want to change the bitmap itself. For example, the bitmap is not one that is under your control (so you shouldn't be modifying it), or the bitmap might be in use on multiple threads (so modifying it will result in race conditions).

    Let's demonstrate this technique by converting the "Gone Fishing" bitmap to grayscale, but doing so without actually modifying the bitmap. As always, we start with our scratch program and make the following changes:

    HBITMAP g_hbm;
    
    
    BOOL
    OnCreate(HWND hwnd, LPCREATESTRUCT lpcs)
    {
     // change path as appropriate
     g_hbm = (HBITMAP)LoadImage(g_hinst,
                          TEXT("C:\\Windows\\Gone Fishing.bmp"),
                          IMAGE_BITMAP, 0, 0,
                          LR_CREATEDIBSECTION | LR_LOADFROMFILE);
     return TRUE;
    }
    
    void
    OnDestroy(HWND hwnd)
    {
     if (g_hbm) DeleteObject(g_hbm);
     PostQuitMessage(0);
    }
    
    void
    PaintContent(HWND hwnd, PAINTSTRUCT *pps)
    {
     if (g_hbm) {
      BITMAP bm;
      if (GetObject(g_hbm, sizeof(bm), &bm) == sizeof(bm) &&
                    bm.bmBits != NULL &&
                    bm.bmPlanes * bm.bmBitsPixel <= 8) {
       struct BITMAPINFO256 {
        BITMAPINFOHEADER bmiHeader;
        RGBQUAD bmiColors[256];
       } bmiGray;
       ZeroMemory(&bmiGray, sizeof(bmiGray));
       HDC hdc = CreateCompatibleDC(NULL);
       if (hdc) {
        HBITMAP hbmPrev = SelectBitmap(hdc, g_hbm);
        UINT cColors = GetDIBColorTable(hdc, 0, 256, bmiGray.bmiColors);
        for (UINT iColor = 0; iColor < cColors; iColor++) {
         BYTE b = (BYTE)((30 * bmiGray.bmiColors[iColor].rgbRed +
                          59 * bmiGray.bmiColors[iColor].rgbGreen +
                          11 * bmiGray.bmiColors[iColor].rgbBlue) / 100);
         bmiGray.bmiColors[iColor].rgbRed   = b;
         bmiGray.bmiColors[iColor].rgbGreen = b;
         bmiGray.bmiColors[iColor].rgbBlue  = b;
        }
        bmiGray.bmiHeader.biSize        = sizeof(bmiGray.bmiHeader);
        bmiGray.bmiHeader.biWidth       = bm.bmWidth;
        bmiGray.bmiHeader.biHeight      = bm.bmHeight;
        bmiGray.bmiHeader.biPlanes      = bm.bmPlanes;
        bmiGray.bmiHeader.biBitCount    = bm.bmBitsPixel;
        bmiGray.bmiHeader.biCompression = BI_RGB;
        bmiGray.bmiHeader.biClrUsed     = cColors;
        SetDIBitsToDevice(pps->hdc, 0, 0,
                          bmiGray.bmiHeader.biWidth,
                          bmiGray.bmiHeader.biHeight, 0, 0,
                          0, bmiGray.bmiHeader.biHeight,
                          bm.bmBits,
                         (BITMAPINFO*)&bmiGray, DIB_RGB_COLORS);
    
        BitBlt(pps->hdc, bm.bmWidth, 0, bm.bmWidth, bm.bmHeight,
               hdc, 0, 0, SRCCOPY);
        SelectBitmap(hdc, hbmPrev);
        DeleteDC(hdc);
       }
      }
     }
    }
    

    Things start off innocently enough, loading the bitmap into a DIB section for use during painting.

    We do our work at paint time. First, we confirm that we indeed have a DIB section and that it is 8bpp or lower, because bitmaps at higher than 8bpp do not use color tables.

    We then select the bitmap into a DC so we can call GetDIBColorTable to get its current color table. (This is the only step that requires the bitmap to be selected into a device context.) We then edit the color table to convert each color to its grayscale equivalent.

    Finally, we fill in the BITMAPINFO structure with the description of the bitmap bits, and then we call SetDIBitsToDevice to send the pixels to the destination DC.

    Just for good measure, we also BitBlt the original unmodified bitmap, to prove that the original bitmap is intact and unchanged.

    This mini-program is really just a stepping stone to other things you can do with this technique of separating the metadata (the BITMAPINFO) from the pixels. We'll continue our investigations tomorrow.

    (Before you all run out and use this technique everywhere you can imagine, wait for the remarks in Friday's installment.)

  • The Old New Thing

    Failed follow-up: The case of the dubious dental work

    • 4 Comments

    I've been waiting for an opportunity to do a follow-up on this story, but the trail appears to have gone cold. Here's the story as we know it so far:

    In 2004, a woman (who had previously run unsuccessfully for a city council position) files a $6,370 claim for dental work against McDonald's, claiming that she injured her teeth biting into a cherry pie. Less than three months later, she files a $6,006 claim against McDonald's for dental work resulting from biting into a piece of bone in a cheeseburger patty. The insurance company investigates and determines that both claims were false: The dentist who allegedly performed the dental work (coincidentally: her employer, where she had access to billing documents) says he performed no dental work on her.

    It so happens that the year before, the woman had pled guilty to first-degree theft in which she had purchased property with her employer's money as well as embezzled $27,000 in cash. (Coincidentally, in that case, she also worked in a dentist office as an office manager.)

    My frustration is that I haven't found any coverage of what the result of the insurance fraud charges were. There are quite a number of cases involving the defendant over the past five years, but I think 07-1-06399-1 is the relevant one here, since the arraignment date matches the news article date to within a few weeks.

    The hearing was continued to October 9, 2007, then delayed one more day, at which point the defendant pled guilty, and a statement to that effect was filed the next day. In November, a felony judgment and sentence was handed down (case 07-9-33438-1) consisting of $500 plus restitution. Jail time or home detention doesn't appear to be recorded into the case history, so I don't know the full extent of the sentence.

  • The Old New Thing

    Speculation on how a mishandled 13-character string can result in a blue screen

    • 35 Comments

    Commenter nolan reminisces about an old Windows 95 bug in the networking layer that crashed if a string was exactly 13 characters long. "So for the past 10 years or so, I've been wondering exactly how one could write code with that bug. Any bug that weird has to have a great story behind it."

    I don't know what the story behind it is, but if after ten years you still can't imagine how such a bug could be possible, you don't have a very active imagination.

    SomeFunction(char *hostname)
    {
     char tmpbuffer[13]; // most host names are less than this size
     char *buffer;
     if (strlen(hostname) > sizeof(tmpbuffer)) {
       buffer = strdup(hostname);
       if (!buffer) return some error;
     } else {
       buffer = strcpy(tmpbuffer, hostname);
     }
     ... do stuff with buffer ...
     if (buffer != tmpbuffer) free(buffer);
    }
    

    If the host name is exactly 13 characters, then this code overflows the buffer by one character, corrupting the stack. A crash is hardly surprising at this point.

  • The Old New Thing

    The world reaction to the unexpected death of Michael Jackson extends to young children

    • 14 Comments

    I had occasion to meet up with the same family whose two-year-old was learning to lie in an earlier story. It was only a day or two after the death of Michael Jackson, and the older sister (five years old) told me, "Did you know? Michael Jackson, he went to sleep and he is never going to wake up."

    Her younger sister (now three), corrected her.

    "No, he's dead!"

  • The Old New Thing

    If dynamic DLL dependencies were tracked, they'd be all backwards

    • 15 Comments

    Whenever the issue of DLL dependencies arises, I can count on somebody arguing that these dynamic dependencies should be tracked, even if doing so cannot be proven to be reliable. Even if one could walk the call stack reliably, you would still get it wrong.

    The example I gave originally was the common helper library, where A.DLL loads B.DLL via an intermediate function in MIDDLE.DLL. You want the dependency to be that A.DLL depends on B.DLL, but instead the dependency gets assigned to MIDDLE.DLL.

    "But so what? Instead of a direct dependency from A.DLL to B.DLL, we just have two dependencies, one from A.DLL to MIDDLE.DLL, and another from MIDDLE.DLL to B.DLL. It all comes out to the same thing in the end."

    Actually, it doesn't. It comes out much worse.

    After all, MIDDLE.DLL is your common helper library. All of the DLLs in your project depend on it. Therefore, the dependency diagram in reality looks like this:

    A.DLL B.DLL
    MIDDLE.DLL

    A.DLL depends on B.DLL, and both DLLs depend on MIDDLE.DLL. That common DLL really should be called BOTTOM.DLL since everybody depends on it.

    Now you can see why the dependency chain A.DLL → MIDDLE.DLL → B.DLL is horribly wrong. Under the incorrect dependency chain, the DLLs would be uninitialized in the order A.DLL, MIDDLE.DLL, B.DLL, even though B.DLL depends on MIDDLE.DLL. That's because your "invented" dependency introduces a cycle in the dependency chain, and a bogus one at that. Once you have cycles in the dependency chain, everything falls apart. You took something that might have worked into something that explodes upon impact.

    This situation appears much more often than you think. In fact it happens all the time. Because in real life, the loader is implemented in the internal library NTDLL.DLL, and KERNEL32.DLL is just a wrapper function around the real DLL loader. In other words, if your A.DLL calls LoadLibrary("B.DLL"), you are already using a middle DLL; its name is KERNEL32.DLL. If this "dynamic dependency generation" were followed, then KERNEL32.DLL would be listed as dependent on everything. When it came time to uninitialize, KERNEL32.DLL would uninitialized before all dynamically-loaded DLLs, because it was the one who loaded them, and then all the dynamically-loaded DLLs would find themselves in an interesting world where KERNEL32.DLL no longer existed.

    Besides, the original problem arises when A.DLL calls a function in B.DLL during its DLL_PROCESS_DETACH handler, going against the rule that you shouldn't call anything outside your DLL from your DllMain function (except perhaps a little bit of KERNEL32 but even then, it's still not the best idea). It's one thing to make accommodations so that existing bad programs continue to run, but it's another to build an entire infrastructure built on unreliable heuristics in order to encourage people to do something they shouldn't be doing in the first place, and whose guesses end up taking a working situation and breaking it.

    You can't even write programs to take advantage of this new behavior because walking the stack is itself unreliable. You recompile your program with different optimizations, and all of a sudden the stack walking stops working because you enabled tail call elimination. If somebody told you, "Hey, we added this feature that isn't reliable," I suspect your reaction would not be "Awesome, let me start depending on it!"

  • The Old New Thing

    Film students and The Bicycle Thief

    • 41 Comments

    The current generation of young people grew up in a very different world from us older folks. There has always been an Internet. Everybody is accessible by mobile phone. Cars have always had power windows. (Which reminds me of a story of a friend of mine who has an older-model car and was giving a ride to an eight-year-old relative. The youngster pointed at the window crank and asked, "What's this?" Upon learning its purpose, the young passenger spent the remainder of the trip opening and closing the window, giggling with glee. "You know, most people pay extra so they don't have to do that.")

    But it's not just elementary school children whose views of the world are different.

    Some time ago, I was at a dinner where another guest was a film professor at the local university. In one class, they were discussing the classic movie Ladri di Biciclette (The Bicycle Thief in the United States), the story of a poor man in post-war Italy searching for his stolen bicycle, the bicycle he needs for his job. One student asked, "Why doesn't he just buy another bicycle?"

Page 3 of 5 (42 items) 12345