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.Image, r image.Rectangle, src image.Image, sp image.Point) bool { 94 return 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 sr, sg, sb, sa := src0.RGBA() 120 if sa == 0xffff { 121 drawFillSrc(dst0, r, sr, sg, sb, sa) 122 } else { 123 drawFillOver(dst0, r, sr, sg, sb, sa) 124 } 125 return 126 case *image.RGBA: 127 drawCopyOver(dst0, r, src0, sp) 128 return 129 case *image.NRGBA: 130 drawNRGBAOver(dst0, r, src0, sp) 131 return 132 case *image.YCbCr: 133 // An image.YCbCr is always fully opaque, and so if the 134 // mask is nil (i.e. fully opaque) then the op is 135 // effectively always Src. Similarly for image.Gray and 136 // image.CMYK. 137 if imageutil.DrawYCbCr(dst0, r, src0, sp) { 138 return 139 } 140 case *image.Gray: 141 drawGray(dst0, r, src0, sp) 142 return 143 case *image.CMYK: 144 drawCMYK(dst0, r, src0, sp) 145 return 146 } 147 } else if mask0, ok := mask.(*image.Alpha); ok { 148 switch src0 := src.(type) { 149 case *image.Uniform: 150 drawGlyphOver(dst0, r, src0, mask0, mp) 151 return 152 } 153 } 154 } else { 155 if mask == nil { 156 switch src0 := src.(type) { 157 case *image.Uniform: 158 sr, sg, sb, sa := src0.RGBA() 159 drawFillSrc(dst0, r, sr, sg, sb, sa) 160 return 161 case *image.RGBA: 162 drawCopySrc(dst0, r, src0, sp) 163 return 164 case *image.NRGBA: 165 drawNRGBASrc(dst0, r, src0, sp) 166 return 167 case *image.YCbCr: 168 if imageutil.DrawYCbCr(dst0, r, src0, sp) { 169 return 170 } 171 case *image.Gray: 172 drawGray(dst0, r, src0, sp) 173 return 174 case *image.CMYK: 175 drawCMYK(dst0, r, src0, sp) 176 return 177 } 178 } 179 } 180 drawRGBA(dst0, r, src, sp, mask, mp, op) 181 return 182 case *image.Paletted: 183 if op == Src && mask == nil && !processBackward(dst, r, src, sp) { 184 drawPaletted(dst0, r, src, sp, false) 185 return 186 } 187 } 188 189 x0, x1, dx := r.Min.X, r.Max.X, 1 190 y0, y1, dy := r.Min.Y, r.Max.Y, 1 191 if processBackward(dst, r, src, sp) { 192 x0, x1, dx = x1-1, x0-1, -1 193 y0, y1, dy = y1-1, y0-1, -1 194 } 195 196 var out color.RGBA64 197 sy := sp.Y + y0 - r.Min.Y 198 my := mp.Y + y0 - r.Min.Y 199 for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy { 200 sx := sp.X + x0 - r.Min.X 201 mx := mp.X + x0 - r.Min.X 202 for x := x0; x != x1; x, sx, mx = x+dx, sx+dx, mx+dx { 203 ma := uint32(m) 204 if mask != nil { 205 _, _, _, ma = mask.At(mx, my).RGBA() 206 } 207 switch { 208 case ma == 0: 209 if op == Over { 210 // No-op. 211 } else { 212 dst.Set(x, y, color.Transparent) 213 } 214 case ma == m && op == Src: 215 dst.Set(x, y, src.At(sx, sy)) 216 default: 217 sr, sg, sb, sa := src.At(sx, sy).RGBA() 218 if op == Over { 219 dr, dg, db, da := dst.At(x, y).RGBA() 220 a := m - (sa * ma / m) 221 out.R = uint16((dr*a + sr*ma) / m) 222 out.G = uint16((dg*a + sg*ma) / m) 223 out.B = uint16((db*a + sb*ma) / m) 224 out.A = uint16((da*a + sa*ma) / m) 225 } else { 226 out.R = uint16(sr * ma / m) 227 out.G = uint16(sg * ma / m) 228 out.B = uint16(sb * ma / m) 229 out.A = uint16(sa * ma / m) 230 } 231 // The third argument is &out instead of out (and out is 232 // declared outside of the inner loop) to avoid the implicit 233 // conversion to color.Color here allocating memory in the 234 // inner loop if sizeof(color.RGBA64) > sizeof(uintptr). 235 dst.Set(x, y, &out) 236 } 237 } 238 } 239} 240 241func drawFillOver(dst *image.RGBA, r image.Rectangle, sr, sg, sb, sa uint32) { 242 // The 0x101 is here for the same reason as in drawRGBA. 243 a := (m - sa) * 0x101 244 i0 := dst.PixOffset(r.Min.X, r.Min.Y) 245 i1 := i0 + r.Dx()*4 246 for y := r.Min.Y; y != r.Max.Y; y++ { 247 for i := i0; i < i1; i += 4 { 248 dr := &dst.Pix[i+0] 249 dg := &dst.Pix[i+1] 250 db := &dst.Pix[i+2] 251 da := &dst.Pix[i+3] 252 253 *dr = uint8((uint32(*dr)*a/m + sr) >> 8) 254 *dg = uint8((uint32(*dg)*a/m + sg) >> 8) 255 *db = uint8((uint32(*db)*a/m + sb) >> 8) 256 *da = uint8((uint32(*da)*a/m + sa) >> 8) 257 } 258 i0 += dst.Stride 259 i1 += dst.Stride 260 } 261} 262 263func drawFillSrc(dst *image.RGBA, r image.Rectangle, sr, sg, sb, sa uint32) { 264 sr8 := uint8(sr >> 8) 265 sg8 := uint8(sg >> 8) 266 sb8 := uint8(sb >> 8) 267 sa8 := uint8(sa >> 8) 268 // The built-in copy function is faster than a straightforward for loop to fill the destination with 269 // the color, but copy requires a slice source. We therefore use a for loop to fill the first row, and 270 // then use the first row as the slice source for the remaining rows. 271 i0 := dst.PixOffset(r.Min.X, r.Min.Y) 272 i1 := i0 + r.Dx()*4 273 for i := i0; i < i1; i += 4 { 274 dst.Pix[i+0] = sr8 275 dst.Pix[i+1] = sg8 276 dst.Pix[i+2] = sb8 277 dst.Pix[i+3] = sa8 278 } 279 firstRow := dst.Pix[i0:i1] 280 for y := r.Min.Y + 1; y < r.Max.Y; y++ { 281 i0 += dst.Stride 282 i1 += dst.Stride 283 copy(dst.Pix[i0:i1], firstRow) 284 } 285} 286 287func drawCopyOver(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point) { 288 dx, dy := r.Dx(), r.Dy() 289 d0 := dst.PixOffset(r.Min.X, r.Min.Y) 290 s0 := src.PixOffset(sp.X, sp.Y) 291 var ( 292 ddelta, sdelta int 293 i0, i1, idelta int 294 ) 295 if r.Min.Y < sp.Y || r.Min.Y == sp.Y && r.Min.X <= sp.X { 296 ddelta = dst.Stride 297 sdelta = src.Stride 298 i0, i1, idelta = 0, dx*4, +4 299 } else { 300 // If the source start point is higher than the destination start point, or equal height but to the left, 301 // then we compose the rows in right-to-left, bottom-up order instead of left-to-right, top-down. 302 d0 += (dy - 1) * dst.Stride 303 s0 += (dy - 1) * src.Stride 304 ddelta = -dst.Stride 305 sdelta = -src.Stride 306 i0, i1, idelta = (dx-1)*4, -4, -4 307 } 308 for ; dy > 0; dy-- { 309 dpix := dst.Pix[d0:] 310 spix := src.Pix[s0:] 311 for i := i0; i != i1; i += idelta { 312 s := spix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857 313 sr := uint32(s[0]) * 0x101 314 sg := uint32(s[1]) * 0x101 315 sb := uint32(s[2]) * 0x101 316 sa := uint32(s[3]) * 0x101 317 318 // The 0x101 is here for the same reason as in drawRGBA. 319 a := (m - sa) * 0x101 320 321 d := dpix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857 322 d[0] = uint8((uint32(d[0])*a/m + sr) >> 8) 323 d[1] = uint8((uint32(d[1])*a/m + sg) >> 8) 324 d[2] = uint8((uint32(d[2])*a/m + sb) >> 8) 325 d[3] = uint8((uint32(d[3])*a/m + sa) >> 8) 326 } 327 d0 += ddelta 328 s0 += sdelta 329 } 330} 331 332func drawCopySrc(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point) { 333 n, dy := 4*r.Dx(), r.Dy() 334 d0 := dst.PixOffset(r.Min.X, r.Min.Y) 335 s0 := src.PixOffset(sp.X, sp.Y) 336 var ddelta, sdelta int 337 if r.Min.Y <= sp.Y { 338 ddelta = dst.Stride 339 sdelta = src.Stride 340 } else { 341 // If the source start point is higher than the destination start 342 // point, then we compose the rows in bottom-up order instead of 343 // top-down. Unlike the drawCopyOver function, we don't have to check 344 // the x coordinates because the built-in copy function can handle 345 // overlapping slices. 346 d0 += (dy - 1) * dst.Stride 347 s0 += (dy - 1) * src.Stride 348 ddelta = -dst.Stride 349 sdelta = -src.Stride 350 } 351 for ; dy > 0; dy-- { 352 copy(dst.Pix[d0:d0+n], src.Pix[s0:s0+n]) 353 d0 += ddelta 354 s0 += sdelta 355 } 356} 357 358func drawNRGBAOver(dst *image.RGBA, r image.Rectangle, src *image.NRGBA, sp image.Point) { 359 i0 := (r.Min.X - dst.Rect.Min.X) * 4 360 i1 := (r.Max.X - dst.Rect.Min.X) * 4 361 si0 := (sp.X - src.Rect.Min.X) * 4 362 yMax := r.Max.Y - dst.Rect.Min.Y 363 364 y := r.Min.Y - dst.Rect.Min.Y 365 sy := sp.Y - src.Rect.Min.Y 366 for ; y != yMax; y, sy = y+1, sy+1 { 367 dpix := dst.Pix[y*dst.Stride:] 368 spix := src.Pix[sy*src.Stride:] 369 370 for i, si := i0, si0; i < i1; i, si = i+4, si+4 { 371 // Convert from non-premultiplied color to pre-multiplied color. 372 s := spix[si : si+4 : si+4] // Small cap improves performance, see https://golang.org/issue/27857 373 sa := uint32(s[3]) * 0x101 374 sr := uint32(s[0]) * sa / 0xff 375 sg := uint32(s[1]) * sa / 0xff 376 sb := uint32(s[2]) * sa / 0xff 377 378 d := dpix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857 379 dr := uint32(d[0]) 380 dg := uint32(d[1]) 381 db := uint32(d[2]) 382 da := uint32(d[3]) 383 384 // The 0x101 is here for the same reason as in drawRGBA. 385 a := (m - sa) * 0x101 386 387 d[0] = uint8((dr*a/m + sr) >> 8) 388 d[1] = uint8((dg*a/m + sg) >> 8) 389 d[2] = uint8((db*a/m + sb) >> 8) 390 d[3] = uint8((da*a/m + sa) >> 8) 391 } 392 } 393} 394 395func drawNRGBASrc(dst *image.RGBA, r image.Rectangle, src *image.NRGBA, sp image.Point) { 396 i0 := (r.Min.X - dst.Rect.Min.X) * 4 397 i1 := (r.Max.X - dst.Rect.Min.X) * 4 398 si0 := (sp.X - src.Rect.Min.X) * 4 399 yMax := r.Max.Y - dst.Rect.Min.Y 400 401 y := r.Min.Y - dst.Rect.Min.Y 402 sy := sp.Y - src.Rect.Min.Y 403 for ; y != yMax; y, sy = y+1, sy+1 { 404 dpix := dst.Pix[y*dst.Stride:] 405 spix := src.Pix[sy*src.Stride:] 406 407 for i, si := i0, si0; i < i1; i, si = i+4, si+4 { 408 // Convert from non-premultiplied color to pre-multiplied color. 409 s := spix[si : si+4 : si+4] // Small cap improves performance, see https://golang.org/issue/27857 410 sa := uint32(s[3]) * 0x101 411 sr := uint32(s[0]) * sa / 0xff 412 sg := uint32(s[1]) * sa / 0xff 413 sb := uint32(s[2]) * sa / 0xff 414 415 d := dpix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857 416 d[0] = uint8(sr >> 8) 417 d[1] = uint8(sg >> 8) 418 d[2] = uint8(sb >> 8) 419 d[3] = uint8(sa >> 8) 420 } 421 } 422} 423 424func drawGray(dst *image.RGBA, r image.Rectangle, src *image.Gray, sp image.Point) { 425 i0 := (r.Min.X - dst.Rect.Min.X) * 4 426 i1 := (r.Max.X - dst.Rect.Min.X) * 4 427 si0 := (sp.X - src.Rect.Min.X) * 1 428 yMax := r.Max.Y - dst.Rect.Min.Y 429 430 y := r.Min.Y - dst.Rect.Min.Y 431 sy := sp.Y - src.Rect.Min.Y 432 for ; y != yMax; y, sy = y+1, sy+1 { 433 dpix := dst.Pix[y*dst.Stride:] 434 spix := src.Pix[sy*src.Stride:] 435 436 for i, si := i0, si0; i < i1; i, si = i+4, si+1 { 437 p := spix[si] 438 d := dpix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857 439 d[0] = p 440 d[1] = p 441 d[2] = p 442 d[3] = 255 443 } 444 } 445} 446 447func drawCMYK(dst *image.RGBA, r image.Rectangle, src *image.CMYK, sp image.Point) { 448 i0 := (r.Min.X - dst.Rect.Min.X) * 4 449 i1 := (r.Max.X - dst.Rect.Min.X) * 4 450 si0 := (sp.X - src.Rect.Min.X) * 4 451 yMax := r.Max.Y - dst.Rect.Min.Y 452 453 y := r.Min.Y - dst.Rect.Min.Y 454 sy := sp.Y - src.Rect.Min.Y 455 for ; y != yMax; y, sy = y+1, sy+1 { 456 dpix := dst.Pix[y*dst.Stride:] 457 spix := src.Pix[sy*src.Stride:] 458 459 for i, si := i0, si0; i < i1; i, si = i+4, si+4 { 460 s := spix[si : si+4 : si+4] // Small cap improves performance, see https://golang.org/issue/27857 461 d := dpix[i : i+4 : i+4] 462 d[0], d[1], d[2] = color.CMYKToRGB(s[0], s[1], s[2], s[3]) 463 d[3] = 255 464 } 465 } 466} 467 468func drawGlyphOver(dst *image.RGBA, r image.Rectangle, src *image.Uniform, mask *image.Alpha, mp image.Point) { 469 i0 := dst.PixOffset(r.Min.X, r.Min.Y) 470 i1 := i0 + r.Dx()*4 471 mi0 := mask.PixOffset(mp.X, mp.Y) 472 sr, sg, sb, sa := src.RGBA() 473 for y, my := r.Min.Y, mp.Y; y != r.Max.Y; y, my = y+1, my+1 { 474 for i, mi := i0, mi0; i < i1; i, mi = i+4, mi+1 { 475 ma := uint32(mask.Pix[mi]) 476 if ma == 0 { 477 continue 478 } 479 ma |= ma << 8 480 481 // The 0x101 is here for the same reason as in drawRGBA. 482 a := (m - (sa * ma / m)) * 0x101 483 484 d := dst.Pix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857 485 d[0] = uint8((uint32(d[0])*a + sr*ma) / m >> 8) 486 d[1] = uint8((uint32(d[1])*a + sg*ma) / m >> 8) 487 d[2] = uint8((uint32(d[2])*a + sb*ma) / m >> 8) 488 d[3] = uint8((uint32(d[3])*a + sa*ma) / m >> 8) 489 } 490 i0 += dst.Stride 491 i1 += dst.Stride 492 mi0 += mask.Stride 493 } 494} 495 496func drawRGBA(dst *image.RGBA, r image.Rectangle, src image.Image, sp image.Point, mask image.Image, mp image.Point, op Op) { 497 x0, x1, dx := r.Min.X, r.Max.X, 1 498 y0, y1, dy := r.Min.Y, r.Max.Y, 1 499 if image.Image(dst) == src && r.Overlaps(r.Add(sp.Sub(r.Min))) { 500 if sp.Y < r.Min.Y || sp.Y == r.Min.Y && sp.X < r.Min.X { 501 x0, x1, dx = x1-1, x0-1, -1 502 y0, y1, dy = y1-1, y0-1, -1 503 } 504 } 505 506 sy := sp.Y + y0 - r.Min.Y 507 my := mp.Y + y0 - r.Min.Y 508 sx0 := sp.X + x0 - r.Min.X 509 mx0 := mp.X + x0 - r.Min.X 510 sx1 := sx0 + (x1 - x0) 511 i0 := dst.PixOffset(x0, y0) 512 di := dx * 4 513 for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy { 514 for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx { 515 ma := uint32(m) 516 if mask != nil { 517 _, _, _, ma = mask.At(mx, my).RGBA() 518 } 519 sr, sg, sb, sa := src.At(sx, sy).RGBA() 520 d := dst.Pix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857 521 if op == Over { 522 dr := uint32(d[0]) 523 dg := uint32(d[1]) 524 db := uint32(d[2]) 525 da := uint32(d[3]) 526 527 // dr, dg, db and da are all 8-bit color at the moment, ranging in [0,255]. 528 // We work in 16-bit color, and so would normally do: 529 // dr |= dr << 8 530 // and similarly for dg, db and da, but instead we multiply a 531 // (which is a 16-bit color, ranging in [0,65535]) by 0x101. 532 // This yields the same result, but is fewer arithmetic operations. 533 a := (m - (sa * ma / m)) * 0x101 534 535 d[0] = uint8((dr*a + sr*ma) / m >> 8) 536 d[1] = uint8((dg*a + sg*ma) / m >> 8) 537 d[2] = uint8((db*a + sb*ma) / m >> 8) 538 d[3] = uint8((da*a + sa*ma) / m >> 8) 539 540 } else { 541 d[0] = uint8(sr * ma / m >> 8) 542 d[1] = uint8(sg * ma / m >> 8) 543 d[2] = uint8(sb * ma / m >> 8) 544 d[3] = uint8(sa * ma / m >> 8) 545 } 546 } 547 i0 += dy * dst.Stride 548 } 549} 550 551// clamp clamps i to the interval [0, 0xffff]. 552func clamp(i int32) int32 { 553 if i < 0 { 554 return 0 555 } 556 if i > 0xffff { 557 return 0xffff 558 } 559 return i 560} 561 562// sqDiff returns the squared-difference of x and y, shifted by 2 so that 563// adding four of those won't overflow a uint32. 564// 565// x and y are both assumed to be in the range [0, 0xffff]. 566func sqDiff(x, y int32) uint32 { 567 // This is an optimized code relying on the overflow/wrap around 568 // properties of unsigned integers operations guaranteed by the language 569 // spec. See sqDiff from the image/color package for more details. 570 d := uint32(x - y) 571 return (d * d) >> 2 572} 573 574func drawPaletted(dst Image, r image.Rectangle, src image.Image, sp image.Point, floydSteinberg bool) { 575 // TODO(nigeltao): handle the case where the dst and src overlap. 576 // Does it even make sense to try and do Floyd-Steinberg whilst 577 // walking the image backward (right-to-left bottom-to-top)? 578 579 // If dst is an *image.Paletted, we have a fast path for dst.Set and 580 // dst.At. The dst.Set equivalent is a batch version of the algorithm 581 // used by color.Palette's Index method in image/color/color.go, plus 582 // optional Floyd-Steinberg error diffusion. 583 palette, pix, stride := [][4]int32(nil), []byte(nil), 0 584 if p, ok := dst.(*image.Paletted); ok { 585 palette = make([][4]int32, len(p.Palette)) 586 for i, col := range p.Palette { 587 r, g, b, a := col.RGBA() 588 palette[i][0] = int32(r) 589 palette[i][1] = int32(g) 590 palette[i][2] = int32(b) 591 palette[i][3] = int32(a) 592 } 593 pix, stride = p.Pix[p.PixOffset(r.Min.X, r.Min.Y):], p.Stride 594 } 595 596 // quantErrorCurr and quantErrorNext are the Floyd-Steinberg quantization 597 // errors that have been propagated to the pixels in the current and next 598 // rows. The +2 simplifies calculation near the edges. 599 var quantErrorCurr, quantErrorNext [][4]int32 600 if floydSteinberg { 601 quantErrorCurr = make([][4]int32, r.Dx()+2) 602 quantErrorNext = make([][4]int32, r.Dx()+2) 603 } 604 pxRGBA := func(x, y int) (r, g, b, a uint32) { return src.At(x, y).RGBA() } 605 // Fast paths for special cases to avoid excessive use of the color.Color 606 // interface which escapes to the heap but need to be discovered for 607 // each pixel on r. See also https://golang.org/issues/15759. 608 switch src0 := src.(type) { 609 case *image.RGBA: 610 pxRGBA = func(x, y int) (r, g, b, a uint32) { return src0.RGBAAt(x, y).RGBA() } 611 case *image.NRGBA: 612 pxRGBA = func(x, y int) (r, g, b, a uint32) { return src0.NRGBAAt(x, y).RGBA() } 613 case *image.YCbCr: 614 pxRGBA = func(x, y int) (r, g, b, a uint32) { return src0.YCbCrAt(x, y).RGBA() } 615 } 616 617 // Loop over each source pixel. 618 out := color.RGBA64{A: 0xffff} 619 for y := 0; y != r.Dy(); y++ { 620 for x := 0; x != r.Dx(); x++ { 621 // er, eg and eb are the pixel's R,G,B values plus the 622 // optional Floyd-Steinberg error. 623 sr, sg, sb, sa := pxRGBA(sp.X+x, sp.Y+y) 624 er, eg, eb, ea := int32(sr), int32(sg), int32(sb), int32(sa) 625 if floydSteinberg { 626 er = clamp(er + quantErrorCurr[x+1][0]/16) 627 eg = clamp(eg + quantErrorCurr[x+1][1]/16) 628 eb = clamp(eb + quantErrorCurr[x+1][2]/16) 629 ea = clamp(ea + quantErrorCurr[x+1][3]/16) 630 } 631 632 if palette != nil { 633 // Find the closest palette color in Euclidean R,G,B,A space: 634 // the one that minimizes sum-squared-difference. 635 // TODO(nigeltao): consider smarter algorithms. 636 bestIndex, bestSum := 0, uint32(1<<32-1) 637 for index, p := range palette { 638 sum := sqDiff(er, p[0]) + sqDiff(eg, p[1]) + sqDiff(eb, p[2]) + sqDiff(ea, p[3]) 639 if sum < bestSum { 640 bestIndex, bestSum = index, sum 641 if sum == 0 { 642 break 643 } 644 } 645 } 646 pix[y*stride+x] = byte(bestIndex) 647 648 if !floydSteinberg { 649 continue 650 } 651 er -= palette[bestIndex][0] 652 eg -= palette[bestIndex][1] 653 eb -= palette[bestIndex][2] 654 ea -= palette[bestIndex][3] 655 656 } else { 657 out.R = uint16(er) 658 out.G = uint16(eg) 659 out.B = uint16(eb) 660 out.A = uint16(ea) 661 // The third argument is &out instead of out (and out is 662 // declared outside of the inner loop) to avoid the implicit 663 // conversion to color.Color here allocating memory in the 664 // inner loop if sizeof(color.RGBA64) > sizeof(uintptr). 665 dst.Set(r.Min.X+x, r.Min.Y+y, &out) 666 667 if !floydSteinberg { 668 continue 669 } 670 sr, sg, sb, sa = dst.At(r.Min.X+x, r.Min.Y+y).RGBA() 671 er -= int32(sr) 672 eg -= int32(sg) 673 eb -= int32(sb) 674 ea -= int32(sa) 675 } 676 677 // Propagate the Floyd-Steinberg quantization error. 678 quantErrorNext[x+0][0] += er * 3 679 quantErrorNext[x+0][1] += eg * 3 680 quantErrorNext[x+0][2] += eb * 3 681 quantErrorNext[x+0][3] += ea * 3 682 quantErrorNext[x+1][0] += er * 5 683 quantErrorNext[x+1][1] += eg * 5 684 quantErrorNext[x+1][2] += eb * 5 685 quantErrorNext[x+1][3] += ea * 5 686 quantErrorNext[x+2][0] += er * 1 687 quantErrorNext[x+2][1] += eg * 1 688 quantErrorNext[x+2][2] += eb * 1 689 quantErrorNext[x+2][3] += ea * 1 690 quantErrorCurr[x+2][0] += er * 7 691 quantErrorCurr[x+2][1] += eg * 7 692 quantErrorCurr[x+2][2] += eb * 7 693 quantErrorCurr[x+2][3] += ea * 7 694 } 695 696 // Recycle the quantization error buffers. 697 if floydSteinberg { 698 quantErrorCurr, quantErrorNext = quantErrorNext, quantErrorCurr 699 for i := range quantErrorNext { 700 quantErrorNext[i] = [4]int32{} 701 } 702 } 703 } 704} 705