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