diff options
Diffstat (limited to 'Godeps/_workspace/src/code.google.com/p/freetype-go')
10 files changed, 5793 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/geom.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/geom.go new file mode 100644 index 000000000..63c86e6ab --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/geom.go @@ -0,0 +1,280 @@ +// Copyright 2010 The Freetype-Go Authors. All rights reserved. +// Use of this source code is governed by your choice of either the +// FreeType License or the GNU General Public License version 2 (or +// any later version), both of which can be found in the LICENSE file. + +package raster + +import ( + "fmt" + "math" +) + +// A Fix32 is a 24.8 fixed point number. +type Fix32 int32 + +// A Fix64 is a 48.16 fixed point number. +type Fix64 int64 + +// String returns a human-readable representation of a 24.8 fixed point number. +// For example, the number one-and-a-quarter becomes "1:064". +func (x Fix32) String() string { + if x < 0 { + x = -x + return fmt.Sprintf("-%d:%03d", int32(x/256), int32(x%256)) + } + return fmt.Sprintf("%d:%03d", int32(x/256), int32(x%256)) +} + +// String returns a human-readable representation of a 48.16 fixed point number. +// For example, the number one-and-a-quarter becomes "1:16384". +func (x Fix64) String() string { + if x < 0 { + x = -x + return fmt.Sprintf("-%d:%05d", int64(x/65536), int64(x%65536)) + } + return fmt.Sprintf("%d:%05d", int64(x/65536), int64(x%65536)) +} + +// maxAbs returns the maximum of abs(a) and abs(b). +func maxAbs(a, b Fix32) Fix32 { + if a < 0 { + a = -a + } + if b < 0 { + b = -b + } + if a < b { + return b + } + return a +} + +// A Point represents a two-dimensional point or vector, in 24.8 fixed point +// format. +type Point struct { + X, Y Fix32 +} + +// String returns a human-readable representation of a Point. +func (p Point) String() string { + return "(" + p.X.String() + ", " + p.Y.String() + ")" +} + +// Add returns the vector p + q. +func (p Point) Add(q Point) Point { + return Point{p.X + q.X, p.Y + q.Y} +} + +// Sub returns the vector p - q. +func (p Point) Sub(q Point) Point { + return Point{p.X - q.X, p.Y - q.Y} +} + +// Mul returns the vector k * p. +func (p Point) Mul(k Fix32) Point { + return Point{p.X * k / 256, p.Y * k / 256} +} + +// Neg returns the vector -p, or equivalently p rotated by 180 degrees. +func (p Point) Neg() Point { + return Point{-p.X, -p.Y} +} + +// Dot returns the dot product p·q. +func (p Point) Dot(q Point) Fix64 { + px, py := int64(p.X), int64(p.Y) + qx, qy := int64(q.X), int64(q.Y) + return Fix64(px*qx + py*qy) +} + +// Len returns the length of the vector p. +func (p Point) Len() Fix32 { + // TODO(nigeltao): use fixed point math. + x := float64(p.X) + y := float64(p.Y) + return Fix32(math.Sqrt(x*x + y*y)) +} + +// Norm returns the vector p normalized to the given length, or the zero Point +// if p is degenerate. +func (p Point) Norm(length Fix32) Point { + d := p.Len() + if d == 0 { + return Point{} + } + s, t := int64(length), int64(d) + x := int64(p.X) * s / t + y := int64(p.Y) * s / t + return Point{Fix32(x), Fix32(y)} +} + +// Rot45CW returns the vector p rotated clockwise by 45 degrees. +// Note that the Y-axis grows downwards, so {1, 0}.Rot45CW is {1/√2, 1/√2}. +func (p Point) Rot45CW() Point { + // 181/256 is approximately 1/√2, or sin(π/4). + px, py := int64(p.X), int64(p.Y) + qx := (+px - py) * 181 / 256 + qy := (+px + py) * 181 / 256 + return Point{Fix32(qx), Fix32(qy)} +} + +// Rot90CW returns the vector p rotated clockwise by 90 degrees. +// Note that the Y-axis grows downwards, so {1, 0}.Rot90CW is {0, 1}. +func (p Point) Rot90CW() Point { + return Point{-p.Y, p.X} +} + +// Rot135CW returns the vector p rotated clockwise by 135 degrees. +// Note that the Y-axis grows downwards, so {1, 0}.Rot135CW is {-1/√2, 1/√2}. +func (p Point) Rot135CW() Point { + // 181/256 is approximately 1/√2, or sin(π/4). + px, py := int64(p.X), int64(p.Y) + qx := (-px - py) * 181 / 256 + qy := (+px - py) * 181 / 256 + return Point{Fix32(qx), Fix32(qy)} +} + +// Rot45CCW returns the vector p rotated counter-clockwise by 45 degrees. +// Note that the Y-axis grows downwards, so {1, 0}.Rot45CCW is {1/√2, -1/√2}. +func (p Point) Rot45CCW() Point { + // 181/256 is approximately 1/√2, or sin(π/4). + px, py := int64(p.X), int64(p.Y) + qx := (+px + py) * 181 / 256 + qy := (-px + py) * 181 / 256 + return Point{Fix32(qx), Fix32(qy)} +} + +// Rot90CCW returns the vector p rotated counter-clockwise by 90 degrees. +// Note that the Y-axis grows downwards, so {1, 0}.Rot90CCW is {0, -1}. +func (p Point) Rot90CCW() Point { + return Point{p.Y, -p.X} +} + +// Rot135CCW returns the vector p rotated counter-clockwise by 135 degrees. +// Note that the Y-axis grows downwards, so {1, 0}.Rot135CCW is {-1/√2, -1/√2}. +func (p Point) Rot135CCW() Point { + // 181/256 is approximately 1/√2, or sin(π/4). + px, py := int64(p.X), int64(p.Y) + qx := (-px + py) * 181 / 256 + qy := (-px - py) * 181 / 256 + return Point{Fix32(qx), Fix32(qy)} +} + +// An Adder accumulates points on a curve. +type Adder interface { + // Start starts a new curve at the given point. + Start(a Point) + // Add1 adds a linear segment to the current curve. + Add1(b Point) + // Add2 adds a quadratic segment to the current curve. + Add2(b, c Point) + // Add3 adds a cubic segment to the current curve. + Add3(b, c, d Point) +} + +// A Path is a sequence of curves, and a curve is a start point followed by a +// sequence of linear, quadratic or cubic segments. +type Path []Fix32 + +// String returns a human-readable representation of a Path. +func (p Path) String() string { + s := "" + for i := 0; i < len(p); { + if i != 0 { + s += " " + } + switch p[i] { + case 0: + s += "S0" + fmt.Sprint([]Fix32(p[i+1:i+3])) + i += 4 + case 1: + s += "A1" + fmt.Sprint([]Fix32(p[i+1:i+3])) + i += 4 + case 2: + s += "A2" + fmt.Sprint([]Fix32(p[i+1:i+5])) + i += 6 + case 3: + s += "A3" + fmt.Sprint([]Fix32(p[i+1:i+7])) + i += 8 + default: + panic("freetype/raster: bad path") + } + } + return s +} + +// Clear cancels any previous calls to p.Start or p.AddXxx. +func (p *Path) Clear() { + *p = (*p)[:0] +} + +// Start starts a new curve at the given point. +func (p *Path) Start(a Point) { + *p = append(*p, 0, a.X, a.Y, 0) +} + +// Add1 adds a linear segment to the current curve. +func (p *Path) Add1(b Point) { + *p = append(*p, 1, b.X, b.Y, 1) +} + +// Add2 adds a quadratic segment to the current curve. +func (p *Path) Add2(b, c Point) { + *p = append(*p, 2, b.X, b.Y, c.X, c.Y, 2) +} + +// Add3 adds a cubic segment to the current curve. +func (p *Path) Add3(b, c, d Point) { + *p = append(*p, 3, b.X, b.Y, c.X, c.Y, d.X, d.Y, 3) +} + +// AddPath adds the Path q to p. +func (p *Path) AddPath(q Path) { + *p = append(*p, q...) +} + +// AddStroke adds a stroked Path. +func (p *Path) AddStroke(q Path, width Fix32, cr Capper, jr Joiner) { + Stroke(p, q, width, cr, jr) +} + +// firstPoint returns the first point in a non-empty Path. +func (p Path) firstPoint() Point { + return Point{p[1], p[2]} +} + +// lastPoint returns the last point in a non-empty Path. +func (p Path) lastPoint() Point { + return Point{p[len(p)-3], p[len(p)-2]} +} + +// addPathReversed adds q reversed to p. +// For example, if q consists of a linear segment from A to B followed by a +// quadratic segment from B to C to D, then the values of q looks like: +// index: 01234567890123 +// value: 0AA01BB12CCDD2 +// So, when adding q backwards to p, we want to Add2(C, B) followed by Add1(A). +func addPathReversed(p Adder, q Path) { + if len(q) == 0 { + return + } + i := len(q) - 1 + for { + switch q[i] { + case 0: + return + case 1: + i -= 4 + p.Add1(Point{q[i-2], q[i-1]}) + case 2: + i -= 6 + p.Add2(Point{q[i+2], q[i+3]}, Point{q[i-2], q[i-1]}) + case 3: + i -= 8 + p.Add3(Point{q[i+4], q[i+5]}, Point{q[i+2], q[i+3]}, Point{q[i-2], q[i-1]}) + default: + panic("freetype/raster: bad path") + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/paint.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/paint.go new file mode 100644 index 000000000..13cccc192 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/paint.go @@ -0,0 +1,292 @@ +// Copyright 2010 The Freetype-Go Authors. All rights reserved. +// Use of this source code is governed by your choice of either the +// FreeType License or the GNU General Public License version 2 (or +// any later version), both of which can be found in the LICENSE file. + +package raster + +import ( + "image" + "image/color" + "image/draw" + "math" +) + +// A Span is a horizontal segment of pixels with constant alpha. X0 is an +// inclusive bound and X1 is exclusive, the same as for slices. A fully +// opaque Span has A == 1<<32 - 1. +type Span struct { + Y, X0, X1 int + A uint32 +} + +// A Painter knows how to paint a batch of Spans. Rasterization may involve +// Painting multiple batches, and done will be true for the final batch. +// The Spans' Y values are monotonically increasing during a rasterization. +// Paint may use all of ss as scratch space during the call. +type Painter interface { + Paint(ss []Span, done bool) +} + +// The PainterFunc type adapts an ordinary function to the Painter interface. +type PainterFunc func(ss []Span, done bool) + +// Paint just delegates the call to f. +func (f PainterFunc) Paint(ss []Span, done bool) { f(ss, done) } + +// An AlphaOverPainter is a Painter that paints Spans onto an image.Alpha +// using the Over Porter-Duff composition operator. +type AlphaOverPainter struct { + Image *image.Alpha +} + +// Paint satisfies the Painter interface by painting ss onto an image.Alpha. +func (r AlphaOverPainter) Paint(ss []Span, done bool) { + b := r.Image.Bounds() + for _, s := range ss { + if s.Y < b.Min.Y { + continue + } + if s.Y >= b.Max.Y { + return + } + if s.X0 < b.Min.X { + s.X0 = b.Min.X + } + if s.X1 > b.Max.X { + s.X1 = b.Max.X + } + if s.X0 >= s.X1 { + continue + } + base := (s.Y-r.Image.Rect.Min.Y)*r.Image.Stride - r.Image.Rect.Min.X + p := r.Image.Pix[base+s.X0 : base+s.X1] + a := int(s.A >> 24) + for i, c := range p { + v := int(c) + p[i] = uint8((v*255 + (255-v)*a) / 255) + } + } +} + +// NewAlphaOverPainter creates a new AlphaOverPainter for the given image. +func NewAlphaOverPainter(m *image.Alpha) AlphaOverPainter { + return AlphaOverPainter{m} +} + +// An AlphaSrcPainter is a Painter that paints Spans onto an image.Alpha +// using the Src Porter-Duff composition operator. +type AlphaSrcPainter struct { + Image *image.Alpha +} + +// Paint satisfies the Painter interface by painting ss onto an image.Alpha. +func (r AlphaSrcPainter) Paint(ss []Span, done bool) { + b := r.Image.Bounds() + for _, s := range ss { + if s.Y < b.Min.Y { + continue + } + if s.Y >= b.Max.Y { + return + } + if s.X0 < b.Min.X { + s.X0 = b.Min.X + } + if s.X1 > b.Max.X { + s.X1 = b.Max.X + } + if s.X0 >= s.X1 { + continue + } + base := (s.Y-r.Image.Rect.Min.Y)*r.Image.Stride - r.Image.Rect.Min.X + p := r.Image.Pix[base+s.X0 : base+s.X1] + color := uint8(s.A >> 24) + for i := range p { + p[i] = color + } + } +} + +// NewAlphaSrcPainter creates a new AlphaSrcPainter for the given image. +func NewAlphaSrcPainter(m *image.Alpha) AlphaSrcPainter { + return AlphaSrcPainter{m} +} + +type RGBAPainter struct { + // The image to compose onto. + Image *image.RGBA + // The Porter-Duff composition operator. + Op draw.Op + // The 16-bit color to paint the spans. + cr, cg, cb, ca uint32 +} + +// Paint satisfies the Painter interface by painting ss onto an image.RGBA. +func (r *RGBAPainter) Paint(ss []Span, done bool) { + b := r.Image.Bounds() + for _, s := range ss { + if s.Y < b.Min.Y { + continue + } + if s.Y >= b.Max.Y { + return + } + if s.X0 < b.Min.X { + s.X0 = b.Min.X + } + if s.X1 > b.Max.X { + s.X1 = b.Max.X + } + if s.X0 >= s.X1 { + continue + } + // This code is similar to drawGlyphOver in $GOROOT/src/pkg/image/draw/draw.go. + ma := s.A >> 16 + const m = 1<<16 - 1 + i0 := (s.Y-r.Image.Rect.Min.Y)*r.Image.Stride + (s.X0-r.Image.Rect.Min.X)*4 + i1 := i0 + (s.X1-s.X0)*4 + if r.Op == draw.Over { + for i := i0; i < i1; i += 4 { + dr := uint32(r.Image.Pix[i+0]) + dg := uint32(r.Image.Pix[i+1]) + db := uint32(r.Image.Pix[i+2]) + da := uint32(r.Image.Pix[i+3]) + a := (m - (r.ca * ma / m)) * 0x101 + r.Image.Pix[i+0] = uint8((dr*a + r.cr*ma) / m >> 8) + r.Image.Pix[i+1] = uint8((dg*a + r.cg*ma) / m >> 8) + r.Image.Pix[i+2] = uint8((db*a + r.cb*ma) / m >> 8) + r.Image.Pix[i+3] = uint8((da*a + r.ca*ma) / m >> 8) + } + } else { + for i := i0; i < i1; i += 4 { + r.Image.Pix[i+0] = uint8(r.cr * ma / m >> 8) + r.Image.Pix[i+1] = uint8(r.cg * ma / m >> 8) + r.Image.Pix[i+2] = uint8(r.cb * ma / m >> 8) + r.Image.Pix[i+3] = uint8(r.ca * ma / m >> 8) + } + } + } +} + +// SetColor sets the color to paint the spans. +func (r *RGBAPainter) SetColor(c color.Color) { + r.cr, r.cg, r.cb, r.ca = c.RGBA() +} + +// NewRGBAPainter creates a new RGBAPainter for the given image. +func NewRGBAPainter(m *image.RGBA) *RGBAPainter { + return &RGBAPainter{Image: m} +} + +// A MonochromePainter wraps another Painter, quantizing each Span's alpha to +// be either fully opaque or fully transparent. +type MonochromePainter struct { + Painter Painter + y, x0, x1 int +} + +// Paint delegates to the wrapped Painter after quantizing each Span's alpha +// value and merging adjacent fully opaque Spans. +func (m *MonochromePainter) Paint(ss []Span, done bool) { + // We compact the ss slice, discarding any Spans whose alpha quantizes to zero. + j := 0 + for _, s := range ss { + if s.A >= 1<<31 { + if m.y == s.Y && m.x1 == s.X0 { + m.x1 = s.X1 + } else { + ss[j] = Span{m.y, m.x0, m.x1, 1<<32 - 1} + j++ + m.y, m.x0, m.x1 = s.Y, s.X0, s.X1 + } + } + } + if done { + // Flush the accumulated Span. + finalSpan := Span{m.y, m.x0, m.x1, 1<<32 - 1} + if j < len(ss) { + ss[j] = finalSpan + j++ + m.Painter.Paint(ss[:j], true) + } else if j == len(ss) { + m.Painter.Paint(ss, false) + if cap(ss) > 0 { + ss = ss[:1] + } else { + ss = make([]Span, 1) + } + ss[0] = finalSpan + m.Painter.Paint(ss, true) + } else { + panic("unreachable") + } + // Reset the accumulator, so that this Painter can be re-used. + m.y, m.x0, m.x1 = 0, 0, 0 + } else { + m.Painter.Paint(ss[:j], false) + } +} + +// NewMonochromePainter creates a new MonochromePainter that wraps the given +// Painter. +func NewMonochromePainter(p Painter) *MonochromePainter { + return &MonochromePainter{Painter: p} +} + +// A GammaCorrectionPainter wraps another Painter, performing gamma-correction +// on each Span's alpha value. +type GammaCorrectionPainter struct { + // The wrapped Painter. + Painter Painter + // Precomputed alpha values for linear interpolation, with fully opaque == 1<<16-1. + a [256]uint16 + // Whether gamma correction is a no-op. + gammaIsOne bool +} + +// Paint delegates to the wrapped Painter after performing gamma-correction +// on each Span. +func (g *GammaCorrectionPainter) Paint(ss []Span, done bool) { + if !g.gammaIsOne { + const ( + M = 0x1010101 // 255*M == 1<<32-1 + N = 0x8080 // N = M>>9, and N < 1<<16-1 + ) + for i, s := range ss { + if s.A == 0 || s.A == 1<<32-1 { + continue + } + p, q := s.A/M, (s.A%M)>>9 + // The resultant alpha is a linear interpolation of g.a[p] and g.a[p+1]. + a := uint32(g.a[p])*(N-q) + uint32(g.a[p+1])*q + a = (a + N/2) / N + // Convert the alpha from 16-bit (which is g.a's range) to 32-bit. + a |= a << 16 + ss[i].A = a + } + } + g.Painter.Paint(ss, done) +} + +// SetGamma sets the gamma value. +func (g *GammaCorrectionPainter) SetGamma(gamma float64) { + if gamma == 1.0 { + g.gammaIsOne = true + return + } + g.gammaIsOne = false + for i := 0; i < 256; i++ { + a := float64(i) / 0xff + a = math.Pow(a, gamma) + g.a[i] = uint16(0xffff * a) + } +} + +// NewGammaCorrectionPainter creates a new GammaCorrectionPainter that wraps +// the given Painter. +func NewGammaCorrectionPainter(p Painter, gamma float64) *GammaCorrectionPainter { + g := &GammaCorrectionPainter{Painter: p} + g.SetGamma(gamma) + return g +} diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/raster.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/raster.go new file mode 100644 index 000000000..45af7eaa2 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/raster.go @@ -0,0 +1,579 @@ +// Copyright 2010 The Freetype-Go Authors. All rights reserved. +// Use of this source code is governed by your choice of either the +// FreeType License or the GNU General Public License version 2 (or +// any later version), both of which can be found in the LICENSE file. + +// The raster package provides an anti-aliasing 2-D rasterizer. +// +// It is part of the larger Freetype-Go suite of font-related packages, +// but the raster package is not specific to font rasterization, and can +// be used standalone without any other Freetype-Go package. +// +// Rasterization is done by the same area/coverage accumulation algorithm +// as the Freetype "smooth" module, and the Anti-Grain Geometry library. +// A description of the area/coverage algorithm is at +// http://projects.tuxee.net/cl-vectors/section-the-cl-aa-algorithm +package raster + +import ( + "strconv" +) + +// A cell is part of a linked list (for a given yi co-ordinate) of accumulated +// area/coverage for the pixel at (xi, yi). +type cell struct { + xi int + area, cover int + next int +} + +type Rasterizer struct { + // If false, the default behavior is to use the even-odd winding fill + // rule during Rasterize. + UseNonZeroWinding bool + // An offset (in pixels) to the painted spans. + Dx, Dy int + + // The width of the Rasterizer. The height is implicit in len(cellIndex). + width int + // splitScaleN is the scaling factor used to determine how many times + // to decompose a quadratic or cubic segment into a linear approximation. + splitScale2, splitScale3 int + + // The current pen position. + a Point + // The current cell and its area/coverage being accumulated. + xi, yi int + area, cover int + + // Saved cells. + cell []cell + // Linked list of cells, one per row. + cellIndex []int + // Buffers. + cellBuf [256]cell + cellIndexBuf [64]int + spanBuf [64]Span +} + +// findCell returns the index in r.cell for the cell corresponding to +// (r.xi, r.yi). The cell is created if necessary. +func (r *Rasterizer) findCell() int { + if r.yi < 0 || r.yi >= len(r.cellIndex) { + return -1 + } + xi := r.xi + if xi < 0 { + xi = -1 + } else if xi > r.width { + xi = r.width + } + i, prev := r.cellIndex[r.yi], -1 + for i != -1 && r.cell[i].xi <= xi { + if r.cell[i].xi == xi { + return i + } + i, prev = r.cell[i].next, i + } + c := len(r.cell) + if c == cap(r.cell) { + buf := make([]cell, c, 4*c) + copy(buf, r.cell) + r.cell = buf[0 : c+1] + } else { + r.cell = r.cell[0 : c+1] + } + r.cell[c] = cell{xi, 0, 0, i} + if prev == -1 { + r.cellIndex[r.yi] = c + } else { + r.cell[prev].next = c + } + return c +} + +// saveCell saves any accumulated r.area/r.cover for (r.xi, r.yi). +func (r *Rasterizer) saveCell() { + if r.area != 0 || r.cover != 0 { + i := r.findCell() + if i != -1 { + r.cell[i].area += r.area + r.cell[i].cover += r.cover + } + r.area = 0 + r.cover = 0 + } +} + +// setCell sets the (xi, yi) cell that r is accumulating area/coverage for. +func (r *Rasterizer) setCell(xi, yi int) { + if r.xi != xi || r.yi != yi { + r.saveCell() + r.xi, r.yi = xi, yi + } +} + +// scan accumulates area/coverage for the yi'th scanline, going from +// x0 to x1 in the horizontal direction (in 24.8 fixed point co-ordinates) +// and from y0f to y1f fractional vertical units within that scanline. +func (r *Rasterizer) scan(yi int, x0, y0f, x1, y1f Fix32) { + // Break the 24.8 fixed point X co-ordinates into integral and fractional parts. + x0i := int(x0) / 256 + x0f := x0 - Fix32(256*x0i) + x1i := int(x1) / 256 + x1f := x1 - Fix32(256*x1i) + + // A perfectly horizontal scan. + if y0f == y1f { + r.setCell(x1i, yi) + return + } + dx, dy := x1-x0, y1f-y0f + // A single cell scan. + if x0i == x1i { + r.area += int((x0f + x1f) * dy) + r.cover += int(dy) + return + } + // There are at least two cells. Apart from the first and last cells, + // all intermediate cells go through the full width of the cell, + // or 256 units in 24.8 fixed point format. + var ( + p, q, edge0, edge1 Fix32 + xiDelta int + ) + if dx > 0 { + p, q = (256-x0f)*dy, dx + edge0, edge1, xiDelta = 0, 256, 1 + } else { + p, q = x0f*dy, -dx + edge0, edge1, xiDelta = 256, 0, -1 + } + yDelta, yRem := p/q, p%q + if yRem < 0 { + yDelta -= 1 + yRem += q + } + // Do the first cell. + xi, y := x0i, y0f + r.area += int((x0f + edge1) * yDelta) + r.cover += int(yDelta) + xi, y = xi+xiDelta, y+yDelta + r.setCell(xi, yi) + if xi != x1i { + // Do all the intermediate cells. + p = 256 * (y1f - y + yDelta) + fullDelta, fullRem := p/q, p%q + if fullRem < 0 { + fullDelta -= 1 + fullRem += q + } + yRem -= q + for xi != x1i { + yDelta = fullDelta + yRem += fullRem + if yRem >= 0 { + yDelta += 1 + yRem -= q + } + r.area += int(256 * yDelta) + r.cover += int(yDelta) + xi, y = xi+xiDelta, y+yDelta + r.setCell(xi, yi) + } + } + // Do the last cell. + yDelta = y1f - y + r.area += int((edge0 + x1f) * yDelta) + r.cover += int(yDelta) +} + +// Start starts a new curve at the given point. +func (r *Rasterizer) Start(a Point) { + r.setCell(int(a.X/256), int(a.Y/256)) + r.a = a +} + +// Add1 adds a linear segment to the current curve. +func (r *Rasterizer) Add1(b Point) { + x0, y0 := r.a.X, r.a.Y + x1, y1 := b.X, b.Y + dx, dy := x1-x0, y1-y0 + // Break the 24.8 fixed point Y co-ordinates into integral and fractional parts. + y0i := int(y0) / 256 + y0f := y0 - Fix32(256*y0i) + y1i := int(y1) / 256 + y1f := y1 - Fix32(256*y1i) + + if y0i == y1i { + // There is only one scanline. + r.scan(y0i, x0, y0f, x1, y1f) + + } else if dx == 0 { + // This is a vertical line segment. We avoid calling r.scan and instead + // manipulate r.area and r.cover directly. + var ( + edge0, edge1 Fix32 + yiDelta int + ) + if dy > 0 { + edge0, edge1, yiDelta = 0, 256, 1 + } else { + edge0, edge1, yiDelta = 256, 0, -1 + } + x0i, yi := int(x0)/256, y0i + x0fTimes2 := (int(x0) - (256 * x0i)) * 2 + // Do the first pixel. + dcover := int(edge1 - y0f) + darea := int(x0fTimes2 * dcover) + r.area += darea + r.cover += dcover + yi += yiDelta + r.setCell(x0i, yi) + // Do all the intermediate pixels. + dcover = int(edge1 - edge0) + darea = int(x0fTimes2 * dcover) + for yi != y1i { + r.area += darea + r.cover += dcover + yi += yiDelta + r.setCell(x0i, yi) + } + // Do the last pixel. + dcover = int(y1f - edge0) + darea = int(x0fTimes2 * dcover) + r.area += darea + r.cover += dcover + + } else { + // There are at least two scanlines. Apart from the first and last scanlines, + // all intermediate scanlines go through the full height of the row, or 256 + // units in 24.8 fixed point format. + var ( + p, q, edge0, edge1 Fix32 + yiDelta int + ) + if dy > 0 { + p, q = (256-y0f)*dx, dy + edge0, edge1, yiDelta = 0, 256, 1 + } else { + p, q = y0f*dx, -dy + edge0, edge1, yiDelta = 256, 0, -1 + } + xDelta, xRem := p/q, p%q + if xRem < 0 { + xDelta -= 1 + xRem += q + } + // Do the first scanline. + x, yi := x0, y0i + r.scan(yi, x, y0f, x+xDelta, edge1) + x, yi = x+xDelta, yi+yiDelta + r.setCell(int(x)/256, yi) + if yi != y1i { + // Do all the intermediate scanlines. + p = 256 * dx + fullDelta, fullRem := p/q, p%q + if fullRem < 0 { + fullDelta -= 1 + fullRem += q + } + xRem -= q + for yi != y1i { + xDelta = fullDelta + xRem += fullRem + if xRem >= 0 { + xDelta += 1 + xRem -= q + } + r.scan(yi, x, edge0, x+xDelta, edge1) + x, yi = x+xDelta, yi+yiDelta + r.setCell(int(x)/256, yi) + } + } + // Do the last scanline. + r.scan(yi, x, edge0, x1, y1f) + } + // The next lineTo starts from b. + r.a = b +} + +// Add2 adds a quadratic segment to the current curve. +func (r *Rasterizer) Add2(b, c Point) { + // Calculate nSplit (the number of recursive decompositions) based on how `curvy' it is. + // Specifically, how much the middle point b deviates from (a+c)/2. + dev := maxAbs(r.a.X-2*b.X+c.X, r.a.Y-2*b.Y+c.Y) / Fix32(r.splitScale2) + nsplit := 0 + for dev > 0 { + dev /= 4 + nsplit++ + } + // dev is 32-bit, and nsplit++ every time we shift off 2 bits, so maxNsplit is 16. + const maxNsplit = 16 + if nsplit > maxNsplit { + panic("freetype/raster: Add2 nsplit too large: " + strconv.Itoa(nsplit)) + } + // Recursively decompose the curve nSplit levels deep. + var ( + pStack [2*maxNsplit + 3]Point + sStack [maxNsplit + 1]int + i int + ) + sStack[0] = nsplit + pStack[0] = c + pStack[1] = b + pStack[2] = r.a + for i >= 0 { + s := sStack[i] + p := pStack[2*i:] + if s > 0 { + // Split the quadratic curve p[:3] into an equivalent set of two shorter curves: + // p[:3] and p[2:5]. The new p[4] is the old p[2], and p[0] is unchanged. + mx := p[1].X + p[4].X = p[2].X + p[3].X = (p[4].X + mx) / 2 + p[1].X = (p[0].X + mx) / 2 + p[2].X = (p[1].X + p[3].X) / 2 + my := p[1].Y + p[4].Y = p[2].Y + p[3].Y = (p[4].Y + my) / 2 + p[1].Y = (p[0].Y + my) / 2 + p[2].Y = (p[1].Y + p[3].Y) / 2 + // The two shorter curves have one less split to do. + sStack[i] = s - 1 + sStack[i+1] = s - 1 + i++ + } else { + // Replace the level-0 quadratic with a two-linear-piece approximation. + midx := (p[0].X + 2*p[1].X + p[2].X) / 4 + midy := (p[0].Y + 2*p[1].Y + p[2].Y) / 4 + r.Add1(Point{midx, midy}) + r.Add1(p[0]) + i-- + } + } +} + +// Add3 adds a cubic segment to the current curve. +func (r *Rasterizer) Add3(b, c, d Point) { + // Calculate nSplit (the number of recursive decompositions) based on how `curvy' it is. + dev2 := maxAbs(r.a.X-3*(b.X+c.X)+d.X, r.a.Y-3*(b.Y+c.Y)+d.Y) / Fix32(r.splitScale2) + dev3 := maxAbs(r.a.X-2*b.X+d.X, r.a.Y-2*b.Y+d.Y) / Fix32(r.splitScale3) + nsplit := 0 + for dev2 > 0 || dev3 > 0 { + dev2 /= 8 + dev3 /= 4 + nsplit++ + } + // devN is 32-bit, and nsplit++ every time we shift off 2 bits, so maxNsplit is 16. + const maxNsplit = 16 + if nsplit > maxNsplit { + panic("freetype/raster: Add3 nsplit too large: " + strconv.Itoa(nsplit)) + } + // Recursively decompose the curve nSplit levels deep. + var ( + pStack [3*maxNsplit + 4]Point + sStack [maxNsplit + 1]int + i int + ) + sStack[0] = nsplit + pStack[0] = d + pStack[1] = c + pStack[2] = b + pStack[3] = r.a + for i >= 0 { + s := sStack[i] + p := pStack[3*i:] + if s > 0 { + // Split the cubic curve p[:4] into an equivalent set of two shorter curves: + // p[:4] and p[3:7]. The new p[6] is the old p[3], and p[0] is unchanged. + m01x := (p[0].X + p[1].X) / 2 + m12x := (p[1].X + p[2].X) / 2 + m23x := (p[2].X + p[3].X) / 2 + p[6].X = p[3].X + p[5].X = m23x + p[1].X = m01x + p[2].X = (m01x + m12x) / 2 + p[4].X = (m12x + m23x) / 2 + p[3].X = (p[2].X + p[4].X) / 2 + m01y := (p[0].Y + p[1].Y) / 2 + m12y := (p[1].Y + p[2].Y) / 2 + m23y := (p[2].Y + p[3].Y) / 2 + p[6].Y = p[3].Y + p[5].Y = m23y + p[1].Y = m01y + p[2].Y = (m01y + m12y) / 2 + p[4].Y = (m12y + m23y) / 2 + p[3].Y = (p[2].Y + p[4].Y) / 2 + // The two shorter curves have one less split to do. + sStack[i] = s - 1 + sStack[i+1] = s - 1 + i++ + } else { + // Replace the level-0 cubic with a two-linear-piece approximation. + midx := (p[0].X + 3*(p[1].X+p[2].X) + p[3].X) / 8 + midy := (p[0].Y + 3*(p[1].Y+p[2].Y) + p[3].Y) / 8 + r.Add1(Point{midx, midy}) + r.Add1(p[0]) + i-- + } + } +} + +// AddPath adds the given Path. +func (r *Rasterizer) AddPath(p Path) { + for i := 0; i < len(p); { + switch p[i] { + case 0: + r.Start(Point{p[i+1], p[i+2]}) + i += 4 + case 1: + r.Add1(Point{p[i+1], p[i+2]}) + i += 4 + case 2: + r.Add2(Point{p[i+1], p[i+2]}, Point{p[i+3], p[i+4]}) + i += 6 + case 3: + r.Add3(Point{p[i+1], p[i+2]}, Point{p[i+3], p[i+4]}, Point{p[i+5], p[i+6]}) + i += 8 + default: + panic("freetype/raster: bad path") + } + } +} + +// AddStroke adds a stroked Path. +func (r *Rasterizer) AddStroke(q Path, width Fix32, cr Capper, jr Joiner) { + Stroke(r, q, width, cr, jr) +} + +// Converts an area value to a uint32 alpha value. A completely filled pixel +// corresponds to an area of 256*256*2, and an alpha of 1<<32-1. The +// conversion of area values greater than this depends on the winding rule: +// even-odd or non-zero. +func (r *Rasterizer) areaToAlpha(area int) uint32 { + // The C Freetype implementation (version 2.3.12) does "alpha := area>>1" without + // the +1. Round-to-nearest gives a more symmetric result than round-down. + // The C implementation also returns 8-bit alpha, not 32-bit alpha. + a := (area + 1) >> 1 + if a < 0 { + a = -a + } + alpha := uint32(a) + if r.UseNonZeroWinding { + if alpha > 0xffff { + alpha = 0xffff + } + } else { + alpha &= 0x1ffff + if alpha > 0x10000 { + alpha = 0x20000 - alpha + } else if alpha == 0x10000 { + alpha = 0x0ffff + } + } + alpha |= alpha << 16 + return alpha +} + +// Rasterize converts r's accumulated curves into Spans for p. The Spans +// passed to p are non-overlapping, and sorted by Y and then X. They all +// have non-zero width (and 0 <= X0 < X1 <= r.width) and non-zero A, except +// for the final Span, which has Y, X0, X1 and A all equal to zero. +func (r *Rasterizer) Rasterize(p Painter) { + r.saveCell() + s := 0 + for yi := 0; yi < len(r.cellIndex); yi++ { + xi, cover := 0, 0 + for c := r.cellIndex[yi]; c != -1; c = r.cell[c].next { + if cover != 0 && r.cell[c].xi > xi { + alpha := r.areaToAlpha(cover * 256 * 2) + if alpha != 0 { + xi0, xi1 := xi, r.cell[c].xi + if xi0 < 0 { + xi0 = 0 + } + if xi1 >= r.width { + xi1 = r.width + } + if xi0 < xi1 { + r.spanBuf[s] = Span{yi + r.Dy, xi0 + r.Dx, xi1 + r.Dx, alpha} + s++ + } + } + } + cover += r.cell[c].cover + alpha := r.areaToAlpha(cover*256*2 - r.cell[c].area) + xi = r.cell[c].xi + 1 + if alpha != 0 { + xi0, xi1 := r.cell[c].xi, xi + if xi0 < 0 { + xi0 = 0 + } + if xi1 >= r.width { + xi1 = r.width + } + if xi0 < xi1 { + r.spanBuf[s] = Span{yi + r.Dy, xi0 + r.Dx, xi1 + r.Dx, alpha} + s++ + } + } + if s > len(r.spanBuf)-2 { + p.Paint(r.spanBuf[:s], false) + s = 0 + } + } + } + p.Paint(r.spanBuf[:s], true) +} + +// Clear cancels any previous calls to r.Start or r.AddXxx. +func (r *Rasterizer) Clear() { + r.a = Point{} + r.xi = 0 + r.yi = 0 + r.area = 0 + r.cover = 0 + r.cell = r.cell[:0] + for i := 0; i < len(r.cellIndex); i++ { + r.cellIndex[i] = -1 + } +} + +// SetBounds sets the maximum width and height of the rasterized image and +// calls Clear. The width and height are in pixels, not Fix32 units. +func (r *Rasterizer) SetBounds(width, height int) { + if width < 0 { + width = 0 + } + if height < 0 { + height = 0 + } + // Use the same ssN heuristic as the C Freetype implementation. + // The C implementation uses the values 32, 16, but those are in + // 26.6 fixed point units, and we use 24.8 fixed point everywhere. + ss2, ss3 := 128, 64 + if width > 24 || height > 24 { + ss2, ss3 = 2*ss2, 2*ss3 + if width > 120 || height > 120 { + ss2, ss3 = 2*ss2, 2*ss3 + } + } + r.width = width + r.splitScale2 = ss2 + r.splitScale3 = ss3 + r.cell = r.cellBuf[:0] + if height > len(r.cellIndexBuf) { + r.cellIndex = make([]int, height) + } else { + r.cellIndex = r.cellIndexBuf[:height] + } + r.Clear() +} + +// NewRasterizer creates a new Rasterizer with the given bounds. +func NewRasterizer(width, height int) *Rasterizer { + r := new(Rasterizer) + r.SetBounds(width, height) + return r +} diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/stroke.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/stroke.go new file mode 100644 index 000000000..d49b1cee9 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/raster/stroke.go @@ -0,0 +1,466 @@ +// Copyright 2010 The Freetype-Go Authors. All rights reserved. +// Use of this source code is governed by your choice of either the +// FreeType License or the GNU General Public License version 2 (or +// any later version), both of which can be found in the LICENSE file. + +package raster + +// Two points are considered practically equal if the square of the distance +// between them is less than one quarter (i.e. 16384 / 65536 in Fix64). +const epsilon = 16384 + +// A Capper signifies how to begin or end a stroked path. +type Capper interface { + // Cap adds a cap to p given a pivot point and the normal vector of a + // terminal segment. The normal's length is half of the stroke width. + Cap(p Adder, halfWidth Fix32, pivot, n1 Point) +} + +// The CapperFunc type adapts an ordinary function to be a Capper. +type CapperFunc func(Adder, Fix32, Point, Point) + +func (f CapperFunc) Cap(p Adder, halfWidth Fix32, pivot, n1 Point) { + f(p, halfWidth, pivot, n1) +} + +// A Joiner signifies how to join interior nodes of a stroked path. +type Joiner interface { + // Join adds a join to the two sides of a stroked path given a pivot + // point and the normal vectors of the trailing and leading segments. + // Both normals have length equal to half of the stroke width. + Join(lhs, rhs Adder, halfWidth Fix32, pivot, n0, n1 Point) +} + +// The JoinerFunc type adapts an ordinary function to be a Joiner. +type JoinerFunc func(lhs, rhs Adder, halfWidth Fix32, pivot, n0, n1 Point) + +func (f JoinerFunc) Join(lhs, rhs Adder, halfWidth Fix32, pivot, n0, n1 Point) { + f(lhs, rhs, halfWidth, pivot, n0, n1) +} + +// RoundCapper adds round caps to a stroked path. +var RoundCapper Capper = CapperFunc(roundCapper) + +func roundCapper(p Adder, halfWidth Fix32, pivot, n1 Point) { + // The cubic Bézier approximation to a circle involves the magic number + // (√2 - 1) * 4/3, which is approximately 141/256. + const k = 141 + e := n1.Rot90CCW() + side := pivot.Add(e) + start, end := pivot.Sub(n1), pivot.Add(n1) + d, e := n1.Mul(k), e.Mul(k) + p.Add3(start.Add(e), side.Sub(d), side) + p.Add3(side.Add(d), end.Add(e), end) +} + +// ButtCapper adds butt caps to a stroked path. +var ButtCapper Capper = CapperFunc(buttCapper) + +func buttCapper(p Adder, halfWidth Fix32, pivot, n1 Point) { + p.Add1(pivot.Add(n1)) +} + +// SquareCapper adds square caps to a stroked path. +var SquareCapper Capper = CapperFunc(squareCapper) + +func squareCapper(p Adder, halfWidth Fix32, pivot, n1 Point) { + e := n1.Rot90CCW() + side := pivot.Add(e) + p.Add1(side.Sub(n1)) + p.Add1(side.Add(n1)) + p.Add1(pivot.Add(n1)) +} + +// RoundJoiner adds round joins to a stroked path. +var RoundJoiner Joiner = JoinerFunc(roundJoiner) + +func roundJoiner(lhs, rhs Adder, haflWidth Fix32, pivot, n0, n1 Point) { + dot := n0.Rot90CW().Dot(n1) + if dot >= 0 { + addArc(lhs, pivot, n0, n1) + rhs.Add1(pivot.Sub(n1)) + } else { + lhs.Add1(pivot.Add(n1)) + addArc(rhs, pivot, n0.Neg(), n1.Neg()) + } +} + +// BevelJoiner adds bevel joins to a stroked path. +var BevelJoiner Joiner = JoinerFunc(bevelJoiner) + +func bevelJoiner(lhs, rhs Adder, haflWidth Fix32, pivot, n0, n1 Point) { + lhs.Add1(pivot.Add(n1)) + rhs.Add1(pivot.Sub(n1)) +} + +// addArc adds a circular arc from pivot+n0 to pivot+n1 to p. The shorter of +// the two possible arcs is taken, i.e. the one spanning <= 180 degrees. +// The two vectors n0 and n1 must be of equal length. +func addArc(p Adder, pivot, n0, n1 Point) { + // r2 is the square of the length of n0. + r2 := n0.Dot(n0) + if r2 < epsilon { + // The arc radius is so small that we collapse to a straight line. + p.Add1(pivot.Add(n1)) + return + } + // We approximate the arc by 0, 1, 2 or 3 45-degree quadratic segments plus + // a final quadratic segment from s to n1. Each 45-degree segment has control + // points {1, 0}, {1, tan(π/8)} and {1/√2, 1/√2} suitably scaled, rotated and + // translated. tan(π/8) is approximately 106/256. + const tpo8 = 106 + var s Point + // We determine which octant the angle between n0 and n1 is in via three dot products. + // m0, m1 and m2 are n0 rotated clockwise by 45, 90 and 135 degrees. + m0 := n0.Rot45CW() + m1 := n0.Rot90CW() + m2 := m0.Rot90CW() + if m1.Dot(n1) >= 0 { + if n0.Dot(n1) >= 0 { + if m2.Dot(n1) <= 0 { + // n1 is between 0 and 45 degrees clockwise of n0. + s = n0 + } else { + // n1 is between 45 and 90 degrees clockwise of n0. + p.Add2(pivot.Add(n0).Add(m1.Mul(tpo8)), pivot.Add(m0)) + s = m0 + } + } else { + pm1, n0t := pivot.Add(m1), n0.Mul(tpo8) + p.Add2(pivot.Add(n0).Add(m1.Mul(tpo8)), pivot.Add(m0)) + p.Add2(pm1.Add(n0t), pm1) + if m0.Dot(n1) >= 0 { + // n1 is between 90 and 135 degrees clockwise of n0. + s = m1 + } else { + // n1 is between 135 and 180 degrees clockwise of n0. + p.Add2(pm1.Sub(n0t), pivot.Add(m2)) + s = m2 + } + } + } else { + if n0.Dot(n1) >= 0 { + if m0.Dot(n1) >= 0 { + // n1 is between 0 and 45 degrees counter-clockwise of n0. + s = n0 + } else { + // n1 is between 45 and 90 degrees counter-clockwise of n0. + p.Add2(pivot.Add(n0).Sub(m1.Mul(tpo8)), pivot.Sub(m2)) + s = m2.Neg() + } + } else { + pm1, n0t := pivot.Sub(m1), n0.Mul(tpo8) + p.Add2(pivot.Add(n0).Sub(m1.Mul(tpo8)), pivot.Sub(m2)) + p.Add2(pm1.Add(n0t), pm1) + if m2.Dot(n1) <= 0 { + // n1 is between 90 and 135 degrees counter-clockwise of n0. + s = m1.Neg() + } else { + // n1 is between 135 and 180 degrees counter-clockwise of n0. + p.Add2(pm1.Sub(n0t), pivot.Sub(m0)) + s = m0.Neg() + } + } + } + // The final quadratic segment has two endpoints s and n1 and the middle + // control point is a multiple of s.Add(n1), i.e. it is on the angle bisector + // of those two points. The multiple ranges between 128/256 and 150/256 as + // the angle between s and n1 ranges between 0 and 45 degrees. + // When the angle is 0 degrees (i.e. s and n1 are coincident) then s.Add(n1) + // is twice s and so the middle control point of the degenerate quadratic + // segment should be half s.Add(n1), and half = 128/256. + // When the angle is 45 degrees then 150/256 is the ratio of the lengths of + // the two vectors {1, tan(π/8)} and {1 + 1/√2, 1/√2}. + // d is the normalized dot product between s and n1. Since the angle ranges + // between 0 and 45 degrees then d ranges between 256/256 and 181/256. + d := 256 * s.Dot(n1) / r2 + multiple := Fix32(150 - 22*(d-181)/(256-181)) + p.Add2(pivot.Add(s.Add(n1).Mul(multiple)), pivot.Add(n1)) +} + +// midpoint returns the midpoint of two Points. +func midpoint(a, b Point) Point { + return Point{(a.X + b.X) / 2, (a.Y + b.Y) / 2} +} + +// angleGreaterThan45 returns whether the angle between two vectors is more +// than 45 degrees. +func angleGreaterThan45(v0, v1 Point) bool { + v := v0.Rot45CCW() + return v.Dot(v1) < 0 || v.Rot90CW().Dot(v1) < 0 +} + +// interpolate returns the point (1-t)*a + t*b. +func interpolate(a, b Point, t Fix64) Point { + s := 65536 - t + x := s*Fix64(a.X) + t*Fix64(b.X) + y := s*Fix64(a.Y) + t*Fix64(b.Y) + return Point{Fix32(x >> 16), Fix32(y >> 16)} +} + +// curviest2 returns the value of t for which the quadratic parametric curve +// (1-t)²*a + 2*t*(1-t).b + t²*c has maximum curvature. +// +// The curvature of the parametric curve f(t) = (x(t), y(t)) is +// |x′y″-y′x″| / (x′²+y′²)^(3/2). +// +// Let d = b-a and e = c-2*b+a, so that f′(t) = 2*d+2*e*t and f″(t) = 2*e. +// The curvature's numerator is (2*dx+2*ex*t)*(2*ey)-(2*dy+2*ey*t)*(2*ex), +// which simplifies to 4*dx*ey-4*dy*ex, which is constant with respect to t. +// +// Thus, curvature is extreme where the denominator is extreme, i.e. where +// (x′²+y′²) is extreme. The first order condition is that +// 2*x′*x″+2*y′*y″ = 0, or (dx+ex*t)*ex + (dy+ey*t)*ey = 0. +// Solving for t gives t = -(dx*ex+dy*ey) / (ex*ex+ey*ey). +func curviest2(a, b, c Point) Fix64 { + dx := int64(b.X - a.X) + dy := int64(b.Y - a.Y) + ex := int64(c.X - 2*b.X + a.X) + ey := int64(c.Y - 2*b.Y + a.Y) + if ex == 0 && ey == 0 { + return 32768 + } + return Fix64(-65536 * (dx*ex + dy*ey) / (ex*ex + ey*ey)) +} + +// A stroker holds state for stroking a path. +type stroker struct { + // p is the destination that records the stroked path. + p Adder + // u is the half-width of the stroke. + u Fix32 + // cr and jr specify how to end and connect path segments. + cr Capper + jr Joiner + // r is the reverse path. Stroking a path involves constructing two + // parallel paths 2*u apart. The first path is added immediately to p, + // the second path is accumulated in r and eventually added in reverse. + r Path + // a is the most recent segment point. anorm is the segment normal of + // length u at that point. + a, anorm Point +} + +// addNonCurvy2 adds a quadratic segment to the stroker, where the segment +// defined by (k.a, b, c) achieves maximum curvature at either k.a or c. +func (k *stroker) addNonCurvy2(b, c Point) { + // We repeatedly divide the segment at its middle until it is straight + // enough to approximate the stroke by just translating the control points. + // ds and ps are stacks of depths and points. t is the top of the stack. + const maxDepth = 5 + var ( + ds [maxDepth + 1]int + ps [2*maxDepth + 3]Point + t int + ) + // Initially the ps stack has one quadratic segment of depth zero. + ds[0] = 0 + ps[2] = k.a + ps[1] = b + ps[0] = c + anorm := k.anorm + var cnorm Point + + for { + depth := ds[t] + a := ps[2*t+2] + b := ps[2*t+1] + c := ps[2*t+0] + ab := b.Sub(a) + bc := c.Sub(b) + abIsSmall := ab.Dot(ab) < Fix64(1<<16) + bcIsSmall := bc.Dot(bc) < Fix64(1<<16) + if abIsSmall && bcIsSmall { + // Approximate the segment by a circular arc. + cnorm = bc.Norm(k.u).Rot90CCW() + mac := midpoint(a, c) + addArc(k.p, mac, anorm, cnorm) + addArc(&k.r, mac, anorm.Neg(), cnorm.Neg()) + } else if depth < maxDepth && angleGreaterThan45(ab, bc) { + // Divide the segment in two and push both halves on the stack. + mab := midpoint(a, b) + mbc := midpoint(b, c) + t++ + ds[t+0] = depth + 1 + ds[t-1] = depth + 1 + ps[2*t+2] = a + ps[2*t+1] = mab + ps[2*t+0] = midpoint(mab, mbc) + ps[2*t-1] = mbc + continue + } else { + // Translate the control points. + bnorm := c.Sub(a).Norm(k.u).Rot90CCW() + cnorm = bc.Norm(k.u).Rot90CCW() + k.p.Add2(b.Add(bnorm), c.Add(cnorm)) + k.r.Add2(b.Sub(bnorm), c.Sub(cnorm)) + } + if t == 0 { + k.a, k.anorm = c, cnorm + return + } + t-- + anorm = cnorm + } + panic("unreachable") +} + +// Add1 adds a linear segment to the stroker. +func (k *stroker) Add1(b Point) { + bnorm := b.Sub(k.a).Norm(k.u).Rot90CCW() + if len(k.r) == 0 { + k.p.Start(k.a.Add(bnorm)) + k.r.Start(k.a.Sub(bnorm)) + } else { + k.jr.Join(k.p, &k.r, k.u, k.a, k.anorm, bnorm) + } + k.p.Add1(b.Add(bnorm)) + k.r.Add1(b.Sub(bnorm)) + k.a, k.anorm = b, bnorm +} + +// Add2 adds a quadratic segment to the stroker. +func (k *stroker) Add2(b, c Point) { + ab := b.Sub(k.a) + bc := c.Sub(b) + abnorm := ab.Norm(k.u).Rot90CCW() + if len(k.r) == 0 { + k.p.Start(k.a.Add(abnorm)) + k.r.Start(k.a.Sub(abnorm)) + } else { + k.jr.Join(k.p, &k.r, k.u, k.a, k.anorm, abnorm) + } + + // Approximate nearly-degenerate quadratics by linear segments. + abIsSmall := ab.Dot(ab) < epsilon + bcIsSmall := bc.Dot(bc) < epsilon + if abIsSmall || bcIsSmall { + acnorm := c.Sub(k.a).Norm(k.u).Rot90CCW() + k.p.Add1(c.Add(acnorm)) + k.r.Add1(c.Sub(acnorm)) + k.a, k.anorm = c, acnorm + return + } + + // The quadratic segment (k.a, b, c) has a point of maximum curvature. + // If this occurs at an end point, we process the segment as a whole. + t := curviest2(k.a, b, c) + if t <= 0 || t >= 65536 { + k.addNonCurvy2(b, c) + return + } + + // Otherwise, we perform a de Casteljau decomposition at the point of + // maximum curvature and process the two straighter parts. + mab := interpolate(k.a, b, t) + mbc := interpolate(b, c, t) + mabc := interpolate(mab, mbc, t) + + // If the vectors ab and bc are close to being in opposite directions, + // then the decomposition can become unstable, so we approximate the + // quadratic segment by two linear segments joined by an arc. + bcnorm := bc.Norm(k.u).Rot90CCW() + if abnorm.Dot(bcnorm) < -Fix64(k.u)*Fix64(k.u)*2047/2048 { + pArc := abnorm.Dot(bc) < 0 + + k.p.Add1(mabc.Add(abnorm)) + if pArc { + z := abnorm.Rot90CW() + addArc(k.p, mabc, abnorm, z) + addArc(k.p, mabc, z, bcnorm) + } + k.p.Add1(mabc.Add(bcnorm)) + k.p.Add1(c.Add(bcnorm)) + + k.r.Add1(mabc.Sub(abnorm)) + if !pArc { + z := abnorm.Rot90CW() + addArc(&k.r, mabc, abnorm.Neg(), z) + addArc(&k.r, mabc, z, bcnorm.Neg()) + } + k.r.Add1(mabc.Sub(bcnorm)) + k.r.Add1(c.Sub(bcnorm)) + + k.a, k.anorm = c, bcnorm + return + } + + // Process the decomposed parts. + k.addNonCurvy2(mab, mabc) + k.addNonCurvy2(mbc, c) +} + +// Add3 adds a cubic segment to the stroker. +func (k *stroker) Add3(b, c, d Point) { + panic("freetype/raster: stroke unimplemented for cubic segments") +} + +// stroke adds the stroked Path q to p, where q consists of exactly one curve. +func (k *stroker) stroke(q Path) { + // Stroking is implemented by deriving two paths each k.u apart from q. + // The left-hand-side path is added immediately to k.p; the right-hand-side + // path is accumulated in k.r. Once we've finished adding the LHS to k.p, + // we add the RHS in reverse order. + k.r = make(Path, 0, len(q)) + k.a = Point{q[1], q[2]} + for i := 4; i < len(q); { + switch q[i] { + case 1: + k.Add1(Point{q[i+1], q[i+2]}) + i += 4 + case 2: + k.Add2(Point{q[i+1], q[i+2]}, Point{q[i+3], q[i+4]}) + i += 6 + case 3: + k.Add3(Point{q[i+1], q[i+2]}, Point{q[i+3], q[i+4]}, Point{q[i+5], q[i+6]}) + i += 8 + default: + panic("freetype/raster: bad path") + } + } + if len(k.r) == 0 { + return + } + // TODO(nigeltao): if q is a closed curve then we should join the first and + // last segments instead of capping them. + k.cr.Cap(k.p, k.u, q.lastPoint(), k.anorm.Neg()) + addPathReversed(k.p, k.r) + pivot := q.firstPoint() + k.cr.Cap(k.p, k.u, pivot, pivot.Sub(Point{k.r[1], k.r[2]})) +} + +// Stroke adds q stroked with the given width to p. The result is typically +// self-intersecting and should be rasterized with UseNonZeroWinding. +// cr and jr may be nil, which defaults to a RoundCapper or RoundJoiner. +func Stroke(p Adder, q Path, width Fix32, cr Capper, jr Joiner) { + if len(q) == 0 { + return + } + if cr == nil { + cr = RoundCapper + } + if jr == nil { + jr = RoundJoiner + } + if q[0] != 0 { + panic("freetype/raster: bad path") + } + s := stroker{p: p, u: width / 2, cr: cr, jr: jr} + i := 0 + for j := 4; j < len(q); { + switch q[j] { + case 0: + s.stroke(q[i:j]) + i, j = j, j+4 + case 1: + j += 4 + case 2: + j += 6 + case 3: + j += 8 + default: + panic("freetype/raster: bad path") + } + } + s.stroke(q[i:]) +} diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/glyph.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/glyph.go new file mode 100644 index 000000000..b5f327851 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/glyph.go @@ -0,0 +1,530 @@ +// Copyright 2010 The Freetype-Go Authors. All rights reserved. +// Use of this source code is governed by your choice of either the +// FreeType License or the GNU General Public License version 2 (or +// any later version), both of which can be found in the LICENSE file. + +package truetype + +// Hinting is the policy for snapping a glyph's contours to pixel boundaries. +type Hinting int32 + +const ( + // NoHinting means to not perform any hinting. + NoHinting Hinting = iota + // FullHinting means to use the font's hinting instructions. + FullHinting + + // TODO: implement VerticalHinting. +) + +// A Point is a co-ordinate pair plus whether it is ``on'' a contour or an +// ``off'' control point. +type Point struct { + X, Y int32 + // The Flags' LSB means whether or not this Point is ``on'' the contour. + // Other bits are reserved for internal use. + Flags uint32 +} + +// A GlyphBuf holds a glyph's contours. A GlyphBuf can be re-used to load a +// series of glyphs from a Font. +type GlyphBuf struct { + // AdvanceWidth is the glyph's advance width. + AdvanceWidth int32 + // B is the glyph's bounding box. + B Bounds + // Point contains all Points from all contours of the glyph. If + // hinting was used to load a glyph then Unhinted contains those + // Points before they were hinted, and InFontUnits contains those + // Points before they were hinted and scaled. + Point, Unhinted, InFontUnits []Point + // End is the point indexes of the end point of each countour. The + // length of End is the number of contours in the glyph. The i'th + // contour consists of points Point[End[i-1]:End[i]], where End[-1] + // is interpreted to mean zero. + End []int + + font *Font + scale int32 + hinting Hinting + hinter hinter + // phantomPoints are the co-ordinates of the synthetic phantom points + // used for hinting and bounding box calculations. + phantomPoints [4]Point + // pp1x is the X co-ordinate of the first phantom point. The '1' is + // using 1-based indexing; pp1x is almost always phantomPoints[0].X. + // TODO: eliminate this and consistently use phantomPoints[0].X. + pp1x int32 + // metricsSet is whether the glyph's metrics have been set yet. For a + // compound glyph, a sub-glyph may override the outer glyph's metrics. + metricsSet bool + // tmp is a scratch buffer. + tmp []Point +} + +// Flags for decoding a glyph's contours. These flags are documented at +// http://developer.apple.com/fonts/TTRefMan/RM06/Chap6glyf.html. +const ( + flagOnCurve = 1 << iota + flagXShortVector + flagYShortVector + flagRepeat + flagPositiveXShortVector + flagPositiveYShortVector + + // The remaining flags are for internal use. + flagTouchedX + flagTouchedY +) + +// The same flag bits (0x10 and 0x20) are overloaded to have two meanings, +// dependent on the value of the flag{X,Y}ShortVector bits. +const ( + flagThisXIsSame = flagPositiveXShortVector + flagThisYIsSame = flagPositiveYShortVector +) + +// Load loads a glyph's contours from a Font, overwriting any previously +// loaded contours for this GlyphBuf. scale is the number of 26.6 fixed point +// units in 1 em, i is the glyph index, and h is the hinting policy. +func (g *GlyphBuf) Load(f *Font, scale int32, i Index, h Hinting) error { + g.Point = g.Point[:0] + g.Unhinted = g.Unhinted[:0] + g.InFontUnits = g.InFontUnits[:0] + g.End = g.End[:0] + g.font = f + g.hinting = h + g.scale = scale + g.pp1x = 0 + g.phantomPoints = [4]Point{} + g.metricsSet = false + + if h != NoHinting { + if err := g.hinter.init(f, scale); err != nil { + return err + } + } + if err := g.load(0, i, true); err != nil { + return err + } + // TODO: this selection of either g.pp1x or g.phantomPoints[0].X isn't ideal, + // and should be cleaned up once we have all the testScaling tests passing, + // plus additional tests for Freetype-Go's bounding boxes matching C Freetype's. + pp1x := g.pp1x + if h != NoHinting { + pp1x = g.phantomPoints[0].X + } + if pp1x != 0 { + for i := range g.Point { + g.Point[i].X -= pp1x + } + } + + advanceWidth := g.phantomPoints[1].X - g.phantomPoints[0].X + if h != NoHinting { + if len(f.hdmx) >= 8 { + if n := u32(f.hdmx, 4); n > 3+uint32(i) { + for hdmx := f.hdmx[8:]; uint32(len(hdmx)) >= n; hdmx = hdmx[n:] { + if int32(hdmx[0]) == scale>>6 { + advanceWidth = int32(hdmx[2+i]) << 6 + break + } + } + } + } + advanceWidth = (advanceWidth + 32) &^ 63 + } + g.AdvanceWidth = advanceWidth + + // Set g.B to the 'control box', which is the bounding box of the Bézier + // curves' control points. This is easier to calculate, no smaller than + // and often equal to the tightest possible bounding box of the curves + // themselves. This approach is what C Freetype does. We can't just scale + // the nominal bounding box in the glyf data as the hinting process and + // phantom point adjustment may move points outside of that box. + if len(g.Point) == 0 { + g.B = Bounds{} + } else { + p := g.Point[0] + g.B.XMin = p.X + g.B.XMax = p.X + g.B.YMin = p.Y + g.B.YMax = p.Y + for _, p := range g.Point[1:] { + if g.B.XMin > p.X { + g.B.XMin = p.X + } else if g.B.XMax < p.X { + g.B.XMax = p.X + } + if g.B.YMin > p.Y { + g.B.YMin = p.Y + } else if g.B.YMax < p.Y { + g.B.YMax = p.Y + } + } + // Snap the box to the grid, if hinting is on. + if h != NoHinting { + g.B.XMin &^= 63 + g.B.YMin &^= 63 + g.B.XMax += 63 + g.B.XMax &^= 63 + g.B.YMax += 63 + g.B.YMax &^= 63 + } + } + return nil +} + +func (g *GlyphBuf) load(recursion int32, i Index, useMyMetrics bool) (err error) { + // The recursion limit here is arbitrary, but defends against malformed glyphs. + if recursion >= 32 { + return UnsupportedError("excessive compound glyph recursion") + } + // Find the relevant slice of g.font.glyf. + var g0, g1 uint32 + if g.font.locaOffsetFormat == locaOffsetFormatShort { + g0 = 2 * uint32(u16(g.font.loca, 2*int(i))) + g1 = 2 * uint32(u16(g.font.loca, 2*int(i)+2)) + } else { + g0 = u32(g.font.loca, 4*int(i)) + g1 = u32(g.font.loca, 4*int(i)+4) + } + + // Decode the contour count and nominal bounding box, from the first + // 10 bytes of the glyf data. boundsYMin and boundsXMax, at offsets 4 + // and 6, are unused. + glyf, ne, boundsXMin, boundsYMax := []byte(nil), 0, int32(0), int32(0) + if g0+10 <= g1 { + glyf = g.font.glyf[g0:g1] + ne = int(int16(u16(glyf, 0))) + boundsXMin = int32(int16(u16(glyf, 2))) + boundsYMax = int32(int16(u16(glyf, 8))) + } + + // Create the phantom points. + uhm, pp1x := g.font.unscaledHMetric(i), int32(0) + uvm := g.font.unscaledVMetric(i, boundsYMax) + g.phantomPoints = [4]Point{ + {X: boundsXMin - uhm.LeftSideBearing}, + {X: boundsXMin - uhm.LeftSideBearing + uhm.AdvanceWidth}, + {X: uhm.AdvanceWidth / 2, Y: boundsYMax + uvm.TopSideBearing}, + {X: uhm.AdvanceWidth / 2, Y: boundsYMax + uvm.TopSideBearing - uvm.AdvanceHeight}, + } + if len(glyf) == 0 { + g.addPhantomsAndScale(len(g.Point), len(g.Point), true, true) + copy(g.phantomPoints[:], g.Point[len(g.Point)-4:]) + g.Point = g.Point[:len(g.Point)-4] + return nil + } + + // Load and hint the contours. + if ne < 0 { + if ne != -1 { + // http://developer.apple.com/fonts/TTRefMan/RM06/Chap6glyf.html says that + // "the values -2, -3, and so forth, are reserved for future use." + return UnsupportedError("negative number of contours") + } + pp1x = g.font.scale(g.scale * (boundsXMin - uhm.LeftSideBearing)) + if err := g.loadCompound(recursion, uhm, i, glyf, useMyMetrics); err != nil { + return err + } + } else { + np0, ne0 := len(g.Point), len(g.End) + program := g.loadSimple(glyf, ne) + g.addPhantomsAndScale(np0, np0, true, true) + pp1x = g.Point[len(g.Point)-4].X + if g.hinting != NoHinting { + if len(program) != 0 { + err := g.hinter.run( + program, + g.Point[np0:], + g.Unhinted[np0:], + g.InFontUnits[np0:], + g.End[ne0:], + ) + if err != nil { + return err + } + } + // Drop the four phantom points. + g.InFontUnits = g.InFontUnits[:len(g.InFontUnits)-4] + g.Unhinted = g.Unhinted[:len(g.Unhinted)-4] + } + if useMyMetrics { + copy(g.phantomPoints[:], g.Point[len(g.Point)-4:]) + } + g.Point = g.Point[:len(g.Point)-4] + if np0 != 0 { + // The hinting program expects the []End values to be indexed relative + // to the inner glyph, not the outer glyph, so we delay adding np0 until + // after the hinting program (if any) has run. + for i := ne0; i < len(g.End); i++ { + g.End[i] += np0 + } + } + } + if useMyMetrics && !g.metricsSet { + g.metricsSet = true + g.pp1x = pp1x + } + return nil +} + +// loadOffset is the initial offset for loadSimple and loadCompound. The first +// 10 bytes are the number of contours and the bounding box. +const loadOffset = 10 + +func (g *GlyphBuf) loadSimple(glyf []byte, ne int) (program []byte) { + offset := loadOffset + for i := 0; i < ne; i++ { + g.End = append(g.End, 1+int(u16(glyf, offset))) + offset += 2 + } + + // Note the TrueType hinting instructions. + instrLen := int(u16(glyf, offset)) + offset += 2 + program = glyf[offset : offset+instrLen] + offset += instrLen + + np0 := len(g.Point) + np1 := np0 + int(g.End[len(g.End)-1]) + + // Decode the flags. + for i := np0; i < np1; { + c := uint32(glyf[offset]) + offset++ + g.Point = append(g.Point, Point{Flags: c}) + i++ + if c&flagRepeat != 0 { + count := glyf[offset] + offset++ + for ; count > 0; count-- { + g.Point = append(g.Point, Point{Flags: c}) + i++ + } + } + } + + // Decode the co-ordinates. + var x int16 + for i := np0; i < np1; i++ { + f := g.Point[i].Flags + if f&flagXShortVector != 0 { + dx := int16(glyf[offset]) + offset++ + if f&flagPositiveXShortVector == 0 { + x -= dx + } else { + x += dx + } + } else if f&flagThisXIsSame == 0 { + x += int16(u16(glyf, offset)) + offset += 2 + } + g.Point[i].X = int32(x) + } + var y int16 + for i := np0; i < np1; i++ { + f := g.Point[i].Flags + if f&flagYShortVector != 0 { + dy := int16(glyf[offset]) + offset++ + if f&flagPositiveYShortVector == 0 { + y -= dy + } else { + y += dy + } + } else if f&flagThisYIsSame == 0 { + y += int16(u16(glyf, offset)) + offset += 2 + } + g.Point[i].Y = int32(y) + } + + return program +} + +func (g *GlyphBuf) loadCompound(recursion int32, uhm HMetric, i Index, + glyf []byte, useMyMetrics bool) error { + + // Flags for decoding a compound glyph. These flags are documented at + // http://developer.apple.com/fonts/TTRefMan/RM06/Chap6glyf.html. + const ( + flagArg1And2AreWords = 1 << iota + flagArgsAreXYValues + flagRoundXYToGrid + flagWeHaveAScale + flagUnused + flagMoreComponents + flagWeHaveAnXAndYScale + flagWeHaveATwoByTwo + flagWeHaveInstructions + flagUseMyMetrics + flagOverlapCompound + ) + np0, ne0 := len(g.Point), len(g.End) + offset := loadOffset + for { + flags := u16(glyf, offset) + component := Index(u16(glyf, offset+2)) + dx, dy, transform, hasTransform := int32(0), int32(0), [4]int32{}, false + if flags&flagArg1And2AreWords != 0 { + dx = int32(int16(u16(glyf, offset+4))) + dy = int32(int16(u16(glyf, offset+6))) + offset += 8 + } else { + dx = int32(int16(int8(glyf[offset+4]))) + dy = int32(int16(int8(glyf[offset+5]))) + offset += 6 + } + if flags&flagArgsAreXYValues == 0 { + return UnsupportedError("compound glyph transform vector") + } + if flags&(flagWeHaveAScale|flagWeHaveAnXAndYScale|flagWeHaveATwoByTwo) != 0 { + hasTransform = true + switch { + case flags&flagWeHaveAScale != 0: + transform[0] = int32(int16(u16(glyf, offset+0))) + transform[3] = transform[0] + offset += 2 + case flags&flagWeHaveAnXAndYScale != 0: + transform[0] = int32(int16(u16(glyf, offset+0))) + transform[3] = int32(int16(u16(glyf, offset+2))) + offset += 4 + case flags&flagWeHaveATwoByTwo != 0: + transform[0] = int32(int16(u16(glyf, offset+0))) + transform[1] = int32(int16(u16(glyf, offset+2))) + transform[2] = int32(int16(u16(glyf, offset+4))) + transform[3] = int32(int16(u16(glyf, offset+6))) + offset += 8 + } + } + savedPP := g.phantomPoints + np0 := len(g.Point) + componentUMM := useMyMetrics && (flags&flagUseMyMetrics != 0) + if err := g.load(recursion+1, component, componentUMM); err != nil { + return err + } + if flags&flagUseMyMetrics == 0 { + g.phantomPoints = savedPP + } + if hasTransform { + for j := np0; j < len(g.Point); j++ { + p := &g.Point[j] + newX := int32((int64(p.X)*int64(transform[0])+1<<13)>>14) + + int32((int64(p.Y)*int64(transform[2])+1<<13)>>14) + newY := int32((int64(p.X)*int64(transform[1])+1<<13)>>14) + + int32((int64(p.Y)*int64(transform[3])+1<<13)>>14) + p.X, p.Y = newX, newY + } + } + dx = g.font.scale(g.scale * dx) + dy = g.font.scale(g.scale * dy) + if flags&flagRoundXYToGrid != 0 { + dx = (dx + 32) &^ 63 + dy = (dy + 32) &^ 63 + } + for j := np0; j < len(g.Point); j++ { + p := &g.Point[j] + p.X += dx + p.Y += dy + } + // TODO: also adjust g.InFontUnits and g.Unhinted? + if flags&flagMoreComponents == 0 { + break + } + } + + instrLen := 0 + if g.hinting != NoHinting && offset+2 <= len(glyf) { + instrLen = int(u16(glyf, offset)) + offset += 2 + } + + g.addPhantomsAndScale(np0, len(g.Point), false, instrLen > 0) + points, ends := g.Point[np0:], g.End[ne0:] + g.Point = g.Point[:len(g.Point)-4] + for j := range points { + points[j].Flags &^= flagTouchedX | flagTouchedY + } + + if instrLen == 0 { + if !g.metricsSet { + copy(g.phantomPoints[:], points[len(points)-4:]) + } + return nil + } + + // Hint the compound glyph. + program := glyf[offset : offset+instrLen] + // Temporarily adjust the ends to be relative to this compound glyph. + if np0 != 0 { + for i := range ends { + ends[i] -= np0 + } + } + // Hinting instructions of a composite glyph completely refer to the + // (already) hinted subglyphs. + g.tmp = append(g.tmp[:0], points...) + if err := g.hinter.run(program, points, g.tmp, g.tmp, ends); err != nil { + return err + } + if np0 != 0 { + for i := range ends { + ends[i] += np0 + } + } + if !g.metricsSet { + copy(g.phantomPoints[:], points[len(points)-4:]) + } + return nil +} + +func (g *GlyphBuf) addPhantomsAndScale(np0, np1 int, simple, adjust bool) { + // Add the four phantom points. + g.Point = append(g.Point, g.phantomPoints[:]...) + // Scale the points. + if simple && g.hinting != NoHinting { + g.InFontUnits = append(g.InFontUnits, g.Point[np1:]...) + } + for i := np1; i < len(g.Point); i++ { + p := &g.Point[i] + p.X = g.font.scale(g.scale * p.X) + p.Y = g.font.scale(g.scale * p.Y) + } + if g.hinting == NoHinting { + return + } + // Round the 1st phantom point to the grid, shifting all other points equally. + // Note that "all other points" starts from np0, not np1. + // TODO: delete this adjustment and the np0/np1 distinction, when + // we update the compatibility tests to C Freetype 2.5.3. + // See http://git.savannah.gnu.org/cgit/freetype/freetype2.git/commit/?id=05c786d990390a7ca18e62962641dac740bacb06 + if adjust { + pp1x := g.Point[len(g.Point)-4].X + if dx := ((pp1x + 32) &^ 63) - pp1x; dx != 0 { + for i := np0; i < len(g.Point); i++ { + g.Point[i].X += dx + } + } + } + if simple { + g.Unhinted = append(g.Unhinted, g.Point[np1:]...) + } + // Round the 2nd and 4th phantom point to the grid. + p := &g.Point[len(g.Point)-3] + p.X = (p.X + 32) &^ 63 + p = &g.Point[len(g.Point)-1] + p.Y = (p.Y + 32) &^ 63 +} + +// TODO: is this necessary? The zero-valued GlyphBuf is perfectly usable. + +// NewGlyphBuf returns a newly allocated GlyphBuf. +func NewGlyphBuf() *GlyphBuf { + return &GlyphBuf{ + Point: make([]Point, 0, 256), + End: make([]int, 0, 32), + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/hint.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/hint.go new file mode 100644 index 000000000..26c631436 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/hint.go @@ -0,0 +1,1764 @@ +// Copyright 2012 The Freetype-Go Authors. All rights reserved. +// Use of this source code is governed by your choice of either the +// FreeType License or the GNU General Public License version 2 (or +// any later version), both of which can be found in the LICENSE file. + +package truetype + +// This file implements a Truetype bytecode interpreter. +// The opcodes are described at https://developer.apple.com/fonts/TTRefMan/RM05/Chap5.html + +import ( + "errors" + "math" +) + +const ( + twilightZone = 0 + glyphZone = 1 + numZone = 2 +) + +type pointType uint32 + +const ( + current pointType = 0 + unhinted pointType = 1 + inFontUnits pointType = 2 + numPointType = 3 +) + +// callStackEntry is a bytecode call stack entry. +type callStackEntry struct { + program []byte + pc int + loopCount int32 +} + +// hinter implements bytecode hinting. A hinter can be re-used to hint a series +// of glyphs from a Font. +type hinter struct { + stack, store []int32 + + // functions is a map from function number to bytecode. + functions map[int32][]byte + + // font and scale are the font and scale last used for this hinter. + // Changing the font will require running the new font's fpgm bytecode. + // Changing either will require running the font's prep bytecode. + font *Font + scale int32 + + // gs and defaultGS are the current and default graphics state. The + // default graphics state is the global default graphics state after + // the font's fpgm and prep programs have been run. + gs, defaultGS graphicsState + + // points and ends are the twilight zone's points, glyph's points + // and glyph's contour boundaries. + points [numZone][numPointType][]Point + ends []int + + // scaledCVT is the lazily initialized scaled Control Value Table. + scaledCVTInitialized bool + scaledCVT []f26dot6 +} + +// graphicsState is described at https://developer.apple.com/fonts/TTRefMan/RM04/Chap4.html +type graphicsState struct { + // Projection vector, freedom vector and dual projection vector. + pv, fv, dv [2]f2dot14 + // Reference points and zone pointers. + rp, zp [3]int32 + // Control Value / Single Width Cut-In. + controlValueCutIn, singleWidthCutIn, singleWidth f26dot6 + // Delta base / shift. + deltaBase, deltaShift int32 + // Minimum distance. + minDist f26dot6 + // Loop count. + loop int32 + // Rounding policy. + roundPeriod, roundPhase, roundThreshold f26dot6 + roundSuper45 bool + // Auto-flip. + autoFlip bool +} + +var globalDefaultGS = graphicsState{ + pv: [2]f2dot14{0x4000, 0}, // Unit vector along the X axis. + fv: [2]f2dot14{0x4000, 0}, + dv: [2]f2dot14{0x4000, 0}, + zp: [3]int32{1, 1, 1}, + controlValueCutIn: (17 << 6) / 16, // 17/16 as an f26dot6. + deltaBase: 9, + deltaShift: 3, + minDist: 1 << 6, // 1 as an f26dot6. + loop: 1, + roundPeriod: 1 << 6, // 1 as an f26dot6. + roundThreshold: 1 << 5, // 1/2 as an f26dot6. + roundSuper45: false, + autoFlip: true, +} + +func resetTwilightPoints(f *Font, p []Point) []Point { + if n := int(f.maxTwilightPoints) + 4; n <= cap(p) { + p = p[:n] + for i := range p { + p[i] = Point{} + } + } else { + p = make([]Point, n) + } + return p +} + +func (h *hinter) init(f *Font, scale int32) error { + h.points[twilightZone][0] = resetTwilightPoints(f, h.points[twilightZone][0]) + h.points[twilightZone][1] = resetTwilightPoints(f, h.points[twilightZone][1]) + h.points[twilightZone][2] = resetTwilightPoints(f, h.points[twilightZone][2]) + + rescale := h.scale != scale + if h.font != f { + h.font, rescale = f, true + if h.functions == nil { + h.functions = make(map[int32][]byte) + } else { + for k := range h.functions { + delete(h.functions, k) + } + } + + if x := int(f.maxStackElements); x > len(h.stack) { + x += 255 + x &^= 255 + h.stack = make([]int32, x) + } + if x := int(f.maxStorage); x > len(h.store) { + x += 15 + x &^= 15 + h.store = make([]int32, x) + } + if len(f.fpgm) != 0 { + if err := h.run(f.fpgm, nil, nil, nil, nil); err != nil { + return err + } + } + } + + if rescale { + h.scale = scale + h.scaledCVTInitialized = false + + h.defaultGS = globalDefaultGS + + if len(f.prep) != 0 { + if err := h.run(f.prep, nil, nil, nil, nil); err != nil { + return err + } + h.defaultGS = h.gs + // The MS rasterizer doesn't allow the following graphics state + // variables to be modified by the CVT program. + h.defaultGS.pv = globalDefaultGS.pv + h.defaultGS.fv = globalDefaultGS.fv + h.defaultGS.dv = globalDefaultGS.dv + h.defaultGS.rp = globalDefaultGS.rp + h.defaultGS.zp = globalDefaultGS.zp + h.defaultGS.loop = globalDefaultGS.loop + } + } + return nil +} + +func (h *hinter) run(program []byte, pCurrent, pUnhinted, pInFontUnits []Point, ends []int) error { + h.gs = h.defaultGS + h.points[glyphZone][current] = pCurrent + h.points[glyphZone][unhinted] = pUnhinted + h.points[glyphZone][inFontUnits] = pInFontUnits + h.ends = ends + + if len(program) > 50000 { + return errors.New("truetype: hinting: too many instructions") + } + var ( + steps, pc, top int + opcode uint8 + + callStack [32]callStackEntry + callStackTop int + ) + + for 0 <= pc && pc < len(program) { + steps++ + if steps == 100000 { + return errors.New("truetype: hinting: too many steps") + } + opcode = program[pc] + if top < int(popCount[opcode]) { + return errors.New("truetype: hinting: stack underflow") + } + switch opcode { + + case opSVTCA0: + h.gs.pv = [2]f2dot14{0, 0x4000} + h.gs.fv = [2]f2dot14{0, 0x4000} + h.gs.dv = [2]f2dot14{0, 0x4000} + + case opSVTCA1: + h.gs.pv = [2]f2dot14{0x4000, 0} + h.gs.fv = [2]f2dot14{0x4000, 0} + h.gs.dv = [2]f2dot14{0x4000, 0} + + case opSPVTCA0: + h.gs.pv = [2]f2dot14{0, 0x4000} + h.gs.dv = [2]f2dot14{0, 0x4000} + + case opSPVTCA1: + h.gs.pv = [2]f2dot14{0x4000, 0} + h.gs.dv = [2]f2dot14{0x4000, 0} + + case opSFVTCA0: + h.gs.fv = [2]f2dot14{0, 0x4000} + + case opSFVTCA1: + h.gs.fv = [2]f2dot14{0x4000, 0} + + case opSPVTL0, opSPVTL1, opSFVTL0, opSFVTL1: + top -= 2 + p1 := h.point(0, current, h.stack[top+0]) + p2 := h.point(0, current, h.stack[top+1]) + if p1 == nil || p2 == nil { + return errors.New("truetype: hinting: point out of range") + } + dx := f2dot14(p1.X - p2.X) + dy := f2dot14(p1.Y - p2.Y) + if dx == 0 && dy == 0 { + dx = 0x4000 + } else if opcode&1 != 0 { + // Counter-clockwise rotation. + dx, dy = -dy, dx + } + v := normalize(dx, dy) + if opcode < opSFVTL0 { + h.gs.pv = v + h.gs.dv = v + } else { + h.gs.fv = v + } + + case opSPVFS: + top -= 2 + h.gs.pv = normalize(f2dot14(h.stack[top]), f2dot14(h.stack[top+1])) + h.gs.dv = h.gs.pv + + case opSFVFS: + top -= 2 + h.gs.fv = normalize(f2dot14(h.stack[top]), f2dot14(h.stack[top+1])) + + case opGPV: + if top+1 >= len(h.stack) { + return errors.New("truetype: hinting: stack overflow") + } + h.stack[top+0] = int32(h.gs.pv[0]) + h.stack[top+1] = int32(h.gs.pv[1]) + top += 2 + + case opGFV: + if top+1 >= len(h.stack) { + return errors.New("truetype: hinting: stack overflow") + } + h.stack[top+0] = int32(h.gs.fv[0]) + h.stack[top+1] = int32(h.gs.fv[1]) + top += 2 + + case opSFVTPV: + h.gs.fv = h.gs.pv + + case opISECT: + top -= 5 + p := h.point(2, current, h.stack[top+0]) + a0 := h.point(1, current, h.stack[top+1]) + a1 := h.point(1, current, h.stack[top+2]) + b0 := h.point(0, current, h.stack[top+3]) + b1 := h.point(0, current, h.stack[top+4]) + if p == nil || a0 == nil || a1 == nil || b0 == nil || b1 == nil { + return errors.New("truetype: hinting: point out of range") + } + + dbx := b1.X - b0.X + dby := b1.Y - b0.Y + dax := a1.X - a0.X + day := a1.Y - a0.Y + dx := b0.X - a0.X + dy := b0.Y - a0.Y + discriminant := mulDiv(int64(dax), int64(-dby), 0x40) + + mulDiv(int64(day), int64(dbx), 0x40) + dotProduct := mulDiv(int64(dax), int64(dbx), 0x40) + + mulDiv(int64(day), int64(dby), 0x40) + // The discriminant above is actually a cross product of vectors + // da and db. Together with the dot product, they can be used as + // surrogates for sine and cosine of the angle between the vectors. + // Indeed, + // dotproduct = |da||db|cos(angle) + // discriminant = |da||db|sin(angle) + // We use these equations to reject grazing intersections by + // thresholding abs(tan(angle)) at 1/19, corresponding to 3 degrees. + absDisc, absDotP := discriminant, dotProduct + if absDisc < 0 { + absDisc = -absDisc + } + if absDotP < 0 { + absDotP = -absDotP + } + if 19*absDisc > absDotP { + val := mulDiv(int64(dx), int64(-dby), 0x40) + + mulDiv(int64(dy), int64(dbx), 0x40) + rx := mulDiv(val, int64(dax), discriminant) + ry := mulDiv(val, int64(day), discriminant) + p.X = a0.X + int32(rx) + p.Y = a0.Y + int32(ry) + } else { + p.X = (a0.X + a1.X + b0.X + b1.X) / 4 + p.Y = (a0.Y + a1.Y + b0.Y + b1.Y) / 4 + } + p.Flags |= flagTouchedX | flagTouchedY + + case opSRP0, opSRP1, opSRP2: + top-- + h.gs.rp[opcode-opSRP0] = h.stack[top] + + case opSZP0, opSZP1, opSZP2: + top-- + h.gs.zp[opcode-opSZP0] = h.stack[top] + + case opSZPS: + top-- + h.gs.zp[0] = h.stack[top] + h.gs.zp[1] = h.stack[top] + h.gs.zp[2] = h.stack[top] + + case opSLOOP: + top-- + if h.stack[top] <= 0 { + return errors.New("truetype: hinting: invalid data") + } + h.gs.loop = h.stack[top] + + case opRTG: + h.gs.roundPeriod = 1 << 6 + h.gs.roundPhase = 0 + h.gs.roundThreshold = 1 << 5 + h.gs.roundSuper45 = false + + case opRTHG: + h.gs.roundPeriod = 1 << 6 + h.gs.roundPhase = 1 << 5 + h.gs.roundThreshold = 1 << 5 + h.gs.roundSuper45 = false + + case opSMD: + top-- + h.gs.minDist = f26dot6(h.stack[top]) + + case opELSE: + opcode = 1 + goto ifelse + + case opJMPR: + top-- + pc += int(h.stack[top]) + continue + + case opSCVTCI: + top-- + h.gs.controlValueCutIn = f26dot6(h.stack[top]) + + case opSSWCI: + top-- + h.gs.singleWidthCutIn = f26dot6(h.stack[top]) + + case opSSW: + top-- + h.gs.singleWidth = f26dot6(h.font.scale(h.scale * h.stack[top])) + + case opDUP: + if top >= len(h.stack) { + return errors.New("truetype: hinting: stack overflow") + } + h.stack[top] = h.stack[top-1] + top++ + + case opPOP: + top-- + + case opCLEAR: + top = 0 + + case opSWAP: + h.stack[top-1], h.stack[top-2] = h.stack[top-2], h.stack[top-1] + + case opDEPTH: + if top >= len(h.stack) { + return errors.New("truetype: hinting: stack overflow") + } + h.stack[top] = int32(top) + top++ + + case opCINDEX, opMINDEX: + x := int(h.stack[top-1]) + if x <= 0 || x >= top { + return errors.New("truetype: hinting: invalid data") + } + h.stack[top-1] = h.stack[top-1-x] + if opcode == opMINDEX { + copy(h.stack[top-1-x:top-1], h.stack[top-x:top]) + top-- + } + + case opALIGNPTS: + top -= 2 + p := h.point(1, current, h.stack[top]) + q := h.point(0, current, h.stack[top+1]) + if p == nil || q == nil { + return errors.New("truetype: hinting: point out of range") + } + d := dotProduct(f26dot6(q.X-p.X), f26dot6(q.Y-p.Y), h.gs.pv) / 2 + h.move(p, +d, true) + h.move(q, -d, true) + + case opUTP: + top-- + p := h.point(0, current, h.stack[top]) + if p == nil { + return errors.New("truetype: hinting: point out of range") + } + p.Flags &^= flagTouchedX | flagTouchedY + + case opLOOPCALL, opCALL: + if callStackTop >= len(callStack) { + return errors.New("truetype: hinting: call stack overflow") + } + top-- + f, ok := h.functions[h.stack[top]] + if !ok { + return errors.New("truetype: hinting: undefined function") + } + callStack[callStackTop] = callStackEntry{program, pc, 1} + if opcode == opLOOPCALL { + top-- + if h.stack[top] == 0 { + break + } + callStack[callStackTop].loopCount = h.stack[top] + } + callStackTop++ + program, pc = f, 0 + continue + + case opFDEF: + // Save all bytecode up until the next ENDF. + startPC := pc + 1 + fdefloop: + for { + pc++ + if pc >= len(program) { + return errors.New("truetype: hinting: unbalanced FDEF") + } + switch program[pc] { + case opFDEF: + return errors.New("truetype: hinting: nested FDEF") + case opENDF: + top-- + h.functions[h.stack[top]] = program[startPC : pc+1] + break fdefloop + default: + var ok bool + pc, ok = skipInstructionPayload(program, pc) + if !ok { + return errors.New("truetype: hinting: unbalanced FDEF") + } + } + } + + case opENDF: + if callStackTop == 0 { + return errors.New("truetype: hinting: call stack underflow") + } + callStackTop-- + callStack[callStackTop].loopCount-- + if callStack[callStackTop].loopCount != 0 { + callStackTop++ + pc = 0 + continue + } + program, pc = callStack[callStackTop].program, callStack[callStackTop].pc + + case opMDAP0, opMDAP1: + top-- + i := h.stack[top] + p := h.point(0, current, i) + if p == nil { + return errors.New("truetype: hinting: point out of range") + } + distance := f26dot6(0) + if opcode == opMDAP1 { + distance = dotProduct(f26dot6(p.X), f26dot6(p.Y), h.gs.pv) + // TODO: metrics compensation. + distance = h.round(distance) - distance + } + h.move(p, distance, true) + h.gs.rp[0] = i + h.gs.rp[1] = i + + case opIUP0, opIUP1: + iupY, mask := opcode == opIUP0, uint32(flagTouchedX) + if iupY { + mask = flagTouchedY + } + prevEnd := 0 + for _, end := range h.ends { + for i := prevEnd; i < end; i++ { + for i < end && h.points[glyphZone][current][i].Flags&mask == 0 { + i++ + } + if i == end { + break + } + firstTouched, curTouched := i, i + i++ + for ; i < end; i++ { + if h.points[glyphZone][current][i].Flags&mask != 0 { + h.iupInterp(iupY, curTouched+1, i-1, curTouched, i) + curTouched = i + } + } + if curTouched == firstTouched { + h.iupShift(iupY, prevEnd, end, curTouched) + } else { + h.iupInterp(iupY, curTouched+1, end-1, curTouched, firstTouched) + if firstTouched > 0 { + h.iupInterp(iupY, prevEnd, firstTouched-1, curTouched, firstTouched) + } + } + } + prevEnd = end + } + + case opSHP0, opSHP1: + if top < int(h.gs.loop) { + return errors.New("truetype: hinting: stack underflow") + } + _, _, d, ok := h.displacement(opcode&1 == 0) + if !ok { + return errors.New("truetype: hinting: point out of range") + } + for ; h.gs.loop != 0; h.gs.loop-- { + top-- + p := h.point(2, current, h.stack[top]) + if p == nil { + return errors.New("truetype: hinting: point out of range") + } + h.move(p, d, true) + } + h.gs.loop = 1 + + case opSHC0, opSHC1: + top-- + zonePointer, i, d, ok := h.displacement(opcode&1 == 0) + if !ok { + return errors.New("truetype: hinting: point out of range") + } + if h.gs.zp[2] == 0 { + // TODO: implement this when we have a glyph that does this. + return errors.New("hinting: unimplemented SHC instruction") + } + contour := h.stack[top] + if contour < 0 || len(ends) <= int(contour) { + return errors.New("truetype: hinting: contour out of range") + } + j0, j1 := int32(0), int32(h.ends[contour]) + if contour > 0 { + j0 = int32(h.ends[contour-1]) + } + move := h.gs.zp[zonePointer] != h.gs.zp[2] + for j := j0; j < j1; j++ { + if move || j != i { + h.move(h.point(2, current, j), d, true) + } + } + + case opSHZ0, opSHZ1: + top-- + zonePointer, i, d, ok := h.displacement(opcode&1 == 0) + if !ok { + return errors.New("truetype: hinting: point out of range") + } + + // As per C Freetype, SHZ doesn't move the phantom points, or mark + // the points as touched. + limit := int32(len(h.points[h.gs.zp[2]][current])) + if h.gs.zp[2] == glyphZone { + limit -= 4 + } + for j := int32(0); j < limit; j++ { + if i != j || h.gs.zp[zonePointer] != h.gs.zp[2] { + h.move(h.point(2, current, j), d, false) + } + } + + case opSHPIX: + top-- + d := f26dot6(h.stack[top]) + if top < int(h.gs.loop) { + return errors.New("truetype: hinting: stack underflow") + } + for ; h.gs.loop != 0; h.gs.loop-- { + top-- + p := h.point(2, current, h.stack[top]) + if p == nil { + return errors.New("truetype: hinting: point out of range") + } + h.move(p, d, true) + } + h.gs.loop = 1 + + case opIP: + if top < int(h.gs.loop) { + return errors.New("truetype: hinting: stack underflow") + } + pointType := inFontUnits + twilight := h.gs.zp[0] == 0 || h.gs.zp[1] == 0 || h.gs.zp[2] == 0 + if twilight { + pointType = unhinted + } + p := h.point(1, pointType, h.gs.rp[2]) + oldP := h.point(0, pointType, h.gs.rp[1]) + oldRange := dotProduct(f26dot6(p.X-oldP.X), f26dot6(p.Y-oldP.Y), h.gs.dv) + + p = h.point(1, current, h.gs.rp[2]) + curP := h.point(0, current, h.gs.rp[1]) + curRange := dotProduct(f26dot6(p.X-curP.X), f26dot6(p.Y-curP.Y), h.gs.pv) + for ; h.gs.loop != 0; h.gs.loop-- { + top-- + i := h.stack[top] + p = h.point(2, pointType, i) + oldDist := dotProduct(f26dot6(p.X-oldP.X), f26dot6(p.Y-oldP.Y), h.gs.dv) + p = h.point(2, current, i) + curDist := dotProduct(f26dot6(p.X-curP.X), f26dot6(p.Y-curP.Y), h.gs.pv) + newDist := f26dot6(0) + if oldDist != 0 { + if oldRange != 0 { + newDist = f26dot6(mulDiv(int64(oldDist), int64(curRange), int64(oldRange))) + } else { + newDist = -oldDist + } + } + h.move(p, newDist-curDist, true) + } + h.gs.loop = 1 + + case opMSIRP0, opMSIRP1: + top -= 2 + i := h.stack[top] + distance := f26dot6(h.stack[top+1]) + + // TODO: special case h.gs.zp[1] == 0 in C Freetype. + ref := h.point(0, current, h.gs.rp[0]) + p := h.point(1, current, i) + if ref == nil || p == nil { + return errors.New("truetype: hinting: point out of range") + } + curDist := dotProduct(f26dot6(p.X-ref.X), f26dot6(p.Y-ref.Y), h.gs.pv) + + // Set-RP0 bit. + if opcode == opMSIRP1 { + h.gs.rp[0] = i + } + h.gs.rp[1] = h.gs.rp[0] + h.gs.rp[2] = i + + // Move the point. + h.move(p, distance-curDist, true) + + case opALIGNRP: + if top < int(h.gs.loop) { + return errors.New("truetype: hinting: stack underflow") + } + ref := h.point(0, current, h.gs.rp[0]) + if ref == nil { + return errors.New("truetype: hinting: point out of range") + } + for ; h.gs.loop != 0; h.gs.loop-- { + top-- + p := h.point(1, current, h.stack[top]) + if p == nil { + return errors.New("truetype: hinting: point out of range") + } + h.move(p, -dotProduct(f26dot6(p.X-ref.X), f26dot6(p.Y-ref.Y), h.gs.pv), true) + } + h.gs.loop = 1 + + case opRTDG: + h.gs.roundPeriod = 1 << 5 + h.gs.roundPhase = 0 + h.gs.roundThreshold = 1 << 4 + h.gs.roundSuper45 = false + + case opMIAP0, opMIAP1: + top -= 2 + i := h.stack[top] + distance := h.getScaledCVT(h.stack[top+1]) + if h.gs.zp[0] == 0 { + p := h.point(0, unhinted, i) + q := h.point(0, current, i) + p.X = int32((int64(distance) * int64(h.gs.fv[0])) >> 14) + p.Y = int32((int64(distance) * int64(h.gs.fv[1])) >> 14) + *q = *p + } + p := h.point(0, current, i) + oldDist := dotProduct(f26dot6(p.X), f26dot6(p.Y), h.gs.pv) + if opcode == opMIAP1 { + if (distance - oldDist).abs() > h.gs.controlValueCutIn { + distance = oldDist + } + // TODO: metrics compensation. + distance = h.round(distance) + } + h.move(p, distance-oldDist, true) + h.gs.rp[0] = i + h.gs.rp[1] = i + + case opNPUSHB: + opcode = 0 + goto push + + case opNPUSHW: + opcode = 0x80 + goto push + + case opWS: + top -= 2 + i := int(h.stack[top]) + if i < 0 || len(h.store) <= i { + return errors.New("truetype: hinting: invalid data") + } + h.store[i] = h.stack[top+1] + + case opRS: + i := int(h.stack[top-1]) + if i < 0 || len(h.store) <= i { + return errors.New("truetype: hinting: invalid data") + } + h.stack[top-1] = h.store[i] + + case opWCVTP: + top -= 2 + h.setScaledCVT(h.stack[top], f26dot6(h.stack[top+1])) + + case opRCVT: + h.stack[top-1] = int32(h.getScaledCVT(h.stack[top-1])) + + case opGC0, opGC1: + i := h.stack[top-1] + if opcode == opGC0 { + p := h.point(2, current, i) + h.stack[top-1] = int32(dotProduct(f26dot6(p.X), f26dot6(p.Y), h.gs.pv)) + } else { + p := h.point(2, unhinted, i) + // Using dv as per C Freetype. + h.stack[top-1] = int32(dotProduct(f26dot6(p.X), f26dot6(p.Y), h.gs.dv)) + } + + case opSCFS: + top -= 2 + i := h.stack[top] + p := h.point(2, current, i) + if p == nil { + return errors.New("truetype: hinting: point out of range") + } + c := dotProduct(f26dot6(p.X), f26dot6(p.Y), h.gs.pv) + h.move(p, f26dot6(h.stack[top+1])-c, true) + if h.gs.zp[2] != 0 { + break + } + q := h.point(2, unhinted, i) + if q == nil { + return errors.New("truetype: hinting: point out of range") + } + q.X = p.X + q.Y = p.Y + + case opMD0, opMD1: + top-- + pt, v, scale := pointType(0), [2]f2dot14{}, false + if opcode == opMD0 { + pt = current + v = h.gs.pv + } else if h.gs.zp[0] == 0 || h.gs.zp[1] == 0 { + pt = unhinted + v = h.gs.dv + } else { + pt = inFontUnits + v = h.gs.dv + scale = true + } + p := h.point(0, pt, h.stack[top-1]) + q := h.point(1, pt, h.stack[top]) + if p == nil || q == nil { + return errors.New("truetype: hinting: point out of range") + } + d := int32(dotProduct(f26dot6(p.X-q.X), f26dot6(p.Y-q.Y), v)) + if scale { + d = int32(int64(d*h.scale) / int64(h.font.fUnitsPerEm)) + } + h.stack[top-1] = d + + case opMPPEM, opMPS: + if top >= len(h.stack) { + return errors.New("truetype: hinting: stack overflow") + } + // For MPS, point size should be irrelevant; we return the PPEM. + h.stack[top] = h.scale >> 6 + top++ + + case opFLIPON, opFLIPOFF: + h.gs.autoFlip = opcode == opFLIPON + + case opDEBUG: + // No-op. + + case opLT: + top-- + h.stack[top-1] = bool2int32(h.stack[top-1] < h.stack[top]) + + case opLTEQ: + top-- + h.stack[top-1] = bool2int32(h.stack[top-1] <= h.stack[top]) + + case opGT: + top-- + h.stack[top-1] = bool2int32(h.stack[top-1] > h.stack[top]) + + case opGTEQ: + top-- + h.stack[top-1] = bool2int32(h.stack[top-1] >= h.stack[top]) + + case opEQ: + top-- + h.stack[top-1] = bool2int32(h.stack[top-1] == h.stack[top]) + + case opNEQ: + top-- + h.stack[top-1] = bool2int32(h.stack[top-1] != h.stack[top]) + + case opODD, opEVEN: + i := h.round(f26dot6(h.stack[top-1])) >> 6 + h.stack[top-1] = int32(i&1) ^ int32(opcode-opODD) + + case opIF: + top-- + if h.stack[top] == 0 { + opcode = 0 + goto ifelse + } + + case opEIF: + // No-op. + + case opAND: + top-- + h.stack[top-1] = bool2int32(h.stack[top-1] != 0 && h.stack[top] != 0) + + case opOR: + top-- + h.stack[top-1] = bool2int32(h.stack[top-1]|h.stack[top] != 0) + + case opNOT: + h.stack[top-1] = bool2int32(h.stack[top-1] == 0) + + case opDELTAP1: + goto delta + + case opSDB: + top-- + h.gs.deltaBase = h.stack[top] + + case opSDS: + top-- + h.gs.deltaShift = h.stack[top] + + case opADD: + top-- + h.stack[top-1] += h.stack[top] + + case opSUB: + top-- + h.stack[top-1] -= h.stack[top] + + case opDIV: + top-- + if h.stack[top] == 0 { + return errors.New("truetype: hinting: division by zero") + } + h.stack[top-1] = int32(f26dot6(h.stack[top-1]).div(f26dot6(h.stack[top]))) + + case opMUL: + top-- + h.stack[top-1] = int32(f26dot6(h.stack[top-1]).mul(f26dot6(h.stack[top]))) + + case opABS: + if h.stack[top-1] < 0 { + h.stack[top-1] = -h.stack[top-1] + } + + case opNEG: + h.stack[top-1] = -h.stack[top-1] + + case opFLOOR: + h.stack[top-1] &^= 63 + + case opCEILING: + h.stack[top-1] += 63 + h.stack[top-1] &^= 63 + + case opROUND00, opROUND01, opROUND10, opROUND11: + // The four flavors of opROUND are equivalent. See the comment below on + // opNROUND for the rationale. + h.stack[top-1] = int32(h.round(f26dot6(h.stack[top-1]))) + + case opNROUND00, opNROUND01, opNROUND10, opNROUND11: + // No-op. The spec says to add one of four "compensations for the engine + // characteristics", to cater for things like "different dot-size printers". + // https://developer.apple.com/fonts/TTRefMan/RM02/Chap2.html#engine_compensation + // This code does not implement engine compensation, as we don't expect to + // be used to output on dot-matrix printers. + + case opWCVTF: + top -= 2 + h.setScaledCVT(h.stack[top], f26dot6(h.font.scale(h.scale*h.stack[top+1]))) + + case opDELTAP2, opDELTAP3, opDELTAC1, opDELTAC2, opDELTAC3: + goto delta + + case opSROUND, opS45ROUND: + top-- + switch (h.stack[top] >> 6) & 0x03 { + case 0: + h.gs.roundPeriod = 1 << 5 + case 1, 3: + h.gs.roundPeriod = 1 << 6 + case 2: + h.gs.roundPeriod = 1 << 7 + } + h.gs.roundSuper45 = opcode == opS45ROUND + if h.gs.roundSuper45 { + // The spec says to multiply by √2, but the C Freetype code says 1/√2. + // We go with 1/√2. + h.gs.roundPeriod *= 46341 + h.gs.roundPeriod /= 65536 + } + h.gs.roundPhase = h.gs.roundPeriod * f26dot6((h.stack[top]>>4)&0x03) / 4 + if x := h.stack[top] & 0x0f; x != 0 { + h.gs.roundThreshold = h.gs.roundPeriod * f26dot6(x-4) / 8 + } else { + h.gs.roundThreshold = h.gs.roundPeriod - 1 + } + + case opJROT: + top -= 2 + if h.stack[top+1] != 0 { + pc += int(h.stack[top]) + continue + } + + case opJROF: + top -= 2 + if h.stack[top+1] == 0 { + pc += int(h.stack[top]) + continue + } + + case opROFF: + h.gs.roundPeriod = 0 + h.gs.roundPhase = 0 + h.gs.roundThreshold = 0 + h.gs.roundSuper45 = false + + case opRUTG: + h.gs.roundPeriod = 1 << 6 + h.gs.roundPhase = 0 + h.gs.roundThreshold = 1<<6 - 1 + h.gs.roundSuper45 = false + + case opRDTG: + h.gs.roundPeriod = 1 << 6 + h.gs.roundPhase = 0 + h.gs.roundThreshold = 0 + h.gs.roundSuper45 = false + + case opSANGW, opAA: + // These ops are "anachronistic" and no longer used. + top-- + + case opFLIPPT: + if top < int(h.gs.loop) { + return errors.New("truetype: hinting: stack underflow") + } + points := h.points[glyphZone][current] + for ; h.gs.loop != 0; h.gs.loop-- { + top-- + i := h.stack[top] + if i < 0 || len(points) <= int(i) { + return errors.New("truetype: hinting: point out of range") + } + points[i].Flags ^= flagOnCurve + } + h.gs.loop = 1 + + case opFLIPRGON, opFLIPRGOFF: + top -= 2 + i, j, points := h.stack[top], h.stack[top+1], h.points[glyphZone][current] + if i < 0 || len(points) <= int(i) || j < 0 || len(points) <= int(j) { + return errors.New("truetype: hinting: point out of range") + } + for ; i <= j; i++ { + if opcode == opFLIPRGON { + points[i].Flags |= flagOnCurve + } else { + points[i].Flags &^= flagOnCurve + } + } + + case opSCANCTRL: + // We do not support dropout control, as we always rasterize grayscale glyphs. + top-- + + case opSDPVTL0, opSDPVTL1: + top -= 2 + for i := 0; i < 2; i++ { + pt := unhinted + if i != 0 { + pt = current + } + p := h.point(1, pt, h.stack[top]) + q := h.point(2, pt, h.stack[top+1]) + if p == nil || q == nil { + return errors.New("truetype: hinting: point out of range") + } + dx := f2dot14(p.X - q.X) + dy := f2dot14(p.Y - q.Y) + if dx == 0 && dy == 0 { + dx = 0x4000 + } else if opcode&1 != 0 { + // Counter-clockwise rotation. + dx, dy = -dy, dx + } + if i == 0 { + h.gs.dv = normalize(dx, dy) + } else { + h.gs.pv = normalize(dx, dy) + } + } + + case opGETINFO: + res := int32(0) + if h.stack[top-1]&(1<<0) != 0 { + // Set the engine version. We hard-code this to 35, the same as + // the C freetype code, which says that "Version~35 corresponds + // to MS rasterizer v.1.7 as used e.g. in Windows~98". + res |= 35 + } + if h.stack[top-1]&(1<<5) != 0 { + // Set that we support grayscale. + res |= 1 << 12 + } + // We set no other bits, as we do not support rotated or stretched glyphs. + h.stack[top-1] = res + + case opIDEF: + // IDEF is for ancient versions of the bytecode interpreter, and is no longer used. + return errors.New("truetype: hinting: unsupported IDEF instruction") + + case opROLL: + h.stack[top-1], h.stack[top-3], h.stack[top-2] = + h.stack[top-3], h.stack[top-2], h.stack[top-1] + + case opMAX: + top-- + if h.stack[top-1] < h.stack[top] { + h.stack[top-1] = h.stack[top] + } + + case opMIN: + top-- + if h.stack[top-1] > h.stack[top] { + h.stack[top-1] = h.stack[top] + } + + case opSCANTYPE: + // We do not support dropout control, as we always rasterize grayscale glyphs. + top-- + + case opINSTCTRL: + // TODO: support instruction execution control? It seems rare, and even when + // nominally used (e.g. Source Sans Pro), it seems conditional on extreme or + // unusual rasterization conditions. For example, the code snippet at + // https://developer.apple.com/fonts/TTRefMan/RM05/Chap5.html#INSTCTRL + // uses INSTCTRL when grid-fitting a rotated or stretched glyph, but + // freetype-go does not support rotated or stretched glyphs. + top -= 2 + + default: + if opcode < opPUSHB000 { + return errors.New("truetype: hinting: unrecognized instruction") + } + + if opcode < opMDRP00000 { + // PUSHxxxx opcode. + + if opcode < opPUSHW000 { + opcode -= opPUSHB000 - 1 + } else { + opcode -= opPUSHW000 - 1 - 0x80 + } + goto push + } + + if opcode < opMIRP00000 { + // MDRPxxxxx opcode. + + top-- + i := h.stack[top] + ref := h.point(0, current, h.gs.rp[0]) + p := h.point(1, current, i) + if ref == nil || p == nil { + return errors.New("truetype: hinting: point out of range") + } + + oldDist := f26dot6(0) + if h.gs.zp[0] == 0 || h.gs.zp[1] == 0 { + p0 := h.point(1, unhinted, i) + p1 := h.point(0, unhinted, h.gs.rp[0]) + oldDist = dotProduct(f26dot6(p0.X-p1.X), f26dot6(p0.Y-p1.Y), h.gs.dv) + } else { + p0 := h.point(1, inFontUnits, i) + p1 := h.point(0, inFontUnits, h.gs.rp[0]) + oldDist = dotProduct(f26dot6(p0.X-p1.X), f26dot6(p0.Y-p1.Y), h.gs.dv) + oldDist = f26dot6(h.font.scale(h.scale * int32(oldDist))) + } + + // Single-width cut-in test. + if x := (oldDist - h.gs.singleWidth).abs(); x < h.gs.singleWidthCutIn { + if oldDist >= 0 { + oldDist = +h.gs.singleWidth + } else { + oldDist = -h.gs.singleWidth + } + } + + // Rounding bit. + // TODO: metrics compensation. + distance := oldDist + if opcode&0x04 != 0 { + distance = h.round(oldDist) + } + + // Minimum distance bit. + if opcode&0x08 != 0 { + if oldDist >= 0 { + if distance < h.gs.minDist { + distance = h.gs.minDist + } + } else { + if distance > -h.gs.minDist { + distance = -h.gs.minDist + } + } + } + + // Set-RP0 bit. + h.gs.rp[1] = h.gs.rp[0] + h.gs.rp[2] = i + if opcode&0x10 != 0 { + h.gs.rp[0] = i + } + + // Move the point. + oldDist = dotProduct(f26dot6(p.X-ref.X), f26dot6(p.Y-ref.Y), h.gs.pv) + h.move(p, distance-oldDist, true) + + } else { + // MIRPxxxxx opcode. + + top -= 2 + i := h.stack[top] + cvtDist := h.getScaledCVT(h.stack[top+1]) + if (cvtDist - h.gs.singleWidth).abs() < h.gs.singleWidthCutIn { + if cvtDist >= 0 { + cvtDist = +h.gs.singleWidth + } else { + cvtDist = -h.gs.singleWidth + } + } + + if h.gs.zp[1] == 0 { + // TODO: implement once we have a .ttf file that triggers + // this, so that we can step through C's freetype. + return errors.New("truetype: hinting: unimplemented twilight point adjustment") + } + + ref := h.point(0, unhinted, h.gs.rp[0]) + p := h.point(1, unhinted, i) + if ref == nil || p == nil { + return errors.New("truetype: hinting: point out of range") + } + oldDist := dotProduct(f26dot6(p.X-ref.X), f26dot6(p.Y-ref.Y), h.gs.dv) + + ref = h.point(0, current, h.gs.rp[0]) + p = h.point(1, current, i) + if ref == nil || p == nil { + return errors.New("truetype: hinting: point out of range") + } + curDist := dotProduct(f26dot6(p.X-ref.X), f26dot6(p.Y-ref.Y), h.gs.pv) + + if h.gs.autoFlip && oldDist^cvtDist < 0 { + cvtDist = -cvtDist + } + + // Rounding bit. + // TODO: metrics compensation. + distance := cvtDist + if opcode&0x04 != 0 { + // The CVT value is only used if close enough to oldDist. + if (h.gs.zp[0] == h.gs.zp[1]) && + ((cvtDist - oldDist).abs() > h.gs.controlValueCutIn) { + + distance = oldDist + } + distance = h.round(distance) + } + + // Minimum distance bit. + if opcode&0x08 != 0 { + if oldDist >= 0 { + if distance < h.gs.minDist { + distance = h.gs.minDist + } + } else { + if distance > -h.gs.minDist { + distance = -h.gs.minDist + } + } + } + + // Set-RP0 bit. + h.gs.rp[1] = h.gs.rp[0] + h.gs.rp[2] = i + if opcode&0x10 != 0 { + h.gs.rp[0] = i + } + + // Move the point. + h.move(p, distance-curDist, true) + } + } + pc++ + continue + + ifelse: + // Skip past bytecode until the next ELSE (if opcode == 0) or the + // next EIF (for all opcodes). Opcode == 0 means that we have come + // from an IF. Opcode == 1 means that we have come from an ELSE. + { + ifelseloop: + for depth := 0; ; { + pc++ + if pc >= len(program) { + return errors.New("truetype: hinting: unbalanced IF or ELSE") + } + switch program[pc] { + case opIF: + depth++ + case opELSE: + if depth == 0 && opcode == 0 { + break ifelseloop + } + case opEIF: + depth-- + if depth < 0 { + break ifelseloop + } + default: + var ok bool + pc, ok = skipInstructionPayload(program, pc) + if !ok { + return errors.New("truetype: hinting: unbalanced IF or ELSE") + } + } + } + pc++ + continue + } + + push: + // Push n elements from the program to the stack, where n is the low 7 bits of + // opcode. If the low 7 bits are zero, then n is the next byte from the program. + // The high bit being 0 means that the elements are zero-extended bytes. + // The high bit being 1 means that the elements are sign-extended words. + { + width := 1 + if opcode&0x80 != 0 { + opcode &^= 0x80 + width = 2 + } + if opcode == 0 { + pc++ + if pc >= len(program) { + return errors.New("truetype: hinting: insufficient data") + } + opcode = program[pc] + } + pc++ + if top+int(opcode) > len(h.stack) { + return errors.New("truetype: hinting: stack overflow") + } + if pc+width*int(opcode) > len(program) { + return errors.New("truetype: hinting: insufficient data") + } + for ; opcode > 0; opcode-- { + if width == 1 { + h.stack[top] = int32(program[pc]) + } else { + h.stack[top] = int32(int8(program[pc]))<<8 | int32(program[pc+1]) + } + top++ + pc += width + } + continue + } + + delta: + { + if opcode >= opDELTAC1 && !h.scaledCVTInitialized { + h.initializeScaledCVT() + } + top-- + n := h.stack[top] + if int32(top) < 2*n { + return errors.New("truetype: hinting: stack underflow") + } + for ; n > 0; n-- { + top -= 2 + b := h.stack[top] + c := (b & 0xf0) >> 4 + switch opcode { + case opDELTAP2, opDELTAC2: + c += 16 + case opDELTAP3, opDELTAC3: + c += 32 + } + c += h.gs.deltaBase + if ppem := (h.scale + 1<<5) >> 6; ppem != c { + continue + } + b = (b & 0x0f) - 8 + if b >= 0 { + b++ + } + b = b * 64 / (1 << uint32(h.gs.deltaShift)) + if opcode >= opDELTAC1 { + a := h.stack[top+1] + if a < 0 || len(h.scaledCVT) <= int(a) { + return errors.New("truetype: hinting: index out of range") + } + h.scaledCVT[a] += f26dot6(b) + } else { + p := h.point(0, current, h.stack[top+1]) + if p == nil { + return errors.New("truetype: hinting: point out of range") + } + h.move(p, f26dot6(b), true) + } + } + pc++ + continue + } + } + return nil +} + +func (h *hinter) initializeScaledCVT() { + h.scaledCVTInitialized = true + if n := len(h.font.cvt) / 2; n <= cap(h.scaledCVT) { + h.scaledCVT = h.scaledCVT[:n] + } else { + if n < 32 { + n = 32 + } + h.scaledCVT = make([]f26dot6, len(h.font.cvt)/2, n) + } + for i := range h.scaledCVT { + unscaled := uint16(h.font.cvt[2*i])<<8 | uint16(h.font.cvt[2*i+1]) + h.scaledCVT[i] = f26dot6(h.font.scale(h.scale * int32(int16(unscaled)))) + } +} + +// getScaledCVT returns the scaled value from the font's Control Value Table. +func (h *hinter) getScaledCVT(i int32) f26dot6 { + if !h.scaledCVTInitialized { + h.initializeScaledCVT() + } + if i < 0 || len(h.scaledCVT) <= int(i) { + return 0 + } + return h.scaledCVT[i] +} + +// setScaledCVT overrides the scaled value from the font's Control Value Table. +func (h *hinter) setScaledCVT(i int32, v f26dot6) { + if !h.scaledCVTInitialized { + h.initializeScaledCVT() + } + if i < 0 || len(h.scaledCVT) <= int(i) { + return + } + h.scaledCVT[i] = v +} + +func (h *hinter) point(zonePointer uint32, pt pointType, i int32) *Point { + points := h.points[h.gs.zp[zonePointer]][pt] + if i < 0 || len(points) <= int(i) { + return nil + } + return &points[i] +} + +func (h *hinter) move(p *Point, distance f26dot6, touch bool) { + fvx := int64(h.gs.fv[0]) + pvx := int64(h.gs.pv[0]) + if fvx == 0x4000 && pvx == 0x4000 { + p.X += int32(distance) + if touch { + p.Flags |= flagTouchedX + } + return + } + + fvy := int64(h.gs.fv[1]) + pvy := int64(h.gs.pv[1]) + if fvy == 0x4000 && pvy == 0x4000 { + p.Y += int32(distance) + if touch { + p.Flags |= flagTouchedY + } + return + } + + fvDotPv := (fvx*pvx + fvy*pvy) >> 14 + + if fvx != 0 { + p.X += int32(mulDiv(fvx, int64(distance), fvDotPv)) + if touch { + p.Flags |= flagTouchedX + } + } + + if fvy != 0 { + p.Y += int32(mulDiv(fvy, int64(distance), fvDotPv)) + if touch { + p.Flags |= flagTouchedY + } + } +} + +func (h *hinter) iupInterp(interpY bool, p1, p2, ref1, ref2 int) { + if p1 > p2 { + return + } + if ref1 >= len(h.points[glyphZone][current]) || + ref2 >= len(h.points[glyphZone][current]) { + return + } + + var ifu1, ifu2 int32 + if interpY { + ifu1 = h.points[glyphZone][inFontUnits][ref1].Y + ifu2 = h.points[glyphZone][inFontUnits][ref2].Y + } else { + ifu1 = h.points[glyphZone][inFontUnits][ref1].X + ifu2 = h.points[glyphZone][inFontUnits][ref2].X + } + if ifu1 > ifu2 { + ifu1, ifu2 = ifu2, ifu1 + ref1, ref2 = ref2, ref1 + } + + var unh1, unh2, delta1, delta2 int32 + if interpY { + unh1 = h.points[glyphZone][unhinted][ref1].Y + unh2 = h.points[glyphZone][unhinted][ref2].Y + delta1 = h.points[glyphZone][current][ref1].Y - unh1 + delta2 = h.points[glyphZone][current][ref2].Y - unh2 + } else { + unh1 = h.points[glyphZone][unhinted][ref1].X + unh2 = h.points[glyphZone][unhinted][ref2].X + delta1 = h.points[glyphZone][current][ref1].X - unh1 + delta2 = h.points[glyphZone][current][ref2].X - unh2 + } + + var xy, ifuXY int32 + if ifu1 == ifu2 { + for i := p1; i <= p2; i++ { + if interpY { + xy = h.points[glyphZone][unhinted][i].Y + } else { + xy = h.points[glyphZone][unhinted][i].X + } + + if xy <= unh1 { + xy += delta1 + } else { + xy += delta2 + } + + if interpY { + h.points[glyphZone][current][i].Y = xy + } else { + h.points[glyphZone][current][i].X = xy + } + } + return + } + + scale, scaleOK := int64(0), false + for i := p1; i <= p2; i++ { + if interpY { + xy = h.points[glyphZone][unhinted][i].Y + ifuXY = h.points[glyphZone][inFontUnits][i].Y + } else { + xy = h.points[glyphZone][unhinted][i].X + ifuXY = h.points[glyphZone][inFontUnits][i].X + } + + if xy <= unh1 { + xy += delta1 + } else if xy >= unh2 { + xy += delta2 + } else { + if !scaleOK { + scaleOK = true + scale = mulDiv(int64(unh2+delta2-unh1-delta1), 0x10000, int64(ifu2-ifu1)) + } + numer := int64(ifuXY-ifu1) * scale + if numer >= 0 { + numer += 0x8000 + } else { + numer -= 0x8000 + } + xy = unh1 + delta1 + int32(numer/0x10000) + } + + if interpY { + h.points[glyphZone][current][i].Y = xy + } else { + h.points[glyphZone][current][i].X = xy + } + } +} + +func (h *hinter) iupShift(interpY bool, p1, p2, p int) { + var delta int32 + if interpY { + delta = h.points[glyphZone][current][p].Y - h.points[glyphZone][unhinted][p].Y + } else { + delta = h.points[glyphZone][current][p].X - h.points[glyphZone][unhinted][p].X + } + if delta == 0 { + return + } + for i := p1; i < p2; i++ { + if i == p { + continue + } + if interpY { + h.points[glyphZone][current][i].Y += delta + } else { + h.points[glyphZone][current][i].X += delta + } + } +} + +func (h *hinter) displacement(useZP1 bool) (zonePointer uint32, i int32, d f26dot6, ok bool) { + zonePointer, i = uint32(0), h.gs.rp[1] + if useZP1 { + zonePointer, i = 1, h.gs.rp[2] + } + p := h.point(zonePointer, current, i) + q := h.point(zonePointer, unhinted, i) + if p == nil || q == nil { + return 0, 0, 0, false + } + d = dotProduct(f26dot6(p.X-q.X), f26dot6(p.Y-q.Y), h.gs.pv) + return zonePointer, i, d, true +} + +// skipInstructionPayload increments pc by the extra data that follows a +// variable length PUSHB or PUSHW instruction. +func skipInstructionPayload(program []byte, pc int) (newPC int, ok bool) { + switch program[pc] { + case opNPUSHB: + pc++ + if pc >= len(program) { + return 0, false + } + pc += int(program[pc]) + case opNPUSHW: + pc++ + if pc >= len(program) { + return 0, false + } + pc += 2 * int(program[pc]) + case opPUSHB000, opPUSHB001, opPUSHB010, opPUSHB011, + opPUSHB100, opPUSHB101, opPUSHB110, opPUSHB111: + pc += int(program[pc] - (opPUSHB000 - 1)) + case opPUSHW000, opPUSHW001, opPUSHW010, opPUSHW011, + opPUSHW100, opPUSHW101, opPUSHW110, opPUSHW111: + pc += 2 * int(program[pc]-(opPUSHW000-1)) + } + return pc, true +} + +// f2dot14 is a 2.14 fixed point number. +type f2dot14 int16 + +func normalize(x, y f2dot14) [2]f2dot14 { + fx, fy := float64(x), float64(y) + l := 0x4000 / math.Hypot(fx, fy) + fx *= l + if fx >= 0 { + fx += 0.5 + } else { + fx -= 0.5 + } + fy *= l + if fy >= 0 { + fy += 0.5 + } else { + fy -= 0.5 + } + return [2]f2dot14{f2dot14(fx), f2dot14(fy)} +} + +// f26dot6 is a 26.6 fixed point number. +type f26dot6 int32 + +// abs returns abs(x) in 26.6 fixed point arithmetic. +func (x f26dot6) abs() f26dot6 { + if x < 0 { + return -x + } + return x +} + +// div returns x/y in 26.6 fixed point arithmetic. +func (x f26dot6) div(y f26dot6) f26dot6 { + return f26dot6((int64(x) << 6) / int64(y)) +} + +// mul returns x*y in 26.6 fixed point arithmetic. +func (x f26dot6) mul(y f26dot6) f26dot6 { + return f26dot6((int64(x)*int64(y) + 1<<5) >> 6) +} + +// dotProduct returns the dot product of [x, y] and q. It is almost the same as +// px := int64(x) +// py := int64(y) +// qx := int64(q[0]) +// qy := int64(q[1]) +// return f26dot6((px*qx + py*qy + 1<<13) >> 14) +// except that the computation is done with 32-bit integers to produce exactly +// the same rounding behavior as C Freetype. +func dotProduct(x, y f26dot6, q [2]f2dot14) f26dot6 { + // Compute x*q[0] as 64-bit value. + l := uint32((int32(x) & 0xFFFF) * int32(q[0])) + m := (int32(x) >> 16) * int32(q[0]) + + lo1 := l + (uint32(m) << 16) + hi1 := (m >> 16) + (int32(l) >> 31) + bool2int32(lo1 < l) + + // Compute y*q[1] as 64-bit value. + l = uint32((int32(y) & 0xFFFF) * int32(q[1])) + m = (int32(y) >> 16) * int32(q[1]) + + lo2 := l + (uint32(m) << 16) + hi2 := (m >> 16) + (int32(l) >> 31) + bool2int32(lo2 < l) + + // Add them. + lo := lo1 + lo2 + hi := hi1 + hi2 + bool2int32(lo < lo1) + + // Divide the result by 2^14 with rounding. + s := hi >> 31 + l = lo + uint32(s) + hi += s + bool2int32(l < lo) + lo = l + + l = lo + 0x2000 + hi += bool2int32(l < lo) + + return f26dot6((uint32(hi) << 18) | (l >> 14)) +} + +// mulDiv returns x*y/z, rounded to the nearest integer. +func mulDiv(x, y, z int64) int64 { + xy := x * y + if z < 0 { + xy, z = -xy, -z + } + if xy >= 0 { + xy += z / 2 + } else { + xy -= z / 2 + } + return xy / z +} + +// round rounds the given number. The rounding algorithm is described at +// https://developer.apple.com/fonts/TTRefMan/RM02/Chap2.html#rounding +func (h *hinter) round(x f26dot6) f26dot6 { + if h.gs.roundPeriod == 0 { + // Rounding is off. + return x + } + if x >= 0 { + ret := x - h.gs.roundPhase + h.gs.roundThreshold + if h.gs.roundSuper45 { + ret /= h.gs.roundPeriod + ret *= h.gs.roundPeriod + } else { + ret &= -h.gs.roundPeriod + } + if x != 0 && ret < 0 { + ret = 0 + } + return ret + h.gs.roundPhase + } + ret := -x - h.gs.roundPhase + h.gs.roundThreshold + if h.gs.roundSuper45 { + ret /= h.gs.roundPeriod + ret *= h.gs.roundPeriod + } else { + ret &= -h.gs.roundPeriod + } + if ret < 0 { + ret = 0 + } + return -ret - h.gs.roundPhase +} + +func bool2int32(b bool) int32 { + if b { + return 1 + } + return 0 +} diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/hint_test.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/hint_test.go new file mode 100644 index 000000000..c8b8d604d --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/hint_test.go @@ -0,0 +1,673 @@ +// Copyright 2012 The Freetype-Go Authors. All rights reserved. +// Use of this source code is governed by your choice of either the +// FreeType License or the GNU General Public License version 2 (or +// any later version), both of which can be found in the LICENSE file. + +package truetype + +import ( + "reflect" + "strings" + "testing" +) + +func TestBytecode(t *testing.T) { + testCases := []struct { + desc string + prog []byte + want []int32 + errStr string + }{ + { + "underflow", + []byte{ + opDUP, + }, + nil, + "underflow", + }, + { + "infinite loop", + []byte{ + opPUSHW000, // [-1] + 0xff, + 0xff, + opDUP, // [-1, -1] + opJMPR, // [-1] + }, + nil, + "too many steps", + }, + { + "unbalanced if/else", + []byte{ + opPUSHB000, // [0] + 0, + opIF, + }, + nil, + "unbalanced", + }, + { + "vector set/gets", + []byte{ + opSVTCA1, // [] + opGPV, // [0x4000, 0] + opSVTCA0, // [0x4000, 0] + opGFV, // [0x4000, 0, 0, 0x4000] + opNEG, // [0x4000, 0, 0, -0x4000] + opSPVFS, // [0x4000, 0] + opSFVTPV, // [0x4000, 0] + opPUSHB000, // [0x4000, 0, 1] + 1, + opGFV, // [0x4000, 0, 1, 0, -0x4000] + opPUSHB000, // [0x4000, 0, 1, 0, -0x4000, 2] + 2, + }, + []int32{0x4000, 0, 1, 0, -0x4000, 2}, + "", + }, + { + "jumps", + []byte{ + opPUSHB001, // [10, 2] + 10, + 2, + opJMPR, // [10] + opDUP, // not executed + opDUP, // [10, 10] + opPUSHB010, // [10, 10, 20, 2, 1] + 20, + 2, + 1, + opJROT, // [10, 10, 20] + opDUP, // not executed + opDUP, // [10, 10, 20, 20] + opPUSHB010, // [10, 10, 20, 20, 30, 2, 1] + 30, + 2, + 1, + opJROF, // [10, 10, 20, 20, 30] + opDUP, // [10, 10, 20, 20, 30, 30] + opDUP, // [10, 10, 20, 20, 30, 30, 30] + }, + []int32{10, 10, 20, 20, 30, 30, 30}, + "", + }, + { + "stack ops", + []byte{ + opPUSHB010, // [10, 20, 30] + 10, + 20, + 30, + opCLEAR, // [] + opPUSHB010, // [40, 50, 60] + 40, + 50, + 60, + opSWAP, // [40, 60, 50] + opDUP, // [40, 60, 50, 50] + opDUP, // [40, 60, 50, 50, 50] + opPOP, // [40, 60, 50, 50] + opDEPTH, // [40, 60, 50, 50, 4] + opCINDEX, // [40, 60, 50, 50, 40] + opPUSHB000, // [40, 60, 50, 50, 40, 4] + 4, + opMINDEX, // [40, 50, 50, 40, 60] + }, + []int32{40, 50, 50, 40, 60}, + "", + }, + { + "push ops", + []byte{ + opPUSHB000, // [255] + 255, + opPUSHW001, // [255, -2, 253] + 255, + 254, + 0, + 253, + opNPUSHB, // [1, -2, 253, 1, 2] + 2, + 1, + 2, + opNPUSHW, // [1, -2, 253, 1, 2, 0x0405, 0x0607, 0x0809] + 3, + 4, + 5, + 6, + 7, + 8, + 9, + }, + []int32{255, -2, 253, 1, 2, 0x0405, 0x0607, 0x0809}, + "", + }, + { + "store ops", + []byte{ + opPUSHB011, // [1, 22, 3, 44] + 1, + 22, + 3, + 44, + opWS, // [1, 22] + opWS, // [] + opPUSHB000, // [3] + 3, + opRS, // [44] + }, + []int32{44}, + "", + }, + { + "comparison ops", + []byte{ + opPUSHB001, // [10, 20] + 10, + 20, + opLT, // [1] + opPUSHB001, // [1, 10, 20] + 10, + 20, + opLTEQ, // [1, 1] + opPUSHB001, // [1, 1, 10, 20] + 10, + 20, + opGT, // [1, 1, 0] + opPUSHB001, // [1, 1, 0, 10, 20] + 10, + 20, + opGTEQ, // [1, 1, 0, 0] + opEQ, // [1, 1, 1] + opNEQ, // [1, 0] + }, + []int32{1, 0}, + "", + }, + { + "odd/even", + // Calculate odd(2+31/64), odd(2+32/64), even(2), even(1). + []byte{ + opPUSHB000, // [159] + 159, + opODD, // [0] + opPUSHB000, // [0, 160] + 160, + opODD, // [0, 1] + opPUSHB000, // [0, 1, 128] + 128, + opEVEN, // [0, 1, 1] + opPUSHB000, // [0, 1, 1, 64] + 64, + opEVEN, // [0, 1, 1, 0] + }, + []int32{0, 1, 1, 0}, + "", + }, + { + "if true", + []byte{ + opPUSHB001, // [255, 1] + 255, + 1, + opIF, + opPUSHB000, // [255, 2] + 2, + opEIF, + opPUSHB000, // [255, 2, 254] + 254, + }, + []int32{255, 2, 254}, + "", + }, + { + "if false", + []byte{ + opPUSHB001, // [255, 0] + 255, + 0, + opIF, + opPUSHB000, // [255] + 2, + opEIF, + opPUSHB000, // [255, 254] + 254, + }, + []int32{255, 254}, + "", + }, + { + "if/else true", + []byte{ + opPUSHB000, // [1] + 1, + opIF, + opPUSHB000, // [2] + 2, + opELSE, + opPUSHB000, // not executed + 3, + opEIF, + }, + []int32{2}, + "", + }, + { + "if/else false", + []byte{ + opPUSHB000, // [0] + 0, + opIF, + opPUSHB000, // not executed + 2, + opELSE, + opPUSHB000, // [3] + 3, + opEIF, + }, + []int32{3}, + "", + }, + { + "if/else true if/else false", + // 0x58 is the opcode for opIF. The literal 0x58s below are pushed data. + []byte{ + opPUSHB010, // [255, 0, 1] + 255, + 0, + 1, + opIF, + opIF, + opPUSHB001, // not executed + 0x58, + 0x58, + opELSE, + opPUSHW000, // [255, 0x5858] + 0x58, + 0x58, + opEIF, + opELSE, + opIF, + opNPUSHB, // not executed + 3, + 0x58, + 0x58, + 0x58, + opELSE, + opNPUSHW, // not executed + 2, + 0x58, + 0x58, + 0x58, + 0x58, + opEIF, + opEIF, + opPUSHB000, // [255, 0x5858, 254] + 254, + }, + []int32{255, 0x5858, 254}, + "", + }, + { + "if/else false if/else true", + // 0x58 is the opcode for opIF. The literal 0x58s below are pushed data. + []byte{ + opPUSHB010, // [255, 1, 0] + 255, + 1, + 0, + opIF, + opIF, + opPUSHB001, // not executed + 0x58, + 0x58, + opELSE, + opPUSHW000, // not executed + 0x58, + 0x58, + opEIF, + opELSE, + opIF, + opNPUSHB, // [255, 0x58, 0x58, 0x58] + 3, + 0x58, + 0x58, + 0x58, + opELSE, + opNPUSHW, // not executed + 2, + 0x58, + 0x58, + 0x58, + 0x58, + opEIF, + opEIF, + opPUSHB000, // [255, 0x58, 0x58, 0x58, 254] + 254, + }, + []int32{255, 0x58, 0x58, 0x58, 254}, + "", + }, + { + "logical ops", + []byte{ + opPUSHB010, // [0, 10, 20] + 0, + 10, + 20, + opAND, // [0, 1] + opOR, // [1] + opNOT, // [0] + }, + []int32{0}, + "", + }, + { + "arithmetic ops", + // Calculate abs((-(1 - (2*3)))/2 + 1/64). + // The answer is 5/2 + 1/64 in ideal numbers, or 161 in 26.6 fixed point math. + []byte{ + opPUSHB010, // [64, 128, 192] + 1 << 6, + 2 << 6, + 3 << 6, + opMUL, // [64, 384] + opSUB, // [-320] + opNEG, // [320] + opPUSHB000, // [320, 128] + 2 << 6, + opDIV, // [160] + opPUSHB000, // [160, 1] + 1, + opADD, // [161] + opABS, // [161] + }, + []int32{161}, + "", + }, + { + "floor, ceiling", + []byte{ + opPUSHB000, // [96] + 96, + opFLOOR, // [64] + opPUSHB000, // [64, 96] + 96, + opCEILING, // [64, 128] + }, + []int32{64, 128}, + "", + }, + { + "rounding", + // Round 1.40625 (which is 90/64) under various rounding policies. + // See figure 20 of https://developer.apple.com/fonts/TTRefMan/RM02/Chap2.html#rounding + []byte{ + opROFF, // [] + opPUSHB000, // [90] + 90, + opROUND00, // [90] + opRTG, // [90] + opPUSHB000, // [90, 90] + 90, + opROUND00, // [90, 64] + opRTHG, // [90, 64] + opPUSHB000, // [90, 64, 90] + 90, + opROUND00, // [90, 64, 96] + opRDTG, // [90, 64, 96] + opPUSHB000, // [90, 64, 96, 90] + 90, + opROUND00, // [90, 64, 96, 64] + opRUTG, // [90, 64, 96, 64] + opPUSHB000, // [90, 64, 96, 64, 90] + 90, + opROUND00, // [90, 64, 96, 64, 128] + opRTDG, // [90, 64, 96, 64, 128] + opPUSHB000, // [90, 64, 96, 64, 128, 90] + 90, + opROUND00, // [90, 64, 96, 64, 128, 96] + }, + []int32{90, 64, 96, 64, 128, 96}, + "", + }, + { + "super-rounding", + // See figure 20 of https://developer.apple.com/fonts/TTRefMan/RM02/Chap2.html#rounding + // and the sign preservation steps of the "Order of rounding operations" section. + []byte{ + opPUSHB000, // [0x58] + 0x58, + opSROUND, // [] + opPUSHW000, // [-81] + 0xff, + 0xaf, + opROUND00, // [-80] + opPUSHW000, // [-80, -80] + 0xff, + 0xb0, + opROUND00, // [-80, -80] + opPUSHW000, // [-80, -80, -17] + 0xff, + 0xef, + opROUND00, // [-80, -80, -16] + opPUSHW000, // [-80, -80, -16, -16] + 0xff, + 0xf0, + opROUND00, // [-80, -80, -16, -16] + opPUSHB000, // [-80, -80, -16, -16, 0] + 0, + opROUND00, // [-80, -80, -16, -16, 16] + opPUSHB000, // [-80, -80, -16, -16, 16, 16] + 16, + opROUND00, // [-80, -80, -16, -16, 16, 16] + opPUSHB000, // [-80, -80, -16, -16, 16, 16, 47] + 47, + opROUND00, // [-80, -80, -16, -16, 16, 16, 16] + opPUSHB000, // [-80, -80, -16, -16, 16, 16, 16, 48] + 48, + opROUND00, // [-80, -80, -16, -16, 16, 16, 16, 80] + }, + []int32{-80, -80, -16, -16, 16, 16, 16, 80}, + "", + }, + { + "roll", + []byte{ + opPUSHB010, // [1, 2, 3] + 1, + 2, + 3, + opROLL, // [2, 3, 1] + }, + []int32{2, 3, 1}, + "", + }, + { + "max/min", + []byte{ + opPUSHW001, // [-2, -3] + 0xff, + 0xfe, + 0xff, + 0xfd, + opMAX, // [-2] + opPUSHW001, // [-2, -4, -5] + 0xff, + 0xfc, + 0xff, + 0xfb, + opMIN, // [-2, -5] + }, + []int32{-2, -5}, + "", + }, + { + "functions", + []byte{ + opPUSHB011, // [3, 7, 0, 3] + 3, + 7, + 0, + 3, + + opFDEF, // Function #3 (not called) + opPUSHB000, + 98, + opENDF, + + opFDEF, // Function #0 + opDUP, + opADD, + opENDF, + + opFDEF, // Function #7 + opPUSHB001, + 10, + 0, + opCALL, + opDUP, + opENDF, + + opFDEF, // Function #3 (again) + opPUSHB000, + 99, + opENDF, + + opPUSHB001, // [2, 0] + 2, + 0, + opCALL, // [4] + opPUSHB000, // [4, 3] + 3, + opLOOPCALL, // [99, 99, 99, 99] + opPUSHB000, // [99, 99, 99, 99, 7] + 7, + opCALL, // [99, 99, 99, 99, 20, 20] + }, + []int32{99, 99, 99, 99, 20, 20}, + "", + }, + } + + for _, tc := range testCases { + h := &hinter{} + h.init(&Font{ + maxStorage: 32, + maxStackElements: 100, + }, 768) + err, errStr := h.run(tc.prog, nil, nil, nil, nil), "" + if err != nil { + errStr = err.Error() + } + if tc.errStr != "" { + if errStr == "" { + t.Errorf("%s: got no error, want %q", tc.desc, tc.errStr) + } else if !strings.Contains(errStr, tc.errStr) { + t.Errorf("%s: got error %q, want one containing %q", tc.desc, errStr, tc.errStr) + } + continue + } + if errStr != "" { + t.Errorf("%s: got error %q, want none", tc.desc, errStr) + continue + } + got := h.stack[:len(tc.want)] + if !reflect.DeepEqual(got, tc.want) { + t.Errorf("%s: got %v, want %v", tc.desc, got, tc.want) + continue + } + } +} + +// TestMove tests that the hinter.move method matches the output of the C +// Freetype implementation. +func TestMove(t *testing.T) { + h, p := hinter{}, Point{} + testCases := []struct { + pvX, pvY, fvX, fvY f2dot14 + wantX, wantY int32 + }{ + {+0x4000, +0x0000, +0x4000, +0x0000, +1000, +0}, + {+0x4000, +0x0000, -0x4000, +0x0000, +1000, +0}, + {-0x4000, +0x0000, +0x4000, +0x0000, -1000, +0}, + {-0x4000, +0x0000, -0x4000, +0x0000, -1000, +0}, + {+0x0000, +0x4000, +0x0000, +0x4000, +0, +1000}, + {+0x0000, +0x4000, +0x0000, -0x4000, +0, +1000}, + {+0x4000, +0x0000, +0x2d41, +0x2d41, +1000, +1000}, + {+0x4000, +0x0000, -0x2d41, +0x2d41, +1000, -1000}, + {+0x4000, +0x0000, +0x2d41, -0x2d41, +1000, -1000}, + {+0x4000, +0x0000, -0x2d41, -0x2d41, +1000, +1000}, + {-0x4000, +0x0000, +0x2d41, +0x2d41, -1000, -1000}, + {-0x4000, +0x0000, -0x2d41, +0x2d41, -1000, +1000}, + {-0x4000, +0x0000, +0x2d41, -0x2d41, -1000, +1000}, + {-0x4000, +0x0000, -0x2d41, -0x2d41, -1000, -1000}, + {+0x376d, +0x2000, +0x2d41, +0x2d41, +732, +732}, + {-0x376d, +0x2000, +0x2d41, +0x2d41, -2732, -2732}, + {+0x376d, +0x2000, +0x2d41, -0x2d41, +2732, -2732}, + {-0x376d, +0x2000, +0x2d41, -0x2d41, -732, +732}, + {-0x376d, -0x2000, +0x2d41, +0x2d41, -732, -732}, + {+0x376d, +0x2000, +0x4000, +0x0000, +1155, +0}, + {+0x376d, +0x2000, +0x0000, +0x4000, +0, +2000}, + } + for _, tc := range testCases { + p = Point{} + h.gs.pv = [2]f2dot14{tc.pvX, tc.pvY} + h.gs.fv = [2]f2dot14{tc.fvX, tc.fvY} + h.move(&p, 1000, true) + tx := p.Flags&flagTouchedX != 0 + ty := p.Flags&flagTouchedY != 0 + wantTX := tc.fvX != 0 + wantTY := tc.fvY != 0 + if p.X != tc.wantX || p.Y != tc.wantY || tx != wantTX || ty != wantTY { + t.Errorf("pv=%v, fv=%v\ngot %d, %d, %t, %t\nwant %d, %d, %t, %t", + h.gs.pv, h.gs.fv, p.X, p.Y, tx, ty, tc.wantX, tc.wantY, wantTX, wantTY) + continue + } + + // Check that p is aligned with the freedom vector. + a := int64(p.X) * int64(tc.fvY) + b := int64(p.Y) * int64(tc.fvX) + if a != b { + t.Errorf("pv=%v, fv=%v, p=%v not aligned with fv", h.gs.pv, h.gs.fv, p) + continue + } + + // Check that the projected p is 1000 away from the origin. + dotProd := (int64(p.X)*int64(tc.pvX) + int64(p.Y)*int64(tc.pvY) + 1<<13) >> 14 + if dotProd != 1000 { + t.Errorf("pv=%v, fv=%v, p=%v not 1000 from origin", h.gs.pv, h.gs.fv, p) + continue + } + } +} + +// TestNormalize tests that the normalize function matches the output of the C +// Freetype implementation. +func TestNormalize(t *testing.T) { + testCases := [][2]f2dot14{ + {-15895, 3974}, + {-15543, 5181}, + {-14654, 7327}, + {-11585, 11585}, + {0, 16384}, + {11585, 11585}, + {14654, 7327}, + {15543, 5181}, + {15895, 3974}, + {16066, 3213}, + {16161, 2694}, + {16219, 2317}, + {16257, 2032}, + {16284, 1809}, + } + for i, want := range testCases { + got := normalize(f2dot14(i)-4, 1) + if got != want { + t.Errorf("i=%d: got %v, want %v", i, got, want) + } + } +} diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/opcodes.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/opcodes.go new file mode 100644 index 000000000..1880e1e63 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/opcodes.go @@ -0,0 +1,289 @@ +// Copyright 2012 The Freetype-Go Authors. All rights reserved. +// Use of this source code is governed by your choice of either the +// FreeType License or the GNU General Public License version 2 (or +// any later version), both of which can be found in the LICENSE file. + +package truetype + +// The Truetype opcodes are summarized at +// https://developer.apple.com/fonts/TTRefMan/RM07/appendixA.html + +const ( + opSVTCA0 = 0x00 // Set freedom and projection Vectors To Coordinate Axis + opSVTCA1 = 0x01 // . + opSPVTCA0 = 0x02 // Set Projection Vector To Coordinate Axis + opSPVTCA1 = 0x03 // . + opSFVTCA0 = 0x04 // Set Freedom Vector to Coordinate Axis + opSFVTCA1 = 0x05 // . + opSPVTL0 = 0x06 // Set Projection Vector To Line + opSPVTL1 = 0x07 // . + opSFVTL0 = 0x08 // Set Freedom Vector To Line + opSFVTL1 = 0x09 // . + opSPVFS = 0x0a // Set Projection Vector From Stack + opSFVFS = 0x0b // Set Freedom Vector From Stack + opGPV = 0x0c // Get Projection Vector + opGFV = 0x0d // Get Freedom Vector + opSFVTPV = 0x0e // Set Freedom Vector To Projection Vector + opISECT = 0x0f // moves point p to the InterSECTion of two lines + opSRP0 = 0x10 // Set Reference Point 0 + opSRP1 = 0x11 // Set Reference Point 1 + opSRP2 = 0x12 // Set Reference Point 2 + opSZP0 = 0x13 // Set Zone Pointer 0 + opSZP1 = 0x14 // Set Zone Pointer 1 + opSZP2 = 0x15 // Set Zone Pointer 2 + opSZPS = 0x16 // Set Zone PointerS + opSLOOP = 0x17 // Set LOOP variable + opRTG = 0x18 // Round To Grid + opRTHG = 0x19 // Round To Half Grid + opSMD = 0x1a // Set Minimum Distance + opELSE = 0x1b // ELSE clause + opJMPR = 0x1c // JuMP Relative + opSCVTCI = 0x1d // Set Control Value Table Cut-In + opSSWCI = 0x1e // Set Single Width Cut-In + opSSW = 0x1f // Set Single Width + opDUP = 0x20 // DUPlicate top stack element + opPOP = 0x21 // POP top stack element + opCLEAR = 0x22 // CLEAR the stack + opSWAP = 0x23 // SWAP the top two elements on the stack + opDEPTH = 0x24 // DEPTH of the stack + opCINDEX = 0x25 // Copy the INDEXed element to the top of the stack + opMINDEX = 0x26 // Move the INDEXed element to the top of the stack + opALIGNPTS = 0x27 // ALIGN PoinTS + op_0x28 = 0x28 // deprecated + opUTP = 0x29 // UnTouch Point + opLOOPCALL = 0x2a // LOOP and CALL function + opCALL = 0x2b // CALL function + opFDEF = 0x2c // Function DEFinition + opENDF = 0x2d // END Function definition + opMDAP0 = 0x2e // Move Direct Absolute Point + opMDAP1 = 0x2f // . + opIUP0 = 0x30 // Interpolate Untouched Points through the outline + opIUP1 = 0x31 // . + opSHP0 = 0x32 // SHift Point using reference point + opSHP1 = 0x33 // . + opSHC0 = 0x34 // SHift Contour using reference point + opSHC1 = 0x35 // . + opSHZ0 = 0x36 // SHift Zone using reference point + opSHZ1 = 0x37 // . + opSHPIX = 0x38 // SHift point by a PIXel amount + opIP = 0x39 // Interpolate Point + opMSIRP0 = 0x3a // Move Stack Indirect Relative Point + opMSIRP1 = 0x3b // . + opALIGNRP = 0x3c // ALIGN to Reference Point + opRTDG = 0x3d // Round To Double Grid + opMIAP0 = 0x3e // Move Indirect Absolute Point + opMIAP1 = 0x3f // . + opNPUSHB = 0x40 // PUSH N Bytes + opNPUSHW = 0x41 // PUSH N Words + opWS = 0x42 // Write Store + opRS = 0x43 // Read Store + opWCVTP = 0x44 // Write Control Value Table in Pixel units + opRCVT = 0x45 // Read Control Value Table entry + opGC0 = 0x46 // Get Coordinate projected onto the projection vector + opGC1 = 0x47 // . + opSCFS = 0x48 // Sets Coordinate From the Stack using projection vector and freedom vector + opMD0 = 0x49 // Measure Distance + opMD1 = 0x4a // . + opMPPEM = 0x4b // Measure Pixels Per EM + opMPS = 0x4c // Measure Point Size + opFLIPON = 0x4d // set the auto FLIP Boolean to ON + opFLIPOFF = 0x4e // set the auto FLIP Boolean to OFF + opDEBUG = 0x4f // DEBUG call + opLT = 0x50 // Less Than + opLTEQ = 0x51 // Less Than or EQual + opGT = 0x52 // Greater Than + opGTEQ = 0x53 // Greater Than or EQual + opEQ = 0x54 // EQual + opNEQ = 0x55 // Not EQual + opODD = 0x56 // ODD + opEVEN = 0x57 // EVEN + opIF = 0x58 // IF test + opEIF = 0x59 // End IF + opAND = 0x5a // logical AND + opOR = 0x5b // logical OR + opNOT = 0x5c // logical NOT + opDELTAP1 = 0x5d // DELTA exception P1 + opSDB = 0x5e // Set Delta Base in the graphics state + opSDS = 0x5f // Set Delta Shift in the graphics state + opADD = 0x60 // ADD + opSUB = 0x61 // SUBtract + opDIV = 0x62 // DIVide + opMUL = 0x63 // MULtiply + opABS = 0x64 // ABSolute value + opNEG = 0x65 // NEGate + opFLOOR = 0x66 // FLOOR + opCEILING = 0x67 // CEILING + opROUND00 = 0x68 // ROUND value + opROUND01 = 0x69 // . + opROUND10 = 0x6a // . + opROUND11 = 0x6b // . + opNROUND00 = 0x6c // No ROUNDing of value + opNROUND01 = 0x6d // . + opNROUND10 = 0x6e // . + opNROUND11 = 0x6f // . + opWCVTF = 0x70 // Write Control Value Table in Funits + opDELTAP2 = 0x71 // DELTA exception P2 + opDELTAP3 = 0x72 // DELTA exception P3 + opDELTAC1 = 0x73 // DELTA exception C1 + opDELTAC2 = 0x74 // DELTA exception C2 + opDELTAC3 = 0x75 // DELTA exception C3 + opSROUND = 0x76 // Super ROUND + opS45ROUND = 0x77 // Super ROUND 45 degrees + opJROT = 0x78 // Jump Relative On True + opJROF = 0x79 // Jump Relative On False + opROFF = 0x7a // Round OFF + op_0x7b = 0x7b // deprecated + opRUTG = 0x7c // Round Up To Grid + opRDTG = 0x7d // Round Down To Grid + opSANGW = 0x7e // Set ANGle Weight + opAA = 0x7f // Adjust Angle + opFLIPPT = 0x80 // FLIP PoinT + opFLIPRGON = 0x81 // FLIP RanGe ON + opFLIPRGOFF = 0x82 // FLIP RanGe OFF + op_0x83 = 0x83 // deprecated + op_0x84 = 0x84 // deprecated + opSCANCTRL = 0x85 // SCAN conversion ConTRoL + opSDPVTL0 = 0x86 // Set Dual Projection Vector To Line + opSDPVTL1 = 0x87 // . + opGETINFO = 0x88 // GET INFOrmation + opIDEF = 0x89 // Instruction DEFinition + opROLL = 0x8a // ROLL the top three stack elements + opMAX = 0x8b // MAXimum of top two stack elements + opMIN = 0x8c // MINimum of top two stack elements + opSCANTYPE = 0x8d // SCANTYPE + opINSTCTRL = 0x8e // INSTRuction execution ConTRoL + op_0x8f = 0x8f + op_0x90 = 0x90 + op_0x91 = 0x91 + op_0x92 = 0x92 + op_0x93 = 0x93 + op_0x94 = 0x94 + op_0x95 = 0x95 + op_0x96 = 0x96 + op_0x97 = 0x97 + op_0x98 = 0x98 + op_0x99 = 0x99 + op_0x9a = 0x9a + op_0x9b = 0x9b + op_0x9c = 0x9c + op_0x9d = 0x9d + op_0x9e = 0x9e + op_0x9f = 0x9f + op_0xa0 = 0xa0 + op_0xa1 = 0xa1 + op_0xa2 = 0xa2 + op_0xa3 = 0xa3 + op_0xa4 = 0xa4 + op_0xa5 = 0xa5 + op_0xa6 = 0xa6 + op_0xa7 = 0xa7 + op_0xa8 = 0xa8 + op_0xa9 = 0xa9 + op_0xaa = 0xaa + op_0xab = 0xab + op_0xac = 0xac + op_0xad = 0xad + op_0xae = 0xae + op_0xaf = 0xaf + opPUSHB000 = 0xb0 // PUSH Bytes + opPUSHB001 = 0xb1 // . + opPUSHB010 = 0xb2 // . + opPUSHB011 = 0xb3 // . + opPUSHB100 = 0xb4 // . + opPUSHB101 = 0xb5 // . + opPUSHB110 = 0xb6 // . + opPUSHB111 = 0xb7 // . + opPUSHW000 = 0xb8 // PUSH Words + opPUSHW001 = 0xb9 // . + opPUSHW010 = 0xba // . + opPUSHW011 = 0xbb // . + opPUSHW100 = 0xbc // . + opPUSHW101 = 0xbd // . + opPUSHW110 = 0xbe // . + opPUSHW111 = 0xbf // . + opMDRP00000 = 0xc0 // Move Direct Relative Point + opMDRP00001 = 0xc1 // . + opMDRP00010 = 0xc2 // . + opMDRP00011 = 0xc3 // . + opMDRP00100 = 0xc4 // . + opMDRP00101 = 0xc5 // . + opMDRP00110 = 0xc6 // . + opMDRP00111 = 0xc7 // . + opMDRP01000 = 0xc8 // . + opMDRP01001 = 0xc9 // . + opMDRP01010 = 0xca // . + opMDRP01011 = 0xcb // . + opMDRP01100 = 0xcc // . + opMDRP01101 = 0xcd // . + opMDRP01110 = 0xce // . + opMDRP01111 = 0xcf // . + opMDRP10000 = 0xd0 // . + opMDRP10001 = 0xd1 // . + opMDRP10010 = 0xd2 // . + opMDRP10011 = 0xd3 // . + opMDRP10100 = 0xd4 // . + opMDRP10101 = 0xd5 // . + opMDRP10110 = 0xd6 // . + opMDRP10111 = 0xd7 // . + opMDRP11000 = 0xd8 // . + opMDRP11001 = 0xd9 // . + opMDRP11010 = 0xda // . + opMDRP11011 = 0xdb // . + opMDRP11100 = 0xdc // . + opMDRP11101 = 0xdd // . + opMDRP11110 = 0xde // . + opMDRP11111 = 0xdf // . + opMIRP00000 = 0xe0 // Move Indirect Relative Point + opMIRP00001 = 0xe1 // . + opMIRP00010 = 0xe2 // . + opMIRP00011 = 0xe3 // . + opMIRP00100 = 0xe4 // . + opMIRP00101 = 0xe5 // . + opMIRP00110 = 0xe6 // . + opMIRP00111 = 0xe7 // . + opMIRP01000 = 0xe8 // . + opMIRP01001 = 0xe9 // . + opMIRP01010 = 0xea // . + opMIRP01011 = 0xeb // . + opMIRP01100 = 0xec // . + opMIRP01101 = 0xed // . + opMIRP01110 = 0xee // . + opMIRP01111 = 0xef // . + opMIRP10000 = 0xf0 // . + opMIRP10001 = 0xf1 // . + opMIRP10010 = 0xf2 // . + opMIRP10011 = 0xf3 // . + opMIRP10100 = 0xf4 // . + opMIRP10101 = 0xf5 // . + opMIRP10110 = 0xf6 // . + opMIRP10111 = 0xf7 // . + opMIRP11000 = 0xf8 // . + opMIRP11001 = 0xf9 // . + opMIRP11010 = 0xfa // . + opMIRP11011 = 0xfb // . + opMIRP11100 = 0xfc // . + opMIRP11101 = 0xfd // . + opMIRP11110 = 0xfe // . + opMIRP11111 = 0xff // . +) + +// popCount is the number of stack elements that each opcode pops. +var popCount = [256]uint8{ + // 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f + 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 0, 0, 0, 5, // 0x00 - 0x0f + 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, // 0x10 - 0x1f + 1, 1, 0, 2, 0, 1, 1, 2, 0, 1, 2, 1, 1, 0, 1, 1, // 0x20 - 0x2f + 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 2, 2, 0, 0, 2, 2, // 0x30 - 0x3f + 0, 0, 2, 1, 2, 1, 1, 1, 2, 2, 2, 0, 0, 0, 0, 0, // 0x40 - 0x4f + 2, 2, 2, 2, 2, 2, 1, 1, 1, 0, 2, 2, 1, 1, 1, 1, // 0x50 - 0x5f + 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 0x60 - 0x6f + 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 0, 0, 0, 0, 1, 1, // 0x70 - 0x7f + 0, 2, 2, 0, 0, 1, 2, 2, 1, 1, 3, 2, 2, 1, 2, 0, // 0x80 - 0x8f + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0x90 - 0x9f + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0xa0 - 0xaf + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 0xb0 - 0xbf + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 0xc0 - 0xcf + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 0xd0 - 0xdf + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, // 0xe0 - 0xef + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, // 0xf0 - 0xff +} diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/truetype.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/truetype.go new file mode 100644 index 000000000..96ceef547 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/truetype.go @@ -0,0 +1,554 @@ +// Copyright 2010 The Freetype-Go Authors. All rights reserved. +// Use of this source code is governed by your choice of either the +// FreeType License or the GNU General Public License version 2 (or +// any later version), both of which can be found in the LICENSE file. + +// Package truetype provides a parser for the TTF and TTC file formats. +// Those formats are documented at http://developer.apple.com/fonts/TTRefMan/ +// and http://www.microsoft.com/typography/otspec/ +// +// Some of a font's methods provide lengths or co-ordinates, e.g. bounds, font +// metrics and control points. All these methods take a scale parameter, which +// is the number of device units in 1 em. For example, if 1 em is 10 pixels and +// 1 pixel is 64 units, then scale is 640. If the device space involves pixels, +// 64 units per pixel is recommended, since that is what the bytecode hinter +// uses when snapping point co-ordinates to the pixel grid. +// +// To measure a TrueType font in ideal FUnit space, use scale equal to +// font.FUnitsPerEm(). +package truetype + +import ( + "fmt" +) + +// An Index is a Font's index of a rune. +type Index uint16 + +// A Bounds holds the co-ordinate range of one or more glyphs. +// The endpoints are inclusive. +type Bounds struct { + XMin, YMin, XMax, YMax int32 +} + +// An HMetric holds the horizontal metrics of a single glyph. +type HMetric struct { + AdvanceWidth, LeftSideBearing int32 +} + +// A VMetric holds the vertical metrics of a single glyph. +type VMetric struct { + AdvanceHeight, TopSideBearing int32 +} + +// A FormatError reports that the input is not a valid TrueType font. +type FormatError string + +func (e FormatError) Error() string { + return "freetype: invalid TrueType format: " + string(e) +} + +// An UnsupportedError reports that the input uses a valid but unimplemented +// TrueType feature. +type UnsupportedError string + +func (e UnsupportedError) Error() string { + return "freetype: unsupported TrueType feature: " + string(e) +} + +// u32 returns the big-endian uint32 at b[i:]. +func u32(b []byte, i int) uint32 { + return uint32(b[i])<<24 | uint32(b[i+1])<<16 | uint32(b[i+2])<<8 | uint32(b[i+3]) +} + +// u16 returns the big-endian uint16 at b[i:]. +func u16(b []byte, i int) uint16 { + return uint16(b[i])<<8 | uint16(b[i+1]) +} + +// readTable returns a slice of the TTF data given by a table's directory entry. +func readTable(ttf []byte, offsetLength []byte) ([]byte, error) { + offset := int(u32(offsetLength, 0)) + if offset < 0 { + return nil, FormatError(fmt.Sprintf("offset too large: %d", uint32(offset))) + } + length := int(u32(offsetLength, 4)) + if length < 0 { + return nil, FormatError(fmt.Sprintf("length too large: %d", uint32(length))) + } + end := offset + length + if end < 0 || end > len(ttf) { + return nil, FormatError(fmt.Sprintf("offset + length too large: %d", uint32(offset)+uint32(length))) + } + return ttf[offset:end], nil +} + +const ( + locaOffsetFormatUnknown int = iota + locaOffsetFormatShort + locaOffsetFormatLong +) + +// A cm holds a parsed cmap entry. +type cm struct { + start, end, delta, offset uint32 +} + +// A Font represents a Truetype font. +type Font struct { + // Tables sliced from the TTF data. The different tables are documented + // at http://developer.apple.com/fonts/TTRefMan/RM06/Chap6.html + cmap, cvt, fpgm, glyf, hdmx, head, hhea, hmtx, kern, loca, maxp, os2, prep, vmtx []byte + + cmapIndexes []byte + + // Cached values derived from the raw ttf data. + cm []cm + locaOffsetFormat int + nGlyph, nHMetric, nKern int + fUnitsPerEm int32 + bounds Bounds + // Values from the maxp section. + maxTwilightPoints, maxStorage, maxFunctionDefs, maxStackElements uint16 +} + +func (f *Font) parseCmap() error { + const ( + cmapFormat4 = 4 + cmapFormat12 = 12 + languageIndependent = 0 + + // A 32-bit encoding consists of a most-significant 16-bit Platform ID and a + // least-significant 16-bit Platform Specific ID. The magic numbers are + // specified at https://www.microsoft.com/typography/otspec/name.htm + unicodeEncoding = 0x00000003 // PID = 0 (Unicode), PSID = 3 (Unicode 2.0) + microsoftSymbolEncoding = 0x00030000 // PID = 3 (Microsoft), PSID = 0 (Symbol) + microsoftUCS2Encoding = 0x00030001 // PID = 3 (Microsoft), PSID = 1 (UCS-2) + microsoftUCS4Encoding = 0x0003000a // PID = 3 (Microsoft), PSID = 10 (UCS-4) + ) + + if len(f.cmap) < 4 { + return FormatError("cmap too short") + } + nsubtab := int(u16(f.cmap, 2)) + if len(f.cmap) < 8*nsubtab+4 { + return FormatError("cmap too short") + } + offset, found, x := 0, false, 4 + for i := 0; i < nsubtab; i++ { + // We read the 16-bit Platform ID and 16-bit Platform Specific ID as a single uint32. + // All values are big-endian. + pidPsid, o := u32(f.cmap, x), u32(f.cmap, x+4) + x += 8 + // We prefer the Unicode cmap encoding. Failing to find that, we fall + // back onto the Microsoft cmap encoding. + if pidPsid == unicodeEncoding { + offset, found = int(o), true + break + + } else if pidPsid == microsoftSymbolEncoding || + pidPsid == microsoftUCS2Encoding || + pidPsid == microsoftUCS4Encoding { + + offset, found = int(o), true + // We don't break out of the for loop, so that Unicode can override Microsoft. + } + } + if !found { + return UnsupportedError("cmap encoding") + } + if offset <= 0 || offset > len(f.cmap) { + return FormatError("bad cmap offset") + } + + cmapFormat := u16(f.cmap, offset) + switch cmapFormat { + case cmapFormat4: + language := u16(f.cmap, offset+4) + if language != languageIndependent { + return UnsupportedError(fmt.Sprintf("language: %d", language)) + } + segCountX2 := int(u16(f.cmap, offset+6)) + if segCountX2%2 == 1 { + return FormatError(fmt.Sprintf("bad segCountX2: %d", segCountX2)) + } + segCount := segCountX2 / 2 + offset += 14 + f.cm = make([]cm, segCount) + for i := 0; i < segCount; i++ { + f.cm[i].end = uint32(u16(f.cmap, offset)) + offset += 2 + } + offset += 2 + for i := 0; i < segCount; i++ { + f.cm[i].start = uint32(u16(f.cmap, offset)) + offset += 2 + } + for i := 0; i < segCount; i++ { + f.cm[i].delta = uint32(u16(f.cmap, offset)) + offset += 2 + } + for i := 0; i < segCount; i++ { + f.cm[i].offset = uint32(u16(f.cmap, offset)) + offset += 2 + } + f.cmapIndexes = f.cmap[offset:] + return nil + + case cmapFormat12: + if u16(f.cmap, offset+2) != 0 { + return FormatError(fmt.Sprintf("cmap format: % x", f.cmap[offset:offset+4])) + } + length := u32(f.cmap, offset+4) + language := u32(f.cmap, offset+8) + if language != languageIndependent { + return UnsupportedError(fmt.Sprintf("language: %d", language)) + } + nGroups := u32(f.cmap, offset+12) + if length != 12*nGroups+16 { + return FormatError("inconsistent cmap length") + } + offset += 16 + f.cm = make([]cm, nGroups) + for i := uint32(0); i < nGroups; i++ { + f.cm[i].start = u32(f.cmap, offset+0) + f.cm[i].end = u32(f.cmap, offset+4) + f.cm[i].delta = u32(f.cmap, offset+8) - f.cm[i].start + offset += 12 + } + return nil + } + return UnsupportedError(fmt.Sprintf("cmap format: %d", cmapFormat)) +} + +func (f *Font) parseHead() error { + if len(f.head) != 54 { + return FormatError(fmt.Sprintf("bad head length: %d", len(f.head))) + } + f.fUnitsPerEm = int32(u16(f.head, 18)) + f.bounds.XMin = int32(int16(u16(f.head, 36))) + f.bounds.YMin = int32(int16(u16(f.head, 38))) + f.bounds.XMax = int32(int16(u16(f.head, 40))) + f.bounds.YMax = int32(int16(u16(f.head, 42))) + switch i := u16(f.head, 50); i { + case 0: + f.locaOffsetFormat = locaOffsetFormatShort + case 1: + f.locaOffsetFormat = locaOffsetFormatLong + default: + return FormatError(fmt.Sprintf("bad indexToLocFormat: %d", i)) + } + return nil +} + +func (f *Font) parseHhea() error { + if len(f.hhea) != 36 { + return FormatError(fmt.Sprintf("bad hhea length: %d", len(f.hhea))) + } + f.nHMetric = int(u16(f.hhea, 34)) + if 4*f.nHMetric+2*(f.nGlyph-f.nHMetric) != len(f.hmtx) { + return FormatError(fmt.Sprintf("bad hmtx length: %d", len(f.hmtx))) + } + return nil +} + +func (f *Font) parseKern() error { + // Apple's TrueType documentation (http://developer.apple.com/fonts/TTRefMan/RM06/Chap6kern.html) says: + // "Previous versions of the 'kern' table defined both the version and nTables fields in the header + // as UInt16 values and not UInt32 values. Use of the older format on the Mac OS is discouraged + // (although AAT can sense an old kerning table and still make correct use of it). Microsoft + // Windows still uses the older format for the 'kern' table and will not recognize the newer one. + // Fonts targeted for the Mac OS only should use the new format; fonts targeted for both the Mac OS + // and Windows should use the old format." + // Since we expect that almost all fonts aim to be Windows-compatible, we only parse the "older" format, + // just like the C Freetype implementation. + if len(f.kern) == 0 { + if f.nKern != 0 { + return FormatError("bad kern table length") + } + return nil + } + if len(f.kern) < 18 { + return FormatError("kern data too short") + } + version, offset := u16(f.kern, 0), 2 + if version != 0 { + return UnsupportedError(fmt.Sprintf("kern version: %d", version)) + } + n, offset := u16(f.kern, offset), offset+2 + if n != 1 { + return UnsupportedError(fmt.Sprintf("kern nTables: %d", n)) + } + offset += 2 + length, offset := int(u16(f.kern, offset)), offset+2 + coverage, offset := u16(f.kern, offset), offset+2 + if coverage != 0x0001 { + // We only support horizontal kerning. + return UnsupportedError(fmt.Sprintf("kern coverage: 0x%04x", coverage)) + } + f.nKern, offset = int(u16(f.kern, offset)), offset+2 + if 6*f.nKern != length-14 { + return FormatError("bad kern table length") + } + return nil +} + +func (f *Font) parseMaxp() error { + if len(f.maxp) != 32 { + return FormatError(fmt.Sprintf("bad maxp length: %d", len(f.maxp))) + } + f.nGlyph = int(u16(f.maxp, 4)) + f.maxTwilightPoints = u16(f.maxp, 16) + f.maxStorage = u16(f.maxp, 18) + f.maxFunctionDefs = u16(f.maxp, 20) + f.maxStackElements = u16(f.maxp, 24) + return nil +} + +// scale returns x divided by f.fUnitsPerEm, rounded to the nearest integer. +func (f *Font) scale(x int32) int32 { + if x >= 0 { + x += f.fUnitsPerEm / 2 + } else { + x -= f.fUnitsPerEm / 2 + } + return x / f.fUnitsPerEm +} + +// Bounds returns the union of a Font's glyphs' bounds. +func (f *Font) Bounds(scale int32) Bounds { + b := f.bounds + b.XMin = f.scale(scale * b.XMin) + b.YMin = f.scale(scale * b.YMin) + b.XMax = f.scale(scale * b.XMax) + b.YMax = f.scale(scale * b.YMax) + return b +} + +// FUnitsPerEm returns the number of FUnits in a Font's em-square's side. +func (f *Font) FUnitsPerEm() int32 { + return f.fUnitsPerEm +} + +// Index returns a Font's index for the given rune. +func (f *Font) Index(x rune) Index { + c := uint32(x) + for i, j := 0, len(f.cm); i < j; { + h := i + (j-i)/2 + cm := &f.cm[h] + if c < cm.start { + j = h + } else if cm.end < c { + i = h + 1 + } else if cm.offset == 0 { + return Index(c + cm.delta) + } else { + offset := int(cm.offset) + 2*(h-len(f.cm)+int(c-cm.start)) + return Index(u16(f.cmapIndexes, offset)) + } + } + return 0 +} + +// unscaledHMetric returns the unscaled horizontal metrics for the glyph with +// the given index. +func (f *Font) unscaledHMetric(i Index) (h HMetric) { + j := int(i) + if j < 0 || f.nGlyph <= j { + return HMetric{} + } + if j >= f.nHMetric { + p := 4 * (f.nHMetric - 1) + return HMetric{ + AdvanceWidth: int32(u16(f.hmtx, p)), + LeftSideBearing: int32(int16(u16(f.hmtx, p+2*(j-f.nHMetric)+4))), + } + } + return HMetric{ + AdvanceWidth: int32(u16(f.hmtx, 4*j)), + LeftSideBearing: int32(int16(u16(f.hmtx, 4*j+2))), + } +} + +// HMetric returns the horizontal metrics for the glyph with the given index. +func (f *Font) HMetric(scale int32, i Index) HMetric { + h := f.unscaledHMetric(i) + h.AdvanceWidth = f.scale(scale * h.AdvanceWidth) + h.LeftSideBearing = f.scale(scale * h.LeftSideBearing) + return h +} + +// unscaledVMetric returns the unscaled vertical metrics for the glyph with +// the given index. yMax is the top of the glyph's bounding box. +func (f *Font) unscaledVMetric(i Index, yMax int32) (v VMetric) { + j := int(i) + if j < 0 || f.nGlyph <= j { + return VMetric{} + } + if 4*j+4 <= len(f.vmtx) { + return VMetric{ + AdvanceHeight: int32(u16(f.vmtx, 4*j)), + TopSideBearing: int32(int16(u16(f.vmtx, 4*j+2))), + } + } + // The OS/2 table has grown over time. + // https://developer.apple.com/fonts/TTRefMan/RM06/Chap6OS2.html + // says that it was originally 68 bytes. Optional fields, including + // the ascender and descender, are described at + // http://www.microsoft.com/typography/otspec/os2.htm + if len(f.os2) >= 72 { + sTypoAscender := int32(int16(u16(f.os2, 68))) + sTypoDescender := int32(int16(u16(f.os2, 70))) + return VMetric{ + AdvanceHeight: sTypoAscender - sTypoDescender, + TopSideBearing: sTypoAscender - yMax, + } + } + return VMetric{ + AdvanceHeight: f.fUnitsPerEm, + TopSideBearing: 0, + } +} + +// VMetric returns the vertical metrics for the glyph with the given index. +func (f *Font) VMetric(scale int32, i Index) VMetric { + // TODO: should 0 be bounds.YMax? + v := f.unscaledVMetric(i, 0) + v.AdvanceHeight = f.scale(scale * v.AdvanceHeight) + v.TopSideBearing = f.scale(scale * v.TopSideBearing) + return v +} + +// Kerning returns the kerning for the given glyph pair. +func (f *Font) Kerning(scale int32, i0, i1 Index) int32 { + if f.nKern == 0 { + return 0 + } + g := uint32(i0)<<16 | uint32(i1) + lo, hi := 0, f.nKern + for lo < hi { + i := (lo + hi) / 2 + ig := u32(f.kern, 18+6*i) + if ig < g { + lo = i + 1 + } else if ig > g { + hi = i + } else { + return f.scale(scale * int32(int16(u16(f.kern, 22+6*i)))) + } + } + return 0 +} + +// Parse returns a new Font for the given TTF or TTC data. +// +// For TrueType Collections, the first font in the collection is parsed. +func Parse(ttf []byte) (font *Font, err error) { + return parse(ttf, 0) +} + +func parse(ttf []byte, offset int) (font *Font, err error) { + if len(ttf)-offset < 12 { + err = FormatError("TTF data is too short") + return + } + originalOffset := offset + magic, offset := u32(ttf, offset), offset+4 + switch magic { + case 0x00010000: + // No-op. + case 0x74746366: // "ttcf" as a big-endian uint32. + if originalOffset != 0 { + err = FormatError("recursive TTC") + return + } + ttcVersion, offset := u32(ttf, offset), offset+4 + if ttcVersion != 0x00010000 { + // TODO: support TTC version 2.0, once I have such a .ttc file to test with. + err = FormatError("bad TTC version") + return + } + numFonts, offset := int(u32(ttf, offset)), offset+4 + if numFonts <= 0 { + err = FormatError("bad number of TTC fonts") + return + } + if len(ttf[offset:])/4 < numFonts { + err = FormatError("TTC offset table is too short") + return + } + // TODO: provide an API to select which font in a TrueType collection to return, + // not just the first one. This may require an API to parse a TTC's name tables, + // so users of this package can select the font in a TTC by name. + offset = int(u32(ttf, offset)) + if offset <= 0 || offset > len(ttf) { + err = FormatError("bad TTC offset") + return + } + return parse(ttf, offset) + default: + err = FormatError("bad TTF version") + return + } + n, offset := int(u16(ttf, offset)), offset+2 + if len(ttf) < 16*n+12 { + err = FormatError("TTF data is too short") + return + } + f := new(Font) + // Assign the table slices. + for i := 0; i < n; i++ { + x := 16*i + 12 + switch string(ttf[x : x+4]) { + case "cmap": + f.cmap, err = readTable(ttf, ttf[x+8:x+16]) + case "cvt ": + f.cvt, err = readTable(ttf, ttf[x+8:x+16]) + case "fpgm": + f.fpgm, err = readTable(ttf, ttf[x+8:x+16]) + case "glyf": + f.glyf, err = readTable(ttf, ttf[x+8:x+16]) + case "hdmx": + f.hdmx, err = readTable(ttf, ttf[x+8:x+16]) + case "head": + f.head, err = readTable(ttf, ttf[x+8:x+16]) + case "hhea": + f.hhea, err = readTable(ttf, ttf[x+8:x+16]) + case "hmtx": + f.hmtx, err = readTable(ttf, ttf[x+8:x+16]) + case "kern": + f.kern, err = readTable(ttf, ttf[x+8:x+16]) + case "loca": + f.loca, err = readTable(ttf, ttf[x+8:x+16]) + case "maxp": + f.maxp, err = readTable(ttf, ttf[x+8:x+16]) + case "OS/2": + f.os2, err = readTable(ttf, ttf[x+8:x+16]) + case "prep": + f.prep, err = readTable(ttf, ttf[x+8:x+16]) + case "vmtx": + f.vmtx, err = readTable(ttf, ttf[x+8:x+16]) + } + if err != nil { + return + } + } + // Parse and sanity-check the TTF data. + if err = f.parseHead(); err != nil { + return + } + if err = f.parseMaxp(); err != nil { + return + } + if err = f.parseCmap(); err != nil { + return + } + if err = f.parseKern(); err != nil { + return + } + if err = f.parseHhea(); err != nil { + return + } + font = f + return +} diff --git a/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/truetype_test.go b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/truetype_test.go new file mode 100644 index 000000000..9ef6ec8d2 --- /dev/null +++ b/Godeps/_workspace/src/code.google.com/p/freetype-go/freetype/truetype/truetype_test.go @@ -0,0 +1,366 @@ +// Copyright 2012 The Freetype-Go Authors. All rights reserved. +// Use of this source code is governed by your choice of either the +// FreeType License or the GNU General Public License version 2 (or +// any later version), both of which can be found in the LICENSE file. + +package truetype + +import ( + "bufio" + "fmt" + "io" + "io/ioutil" + "os" + "strconv" + "strings" + "testing" +) + +func parseTestdataFont(name string) (font *Font, testdataIsOptional bool, err error) { + b, err := ioutil.ReadFile(fmt.Sprintf("../../testdata/%s.ttf", name)) + if err != nil { + // The "x-foo" fonts are optional tests, as they are not checked + // in for copyright or file size reasons. + return nil, strings.HasPrefix(name, "x-"), fmt.Errorf("%s: ReadFile: %v", name, err) + } + font, err = Parse(b) + if err != nil { + return nil, true, fmt.Errorf("%s: Parse: %v", name, err) + } + return font, false, nil +} + +// TestParse tests that the luxisr.ttf metrics and glyphs are parsed correctly. +// The numerical values can be manually verified by examining luxisr.ttx. +func TestParse(t *testing.T) { + font, _, err := parseTestdataFont("luxisr") + if err != nil { + t.Fatal(err) + } + if got, want := font.FUnitsPerEm(), int32(2048); got != want { + t.Errorf("FUnitsPerEm: got %v, want %v", got, want) + } + fupe := font.FUnitsPerEm() + if got, want := font.Bounds(fupe), (Bounds{-441, -432, 2024, 2033}); got != want { + t.Errorf("Bounds: got %v, want %v", got, want) + } + + i0 := font.Index('A') + i1 := font.Index('V') + if i0 != 36 || i1 != 57 { + t.Fatalf("Index: i0, i1 = %d, %d, want 36, 57", i0, i1) + } + if got, want := font.HMetric(fupe, i0), (HMetric{1366, 19}); got != want { + t.Errorf("HMetric: got %v, want %v", got, want) + } + if got, want := font.VMetric(fupe, i0), (VMetric{2465, 553}); got != want { + t.Errorf("VMetric: got %v, want %v", got, want) + } + if got, want := font.Kerning(fupe, i0, i1), int32(-144); got != want { + t.Errorf("Kerning: got %v, want %v", got, want) + } + + g := NewGlyphBuf() + err = g.Load(font, fupe, i0, NoHinting) + if err != nil { + t.Fatalf("Load: %v", err) + } + g0 := &GlyphBuf{ + B: g.B, + Point: g.Point, + End: g.End, + } + g1 := &GlyphBuf{ + B: Bounds{19, 0, 1342, 1480}, + Point: []Point{ + {19, 0, 51}, + {581, 1480, 1}, + {789, 1480, 51}, + {1342, 0, 1}, + {1116, 0, 35}, + {962, 410, 3}, + {368, 410, 33}, + {214, 0, 3}, + {428, 566, 19}, + {904, 566, 33}, + {667, 1200, 3}, + }, + End: []int{8, 11}, + } + if got, want := fmt.Sprint(g0), fmt.Sprint(g1); got != want { + t.Errorf("GlyphBuf:\ngot %v\nwant %v", got, want) + } +} + +func TestIndex(t *testing.T) { + testCases := map[string]map[rune]Index{ + "luxisr": { + ' ': 3, + '!': 4, + 'A': 36, + 'V': 57, + 'É': 101, + 'fl': 193, + '\u22c5': 385, + '中': 0, + }, + + // The x-etc test cases use those versions of the .ttf files provided + // by Ubuntu 14.04. See testdata/make-other-hinting-txts.sh for details. + + "x-arial-bold": { + ' ': 3, + '+': 14, + '0': 19, + '_': 66, + 'w': 90, + '~': 97, + 'Ä': 98, + 'fl': 192, + '½': 242, + 'σ': 305, + 'λ': 540, + 'ỹ': 1275, + '\u04e9': 1319, + '中': 0, + }, + "x-deja-vu-sans-oblique": { + ' ': 3, + '*': 13, + 'Œ': 276, + 'ω': 861, + '‡': 2571, + '⊕': 3110, + 'fl': 4728, + '\ufb03': 4729, + '\ufffd': 4813, + // TODO: '\U0001f640': ???, + '中': 0, + }, + "x-droid-sans-japanese": { + ' ': 0, + '\u3000': 3, + '\u3041': 25, + '\u30fe': 201, + '\uff61': 202, + '\uff67': 208, + '\uff9e': 263, + '\uff9f': 264, + '\u4e00': 265, + '\u557e': 1000, + '\u61b6': 2024, + '\u6ede': 3177, + '\u7505': 3555, + '\u81e3': 4602, + '\u81e5': 4603, + '\u81e7': 4604, + '\u81e8': 4605, + '\u81ea': 4606, + '\u81ed': 4607, + '\u81f3': 4608, + '\u81f4': 4609, + '\u91c7': 5796, + '\u9fa0': 6620, + '\u203e': 12584, + }, + "x-times-new-roman": { + ' ': 3, + ':': 29, + 'fl': 192, + 'Ŀ': 273, + '♠': 388, + 'Ŗ': 451, + 'Σ': 520, + '\u200D': 745, + 'Ẽ': 1216, + '\u04e9': 1319, + '中': 0, + }, + } + for name, wants := range testCases { + font, testdataIsOptional, err := parseTestdataFont(name) + if err != nil { + if testdataIsOptional { + t.Log(err) + } else { + t.Fatal(err) + } + continue + } + for r, want := range wants { + if got := font.Index(r); got != want { + t.Errorf("%s: Index of %q, aka %U: got %d, want %d", name, r, r, got, want) + } + } + } +} + +type scalingTestData struct { + advanceWidth int32 + bounds Bounds + points []Point +} + +// scalingTestParse parses a line of points like +// 213 -22 -111 236 555;-22 -111 1, 178 555 1, 236 555 1, 36 -111 1 +// The line will not have a trailing "\n". +func scalingTestParse(line string) (ret scalingTestData) { + next := func(s string) (string, int32) { + t, i := "", strings.Index(s, " ") + if i != -1 { + s, t = s[:i], s[i+1:] + } + x, _ := strconv.Atoi(s) + return t, int32(x) + } + + i := strings.Index(line, ";") + prefix, line := line[:i], line[i+1:] + + prefix, ret.advanceWidth = next(prefix) + prefix, ret.bounds.XMin = next(prefix) + prefix, ret.bounds.YMin = next(prefix) + prefix, ret.bounds.XMax = next(prefix) + prefix, ret.bounds.YMax = next(prefix) + + ret.points = make([]Point, 0, 1+strings.Count(line, ",")) + for len(line) > 0 { + s := line + if i := strings.Index(line, ","); i != -1 { + s, line = line[:i], line[i+1:] + for len(line) > 0 && line[0] == ' ' { + line = line[1:] + } + } else { + line = "" + } + s, x := next(s) + s, y := next(s) + s, f := next(s) + ret.points = append(ret.points, Point{X: x, Y: y, Flags: uint32(f)}) + } + return ret +} + +// scalingTestEquals is equivalent to, but faster than, calling +// reflect.DeepEquals(a, b), and also returns the index of the first non-equal +// element. It also treats a nil []Point and an empty non-nil []Point as equal. +// a and b must have equal length. +func scalingTestEquals(a, b []Point) (index int, equals bool) { + for i, p := range a { + if p != b[i] { + return i, false + } + } + return 0, true +} + +var scalingTestCases = []struct { + name string + size int32 +}{ + {"luxisr", 12}, + {"x-arial-bold", 11}, + {"x-deja-vu-sans-oblique", 17}, + {"x-droid-sans-japanese", 9}, + {"x-times-new-roman", 13}, +} + +func testScaling(t *testing.T, h Hinting) { + for _, tc := range scalingTestCases { + font, testdataIsOptional, err := parseTestdataFont(tc.name) + if err != nil { + if testdataIsOptional { + t.Log(err) + } else { + t.Error(err) + } + continue + } + hintingStr := "sans" + if h != NoHinting { + hintingStr = "with" + } + f, err := os.Open(fmt.Sprintf( + "../../testdata/%s-%dpt-%s-hinting.txt", tc.name, tc.size, hintingStr)) + if err != nil { + t.Errorf("%s: Open: %v", tc.name, err) + continue + } + defer f.Close() + + wants := []scalingTestData{} + scanner := bufio.NewScanner(f) + if scanner.Scan() { + major, minor, patch := 0, 0, 0 + _, err := fmt.Sscanf(scanner.Text(), "freetype version %d.%d.%d", &major, &minor, &patch) + if err != nil { + t.Errorf("%s: version information: %v", tc.name, err) + } + if (major < 2) || (major == 2 && minor < 5) || (major == 2 && minor == 5 && patch < 1) { + t.Errorf("%s: need freetype version >= 2.5.1.\n"+ + "Try setting LD_LIBRARY_PATH=/path/to/freetype_built_from_src/objs/.libs/\n"+ + "and re-running testdata/make-other-hinting-txts.sh", + tc.name) + continue + } + } else { + t.Errorf("%s: no version information", tc.name) + continue + } + for scanner.Scan() { + wants = append(wants, scalingTestParse(scanner.Text())) + } + if err := scanner.Err(); err != nil && err != io.EOF { + t.Errorf("%s: Scanner: %v", tc.name, err) + continue + } + + glyphBuf := NewGlyphBuf() + for i, want := range wants { + if err = glyphBuf.Load(font, tc.size*64, Index(i), h); err != nil { + t.Errorf("%s: glyph #%d: Load: %v", tc.name, i, err) + continue + } + got := scalingTestData{ + advanceWidth: glyphBuf.AdvanceWidth, + bounds: glyphBuf.B, + points: glyphBuf.Point, + } + + if got.advanceWidth != want.advanceWidth { + t.Errorf("%s: glyph #%d advance width:\ngot %v\nwant %v", + tc.name, i, got.advanceWidth, want.advanceWidth) + continue + } + + if got.bounds != want.bounds { + t.Errorf("%s: glyph #%d bounds:\ngot %v\nwant %v", + tc.name, i, got.bounds, want.bounds) + continue + } + + for i := range got.points { + got.points[i].Flags &= 0x01 + } + if len(got.points) != len(want.points) { + t.Errorf("%s: glyph #%d:\ngot %v\nwant %v\ndifferent slice lengths: %d versus %d", + tc.name, i, got.points, want.points, len(got.points), len(want.points)) + continue + } + if j, equals := scalingTestEquals(got.points, want.points); !equals { + t.Errorf("%s: glyph #%d:\ngot %v\nwant %v\nat index %d: %v versus %v", + tc.name, i, got.points, want.points, j, got.points[j], want.points[j]) + continue + } + } + } +} + +func TestScalingSansHinting(t *testing.T) { + testScaling(t, NoHinting) +} + +func TestScalingWithHinting(t *testing.T) { + testScaling(t, FullHinting) +} |