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

View as plain text