...
Run Format

Source file src/pkg/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	// http://golang.org/doc/articles/image_draw.html
     9	package draw
    10	
    11	import (
    12		"image"
    13		"image/color"
    14	)
    15	
    16	// m is the maximum color value returned by image.Color.RGBA.
    17	const m = 1<<16 - 1
    18	
    19	// Image is an image.Image with a Set method to change a single pixel.
    20	type Image interface {
    21		image.Image
    22		Set(x, y int, c color.Color)
    23	}
    24	
    25	// Quantizer produces a palette for an image.
    26	type Quantizer interface {
    27		// Quantize appends up to cap(p) - len(p) colors to p and returns the
    28		// updated palette suitable for converting m to a paletted image.
    29		Quantize(p color.Palette, m image.Image) color.Palette
    30	}
    31	
    32	// Op is a Porter-Duff compositing operator.
    33	type Op int
    34	
    35	const (
    36		// Over specifies ``(src in mask) over dst''.
    37		Over Op = iota
    38		// Src specifies ``src in mask''.
    39		Src
    40	)
    41	
    42	// Draw implements the Drawer interface by calling the Draw function with this
    43	// Op.
    44	func (op Op) Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point) {
    45		DrawMask(dst, r, src, sp, nil, image.Point{}, op)
    46	}
    47	
    48	// Drawer contains the Draw method.
    49	type Drawer interface {
    50		// Draw aligns r.Min in dst with sp in src and then replaces the
    51		// rectangle r in dst with the result of drawing src on dst.
    52		Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point)
    53	}
    54	
    55	// FloydSteinberg is a Drawer that is the Src Op with Floyd-Steinberg error
    56	// diffusion.
    57	var FloydSteinberg Drawer = floydSteinberg{}
    58	
    59	type floydSteinberg struct{}
    60	
    61	func (floydSteinberg) Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point) {
    62		clip(dst, &r, src, &sp, nil, nil)
    63		if r.Empty() {
    64			return
    65		}
    66		drawPaletted(dst, r, src, sp, true)
    67	}
    68	
    69	// clip clips r against each image's bounds (after translating into the
    70	// destination image's co-ordinate space) and shifts the points sp and mp by
    71	// the same amount as the change in r.Min.
    72	func clip(dst Image, r *image.Rectangle, src image.Image, sp *image.Point, mask image.Image, mp *image.Point) {
    73		orig := r.Min
    74		*r = r.Intersect(dst.Bounds())
    75		*r = r.Intersect(src.Bounds().Add(orig.Sub(*sp)))
    76		if mask != nil {
    77			*r = r.Intersect(mask.Bounds().Add(orig.Sub(*mp)))
    78		}
    79		dx := r.Min.X - orig.X
    80		dy := r.Min.Y - orig.Y
    81		if dx == 0 && dy == 0 {
    82			return
    83		}
    84		(*sp).X += dx
    85		(*sp).Y += dy
    86		(*mp).X += dx
    87		(*mp).Y += dy
    88	}
    89	
    90	func processBackward(dst Image, r image.Rectangle, src image.Image, sp image.Point) bool {
    91		return image.Image(dst) == src &&
    92			r.Overlaps(r.Add(sp.Sub(r.Min))) &&
    93			(sp.Y < r.Min.Y || (sp.Y == r.Min.Y && sp.X < r.Min.X))
    94	}
    95	
    96	// Draw calls DrawMask with a nil mask.
    97	func Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point, op Op) {
    98		DrawMask(dst, r, src, sp, nil, image.Point{}, op)
    99	}
   100	
   101	// DrawMask aligns r.Min in dst with sp in src and mp in mask and then replaces the rectangle r
   102	// in dst with the result of a Porter-Duff composition. A nil mask is treated as opaque.
   103	func DrawMask(dst Image, r image.Rectangle, src image.Image, sp image.Point, mask image.Image, mp image.Point, op Op) {
   104		clip(dst, &r, src, &sp, mask, &mp)
   105		if r.Empty() {
   106			return
   107		}
   108	
   109		// Fast paths for special cases. If none of them apply, then we fall back to a general but slow implementation.
   110		switch dst0 := dst.(type) {
   111		case *image.RGBA:
   112			if op == Over {
   113				if mask == nil {
   114					switch src0 := src.(type) {
   115					case *image.Uniform:
   116						drawFillOver(dst0, r, src0)
   117						return
   118					case *image.RGBA:
   119						drawCopyOver(dst0, r, src0, sp)
   120						return
   121					case *image.NRGBA:
   122						drawNRGBAOver(dst0, r, src0, sp)
   123						return
   124					case *image.YCbCr:
   125						if drawYCbCr(dst0, r, src0, sp) {
   126							return
   127						}
   128					}
   129				} else if mask0, ok := mask.(*image.Alpha); ok {
   130					switch src0 := src.(type) {
   131					case *image.Uniform:
   132						drawGlyphOver(dst0, r, src0, mask0, mp)
   133						return
   134					}
   135				}
   136			} else {
   137				if mask == nil {
   138					switch src0 := src.(type) {
   139					case *image.Uniform:
   140						drawFillSrc(dst0, r, src0)
   141						return
   142					case *image.RGBA:
   143						drawCopySrc(dst0, r, src0, sp)
   144						return
   145					case *image.NRGBA:
   146						drawNRGBASrc(dst0, r, src0, sp)
   147						return
   148					case *image.YCbCr:
   149						if drawYCbCr(dst0, r, src0, sp) {
   150							return
   151						}
   152					}
   153				}
   154			}
   155			drawRGBA(dst0, r, src, sp, mask, mp, op)
   156			return
   157		case *image.Paletted:
   158			if op == Src && mask == nil && !processBackward(dst, r, src, sp) {
   159				drawPaletted(dst0, r, src, sp, false)
   160			}
   161		}
   162	
   163		x0, x1, dx := r.Min.X, r.Max.X, 1
   164		y0, y1, dy := r.Min.Y, r.Max.Y, 1
   165		if processBackward(dst, r, src, sp) {
   166			x0, x1, dx = x1-1, x0-1, -1
   167			y0, y1, dy = y1-1, y0-1, -1
   168		}
   169	
   170		var out color.RGBA64
   171		sy := sp.Y + y0 - r.Min.Y
   172		my := mp.Y + y0 - r.Min.Y
   173		for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   174			sx := sp.X + x0 - r.Min.X
   175			mx := mp.X + x0 - r.Min.X
   176			for x := x0; x != x1; x, sx, mx = x+dx, sx+dx, mx+dx {
   177				ma := uint32(m)
   178				if mask != nil {
   179					_, _, _, ma = mask.At(mx, my).RGBA()
   180				}
   181				switch {
   182				case ma == 0:
   183					if op == Over {
   184						// No-op.
   185					} else {
   186						dst.Set(x, y, color.Transparent)
   187					}
   188				case ma == m && op == Src:
   189					dst.Set(x, y, src.At(sx, sy))
   190				default:
   191					sr, sg, sb, sa := src.At(sx, sy).RGBA()
   192					if op == Over {
   193						dr, dg, db, da := dst.At(x, y).RGBA()
   194						a := m - (sa * ma / m)
   195						out.R = uint16((dr*a + sr*ma) / m)
   196						out.G = uint16((dg*a + sg*ma) / m)
   197						out.B = uint16((db*a + sb*ma) / m)
   198						out.A = uint16((da*a + sa*ma) / m)
   199					} else {
   200						out.R = uint16(sr * ma / m)
   201						out.G = uint16(sg * ma / m)
   202						out.B = uint16(sb * ma / m)
   203						out.A = uint16(sa * ma / m)
   204					}
   205					// The third argument is &out instead of out (and out is
   206					// declared outside of the inner loop) to avoid the implicit
   207					// conversion to color.Color here allocating memory in the
   208					// inner loop if sizeof(color.RGBA64) > sizeof(uintptr).
   209					dst.Set(x, y, &out)
   210				}
   211			}
   212		}
   213	}
   214	
   215	func drawFillOver(dst *image.RGBA, r image.Rectangle, src *image.Uniform) {
   216		sr, sg, sb, sa := src.RGBA()
   217		// The 0x101 is here for the same reason as in drawRGBA.
   218		a := (m - sa) * 0x101
   219		i0 := dst.PixOffset(r.Min.X, r.Min.Y)
   220		i1 := i0 + r.Dx()*4
   221		for y := r.Min.Y; y != r.Max.Y; y++ {
   222			for i := i0; i < i1; i += 4 {
   223				dr := uint32(dst.Pix[i+0])
   224				dg := uint32(dst.Pix[i+1])
   225				db := uint32(dst.Pix[i+2])
   226				da := uint32(dst.Pix[i+3])
   227	
   228				dst.Pix[i+0] = uint8((dr*a/m + sr) >> 8)
   229				dst.Pix[i+1] = uint8((dg*a/m + sg) >> 8)
   230				dst.Pix[i+2] = uint8((db*a/m + sb) >> 8)
   231				dst.Pix[i+3] = uint8((da*a/m + sa) >> 8)
   232			}
   233			i0 += dst.Stride
   234			i1 += dst.Stride
   235		}
   236	}
   237	
   238	func drawFillSrc(dst *image.RGBA, r image.Rectangle, src *image.Uniform) {
   239		sr, sg, sb, sa := src.RGBA()
   240		// The built-in copy function is faster than a straightforward for loop to fill the destination with
   241		// the color, but copy requires a slice source. We therefore use a for loop to fill the first row, and
   242		// then use the first row as the slice source for the remaining rows.
   243		i0 := dst.PixOffset(r.Min.X, r.Min.Y)
   244		i1 := i0 + r.Dx()*4
   245		for i := i0; i < i1; i += 4 {
   246			dst.Pix[i+0] = uint8(sr >> 8)
   247			dst.Pix[i+1] = uint8(sg >> 8)
   248			dst.Pix[i+2] = uint8(sb >> 8)
   249			dst.Pix[i+3] = uint8(sa >> 8)
   250		}
   251		firstRow := dst.Pix[i0:i1]
   252		for y := r.Min.Y + 1; y < r.Max.Y; y++ {
   253			i0 += dst.Stride
   254			i1 += dst.Stride
   255			copy(dst.Pix[i0:i1], firstRow)
   256		}
   257	}
   258	
   259	func drawCopyOver(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point) {
   260		dx, dy := r.Dx(), r.Dy()
   261		d0 := dst.PixOffset(r.Min.X, r.Min.Y)
   262		s0 := src.PixOffset(sp.X, sp.Y)
   263		var (
   264			ddelta, sdelta int
   265			i0, i1, idelta int
   266		)
   267		if r.Min.Y < sp.Y || r.Min.Y == sp.Y && r.Min.X <= sp.X {
   268			ddelta = dst.Stride
   269			sdelta = src.Stride
   270			i0, i1, idelta = 0, dx*4, +4
   271		} else {
   272			// If the source start point is higher than the destination start point, or equal height but to the left,
   273			// then we compose the rows in right-to-left, bottom-up order instead of left-to-right, top-down.
   274			d0 += (dy - 1) * dst.Stride
   275			s0 += (dy - 1) * src.Stride
   276			ddelta = -dst.Stride
   277			sdelta = -src.Stride
   278			i0, i1, idelta = (dx-1)*4, -4, -4
   279		}
   280		for ; dy > 0; dy-- {
   281			dpix := dst.Pix[d0:]
   282			spix := src.Pix[s0:]
   283			for i := i0; i != i1; i += idelta {
   284				sr := uint32(spix[i+0]) * 0x101
   285				sg := uint32(spix[i+1]) * 0x101
   286				sb := uint32(spix[i+2]) * 0x101
   287				sa := uint32(spix[i+3]) * 0x101
   288	
   289				dr := uint32(dpix[i+0])
   290				dg := uint32(dpix[i+1])
   291				db := uint32(dpix[i+2])
   292				da := uint32(dpix[i+3])
   293	
   294				// The 0x101 is here for the same reason as in drawRGBA.
   295				a := (m - sa) * 0x101
   296	
   297				dpix[i+0] = uint8((dr*a/m + sr) >> 8)
   298				dpix[i+1] = uint8((dg*a/m + sg) >> 8)
   299				dpix[i+2] = uint8((db*a/m + sb) >> 8)
   300				dpix[i+3] = uint8((da*a/m + sa) >> 8)
   301			}
   302			d0 += ddelta
   303			s0 += sdelta
   304		}
   305	}
   306	
   307	func drawCopySrc(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point) {
   308		n, dy := 4*r.Dx(), r.Dy()
   309		d0 := dst.PixOffset(r.Min.X, r.Min.Y)
   310		s0 := src.PixOffset(sp.X, sp.Y)
   311		var ddelta, sdelta int
   312		if r.Min.Y <= sp.Y {
   313			ddelta = dst.Stride
   314			sdelta = src.Stride
   315		} else {
   316			// If the source start point is higher than the destination start point, then we compose the rows
   317			// in bottom-up order instead of top-down. Unlike the drawCopyOver function, we don't have to
   318			// check the x co-ordinates because the built-in copy function can handle overlapping slices.
   319			d0 += (dy - 1) * dst.Stride
   320			s0 += (dy - 1) * src.Stride
   321			ddelta = -dst.Stride
   322			sdelta = -src.Stride
   323		}
   324		for ; dy > 0; dy-- {
   325			copy(dst.Pix[d0:d0+n], src.Pix[s0:s0+n])
   326			d0 += ddelta
   327			s0 += sdelta
   328		}
   329	}
   330	
   331	func drawNRGBAOver(dst *image.RGBA, r image.Rectangle, src *image.NRGBA, sp image.Point) {
   332		i0 := (r.Min.X - dst.Rect.Min.X) * 4
   333		i1 := (r.Max.X - dst.Rect.Min.X) * 4
   334		si0 := (sp.X - src.Rect.Min.X) * 4
   335		yMax := r.Max.Y - dst.Rect.Min.Y
   336	
   337		y := r.Min.Y - dst.Rect.Min.Y
   338		sy := sp.Y - src.Rect.Min.Y
   339		for ; y != yMax; y, sy = y+1, sy+1 {
   340			dpix := dst.Pix[y*dst.Stride:]
   341			spix := src.Pix[sy*src.Stride:]
   342	
   343			for i, si := i0, si0; i < i1; i, si = i+4, si+4 {
   344				// Convert from non-premultiplied color to pre-multiplied color.
   345				sa := uint32(spix[si+3]) * 0x101
   346				sr := uint32(spix[si+0]) * sa / 0xff
   347				sg := uint32(spix[si+1]) * sa / 0xff
   348				sb := uint32(spix[si+2]) * sa / 0xff
   349	
   350				dr := uint32(dpix[i+0])
   351				dg := uint32(dpix[i+1])
   352				db := uint32(dpix[i+2])
   353				da := uint32(dpix[i+3])
   354	
   355				// The 0x101 is here for the same reason as in drawRGBA.
   356				a := (m - sa) * 0x101
   357	
   358				dpix[i+0] = uint8((dr*a/m + sr) >> 8)
   359				dpix[i+1] = uint8((dg*a/m + sg) >> 8)
   360				dpix[i+2] = uint8((db*a/m + sb) >> 8)
   361				dpix[i+3] = uint8((da*a/m + sa) >> 8)
   362			}
   363		}
   364	}
   365	
   366	func drawNRGBASrc(dst *image.RGBA, r image.Rectangle, src *image.NRGBA, sp image.Point) {
   367		i0 := (r.Min.X - dst.Rect.Min.X) * 4
   368		i1 := (r.Max.X - dst.Rect.Min.X) * 4
   369		si0 := (sp.X - src.Rect.Min.X) * 4
   370		yMax := r.Max.Y - dst.Rect.Min.Y
   371	
   372		y := r.Min.Y - dst.Rect.Min.Y
   373		sy := sp.Y - src.Rect.Min.Y
   374		for ; y != yMax; y, sy = y+1, sy+1 {
   375			dpix := dst.Pix[y*dst.Stride:]
   376			spix := src.Pix[sy*src.Stride:]
   377	
   378			for i, si := i0, si0; i < i1; i, si = i+4, si+4 {
   379				// Convert from non-premultiplied color to pre-multiplied color.
   380				sa := uint32(spix[si+3]) * 0x101
   381				sr := uint32(spix[si+0]) * sa / 0xff
   382				sg := uint32(spix[si+1]) * sa / 0xff
   383				sb := uint32(spix[si+2]) * sa / 0xff
   384	
   385				dpix[i+0] = uint8(sr >> 8)
   386				dpix[i+1] = uint8(sg >> 8)
   387				dpix[i+2] = uint8(sb >> 8)
   388				dpix[i+3] = uint8(sa >> 8)
   389			}
   390		}
   391	}
   392	
   393	func drawYCbCr(dst *image.RGBA, r image.Rectangle, src *image.YCbCr, sp image.Point) (ok bool) {
   394		// An image.YCbCr is always fully opaque, and so if the mask is implicitly nil
   395		// (i.e. fully opaque) then the op is effectively always Src.
   396		x0 := (r.Min.X - dst.Rect.Min.X) * 4
   397		x1 := (r.Max.X - dst.Rect.Min.X) * 4
   398		y0 := r.Min.Y - dst.Rect.Min.Y
   399		y1 := r.Max.Y - dst.Rect.Min.Y
   400		switch src.SubsampleRatio {
   401		case image.YCbCrSubsampleRatio444:
   402			for y, sy := y0, sp.Y; y != y1; y, sy = y+1, sy+1 {
   403				dpix := dst.Pix[y*dst.Stride:]
   404				yi := (sy-src.Rect.Min.Y)*src.YStride + (sp.X - src.Rect.Min.X)
   405				ci := (sy-src.Rect.Min.Y)*src.CStride + (sp.X - src.Rect.Min.X)
   406				for x := x0; x != x1; x, yi, ci = x+4, yi+1, ci+1 {
   407					rr, gg, bb := color.YCbCrToRGB(src.Y[yi], src.Cb[ci], src.Cr[ci])
   408					dpix[x+0] = rr
   409					dpix[x+1] = gg
   410					dpix[x+2] = bb
   411					dpix[x+3] = 255
   412				}
   413			}
   414		case image.YCbCrSubsampleRatio422:
   415			for y, sy := y0, sp.Y; y != y1; y, sy = y+1, sy+1 {
   416				dpix := dst.Pix[y*dst.Stride:]
   417				yi := (sy-src.Rect.Min.Y)*src.YStride + (sp.X - src.Rect.Min.X)
   418				ciBase := (sy-src.Rect.Min.Y)*src.CStride - src.Rect.Min.X/2
   419				for x, sx := x0, sp.X; x != x1; x, sx, yi = x+4, sx+1, yi+1 {
   420					ci := ciBase + sx/2
   421					rr, gg, bb := color.YCbCrToRGB(src.Y[yi], src.Cb[ci], src.Cr[ci])
   422					dpix[x+0] = rr
   423					dpix[x+1] = gg
   424					dpix[x+2] = bb
   425					dpix[x+3] = 255
   426				}
   427			}
   428		case image.YCbCrSubsampleRatio420:
   429			for y, sy := y0, sp.Y; y != y1; y, sy = y+1, sy+1 {
   430				dpix := dst.Pix[y*dst.Stride:]
   431				yi := (sy-src.Rect.Min.Y)*src.YStride + (sp.X - src.Rect.Min.X)
   432				ciBase := (sy/2-src.Rect.Min.Y/2)*src.CStride - src.Rect.Min.X/2
   433				for x, sx := x0, sp.X; x != x1; x, sx, yi = x+4, sx+1, yi+1 {
   434					ci := ciBase + sx/2
   435					rr, gg, bb := color.YCbCrToRGB(src.Y[yi], src.Cb[ci], src.Cr[ci])
   436					dpix[x+0] = rr
   437					dpix[x+1] = gg
   438					dpix[x+2] = bb
   439					dpix[x+3] = 255
   440				}
   441			}
   442		case image.YCbCrSubsampleRatio440:
   443			for y, sy := y0, sp.Y; y != y1; y, sy = y+1, sy+1 {
   444				dpix := dst.Pix[y*dst.Stride:]
   445				yi := (sy-src.Rect.Min.Y)*src.YStride + (sp.X - src.Rect.Min.X)
   446				ci := (sy/2-src.Rect.Min.Y/2)*src.CStride + (sp.X - src.Rect.Min.X)
   447				for x := x0; x != x1; x, yi, ci = x+4, yi+1, ci+1 {
   448					rr, gg, bb := color.YCbCrToRGB(src.Y[yi], src.Cb[ci], src.Cr[ci])
   449					dpix[x+0] = rr
   450					dpix[x+1] = gg
   451					dpix[x+2] = bb
   452					dpix[x+3] = 255
   453				}
   454			}
   455		default:
   456			return false
   457		}
   458		return true
   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	func drawPaletted(dst Image, r image.Rectangle, src image.Image, sp image.Point, floydSteinberg bool) {
   559		// TODO(nigeltao): handle the case where the dst and src overlap.
   560		// Does it even make sense to try and do Floyd-Steinberg whilst
   561		// walking the image backward (right-to-left bottom-to-top)?
   562	
   563		// If dst is an *image.Paletted, we have a fast path for dst.Set and
   564		// dst.At. The dst.Set equivalent is a batch version of the algorithm
   565		// used by color.Palette's Index method in image/color/color.go, plus
   566		// optional Floyd-Steinberg error diffusion.
   567		palette, pix, stride := [][3]int32(nil), []byte(nil), 0
   568		if p, ok := dst.(*image.Paletted); ok {
   569			palette = make([][3]int32, len(p.Palette))
   570			for i, col := range p.Palette {
   571				r, g, b, _ := col.RGBA()
   572				palette[i][0] = int32(r)
   573				palette[i][1] = int32(g)
   574				palette[i][2] = int32(b)
   575			}
   576			pix, stride = p.Pix[p.PixOffset(r.Min.X, r.Min.Y):], p.Stride
   577		}
   578	
   579		// quantErrorCurr and quantErrorNext are the Floyd-Steinberg quantization
   580		// errors that have been propagated to the pixels in the current and next
   581		// rows. The +2 simplifies calculation near the edges.
   582		var quantErrorCurr, quantErrorNext [][3]int32
   583		if floydSteinberg {
   584			quantErrorCurr = make([][3]int32, r.Dx()+2)
   585			quantErrorNext = make([][3]int32, r.Dx()+2)
   586		}
   587	
   588		// Loop over each source pixel.
   589		out := color.RGBA64{A: 0xffff}
   590		for y := 0; y != r.Dy(); y++ {
   591			for x := 0; x != r.Dx(); x++ {
   592				// er, eg and eb are the pixel's R,G,B values plus the
   593				// optional Floyd-Steinberg error.
   594				sr, sg, sb, _ := src.At(sp.X+x, sp.Y+y).RGBA()
   595				er, eg, eb := int32(sr), int32(sg), int32(sb)
   596				if floydSteinberg {
   597					er = clamp(er + quantErrorCurr[x+1][0]/16)
   598					eg = clamp(eg + quantErrorCurr[x+1][1]/16)
   599					eb = clamp(eb + quantErrorCurr[x+1][2]/16)
   600				}
   601	
   602				if palette != nil {
   603					// Find the closest palette color in Euclidean R,G,B space: the
   604					// one that minimizes sum-squared-difference. We shift by 1 bit
   605					// to avoid potential uint32 overflow in sum-squared-difference.
   606					// TODO(nigeltao): consider smarter algorithms.
   607					bestIndex, bestSSD := 0, uint32(1<<32-1)
   608					for index, p := range palette {
   609						delta := (er - p[0]) >> 1
   610						ssd := uint32(delta * delta)
   611						delta = (eg - p[1]) >> 1
   612						ssd += uint32(delta * delta)
   613						delta = (eb - p[2]) >> 1
   614						ssd += uint32(delta * delta)
   615						if ssd < bestSSD {
   616							bestIndex, bestSSD = index, ssd
   617							if ssd == 0 {
   618								break
   619							}
   620						}
   621					}
   622					pix[y*stride+x] = byte(bestIndex)
   623	
   624					if !floydSteinberg {
   625						continue
   626					}
   627					er -= int32(palette[bestIndex][0])
   628					eg -= int32(palette[bestIndex][1])
   629					eb -= int32(palette[bestIndex][2])
   630	
   631				} else {
   632					out.R = uint16(er)
   633					out.G = uint16(eg)
   634					out.B = uint16(eb)
   635					// The third argument is &out instead of out (and out is
   636					// declared outside of the inner loop) to avoid the implicit
   637					// conversion to color.Color here allocating memory in the
   638					// inner loop if sizeof(color.RGBA64) > sizeof(uintptr).
   639					dst.Set(r.Min.X+x, r.Min.Y+y, &out)
   640	
   641					if !floydSteinberg {
   642						continue
   643					}
   644					sr, sg, sb, _ = dst.At(r.Min.X+x, r.Min.Y+y).RGBA()
   645					er -= int32(sr)
   646					eg -= int32(sg)
   647					eb -= int32(sb)
   648				}
   649	
   650				// Propagate the Floyd-Steinberg quantization error.
   651				quantErrorNext[x+0][0] += er * 3
   652				quantErrorNext[x+0][1] += eg * 3
   653				quantErrorNext[x+0][2] += eb * 3
   654				quantErrorNext[x+1][0] += er * 5
   655				quantErrorNext[x+1][1] += eg * 5
   656				quantErrorNext[x+1][2] += eb * 5
   657				quantErrorNext[x+2][0] += er * 1
   658				quantErrorNext[x+2][1] += eg * 1
   659				quantErrorNext[x+2][2] += eb * 1
   660				quantErrorCurr[x+2][0] += er * 7
   661				quantErrorCurr[x+2][1] += eg * 7
   662				quantErrorCurr[x+2][2] += eb * 7
   663			}
   664	
   665			// Recycle the quantization error buffers.
   666			if floydSteinberg {
   667				quantErrorCurr, quantErrorNext = quantErrorNext, quantErrorCurr
   668				for i := range quantErrorNext {
   669					quantErrorNext[i] = [3]int32{}
   670				}
   671			}
   672		}
   673	}
   674	

View as plain text