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

View as plain text