...
Run Format

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

View as plain text