16/xlib/xfill.asm

   1 ;-----------------------------------------------------------------------\r
   2 ; MODULE XFILL\r
   3 ;\r
   4 ; Point functions all MODE X 256 Color resolutions\r
   5 ;\r
   6 ; Compile with Tasm.\r
   7 ; C callable.\r
   8 ;\r
   9 ;\r
  10 ; ****** XLIB - Mode X graphics library                ****************\r
  11 ; ******                                               ****************\r
  12 ; ****** Written By Themie Gouthas                     ****************\r
  13 ;\r
  14 ; egg@dstos3.dsto.gov.au\r
  15 ; teg@bart.dsto.gov.au\r
  16 ;-----------------------------------------------------------------------\r
  17 \r
  18 COMMENT $\r
  19 \r
  20   This code is my interpretation of a simple "C" flood filling algorithm\r
  21   titled:\r
  22 \r
  23   * A Seed Fill Algorithm\r
  24   * by Paul Heckbert\r
  25   * from "Graphics Gems", Academic Press, 1990\r
  26 \r
  27   The original C source is readily available at numerous internet archive\r
  28   sites.\r
  29 \r
  30   Its been modified and optimized for tweaked 13h modes (Mode X derrivatives).\r
  31   The most fundamental change is that it fills a column at a time rather\r
  32   than a row at a time to minimize the number of plane setting "out"s.\r
  33   And of course the border fill variant was a logical and useful further\r
  34   modification.\r
  35 \r
  36   Both functions return the number of pixels filled..\r
  37 \r
  38   WARNING: These fill functions make heavy use of the stack and no stack\r
  39     checking is performed, so caution is advised.\r
  40 \r
  41 $\r
  42 \r
  43 \r
  44 include xlib.inc\r
  45 include xfill.inc\r
  46 \r
  47         .code\r
  48 \r
  49 _x_flood_fill  proc\r
  50         ARG X:word,Y:word,PgOfs:word,Color:word\r
  51         LOCAL len:word,y1:word,y2:word,deltax:word,floodval:word,\\r
  52               stackptr:word,FillCount:word=STK\r
  53         push bp\r
  54         mov  bp,sp\r
  55         sub  sp,STK\r
  56         mov  [FillCount],0\r
  57         push di si\r
  58         mov  si,[Y]\r
  59         mov  ax,[_ScrnLogicalByteWidth]\r
  60         mul  si                   ;offset of pixel's scan line in page\r
  61         mov  di,[X]\r
  62         mov  bx,di\r
  63         shr  di,2                 ;X/4 = offset of pixel in scan line\r
  64         add  di,ax                ;offset of pixel in page\r
  65         add  di,[PgOfs]           ;offset of pixel in display memory\r
  66         mov  ax,SCREEN_SEG\r
  67         mov  es,ax                ;point ES:DI to the pixel's address\r
  68 \r
  69         ;---- Select read plane ------\r
  70 \r
  71         mov  ah,bl\r
  72         and  ah,011b              ;AH = pixel's plane\r
  73         mov  al,READ_MAP          ;AL = index in GC of the Read Map reg\r
  74         mov  dx,GC_INDEX          ;set the Read Map to read the pixel's\r
  75         out  dx,ax                ; plane\r
  76 \r
  77         mov  al,es:[di]           ;read the pixel's color\r
  78         cmp  al,byte ptr Color    ;Is dest pixel the same color as the flood?\r
  79         je   @@Done2              ; if it is abort.\r
  80 \r
  81         mov  cx,_LeftClip         ; Is the dest. pixel out of the clipping window?\r
  82         sal  cx,2                 ;  if not abort.\r
  83         cmp  bx,cx\r
  84         jl   @@Done2\r
  85 \r
  86         mov  cx,_RightClip\r
  87         sal  cx,2\r
  88         cmp  bx,cx\r
  89         jg   @@Done2\r
  90 \r
  91         mov  floodval,ax           ; store the color to flood\r
  92 \r
  93         ;-- Push fill segment ---\r
  94 \r
  95         push bx         ; X\r
  96         push si         ; Y\r
  97         push si         ; Y\r
  98         mov  cx,1       ; deltaX  (either 1 or -1 indicating direction)\r
  99         push cx\r
 100         mov  stackptr,1\r
 101 \r
 102         mov  deltax,-1  ; Initialize first column scan\r
 103         mov  y1,si      ;   then bypass some of the preliminary crap in\r
 104         mov  y2,si      ;   the main fill loop\r
 105         jmp  short @@entry\r
 106 \r
 107 @@Done2:mov  ax,[FillCount]\r
 108         pop  si di\r
 109         mov  sp,bp\r
 110         pop  bp\r
 111         ret\r
 112 \r
 113 @@NextScanCol:\r
 114         dec  stackptr\r
 115         js   @@Done2\r
 116 \r
 117 @@WhileLoop:\r
 118         pop  cx           ; get fill segment from stack\r
 119         mov  deltax,cx    ; ie deltaX, Y1, Y2, X\r
 120         pop  ax\r
 121         mov  y2,ax\r
 122         pop  si\r
 123         mov  y1,si\r
 124         pop  bx\r
 125 \r
 126         sub  ax,si           ; Acculmulate number of filled pixels\r
 127         jns  @@PositiveY\r
 128         neg  ax\r
 129 @@PositiveY:\r
 130         add  FillCount,ax\r
 131 \r
 132 \r
 133         add  bx,cx          ; move to new column according to deltaX\r
 134 \r
 135         mov  ax,bx          ; Make sure the column is within the clipping\r
 136         sar  ax,2           ; rectangle\r
 137         cmp  ax,_LeftClip\r
 138         jl   @@NextScanCol\r
 139 \r
 140         cmp  ax,_RightClip\r
 141         jg   @@NextScanCol\r
 142 \r
 143 \r
 144         ;---- Select read plane ------\r
 145 \r
 146         mov  ah,bl\r
 147         and  ah,011b              ;AH = pixel's plane\r
 148         mov  al,READ_MAP          ;AL = index in GC of the Read Map reg\r
 149         mov  dx,GC_INDEX          ;set the Read Map to read the pixel's\r
 150         out  dx,ax                ; plane\r
 151 \r
 152 @@entry:\r
 153 \r
 154         ;---- Select write plane ------\r
 155 \r
 156         mov  cl,bl\r
 157         and  cl,011b              ;CL = pixel's plane\r
 158         mov  ax,0100h + MAP_MASK  ;AL = index in SC of Map Mask reg\r
 159         shl  ah,cl                ;set only the bit for the pixel's\r
 160                                   ; plane to 1\r
 161         mov  dx,SC_INDEX          ;set the Map Mask to enable only the\r
 162         out  dx,ax                ; pixel's plane\r
 163 \r
 164         mov  ax,_ScrnLogicalByteWidth     ; store logical width in CX\r
 165         mov  cx,ax                        ; get offset of scan row\r
 166         mul  si                           ; set ES:DI ->\r
 167         mov  di,bx                        ; address of pixel at x,y1\r
 168         shr  di,2\r
 169         add  di,ax\r
 170         add  di,PgOfs          ;ES:DI->first pixel of column segment to fill\r
 171         mov  dx,di             ; save y1 offset for after upward fill\r
 172 \r
 173         mov  al,byte ptr Color\r
 174         mov  ah,byte ptr floodval\r
 175 \r
 176 @@FillColUpward:\r
 177         cmp  si,_TopClip           ; Dont fill beyond clip boundaries\r
 178         jl   @@UpwardFillDone\r
 179 \r
 180         cmp  es:[di],ah            ; if flood pixel color then replace\r
 181         jne  @@UpwardFillDone      ; with new color otherwise column is done\r
 182 \r
 183         mov  es:[di],al\r
 184         sub  di,cx\r
 185         dec  si\r
 186         jmp  short @@FillColUpward\r
 187 \r
 188 @@UpwardFillDone:\r
 189         cmp  si,y1\r
 190         jge  @@Skip\r
 191 \r
 192         inc  si\r
 193         mov  len,si\r
 194 \r
 195         cmp  si,y1\r
 196         jge  @@AtColumnTop\r
 197 \r
 198         push bx     ;  queue an upward leak check\r
 199         push si\r
 200         mov  ax,y1\r
 201         dec  ax\r
 202         push ax\r
 203         mov  ax,deltax\r
 204         neg  ax\r
 205         push ax\r
 206         inc  stackptr\r
 207 \r
 208 @@AtColumnTop:\r
 209         mov  si,y1\r
 210         mov  di,dx\r
 211         add  di,cx\r
 212         inc  si\r
 213 \r
 214 \r
 215 @@ColumnLoop:\r
 216         mov  ah,byte ptr floodval\r
 217         mov  al,byte ptr Color\r
 218 \r
 219 @@DownwardFill:\r
 220         cmp  si,_BottomClip\r
 221         jg   @@DownwardFillDone\r
 222         cmp  es:[di],ah\r
 223         jne  @@DownwardFillDone\r
 224         mov  es:[di],al\r
 225         add  di,cx\r
 226         inc  si\r
 227         jmp  short @@DownwardFill\r
 228 \r
 229 @@DownwardFillDone:\r
 230 \r
 231         push bx      ; queue an upward leak check\r
 232         mov  ax,len\r
 233         push ax\r
 234         mov  ax,si\r
 235         dec  ax\r
 236         push ax\r
 237         mov  ax,deltax\r
 238         push ax\r
 239         inc  stackptr\r
 240 \r
 241         mov  ax,y2\r
 242         inc  ax\r
 243         cmp  si,ax\r
 244         jle  @@Skip\r
 245 \r
 246         push bx       ;  queue a downward leak check\r
 247         push ax\r
 248         mov  ax,si\r
 249         dec  ax\r
 250         push ax\r
 251         mov  ax,deltax\r
 252         neg  ax\r
 253         push ax\r
 254         inc  stackptr\r
 255 \r
 256 @@Skip:\r
 257         mov  ah,byte ptr floodval\r
 258         mov  dx,y2\r
 259 \r
 260 @@Backtrack:\r
 261         add  di,cx\r
 262         inc  si\r
 263         cmp  si,dx\r
 264         jg   @@BacktrackDone\r
 265 \r
 266         cmp  byte ptr es:[di],ah\r
 267         jne  @@Backtrack\r
 268 \r
 269 @@BacktrackDone:\r
 270         mov  len,si\r
 271         cmp  si,dx\r
 272         jle  @@ColumnLoop\r
 273 \r
 274         dec  stackptr\r
 275         js   @@Done\r
 276         jmp  @@WhileLoop\r
 277 @@Done:\r
 278         mov  ax,[FillCount]\r
 279         pop  si di\r
 280         mov  sp,bp\r
 281         pop  bp\r
 282         ret\r
 283 _x_flood_fill   endp\r
 284 \r
 285 \r
 286 _x_boundary_fill  proc\r
 287         ARG X:word,Y:word,PgOfs:word,BoundaryColor:word,Color:word\r
 288         LOCAL len:word,y1:word,y2:word,deltax:word,y1_offs:word,\\r
 289               stackptr:word,FillCount:word=STK\r
 290         push bp\r
 291         mov  bp,sp\r
 292         sub  sp,STK\r
 293         mov  [FillCount],0\r
 294         push di si\r
 295         mov  si,[Y]\r
 296         mov  ax,[_ScrnLogicalByteWidth]\r
 297         mul  si                  ;offset of pixel's scan line in page\r
 298         mov  di,[X]\r
 299         mov  bx,di\r
 300         shr  di,2                 ;X/4 = offset of pixel in scan line\r
 301         add  di,ax                ;offset of pixel in page\r
 302         add  di,[PgOfs]           ;offset of pixel in display memory\r
 303         mov  ax,SCREEN_SEG\r
 304         mov  es,ax                ;point ES:DI to the pixel's address\r
 305 \r
 306         ;---- Select read plane ------\r
 307 \r
 308         mov  ah,bl\r
 309         and  ah,011b              ;AH = pixel's plane\r
 310         mov  al,READ_MAP          ;AL = index in GC of the Read Map reg\r
 311         mov  dx,GC_INDEX          ;set the Read Map to read the pixel's\r
 312         out  dx,ax                ; plane\r
 313 \r
 314         mov  al,es:[di]           ;read the pixel's color\r
 315         cmp  al,byte ptr Color    ;Is dest pixel the same color as the flood?\r
 316         je   @@Done2\r
 317 \r
 318         cmp  al,byte ptr BoundaryColor ;Is dest pixel the same color\r
 319         je   @@Done2                   ; as the boundary color?\r
 320 \r
 321 \r
 322         mov  cx,_LeftClip         ; Is the dest. pixel out of the clipping window?\r
 323         sal  cx,2\r
 324         cmp  bx,cx\r
 325         jl   @@Done2\r
 326 \r
 327         mov  cx,_RightClip\r
 328         sal  cx,2\r
 329         cmp  bx,cx\r
 330         jg   @@Done2\r
 331 \r
 332         push bx      ; X\r
 333         push si      ; Y\r
 334         push si      ; Y\r
 335         mov  cx,1    ; DX\r
 336         push cx\r
 337         mov  stackptr,1\r
 338         mov  al,byte ptr BoundaryColor\r
 339         mov  byte ptr [Color+1],al\r
 340 \r
 341         mov  deltax,-1\r
 342         mov  y1,si\r
 343         mov  y2,si\r
 344         jmp  short @@entry\r
 345 \r
 346 @@Done2:mov  ax,[FillCount]\r
 347         pop  si di\r
 348         mov  sp,bp\r
 349         pop  bp\r
 350         ret\r
 351 \r
 352 @@NextScanCol:\r
 353         dec  stackptr\r
 354         js   @@Done2\r
 355 \r
 356 @@WhileLoop:\r
 357         pop  cx\r
 358         mov  deltax,cx\r
 359         pop  ax\r
 360         mov  y2,ax\r
 361         pop  si\r
 362         mov  y1,si\r
 363         pop  bx\r
 364         add  bx,cx   ; bx = X\r
 365 \r
 366         sub  ax,si           ; Acculmulate number of filled pixels\r
 367         jns  @@PositiveY\r
 368         neg  ax\r
 369 @@PositiveY:\r
 370         add  FillCount,ax\r
 371 \r
 372 \r
 373 \r
 374         mov  ax,bx          ; Make sure the column is within the clipping\r
 375         sar  ax,2           ; rectangle\r
 376         cmp  ax,_LeftClip\r
 377         jl   @@NextScanCol\r
 378         cmp  ax,_RightClip\r
 379         jg   @@NextScanCol\r
 380 \r
 381 \r
 382         ;---- Select read plane ------\r
 383 \r
 384         mov  ah,bl\r
 385         and  ah,011b              ;AH = pixel's plane\r
 386         mov  al,READ_MAP          ;AL = index in GC of the Read Map reg\r
 387         mov  dx,GC_INDEX          ;set the Read Map to read the pixel's\r
 388         out  dx,ax                ; plane\r
 389 \r
 390 @@entry:\r
 391 \r
 392         ;---- Select write plane ------\r
 393 \r
 394         mov  cl,bl\r
 395         and  cl,011b              ;CL = pixel's plane\r
 396         mov  ax,0100h + MAP_MASK  ;AL = index in SC of Map Mask reg\r
 397         shl  ah,cl                ;set only the bit for the pixel's\r
 398                                   ; plane to 1\r
 399         mov  dx,SC_INDEX          ;set the Map Mask to enable only the\r
 400         out  dx,ax                ; pixel's plane\r
 401 \r
 402         mov  ax,_ScrnLogicalByteWidth     ; store logical width in CX\r
 403         mov  cx,ax                        ; get offset of scan row\r
 404         mul  si                           ; set ES:DI ->\r
 405         mov  di,bx                        ; address of pixel at x,y1\r
 406         shr  di,2\r
 407         add  di,ax\r
 408         add  di,PgOfs\r
 409         mov  y1_offs,di                   ; save y1 offset for after upward fill\r
 410 \r
 411         mov   ax,Color                    ; al = Color ah = BoundaryColor\r
 412 \r
 413 @@FillColUpward:\r
 414         cmp  si,_TopClip                  ; Dont fill beyond clip boundaries\r
 415         jl   @@UpwardFillDone\r
 416 \r
 417         mov  dl,es:[di]\r
 418         cmp  dl,ah\r
 419         je   @@UpwardFillDone\r
 420 \r
 421         cmp  dl,al\r
 422         je   @@UpwardFillDone\r
 423 \r
 424         mov  es:[di],al\r
 425         sub  di,cx\r
 426         dec  si\r
 427         jmp  short @@FillColUpward\r
 428 \r
 429 @@UpwardFillDone:\r
 430         cmp  si,y1\r
 431         jge  @@Skip\r
 432 \r
 433         inc  si\r
 434         mov  len,si\r
 435 \r
 436         cmp  si,y1\r
 437         jge  @@AtColumnTop\r
 438 \r
 439         push bx     ;  queue an upward leak check\r
 440         push si\r
 441         mov  ax,y1\r
 442         dec  ax\r
 443         push ax\r
 444         mov  ax,deltax\r
 445         neg  ax\r
 446         push ax\r
 447         inc  stackptr\r
 448 \r
 449 @@AtColumnTop:\r
 450         mov  si,y1\r
 451         mov  di,y1_offs\r
 452         add  di,cx\r
 453         inc  si\r
 454 \r
 455 \r
 456 @@ColumnLoop:\r
 457         mov   ax,Color           ; al = Color ah = BoundaryColor\r
 458 \r
 459 @@DownwardFill:\r
 460         cmp  si,_BottomClip\r
 461         jg   @@DownwardFillDone\r
 462 \r
 463         cmp  es:[di],ah\r
 464         je   @@DownwardFillDone\r
 465 \r
 466         cmp  es:[di],al\r
 467         je   @@DownwardFillDone\r
 468 \r
 469         mov  es:[di],al\r
 470         add  di,cx\r
 471         inc  si\r
 472         jmp  short @@DownwardFill\r
 473 \r
 474 @@DownwardFillDone:\r
 475 \r
 476         push bx      ; queue an upward leak check\r
 477         mov  ax,len\r
 478         push ax\r
 479         mov  ax,si\r
 480         dec  ax\r
 481         push ax\r
 482         mov  ax,deltax\r
 483         push ax\r
 484         inc  stackptr\r
 485 \r
 486         mov  ax,y2\r
 487         inc  ax\r
 488         cmp  si,ax\r
 489         jle  @@Skip\r
 490 \r
 491         push bx       ;  queue a downward leak check\r
 492         push ax\r
 493         mov  ax,si\r
 494         dec  ax\r
 495         push ax\r
 496         mov  ax,deltax\r
 497         neg  ax\r
 498         push ax\r
 499         inc  stackptr\r
 500 \r
 501 @@Skip:\r
 502         mov  ax,Color                ; al = Color ah = BoundaryColor\r
 503 \r
 504 @@Backtrack:\r
 505         add  di,cx\r
 506         inc  si\r
 507         cmp  si,y2\r
 508         jg   @@BacktrackDone\r
 509 \r
 510         mov  dl,byte ptr es:[di]\r
 511         cmp  dl,al\r
 512         je   @@Backtrack\r
 513 \r
 514         cmp  dl,ah\r
 515         je   @@Backtrack\r
 516 \r
 517 @@BacktrackDone:\r
 518         mov  len,si\r
 519         cmp  si,y2\r
 520         jle  @@ColumnLoop\r
 521 \r
 522         dec  stackptr\r
 523         js   @@Done\r
 524         jmp  @@WhileLoop\r
 525 @@Done:\r
 526         mov  ax,[FillCount]\r
 527         pop  si di\r
 528         mov  sp,bp\r
 529         pop  bp\r
 530         ret\r
 531 _x_boundary_fill   endp\r
 532 \r
 533 end\r