...
Run Format

Source file src/image/draw/draw.go

Documentation: image/draw

     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  					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  			sr := uint32(spix[i+0]) * 0x101
   313  			sg := uint32(spix[i+1]) * 0x101
   314  			sb := uint32(spix[i+2]) * 0x101
   315  			sa := uint32(spix[i+3]) * 0x101
   316  
   317  			dr := &dpix[i+0]
   318  			dg := &dpix[i+1]
   319  			db := &dpix[i+2]
   320  			da := &dpix[i+3]
   321  
   322  			// The 0x101 is here for the same reason as in drawRGBA.
   323  			a := (m - sa) * 0x101
   324  
   325  			*dr = uint8((uint32(*dr)*a/m + sr) >> 8)
   326  			*dg = uint8((uint32(*dg)*a/m + sg) >> 8)
   327  			*db = uint8((uint32(*db)*a/m + sb) >> 8)
   328  			*da = uint8((uint32(*da)*a/m + sa) >> 8)
   329  		}
   330  		d0 += ddelta
   331  		s0 += sdelta
   332  	}
   333  }
   334  
   335  func drawCopySrc(dst *image.RGBA, r image.Rectangle, src *image.RGBA, sp image.Point) {
   336  	n, dy := 4*r.Dx(), r.Dy()
   337  	d0 := dst.PixOffset(r.Min.X, r.Min.Y)
   338  	s0 := src.PixOffset(sp.X, sp.Y)
   339  	var ddelta, sdelta int
   340  	if r.Min.Y <= sp.Y {
   341  		ddelta = dst.Stride
   342  		sdelta = src.Stride
   343  	} else {
   344  		// If the source start point is higher than the destination start
   345  		// point, then we compose the rows in bottom-up order instead of
   346  		// top-down. Unlike the drawCopyOver function, we don't have to check
   347  		// the x coordinates because the built-in copy function can handle
   348  		// overlapping slices.
   349  		d0 += (dy - 1) * dst.Stride
   350  		s0 += (dy - 1) * src.Stride
   351  		ddelta = -dst.Stride
   352  		sdelta = -src.Stride
   353  	}
   354  	for ; dy > 0; dy-- {
   355  		copy(dst.Pix[d0:d0+n], src.Pix[s0:s0+n])
   356  		d0 += ddelta
   357  		s0 += sdelta
   358  	}
   359  }
   360  
   361  func drawNRGBAOver(dst *image.RGBA, r image.Rectangle, src *image.NRGBA, sp image.Point) {
   362  	i0 := (r.Min.X - dst.Rect.Min.X) * 4
   363  	i1 := (r.Max.X - dst.Rect.Min.X) * 4
   364  	si0 := (sp.X - src.Rect.Min.X) * 4
   365  	yMax := r.Max.Y - dst.Rect.Min.Y
   366  
   367  	y := r.Min.Y - dst.Rect.Min.Y
   368  	sy := sp.Y - src.Rect.Min.Y
   369  	for ; y != yMax; y, sy = y+1, sy+1 {
   370  		dpix := dst.Pix[y*dst.Stride:]
   371  		spix := src.Pix[sy*src.Stride:]
   372  
   373  		for i, si := i0, si0; i < i1; i, si = i+4, si+4 {
   374  			// Convert from non-premultiplied color to pre-multiplied color.
   375  			sa := uint32(spix[si+3]) * 0x101
   376  			sr := uint32(spix[si+0]) * sa / 0xff
   377  			sg := uint32(spix[si+1]) * sa / 0xff
   378  			sb := uint32(spix[si+2]) * sa / 0xff
   379  
   380  			dr := uint32(dpix[i+0])
   381  			dg := uint32(dpix[i+1])
   382  			db := uint32(dpix[i+2])
   383  			da := uint32(dpix[i+3])
   384  
   385  			// The 0x101 is here for the same reason as in drawRGBA.
   386  			a := (m - sa) * 0x101
   387  
   388  			dpix[i+0] = uint8((dr*a/m + sr) >> 8)
   389  			dpix[i+1] = uint8((dg*a/m + sg) >> 8)
   390  			dpix[i+2] = uint8((db*a/m + sb) >> 8)
   391  			dpix[i+3] = uint8((da*a/m + sa) >> 8)
   392  		}
   393  	}
   394  }
   395  
   396  func drawNRGBASrc(dst *image.RGBA, r image.Rectangle, src *image.NRGBA, sp image.Point) {
   397  	i0 := (r.Min.X - dst.Rect.Min.X) * 4
   398  	i1 := (r.Max.X - dst.Rect.Min.X) * 4
   399  	si0 := (sp.X - src.Rect.Min.X) * 4
   400  	yMax := r.Max.Y - dst.Rect.Min.Y
   401  
   402  	y := r.Min.Y - dst.Rect.Min.Y
   403  	sy := sp.Y - src.Rect.Min.Y
   404  	for ; y != yMax; y, sy = y+1, sy+1 {
   405  		dpix := dst.Pix[y*dst.Stride:]
   406  		spix := src.Pix[sy*src.Stride:]
   407  
   408  		for i, si := i0, si0; i < i1; i, si = i+4, si+4 {
   409  			// Convert from non-premultiplied color to pre-multiplied color.
   410  			sa := uint32(spix[si+3]) * 0x101
   411  			sr := uint32(spix[si+0]) * sa / 0xff
   412  			sg := uint32(spix[si+1]) * sa / 0xff
   413  			sb := uint32(spix[si+2]) * sa / 0xff
   414  
   415  			dpix[i+0] = uint8(sr >> 8)
   416  			dpix[i+1] = uint8(sg >> 8)
   417  			dpix[i+2] = uint8(sb >> 8)
   418  			dpix[i+3] = uint8(sa >> 8)
   419  		}
   420  	}
   421  }
   422  
   423  func drawGray(dst *image.RGBA, r image.Rectangle, src *image.Gray, sp image.Point) {
   424  	i0 := (r.Min.X - dst.Rect.Min.X) * 4
   425  	i1 := (r.Max.X - dst.Rect.Min.X) * 4
   426  	si0 := (sp.X - src.Rect.Min.X) * 1
   427  	yMax := r.Max.Y - dst.Rect.Min.Y
   428  
   429  	y := r.Min.Y - dst.Rect.Min.Y
   430  	sy := sp.Y - src.Rect.Min.Y
   431  	for ; y != yMax; y, sy = y+1, sy+1 {
   432  		dpix := dst.Pix[y*dst.Stride:]
   433  		spix := src.Pix[sy*src.Stride:]
   434  
   435  		for i, si := i0, si0; i < i1; i, si = i+4, si+1 {
   436  			p := spix[si]
   437  			dpix[i+0] = p
   438  			dpix[i+1] = p
   439  			dpix[i+2] = p
   440  			dpix[i+3] = 255
   441  		}
   442  	}
   443  }
   444  
   445  func drawCMYK(dst *image.RGBA, r image.Rectangle, src *image.CMYK, sp image.Point) {
   446  	i0 := (r.Min.X - dst.Rect.Min.X) * 4
   447  	i1 := (r.Max.X - dst.Rect.Min.X) * 4
   448  	si0 := (sp.X - src.Rect.Min.X) * 4
   449  	yMax := r.Max.Y - dst.Rect.Min.Y
   450  
   451  	y := r.Min.Y - dst.Rect.Min.Y
   452  	sy := sp.Y - src.Rect.Min.Y
   453  	for ; y != yMax; y, sy = y+1, sy+1 {
   454  		dpix := dst.Pix[y*dst.Stride:]
   455  		spix := src.Pix[sy*src.Stride:]
   456  
   457  		for i, si := i0, si0; i < i1; i, si = i+4, si+4 {
   458  			dpix[i+0], dpix[i+1], dpix[i+2] =
   459  				color.CMYKToRGB(spix[si+0], spix[si+1], spix[si+2], spix[si+3])
   460  			dpix[i+3] = 255
   461  		}
   462  	}
   463  }
   464  
   465  func drawGlyphOver(dst *image.RGBA, r image.Rectangle, src *image.Uniform, mask *image.Alpha, mp image.Point) {
   466  	i0 := dst.PixOffset(r.Min.X, r.Min.Y)
   467  	i1 := i0 + r.Dx()*4
   468  	mi0 := mask.PixOffset(mp.X, mp.Y)
   469  	sr, sg, sb, sa := src.RGBA()
   470  	for y, my := r.Min.Y, mp.Y; y != r.Max.Y; y, my = y+1, my+1 {
   471  		for i, mi := i0, mi0; i < i1; i, mi = i+4, mi+1 {
   472  			ma := uint32(mask.Pix[mi])
   473  			if ma == 0 {
   474  				continue
   475  			}
   476  			ma |= ma << 8
   477  
   478  			dr := &dst.Pix[i+0]
   479  			dg := &dst.Pix[i+1]
   480  			db := &dst.Pix[i+2]
   481  			da := &dst.Pix[i+3]
   482  
   483  			// The 0x101 is here for the same reason as in drawRGBA.
   484  			a := (m - (sa * ma / m)) * 0x101
   485  
   486  			*dr = uint8((uint32(*dr)*a + sr*ma) / m >> 8)
   487  			*dg = uint8((uint32(*dg)*a + sg*ma) / m >> 8)
   488  			*db = uint8((uint32(*db)*a + sb*ma) / m >> 8)
   489  			*da = uint8((uint32(*da)*a + sa*ma) / m >> 8)
   490  		}
   491  		i0 += dst.Stride
   492  		i1 += dst.Stride
   493  		mi0 += mask.Stride
   494  	}
   495  }
   496  
   497  func drawRGBA(dst *image.RGBA, r image.Rectangle, src image.Image, sp image.Point, mask image.Image, mp image.Point, op Op) {
   498  	x0, x1, dx := r.Min.X, r.Max.X, 1
   499  	y0, y1, dy := r.Min.Y, r.Max.Y, 1
   500  	if image.Image(dst) == src && r.Overlaps(r.Add(sp.Sub(r.Min))) {
   501  		if sp.Y < r.Min.Y || sp.Y == r.Min.Y && sp.X < r.Min.X {
   502  			x0, x1, dx = x1-1, x0-1, -1
   503  			y0, y1, dy = y1-1, y0-1, -1
   504  		}
   505  	}
   506  
   507  	sy := sp.Y + y0 - r.Min.Y
   508  	my := mp.Y + y0 - r.Min.Y
   509  	sx0 := sp.X + x0 - r.Min.X
   510  	mx0 := mp.X + x0 - r.Min.X
   511  	sx1 := sx0 + (x1 - x0)
   512  	i0 := dst.PixOffset(x0, y0)
   513  	di := dx * 4
   514  	for y := y0; y != y1; y, sy, my = y+dy, sy+dy, my+dy {
   515  		for i, sx, mx := i0, sx0, mx0; sx != sx1; i, sx, mx = i+di, sx+dx, mx+dx {
   516  			ma := uint32(m)
   517  			if mask != nil {
   518  				_, _, _, ma = mask.At(mx, my).RGBA()
   519  			}
   520  			sr, sg, sb, sa := src.At(sx, sy).RGBA()
   521  			if op == Over {
   522  				dr := uint32(dst.Pix[i+0])
   523  				dg := uint32(dst.Pix[i+1])
   524  				db := uint32(dst.Pix[i+2])
   525  				da := uint32(dst.Pix[i+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  				dst.Pix[i+0] = uint8((dr*a + sr*ma) / m >> 8)
   536  				dst.Pix[i+1] = uint8((dg*a + sg*ma) / m >> 8)
   537  				dst.Pix[i+2] = uint8((db*a + sb*ma) / m >> 8)
   538  				dst.Pix[i+3] = uint8((da*a + sa*ma) / m >> 8)
   539  
   540  			} else {
   541  				dst.Pix[i+0] = uint8(sr * ma / m >> 8)
   542  				dst.Pix[i+1] = uint8(sg * ma / m >> 8)
   543  				dst.Pix[i+2] = uint8(sb * ma / m >> 8)
   544  				dst.Pix[i+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