Source file src/image/draw/draw.go

Documentation: image/draw

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

View as plain text