subsystems/win32/win32k/dib/floodfill.c

   1 /*
   2 * COPYRIGHT:         See COPYING in the top level directory
   3 * PROJECT:           ReactOS win32 subsystem
   4 * PURPOSE:           Flood filling support
   5 * FILE:              subsystems/win32/win32k/dib/floodfill.c
   6 * PROGRAMMER:        Gregor Schneider, <grschneider AT gmail DOT com>
   7 */
   8
   9 #include <win32k.h>
  10
  11 #define NDEBUG
  12 #include <debug.h>
  13
  14 /*
  15 *  This floodfill algorithm is an iterative four neighbors version. It works with an internal stack like data structure.
  16 *  The stack is kept in an array, sized for the worst case scenario of having to add all pixels of the surface.
  17 *  This avoids having to allocate and free memory blocks  all the time. The stack grows from the end of the array towards the start.
  18 *  All pixels are checked before being added, against belonging to the fill rule (FLOODFILLBORDER or FLOODFILLSURFACE)
  19 *  and the position in respect to the clip region. This guarantees all pixels lying on the stack belong to the filled surface.
  20 *  Further optimisations of the algorithm are possible.
  21 */
  22
  23 /* Floodfil helper structures and functions */
  24 typedef struct _floodItem
  25 {
  26   ULONG x;
  27   ULONG y;
  28 } FLOODITEM;
  29
  30 typedef struct _floodInfo
  31 {
  32   ULONG floodLen;
  33   FLOODITEM *floodStart;
  34   FLOODITEM *floodData;
  35 } FLOODINFO;
  36
  37 static __inline BOOL initFlood(FLOODINFO *info, RECTL *DstRect)
  38 {
  39   ULONG width = DstRect->right - DstRect->left;
  40   ULONG height = DstRect->bottom - DstRect->top;
  41   info->floodData = ExAllocatePoolWithTag(NonPagedPool, width * height * sizeof(FLOODITEM), TAG_DIB);
  42   if (info->floodData == NULL)
  43   {
  44     return FALSE;
  45   }
  46   info->floodStart = info->floodData + (width * height);
  47   DPRINT("Allocated flood stack from %p to %p\n", info->floodData, info->floodStart);
  48   return TRUE;
  49 }
  50 static __inline VOID finalizeFlood(FLOODINFO *info)
  51 {
  52   ExFreePoolWithTag(info->floodData, TAG_DIB);
  53 }
  54 static __inline VOID addItemFlood(FLOODINFO *info,
  55                                   ULONG x,
  56                                   ULONG y,
  57                                   SURFOBJ *DstSurf,
  58                                   RECTL *DstRect,
  59                                   ULONG Color,
  60                                   BOOL isSurf)
  61 {
  62   if (x >= DstRect->left && x <= DstRect->right &&
  63     y >= DstRect->top && y <= DstRect->bottom)
  64   {
  65     if (isSurf == TRUE &&
  66       DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y) != Color)
  67     {
  68       return;
  69     }
  70     else if (isSurf == FALSE &&
  71       DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y) == Color)
  72     {
  73       return;
  74     }
  75     info->floodStart--;
  76     info->floodStart->x = x;
  77     info->floodStart->y = y;
  78     info->floodLen++;
  79   }
  80 }
  81 static __inline VOID removeItemFlood(FLOODINFO *info)
  82 {
  83   info->floodStart++;
  84   info->floodLen--;
  85 }
  86
  87 BOOLEAN DIB_XXBPP_FloodFillSolid(SURFOBJ *DstSurf,
  88                                  BRUSHOBJ *Brush,
  89                                  RECTL *DstRect,
  90                                  POINTL *Origin,
  91                                  ULONG ConvColor,
  92                                  UINT FillType)
  93 {
  94   ULONG x, y;
  95   ULONG BrushColor;
  96   FLOODINFO flood = {0, NULL, NULL};
  97
  98   BrushColor = Brush->iSolidColor;
  99   x = Origin->x;
 100   y = Origin->y;
 101
 102   if (FillType == FLOODFILLBORDER)
 103   {
 104     /* Check if the start pixel has the border color */
 105     if (DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y) == ConvColor)
 106     {
 107       return FALSE;
 108     }
 109
 110     if (initFlood(&flood, DstRect) == FALSE)
 111     {
 112       return FALSE;
 113     }
 114     addItemFlood(&flood, x, y, DstSurf, DstRect, ConvColor, FALSE);
 115     while (flood.floodLen != 0)
 116     {
 117       x = flood.floodStart->x;
 118       y = flood.floodStart->y;
 119       removeItemFlood(&flood);
 120
 121       DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_PutPixel(DstSurf, x, y, BrushColor);
 122       if (flood.floodStart - 4 < flood.floodData)
 123       {
 124         DPRINT1("Can't finish flooding!\n");
 125         finalizeFlood(&flood);
 126         return FALSE;
 127       }
 128       addItemFlood(&flood, x, y + 1, DstSurf, DstRect, ConvColor, FALSE);
 129       addItemFlood(&flood, x, y - 1, DstSurf, DstRect, ConvColor, FALSE);
 130       addItemFlood(&flood, x + 1, y, DstSurf, DstRect, ConvColor, FALSE);
 131       addItemFlood(&flood, x - 1, y, DstSurf, DstRect, ConvColor, FALSE);
 132     }
 133     finalizeFlood(&flood);
 134   }
 135   else if (FillType == FLOODFILLSURFACE)
 136   {
 137     /* Check if the start pixel has the surface color */
 138     if (DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_GetPixel(DstSurf, x, y) != ConvColor)
 139     {
 140       return FALSE;
 141     }
 142
 143     if (initFlood(&flood, DstRect) == FALSE)
 144     {
 145       return FALSE;
 146     }
 147     addItemFlood(&flood, x, y, DstSurf, DstRect, ConvColor, TRUE);
 148     while (flood.floodLen != 0)
 149     {
 150       x = flood.floodStart->x;
 151       y = flood.floodStart->y;
 152       removeItemFlood(&flood);
 153
 154       DibFunctionsForBitmapFormat[DstSurf->iBitmapFormat].DIB_PutPixel(DstSurf, x, y, BrushColor);
 155       if (flood.floodStart - 4 < flood.floodData)
 156       {
 157         DPRINT1("Can't finish flooding!\n");
 158         finalizeFlood(&flood);
 159         return FALSE;
 160       }
 161       addItemFlood(&flood, x, y + 1, DstSurf, DstRect, ConvColor, TRUE);
 162       addItemFlood(&flood, x, y - 1, DstSurf, DstRect, ConvColor, TRUE);
 163       addItemFlood(&flood, x + 1, y, DstSurf, DstRect, ConvColor, TRUE);
 164       addItemFlood(&flood, x - 1, y, DstSurf, DstRect, ConvColor, TRUE);
 165     }
 166     finalizeFlood(&flood);
 167   }
 168   else
 169   {
 170     DPRINT1("Unsupported FloodFill type!\n");
 171     return FALSE;
 172   }
 173   return TRUE;
 174 }