windows-server-2003/windows/core/ntgdi/gre/dither.cxx

/******************************Module*Header*******************************\
* Module Name: dither.cxx
*
* This algorithm for color dithering is patent pending and its use is
* restricted to Microsoft products and drivers for Microsoft products.
* Use in non-Microsoft products or in drivers for non-Microsoft products
* is prohibited without the expressed written consent of Microsoft Corp.
*
* The patent application is the primary reference for the operation of the
* color dithering code.
*
* Note that in the comments and variable names, "vertex" means "vertex of
* either the inner (half intensity) or outer (full intensity) color cube."
* Vertices map to colors 0-7 and 9-15 of the Windows standard (required)
* 16-color palette, where vertices 0-7 are the vertices of the inner color
* cube, and 0 plus 9-15 are the vertices of the full color cube. Vertex 8 is
* 75% gray; this could be used in the dither, but that would break apps that
* depend on the exact Windows 3.1 dithering. This code is Window 3.1
* compatible.
*
* Note that as a result of the compatibility requirement, the dither
* produced by this algorithm is the exact same dither as that produced
* by the default Windows 3.1 16 color and 256 color VGA drivers.
*
* Copyright (c) 1992-1999 Microsoft Corporation
\**************************************************************************/

#include "precomp.hxx"

/**************************************************************************\
* This function takes a value from 0 - 255 and uses it to create an
* 8x8 pile of bits in the form of a 1BPP bitmap.  It can also take an
* RGB value and make an 8x8 bitmap.  These can then be used as brushes
* to simulate color unavaible on the device.
*
* For monochrome the basic algorithm is equivalent to turning on bits
* in the 8x8 array according to the following order:
*
*  00 32 08 40 02 34 10 42
*  48 16 56 24 50 18 58 26
*  12 44 04 36 14 46 06 38
*  60 28 52 20 62 30 54 22
*  03 35 11 43 01 33 09 41
*  51 19 59 27 49 17 57 25
*  15 47 07 39 13 45 05 37
*  63 31 55 23 61 29 53 21
*
* Reference: A Survey of Techniques for the Display of Continous
*            Tone Pictures on Bilevel Displays,;
*            Jarvis, Judice, & Ninke;
*            COMPUTER GRAPHICS AND IMAGE PROCESSING 5, pp 13-40, (1976)
\**************************************************************************/

#define SWAP_RB 0x00000004
#define SWAP_GB 0x00000002
#define SWAP_RG 0x00000001

#define SWAPTHEM(a,b) (ulTemp = a, a = b, b = ulTemp)

// PATTERNSIZE is the number of pixels in a dither pattern.
#define PATTERNSIZE 64

// Tells which row to turn a pel on in when dithering for monochrome bitmaps.
static BYTE ajByte[] = {
    0, 4, 0, 4, 2, 6, 2, 6,
    0, 4, 0, 4, 2, 6, 2, 6,
    1, 5, 1, 5, 3, 7, 3, 7,
    1, 5, 1, 5, 3, 7, 3, 7,
    0, 4, 0, 4, 2, 6, 2, 6,
    0, 4, 0, 4, 2, 6, 2, 6,
    1, 5, 1, 5, 3, 7, 3, 7,
    1, 5, 1, 5, 3, 7, 3, 7
};

// The array of monochrome bits used for monc
static BYTE ajBits[] = {
    0x80, 0x08, 0x08, 0x80, 0x20, 0x02, 0x02, 0x20,
    0x20, 0x02, 0x02, 0x20, 0x80, 0x08, 0x08, 0x80,
    0x40, 0x04, 0x04, 0x40, 0x10, 0x01, 0x01, 0x10,
    0x10, 0x01, 0x01, 0x10, 0x40, 0x04, 0x04, 0x40,
    0x40, 0x04, 0x04, 0x40, 0x10, 0x01, 0x01, 0x10,
    0x10, 0x01, 0x01, 0x10, 0x40, 0x04, 0x04, 0x40,
    0x80, 0x08, 0x08, 0x80, 0x20, 0x02, 0x02, 0x20,
    0x20, 0x02, 0x02, 0x20, 0x80, 0x08, 0x08, 0x80
};

// Translates vertices back to the original subspace. Each row is a subspace,
// as encoded in ulSymmetry, and each column is a vertex between 0 and 15.
BYTE jSwapSubSpace[8*16] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
    0, 2, 1, 3, 4, 6, 5, 7, 8, 10, 9, 11, 12, 14, 13, 15,
    0, 1, 4, 5, 2, 3, 6, 7, 8, 9, 12, 13, 10, 11, 14, 15,
    0, 4, 1, 5, 2, 6, 3, 7, 8, 12, 9, 13, 10, 14, 11, 15,
    0, 4, 2, 6, 1, 5, 3, 7, 8, 12, 10, 14, 9, 13, 11, 15,
    0, 2, 4, 6, 1, 3, 5, 7, 8, 10, 12, 14, 9, 11, 13, 15,
    0, 4, 1, 5, 2, 6, 3, 7, 8, 12, 9, 13, 10, 14, 11, 15,
    0, 1, 4, 5, 2, 3, 6, 7, 8, 9, 12, 13, 10, 11, 14, 15,
};


// Converts a nibble value in the range 0-15 to a dword value containing the
// nibble value packed 8 times.

// For 8bpp, also translate to 256-color palette index.
ULONG ulNibbleTo8bppDword[16] = {
    0x00000000,
    0x01010101,
    0x02020202,
    0x03030303,
    0x04040404,
    0x05050505,
    0x06060606,
    0xF8F8F8F8,
    0x07070707,
    0xF9F9F9F9,
    0xFAFAFAFA,
    0xFBFBFBFB,
    0xFCFCFCFC,
    0xFDFDFDFD,
    0xFEFEFEFE,
    0xFFFFFFFF
};

// For 4bpp, no translation is necessary.
ULONG ulNibbleTo4bppDword[16] = {
    0x00000000,
    0x01010101,
    0x02020202,
    0x03030303,
    0x04040404,
    0x05050505,
    0x06060606,
    0x07070707,
    0x08080808,
    0x09090909,
    0x0A0A0A0A,
    0x0B0B0B0B,
    0x0C0C0C0C,
    0x0D0D0D0D,
    0x0E0E0E0E,
    0x0F0F0F0F
};


// Specifies where in the dither pattern colors should be placed in order
// of increasing intensity.

// 8bpp specific version.
ULONG aulDither8bppOrder[] = {
  0, 36,  4, 32, 18, 54, 22, 50,
  2, 38,  6, 34, 16, 52, 20, 48,
  9, 45, 13, 41, 27, 63, 31, 59,
 11, 47, 15, 43, 25, 61, 29, 57,
  1, 37,  5, 33, 19, 55, 23, 51,
  3, 39,  7, 35, 17, 53, 21, 49,
  8, 44, 12, 40, 26, 62, 30, 58,
 10, 46, 14, 42, 24, 60, 28, 56,
};

// 4bpp specific version. This is organized in the following form, for
// efficiency: every set of 8 pixels (0-7, 8-15, 16-23, ... ,56-63) is
// placed in the dither pattern in the order: 0 2 4 6 1 3 5 7. This is
// done so that two longs can be combined to put 8 pixels in DIB4 format
// at once (the first dword is shifted left 4, then the two dwords are
// ORed, to produce 0 1 2 3 4 5 6 7 order in memory), which is much faster than
// combining the output of the straight dither ordering.
// The effective dither ordering after we combine each pair of ULONGS at the
// end (the desired dither ordering) matches aulDither8bppOrder (see above).
//
ULONG aulDither4bppOrder[] = {
  0, 34,  2, 32, 17, 51, 19, 49,
  1, 35,  3, 33, 16, 50, 18, 48,
 12, 46, 14, 44, 29, 63, 31, 61,
 13, 47, 15, 45, 28, 62, 30, 60,
  4, 38,  6, 36, 21, 55, 23, 53,
  5, 39,  7, 37, 20, 54, 22, 52,
  8, 42, 10, 40, 25, 59, 27, 57,
  9, 43, 11, 41, 24, 58, 26, 56,
};


// Array to convert to 256 color from 16 color. Maps from index that represents
// a 16-color vertex (color) to value that specifies the color index in the
// 256-color palette.
BYTE ajConvert[] =
{
    0,
    1,
    2,
    3,
    4,
    5,
    6,
    248,
    7,
    249,
    250,
    251,
    252,
    253,
    254,
    255
};

// Describes a single colour tetrahedron vertex for dithering:
typedef struct _VERTEX_DATA {
    ULONG ulCount;              // Number of pixels in this vertex
    ULONG ulVertex;             // Vertex number
} VERTEX_DATA;                      /* vd, pv */

VERTEX_DATA*    vComputeSubspaces(ULONG, VERTEX_DATA*);
VOID            vDitherColor8bpp(ULONG*, VERTEX_DATA*, VERTEX_DATA*, ULONG);
VOID            vDitherColor4bpp(ULONG*, VERTEX_DATA*, VERTEX_DATA*, ULONG);

/******************************Public*Routine******************************\
* vComputeSubspaces
*
* Calculates the subspace data associated with rgb, stores the data at
* pvVertexData, in the form of an array of VERTEX_DATA structures,
* suitable for vDitherColor. Returns a pointer to the byte after the
* last VERTEX_DATA structure.
*
* Ignores the high byte of rgb.
*
\**************************************************************************/

VERTEX_DATA* vComputeSubspaces(
ULONG           rgb,
VERTEX_DATA*    pvVertexData)
{
    ULONG   ulRedTemp, ulGreenTemp, ulBlueTemp, ulSymmetry;
    ULONG   ulRed, ulGre, ulBlu, ulTemp;
    ULONG   ulVertex0Temp, ulVertex1Temp, ulVertex2Temp, ulVertex3Temp;

    // Split the color into red, green, and blue components
    ulRedTemp   = ((PAL_ULONG *)&rgb)->pal.peRed;
    ulGreenTemp   = ((PAL_ULONG *)&rgb)->pal.peGreen;
    ulBlueTemp   = ((PAL_ULONG *)&rgb)->pal.peBlue;

    // Sort the RGB so that the point is transformed into subspace 0, and
    // keep track of the swaps in ulSymmetry so we can unravel it again
    // later.  We want r >= g >= b (subspace 0).
    ulSymmetry = 0;
    if (ulBlueTemp > ulRedTemp) {
        SWAPTHEM(ulBlueTemp,ulRedTemp);
        ulSymmetry = SWAP_RB;
    }

    if (ulBlueTemp > ulGreenTemp) {
        SWAPTHEM(ulBlueTemp,ulGreenTemp);
        ulSymmetry |= SWAP_GB;
    }

    if (ulGreenTemp > ulRedTemp) {
        SWAPTHEM(ulGreenTemp,ulRedTemp);
        ulSymmetry |= SWAP_RG;
    }

    ulSymmetry <<= 4;   // for lookup purposes

    // Scale the values from 0-255 to 0-64. Note that the scaling is not
    // symmetric at the ends; this is done to match Windows 3.1 dithering
    ulRed = (ulRedTemp + 1) >> 2;
    ulGre = (ulGreenTemp + 1) >> 2;
    ulBlu = (ulBlueTemp + 1) >> 2;

    // Compute the subsubspace within subspace 0 in which the point lies,
    // then calculate the # of pixels to dither in the colors that are the
    // four vertexes of the tetrahedron bounding the color we're emulating.
    // Only vertices with more than zero pixels are stored, and the
    // vertices are stored in order of increasing intensity, saving us the
    // need to sort them later
    if ((ulRedTemp + ulGreenTemp) > 256) {
        // Subsubspace 2 or 3
        if ((ulRedTemp + ulBlueTemp) > 256) {
            // Subsubspace 3
            // Calculate the number of pixels per vertex, still in
            // subsubspace 3, then convert to original subspace. The pixel
            // counts and vertex numbers are matching pairs, stored in
            // ascending intensity order, skipping vertices with zero
            // pixels. The vertex intensity order for subsubspace 3 is:
            // 7, 9, 0x0B, 0x0F
            if ((ulVertex0Temp = (64 - ulRed) << 1) != 0) {
                pvVertexData->ulCount = ulVertex0Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x07];
            }
            ulVertex2Temp = ulGre - ulBlu;
            ulVertex3Temp = (ulRed - 64) + ulBlu;
            if ((ulVertex1Temp = ((PATTERNSIZE - ulVertex0Temp) -
                    ulVertex2Temp) - ulVertex3Temp) != 0) {
                pvVertexData->ulCount = ulVertex1Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x09];
            }
            if (ulVertex2Temp != 0) {
                pvVertexData->ulCount = ulVertex2Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x0B];
            }
            if (ulVertex3Temp != 0) {
                pvVertexData->ulCount = ulVertex3Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x0F];
            }
        } else {
            // Subsubspace 2
            // Calculate the number of pixels per vertex, still in
            // subsubspace 2, then convert to original subspace. The pixel
            // counts and vertex numbers are matching pairs, stored in
            // ascending intensity order, skipping vertices with zero
            // pixels. The vertex intensity order for subsubspace 2 is:
            // 3, 7, 9, 0x0B
            ulVertex1Temp = ulBlu << 1;
            ulVertex2Temp = ulRed - ulGre;
            ulVertex3Temp = (ulRed - 32) + (ulGre - 32);
            if ((ulVertex0Temp = ((PATTERNSIZE - ulVertex1Temp) -
                        ulVertex2Temp) - ulVertex3Temp) != 0) {
                pvVertexData->ulCount = ulVertex0Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x03];
            }
            if (ulVertex1Temp != 0) {
                pvVertexData->ulCount = ulVertex1Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x07];
            }
            if (ulVertex2Temp != 0) {
                pvVertexData->ulCount = ulVertex2Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x09];
            }
            if (ulVertex3Temp != 0) {
                pvVertexData->ulCount = ulVertex3Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x0B];
            }
        }
    } else {
        // Subsubspace 0 or 1
        if (ulRedTemp > 128) {
            // Subsubspace 1
            // Calculate the number of pixels per vertex, still in
            // subsubspace 1, then convert to original subspace. The pixel
            // counts and vertex numbers are matching pairs, stored in
            // ascending intensity order, skipping vertices with zero
            // pixels. The vertex intensity order for subsubspace 1 is:
            // 1, 3, 7, 9
            if ((ulVertex0Temp = ((32 - ulGre) + (32 - ulRed)) << 1) != 0) {
                pvVertexData->ulCount = ulVertex0Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x01];
            }
            ulVertex2Temp = ulBlu << 1;
            ulVertex3Temp = (ulRed - 32) << 1;
            if ((ulVertex1Temp = ((PATTERNSIZE - ulVertex0Temp) -
                    ulVertex2Temp) - ulVertex3Temp) != 0) {
                pvVertexData->ulCount = ulVertex1Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x03];
            }
            if (ulVertex2Temp != 0) {
                pvVertexData->ulCount = ulVertex2Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x07];
            }
            if (ulVertex3Temp != 0) {
                pvVertexData->ulCount = ulVertex3Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x09];
            }
        } else {
            // Subsubspace 0
            // Calculate the number of pixels per vertex, still in
            // subsubspace 0, then convert to original subspace. The pixel
            // counts and vertex numbers are matching pairs, stored in
            // ascending intensity order, skipping vertices with zero
            // pixels. The vertex intensity order for subsubspace 0 is:
            // 0, 1, 3, 7
            if ((ulVertex0Temp = (32 - ulRed) << 1) != 0) {
                pvVertexData->ulCount = ulVertex0Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x00];
            }
            if ((ulVertex1Temp = (ulRed - ulGre) << 1) != 0) {
                pvVertexData->ulCount = ulVertex1Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x01];
            }
            ulVertex3Temp = ulBlu << 1;
            if ((ulVertex2Temp = ((PATTERNSIZE - ulVertex0Temp) -
                    ulVertex1Temp) - ulVertex3Temp) != 0) {
                pvVertexData->ulCount = ulVertex2Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x03];
            }
            if (ulVertex3Temp != 0) {
                pvVertexData->ulCount = ulVertex3Temp;
                pvVertexData++->ulVertex = jSwapSubSpace[ulSymmetry + 0x07];
            }
        }
    }

    return(pvVertexData);
}

/******************************Public*Routine******************************\
* vDitherColor8bpp
*
* Dithers the ulNumVertices vertices described by vVertexData into pulDest.
*
\**************************************************************************/

VOID vDitherColor8bpp(
ULONG*          pulDest,
VERTEX_DATA*    vVertexData,
VERTEX_DATA*    pvVertexDataEnd,
ULONG           ulNumVertices)
{
    ULONG ulTemp, ulNumPixels, ulColor;
    VERTEX_DATA *pvMaxVertex, *pvVertexData;
    ULONG  *pulDitherOrder;
    BYTE    jColor;
    BYTE   *pjDither = (BYTE *)pulDest;

    if (ulNumVertices > 2) {

        // There are 3 or 4 vertices in this dither
        if (ulNumVertices == 3) {

            // There are 3 vertices in this dither

            // Find the vertex with the most pixels, and fill the whole
            // destination bitmap with that vertex's color, which is faster
            // than dithering it
            if (vVertexData[1].ulCount >= vVertexData[2].ulCount) {
                pvMaxVertex = &vVertexData[1];
                ulTemp = vVertexData[1].ulCount;
            } else {
                pvMaxVertex = &vVertexData[2];
                ulTemp = vVertexData[2].ulCount;
            }

        } else {

            // There are 4 vertices in this dither

            // Find the vertex with the most pixels, and fill the whole
            // destination bitmap with that vertex's color, which is faster
            // than dithering it
            if (vVertexData[2].ulCount >= vVertexData[3].ulCount) {
                pvMaxVertex = &vVertexData[2];
                ulTemp = vVertexData[2].ulCount;
            } else {
                pvMaxVertex = &vVertexData[3];
                ulTemp = vVertexData[3].ulCount;
            }
        }

        if (vVertexData[1].ulCount > ulTemp) {
            pvMaxVertex = &vVertexData[1];
            ulTemp = vVertexData[1].ulCount;
        }
        if (vVertexData[0].ulCount > ulTemp) {
            pvMaxVertex = &vVertexData[0];
        }

        // Prepare a dword version of the most common vertex number (color)
        ulColor = ulNibbleTo8bppDword[pvMaxVertex->ulVertex];

        // Mark that the vertex we're about to do doesn't need to be done
        // later
        pvMaxVertex->ulVertex = 0xFF;

        // Block fill the dither pattern with the more common vertex
        *pulDest = ulColor;
        *(pulDest+1) = ulColor;
        *(pulDest+2) = ulColor;
        *(pulDest+3) = ulColor;
        *(pulDest+4) = ulColor;
        *(pulDest+5) = ulColor;
        *(pulDest+6) = ulColor;
        *(pulDest+7) = ulColor;
        *(pulDest+8) = ulColor;
        *(pulDest+9) = ulColor;
        *(pulDest+10) = ulColor;
        *(pulDest+11) = ulColor;
        *(pulDest+12) = ulColor;
        *(pulDest+13) = ulColor;
        *(pulDest+14) = ulColor;
        *(pulDest+15) = ulColor;

        // Now dither all the remaining vertices in order 0->2 or 0->3
        // (in order of increasing intensity)
        pulDitherOrder = aulDither8bppOrder;
        pvVertexData = vVertexData;
        do {
            if (pvVertexData->ulVertex == 0xFF) {
                // This is the max vertex, which we already did, but we
                // have to account for it in the dither order
                pulDitherOrder += pvVertexData->ulCount;
            } else {
                jColor = (BYTE) ajConvert[pvVertexData->ulVertex];
                ulNumPixels = pvVertexData->ulCount;
                switch (ulNumPixels & 3) {
                    case 3:
                        pjDither[*(pulDitherOrder+2)] = jColor;
                    case 2:
                        pjDither[*(pulDitherOrder+1)] = jColor;
                    case 1:
                        pjDither[*(pulDitherOrder+0)] = jColor;
                        pulDitherOrder += ulNumPixels & 3;
                    case 0:
                        break;
                }
                if ((ulNumPixels >>= 2) != 0) {
                    do {
                        pjDither[*pulDitherOrder] = jColor;
                        pjDither[*(pulDitherOrder+1)] = jColor;
                        pjDither[*(pulDitherOrder+2)] = jColor;
                        pjDither[*(pulDitherOrder+3)] = jColor;
                        pulDitherOrder += 4;
                    } while (--ulNumPixels);
                }
            }
        } while (++pvVertexData < pvVertexDataEnd);

    } else if (ulNumVertices == 2) {

        // There are exactly two vertices with more than zero pixels; fill
        // in the dither array as follows: block fill with vertex with more
        // points first, then dither in the other vertex
        if (vVertexData[0].ulCount >= vVertexData[1].ulCount) {
            // There are no more vertex 1 than vertex 0 pixels, so do
            // the block fill with vertex 0
            ulColor = ulNibbleTo8bppDword[vVertexData[0].ulVertex];
            // Do the dither with vertex 1
            jColor = (BYTE) ajConvert[vVertexData[1].ulVertex];
            ulNumPixels = vVertexData[1].ulCount;
            // Set where to start dithering with vertex 1 (vertex 0 is
            // lower intensity, so its pixels come first in the dither
            // order)
            pulDitherOrder = aulDither8bppOrder + vVertexData[0].ulCount;
        } else {
            // There are more vertex 1 pixels, so do the block fill
            // with vertex 1
            ulColor = ulNibbleTo8bppDword[vVertexData[1].ulVertex];
            // Do the dither with vertex 0
            jColor = (BYTE) ajConvert[vVertexData[0].ulVertex];
            ulNumPixels = vVertexData[0].ulCount;
            // Set where to start dithering with vertex 0 (vertex 0 is
            // lower intensity, so its pixels come first in the dither
            // order)
            pulDitherOrder = aulDither8bppOrder;
        }

        // Block fill the dither pattern with the more common vertex
        *pulDest = ulColor;
        *(pulDest+1) = ulColor;
        *(pulDest+2) = ulColor;
        *(pulDest+3) = ulColor;
        *(pulDest+4) = ulColor;
        *(pulDest+5) = ulColor;
        *(pulDest+6) = ulColor;
        *(pulDest+7) = ulColor;
        *(pulDest+8) = ulColor;
        *(pulDest+9) = ulColor;
        *(pulDest+10) = ulColor;
        *(pulDest+11) = ulColor;
        *(pulDest+12) = ulColor;
        *(pulDest+13) = ulColor;
        *(pulDest+14) = ulColor;
        *(pulDest+15) = ulColor;

        // Dither in the less common vertex
        switch (ulNumPixels & 3) {
            case 3:
                pjDither[*(pulDitherOrder+2)] = jColor;
            case 2:
                pjDither[*(pulDitherOrder+1)] = jColor;
            case 1:
                pjDither[*(pulDitherOrder+0)] = jColor;
                pulDitherOrder += ulNumPixels & 3;
            case 0:
                break;
        }
        if ((ulNumPixels >>= 2) != 0) {
            do {
                pjDither[*pulDitherOrder] = jColor;
                pjDither[*(pulDitherOrder+1)] = jColor;
                pjDither[*(pulDitherOrder+2)] = jColor;
                pjDither[*(pulDitherOrder+3)] = jColor;
                pulDitherOrder += 4;
            } while (--ulNumPixels);
        }

    } else {

        // There is only one vertex in this dither

        // No sorting or dithering is needed for just one color; we can
        // just generate the final DIB directly
        ulColor = ulNibbleTo8bppDword[vVertexData[0].ulVertex];
        *pulDest = ulColor;
        *(pulDest+1) = ulColor;
        *(pulDest+2) = ulColor;
        *(pulDest+3) = ulColor;
        *(pulDest+4) = ulColor;
        *(pulDest+5) = ulColor;
        *(pulDest+6) = ulColor;
        *(pulDest+7) = ulColor;
        *(pulDest+8) = ulColor;
        *(pulDest+9) = ulColor;
        *(pulDest+10) = ulColor;
        *(pulDest+11) = ulColor;
        *(pulDest+12) = ulColor;
        *(pulDest+13) = ulColor;
        *(pulDest+14) = ulColor;
        *(pulDest+15) = ulColor;
    }
}


/******************************Public*Routine******************************\
* vDitherColor4bpp
*
* Dithers the ulNumVertices vertices described by vVertexData into pulDest.
*
\**************************************************************************/

VOID vDitherColor4bpp(
    ULONG * pulDest,
    VERTEX_DATA * vVertexData,
    VERTEX_DATA * pvVertexDataEnd,
    ULONG ulNumVertices)
{
    ULONG ulTemp, ulNumPixels, ulColor;
    VERTEX_DATA *pvMaxVertex, *pvVertexData;
    ULONG  *pulTemp, *pulDitherOrder;
    BYTE    jColor;
    BYTE    ajDither[64];

    if (ulNumVertices > 2) {

        // There are 3 or 4 vertices in this dither
        if (ulNumVertices == 3) {

            // There are 3 vertices in this dither

            // Find the vertex with the most pixels, and fill the whole
            // destination bitmap with that vertex's color, which is faster
            // than dithering it
            if (vVertexData[1].ulCount >= vVertexData[2].ulCount) {
                pvMaxVertex = &vVertexData[1];
                ulTemp = vVertexData[1].ulCount;
            } else {
                pvMaxVertex = &vVertexData[2];
                ulTemp = vVertexData[2].ulCount;
            }

        } else {

            // There are 4 vertices in this dither

            // Find the vertex with the most pixels, and fill the whole
            // destination bitmap with that vertex's color, which is faster
            // than dithering it
            if (vVertexData[2].ulCount >= vVertexData[3].ulCount) {
                pvMaxVertex = &vVertexData[2];
                ulTemp = vVertexData[2].ulCount;
            } else {
                pvMaxVertex = &vVertexData[3];
                ulTemp = vVertexData[3].ulCount;
            }
        }

        if (vVertexData[1].ulCount > ulTemp) {
            pvMaxVertex = &vVertexData[1];
            ulTemp = vVertexData[1].ulCount;
        }
        if (vVertexData[0].ulCount > ulTemp) {
            pvMaxVertex = &vVertexData[0];
        }

        // Prepare a dword version of the most common vertex number (color)
        ulColor = ulNibbleTo4bppDword[pvMaxVertex->ulVertex];

        // Mark that the vertex we're about to do doesn't need to be done
        // later
        pvMaxVertex->ulVertex = 0xFF;

        // Block fill the dither pattern with the more common vertex
        pulTemp = (ULONG *)ajDither;
        *pulTemp = ulColor;
        *(pulTemp+1) = ulColor;
        *(pulTemp+2) = ulColor;
        *(pulTemp+3) = ulColor;
        *(pulTemp+4) = ulColor;
        *(pulTemp+5) = ulColor;
        *(pulTemp+6) = ulColor;
        *(pulTemp+7) = ulColor;
        *(pulTemp+8) = ulColor;
        *(pulTemp+9) = ulColor;
        *(pulTemp+10) = ulColor;
        *(pulTemp+11) = ulColor;
        *(pulTemp+12) = ulColor;
        *(pulTemp+13) = ulColor;
        *(pulTemp+14) = ulColor;
        *(pulTemp+15) = ulColor;

        // Now dither all the remaining vertices in order 0->2 or 0->3
        // (in order of increasing intensity)
        pulDitherOrder = aulDither4bppOrder;
        pvVertexData = vVertexData;
        do {
            if (pvVertexData->ulVertex == 0xFF) {
                // This is the max vertex, which we already did, but we
                // have to account for it in the dither order
                pulDitherOrder += pvVertexData->ulCount;
            } else {
                jColor = (BYTE) pvVertexData->ulVertex;
                ulNumPixels = pvVertexData->ulCount;
                switch (ulNumPixels & 3) {
                    case 3:
                        ajDither[*(pulDitherOrder+2)] = jColor;
                    case 2:
                        ajDither[*(pulDitherOrder+1)] = jColor;
                    case 1:
                        ajDither[*(pulDitherOrder+0)] = jColor;
                        pulDitherOrder += ulNumPixels & 3;
                    case 0:
                        break;
                }
                if ((ulNumPixels >>= 2) != 0) {
                    do {
                        ajDither[*pulDitherOrder] = jColor;
                        ajDither[*(pulDitherOrder+1)] = jColor;
                        ajDither[*(pulDitherOrder+2)] = jColor;
                        ajDither[*(pulDitherOrder+3)] = jColor;
                        pulDitherOrder += 4;
                    } while (--ulNumPixels);
                }
            }
        } while (++pvVertexData < pvVertexDataEnd);

    } else if (ulNumVertices == 2) {

        // There are exactly two vertices with more than zero pixels; fill
        // in the dither array as follows: block fill with vertex with more
        // points first, then dither in the other vertex
        if (vVertexData[0].ulCount >= vVertexData[1].ulCount) {
            // There are no more vertex 1 than vertex 0 pixels, so do
            // the block fill with vertex 0
            ulColor = ulNibbleTo4bppDword[vVertexData[0].ulVertex];
            // Do the dither with vertex 1
            jColor = (BYTE) vVertexData[1].ulVertex;
            ulNumPixels = vVertexData[1].ulCount;
            // Set where to start dithering with vertex 1 (vertex 0 is
            // lower intensity, so its pixels come first in the dither
            // order)
            pulDitherOrder = aulDither4bppOrder + vVertexData[0].ulCount;
        } else {
            // There are more vertex 1 pixels, so do the block fill
            // with vertex 1
            ulColor = ulNibbleTo4bppDword[vVertexData[1].ulVertex];
            // Do the dither with vertex 0
            jColor = (BYTE) vVertexData[0].ulVertex;
            ulNumPixels = vVertexData[0].ulCount;
            // Set where to start dithering with vertex 0 (vertex 0 is
            // lower intensity, so its pixels come first in the dither
            // order)
            pulDitherOrder = aulDither4bppOrder;
        }

        // Block fill the dither pattern with the more common vertex
        pulTemp = (ULONG *)ajDither;
        *pulTemp = ulColor;
        *(pulTemp+1) = ulColor;
        *(pulTemp+2) = ulColor;
        *(pulTemp+3) = ulColor;
        *(pulTemp+4) = ulColor;
        *(pulTemp+5) = ulColor;
        *(pulTemp+6) = ulColor;
        *(pulTemp+7) = ulColor;
        *(pulTemp+8) = ulColor;
        *(pulTemp+9) = ulColor;
        *(pulTemp+10) = ulColor;
        *(pulTemp+11) = ulColor;
        *(pulTemp+12) = ulColor;
        *(pulTemp+13) = ulColor;
        *(pulTemp+14) = ulColor;
        *(pulTemp+15) = ulColor;

        // Dither in the less common vertex
        switch (ulNumPixels & 3) {
            case 3:
                ajDither[*(pulDitherOrder+2)] = jColor;
            case 2:
                ajDither[*(pulDitherOrder+1)] = jColor;
            case 1:
                ajDither[*(pulDitherOrder+0)] = jColor;
                pulDitherOrder += ulNumPixels & 3;
            case 0:
                break;
        }
        if ((ulNumPixels >>= 2) != 0) {
            do {
                ajDither[*pulDitherOrder] = jColor;
                ajDither[*(pulDitherOrder+1)] = jColor;
                ajDither[*(pulDitherOrder+2)] = jColor;
                ajDither[*(pulDitherOrder+3)] = jColor;
                pulDitherOrder += 4;
            } while (--ulNumPixels);
        }

    } else {

        // There is only one vertex in this dither

        // No sorting or dithering is needed for just one color; we can
        // just generate the final DIB directly
        ulColor = ulNibbleTo4bppDword[vVertexData[0].ulVertex];
        ulColor |= ulColor << 4;
        *pulDest = ulColor;
        *(pulDest+1) = ulColor;
        *(pulDest+2) = ulColor;
        *(pulDest+3) = ulColor;
        *(pulDest+4) = ulColor;
        *(pulDest+5) = ulColor;
        *(pulDest+6) = ulColor;
        *(pulDest+7) = ulColor;

        return;
    }

    // Now convert the 64 bytes into the 4BPP Engine Format Bitmap
    pulTemp = (ULONG *)ajDither;

    *pulDest = (*pulTemp << 4) | *(pulTemp + 1);
    *(pulDest + 1) = (*(pulTemp + 2) << 4) | *(pulTemp + 3);
    *(pulDest + 2) = (*(pulTemp + 4) << 4) | *(pulTemp + 5);
    *(pulDest + 3) = (*(pulTemp + 6) << 4) | *(pulTemp + 7);
    *(pulDest + 4) = (*(pulTemp + 8) << 4) | *(pulTemp + 9);
    *(pulDest + 5) = (*(pulTemp + 10) << 4) | *(pulTemp + 11);
    *(pulDest + 6) = (*(pulTemp + 12) << 4) | *(pulTemp + 13);
    *(pulDest + 7) = (*(pulTemp + 14) << 4) | *(pulTemp + 15);
}


/******************************Public*Routine******************************\
* EngDitherColor
*
* Dithers an RGB color to an 8X8 approximation using the reserved VGA
* colours.
*
\**************************************************************************/

ULONG EngDitherColor(
HDEV    hdev, 
ULONG   iMode,
ULONG   rgb,
ULONG*  pul)
{
    ULONG   ulGrey, ulRed, ulGre, ulBlu, ulTemp, ulRet;
    VERTEX_DATA vVertexData[4];
    VERTEX_DATA *pvVertexData;
    PDEVOBJ po(hdev);

    ulRet = DCR_SOLID;

    // We handle only 8x8 dithers.  If the driver has their value set to
    // something else, we have to bail.

    if ((po.cxDither() != 8) || (po.cyDither() != 8))
    {
        WARNING("EngDitherColor works only when driver sets its DEVINFO");
        WARNING("cxDither and cyDither values to 8");
    }
    else
    {
        // Figure out if we need a full color dither or only a monochrome dither.
    
        // Note: we should get color dithers only at 8bpp and 4bpp, because
        //       those are the only color depths at which drivers should
        //       set GCAPS_COLOR_DITHER.
    
        if (iMode != DM_MONOCHROME)
        {
            // We only handle 8bpp and 4bpp color dithers:
    
            if (po.iDitherFormat() == BMF_8BPP ||
                po.iDitherFormat() == BMF_4BPP)
            {
                // Full color dither
        
                // Calculate what color subspaces are involved in the dither
                pvVertexData = vComputeSubspaces(rgb, vVertexData);
        
                // Now that we have found the bounding vertices and the number of
                // pixels to dither for each vertex, we can create the dither pattern
        
                // Handle 1, 2, and 3 & 4 vertices per dither separately
                ulTemp = (ULONG) (pvVertexData - vVertexData);    
                                                        // # of vertices with more than
                                                        //  zero pixels in the dither
        
                if (po.iDitherFormat() == BMF_8BPP)
                {
                    vDitherColor8bpp(pul, vVertexData, pvVertexData, ulTemp);
                }
                else
                {
                    vDitherColor4bpp(pul, vVertexData, pvVertexData, ulTemp);
                }
        
                ulRet = DCR_DRIVER;
            }
            else
            {
                WARNING("EngDitherColor works for DM_DEFAULT only when at 8bpp or 4bpp");
            }
        }
        else
        {
            // Note: we can get monochrome dithers at any colour depth because
            //       we always set GCAPS_MONO_DITHER.
    
            // For monochrome we will only use the Intensity (grey level)
    
            RtlFillMemory((PVOID) pul, PATTERNSIZE/2, 0);  // zero the dither bits
    
            ulRed   = (ULONG) ((PALETTEENTRY *) &rgb)->peRed;
            ulGre = (ULONG) ((PALETTEENTRY *) &rgb)->peGreen;
            ulBlu  = (ULONG) ((PALETTEENTRY *) &rgb)->peBlue;
    
            // I = .30R + .59G + .11B
            // For convience the following ratios are used:
            //
            //  77/256 = 30.08%
            // 151/256 = 58.98%
            //  28/256 = 10.94%
    
            ulGrey  = (((ulRed * 77) + (ulGre * 151) + (ulBlu * 28)) >> 8) & 255;
    
            // Convert the RGBI from 0-255 to 0-64 notation.
    
            ulGrey = (ulGrey + 1) >> 2;
    
            while(ulGrey) {
                ulGrey--;
                pul[ajByte[ulGrey]] |= ((ULONG) ajBits[ulGrey]);
            }
    
            ulRet = DCR_DRIVER;
        }
    }

    return(ulRet);
}