draw.go

     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
   123  	// to general but slower implementations.
   124  	//
   125  	// For NRGBA and NRGBA64 image types, the code paths aren't just faster.
   126  	// They also avoid the information loss that would otherwise occur from
   127  	// converting non-alpha-premultiplied color to and from alpha-premultiplied
   128  	// color. See TestDrawSrcNonpremultiplied.
   129  	switch dst0 := dst.(type) {
   130  	case *image.RGBA:
   131  		if op == Over {
   132  			if mask == nil {
   133  				switch src0 := src.(type) {
   134  				case *image.Uniform:
   135  					sr, sg, sb, sa := src0.RGBA()
   136  					if sa == 0xffff {
   137  						drawFillSrc(dst0, r, sr, sg, sb, sa)
   138  					} else {
   139  						drawFillOver(dst0, r, sr, sg, sb, sa)
   140  					}
   141  					return
   142  				case *image.RGBA:
   143  					drawCopyOver(dst0, r, src0, sp)
   144  					return
   145  				case *image.NRGBA:
   146  					drawNRGBAOver(dst0, r, src0, sp)
   147  					return
   148  				case *image.YCbCr:
   149  					// An image.YCbCr is always fully opaque, and so if the
   150  					// mask is nil (i.e. fully opaque) then the op is
   151  					// effectively always Src. Similarly for image.Gray and
   152  					// image.CMYK.
   153  					if imageutil.DrawYCbCr(dst0, r, src0, sp) {
   154  						return
   155  					}
   156  				case *image.Gray:
   157  					drawGray(dst0, r, src0, sp)
   158  					return
   159  				case *image.CMYK:
   160  					drawCMYK(dst0, r, src0, sp)
   161  					return
   162  				}
   163  			} else if mask0, ok := mask.(*image.Alpha); ok {
   164  				switch src0 := src.(type) {
   165  				case *image.Uniform:
   166  					drawGlyphOver(dst0, r, src0, mask0, mp)
   167  					return
   168  				case *image.RGBA:
   169  					drawRGBAMaskOver(dst0, r, src0, sp, mask0, mp)
   170  					return
   171  				case *image.Gray:
   172  					drawGrayMaskOver(dst0, r, src0, sp, mask0, mp)
   173  					return
   174  				// Case order matters. The next case (image.RGBA64Image) is an
   175  				// interface type that the concrete types above also implement.
   176  				case image.RGBA64Image:
   177  					drawRGBA64ImageMaskOver(dst0, r, src0, sp, mask0, mp)
   178  					return
   179  				}
   180  			}
   181  		} else {
   182  			if mask == nil {
   183  				switch src0 := src.(type) {
   184  				case *image.Uniform:
   185  					sr, sg, sb, sa := src0.RGBA()
   186  					drawFillSrc(dst0, r, sr, sg, sb, sa)
   187  					return
   188  				case *image.RGBA:
   189  					d0 := dst0.PixOffset(r.Min.X, r.Min.Y)
   190  					s0 := src0.PixOffset(sp.X, sp.Y)
   191  					drawCopySrc(
   192  						dst0.Pix[d0:], dst0.Stride, r, src0.Pix[s0:], src0.Stride, sp, 4*r.Dx())
   193  					return
   194  				case *image.NRGBA:
   195  					drawNRGBASrc(dst0, r, src0, sp)
   196  					return
   197  				case *image.YCbCr:
   198  					if imageutil.DrawYCbCr(dst0, r, src0, sp) {
   199  						return
   200  					}
   201  				case *image.Gray:
   202  					drawGray(dst0, r, src0, sp)
   203  					return
   204  				case *image.CMYK:
   205  					drawCMYK(dst0, r, src0, sp)
   206  					return
   207  				}
   208  			}
   209  		}
   210  		drawRGBA(dst0, r, src, sp, mask, mp, op)
   211  		return
   212  	case *image.Paletted:
   213  		if op == Src && mask == nil {
   214  			if src0, ok := src.(*image.Uniform); ok {
   215  				colorIndex := uint8(dst0.Palette.Index(src0.C))
   216  				i0 := dst0.PixOffset(r.Min.X, r.Min.Y)
   217  				i1 := i0 + r.Dx()
   218  				for i := i0; i < i1; i++ {
   219  					dst0.Pix[i] = colorIndex
   220  				}
   221  				firstRow := dst0.Pix[i0:i1]
   222  				for y := r.Min.Y + 1; y < r.Max.Y; y++ {
   223  					i0 += dst0.Stride
   224  					i1 += dst0.Stride
   225  					copy(dst0.Pix[i0:i1], firstRow)
   226  				}
   227  				return
   228  			} else if !processBackward(dst, r, src, sp) {
   229  				drawPaletted(dst0, r, src, sp, false)
   230  				return
   231  			}
   232  		}
   233  	case *image.NRGBA:
   234  		if op == Src && mask == nil {
   235  			if src0, ok := src.(*image.NRGBA); ok {
   236  				d0 := dst0.PixOffset(r.Min.X, r.Min.Y)
   237  				s0 := src0.PixOffset(sp.X, sp.Y)
   238  				drawCopySrc(
   239  					dst0.Pix[d0:], dst0.Stride, r, src0.Pix[s0:], src0.Stride, sp, 4*r.Dx())
   240  				return
   241  			}
   242  		}
   243  	case *image.NRGBA64:
   244  		if op == Src && mask == nil {
   245  			if src0, ok := src.(*image.NRGBA64); ok {
   246  				d0 := dst0.PixOffset(r.Min.X, r.Min.Y)
   247  				s0 := src0.PixOffset(sp.X, sp.Y)
   248  				drawCopySrc(
   249  					dst0.Pix[d0:], dst0.Stride, r, src0.Pix[s0:], src0.Stride, sp, 8*r.Dx())
   250  				return
   251  			}
   252  		}
   253  	}
   254  
   255  	x0, x1, dx := r.Min.X, r.Max.X, 1
   256  	y0, y1, dy := r.Min.Y, r.Max.Y, 1
   257  	if processBackward(dst, r, src, sp) {
   258  		x0, x1, dx = x1-1, x0-1, -1
   259  		y0, y1, dy = y1-1, y0-1, -1
   260  	}
   261  
   262  	// FALLBACK1.17
   263  	//
   264  	// Try the draw.RGBA64Image and image.RGBA64Image interfaces, part of the
   265  	// standard library since Go 1.17. These are like the draw.Image and
   266  	// image.Image interfaces but they can avoid allocations from converting
   267  	// concrete color types to the color.Color interface type.
   268  
   269  	if dst0, _ := dst.(RGBA64Image); dst0 != nil {
   270  		if src0, _ := src.(image.RGBA64Image); src0 != nil {
   271  			if mask == nil {
   272  				sy := sp.Y + y0 - r.Min.Y
   273  				my := mp.Y + y0 - r.Min.Y
   274  				for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   275  					sx := sp.X + x0 - r.Min.X
   276  					mx := mp.X + x0 - r.Min.X
   277  					for x := x0; x != x1; x, sx, mx = x+dx, sx+dx, mx+dx {
   278  						if op == Src {
   279  							dst0.SetRGBA64(x, y, src0.RGBA64At(sx, sy))
   280  						} else {
   281  							srgba := src0.RGBA64At(sx, sy)
   282  							a := m - uint32(srgba.A)
   283  							drgba := dst0.RGBA64At(x, y)
   284  							dst0.SetRGBA64(x, y, color.RGBA64{
   285  								R: uint16((uint32(drgba.R)*a)/m) + srgba.R,
   286  								G: uint16((uint32(drgba.G)*a)/m) + srgba.G,
   287  								B: uint16((uint32(drgba.B)*a)/m) + srgba.B,
   288  								A: uint16((uint32(drgba.A)*a)/m) + srgba.A,
   289  							})
   290  						}
   291  					}
   292  				}
   293  				return
   294  
   295  			} else if mask0, _ := mask.(image.RGBA64Image); mask0 != nil {
   296  				sy := sp.Y + y0 - r.Min.Y
   297  				my := mp.Y + y0 - r.Min.Y
   298  				for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   299  					sx := sp.X + x0 - r.Min.X
   300  					mx := mp.X + x0 - r.Min.X
   301  					for x := x0; x != x1; x, sx, mx = x+dx, sx+dx, mx+dx {
   302  						ma := uint32(mask0.RGBA64At(mx, my).A)
   303  						switch {
   304  						case ma == 0:
   305  							if op == Over {
   306  								// No-op.
   307  							} else {
   308  								dst0.SetRGBA64(x, y, color.RGBA64{})
   309  							}
   310  						case ma == m && op == Src:
   311  							dst0.SetRGBA64(x, y, src0.RGBA64At(sx, sy))
   312  						default:
   313  							srgba := src0.RGBA64At(sx, sy)
   314  							if op == Over {
   315  								drgba := dst0.RGBA64At(x, y)
   316  								a := m - (uint32(srgba.A) * ma / m)
   317  								dst0.SetRGBA64(x, y, color.RGBA64{
   318  									R: uint16((uint32(drgba.R)*a + uint32(srgba.R)*ma) / m),
   319  									G: uint16((uint32(drgba.G)*a + uint32(srgba.G)*ma) / m),
   320  									B: uint16((uint32(drgba.B)*a + uint32(srgba.B)*ma) / m),
   321  									A: uint16((uint32(drgba.A)*a + uint32(srgba.A)*ma) / m),
   322  								})
   323  							} else {
   324  								dst0.SetRGBA64(x, y, color.RGBA64{
   325  									R: uint16(uint32(srgba.R) * ma / m),
   326  									G: uint16(uint32(srgba.G) * ma / m),
   327  									B: uint16(uint32(srgba.B) * ma / m),
   328  									A: uint16(uint32(srgba.A) * ma / m),
   329  								})
   330  							}
   331  						}
   332  					}
   333  				}
   334  				return
   335  			}
   336  		}
   337  	}
   338  
   339  	// FALLBACK1.0
   340  	//
   341  	// If none of the faster code paths above apply, use the draw.Image and
   342  	// image.Image interfaces, part of the standard library since Go 1.0.
   343  
   344  	var out color.RGBA64
   345  	sy := sp.Y + y0 - r.Min.Y
   346  	my := mp.Y + y0 - r.Min.Y
   347  	for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   348  		sx := sp.X + x0 - r.Min.X
   349  		mx := mp.X + x0 - r.Min.X
   350  		for x := x0; x != x1; x, sx, mx = x+dx, sx+dx, mx+dx {
   351  			ma := uint32(m)
   352  			if mask != nil {
   353  				_, _, _, ma = mask.At(mx, my).RGBA()
   354  			}
   355  			switch {
   356  			case ma == 0:
   357  				if op == Over {
   358  					// No-op.
   359  				} else {
   360  					dst.Set(x, y, color.Transparent)
   361  				}
   362  			case ma == m && op == Src:
   363  				dst.Set(x, y, src.At(sx, sy))
   364  			default:
   365  				sr, sg, sb, sa := src.At(sx, sy).RGBA()
   366  				if op == Over {
   367  					dr, dg, db, da := dst.At(x, y).RGBA()
   368  					a := m - (sa * ma / m)
   369  					out.R = uint16((dr*a + sr*ma) / m)
   370  					out.G = uint16((dg*a + sg*ma) / m)
   371  					out.B = uint16((db*a + sb*ma) / m)
   372  					out.A = uint16((da*a + sa*ma) / m)
   373  				} else {
   374  					out.R = uint16(sr * ma / m)
   375  					out.G = uint16(sg * ma / m)
   376  					out.B = uint16(sb * ma / m)
   377  					out.A = uint16(sa * ma / m)
   378  				}
   379  				// The third argument is &out instead of out (and out is
   380  				// declared outside of the inner loop) to avoid the implicit
   381  				// conversion to color.Color here allocating memory in the
   382  				// inner loop if sizeof(color.RGBA64) > sizeof(uintptr).
   383  				dst.Set(x, y, &out)
   384  			}
   385  		}
   386  	}
   387  }
   388  
   389  func drawFillOver(dst *image.RGBA, r image.Rectangle, sr, sg, sb, sa uint32) {
   390  	// The 0x101 is here for the same reason as in drawRGBA.
   391  	a := (m - sa) * 0x101
   392  	i0 := dst.PixOffset(r.Min.X, r.Min.Y)
   393  	i1 := i0 + r.Dx()*4
   394  	for y := r.Min.Y; y != r.Max.Y; y++ {
   395  		for i := i0; i < i1; i += 4 {
   396  			dr := &dst.Pix[i+0]
   397  			dg := &dst.Pix[i+1]
   398  			db := &dst.Pix[i+2]
   399  			da := &dst.Pix[i+3]
   400  
   401  			*dr = uint8((uint32(*dr)*a/m + sr) >> 8)
   402  			*dg = uint8((uint32(*dg)*a/m + sg) >> 8)
   403  			*db = uint8((uint32(*db)*a/m + sb) >> 8)
   404  			*da = uint8((uint32(*da)*a/m + sa) >> 8)
   405  		}
   406  		i0 += dst.Stride
   407  		i1 += dst.Stride
   408  	}
   409  }
   410  
   411  func drawFillSrc(dst *image.RGBA, r image.Rectangle, sr, sg, sb, sa uint32) {
   412  	sr8 := uint8(sr >> 8)
   413  	sg8 := uint8(sg >> 8)
   414  	sb8 := uint8(sb >> 8)
   415  	sa8 := uint8(sa >> 8)
   416  	// The built-in copy function is faster than a straightforward for loop to fill the destination with
   417  	// the color, but copy requires a slice source. We therefore use a for loop to fill the first row, and
   418  	// then use the first row as the slice source for the remaining rows.
   419  	i0 := dst.PixOffset(r.Min.X, r.Min.Y)
   420  	i1 := i0 + r.Dx()*4
   421  	for i := i0; i < i1; i += 4 {
   422  		dst.Pix[i+0] = sr8
   423  		dst.Pix[i+1] = sg8
   424  		dst.Pix[i+2] = sb8
   425  		dst.Pix[i+3] = sa8
   426  	}
   427  	firstRow := dst.Pix[i0:i1]
   428  	for y := r.Min.Y + 1; y < r.Max.Y; y++ {
   429  		i0 += dst.Stride
   430  		i1 += dst.Stride
   431  		copy(dst.Pix[i0:i1], firstRow)
   432  	}
   433  }
   434  
   435  func drawCopyOver(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point) {
   436  	dx, dy := r.Dx(), r.Dy()
   437  	d0 := dst.PixOffset(r.Min.X, r.Min.Y)
   438  	s0 := src.PixOffset(sp.X, sp.Y)
   439  	var (
   440  		ddelta, sdelta int
   441  		i0, i1, idelta int
   442  	)
   443  	if r.Min.Y < sp.Y || r.Min.Y == sp.Y && r.Min.X <= sp.X {
   444  		ddelta = dst.Stride
   445  		sdelta = src.Stride
   446  		i0, i1, idelta = 0, dx*4, +4
   447  	} else {
   448  		// If the source start point is higher than the destination start point, or equal height but to the left,
   449  		// then we compose the rows in right-to-left, bottom-up order instead of left-to-right, top-down.
   450  		d0 += (dy - 1) * dst.Stride
   451  		s0 += (dy - 1) * src.Stride
   452  		ddelta = -dst.Stride
   453  		sdelta = -src.Stride
   454  		i0, i1, idelta = (dx-1)*4, -4, -4
   455  	}
   456  	for ; dy > 0; dy-- {
   457  		dpix := dst.Pix[d0:]
   458  		spix := src.Pix[s0:]
   459  		for i := i0; i != i1; i += idelta {
   460  			s := spix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857
   461  			sr := uint32(s[0]) * 0x101
   462  			sg := uint32(s[1]) * 0x101
   463  			sb := uint32(s[2]) * 0x101
   464  			sa := uint32(s[3]) * 0x101
   465  
   466  			// The 0x101 is here for the same reason as in drawRGBA.
   467  			a := (m - sa) * 0x101
   468  
   469  			d := dpix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857
   470  			d[0] = uint8((uint32(d[0])*a/m + sr) >> 8)
   471  			d[1] = uint8((uint32(d[1])*a/m + sg) >> 8)
   472  			d[2] = uint8((uint32(d[2])*a/m + sb) >> 8)
   473  			d[3] = uint8((uint32(d[3])*a/m + sa) >> 8)
   474  		}
   475  		d0 += ddelta
   476  		s0 += sdelta
   477  	}
   478  }
   479  
   480  // drawCopySrc copies bytes to dstPix from srcPix. These arguments roughly
   481  // correspond to the Pix fields of the image package's concrete image.Image
   482  // implementations, but are offset (dstPix is dst.Pix[dpOffset:] not dst.Pix).
   483  func drawCopySrc(
   484  	dstPix []byte, dstStride int, r image.Rectangle,
   485  	srcPix []byte, srcStride int, sp image.Point,
   486  	bytesPerRow int) {
   487  
   488  	d0, s0, ddelta, sdelta, dy := 0, 0, dstStride, srcStride, r.Dy()
   489  	if r.Min.Y > sp.Y {
   490  		// If the source start point is higher than the destination start
   491  		// point, then we compose the rows in bottom-up order instead of
   492  		// top-down. Unlike the drawCopyOver function, we don't have to check
   493  		// the x coordinates because the built-in copy function can handle
   494  		// overlapping slices.
   495  		d0 = (dy - 1) * dstStride
   496  		s0 = (dy - 1) * srcStride
   497  		ddelta = -dstStride
   498  		sdelta = -srcStride
   499  	}
   500  	for ; dy > 0; dy-- {
   501  		copy(dstPix[d0:d0+bytesPerRow], srcPix[s0:s0+bytesPerRow])
   502  		d0 += ddelta
   503  		s0 += sdelta
   504  	}
   505  }
   506  
   507  func drawNRGBAOver(dst *image.RGBA, r image.Rectangle, src *image.NRGBA, sp image.Point) {
   508  	i0 := (r.Min.X - dst.Rect.Min.X) * 4
   509  	i1 := (r.Max.X - dst.Rect.Min.X) * 4
   510  	si0 := (sp.X - src.Rect.Min.X) * 4
   511  	yMax := r.Max.Y - dst.Rect.Min.Y
   512  
   513  	y := r.Min.Y - dst.Rect.Min.Y
   514  	sy := sp.Y - src.Rect.Min.Y
   515  	for ; y != yMax; y, sy = y+1, sy+1 {
   516  		dpix := dst.Pix[y*dst.Stride:]
   517  		spix := src.Pix[sy*src.Stride:]
   518  
   519  		for i, si := i0, si0; i < i1; i, si = i+4, si+4 {
   520  			// Convert from non-premultiplied color to pre-multiplied color.
   521  			s := spix[si : si+4 : si+4] // Small cap improves performance, see https://golang.org/issue/27857
   522  			sa := uint32(s[3]) * 0x101
   523  			sr := uint32(s[0]) * sa / 0xff
   524  			sg := uint32(s[1]) * sa / 0xff
   525  			sb := uint32(s[2]) * sa / 0xff
   526  
   527  			d := dpix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857
   528  			dr := uint32(d[0])
   529  			dg := uint32(d[1])
   530  			db := uint32(d[2])
   531  			da := uint32(d[3])
   532  
   533  			// The 0x101 is here for the same reason as in drawRGBA.
   534  			a := (m - sa) * 0x101
   535  
   536  			d[0] = uint8((dr*a/m + sr) >> 8)
   537  			d[1] = uint8((dg*a/m + sg) >> 8)
   538  			d[2] = uint8((db*a/m + sb) >> 8)
   539  			d[3] = uint8((da*a/m + sa) >> 8)
   540  		}
   541  	}
   542  }
   543  
   544  func drawNRGBASrc(dst *image.RGBA, r image.Rectangle, src *image.NRGBA, sp image.Point) {
   545  	i0 := (r.Min.X - dst.Rect.Min.X) * 4
   546  	i1 := (r.Max.X - dst.Rect.Min.X) * 4
   547  	si0 := (sp.X - src.Rect.Min.X) * 4
   548  	yMax := r.Max.Y - dst.Rect.Min.Y
   549  
   550  	y := r.Min.Y - dst.Rect.Min.Y
   551  	sy := sp.Y - src.Rect.Min.Y
   552  	for ; y != yMax; y, sy = y+1, sy+1 {
   553  		dpix := dst.Pix[y*dst.Stride:]
   554  		spix := src.Pix[sy*src.Stride:]
   555  
   556  		for i, si := i0, si0; i < i1; i, si = i+4, si+4 {
   557  			// Convert from non-premultiplied color to pre-multiplied color.
   558  			s := spix[si : si+4 : si+4] // Small cap improves performance, see https://golang.org/issue/27857
   559  			sa := uint32(s[3]) * 0x101
   560  			sr := uint32(s[0]) * sa / 0xff
   561  			sg := uint32(s[1]) * sa / 0xff
   562  			sb := uint32(s[2]) * sa / 0xff
   563  
   564  			d := dpix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857
   565  			d[0] = uint8(sr >> 8)
   566  			d[1] = uint8(sg >> 8)
   567  			d[2] = uint8(sb >> 8)
   568  			d[3] = uint8(sa >> 8)
   569  		}
   570  	}
   571  }
   572  
   573  func drawGray(dst *image.RGBA, r image.Rectangle, src *image.Gray, sp image.Point) {
   574  	i0 := (r.Min.X - dst.Rect.Min.X) * 4
   575  	i1 := (r.Max.X - dst.Rect.Min.X) * 4
   576  	si0 := (sp.X - src.Rect.Min.X) * 1
   577  	yMax := r.Max.Y - dst.Rect.Min.Y
   578  
   579  	y := r.Min.Y - dst.Rect.Min.Y
   580  	sy := sp.Y - src.Rect.Min.Y
   581  	for ; y != yMax; y, sy = y+1, sy+1 {
   582  		dpix := dst.Pix[y*dst.Stride:]
   583  		spix := src.Pix[sy*src.Stride:]
   584  
   585  		for i, si := i0, si0; i < i1; i, si = i+4, si+1 {
   586  			p := spix[si]
   587  			d := dpix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857
   588  			d[0] = p
   589  			d[1] = p
   590  			d[2] = p
   591  			d[3] = 255
   592  		}
   593  	}
   594  }
   595  
   596  func drawCMYK(dst *image.RGBA, r image.Rectangle, src *image.CMYK, sp image.Point) {
   597  	i0 := (r.Min.X - dst.Rect.Min.X) * 4
   598  	i1 := (r.Max.X - dst.Rect.Min.X) * 4
   599  	si0 := (sp.X - src.Rect.Min.X) * 4
   600  	yMax := r.Max.Y - dst.Rect.Min.Y
   601  
   602  	y := r.Min.Y - dst.Rect.Min.Y
   603  	sy := sp.Y - src.Rect.Min.Y
   604  	for ; y != yMax; y, sy = y+1, sy+1 {
   605  		dpix := dst.Pix[y*dst.Stride:]
   606  		spix := src.Pix[sy*src.Stride:]
   607  
   608  		for i, si := i0, si0; i < i1; i, si = i+4, si+4 {
   609  			s := spix[si : si+4 : si+4] // Small cap improves performance, see https://golang.org/issue/27857
   610  			d := dpix[i : i+4 : i+4]
   611  			d[0], d[1], d[2] = color.CMYKToRGB(s[0], s[1], s[2], s[3])
   612  			d[3] = 255
   613  		}
   614  	}
   615  }
   616  
   617  func drawGlyphOver(dst *image.RGBA, r image.Rectangle, src *image.Uniform, mask *image.Alpha, mp image.Point) {
   618  	i0 := dst.PixOffset(r.Min.X, r.Min.Y)
   619  	i1 := i0 + r.Dx()*4
   620  	mi0 := mask.PixOffset(mp.X, mp.Y)
   621  	sr, sg, sb, sa := src.RGBA()
   622  	for y, my := r.Min.Y, mp.Y; y != r.Max.Y; y, my = y+1, my+1 {
   623  		for i, mi := i0, mi0; i < i1; i, mi = i+4, mi+1 {
   624  			ma := uint32(mask.Pix[mi])
   625  			if ma == 0 {
   626  				continue
   627  			}
   628  			ma |= ma << 8
   629  
   630  			// The 0x101 is here for the same reason as in drawRGBA.
   631  			a := (m - (sa * ma / m)) * 0x101
   632  
   633  			d := dst.Pix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857
   634  			d[0] = uint8((uint32(d[0])*a + sr*ma) / m >> 8)
   635  			d[1] = uint8((uint32(d[1])*a + sg*ma) / m >> 8)
   636  			d[2] = uint8((uint32(d[2])*a + sb*ma) / m >> 8)
   637  			d[3] = uint8((uint32(d[3])*a + sa*ma) / m >> 8)
   638  		}
   639  		i0 += dst.Stride
   640  		i1 += dst.Stride
   641  		mi0 += mask.Stride
   642  	}
   643  }
   644  
   645  func drawGrayMaskOver(dst *image.RGBA, r image.Rectangle, src *image.Gray, sp image.Point, mask *image.Alpha, mp image.Point) {
   646  	x0, x1, dx := r.Min.X, r.Max.X, 1
   647  	y0, y1, dy := r.Min.Y, r.Max.Y, 1
   648  	if r.Overlaps(r.Add(sp.Sub(r.Min))) {
   649  		if sp.Y < r.Min.Y || sp.Y == r.Min.Y && sp.X < r.Min.X {
   650  			x0, x1, dx = x1-1, x0-1, -1
   651  			y0, y1, dy = y1-1, y0-1, -1
   652  		}
   653  	}
   654  
   655  	sy := sp.Y + y0 - r.Min.Y
   656  	my := mp.Y + y0 - r.Min.Y
   657  	sx0 := sp.X + x0 - r.Min.X
   658  	mx0 := mp.X + x0 - r.Min.X
   659  	sx1 := sx0 + (x1 - x0)
   660  	i0 := dst.PixOffset(x0, y0)
   661  	di := dx * 4
   662  	for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   663  		for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx {
   664  			mi := mask.PixOffset(mx, my)
   665  			ma := uint32(mask.Pix[mi])
   666  			ma |= ma << 8
   667  			si := src.PixOffset(sx, sy)
   668  			sy := uint32(src.Pix[si])
   669  			sy |= sy << 8
   670  			sa := uint32(0xffff)
   671  
   672  			d := dst.Pix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857
   673  			dr := uint32(d[0])
   674  			dg := uint32(d[1])
   675  			db := uint32(d[2])
   676  			da := uint32(d[3])
   677  
   678  			// dr, dg, db and da are all 8-bit color at the moment, ranging in [0,255].
   679  			// We work in 16-bit color, and so would normally do:
   680  			// dr |= dr << 8
   681  			// and similarly for dg, db and da, but instead we multiply a
   682  			// (which is a 16-bit color, ranging in [0,65535]) by 0x101.
   683  			// This yields the same result, but is fewer arithmetic operations.
   684  			a := (m - (sa * ma / m)) * 0x101
   685  
   686  			d[0] = uint8((dr*a + sy*ma) / m >> 8)
   687  			d[1] = uint8((dg*a + sy*ma) / m >> 8)
   688  			d[2] = uint8((db*a + sy*ma) / m >> 8)
   689  			d[3] = uint8((da*a + sa*ma) / m >> 8)
   690  		}
   691  		i0 += dy * dst.Stride
   692  	}
   693  }
   694  
   695  func drawRGBAMaskOver(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point, mask *image.Alpha, mp image.Point) {
   696  	x0, x1, dx := r.Min.X, r.Max.X, 1
   697  	y0, y1, dy := r.Min.Y, r.Max.Y, 1
   698  	if dst == src && r.Overlaps(r.Add(sp.Sub(r.Min))) {
   699  		if sp.Y < r.Min.Y || sp.Y == r.Min.Y && sp.X < r.Min.X {
   700  			x0, x1, dx = x1-1, x0-1, -1
   701  			y0, y1, dy = y1-1, y0-1, -1
   702  		}
   703  	}
   704  
   705  	sy := sp.Y + y0 - r.Min.Y
   706  	my := mp.Y + y0 - r.Min.Y
   707  	sx0 := sp.X + x0 - r.Min.X
   708  	mx0 := mp.X + x0 - r.Min.X
   709  	sx1 := sx0 + (x1 - x0)
   710  	i0 := dst.PixOffset(x0, y0)
   711  	di := dx * 4
   712  	for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   713  		for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx {
   714  			mi := mask.PixOffset(mx, my)
   715  			ma := uint32(mask.Pix[mi])
   716  			ma |= ma << 8
   717  			si := src.PixOffset(sx, sy)
   718  			sr := uint32(src.Pix[si+0])
   719  			sg := uint32(src.Pix[si+1])
   720  			sb := uint32(src.Pix[si+2])
   721  			sa := uint32(src.Pix[si+3])
   722  			sr |= sr << 8
   723  			sg |= sg << 8
   724  			sb |= sb << 8
   725  			sa |= sa << 8
   726  			d := dst.Pix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857
   727  			dr := uint32(d[0])
   728  			dg := uint32(d[1])
   729  			db := uint32(d[2])
   730  			da := uint32(d[3])
   731  
   732  			// dr, dg, db and da are all 8-bit color at the moment, ranging in [0,255].
   733  			// We work in 16-bit color, and so would normally do:
   734  			// dr |= dr << 8
   735  			// and similarly for dg, db and da, but instead we multiply a
   736  			// (which is a 16-bit color, ranging in [0,65535]) by 0x101.
   737  			// This yields the same result, but is fewer arithmetic operations.
   738  			a := (m - (sa * ma / m)) * 0x101
   739  
   740  			d[0] = uint8((dr*a + sr*ma) / m >> 8)
   741  			d[1] = uint8((dg*a + sg*ma) / m >> 8)
   742  			d[2] = uint8((db*a + sb*ma) / m >> 8)
   743  			d[3] = uint8((da*a + sa*ma) / m >> 8)
   744  		}
   745  		i0 += dy * dst.Stride
   746  	}
   747  }
   748  
   749  func drawRGBA64ImageMaskOver(dst *image.RGBA, r image.Rectangle, src image.RGBA64Image, sp image.Point, mask *image.Alpha, mp image.Point) {
   750  	x0, x1, dx := r.Min.X, r.Max.X, 1
   751  	y0, y1, dy := r.Min.Y, r.Max.Y, 1
   752  	if image.Image(dst) == src && r.Overlaps(r.Add(sp.Sub(r.Min))) {
   753  		if sp.Y < r.Min.Y || sp.Y == r.Min.Y && sp.X < r.Min.X {
   754  			x0, x1, dx = x1-1, x0-1, -1
   755  			y0, y1, dy = y1-1, y0-1, -1
   756  		}
   757  	}
   758  
   759  	sy := sp.Y + y0 - r.Min.Y
   760  	my := mp.Y + y0 - r.Min.Y
   761  	sx0 := sp.X + x0 - r.Min.X
   762  	mx0 := mp.X + x0 - r.Min.X
   763  	sx1 := sx0 + (x1 - x0)
   764  	i0 := dst.PixOffset(x0, y0)
   765  	di := dx * 4
   766  	for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   767  		for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx {
   768  			mi := mask.PixOffset(mx, my)
   769  			ma := uint32(mask.Pix[mi])
   770  			ma |= ma << 8
   771  			srgba := src.RGBA64At(sx, sy)
   772  			d := dst.Pix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857
   773  			dr := uint32(d[0])
   774  			dg := uint32(d[1])
   775  			db := uint32(d[2])
   776  			da := uint32(d[3])
   777  
   778  			// dr, dg, db and da are all 8-bit color at the moment, ranging in [0,255].
   779  			// We work in 16-bit color, and so would normally do:
   780  			// dr |= dr << 8
   781  			// and similarly for dg, db and da, but instead we multiply a
   782  			// (which is a 16-bit color, ranging in [0,65535]) by 0x101.
   783  			// This yields the same result, but is fewer arithmetic operations.
   784  			a := (m - (uint32(srgba.A) * ma / m)) * 0x101
   785  
   786  			d[0] = uint8((dr*a + uint32(srgba.R)*ma) / m >> 8)
   787  			d[1] = uint8((dg*a + uint32(srgba.G)*ma) / m >> 8)
   788  			d[2] = uint8((db*a + uint32(srgba.B)*ma) / m >> 8)
   789  			d[3] = uint8((da*a + uint32(srgba.A)*ma) / m >> 8)
   790  		}
   791  		i0 += dy * dst.Stride
   792  	}
   793  }
   794  
   795  func drawRGBA(dst *image.RGBA, r image.Rectangle, src image.Image, sp image.Point, mask image.Image, mp image.Point, op Op) {
   796  	x0, x1, dx := r.Min.X, r.Max.X, 1
   797  	y0, y1, dy := r.Min.Y, r.Max.Y, 1
   798  	if image.Image(dst) == src && r.Overlaps(r.Add(sp.Sub(r.Min))) {
   799  		if sp.Y < r.Min.Y || sp.Y == r.Min.Y && sp.X < r.Min.X {
   800  			x0, x1, dx = x1-1, x0-1, -1
   801  			y0, y1, dy = y1-1, y0-1, -1
   802  		}
   803  	}
   804  
   805  	sy := sp.Y + y0 - r.Min.Y
   806  	my := mp.Y + y0 - r.Min.Y
   807  	sx0 := sp.X + x0 - r.Min.X
   808  	mx0 := mp.X + x0 - r.Min.X
   809  	sx1 := sx0 + (x1 - x0)
   810  	i0 := dst.PixOffset(x0, y0)
   811  	di := dx * 4
   812  
   813  	// Try the image.RGBA64Image interface, part of the standard library since
   814  	// Go 1.17.
   815  	//
   816  	// This optimization is similar to how FALLBACK1.17 optimizes FALLBACK1.0
   817  	// in DrawMask, except here the concrete type of dst is known to be
   818  	// *image.RGBA.
   819  	if src0, _ := src.(image.RGBA64Image); src0 != nil {
   820  		if mask == nil {
   821  			if op == Over {
   822  				for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   823  					for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx {
   824  						srgba := src0.RGBA64At(sx, sy)
   825  						d := dst.Pix[i : i+4 : i+4]
   826  						dr := uint32(d[0])
   827  						dg := uint32(d[1])
   828  						db := uint32(d[2])
   829  						da := uint32(d[3])
   830  						a := (m - uint32(srgba.A)) * 0x101
   831  						d[0] = uint8((dr*a/m + uint32(srgba.R)) >> 8)
   832  						d[1] = uint8((dg*a/m + uint32(srgba.G)) >> 8)
   833  						d[2] = uint8((db*a/m + uint32(srgba.B)) >> 8)
   834  						d[3] = uint8((da*a/m + uint32(srgba.A)) >> 8)
   835  					}
   836  					i0 += dy * dst.Stride
   837  				}
   838  			} else {
   839  				for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   840  					for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx {
   841  						srgba := src0.RGBA64At(sx, sy)
   842  						d := dst.Pix[i : i+4 : i+4]
   843  						d[0] = uint8(srgba.R >> 8)
   844  						d[1] = uint8(srgba.G >> 8)
   845  						d[2] = uint8(srgba.B >> 8)
   846  						d[3] = uint8(srgba.A >> 8)
   847  					}
   848  					i0 += dy * dst.Stride
   849  				}
   850  			}
   851  			return
   852  
   853  		} else if mask0, _ := mask.(image.RGBA64Image); mask0 != nil {
   854  			if op == Over {
   855  				for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   856  					for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx {
   857  						ma := uint32(mask0.RGBA64At(mx, my).A)
   858  						srgba := src0.RGBA64At(sx, sy)
   859  						d := dst.Pix[i : i+4 : i+4]
   860  						dr := uint32(d[0])
   861  						dg := uint32(d[1])
   862  						db := uint32(d[2])
   863  						da := uint32(d[3])
   864  						a := (m - (uint32(srgba.A) * ma / m)) * 0x101
   865  						d[0] = uint8((dr*a + uint32(srgba.R)*ma) / m >> 8)
   866  						d[1] = uint8((dg*a + uint32(srgba.G)*ma) / m >> 8)
   867  						d[2] = uint8((db*a + uint32(srgba.B)*ma) / m >> 8)
   868  						d[3] = uint8((da*a + uint32(srgba.A)*ma) / m >> 8)
   869  					}
   870  					i0 += dy * dst.Stride
   871  				}
   872  			} else {
   873  				for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   874  					for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx {
   875  						ma := uint32(mask0.RGBA64At(mx, my).A)
   876  						srgba := src0.RGBA64At(sx, sy)
   877  						d := dst.Pix[i : i+4 : i+4]
   878  						d[0] = uint8(uint32(srgba.R) * ma / m >> 8)
   879  						d[1] = uint8(uint32(srgba.G) * ma / m >> 8)
   880  						d[2] = uint8(uint32(srgba.B) * ma / m >> 8)
   881  						d[3] = uint8(uint32(srgba.A) * ma / m >> 8)
   882  					}
   883  					i0 += dy * dst.Stride
   884  				}
   885  			}
   886  			return
   887  		}
   888  	}
   889  
   890  	// Use the image.Image interface, part of the standard library since Go
   891  	// 1.0.
   892  	//
   893  	// This is similar to FALLBACK1.0 in DrawMask, except here the concrete
   894  	// type of dst is known to be *image.RGBA.
   895  	for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   896  		for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx {
   897  			ma := uint32(m)
   898  			if mask != nil {
   899  				_, _, _, ma = mask.At(mx, my).RGBA()
   900  			}
   901  			sr, sg, sb, sa := src.At(sx, sy).RGBA()
   902  			d := dst.Pix[i : i+4 : i+4] // Small cap improves performance, see https://golang.org/issue/27857
   903  			if op == Over {
   904  				dr := uint32(d[0])
   905  				dg := uint32(d[1])
   906  				db := uint32(d[2])
   907  				da := uint32(d[3])
   908  
   909  				// dr, dg, db and da are all 8-bit color at the moment, ranging in [0,255].
   910  				// We work in 16-bit color, and so would normally do:
   911  				// dr |= dr << 8
   912  				// and similarly for dg, db and da, but instead we multiply a
   913  				// (which is a 16-bit color, ranging in [0,65535]) by 0x101.
   914  				// This yields the same result, but is fewer arithmetic operations.
   915  				a := (m - (sa * ma / m)) * 0x101
   916  
   917  				d[0] = uint8((dr*a + sr*ma) / m >> 8)
   918  				d[1] = uint8((dg*a + sg*ma) / m >> 8)
   919  				d[2] = uint8((db*a + sb*ma) / m >> 8)
   920  				d[3] = uint8((da*a + sa*ma) / m >> 8)
   921  
   922  			} else {
   923  				d[0] = uint8(sr * ma / m >> 8)
   924  				d[1] = uint8(sg * ma / m >> 8)
   925  				d[2] = uint8(sb * ma / m >> 8)
   926  				d[3] = uint8(sa * ma / m >> 8)
   927  			}
   928  		}
   929  		i0 += dy * dst.Stride
   930  	}
   931  }
   932  
   933  // clamp clamps i to the interval [0, 0xffff].
   934  func clamp(i int32) int32 {
   935  	if i < 0 {
   936  		return 0
   937  	}
   938  	if i > 0xffff {
   939  		return 0xffff
   940  	}
   941  	return i
   942  }
   943  
   944  // sqDiff returns the squared-difference of x and y, shifted by 2 so that
   945  // adding four of those won't overflow a uint32.
   946  //
   947  // x and y are both assumed to be in the range [0, 0xffff].
   948  func sqDiff(x, y int32) uint32 {
   949  	// This is an optimized code relying on the overflow/wrap around
   950  	// properties of unsigned integers operations guaranteed by the language
   951  	// spec. See sqDiff from the image/color package for more details.
   952  	d := uint32(x - y)
   953  	return (d * d) >> 2
   954  }
   955  
   956  func drawPaletted(dst Image, r image.Rectangle, src image.Image, sp image.Point, floydSteinberg bool) {
   957  	// TODO(nigeltao): handle the case where the dst and src overlap.
   958  	// Does it even make sense to try and do Floyd-Steinberg whilst
   959  	// walking the image backward (right-to-left bottom-to-top)?
   960  
   961  	// If dst is an *image.Paletted, we have a fast path for dst.Set and
   962  	// dst.At. The dst.Set equivalent is a batch version of the algorithm
   963  	// used by color.Palette's Index method in image/color/color.go, plus
   964  	// optional Floyd-Steinberg error diffusion.
   965  	palette, pix, stride := [][4]int32(nil), []byte(nil), 0
   966  	if p, ok := dst.(*image.Paletted); ok {
   967  		palette = make([][4]int32, len(p.Palette))
   968  		for i, col := range p.Palette {
   969  			r, g, b, a := col.RGBA()
   970  			palette[i][0] = int32(r)
   971  			palette[i][1] = int32(g)
   972  			palette[i][2] = int32(b)
   973  			palette[i][3] = int32(a)
   974  		}
   975  		pix, stride = p.Pix[p.PixOffset(r.Min.X, r.Min.Y):], p.Stride
   976  	}
   977  
   978  	// quantErrorCurr and quantErrorNext are the Floyd-Steinberg quantization
   979  	// errors that have been propagated to the pixels in the current and next
   980  	// rows. The +2 simplifies calculation near the edges.
   981  	var quantErrorCurr, quantErrorNext [][4]int32
   982  	if floydSteinberg {
   983  		quantErrorCurr = make([][4]int32, r.Dx()+2)
   984  		quantErrorNext = make([][4]int32, r.Dx()+2)
   985  	}
   986  	pxRGBA := func(x, y int) (r, g, b, a uint32) { return src.At(x, y).RGBA() }
   987  	// Fast paths for special cases to avoid excessive use of the color.Color
   988  	// interface which escapes to the heap but need to be discovered for
   989  	// each pixel on r. See also https://golang.org/issues/15759.
   990  	switch src0 := src.(type) {
   991  	case *image.RGBA:
   992  		pxRGBA = func(x, y int) (r, g, b, a uint32) { return src0.RGBAAt(x, y).RGBA() }
   993  	case *image.NRGBA:
   994  		pxRGBA = func(x, y int) (r, g, b, a uint32) { return src0.NRGBAAt(x, y).RGBA() }
   995  	case *image.YCbCr:
   996  		pxRGBA = func(x, y int) (r, g, b, a uint32) { return src0.YCbCrAt(x, y).RGBA() }
   997  	}
   998  
   999  	// Loop over each source pixel.
  1000  	out := color.RGBA64{A: 0xffff}
  1001  	for y := 0; y != r.Dy(); y++ {
  1002  		for x := 0; x != r.Dx(); x++ {
  1003  			// er, eg and eb are the pixel's R,G,B values plus the
  1004  			// optional Floyd-Steinberg error.
  1005  			sr, sg, sb, sa := pxRGBA(sp.X+x, sp.Y+y)
  1006  			er, eg, eb, ea := int32(sr), int32(sg), int32(sb), int32(sa)
  1007  			if floydSteinberg {
  1008  				er = clamp(er + quantErrorCurr[x+1][0]/16)
  1009  				eg = clamp(eg + quantErrorCurr[x+1][1]/16)
  1010  				eb = clamp(eb + quantErrorCurr[x+1][2]/16)
  1011  				ea = clamp(ea + quantErrorCurr[x+1][3]/16)
  1012  			}
  1013  
  1014  			if palette != nil {
  1015  				// Find the closest palette color in Euclidean R,G,B,A space:
  1016  				// the one that minimizes sum-squared-difference.
  1017  				// TODO(nigeltao): consider smarter algorithms.
  1018  				bestIndex, bestSum := 0, uint32(1<<32-1)
  1019  				for index, p := range palette {
  1020  					sum := sqDiff(er, p[0]) + sqDiff(eg, p[1]) + sqDiff(eb, p[2]) + sqDiff(ea, p[3])
  1021  					if sum < bestSum {
  1022  						bestIndex, bestSum = index, sum
  1023  						if sum == 0 {
  1024  							break
  1025  						}
  1026  					}
  1027  				}
  1028  				pix[y*stride+x] = byte(bestIndex)
  1029  
  1030  				if !floydSteinberg {
  1031  					continue
  1032  				}
  1033  				er -= palette[bestIndex][0]
  1034  				eg -= palette[bestIndex][1]
  1035  				eb -= palette[bestIndex][2]
  1036  				ea -= palette[bestIndex][3]
  1037  
  1038  			} else {
  1039  				out.R = uint16(er)
  1040  				out.G = uint16(eg)
  1041  				out.B = uint16(eb)
  1042  				out.A = uint16(ea)
  1043  				// The third argument is &out instead of out (and out is
  1044  				// declared outside of the inner loop) to avoid the implicit
  1045  				// conversion to color.Color here allocating memory in the
  1046  				// inner loop if sizeof(color.RGBA64) > sizeof(uintptr).
  1047  				dst.Set(r.Min.X+x, r.Min.Y+y, &out)
  1048  
  1049  				if !floydSteinberg {
  1050  					continue
  1051  				}
  1052  				sr, sg, sb, sa = dst.At(r.Min.X+x, r.Min.Y+y).RGBA()
  1053  				er -= int32(sr)
  1054  				eg -= int32(sg)
  1055  				eb -= int32(sb)
  1056  				ea -= int32(sa)
  1057  			}
  1058  
  1059  			// Propagate the Floyd-Steinberg quantization error.
  1060  			quantErrorNext[x+0][0] += er * 3
  1061  			quantErrorNext[x+0][1] += eg * 3
  1062  			quantErrorNext[x+0][2] += eb * 3
  1063  			quantErrorNext[x+0][3] += ea * 3
  1064  			quantErrorNext[x+1][0] += er * 5
  1065  			quantErrorNext[x+1][1] += eg * 5
  1066  			quantErrorNext[x+1][2] += eb * 5
  1067  			quantErrorNext[x+1][3] += ea * 5
  1068  			quantErrorNext[x+2][0] += er * 1
  1069  			quantErrorNext[x+2][1] += eg * 1
  1070  			quantErrorNext[x+2][2] += eb * 1
  1071  			quantErrorNext[x+2][3] += ea * 1
  1072  			quantErrorCurr[x+2][0] += er * 7
  1073  			quantErrorCurr[x+2][1] += eg * 7
  1074  			quantErrorCurr[x+2][2] += eb * 7
  1075  			quantErrorCurr[x+2][3] += ea * 7
  1076  		}
  1077  
  1078  		// Recycle the quantization error buffers.
  1079  		if floydSteinberg {
  1080  			quantErrorCurr, quantErrorNext = quantErrorNext, quantErrorCurr
  1081  			clear(quantErrorNext)
  1082  		}
  1083  	}
  1084  }
  1085
View as plain text