// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package draw provides image composition functions. // // See "The Go image/draw package" for an introduction to this package: // https://golang.org/doc/articles/image_draw.html
package draw import ( ) // m is the maximum color value returned by image.Color.RGBA. const m = 1<<16 - 1 // Image is an image.Image with a Set method to change a single pixel. type Image interface { image.Image Set(x, y int, c color.Color) } // RGBA64Image extends both the Image and image.RGBA64Image interfaces with a // SetRGBA64 method to change a single pixel. SetRGBA64 is equivalent to // calling Set, but it can avoid allocations from converting concrete color // types to the color.Color interface type. type RGBA64Image interface { image.RGBA64Image Set(x, y int, c color.Color) SetRGBA64(x, y int, c color.RGBA64) } // Quantizer produces a palette for an image. type Quantizer interface { // Quantize appends up to cap(p) - len(p) colors to p and returns the // updated palette suitable for converting m to a paletted image. Quantize(p color.Palette, m image.Image) color.Palette } // Op is a Porter-Duff compositing operator. type Op int const ( // Over specifies ``(src in mask) over dst''. Over Op = iota // Src specifies ``src in mask''. Src ) // Draw implements the Drawer interface by calling the Draw function with this // Op. func ( Op) ( Image, image.Rectangle, image.Image, image.Point) { DrawMask(, , , , nil, image.Point{}, ) } // Drawer contains the Draw method. type Drawer interface { // Draw aligns r.Min in dst with sp in src and then replaces the // rectangle r in dst with the result of drawing src on dst. Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point) } // FloydSteinberg is a Drawer that is the Src Op with Floyd-Steinberg error // diffusion. var FloydSteinberg Drawer = floydSteinberg{} type floydSteinberg struct{} func (floydSteinberg) ( Image, image.Rectangle, image.Image, image.Point) { clip(, &, , &, nil, nil) if .Empty() { return } drawPaletted(, , , , true) } // clip clips r against each image's bounds (after translating into the // destination image's coordinate space) and shifts the points sp and mp by // the same amount as the change in r.Min. func clip( Image, *image.Rectangle, image.Image, *image.Point, image.Image, *image.Point) { := .Min * = .Intersect(.Bounds()) * = .Intersect(.Bounds().Add(.Sub(*))) if != nil { * = .Intersect(.Bounds().Add(.Sub(*))) } := .Min.X - .X := .Min.Y - .Y if == 0 && == 0 { return } .X += .Y += if != nil { .X += .Y += } } func processBackward( image.Image, image.Rectangle, image.Image, image.Point) bool { return == && .Overlaps(.Add(.Sub(.Min))) && (.Y < .Min.Y || (.Y == .Min.Y && .X < .Min.X)) } // Draw calls DrawMask with a nil mask. func ( Image, image.Rectangle, image.Image, image.Point, Op) { DrawMask(, , , , nil, image.Point{}, ) } // DrawMask aligns r.Min in dst with sp in src and mp in mask and then replaces the rectangle r // in dst with the result of a Porter-Duff composition. A nil mask is treated as opaque. func ( Image, image.Rectangle, image.Image, image.Point, image.Image, image.Point, Op) { clip(, &, , &, , &) if .Empty() { return } // Fast paths for special cases. If none of them apply, then we fall back to a general but slow implementation. switch dst0 := .(type) { case *image.RGBA: if == Over { if == nil { switch src0 := .(type) { case *image.Uniform: , , , := .RGBA() if == 0xffff { drawFillSrc(, , , , , ) } else { drawFillOver(, , , , , ) } return case *image.RGBA: drawCopyOver(, , , ) return case *image.NRGBA: drawNRGBAOver(, , , ) return case *image.YCbCr: // An image.YCbCr is always fully opaque, and so if the // mask is nil (i.e. fully opaque) then the op is // effectively always Src. Similarly for image.Gray and // image.CMYK. if imageutil.DrawYCbCr(, , , ) { return } case *image.Gray: drawGray(, , , ) return case *image.CMYK: drawCMYK(, , , ) return } } else if , := .(*image.Alpha); { switch src0 := .(type) { case *image.Uniform: drawGlyphOver(, , , , ) return } } } else { if == nil { switch src0 := .(type) { case *image.Uniform: , , , := .RGBA() drawFillSrc(, , , , , ) return case *image.RGBA: drawCopySrc(, , , ) return case *image.NRGBA: drawNRGBASrc(, , , ) return case *image.YCbCr: if imageutil.DrawYCbCr(, , , ) { return } case *image.Gray: drawGray(, , , ) return case *image.CMYK: drawCMYK(, , , ) return } } } drawRGBA(, , , , , , ) return case *image.Paletted: if == Src && == nil { if , := .(*image.Uniform); { := uint8(.Palette.Index(.C)) := .PixOffset(.Min.X, .Min.Y) := + .Dx() for := ; < ; ++ { .Pix[] = } := .Pix[:] for := .Min.Y + 1; < .Max.Y; ++ { += .Stride += .Stride copy(.Pix[:], ) } return } else if !processBackward(, , , ) { drawPaletted(, , , , false) return } } } , , := .Min.X, .Max.X, 1 , , := .Min.Y, .Max.Y, 1 if processBackward(, , , ) { , , = -1, -1, -1 , , = -1, -1, -1 } var color.RGBA64 := .Y + - .Min.Y := .Y + - .Min.Y for := ; != ; , , = +, +, + { := .X + - .Min.X := .X + - .Min.X for := ; != ; , , = +, +, + { := uint32(m) if != nil { _, _, _, = .At(, ).RGBA() } switch { case == 0: if == Over { // No-op. } else { .Set(, , color.Transparent) } case == m && == Src: .Set(, , .At(, )) default: , , , := .At(, ).RGBA() if == Over { , , , := .At(, ).RGBA() := m - ( * / m) .R = uint16((* + *) / m) .G = uint16((* + *) / m) .B = uint16((* + *) / m) .A = uint16((* + *) / m) } else { .R = uint16( * / m) .G = uint16( * / m) .B = uint16( * / m) .A = uint16( * / m) } // The third argument is &out instead of out (and out is // declared outside of the inner loop) to avoid the implicit // conversion to color.Color here allocating memory in the // inner loop if sizeof(color.RGBA64) > sizeof(uintptr). .Set(, , &) } } } } func drawFillOver( *image.RGBA, image.Rectangle, , , , uint32) { // The 0x101 is here for the same reason as in drawRGBA. := (m - ) * 0x101 := .PixOffset(.Min.X, .Min.Y) := + .Dx()*4 for := .Min.Y; != .Max.Y; ++ { for := ; < ; += 4 { := &.Pix[+0] := &.Pix[+1] := &.Pix[+2] := &.Pix[+3] * = uint8((uint32(*)*/m + ) >> 8) * = uint8((uint32(*)*/m + ) >> 8) * = uint8((uint32(*)*/m + ) >> 8) * = uint8((uint32(*)*/m + ) >> 8) } += .Stride += .Stride } } func drawFillSrc( *image.RGBA, image.Rectangle, , , , uint32) { := uint8( >> 8) := uint8( >> 8) := uint8( >> 8) := uint8( >> 8) // The built-in copy function is faster than a straightforward for loop to fill the destination with // the color, but copy requires a slice source. We therefore use a for loop to fill the first row, and // then use the first row as the slice source for the remaining rows. := .PixOffset(.Min.X, .Min.Y) := + .Dx()*4 for := ; < ; += 4 { .Pix[+0] = .Pix[+1] = .Pix[+2] = .Pix[+3] = } := .Pix[:] for := .Min.Y + 1; < .Max.Y; ++ { += .Stride += .Stride copy(.Pix[:], ) } } func drawCopyOver( *image.RGBA, image.Rectangle, *image.RGBA, image.Point) { , := .Dx(), .Dy() := .PixOffset(.Min.X, .Min.Y) := .PixOffset(.X, .Y) var ( , int , , int ) if .Min.Y < .Y || .Min.Y == .Y && .Min.X <= .X { = .Stride = .Stride , , = 0, *4, +4 } else { // If the source start point is higher than the destination start point, or equal height but to the left, // then we compose the rows in right-to-left, bottom-up order instead of left-to-right, top-down. += ( - 1) * .Stride += ( - 1) * .Stride = -.Stride = -.Stride , , = (-1)*4, -4, -4 } for ; > 0; -- { := .Pix[:] := .Pix[:] for := ; != ; += { := [ : +4 : +4] // Small cap improves performance, see https://golang.org/issue/27857 := uint32([0]) * 0x101 := uint32([1]) * 0x101 := uint32([2]) * 0x101 := uint32([3]) * 0x101 // The 0x101 is here for the same reason as in drawRGBA. := (m - ) * 0x101 := [ : +4 : +4] // Small cap improves performance, see https://golang.org/issue/27857 [0] = uint8((uint32([0])*/m + ) >> 8) [1] = uint8((uint32([1])*/m + ) >> 8) [2] = uint8((uint32([2])*/m + ) >> 8) [3] = uint8((uint32([3])*/m + ) >> 8) } += += } } func drawCopySrc( *image.RGBA, image.Rectangle, *image.RGBA, image.Point) { , := 4*.Dx(), .Dy() := .PixOffset(.Min.X, .Min.Y) := .PixOffset(.X, .Y) var , int if .Min.Y <= .Y { = .Stride = .Stride } else { // If the source start point is higher than the destination start // point, then we compose the rows in bottom-up order instead of // top-down. Unlike the drawCopyOver function, we don't have to check // the x coordinates because the built-in copy function can handle // overlapping slices. += ( - 1) * .Stride += ( - 1) * .Stride = -.Stride = -.Stride } for ; > 0; -- { copy(.Pix[:+], .Pix[:+]) += += } } func drawNRGBAOver( *image.RGBA, image.Rectangle, *image.NRGBA, image.Point) { := (.Min.X - .Rect.Min.X) * 4 := (.Max.X - .Rect.Min.X) * 4 := (.X - .Rect.Min.X) * 4 := .Max.Y - .Rect.Min.Y := .Min.Y - .Rect.Min.Y := .Y - .Rect.Min.Y for ; != ; , = +1, +1 { := .Pix[*.Stride:] := .Pix[*.Stride:] for , := , ; < ; , = +4, +4 { // Convert from non-premultiplied color to pre-multiplied color. := [ : +4 : +4] // Small cap improves performance, see https://golang.org/issue/27857 := uint32([3]) * 0x101 := uint32([0]) * / 0xff := uint32([1]) * / 0xff := uint32([2]) * / 0xff := [ : +4 : +4] // Small cap improves performance, see https://golang.org/issue/27857 := uint32([0]) := uint32([1]) := uint32([2]) := uint32([3]) // The 0x101 is here for the same reason as in drawRGBA. := (m - ) * 0x101 [0] = uint8((*/m + ) >> 8) [1] = uint8((*/m + ) >> 8) [2] = uint8((*/m + ) >> 8) [3] = uint8((*/m + ) >> 8) } } } func drawNRGBASrc( *image.RGBA, image.Rectangle, *image.NRGBA, image.Point) { := (.Min.X - .Rect.Min.X) * 4 := (.Max.X - .Rect.Min.X) * 4 := (.X - .Rect.Min.X) * 4 := .Max.Y - .Rect.Min.Y := .Min.Y - .Rect.Min.Y := .Y - .Rect.Min.Y for ; != ; , = +1, +1 { := .Pix[*.Stride:] := .Pix[*.Stride:] for , := , ; < ; , = +4, +4 { // Convert from non-premultiplied color to pre-multiplied color. := [ : +4 : +4] // Small cap improves performance, see https://golang.org/issue/27857 := uint32([3]) * 0x101 := uint32([0]) * / 0xff := uint32([1]) * / 0xff := uint32([2]) * / 0xff := [ : +4 : +4] // Small cap improves performance, see https://golang.org/issue/27857 [0] = uint8( >> 8) [1] = uint8( >> 8) [2] = uint8( >> 8) [3] = uint8( >> 8) } } } func drawGray( *image.RGBA, image.Rectangle, *image.Gray, image.Point) { := (.Min.X - .Rect.Min.X) * 4 := (.Max.X - .Rect.Min.X) * 4 := (.X - .Rect.Min.X) * 1 := .Max.Y - .Rect.Min.Y := .Min.Y - .Rect.Min.Y := .Y - .Rect.Min.Y for ; != ; , = +1, +1 { := .Pix[*.Stride:] := .Pix[*.Stride:] for , := , ; < ; , = +4, +1 { := [] := [ : +4 : +4] // Small cap improves performance, see https://golang.org/issue/27857 [0] = [1] = [2] = [3] = 255 } } } func drawCMYK( *image.RGBA, image.Rectangle, *image.CMYK, image.Point) { := (.Min.X - .Rect.Min.X) * 4 := (.Max.X - .Rect.Min.X) * 4 := (.X - .Rect.Min.X) * 4 := .Max.Y - .Rect.Min.Y := .Min.Y - .Rect.Min.Y := .Y - .Rect.Min.Y for ; != ; , = +1, +1 { := .Pix[*.Stride:] := .Pix[*.Stride:] for , := , ; < ; , = +4, +4 { := [ : +4 : +4] // Small cap improves performance, see https://golang.org/issue/27857 := [ : +4 : +4] [0], [1], [2] = color.CMYKToRGB([0], [1], [2], [3]) [3] = 255 } } } func drawGlyphOver( *image.RGBA, image.Rectangle, *image.Uniform, *image.Alpha, image.Point) { := .PixOffset(.Min.X, .Min.Y) := + .Dx()*4 := .PixOffset(.X, .Y) , , , := .RGBA() for , := .Min.Y, .Y; != .Max.Y; , = +1, +1 { for , := , ; < ; , = +4, +1 { := uint32(.Pix[]) if == 0 { continue } |= << 8 // The 0x101 is here for the same reason as in drawRGBA. := (m - ( * / m)) * 0x101 := .Pix[ : +4 : +4] // Small cap improves performance, see https://golang.org/issue/27857 [0] = uint8((uint32([0])* + *) / m >> 8) [1] = uint8((uint32([1])* + *) / m >> 8) [2] = uint8((uint32([2])* + *) / m >> 8) [3] = uint8((uint32([3])* + *) / m >> 8) } += .Stride += .Stride += .Stride } } func drawRGBA( *image.RGBA, image.Rectangle, image.Image, image.Point, image.Image, image.Point, Op) { , , := .Min.X, .Max.X, 1 , , := .Min.Y, .Max.Y, 1 if image.Image() == && .Overlaps(.Add(.Sub(.Min))) { if .Y < .Min.Y || .Y == .Min.Y && .X < .Min.X { , , = -1, -1, -1 , , = -1, -1, -1 } } := .Y + - .Min.Y := .Y + - .Min.Y := .X + - .Min.X := .X + - .Min.X := + ( - ) := .PixOffset(, ) := * 4 for := ; != ; , , = +, +, + { for , , := , , ; != ; , , = +, +, + { := uint32(m) if != nil { _, _, _, = .At(, ).RGBA() } , , , := .At(, ).RGBA() := .Pix[ : +4 : +4] // Small cap improves performance, see https://golang.org/issue/27857 if == Over { := uint32([0]) := uint32([1]) := uint32([2]) := uint32([3]) // dr, dg, db and da are all 8-bit color at the moment, ranging in [0,255]. // We work in 16-bit color, and so would normally do: // dr |= dr << 8 // and similarly for dg, db and da, but instead we multiply a // (which is a 16-bit color, ranging in [0,65535]) by 0x101. // This yields the same result, but is fewer arithmetic operations. := (m - ( * / m)) * 0x101 [0] = uint8((* + *) / m >> 8) [1] = uint8((* + *) / m >> 8) [2] = uint8((* + *) / m >> 8) [3] = uint8((* + *) / m >> 8) } else { [0] = uint8( * / m >> 8) [1] = uint8( * / m >> 8) [2] = uint8( * / m >> 8) [3] = uint8( * / m >> 8) } } += * .Stride } } // clamp clamps i to the interval [0, 0xffff]. func clamp( int32) int32 { if < 0 { return 0 } if > 0xffff { return 0xffff } return } // sqDiff returns the squared-difference of x and y, shifted by 2 so that // adding four of those won't overflow a uint32. // // x and y are both assumed to be in the range [0, 0xffff]. func sqDiff(, int32) uint32 { // This is an optimized code relying on the overflow/wrap around // properties of unsigned integers operations guaranteed by the language // spec. See sqDiff from the image/color package for more details. := uint32( - ) return ( * ) >> 2 } func drawPaletted( Image, image.Rectangle, image.Image, image.Point, bool) { // TODO(nigeltao): handle the case where the dst and src overlap. // Does it even make sense to try and do Floyd-Steinberg whilst // walking the image backward (right-to-left bottom-to-top)? // If dst is an *image.Paletted, we have a fast path for dst.Set and // dst.At. The dst.Set equivalent is a batch version of the algorithm // used by color.Palette's Index method in image/color/color.go, plus // optional Floyd-Steinberg error diffusion. , , := [][4]int32(nil), []byte(nil), 0 if , := .(*image.Paletted); { = make([][4]int32, len(.Palette)) for , := range .Palette { , , , := .RGBA() [][0] = int32() [][1] = int32() [][2] = int32() [][3] = int32() } , = .Pix[.PixOffset(.Min.X, .Min.Y):], .Stride } // quantErrorCurr and quantErrorNext are the Floyd-Steinberg quantization // errors that have been propagated to the pixels in the current and next // rows. The +2 simplifies calculation near the edges. var , [][4]int32 if { = make([][4]int32, .Dx()+2) = make([][4]int32, .Dx()+2) } := func(, int) (, , , uint32) { return .At(, ).RGBA() } // Fast paths for special cases to avoid excessive use of the color.Color // interface which escapes to the heap but need to be discovered for // each pixel on r. See also https://golang.org/issues/15759. switch src0 := .(type) { case *image.RGBA: = func(, int) (, , , uint32) { return .RGBAAt(, ).RGBA() } case *image.NRGBA: = func(, int) (, , , uint32) { return .NRGBAAt(, ).RGBA() } case *image.YCbCr: = func(, int) (, , , uint32) { return .YCbCrAt(, ).RGBA() } } // Loop over each source pixel. := color.RGBA64{A: 0xffff} for := 0; != .Dy(); ++ { for := 0; != .Dx(); ++ { // er, eg and eb are the pixel's R,G,B values plus the // optional Floyd-Steinberg error. , , , := (.X+, .Y+) , , , := int32(), int32(), int32(), int32() if { = clamp( + [+1][0]/16) = clamp( + [+1][1]/16) = clamp( + [+1][2]/16) = clamp( + [+1][3]/16) } if != nil { // Find the closest palette color in Euclidean R,G,B,A space: // the one that minimizes sum-squared-difference. // TODO(nigeltao): consider smarter algorithms. , := 0, uint32(1<<32-1) for , := range { := sqDiff(, [0]) + sqDiff(, [1]) + sqDiff(, [2]) + sqDiff(, [3]) if < { , = , if == 0 { break } } } [*+] = byte() if ! { continue } -= [][0] -= [][1] -= [][2] -= [][3] } else { .R = uint16() .G = uint16() .B = uint16() .A = uint16() // The third argument is &out instead of out (and out is // declared outside of the inner loop) to avoid the implicit // conversion to color.Color here allocating memory in the // inner loop if sizeof(color.RGBA64) > sizeof(uintptr). .Set(.Min.X+, .Min.Y+, &) if ! { continue } , , , = .At(.Min.X+, .Min.Y+).RGBA() -= int32() -= int32() -= int32() -= int32() } // Propagate the Floyd-Steinberg quantization error. [+0][0] += * 3 [+0][1] += * 3 [+0][2] += * 3 [+0][3] += * 3 [+1][0] += * 5 [+1][1] += * 5 [+1][2] += * 5 [+1][3] += * 5 [+2][0] += * 1 [+2][1] += * 1 [+2][2] += * 1 [+2][3] += * 1 [+2][0] += * 7 [+2][1] += * 7 [+2][2] += * 7 [+2][3] += * 7 } // Recycle the quantization error buffers. if { , = , for := range { [] = [4]int32{} } } } }