bitmaptools/__init__.py

   1 import math
   2 import struct
   3 from typing import Optional, Tuple, BinaryIO
   4 import numpy as np
   5 from displayio import Bitmap, Colorspace
   6 import circuitpython_typing
   7
   8
   9 def fill_region(dest_bitmap: Bitmap, x1: int, y1: int, x2: int, y2: int, value: int):
  10     for y in range(y1, y2):
  11         for x in range(x1, x2):
  12             dest_bitmap[x, y] = value
  13
  14
  15 def draw_line(dest_bitmap: Bitmap, x1: int, y1: int, x2: int, y2: int, value: int):
  16     dx = abs(x2 - x1)
  17     sx = 1 if x1 < x2 else -1
  18     dy = -abs(y2 - y1)
  19     sy = 1 if y1 < y2 else -1
  20     error = dx + dy
  21
  22     while True:
  23         dest_bitmap[x1, y1] = value
  24         if x1 == x2 and y1 == y2:
  25             break
  26         e2 = 2 * error
  27         if e2 >= dy:
  28             error += dy
  29             x1 += sx
  30         if e2 <= dx:
  31             error += dx
  32             y1 += sy
  33
  34
  35 def draw_circle(dest_bitmap: Bitmap, x: int, y: int, radius: int, value: int):
  36     x = max(0, min(x, dest_bitmap.width - 1))
  37     y = max(0, min(y, dest_bitmap.height - 1))
  38
  39     xb = 0
  40     yb = radius
  41     d = 3 - 2 * radius
  42
  43     # Bresenham's circle algorithm
  44     while xb <= yb:
  45         dest_bitmap[xb + x, yb + y] = value
  46         dest_bitmap[-xb + x, -yb + y] = value
  47         dest_bitmap[-xb + x, yb + y] = value
  48         dest_bitmap[xb + x, -yb + y] = value
  49         dest_bitmap[yb + x, xb + y] = value
  50         dest_bitmap[-yb + x, xb + y] = value
  51         dest_bitmap[-yb + x, -xb + y] = value
  52         dest_bitmap[yb + x, -xb + y] = value
  53
  54         if d <= 0:
  55             d = d + (4 * xb) + 6
  56         else:
  57             d = d + 4 * (xb - yb) + 10
  58             yb = yb - 1
  59         xb += 1
  60
  61
  62 def draw_polygon(
  63     dest_bitmap: Bitmap,
  64     xs: circuitpython_typing.ReadableBuffer,
  65     ys: circuitpython_typing.ReadableBuffer,
  66     value: int,
  67     close: bool = True,
  68 ):
  69     if len(xs) != len(ys):
  70         raise ValueError("Length of xs and ys must be equal.")
  71
  72     for i in range(len(xs) - 1):
  73         cur_point = (xs[i], ys[i])
  74         next_point = (xs[i + 1], ys[i + 1])
  75         print(f"cur: {cur_point}, next: {next_point}")
  76         draw_line(
  77             dest_bitmap=dest_bitmap,
  78             x1=cur_point[0],
  79             y1=cur_point[1],
  80             x2=next_point[0],
  81             y2=next_point[1],
  82             value=value,
  83         )
  84
  85     if close:
  86         print(f"close: {(xs[0], ys[0])} - {(xs[-1], ys[-1])}")
  87         draw_line(
  88             dest_bitmap=dest_bitmap,
  89             x1=xs[0],
  90             y1=ys[0],
  91             x2=xs[-1],
  92             y2=ys[-1],
  93             value=value,
  94         )
  95
  96
  97 def blit(
  98     dest_bitmap: Bitmap,
  99     source_bitmap: Bitmap,
 100     x: int,
 101     y: int,
 102     *,
 103     x1: int = 0,
 104     y1: int = 0,
 105     x2: int | None = None,
 106     y2: int | None = None,
 107     skip_source_index: int | None = None,
 108     skip_dest_index: int | None = None,
 109 ):
 110     """Inserts the source_bitmap region defined by rectangular boundaries"""
 111     # pylint: disable=invalid-name
 112     if x2 is None:
 113         x2 = source_bitmap.width
 114     if y2 is None:
 115         y2 = source_bitmap.height
 116
 117     # Rearrange so that x1 < x2 and y1 < y2
 118     if x1 > x2:
 119         x1, x2 = x2, x1
 120     if y1 > y2:
 121         y1, y2 = y2, y1
 122
 123     # Ensure that x2 and y2 are within source bitmap size
 124     x2 = min(x2, source_bitmap.width)
 125     y2 = min(y2, source_bitmap.height)
 126
 127     for y_count in range(y2 - y1):
 128         for x_count in range(x2 - x1):
 129             x_placement = x + x_count
 130             y_placement = y + y_count
 131
 132             if (dest_bitmap.width > x_placement >= 0) and (
 133                 dest_bitmap.height > y_placement >= 0
 134             ):  # ensure placement is within target bitmap
 135                 # get the palette index from the source bitmap
 136                 this_pixel_color = source_bitmap[
 137                     y1 + (y_count * source_bitmap.width) + x1 + x_count
 138                 ]
 139
 140                 if (skip_source_index is None) or (
 141                     this_pixel_color != skip_source_index
 142                 ):
 143                     if (skip_dest_index is None) or (
 144                         dest_bitmap[y_placement * dest_bitmap.width + x_placement]
 145                         != skip_dest_index
 146                     ):
 147                         dest_bitmap[  # Direct index into a bitmap array is speedier than [x,y] tuple
 148                             y_placement * dest_bitmap.width + x_placement
 149                         ] = this_pixel_color
 150             elif y_placement > dest_bitmap.height:
 151                 break
 152
 153
 154 def rotozoom(
 155     dest_bitmap: Bitmap,
 156     source_bitmap: Bitmap,
 157     *,
 158     ox: Optional[int] = None,
 159     oy: Optional[int] = None,
 160     dest_clip0: Optional[Tuple[int, int]] = None,
 161     dest_clip1: Optional[Tuple[int, int]] = None,
 162     px: Optional[int] = None,
 163     py: Optional[int] = None,
 164     source_clip0: Optional[Tuple[int, int]] = None,
 165     source_clip1: Optional[Tuple[int, int]] = None,
 166     angle: Optional[float] = None,
 167     scale: Optional[float] = None,
 168     skip_index: Optional[int] = None,
 169 ):
 170     if ox is None:
 171         ox = dest_bitmap.width // 2
 172     if oy in None:
 173         oy = dest_bitmap.height // 2
 174
 175     if dest_clip0 is None:
 176         dest_clip0 = (0, 0)
 177     if dest_clip1 is None:
 178         dest_clip1 = (dest_bitmap.width, dest_bitmap.height)
 179
 180     if px is None:
 181         px = source_bitmap.width // 2
 182     if py in None:
 183         py = source_bitmap.height // 2
 184
 185     if source_clip0 is None:
 186         source_clip0 = (0, 0)
 187     if source_clip1 is None:
 188         source_clip1 = (source_bitmap.width, source_bitmap.height)
 189
 190     if angle is None:
 191         angle = 0.0
 192     if scale is None:
 193         scale = 1.0
 194
 195     dest_clip0_x, dest_clip0_y = dest_clip0
 196     dest_clip1_x, dest_clip1_y = dest_clip1
 197     source_clip0_x, source_clip0_y = source_clip0
 198     source_clip1_x, source_clip1_y = source_clip1
 199
 200     minx = dest_clip1_x
 201     miny = dest_clip1_y
 202     maxx = dest_clip0_x
 203     maxy = dest_clip0_y
 204
 205     sin_angle = math.sin(angle)
 206     cos_angle = math.cos(angle)
 207
 208     def update_bounds(dx, dy):
 209         nonlocal minx, maxx, miny, maxy
 210         if dx < minx:
 211             minx = int(dx)
 212         if dx > maxx:
 213             maxx = int(dx)
 214         if dy < miny:
 215             miny = int(dy)
 216         if dy > maxy:
 217             maxy = int(dy)
 218
 219     w = source_bitmap.width
 220     h = source_bitmap.height
 221
 222     dx = -cos_angle * px * scale + sin_angle * py * scale + ox
 223     dy = -sin_angle * px * scale - cos_angle * py * scale + oy
 224     update_bounds(dx, dy)
 225
 226     dx = cos_angle * (w - px) * scale + sin_angle * py * scale + ox
 227     dy = sin_angle * (w - px) * scale - cos_angle * py * scale + oy
 228     update_bounds(dx, dy)
 229
 230     dx = cos_angle * (w - px) * scale - sin_angle * (h - py) * scale + ox
 231     dy = sin_angle * (w - px) * scale + cos_angle * (h - py) * scale + oy
 232     update_bounds(dx, dy)
 233
 234     dx = -cos_angle * px * scale - sin_angle * (h - py) * scale + ox
 235     dy = -sin_angle * px * scale + cos_angle * (h - py) * scale + oy
 236     update_bounds(dx, dy)
 237
 238     # Clip to destination area
 239     minx = max(minx, dest_clip0_x)
 240     maxx = min(maxx, dest_clip1_x - 1)
 241     miny = max(miny, dest_clip0_y)
 242     maxy = min(maxy, dest_clip1_y - 1)
 243
 244     dv_col = cos_angle / scale
 245     du_col = sin_angle / scale
 246     du_row = dv_col
 247     dv_row = -du_col
 248
 249     startu = px - (ox * dv_col + oy * du_col)
 250     startv = py - (ox * dv_row + oy * du_row)
 251
 252     rowu = startu + miny * du_col
 253     rowv = startv + miny * dv_col
 254
 255     for y in range(miny, maxy + 1):
 256         u = rowu + minx * du_row
 257         v = rowv + minx * dv_row
 258         for x in range(minx, maxx + 1):
 259             if (source_clip0_x <= u < source_clip1_x) and (
 260                 source_clip0_y <= v < source_clip1_y
 261             ):
 262                 c = source_bitmap[int(u), int(v)]
 263                 if skip_index is None or c != skip_index:
 264                     dest_bitmap[x, y] = c
 265             u += du_row
 266             v += dv_row
 267         rowu += du_col
 268         rowv += dv_col
 269
 270
 271 def arrayblit(
 272     bitmap: Bitmap,
 273     data: circuitpython_typing.ReadableBuffer,
 274     x1: int = 0,
 275     y1: int = 0,
 276     x2: Optional[int] = None,
 277     y2: Optional[int] = None,
 278     skip_index: Optional[int] = None,
 279 ):
 280     if x2 is None:
 281         x2 = bitmap.width
 282     if y2 is None:
 283         y2 = bitmap.height
 284
 285     _value_count = 2**bitmap._bits_per_value
 286     for y in range(y1, y2):
 287         for x in range(x1, x2):
 288             i = y * (x2 - x1) + x
 289             value = int(data[i] % _value_count)
 290             if skip_index is None or value != skip_index:
 291                 bitmap[x, y] = value
 292
 293
 294 def readinto(
 295     bitmap: Bitmap,
 296     file: BinaryIO,
 297     bits_per_pixel: int,
 298     element_size: int = 1,
 299     reverse_pixels_in_element: bool = False,
 300     swap_bytes: bool = False,
 301     reverse_rows: bool = False,
 302 ):
 303     width = bitmap.width
 304     height = bitmap.height
 305     bits_per_value = bitmap._bits_per_value
 306     mask = (1 << bits_per_value) - 1
 307
 308     elements_per_row = (width * bits_per_pixel + element_size * 8 - 1) // (
 309         element_size * 8
 310     )
 311     rowsize = element_size * elements_per_row
 312
 313     for y in range(height):
 314         row_bytes = file.read(rowsize)
 315         if len(row_bytes) != rowsize:
 316             raise EOFError()
 317
 318         # Convert the raw bytes into the appropriate type array for processing
 319         rowdata = bytearray(row_bytes)
 320
 321         if swap_bytes:
 322             if element_size == 2:
 323                 rowdata = bytearray(
 324                     b"".join(
 325                         struct.pack("<H", struct.unpack(">H", rowdata[i : i + 2])[0])
 326                         for i in range(0, len(rowdata), 2)
 327                     )
 328                 )
 329             elif element_size == 4:
 330                 rowdata = bytearray(
 331                     b"".join(
 332                         struct.pack("<I", struct.unpack(">I", rowdata[i : i + 4])[0])
 333                         for i in range(0, len(rowdata), 4)
 334                     )
 335                 )
 336
 337         y_draw = height - 1 - y if reverse_rows else y
 338
 339         for x in range(width):
 340             value = 0
 341             if bits_per_pixel == 1:
 342                 byte_offset = x // 8
 343                 bit_offset = 7 - (x % 8) if reverse_pixels_in_element else x % 8
 344                 value = (rowdata[byte_offset] >> bit_offset) & 0x1
 345             elif bits_per_pixel == 2:
 346                 byte_offset = x // 4
 347                 bit_index = 3 - (x % 4) if reverse_pixels_in_element else x % 4
 348                 bit_offset = 2 * bit_index
 349                 value = (rowdata[byte_offset] >> bit_offset) & 0x3
 350             elif bits_per_pixel == 4:
 351                 byte_offset = x // 2
 352                 bit_index = 1 - (x % 2) if reverse_pixels_in_element else x % 2
 353                 bit_offset = 4 * bit_index
 354                 value = (rowdata[byte_offset] >> bit_offset) & 0xF
 355             elif bits_per_pixel == 8:
 356                 value = rowdata[x]
 357             elif bits_per_pixel == 16:
 358                 value = struct.unpack_from("<H", rowdata, x * 2)[0]
 359             elif bits_per_pixel == 24:
 360                 offset = x * 3
 361                 value = (
 362                     (rowdata[offset] << 16)
 363                     | (rowdata[offset + 1] << 8)
 364                     | rowdata[offset + 2]
 365                 )
 366             elif bits_per_pixel == 32:
 367                 value = struct.unpack_from("<I", rowdata, x * 4)[0]
 368
 369             bitmap[x, y_draw] = value & mask
 370
 371
 372 class BlendMode:
 373     Normal = "bitmaptools.BlendMode.Normal"
 374     Screen = "bitmaptools.BlendMode.Screen"
 375
 376
 377 def alphablend(
 378     dest: Bitmap,
 379     source1: Bitmap,
 380     source2: Bitmap,
 381     colorspace: Colorspace,
 382     factor1: float = 0.5,
 383     factor2: Optional[float] = None,
 384     blendmode: BlendMode = BlendMode.Normal,
 385     skip_source1_index: Optional[int] = None,
 386     skip_source2_index: Optional[int] = None,
 387 ):
 388     """
 389         colorspace should be one of: 'L8', 'RGB565', 'RGB565_SWAPPED', 'BGR565_SWAPPED'.
 390
 391     blendmode can be 'normal' (or any default) or 'screen'.
 392
 393     This assumes that all bitmaps (dest, source1, source2) support 2D access like bitmap[x, y].
 394
 395     dest.width and dest.height are used; make sure the bitmap objects have these attributes or replace them with your own logic.
 396     """
 397
 398     def clamp(val, minval, maxval):
 399         return max(minval, min(maxval, val))
 400
 401     ifactor1 = int(factor1 * 256)
 402     ifactor2 = int(factor2 * 256)
 403
 404     width, height = dest.width, dest.height
 405
 406     if colorspace == "L8":
 407         for y in range(height):
 408             for x in range(width):
 409                 sp1 = source1[x, y]
 410                 sp2 = source2[x, y]
 411                 blend_source1 = skip_source1_index is None or sp1 != skip_source1_index
 412                 blend_source2 = skip_source2_index is None or sp2 != skip_source2_index
 413
 414                 if blend_source1 and blend_source2:
 415                     sda = sp1 * ifactor1
 416                     sca = sp2 * ifactor2
 417
 418                     if blendmode == BlendMode.Screen:
 419                         blend = sca + sda - (sca * sda // 65536)
 420                     elif blendmode == BlendMode.Normal:
 421                         blend = sca + sda * (256 - ifactor2) // 256
 422
 423                     denom = ifactor1 + ifactor2 - ifactor1 * ifactor2 // 256
 424                     pixel = blend // denom
 425                 elif blend_source1:
 426                     pixel = sp1 * ifactor1 // 256
 427                 elif blend_source2:
 428                     pixel = sp2 * ifactor2 // 256
 429                 else:
 430                     pixel = dest[x, y]
 431
 432                 dest[x, y] = clamp(pixel, 0, 255)
 433
 434     else:
 435         swap = colorspace in ("RGB565_SWAPPED", "BGR565_SWAPPED")
 436         r_mask = 0xF800
 437         g_mask = 0x07E0
 438         b_mask = 0x001F
 439
 440         for y in range(height):
 441             for x in range(width):
 442                 sp1 = source1[x, y]
 443                 sp2 = source2[x, y]
 444
 445                 if swap:
 446                     sp1 = ((sp1 & 0xFF) << 8) | ((sp1 >> 8) & 0xFF)
 447                     sp2 = ((sp2 & 0xFF) << 8) | ((sp2 >> 8) & 0xFF)
 448
 449                 blend_source1 = skip_source1_index is None or sp1 != skip_source1_index
 450                 blend_source2 = skip_source2_index is None or sp2 != skip_source2_index
 451
 452                 if blend_source1 and blend_source2:
 453                     ifactor_blend = ifactor1 + ifactor2 - ifactor1 * ifactor2 // 256
 454
 455                     red_dca = ((sp1 & r_mask) >> 8) * ifactor1
 456                     grn_dca = ((sp1 & g_mask) >> 3) * ifactor1
 457                     blu_dca = ((sp1 & b_mask) << 3) * ifactor1
 458
 459                     red_sca = ((sp2 & r_mask) >> 8) * ifactor2
 460                     grn_sca = ((sp2 & g_mask) >> 3) * ifactor2
 461                     blu_sca = ((sp2 & b_mask) << 3) * ifactor2
 462
 463                     if blendmode == BlendMode.Screen:
 464                         red_blend = red_sca + red_dca - (red_sca * red_dca // 65536)
 465                         grn_blend = grn_sca + grn_dca - (grn_sca * grn_dca // 65536)
 466                         blu_blend = blu_sca + blu_dca - (blu_sca * blu_dca // 65536)
 467                     elif blendmode == BlendMode.Normal:
 468                         red_blend = red_sca + red_dca * (256 - ifactor2) // 256
 469                         grn_blend = grn_sca + grn_dca * (256 - ifactor2) // 256
 470                         blu_blend = blu_sca + blu_dca * (256 - ifactor2) // 256
 471
 472                     r = ((red_blend // ifactor_blend) << 8) & r_mask
 473                     g = ((grn_blend // ifactor_blend) << 3) & g_mask
 474                     b = ((blu_blend // ifactor_blend) >> 3) & b_mask
 475
 476                     pixel = (r & r_mask) | (g & g_mask) | (b & b_mask)
 477
 478                     if swap:
 479                         pixel = ((pixel & 0xFF) << 8) | ((pixel >> 8) & 0xFF)
 480
 481                 elif blend_source1:
 482                     r = ((sp1 & r_mask) * ifactor1 // 256) & r_mask
 483                     g = ((sp1 & g_mask) * ifactor1 // 256) & g_mask
 484                     b = ((sp1 & b_mask) * ifactor1 // 256) & b_mask
 485                     pixel = r | g | b
 486                 elif blend_source2:
 487                     r = ((sp2 & r_mask) * ifactor2 // 256) & r_mask
 488                     g = ((sp2 & g_mask) * ifactor2 // 256) & g_mask
 489                     b = ((sp2 & b_mask) * ifactor2 // 256) & b_mask
 490                     pixel = r | g | b
 491                 else:
 492                     pixel = dest[x, y]
 493
 494                 print(f"pixel hex: {hex(pixel)}")
 495                 dest[x, y] = pixel
 496
 497
 498 class DitherAlgorithm:
 499     Atkinson = "bitmaptools.DitherAlgorithm.Atkinson"
 500     FloydStenberg = "bitmaptools.DitherAlgorithm.FloydStenberg"
 501
 502     atkinson = {
 503         "count": 4,
 504         "mx": 2,
 505         "dl": 256 // 8,
 506         "terms": [
 507             {"dx": 2, "dy": 0, "dl": 256 // 8},
 508             {"dx": -1, "dy": 1, "dl": 256 // 8},
 509             {"dx": 0, "dy": 1, "dl": 256 // 8},
 510             {"dx": 0, "dy": 2, "dl": 256 // 8},
 511         ],
 512     }
 513
 514     floyd_stenberg = {
 515         "count": 3,
 516         "mx": 1,
 517         "dl": 7 * 256 // 16,
 518         "terms": [
 519             {"dx": -1, "dy": 1, "dl": 3 * 256 // 16},
 520             {"dx": 0, "dy": 1, "dl": 5 * 256 // 16},
 521             {"dx": 1, "dy": 1, "dl": 1 * 256 // 16},
 522         ],
 523     }
 524
 525     algorithm_map = {Atkinson: atkinson, FloydStenberg: floyd_stenberg}
 526
 527
 528 def dither(dest_bitmap, source_bitmap, colorspace, algorithm=DitherAlgorithm.Atkinson):
 529     SWAP_BYTES = 1 << 0
 530     SWAP_RB = 1 << 1
 531     height, width = dest_bitmap.width, dest_bitmap.height
 532     swap_bytes = colorspace in (Colorspace.RGB565_SWAPPED, Colorspace.BGR565_SWAPPED)
 533     swap_rb = colorspace in (Colorspace.BGR565, Colorspace.BGR565_SWAPPED)
 534     algorithm_info = DitherAlgorithm.algorithm_map[algorithm]
 535     mx = algorithm_info["mx"]
 536     count = algorithm_info["count"]
 537     terms = algorithm_info["terms"]
 538     dl = algorithm_info["dl"]
 539
 540     swap = 0
 541     if swap_bytes:
 542         swap |= SWAP_BYTES
 543
 544     if swap_rb:
 545         swap |= SWAP_RB
 546
 547     print(f"swap: {swap}")
 548
 549     # Create row data arrays (3 rows with padding on both sides)
 550     rowdata = [[0] * (width + 2 * mx) for _ in range(3)]
 551     rows = [rowdata[0][mx:], rowdata[1][mx:], rowdata[2][mx:]]
 552
 553     # Output array for one row at a time (padded to multiple of 32)
 554     out = [False] * (((width + 31) // 32) * 32)
 555
 556     # Helper function to fill a row with luminance data
 557     def fill_row(bitmap, swap, luminance_data, y, mx):
 558         if y >= bitmap.height:
 559             return
 560
 561         # Zero out padding area
 562         for i in range(mx):
 563             luminance_data[-mx + i] = 0
 564             luminance_data[bitmap.width + i] = 0
 565
 566         if bitmap._bits_per_value == 8:
 567             for x in range(bitmap.width):
 568                 luminance_data[x] = bitmap[x, y]
 569         else:
 570             for x in range(bitmap.width):
 571                 pixel = bitmap[x, y]
 572                 if swap & SWAP_BYTES:
 573                     # Swap bytes (equivalent to __builtin_bswap16)
 574                     pixel = ((pixel & 0xFF) << 8) | ((pixel >> 8) & 0xFF)
 575
 576                 r = (pixel >> 8) & 0xF8
 577                 g = (pixel >> 3) & 0xFC
 578                 b = (pixel << 3) & 0xF8
 579
 580                 if swap & SWAP_BYTES:
 581                     r, b = b, r
 582
 583                 # Calculate luminance using same formula as C version
 584                 luminance_data[x] = (r * 78 + g * 154 + b * 29) // 256
 585
 586     # Helper function to write pixels to destination bitmap
 587     def write_pixels(bitmap, y, data):
 588         if bitmap._bits_per_value == 1:
 589             for i in range(0, bitmap.width, 32):
 590                 # Pack 32 bits into an integer
 591                 p = 0
 592                 for j in range(min(32, bitmap.width - i)):
 593                     p = p << 1
 594                     if data[i + j]:
 595                         p |= 1
 596
 597                 # Write packed value
 598                 for j in range(min(32, bitmap.width - i)):
 599                     bitmap[i + j, y] = (p >> (31 - j)) & 1
 600         else:
 601             for i in range(bitmap.width):
 602                 bitmap[i, y] = 65535 if data[i] else 0
 603
 604     # Fill initial rows
 605     fill_row(source_bitmap, swap, rows[0], 0, mx)
 606     fill_row(source_bitmap, swap, rows[1], 1, mx)
 607     fill_row(source_bitmap, swap, rows[2], 2, mx)
 608
 609     err = 0
 610
 611     for y in range(height):
 612         # Going left to right
 613         for x in range(width):
 614             pixel_in = rows[0][x] + err
 615             pixel_out = pixel_in >= 128
 616             out[x] = pixel_out
 617
 618             err = pixel_in - (255 if pixel_out else 0)
 619
 620             # Distribute error to neighboring pixels
 621             for i in range(count):
 622                 x1 = x + terms[i]["dx"]
 623                 dy = terms[i]["dy"]
 624
 625                 rows[dy][x1] = ((terms[i]["dl"] * err) // 256) + rows[dy][x1]
 626
 627             err = (err * dl) // 256
 628
 629         write_pixels(dest_bitmap, y, out)
 630
 631         # Cycle the rows
 632         rows[0], rows[1], rows[2] = rows[1], rows[2], rows[0]
 633
 634         y += 1
 635         if y == height:
 636             break
 637
 638         # Fill the next row for future processing
 639         fill_row(source_bitmap, swap, rows[2], y + 2, mx)
 640
 641         # Going right to left
 642         for x in range(width - 1, -1, -1):
 643             pixel_in = rows[0][x] + err
 644             pixel_out = pixel_in >= 128
 645             out[x] = pixel_out
 646
 647             err = pixel_in - (255 if pixel_out else 0)
 648
 649             # Distribute error to neighboring pixels (in reverse direction)
 650             for i in range(count):
 651                 x1 = x - terms[i]["dx"]
 652                 dy = terms[i]["dy"]
 653
 654                 rows[dy][x1] = ((terms[i]["dl"] * err) // 256) + rows[dy][x1]
 655
 656             err = (err * dl) // 256
 657
 658         write_pixels(dest_bitmap, y, out)
 659
 660         # Cycle the rows again
 661         rows[0], rows[1], rows[2] = rows[1], rows[2], rows[0]
 662
 663         # Fill the next row for future processing
 664         fill_row(source_bitmap, swap, rows[2], y + 3, mx)
 665
 666
 667 def boundary_fill(
 668     dest_bitmap: Bitmap,
 669     x: int,
 670     y: int,
 671     fill_color_value: int,
 672     replaced_color_value: Optional[int] = None,
 673 ):
 674     if fill_color_value == replaced_color_value:
 675         return
 676     if replaced_color_value == -1:
 677         replaced_color_value = dest_bitmap[x, y]
 678
 679     fill_points = []
 680     fill_points.append((x, y))
 681
 682     seen_points = []
 683     minx = x
 684     miny = y
 685     maxx = x
 686     maxy = y
 687
 688     while len(fill_points):
 689         cur_point = fill_points.pop(0)
 690         seen_points.append(cur_point)
 691         cur_x = cur_point[0]
 692         cur_y = cur_point[1]
 693
 694         cur_point_color = dest_bitmap[cur_x, cur_y]
 695         if replaced_color_value is not None and cur_point_color != replaced_color_value:
 696             continue
 697         if cur_x < minx:
 698             minx = cur_x
 699         if cur_y < miny:
 700             miny = cur_y
 701         if cur_x > maxx:
 702             maxx = cur_x
 703         if cur_y > maxy:
 704             maxy = cur_y
 705
 706         dest_bitmap[cur_x, cur_y] = fill_color_value
 707
 708         above_point = (cur_x, cur_y - 1)
 709         below_point = (cur_x, cur_y + 1)
 710         left_point = (cur_x - 1, cur_y)
 711         right_point = (cur_x + 1, cur_y)
 712
 713         if (
 714             above_point[1] >= 0
 715             and above_point not in seen_points
 716             and above_point not in fill_points
 717         ):
 718             fill_points.append(above_point)
 719         if (
 720             below_point[1] < dest_bitmap.height
 721             and below_point not in seen_points
 722             and below_point not in fill_points
 723         ):
 724             fill_points.append(below_point)
 725         if (
 726             left_point[0] >= 0
 727             and left_point not in seen_points
 728             and left_point not in fill_points
 729         ):
 730             fill_points.append(left_point)
 731         if (
 732             right_point[0] < dest_bitmap.width
 733             and right_point not in seen_points
 734             and right_point not in fill_points
 735         ):
 736             fill_points.append(right_point)