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 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