1// Copyright 2009 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// Package draw provides image composition functions. 6// 7// See "The Go image/draw package" for an introduction to this package: 8// https://golang.org/doc/articles/image_draw.html 9package draw 10 11import ( 12 "image" 13 "image/color" 14 "image/internal/imageutil" 15) 16 17// m is the maximum color value returned by image.Color.RGBA. 18const m = 1<<16 - 1 19 20// Image is an image.Image with a Set method to change a single pixel. 21type Image interface { 22 image.Image 23 Set(x, y int, c color.Color) 24} 25 26// Quantizer produces a palette for an image. 27type Quantizer interface { 28 // Quantize appends up to cap(p) - len(p) colors to p and returns the 29 // updated palette suitable for converting m to a paletted image. 30 Quantize(p color.Palette, m image.Image) color.Palette 31} 32 33// Op is a Porter-Duff compositing operator. 34type Op int 35 36const ( 37 // Over specifies ``(src in mask) over dst''. 38 Over Op = iota 39 // Src specifies ``src in mask''. 40 Src 41) 42 43// Draw implements the Drawer interface by calling the Draw function with this 44// Op. 45func (op Op) Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point) { 46 DrawMask(dst, r, src, sp, nil, image.Point{}, op) 47} 48 49// Drawer contains the Draw method. 50type Drawer interface { 51 // Draw aligns r.Min in dst with sp in src and then replaces the 52 // rectangle r in dst with the result of drawing src on dst. 53 Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point) 54} 55 56// FloydSteinberg is a Drawer that is the Src Op with Floyd-Steinberg error 57// diffusion. 58var FloydSteinberg Drawer = floydSteinberg{} 59 60type floydSteinberg struct{} 61 62func (floydSteinberg) Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point) { 63 clip(dst, &r, src, &sp, nil, nil) 64 if r.Empty() { 65 return 66 } 67 drawPaletted(dst, r, src, sp, true) 68} 69 70// clip clips r against each image's bounds (after translating into the 71// destination image's coordinate space) and shifts the points sp and mp by 72// the same amount as the change in r.Min. 73func clip(dst Image, r *image.Rectangle, src image.Image, sp *image.Point, mask image.Image, mp *image.Point) { 74 orig := r.Min 75 *r = r.Intersect(dst.Bounds()) 76 *r = r.Intersect(src.Bounds().Add(orig.Sub(*sp))) 77 if mask != nil { 78 *r = r.Intersect(mask.Bounds().Add(orig.Sub(*mp))) 79 } 80 dx := r.Min.X - orig.X 81 dy := r.Min.Y - orig.Y 82 if dx == 0 && dy == 0 { 83 return 84 } 85 sp.X += dx 86 sp.Y += dy 87 if mp != nil { 88 mp.X += dx 89 mp.Y += dy 90 } 91} 92 93func processBackward(dst Image, r image.Rectangle, src image.Image, sp image.Point) bool { 94 return image.Image(dst) == src && 95 r.Overlaps(r.Add(sp.Sub(r.Min))) && 96 (sp.Y < r.Min.Y || (sp.Y == r.Min.Y && sp.X < r.Min.X)) 97} 98 99// Draw calls DrawMask with a nil mask. 100func Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point, op Op) { 101 DrawMask(dst, r, src, sp, nil, image.Point{}, op) 102} 103 104// DrawMask aligns r.Min in dst with sp in src and mp in mask and then replaces the rectangle r 105// in dst with the result of a Porter-Duff composition. A nil mask is treated as opaque. 106func DrawMask(dst Image, r image.Rectangle, src image.Image, sp image.Point, mask image.Image, mp image.Point, op Op) { 107 clip(dst, &r, src, &sp, mask, &mp) 108 if r.Empty() { 109 return 110 } 111 112 // Fast paths for special cases. If none of them apply, then we fall back to a general but slow implementation. 113 switch dst0 := dst.(type) { 114 case *image.RGBA: 115 if op == Over { 116 if mask == nil { 117 switch src0 := src.(type) { 118 case *image.Uniform: 119 drawFillOver(dst0, r, src0) 120 return 121 case *image.RGBA: 122 drawCopyOver(dst0, r, src0, sp) 123 return 124 case *image.NRGBA: 125 drawNRGBAOver(dst0, r, src0, sp) 126 return 127 case *image.YCbCr: 128 // An image.YCbCr is always fully opaque, and so if the 129 // mask is nil (i.e. fully opaque) then the op is 130 // effectively always Src. Similarly for image.Gray and 131 // image.CMYK. 132 if imageutil.DrawYCbCr(dst0, r, src0, sp) { 133 return 134 } 135 case *image.Gray: 136 drawGray(dst0, r, src0, sp) 137 return 138 case *image.CMYK: 139 drawCMYK(dst0, r, src0, sp) 140 return 141 } 142 } else if mask0, ok := mask.(*image.Alpha); ok { 143 switch src0 := src.(type) { 144 case *image.Uniform: 145 drawGlyphOver(dst0, r, src0, mask0, mp) 146 return 147 } 148 } 149 } else { 150 if mask == nil { 151 switch src0 := src.(type) { 152 case *image.Uniform: 153 drawFillSrc(dst0, r, src0) 154 return 155 case *image.RGBA: 156 drawCopySrc(dst0, r, src0, sp) 157 return 158 case *image.NRGBA: 159 drawNRGBASrc(dst0, r, src0, sp) 160 return 161 case *image.YCbCr: 162 if imageutil.DrawYCbCr(dst0, r, src0, sp) { 163 return 164 } 165 case *image.Gray: 166 drawGray(dst0, r, src0, sp) 167 return 168 case *image.CMYK: 169 drawCMYK(dst0, r, src0, sp) 170 return 171 } 172 } 173 } 174 drawRGBA(dst0, r, src, sp, mask, mp, op) 175 return 176 case *image.Paletted: 177 if op == Src && mask == nil && !processBackward(dst, r, src, sp) { 178 drawPaletted(dst0, r, src, sp, false) 179 return 180 } 181 } 182 183 x0, x1, dx := r.Min.X, r.Max.X, 1 184 y0, y1, dy := r.Min.Y, r.Max.Y, 1 185 if processBackward(dst, r, src, sp) { 186 x0, x1, dx = x1-1, x0-1, -1 187 y0, y1, dy = y1-1, y0-1, -1 188 } 189 190 var out color.RGBA64 191 sy := sp.Y + y0 - r.Min.Y 192 my := mp.Y + y0 - r.Min.Y 193 for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy { 194 sx := sp.X + x0 - r.Min.X 195 mx := mp.X + x0 - r.Min.X 196 for x := x0; x != x1; x, sx, mx = x+dx, sx+dx, mx+dx { 197 ma := uint32(m) 198 if mask != nil { 199 _, _, _, ma = mask.At(mx, my).RGBA() 200 } 201 switch { 202 case ma == 0: 203 if op == Over { 204 // No-op. 205 } else { 206 dst.Set(x, y, color.Transparent) 207 } 208 case ma == m && op == Src: 209 dst.Set(x, y, src.At(sx, sy)) 210 default: 211 sr, sg, sb, sa := src.At(sx, sy).RGBA() 212 if op == Over { 213 dr, dg, db, da := dst.At(x, y).RGBA() 214 a := m - (sa * ma / m) 215 out.R = uint16((dr*a + sr*ma) / m) 216 out.G = uint16((dg*a + sg*ma) / m) 217 out.B = uint16((db*a + sb*ma) / m) 218 out.A = uint16((da*a + sa*ma) / m) 219 } else { 220 out.R = uint16(sr * ma / m) 221 out.G = uint16(sg * ma / m) 222 out.B = uint16(sb * ma / m) 223 out.A = uint16(sa * ma / m) 224 } 225 // The third argument is &out instead of out (and out is 226 // declared outside of the inner loop) to avoid the implicit 227 // conversion to color.Color here allocating memory in the 228 // inner loop if sizeof(color.RGBA64) > sizeof(uintptr). 229 dst.Set(x, y, &out) 230 } 231 } 232 } 233} 234 235func drawFillOver(dst *image.RGBA, r image.Rectangle, src *image.Uniform) { 236 sr, sg, sb, sa := src.RGBA() 237 // The 0x101 is here for the same reason as in drawRGBA. 238 a := (m - sa) * 0x101 239 i0 := dst.PixOffset(r.Min.X, r.Min.Y) 240 i1 := i0 + r.Dx()*4 241 for y := r.Min.Y; y != r.Max.Y; y++ { 242 for i := i0; i < i1; i += 4 { 243 dr := &dst.Pix[i+0] 244 dg := &dst.Pix[i+1] 245 db := &dst.Pix[i+2] 246 da := &dst.Pix[i+3] 247 248 *dr = uint8((uint32(*dr)*a/m + sr) >> 8) 249 *dg = uint8((uint32(*dg)*a/m + sg) >> 8) 250 *db = uint8((uint32(*db)*a/m + sb) >> 8) 251 *da = uint8((uint32(*da)*a/m + sa) >> 8) 252 } 253 i0 += dst.Stride 254 i1 += dst.Stride 255 } 256} 257 258func drawFillSrc(dst *image.RGBA, r image.Rectangle, src *image.Uniform) { 259 sr, sg, sb, sa := src.RGBA() 260 sr8 := uint8(sr >> 8) 261 sg8 := uint8(sg >> 8) 262 sb8 := uint8(sb >> 8) 263 sa8 := uint8(sa >> 8) 264 // The built-in copy function is faster than a straightforward for loop to fill the destination with 265 // the color, but copy requires a slice source. We therefore use a for loop to fill the first row, and 266 // then use the first row as the slice source for the remaining rows. 267 i0 := dst.PixOffset(r.Min.X, r.Min.Y) 268 i1 := i0 + r.Dx()*4 269 for i := i0; i < i1; i += 4 { 270 dst.Pix[i+0] = sr8 271 dst.Pix[i+1] = sg8 272 dst.Pix[i+2] = sb8 273 dst.Pix[i+3] = sa8 274 } 275 firstRow := dst.Pix[i0:i1] 276 for y := r.Min.Y + 1; y < r.Max.Y; y++ { 277 i0 += dst.Stride 278 i1 += dst.Stride 279 copy(dst.Pix[i0:i1], firstRow) 280 } 281} 282 283func drawCopyOver(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point) { 284 dx, dy := r.Dx(), r.Dy() 285 d0 := dst.PixOffset(r.Min.X, r.Min.Y) 286 s0 := src.PixOffset(sp.X, sp.Y) 287 var ( 288 ddelta, sdelta int 289 i0, i1, idelta int 290 ) 291 if r.Min.Y < sp.Y || r.Min.Y == sp.Y && r.Min.X <= sp.X { 292 ddelta = dst.Stride 293 sdelta = src.Stride 294 i0, i1, idelta = 0, dx*4, +4 295 } else { 296 // If the source start point is higher than the destination start point, or equal height but to the left, 297 // then we compose the rows in right-to-left, bottom-up order instead of left-to-right, top-down. 298 d0 += (dy - 1) * dst.Stride 299 s0 += (dy - 1) * src.Stride 300 ddelta = -dst.Stride 301 sdelta = -src.Stride 302 i0, i1, idelta = (dx-1)*4, -4, -4 303 } 304 for ; dy > 0; dy-- { 305 dpix := dst.Pix[d0:] 306 spix := src.Pix[s0:] 307 for i := i0; i != i1; i += idelta { 308 sr := uint32(spix[i+0]) * 0x101 309 sg := uint32(spix[i+1]) * 0x101 310 sb := uint32(spix[i+2]) * 0x101 311 sa := uint32(spix[i+3]) * 0x101 312 313 dr := &dpix[i+0] 314 dg := &dpix[i+1] 315 db := &dpix[i+2] 316 da := &dpix[i+3] 317 318 // The 0x101 is here for the same reason as in drawRGBA. 319 a := (m - sa) * 0x101 320 321 *dr = uint8((uint32(*dr)*a/m + sr) >> 8) 322 *dg = uint8((uint32(*dg)*a/m + sg) >> 8) 323 *db = uint8((uint32(*db)*a/m + sb) >> 8) 324 *da = uint8((uint32(*da)*a/m + sa) >> 8) 325 } 326 d0 += ddelta 327 s0 += sdelta 328 } 329} 330 331func drawCopySrc(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point) { 332 n, dy := 4*r.Dx(), r.Dy() 333 d0 := dst.PixOffset(r.Min.X, r.Min.Y) 334 s0 := src.PixOffset(sp.X, sp.Y) 335 var ddelta, sdelta int 336 if r.Min.Y <= sp.Y { 337 ddelta = dst.Stride 338 sdelta = src.Stride 339 } else { 340 // If the source start point is higher than the destination start 341 // point, then we compose the rows in bottom-up order instead of 342 // top-down. Unlike the drawCopyOver function, we don't have to check 343 // the x coordinates because the built-in copy function can handle 344 // overlapping slices. 345 d0 += (dy - 1) * dst.Stride 346 s0 += (dy - 1) * src.Stride 347 ddelta = -dst.Stride 348 sdelta = -src.Stride 349 } 350 for ; dy > 0; dy-- { 351 copy(dst.Pix[d0:d0+n], src.Pix[s0:s0+n]) 352 d0 += ddelta 353 s0 += sdelta 354 } 355} 356 357func drawNRGBAOver(dst *image.RGBA, r image.Rectangle, src *image.NRGBA, sp image.Point) { 358 i0 := (r.Min.X - dst.Rect.Min.X) * 4 359 i1 := (r.Max.X - dst.Rect.Min.X) * 4 360 si0 := (sp.X - src.Rect.Min.X) * 4 361 yMax := r.Max.Y - dst.Rect.Min.Y 362 363 y := r.Min.Y - dst.Rect.Min.Y 364 sy := sp.Y - src.Rect.Min.Y 365 for ; y != yMax; y, sy = y+1, sy+1 { 366 dpix := dst.Pix[y*dst.Stride:] 367 spix := src.Pix[sy*src.Stride:] 368 369 for i, si := i0, si0; i < i1; i, si = i+4, si+4 { 370 // Convert from non-premultiplied color to pre-multiplied color. 371 sa := uint32(spix[si+3]) * 0x101 372 sr := uint32(spix[si+0]) * sa / 0xff 373 sg := uint32(spix[si+1]) * sa / 0xff 374 sb := uint32(spix[si+2]) * sa / 0xff 375 376 dr := uint32(dpix[i+0]) 377 dg := uint32(dpix[i+1]) 378 db := uint32(dpix[i+2]) 379 da := uint32(dpix[i+3]) 380 381 // The 0x101 is here for the same reason as in drawRGBA. 382 a := (m - sa) * 0x101 383 384 dpix[i+0] = uint8((dr*a/m + sr) >> 8) 385 dpix[i+1] = uint8((dg*a/m + sg) >> 8) 386 dpix[i+2] = uint8((db*a/m + sb) >> 8) 387 dpix[i+3] = uint8((da*a/m + sa) >> 8) 388 } 389 } 390} 391 392func drawNRGBASrc(dst *image.RGBA, r image.Rectangle, src *image.NRGBA, sp image.Point) { 393 i0 := (r.Min.X - dst.Rect.Min.X) * 4 394 i1 := (r.Max.X - dst.Rect.Min.X) * 4 395 si0 := (sp.X - src.Rect.Min.X) * 4 396 yMax := r.Max.Y - dst.Rect.Min.Y 397 398 y := r.Min.Y - dst.Rect.Min.Y 399 sy := sp.Y - src.Rect.Min.Y 400 for ; y != yMax; y, sy = y+1, sy+1 { 401 dpix := dst.Pix[y*dst.Stride:] 402 spix := src.Pix[sy*src.Stride:] 403 404 for i, si := i0, si0; i < i1; i, si = i+4, si+4 { 405 // Convert from non-premultiplied color to pre-multiplied color. 406 sa := uint32(spix[si+3]) * 0x101 407 sr := uint32(spix[si+0]) * sa / 0xff 408 sg := uint32(spix[si+1]) * sa / 0xff 409 sb := uint32(spix[si+2]) * sa / 0xff 410 411 dpix[i+0] = uint8(sr >> 8) 412 dpix[i+1] = uint8(sg >> 8) 413 dpix[i+2] = uint8(sb >> 8) 414 dpix[i+3] = uint8(sa >> 8) 415 } 416 } 417} 418 419func drawGray(dst *image.RGBA, r image.Rectangle, src *image.Gray, sp image.Point) { 420 i0 := (r.Min.X - dst.Rect.Min.X) * 4 421 i1 := (r.Max.X - dst.Rect.Min.X) * 4 422 si0 := (sp.X - src.Rect.Min.X) * 1 423 yMax := r.Max.Y - dst.Rect.Min.Y 424 425 y := r.Min.Y - dst.Rect.Min.Y 426 sy := sp.Y - src.Rect.Min.Y 427 for ; y != yMax; y, sy = y+1, sy+1 { 428 dpix := dst.Pix[y*dst.Stride:] 429 spix := src.Pix[sy*src.Stride:] 430 431 for i, si := i0, si0; i < i1; i, si = i+4, si+1 { 432 p := spix[si] 433 dpix[i+0] = p 434 dpix[i+1] = p 435 dpix[i+2] = p 436 dpix[i+3] = 255 437 } 438 } 439} 440 441func drawCMYK(dst *image.RGBA, r image.Rectangle, src *image.CMYK, sp image.Point) { 442 i0 := (r.Min.X - dst.Rect.Min.X) * 4 443 i1 := (r.Max.X - dst.Rect.Min.X) * 4 444 si0 := (sp.X - src.Rect.Min.X) * 4 445 yMax := r.Max.Y - dst.Rect.Min.Y 446 447 y := r.Min.Y - dst.Rect.Min.Y 448 sy := sp.Y - src.Rect.Min.Y 449 for ; y != yMax; y, sy = y+1, sy+1 { 450 dpix := dst.Pix[y*dst.Stride:] 451 spix := src.Pix[sy*src.Stride:] 452 453 for i, si := i0, si0; i < i1; i, si = i+4, si+4 { 454 dpix[i+0], dpix[i+1], dpix[i+2] = 455 color.CMYKToRGB(spix[si+0], spix[si+1], spix[si+2], spix[si+3]) 456 dpix[i+3] = 255 457 } 458 } 459} 460 461func drawGlyphOver(dst *image.RGBA, r image.Rectangle, src *image.Uniform, mask *image.Alpha, mp image.Point) { 462 i0 := dst.PixOffset(r.Min.X, r.Min.Y) 463 i1 := i0 + r.Dx()*4 464 mi0 := mask.PixOffset(mp.X, mp.Y) 465 sr, sg, sb, sa := src.RGBA() 466 for y, my := r.Min.Y, mp.Y; y != r.Max.Y; y, my = y+1, my+1 { 467 for i, mi := i0, mi0; i < i1; i, mi = i+4, mi+1 { 468 ma := uint32(mask.Pix[mi]) 469 if ma == 0 { 470 continue 471 } 472 ma |= ma << 8 473 474 dr := &dst.Pix[i+0] 475 dg := &dst.Pix[i+1] 476 db := &dst.Pix[i+2] 477 da := &dst.Pix[i+3] 478 479 // The 0x101 is here for the same reason as in drawRGBA. 480 a := (m - (sa * ma / m)) * 0x101 481 482 *dr = uint8((uint32(*dr)*a + sr*ma) / m >> 8) 483 *dg = uint8((uint32(*dg)*a + sg*ma) / m >> 8) 484 *db = uint8((uint32(*db)*a + sb*ma) / m >> 8) 485 *da = uint8((uint32(*da)*a + sa*ma) / m >> 8) 486 } 487 i0 += dst.Stride 488 i1 += dst.Stride 489 mi0 += mask.Stride 490 } 491} 492 493func drawRGBA(dst *image.RGBA, r image.Rectangle, src image.Image, sp image.Point, mask image.Image, mp image.Point, op Op) { 494 x0, x1, dx := r.Min.X, r.Max.X, 1 495 y0, y1, dy := r.Min.Y, r.Max.Y, 1 496 if image.Image(dst) == src && r.Overlaps(r.Add(sp.Sub(r.Min))) { 497 if sp.Y < r.Min.Y || sp.Y == r.Min.Y && sp.X < r.Min.X { 498 x0, x1, dx = x1-1, x0-1, -1 499 y0, y1, dy = y1-1, y0-1, -1 500 } 501 } 502 503 sy := sp.Y + y0 - r.Min.Y 504 my := mp.Y + y0 - r.Min.Y 505 sx0 := sp.X + x0 - r.Min.X 506 mx0 := mp.X + x0 - r.Min.X 507 sx1 := sx0 + (x1 - x0) 508 i0 := dst.PixOffset(x0, y0) 509 di := dx * 4 510 for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy { 511 for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx { 512 ma := uint32(m) 513 if mask != nil { 514 _, _, _, ma = mask.At(mx, my).RGBA() 515 } 516 sr, sg, sb, sa := src.At(sx, sy).RGBA() 517 if op == Over { 518 dr := uint32(dst.Pix[i+0]) 519 dg := uint32(dst.Pix[i+1]) 520 db := uint32(dst.Pix[i+2]) 521 da := uint32(dst.Pix[i+3]) 522 523 // dr, dg, db and da are all 8-bit color at the moment, ranging in [0,255]. 524 // We work in 16-bit color, and so would normally do: 525 // dr |= dr << 8 526 // and similarly for dg, db and da, but instead we multiply a 527 // (which is a 16-bit color, ranging in [0,65535]) by 0x101. 528 // This yields the same result, but is fewer arithmetic operations. 529 a := (m - (sa * ma / m)) * 0x101 530 531 dst.Pix[i+0] = uint8((dr*a + sr*ma) / m >> 8) 532 dst.Pix[i+1] = uint8((dg*a + sg*ma) / m >> 8) 533 dst.Pix[i+2] = uint8((db*a + sb*ma) / m >> 8) 534 dst.Pix[i+3] = uint8((da*a + sa*ma) / m >> 8) 535 536 } else { 537 dst.Pix[i+0] = uint8(sr * ma / m >> 8) 538 dst.Pix[i+1] = uint8(sg * ma / m >> 8) 539 dst.Pix[i+2] = uint8(sb * ma / m >> 8) 540 dst.Pix[i+3] = uint8(sa * ma / m >> 8) 541 } 542 } 543 i0 += dy * dst.Stride 544 } 545} 546 547// clamp clamps i to the interval [0, 0xffff]. 548func clamp(i int32) int32 { 549 if i < 0 { 550 return 0 551 } 552 if i > 0xffff { 553 return 0xffff 554 } 555 return i 556} 557 558// sqDiff returns the squared-difference of x and y, shifted by 2 so that 559// adding four of those won't overflow a uint32. 560// 561// x and y are both assumed to be in the range [0, 0xffff]. 562func sqDiff(x, y int32) uint32 { 563 var d uint32 564 if x > y { 565 d = uint32(x - y) 566 } else { 567 d = uint32(y - x) 568 } 569 return (d * d) >> 2 570} 571 572func drawPaletted(dst Image, r image.Rectangle, src image.Image, sp image.Point, floydSteinberg bool) { 573 // TODO(nigeltao): handle the case where the dst and src overlap. 574 // Does it even make sense to try and do Floyd-Steinberg whilst 575 // walking the image backward (right-to-left bottom-to-top)? 576 577 // If dst is an *image.Paletted, we have a fast path for dst.Set and 578 // dst.At. The dst.Set equivalent is a batch version of the algorithm 579 // used by color.Palette's Index method in image/color/color.go, plus 580 // optional Floyd-Steinberg error diffusion. 581 palette, pix, stride := [][4]int32(nil), []byte(nil), 0 582 if p, ok := dst.(*image.Paletted); ok { 583 palette = make([][4]int32, len(p.Palette)) 584 for i, col := range p.Palette { 585 r, g, b, a := col.RGBA() 586 palette[i][0] = int32(r) 587 palette[i][1] = int32(g) 588 palette[i][2] = int32(b) 589 palette[i][3] = int32(a) 590 } 591 pix, stride = p.Pix[p.PixOffset(r.Min.X, r.Min.Y):], p.Stride 592 } 593 594 // quantErrorCurr and quantErrorNext are the Floyd-Steinberg quantization 595 // errors that have been propagated to the pixels in the current and next 596 // rows. The +2 simplifies calculation near the edges. 597 var quantErrorCurr, quantErrorNext [][4]int32 598 if floydSteinberg { 599 quantErrorCurr = make([][4]int32, r.Dx()+2) 600 quantErrorNext = make([][4]int32, r.Dx()+2) 601 } 602 603 // Loop over each source pixel. 604 out := color.RGBA64{A: 0xffff} 605 for y := 0; y != r.Dy(); y++ { 606 for x := 0; x != r.Dx(); x++ { 607 // er, eg and eb are the pixel's R,G,B values plus the 608 // optional Floyd-Steinberg error. 609 sr, sg, sb, sa := src.At(sp.X+x, sp.Y+y).RGBA() 610 er, eg, eb, ea := int32(sr), int32(sg), int32(sb), int32(sa) 611 if floydSteinberg { 612 er = clamp(er + quantErrorCurr[x+1][0]/16) 613 eg = clamp(eg + quantErrorCurr[x+1][1]/16) 614 eb = clamp(eb + quantErrorCurr[x+1][2]/16) 615 ea = clamp(ea + quantErrorCurr[x+1][3]/16) 616 } 617 618 if palette != nil { 619 // Find the closest palette color in Euclidean R,G,B,A space: 620 // the one that minimizes sum-squared-difference. 621 // TODO(nigeltao): consider smarter algorithms. 622 bestIndex, bestSum := 0, uint32(1<<32-1) 623 for index, p := range palette { 624 sum := sqDiff(er, p[0]) + sqDiff(eg, p[1]) + sqDiff(eb, p[2]) + sqDiff(ea, p[3]) 625 if sum < bestSum { 626 bestIndex, bestSum = index, sum 627 if sum == 0 { 628 break 629 } 630 } 631 } 632 pix[y*stride+x] = byte(bestIndex) 633 634 if !floydSteinberg { 635 continue 636 } 637 er -= int32(palette[bestIndex][0]) 638 eg -= int32(palette[bestIndex][1]) 639 eb -= int32(palette[bestIndex][2]) 640 ea -= int32(palette[bestIndex][3]) 641 642 } else { 643 out.R = uint16(er) 644 out.G = uint16(eg) 645 out.B = uint16(eb) 646 out.A = uint16(ea) 647 // The third argument is &out instead of out (and out is 648 // declared outside of the inner loop) to avoid the implicit 649 // conversion to color.Color here allocating memory in the 650 // inner loop if sizeof(color.RGBA64) > sizeof(uintptr). 651 dst.Set(r.Min.X+x, r.Min.Y+y, &out) 652 653 if !floydSteinberg { 654 continue 655 } 656 sr, sg, sb, sa = dst.At(r.Min.X+x, r.Min.Y+y).RGBA() 657 er -= int32(sr) 658 eg -= int32(sg) 659 eb -= int32(sb) 660 ea -= int32(sa) 661 } 662 663 // Propagate the Floyd-Steinberg quantization error. 664 quantErrorNext[x+0][0] += er * 3 665 quantErrorNext[x+0][1] += eg * 3 666 quantErrorNext[x+0][2] += eb * 3 667 quantErrorNext[x+0][3] += ea * 3 668 quantErrorNext[x+1][0] += er * 5 669 quantErrorNext[x+1][1] += eg * 5 670 quantErrorNext[x+1][2] += eb * 5 671 quantErrorNext[x+1][3] += ea * 5 672 quantErrorNext[x+2][0] += er * 1 673 quantErrorNext[x+2][1] += eg * 1 674 quantErrorNext[x+2][2] += eb * 1 675 quantErrorNext[x+2][3] += ea * 1 676 quantErrorCurr[x+2][0] += er * 7 677 quantErrorCurr[x+2][1] += eg * 7 678 quantErrorCurr[x+2][2] += eb * 7 679 quantErrorCurr[x+2][3] += ea * 7 680 } 681 682 // Recycle the quantization error buffers. 683 if floydSteinberg { 684 quantErrorCurr, quantErrorNext = quantErrorNext, quantErrorCurr 685 for i := range quantErrorNext { 686 quantErrorNext[i] = [4]int32{} 687 } 688 } 689 } 690} 691