Joseph M. Newcomer and Bruce Horn

The "Undocumented Corner" is a new DDJ column that will cover undocumented aspects of the programming interfaces for DOS, Windows, OS/2, networks, and any other operating systems for which DDJ readers are programming. The intent is to not just explain obscure or nonintuitive interfaces, but to present solid reference material that really isn't in the manuals -- but should be.

For example, an explanation of how to use the Windows DDE interface wouldn't belong here because, while extremely difficult, that interface is documented. If, however, you've found five new DDE messages that are genuinely useful or important (this is a purely hypothetical example), but aren't mentioned in the manuals that come with the Windows SDK, then this is the place to talk about them. Likewise if you have, say, disassembled Windows and want to talk about how the documented DDE interface is implemented. In other words, in this column DDJ readers will be writing in to talk about undocumented interfaces and operating-system internals.

One purpose of this column is to provide a forum for readers of Undocumented DOS (Addison-Wesley, 1990) and Undocumented Windows (Addison-Wesley, 1992), for which I was a coauthor. While generally recognized as standard works on the subject, both books contain errors and omissions that deserve some public attention before the next editions appear. (The second edition of Undocumented DOS is due to appear in April 1993. It will be about 150 pages longer than the first edition, and will cover topics such as DR-DOS, the relation between Windows and undocumented DOS, and disassembly of the DOS kernel.)

Future "Undocumented Corners" might cover, for example, undocumented LAN Manager named-pipe functions available under DOS, the SmartDrive 4 "BABE" interface, the PIF file format, FDISK internals, walking the Windows VxD chain, undocumented DPMI, undocumented DR-DOS, and undocumented NT. (If you have NT and want a sneak preview, just run coff -dump -imports pview.exe.)

Of course, the usual cautions about relying on undocumented operating-system features apply. These features can change in the next version of the operating system, because the vendor is under no obligation to support them. On the other hand, the most useful undocumented features tend to get documented (look at Microsoft's MS-DOS Programmer's Reference for DOS 5, and the Get/SetSelectorBase/Limit functions in Windows 3.1), so knowing about and using these features may do nothing more dangerous than giving you a year or two jump on your more cautious competitors.

The first problem we confronted was discovering exactly what a region looked like. Precisely where were the bits stored? Undocumented Windows (by Schulman, Maxey, and Pietrek, Addison-Wesley, 1992), hereafter referred to as UndocWin, describes in a less-than-useful fashion the key component of the RGNOBJ structure as "not currently understood" (pp. 589). We were therefore on our own in reverse-engineering the actual GDI data.

Several hours of tracing assembly code with Codeview began to reveal some of the truth. The critical question was how, given the HRGN region handle, to get an address for an actual region.

Regions are objects that change size. They are managed in a local storage heap of the Windows GDI module. However, because they can change size, GDI wants to be able to shift their position around, to allocate new storage and compact existing storage. The particular function that does this is GdiSeeGdiDo( ), described on page 570 of UndocWin. So an indirection table, similar to the Macintosh's master pointer block, is used. The region handle is the offset in a GDI data segment of the actual pointer to the region data. This pointer remains fixed during the entire lifetime of the region. As the contents of the region change (based on operations such as CombineRgn( )), the actual region data may shift position. In other words, the region handle is an LMEM_MOVEABLE pointer into the GDI heap. In Windows, LMEM_MOVEABLE is a pointer to a pointer, just like handles on the Macintosh (see UndocWin, pp. 305).

We first had to convert the handle to a far pointer, then use this far pointer to access another pointer, which was the pointer to the actual region data. This second pointer can be thought of as a handle to a movable chunk of storage that contains the actual region data. We thus have to convert this second handle to a global segment:offset pointer, simulating the effect of LocalLock.

Having carefully studied the way in which regions were created and combined, we knew that one of the WORDs was a length of the region data, which simplified some of the printout. We knew we only had to print out a fixed number of words to get the complete region displayed. Our examples were a set of examples of two rectangles, a hollow box formed from them, an L-shaped region formed from two rectangles, and an ellipse.

Our next job was to decode the region. The adventures here, including the false starts, guesses, and general staring at the code and data would make a great series of boring war stories told over suitable beverages, but we'll proceed directly to the final result, with only a brief diversion about reverse engineering.

Some years ago, Donald Knuth wrote a paper on the early Babylonian mathematicians' representation of algorithms ("Ancient Babylonian Algorithms," Communications of the ACM, July 1972, pp. 671-677; thanks to Jeremy Gibbons in New Zealand for this citation). They had no notion of algebra, nor of variables, but expressed the algorithms numerically. The art was to choose the initial values so that all intermediate values were unique; thus an integer represented the equivalent of a variable of that "name." Once the sequence of operations in terms of the numbers was memorized, the person executing the algorithm had only to associate the numbers representing the "variables" or "parameters" at each step with the actual numbers of the particular computation.

Whenever you are reverse-engineering something, it's important to similarly choose values that guarantee that, insofar as possible, you have unique values internally. For example, a rectangular region with coordinates {100, 100, 200, 200} would be an exceedingly poor choice, because not only would it not be possible to tell the X[0] coordinate from the Y[0] coordinate, or X[1] from Y[1], but if the internal representation happened to store width and height instead of absolute coordinates, the internal representation might be {100, 100, 100, 100}. The values we used were chosen so that not only were the values unique, but all differences in X and Y were also unique values.

We had a choice of how to implement region mapping. The X Window system implements two primitives, Xoffset-Region, which performs a linear transformation of the region, and XShrink-Region, which shrinks a region by specified integral amounts in the X and Y direction. The Macintosh Toolbox implements a much more general mechanism, MapRgn. We chose to implement the latter.

MapRgn( ) is defined as mapping a region based on the relationship of two rectangles, the source and destination rectangles. The vertical dimensions of the region are scaled according to the ratio of the destination-rectangle height to the source-rectangle height. The horizontal dimensions of the region are scaled according to the ratio of their widths. The final (absolute) position of the region is effectively the result placing the top-left corner of its bounding box of the region relative to the destination rectangle in the scaled relationship as the top-left corner of the unmapped region relative to the source rectangle.

This can be done by mapping each of the X,Y coordinates of the region according to the formula dst=(src-pos_src) * scale+pos_dst, where: dst is the value for x or y in the mapped region; src is the value for x or y in the source region; pos_src is the value for x or y of the top-left corner of the source rectangle; pos_dst is the value for x or y of the top-left corner of the destination rectangle; and scale represents the ratio of the destination-rectangle width or height to the corresponding source-rectangle dimension.

The dimensions of the rectangles are expressed as integer values. We have to deal with nonintegral ratios, such as a mapping of 0.7 or 1.2. The solution is obvious: We need to use floating-point computations. This means that to map the points, we need to convert each point in the region to floating point, perform a floating-point computation, and convert the result back to an integer. This is not particularly attractive from the view-point of performance, particularly if a math coprocessor is not available.

There is an alternative: fixed-point arithmetic. We convert each 16-bit integer to a 32-bit fixed-point number, where the high-order 16 bits are the integer part of the number and the low-order 16 bits are the fractional part of the number. We need to implement the following operations: convert integer to fixed point, convert fixed point to integer (rounded), multiply two fixed-point numbers generating a fixed-point result, and divide two integers, producing a fixed-point result.

You may be wondering: Why this particular implementation of regions? As we analyzed this data, we came up with some conjectures of the rationale for the particular representation chosen.

One representation that might be chosen is to keep the properties as abstract as possible; for example, when an elliptical region is created, to store the parameters of the elliptical region and mark the region type as elliptical; similarly for a rectangular region. A significant problem with this representation is the operations of intersection or difference on the regions; for example, imagine what it would take to represent an elliptical region with a rectangular hole in the middle of it. Four elliptical chords could do it, but these are expensive to compute in the first place and even more expensive to do subsequent operations with. The organization of rectangular banding seems a natural way to reduce the computational complexity.

The problem with this is, as we observed earlier, rectangular approximations to nonrectangular polygons (and the "infinite-sided polygon" elliptical regions) are only as accurate as the quantization. Making smaller (down to one pixel) bands gives the best approximation, but at the highest cost of storage; making larger bands reduces the number of rectangles, at the cost of accuracy. The Windows NT GDI represents regions as trapezoids, which allows for better approximations with fewer region segments, at a slightly higher computational cost.

Another representation would be a linked list of segments. One such representation is described in the paper "Scan-Line Coherent Shape Algebra," by Jonathan E. Steinhart (Graphics Gems II, James Arvo, ed., Academic Press, 1991). A region is represented not by rectangular segments, as described here, but as a linked list of horizontal spans. Each span contains its top Y-coordinate, a pointer to the next span, and a pointer to the segment list. The bottom Y coordinate is obtained from the top Y coordinate of the next span (and a discontinuity in the spans is thus represented as a span with no segments). The segment list is a linked list of segments ordered by X coordinates. In the paper Steinhart describes how to implement the operations of intersection, union, and translation.

As in the Steinhart paper, the Microsoft GDI maintains ordering in both Y and X. This serves two purposes. For one thing, it makes it easy to clip regions; you ignore all regions above your clipping region, and when you finally encounter a region whose top is below your clipping region, you can stop. Since the segments are maintained in X-coordinate order within each span, you can apply the same technique for clipping left and right; only the subregions partially intersecting the clipping region require computation. More importantly (especially when polygonal regions are used), it allows for a more efficient computation of the intersection, union, difference, XOR, and other operations because you can ignore certain computations outside the bounding box of the other region, and need only compute new rectangles in the overlapping areas. For example, in computing an intersection of two regions A and B, any rectangles in A that are outside the bounding box of B can be ignored, as can any rectangles in B that are outside the bounding box of A.

Why a vector instead of a linked list? We conjecture that this is because the GDI space is limited to a single 64K local heap; the vector representation is much more compact than a linked-list representation. We also conjecture that the repeated number of X-spans in the region (Y-span word 3+nx) is present to allow the structure to be traversed in a backward direction, for example, to locate the start of the previous Y-span.

One aspect of the representation we find dismaying is that it appears that coordinates are kept in the screen space rather than in a user-space coordinate system. This means that scaling a rectangle of a region so that it has a 0 dimension and then scaling it by a multiple greater than 1 means that it will not give the same effect as scaling the original to the same size; for example, scaling a region by 0.1 and then scaling the resulting region by 20 is not necessarily the same as scaling the original region by 2.

We suppose this was done because it has an impact only when scaling, and the absence of that operation made the more-general representation superfluous. Because Windows was originally committed to run efficiently on an 8088, and adding the necessary transformations to the internals of the region operations would have made these representations unacceptably inefficient. However, since this representation is an undocumented interface, there's no reason for Microsoft to maintain it across releases. Perhaps a future release of Windows could use a representation more amenable to scaling, and we could have a supported scale-region operation.

In conclusion, with some considerable effort we were able to enhance the Windows region operations with a new and very useful operation. It is the fond hope of the authors that such an operation will become part of the official Windows API in the future; but we were faced with the problem that we needed this operation and had no other choice but to add it ourselves.

We would like to acknowledge Maya Design Group and Jim Morris for permission to publish this work.

<a name="00dd_000b">

WORD GetGDIsegment(void)
    {
     HRGN (FAR PASCAL * A)(int, int, int, int);
     unsigned short far * B;
     WORD GDIseg;  /* GDI segment */
     A = CreateRectRgn;
     B = (unsigned short far *)A; /* function prolog: MOV AX,DGROUP */
     ((char far *) B)++;
     GDIseg = *B;
     return GDIseg;
    }





<a name="00dd_000c">
<a name="00dd_000d">

<a name="00dd_000d">


#include <toolhelp.h>
WORD GetGDISegment(void)
    {
     SYSHEAPINFO info;
     info.dwSize = sizeof(info);
     SystemHeapInfo(&info);
     return info.hGDISegment;
    }





<a name="00dd_000e">
<a name="00dd_000f">

<a name="00dd_000f">

#include <dos.h>
static unsigned short far * ConvertRegionToAddress(HRGN region)
    {
     WORD GDIseg;
     unsigned short far * * p; /* pointer to GDI segment */
     unsigned short far *  pv; /* pointer to region data */
     GDIseg = GetGDIsegment();
     FP_SEG(p) = GDIseg;
     FP_OFF(p) = handle;
     pv = (unsigned short far *) *p;
     FP_SEG(pv) = GDIseg;
     return pv;
    }






<a name="00dd_0010">
<a name="00dd_0011">

<a name="00dd_0011">

static tFixed ToFixed(int value)
    {
     return ((tFixed) value) << 16;
    }





<a name="00dd_0012">
<a name="00dd_0013">

<a name="00dd_0013">

static tFixed tFixMul(tFixed num1, tFixed num2)
    {
     tFixed result;
     int    negated = false;
     unsigned short int2;
     unsigned short frac2;

    /* 'negated' is the sign of the result. We in effect store
    the sign bits. This will fail if we give it -32768.0000 */
     num1 = ((long) num1 < 0) ? negated = !negated, -num1 : num1;
     num2 = ((long) num2 < 0) ? negated = !negated, -num2 : num2;

     /* Extract the highword (integer part) and lowword (fraction
     part) of the second operand */
     int2 = (unsigned long) num2 >> 16;
     frac2 = (unsigned long) num2 & 0xFFFF;

     result=(((unsigned long) num1*frac2) >> 16)+((unsigned long) num1*int2);
     return (negated ? -result : result);
    }





<a name="00dd_0014">
<a name="00dd_0015">

<a name="00dd_0015">

static tFixed tFixRatio(int num, int denom)
    {
     tFixed     result;
     result = ((long) num << 16) / (long) denom;
     return result;
    }





<a name="00dd_0016">
<a name="00dd_0017">

<a name="00dd_0017">

static short tFixRound(tFixed num)
    {
     int negated = ((long) num < 0);
     short result  = negated ? (-num) >> 16 : num >> 16;
     unsigned short low = negated ? (-num) & 0xFFFF : num & 0xFFFF;
     if (negated)
        return -result - (low > 0x7FFF ? 1 : 0);
     else
        return  result + (low > 0x7FFF ? 1 : 0);
}






<a name="00dd_0018">
<a name="00dd_0019">

<a name="00dd_0019">

HRGN outer = CreateRectRgn(100,200,300,400);
HRGN inner = CreateRectRgn(110,210,290,390);
HRGN hollow = CreateRectRgn(0,0,0,0);
CombineRgn(hollow, outer, NULL, RGN_COPY);
CombineRgn(hollow, hollow, inner, RGN_DIFF);




<a name="00dd_001a">
<a name="00dd_001b">

<a name="00dd_001b">

static short MapScalar(short value, short srcOffset, short dstOffset,
    tFixed scale)
    {
     return tFixRound(tFixMul(scale, ToFixed(value-srcOffset))) + dstOffset;
    }
void MapRgn(HRGN rgn, RECT * srcRect, RECT * dstRect)
    {
     register short srcX = srcRect->left;
     register short srcY = srcRect->top;
     register short dstX = dstRect->left;
     register short dstY = dstRect->top;
     /* Compute the X-scale and Y-scale as the ratio of the
        length of the source and destination width and height */
     tFixed scaleX = tFixRatio( (dstRect->right - dstX),
                                (srcRect->right - srcX));
     tFixed scaleY = tFixRatio( (dstRect->bottom - dstY),
                                (srcRect->bottom - srcY));
     short ySpans;         // number of Y-spans in the region
     short yspan;          // current Y-span being processed
     short xSpans;         // number of X-spans in this Y-span
     short xspan;          // current X-span being processed
     short RgnLength;      // length of region, in words
     short * regionbase;   // base of region data
     short * scanC;        // current region word

     regionbase = ConvertRegionToAddress(rgn); // Point to beginning of region
     scanC = regionbase;            // start at base of region
     scanC += 5;                    // skip GDI header, point to region length
     if (GetSystemMetrics(SM_DEBUG) && (GetVersion() != 3))
         scanC += 2;                // adjust for 3.1+ Debug version!!
     RgnLength     = *scanC++;      // word 5: region length
     ySpans        = *scanC++;      // word 6: number of Y-spans
     scanC += 1;                    // Skip to bounding box.

     // Map bounding box for the region
     *scanC++ = MapScalar(*scanC, srcX, dstX, scaleX);     // left
     *scanC++ = MapScalar(*scanC, srcY, dstY, scaleY);     // top
     *scanC++ = MapScalar(*scanC, srcX, dstX, scaleX);     // right
     *scanC++ = MapScalar(*scanC, srcY, dstY, scaleY);     // bottom
     for (yspan = 0; yspan < ySpans; yspan++)
        { /* foreach y-span */
         xSpans = *scanC++ / 2;

         // Now we are pointing to the y start and y end points. Scale them.
         *scanC = MapScalar(*scanC, srcY, dstY, scaleY);   // startY
         scanC++;
         *scanC = MapScalar(*scanC, srcY, dstY, scaleY);   // endY
         scanC++;
         // We are pointing to the x limit pairs for this y-span.
         // Iterate down these, scaling each of them
         for (xspan = 0; xspan < xSpans; xspan++)
            { /* foreach x-span */
             // now we are pointing to the x start and end points. Scale them
             *scanC = MapScalar(*scanC, srcX, dstX, scaleX);  // startX
             scanC++;
             *scanC = MapScalar(*scanC, srcX, dstX, scaleX);  // endX
             scanC++;
            } /* foreach x-span */
         // The next word is the second copy of the number of X spans * 2.
         // Ignore it.
         scanC++;
        } /* foreach y-span */

}

Copyright © 1993, Dr. Dobb's Journal