aboutsummaryrefslogtreecommitdiff
path: root/vendor/golang.org/x/image/math
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/golang.org/x/image/math')
-rw-r--r--vendor/golang.org/x/image/math/f32/f32.go37
-rw-r--r--vendor/golang.org/x/image/math/f64/f64.go37
-rw-r--r--vendor/golang.org/x/image/math/fixed/fixed.go410
-rw-r--r--vendor/golang.org/x/image/math/fixed/fixed_test.go439
4 files changed, 923 insertions, 0 deletions
diff --git a/vendor/golang.org/x/image/math/f32/f32.go b/vendor/golang.org/x/image/math/f32/f32.go
new file mode 100644
index 0000000..4ca1eb4
--- /dev/null
+++ b/vendor/golang.org/x/image/math/f32/f32.go
@@ -0,0 +1,37 @@
+// Copyright 2015 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package f32 implements float32 vector and matrix types.
+package f32 // import "golang.org/x/image/math/f32"
+
+// Vec2 is a 2-element vector.
+type Vec2 [2]float32
+
+// Vec3 is a 3-element vector.
+type Vec3 [3]float32
+
+// Vec4 is a 4-element vector.
+type Vec4 [4]float32
+
+// Mat3 is a 3x3 matrix in row major order.
+//
+// m[3*r + c] is the element in the r'th row and c'th column.
+type Mat3 [9]float32
+
+// Mat4 is a 4x4 matrix in row major order.
+//
+// m[4*r + c] is the element in the r'th row and c'th column.
+type Mat4 [16]float32
+
+// Aff3 is a 3x3 affine transformation matrix in row major order, where the
+// bottom row is implicitly [0 0 1].
+//
+// m[3*r + c] is the element in the r'th row and c'th column.
+type Aff3 [6]float32
+
+// Aff4 is a 4x4 affine transformation matrix in row major order, where the
+// bottom row is implicitly [0 0 0 1].
+//
+// m[4*r + c] is the element in the r'th row and c'th column.
+type Aff4 [12]float32
diff --git a/vendor/golang.org/x/image/math/f64/f64.go b/vendor/golang.org/x/image/math/f64/f64.go
new file mode 100644
index 0000000..a1f7fc0
--- /dev/null
+++ b/vendor/golang.org/x/image/math/f64/f64.go
@@ -0,0 +1,37 @@
+// Copyright 2015 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package f64 implements float64 vector and matrix types.
+package f64 // import "golang.org/x/image/math/f64"
+
+// Vec2 is a 2-element vector.
+type Vec2 [2]float64
+
+// Vec3 is a 3-element vector.
+type Vec3 [3]float64
+
+// Vec4 is a 4-element vector.
+type Vec4 [4]float64
+
+// Mat3 is a 3x3 matrix in row major order.
+//
+// m[3*r + c] is the element in the r'th row and c'th column.
+type Mat3 [9]float64
+
+// Mat4 is a 4x4 matrix in row major order.
+//
+// m[4*r + c] is the element in the r'th row and c'th column.
+type Mat4 [16]float64
+
+// Aff3 is a 3x3 affine transformation matrix in row major order, where the
+// bottom row is implicitly [0 0 1].
+//
+// m[3*r + c] is the element in the r'th row and c'th column.
+type Aff3 [6]float64
+
+// Aff4 is a 4x4 affine transformation matrix in row major order, where the
+// bottom row is implicitly [0 0 0 1].
+//
+// m[4*r + c] is the element in the r'th row and c'th column.
+type Aff4 [12]float64
diff --git a/vendor/golang.org/x/image/math/fixed/fixed.go b/vendor/golang.org/x/image/math/fixed/fixed.go
new file mode 100644
index 0000000..3d91663
--- /dev/null
+++ b/vendor/golang.org/x/image/math/fixed/fixed.go
@@ -0,0 +1,410 @@
+// Copyright 2015 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package fixed implements fixed-point integer types.
+package fixed // import "golang.org/x/image/math/fixed"
+
+import (
+ "fmt"
+)
+
+// TODO: implement fmt.Formatter for %f and %g.
+
+// I returns the integer value i as an Int26_6.
+//
+// For example, passing the integer value 2 yields Int26_6(128).
+func I(i int) Int26_6 {
+ return Int26_6(i << 6)
+}
+
+// Int26_6 is a signed 26.6 fixed-point number.
+//
+// The integer part ranges from -33554432 to 33554431, inclusive. The
+// fractional part has 6 bits of precision.
+//
+// For example, the number one-and-a-quarter is Int26_6(1<<6 + 1<<4).
+type Int26_6 int32
+
+// String returns a human-readable representation of a 26.6 fixed-point number.
+//
+// For example, the number one-and-a-quarter becomes "1:16".
+func (x Int26_6) String() string {
+ const shift, mask = 6, 1<<6 - 1
+ if x >= 0 {
+ return fmt.Sprintf("%d:%02d", int32(x>>shift), int32(x&mask))
+ }
+ x = -x
+ if x >= 0 {
+ return fmt.Sprintf("-%d:%02d", int32(x>>shift), int32(x&mask))
+ }
+ return "-33554432:00" // The minimum value is -(1<<25).
+}
+
+// Floor returns the greatest integer value less than or equal to x.
+//
+// Its return type is int, not Int26_6.
+func (x Int26_6) Floor() int { return int((x + 0x00) >> 6) }
+
+// Round returns the nearest integer value to x. Ties are rounded up.
+//
+// Its return type is int, not Int26_6.
+func (x Int26_6) Round() int { return int((x + 0x20) >> 6) }
+
+// Ceil returns the least integer value greater than or equal to x.
+//
+// Its return type is int, not Int26_6.
+func (x Int26_6) Ceil() int { return int((x + 0x3f) >> 6) }
+
+// Mul returns x*y in 26.6 fixed-point arithmetic.
+func (x Int26_6) Mul(y Int26_6) Int26_6 {
+ return Int26_6((int64(x)*int64(y) + 1<<5) >> 6)
+}
+
+// Int52_12 is a signed 52.12 fixed-point number.
+//
+// The integer part ranges from -2251799813685248 to 2251799813685247,
+// inclusive. The fractional part has 12 bits of precision.
+//
+// For example, the number one-and-a-quarter is Int52_12(1<<12 + 1<<10).
+type Int52_12 int64
+
+// String returns a human-readable representation of a 52.12 fixed-point
+// number.
+//
+// For example, the number one-and-a-quarter becomes "1:1024".
+func (x Int52_12) String() string {
+ const shift, mask = 12, 1<<12 - 1
+ if x >= 0 {
+ return fmt.Sprintf("%d:%04d", int64(x>>shift), int64(x&mask))
+ }
+ x = -x
+ if x >= 0 {
+ return fmt.Sprintf("-%d:%04d", int64(x>>shift), int64(x&mask))
+ }
+ return "-2251799813685248:0000" // The minimum value is -(1<<51).
+}
+
+// Floor returns the greatest integer value less than or equal to x.
+//
+// Its return type is int, not Int52_12.
+func (x Int52_12) Floor() int { return int((x + 0x000) >> 12) }
+
+// Round returns the nearest integer value to x. Ties are rounded up.
+//
+// Its return type is int, not Int52_12.
+func (x Int52_12) Round() int { return int((x + 0x800) >> 12) }
+
+// Ceil returns the least integer value greater than or equal to x.
+//
+// Its return type is int, not Int52_12.
+func (x Int52_12) Ceil() int { return int((x + 0xfff) >> 12) }
+
+// Mul returns x*y in 52.12 fixed-point arithmetic.
+func (x Int52_12) Mul(y Int52_12) Int52_12 {
+ const M, N = 52, 12
+ lo, hi := muli64(int64(x), int64(y))
+ ret := Int52_12(hi<<M | lo>>N)
+ ret += Int52_12((lo >> (N - 1)) & 1) // Round to nearest, instead of rounding down.
+ return ret
+}
+
+// muli64 multiplies two int64 values, returning the 128-bit signed integer
+// result as two uint64 values.
+//
+// This implementation is similar to $GOROOT/src/runtime/softfloat64.go's mullu
+// function, which is in turn adapted from Hacker's Delight.
+func muli64(u, v int64) (lo, hi uint64) {
+ const (
+ s = 32
+ mask = 1<<s - 1
+ )
+
+ u1 := uint64(u >> s)
+ u0 := uint64(u & mask)
+ v1 := uint64(v >> s)
+ v0 := uint64(v & mask)
+
+ w0 := u0 * v0
+ t := u1*v0 + w0>>s
+ w1 := t & mask
+ w2 := uint64(int64(t) >> s)
+ w1 += u0 * v1
+ return uint64(u) * uint64(v), u1*v1 + w2 + uint64(int64(w1)>>s)
+}
+
+// P returns the integer values x and y as a Point26_6.
+//
+// For example, passing the integer values (2, -3) yields Point26_6{128, -192}.
+func P(x, y int) Point26_6 {
+ return Point26_6{Int26_6(x << 6), Int26_6(y << 6)}
+}
+
+// Point26_6 is a 26.6 fixed-point coordinate pair.
+//
+// It is analogous to the image.Point type in the standard library.
+type Point26_6 struct {
+ X, Y Int26_6
+}
+
+// Add returns the vector p+q.
+func (p Point26_6) Add(q Point26_6) Point26_6 {
+ return Point26_6{p.X + q.X, p.Y + q.Y}
+}
+
+// Sub returns the vector p-q.
+func (p Point26_6) Sub(q Point26_6) Point26_6 {
+ return Point26_6{p.X - q.X, p.Y - q.Y}
+}
+
+// Mul returns the vector p*k.
+func (p Point26_6) Mul(k Int26_6) Point26_6 {
+ return Point26_6{p.X * k / 64, p.Y * k / 64}
+}
+
+// Div returns the vector p/k.
+func (p Point26_6) Div(k Int26_6) Point26_6 {
+ return Point26_6{p.X * 64 / k, p.Y * 64 / k}
+}
+
+// In returns whether p is in r.
+func (p Point26_6) In(r Rectangle26_6) bool {
+ return r.Min.X <= p.X && p.X < r.Max.X && r.Min.Y <= p.Y && p.Y < r.Max.Y
+}
+
+// Point52_12 is a 52.12 fixed-point coordinate pair.
+//
+// It is analogous to the image.Point type in the standard library.
+type Point52_12 struct {
+ X, Y Int52_12
+}
+
+// Add returns the vector p+q.
+func (p Point52_12) Add(q Point52_12) Point52_12 {
+ return Point52_12{p.X + q.X, p.Y + q.Y}
+}
+
+// Sub returns the vector p-q.
+func (p Point52_12) Sub(q Point52_12) Point52_12 {
+ return Point52_12{p.X - q.X, p.Y - q.Y}
+}
+
+// Mul returns the vector p*k.
+func (p Point52_12) Mul(k Int52_12) Point52_12 {
+ return Point52_12{p.X * k / 4096, p.Y * k / 4096}
+}
+
+// Div returns the vector p/k.
+func (p Point52_12) Div(k Int52_12) Point52_12 {
+ return Point52_12{p.X * 4096 / k, p.Y * 4096 / k}
+}
+
+// In returns whether p is in r.
+func (p Point52_12) In(r Rectangle52_12) bool {
+ return r.Min.X <= p.X && p.X < r.Max.X && r.Min.Y <= p.Y && p.Y < r.Max.Y
+}
+
+// R returns the integer values minX, minY, maxX, maxY as a Rectangle26_6.
+//
+// For example, passing the integer values (0, 1, 2, 3) yields
+// Rectangle26_6{Point26_6{0, 64}, Point26_6{128, 192}}.
+//
+// Like the image.Rect function in the standard library, the returned rectangle
+// has minimum and maximum coordinates swapped if necessary so that it is
+// well-formed.
+func R(minX, minY, maxX, maxY int) Rectangle26_6 {
+ if minX > maxX {
+ minX, maxX = maxX, minX
+ }
+ if minY > maxY {
+ minY, maxY = maxY, minY
+ }
+ return Rectangle26_6{
+ Point26_6{
+ Int26_6(minX << 6),
+ Int26_6(minY << 6),
+ },
+ Point26_6{
+ Int26_6(maxX << 6),
+ Int26_6(maxY << 6),
+ },
+ }
+}
+
+// Rectangle26_6 is a 26.6 fixed-point coordinate rectangle. The Min bound is
+// inclusive and the Max bound is exclusive. It is well-formed if Min.X <=
+// Max.X and likewise for Y.
+//
+// It is analogous to the image.Rectangle type in the standard library.
+type Rectangle26_6 struct {
+ Min, Max Point26_6
+}
+
+// Add returns the rectangle r translated by p.
+func (r Rectangle26_6) Add(p Point26_6) Rectangle26_6 {
+ return Rectangle26_6{
+ Point26_6{r.Min.X + p.X, r.Min.Y + p.Y},
+ Point26_6{r.Max.X + p.X, r.Max.Y + p.Y},
+ }
+}
+
+// Sub returns the rectangle r translated by -p.
+func (r Rectangle26_6) Sub(p Point26_6) Rectangle26_6 {
+ return Rectangle26_6{
+ Point26_6{r.Min.X - p.X, r.Min.Y - p.Y},
+ Point26_6{r.Max.X - p.X, r.Max.Y - p.Y},
+ }
+}
+
+// Intersect returns the largest rectangle contained by both r and s. If the
+// two rectangles do not overlap then the zero rectangle will be returned.
+func (r Rectangle26_6) Intersect(s Rectangle26_6) Rectangle26_6 {
+ if r.Min.X < s.Min.X {
+ r.Min.X = s.Min.X
+ }
+ if r.Min.Y < s.Min.Y {
+ r.Min.Y = s.Min.Y
+ }
+ if r.Max.X > s.Max.X {
+ r.Max.X = s.Max.X
+ }
+ if r.Max.Y > s.Max.Y {
+ r.Max.Y = s.Max.Y
+ }
+ // Letting r0 and s0 be the values of r and s at the time that the method
+ // is called, this next line is equivalent to:
+ //
+ // if max(r0.Min.X, s0.Min.X) >= min(r0.Max.X, s0.Max.X) || likewiseForY { etc }
+ if r.Empty() {
+ return Rectangle26_6{}
+ }
+ return r
+}
+
+// Union returns the smallest rectangle that contains both r and s.
+func (r Rectangle26_6) Union(s Rectangle26_6) Rectangle26_6 {
+ if r.Empty() {
+ return s
+ }
+ if s.Empty() {
+ return r
+ }
+ if r.Min.X > s.Min.X {
+ r.Min.X = s.Min.X
+ }
+ if r.Min.Y > s.Min.Y {
+ r.Min.Y = s.Min.Y
+ }
+ if r.Max.X < s.Max.X {
+ r.Max.X = s.Max.X
+ }
+ if r.Max.Y < s.Max.Y {
+ r.Max.Y = s.Max.Y
+ }
+ return r
+}
+
+// Empty returns whether the rectangle contains no points.
+func (r Rectangle26_6) Empty() bool {
+ return r.Min.X >= r.Max.X || r.Min.Y >= r.Max.Y
+}
+
+// In returns whether every point in r is in s.
+func (r Rectangle26_6) In(s Rectangle26_6) bool {
+ if r.Empty() {
+ return true
+ }
+ // Note that r.Max is an exclusive bound for r, so that r.In(s)
+ // does not require that r.Max.In(s).
+ return s.Min.X <= r.Min.X && r.Max.X <= s.Max.X &&
+ s.Min.Y <= r.Min.Y && r.Max.Y <= s.Max.Y
+}
+
+// Rectangle52_12 is a 52.12 fixed-point coordinate rectangle. The Min bound is
+// inclusive and the Max bound is exclusive. It is well-formed if Min.X <=
+// Max.X and likewise for Y.
+//
+// It is analogous to the image.Rectangle type in the standard library.
+type Rectangle52_12 struct {
+ Min, Max Point52_12
+}
+
+// Add returns the rectangle r translated by p.
+func (r Rectangle52_12) Add(p Point52_12) Rectangle52_12 {
+ return Rectangle52_12{
+ Point52_12{r.Min.X + p.X, r.Min.Y + p.Y},
+ Point52_12{r.Max.X + p.X, r.Max.Y + p.Y},
+ }
+}
+
+// Sub returns the rectangle r translated by -p.
+func (r Rectangle52_12) Sub(p Point52_12) Rectangle52_12 {
+ return Rectangle52_12{
+ Point52_12{r.Min.X - p.X, r.Min.Y - p.Y},
+ Point52_12{r.Max.X - p.X, r.Max.Y - p.Y},
+ }
+}
+
+// Intersect returns the largest rectangle contained by both r and s. If the
+// two rectangles do not overlap then the zero rectangle will be returned.
+func (r Rectangle52_12) Intersect(s Rectangle52_12) Rectangle52_12 {
+ if r.Min.X < s.Min.X {
+ r.Min.X = s.Min.X
+ }
+ if r.Min.Y < s.Min.Y {
+ r.Min.Y = s.Min.Y
+ }
+ if r.Max.X > s.Max.X {
+ r.Max.X = s.Max.X
+ }
+ if r.Max.Y > s.Max.Y {
+ r.Max.Y = s.Max.Y
+ }
+ // Letting r0 and s0 be the values of r and s at the time that the method
+ // is called, this next line is equivalent to:
+ //
+ // if max(r0.Min.X, s0.Min.X) >= min(r0.Max.X, s0.Max.X) || likewiseForY { etc }
+ if r.Empty() {
+ return Rectangle52_12{}
+ }
+ return r
+}
+
+// Union returns the smallest rectangle that contains both r and s.
+func (r Rectangle52_12) Union(s Rectangle52_12) Rectangle52_12 {
+ if r.Empty() {
+ return s
+ }
+ if s.Empty() {
+ return r
+ }
+ if r.Min.X > s.Min.X {
+ r.Min.X = s.Min.X
+ }
+ if r.Min.Y > s.Min.Y {
+ r.Min.Y = s.Min.Y
+ }
+ if r.Max.X < s.Max.X {
+ r.Max.X = s.Max.X
+ }
+ if r.Max.Y < s.Max.Y {
+ r.Max.Y = s.Max.Y
+ }
+ return r
+}
+
+// Empty returns whether the rectangle contains no points.
+func (r Rectangle52_12) Empty() bool {
+ return r.Min.X >= r.Max.X || r.Min.Y >= r.Max.Y
+}
+
+// In returns whether every point in r is in s.
+func (r Rectangle52_12) In(s Rectangle52_12) bool {
+ if r.Empty() {
+ return true
+ }
+ // Note that r.Max is an exclusive bound for r, so that r.In(s)
+ // does not require that r.Max.In(s).
+ return s.Min.X <= r.Min.X && r.Max.X <= s.Max.X &&
+ s.Min.Y <= r.Min.Y && r.Max.Y <= s.Max.Y
+}
diff --git a/vendor/golang.org/x/image/math/fixed/fixed_test.go b/vendor/golang.org/x/image/math/fixed/fixed_test.go
new file mode 100644
index 0000000..c81fb72
--- /dev/null
+++ b/vendor/golang.org/x/image/math/fixed/fixed_test.go
@@ -0,0 +1,439 @@
+// Copyright 2015 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package fixed
+
+import (
+ "math"
+ "math/rand"
+ "testing"
+)
+
+var testCases = []struct {
+ x float64
+ s26_6 string
+ s52_12 string
+ floor int
+ round int
+ ceil int
+}{{
+ x: 0,
+ s26_6: "0:00",
+ s52_12: "0:0000",
+ floor: 0,
+ round: 0,
+ ceil: 0,
+}, {
+ x: 1,
+ s26_6: "1:00",
+ s52_12: "1:0000",
+ floor: 1,
+ round: 1,
+ ceil: 1,
+}, {
+ x: 1.25,
+ s26_6: "1:16",
+ s52_12: "1:1024",
+ floor: 1,
+ round: 1,
+ ceil: 2,
+}, {
+ x: 2.5,
+ s26_6: "2:32",
+ s52_12: "2:2048",
+ floor: 2,
+ round: 3,
+ ceil: 3,
+}, {
+ x: 63 / 64.0,
+ s26_6: "0:63",
+ s52_12: "0:4032",
+ floor: 0,
+ round: 1,
+ ceil: 1,
+}, {
+ x: -0.5,
+ s26_6: "-0:32",
+ s52_12: "-0:2048",
+ floor: -1,
+ round: +0,
+ ceil: +0,
+}, {
+ x: -4.125,
+ s26_6: "-4:08",
+ s52_12: "-4:0512",
+ floor: -5,
+ round: -4,
+ ceil: -4,
+}, {
+ x: -7.75,
+ s26_6: "-7:48",
+ s52_12: "-7:3072",
+ floor: -8,
+ round: -8,
+ ceil: -7,
+}}
+
+func TestInt26_6(t *testing.T) {
+ const one = Int26_6(1 << 6)
+ for _, tc := range testCases {
+ x := Int26_6(tc.x * (1 << 6))
+ if got, want := x.String(), tc.s26_6; got != want {
+ t.Errorf("tc.x=%v: String: got %q, want %q", tc.x, got, want)
+ }
+ if got, want := x.Floor(), tc.floor; got != want {
+ t.Errorf("tc.x=%v: Floor: got %v, want %v", tc.x, got, want)
+ }
+ if got, want := x.Round(), tc.round; got != want {
+ t.Errorf("tc.x=%v: Round: got %v, want %v", tc.x, got, want)
+ }
+ if got, want := x.Ceil(), tc.ceil; got != want {
+ t.Errorf("tc.x=%v: Ceil: got %v, want %v", tc.x, got, want)
+ }
+ if got, want := x.Mul(one), x; got != want {
+ t.Errorf("tc.x=%v: Mul by one: got %v, want %v", tc.x, got, want)
+ }
+ if got, want := x.mul(one), x; got != want {
+ t.Errorf("tc.x=%v: mul by one: got %v, want %v", tc.x, got, want)
+ }
+ }
+}
+
+func TestInt52_12(t *testing.T) {
+ const one = Int52_12(1 << 12)
+ for _, tc := range testCases {
+ x := Int52_12(tc.x * (1 << 12))
+ if got, want := x.String(), tc.s52_12; got != want {
+ t.Errorf("tc.x=%v: String: got %q, want %q", tc.x, got, want)
+ }
+ if got, want := x.Floor(), tc.floor; got != want {
+ t.Errorf("tc.x=%v: Floor: got %v, want %v", tc.x, got, want)
+ }
+ if got, want := x.Round(), tc.round; got != want {
+ t.Errorf("tc.x=%v: Round: got %v, want %v", tc.x, got, want)
+ }
+ if got, want := x.Ceil(), tc.ceil; got != want {
+ t.Errorf("tc.x=%v: Ceil: got %v, want %v", tc.x, got, want)
+ }
+ if got, want := x.Mul(one), x; got != want {
+ t.Errorf("tc.x=%v: Mul by one: got %v, want %v", tc.x, got, want)
+ }
+ }
+}
+
+var mulTestCases = []struct {
+ x float64
+ y float64
+ z26_6 float64 // Equals truncate26_6(x)*truncate26_6(y).
+ z52_12 float64 // Equals truncate52_12(x)*truncate52_12(y).
+ s26_6 string
+ s52_12 string
+}{{
+ x: 0,
+ y: 1.5,
+ z26_6: 0,
+ z52_12: 0,
+ s26_6: "0:00",
+ s52_12: "0:0000",
+}, {
+ x: +1.25,
+ y: +4,
+ z26_6: +5,
+ z52_12: +5,
+ s26_6: "5:00",
+ s52_12: "5:0000",
+}, {
+ x: +1.25,
+ y: -4,
+ z26_6: -5,
+ z52_12: -5,
+ s26_6: "-5:00",
+ s52_12: "-5:0000",
+}, {
+ x: -1.25,
+ y: +4,
+ z26_6: -5,
+ z52_12: -5,
+ s26_6: "-5:00",
+ s52_12: "-5:0000",
+}, {
+ x: -1.25,
+ y: -4,
+ z26_6: +5,
+ z52_12: +5,
+ s26_6: "5:00",
+ s52_12: "5:0000",
+}, {
+ x: 1.25,
+ y: 1.5,
+ z26_6: 1.875,
+ z52_12: 1.875,
+ s26_6: "1:56",
+ s52_12: "1:3584",
+}, {
+ x: 1234.5,
+ y: -8888.875,
+ z26_6: -10973316.1875,
+ z52_12: -10973316.1875,
+ s26_6: "-10973316:12",
+ s52_12: "-10973316:0768",
+}, {
+ x: 1.515625, // 1 + 33/64 = 97/64
+ y: 1.531250, // 1 + 34/64 = 98/64
+ z26_6: 2.32080078125, // 2 + 1314/4096 = 9506/4096
+ z52_12: 2.32080078125, // 2 + 1314/4096 = 9506/4096
+ s26_6: "2:21", // 2.32812500000, which is closer than 2:20 (in decimal, 2.3125)
+ s52_12: "2:1314", // 2.32080078125
+}, {
+ x: 0.500244140625, // 2049/4096, approximately 32/64
+ y: 0.500732421875, // 2051/4096, approximately 32/64
+ z26_6: 0.25, // 4194304/16777216, or 1024/4096
+ z52_12: 0.2504884600639343, // 4202499/16777216
+ s26_6: "0:16", // 0.25000000000
+ s52_12: "0:1026", // 0.25048828125, which is closer than 0:1027 (in decimal, 0.250732421875)
+}, {
+ x: 0.015625, // 1/64
+ y: 0.000244140625, // 1/4096, approximately 0/64
+ z26_6: 0.0, // 0
+ z52_12: 0.000003814697265625, // 1/262144
+ s26_6: "0:00", // 0
+ s52_12: "0:0000", // 0, which is closer than 0:0001 (in decimal, 0.000244140625)
+}, {
+ // Round the Int52_12 calculation down.
+ x: 1.44140625, // 1 + 1808/4096 = 5904/4096, approximately 92/64
+ y: 1.44140625, // 1 + 1808/4096 = 5904/4096, approximately 92/64
+ z26_6: 2.06640625, // 2 + 272/4096 = 8464/4096
+ z52_12: 2.0776519775390625, // 2 + 318/4096 + 256/16777216 = 34857216/16777216
+ s26_6: "2:04", // 2.06250000000, which is closer than 2:05 (in decimal, 2.078125000000)
+ s52_12: "2:0318", // 2.07763671875, which is closer than 2:0319 (in decimal, 2.077880859375)
+}, {
+ // Round the Int52_12 calculation up.
+ x: 1.44140625, // 1 + 1808/4096 = 5904/4096, approximately 92/64
+ y: 1.441650390625, // 1 + 1809/4096 = 5905/4096, approximately 92/64
+ z26_6: 2.06640625, // 2 + 272/4096 = 8464/4096
+ z52_12: 2.0780038833618164, // 2 + 319/4096 + 2064/16777216 = 34863120/16777216
+ s26_6: "2:04", // 2.06250000000, which is closer than 2:05 (in decimal, 2.078125000000)
+ s52_12: "2:0320", // 2.07812500000, which is closer than 2:0319 (in decimal, 2.077880859375)
+}}
+
+func TestInt26_6Mul(t *testing.T) {
+ for _, tc := range mulTestCases {
+ x := Int26_6(tc.x * (1 << 6))
+ y := Int26_6(tc.y * (1 << 6))
+ if z := float64(x) * float64(y) / (1 << 12); z != tc.z26_6 {
+ t.Errorf("tc.x=%v, tc.y=%v: z: got %v, want %v", tc.x, tc.y, z, tc.z26_6)
+ continue
+ }
+ if got, want := x.Mul(y).String(), tc.s26_6; got != want {
+ t.Errorf("tc.x=%v: Mul: got %q, want %q", tc.x, got, want)
+ }
+ }
+}
+
+func TestInt52_12Mul(t *testing.T) {
+ for _, tc := range mulTestCases {
+ x := Int52_12(tc.x * (1 << 12))
+ y := Int52_12(tc.y * (1 << 12))
+ if z := float64(x) * float64(y) / (1 << 24); z != tc.z52_12 {
+ t.Errorf("tc.x=%v, tc.y=%v: z: got %v, want %v", tc.x, tc.y, z, tc.z52_12)
+ continue
+ }
+ if got, want := x.Mul(y).String(), tc.s52_12; got != want {
+ t.Errorf("tc.x=%v: Mul: got %q, want %q", tc.x, got, want)
+ }
+ }
+}
+
+func TestInt26_6MulByOneMinusIota(t *testing.T) {
+ const (
+ totalBits = 32
+ fracBits = 6
+
+ oneMinusIota = Int26_6(1<<fracBits) - 1
+ oneMinusIotaF = float64(oneMinusIota) / (1 << fracBits)
+ )
+
+ for _, neg := range []bool{false, true} {
+ for i := uint(0); i < totalBits; i++ {
+ x := Int26_6(1 << i)
+ if neg {
+ x = -x
+ } else if i == totalBits-1 {
+ // A signed int32 can't represent 1<<31.
+ continue
+ }
+
+ // want equals x * oneMinusIota, rounded to nearest.
+ want := Int26_6(0)
+ if -1<<fracBits < x && x < 1<<fracBits {
+ // (x * oneMinusIota) isn't exactly representable as an
+ // Int26_6. Calculate the rounded value using float64 math.
+ xF := float64(x) / (1 << fracBits)
+ wantF := xF * oneMinusIotaF * (1 << fracBits)
+ want = Int26_6(math.Floor(wantF + 0.5))
+ } else {
+ // (x * oneMinusIota) is exactly representable.
+ want = oneMinusIota << (i - fracBits)
+ if neg {
+ want = -want
+ }
+ }
+
+ if got := x.Mul(oneMinusIota); got != want {
+ t.Errorf("neg=%t, i=%d, x=%v, Mul: got %v, want %v", neg, i, x, got, want)
+ }
+ if got := x.mul(oneMinusIota); got != want {
+ t.Errorf("neg=%t, i=%d, x=%v, mul: got %v, want %v", neg, i, x, got, want)
+ }
+ }
+ }
+}
+
+func TestInt52_12MulByOneMinusIota(t *testing.T) {
+ const (
+ totalBits = 64
+ fracBits = 12
+
+ oneMinusIota = Int52_12(1<<fracBits) - 1
+ oneMinusIotaF = float64(oneMinusIota) / (1 << fracBits)
+ )
+
+ for _, neg := range []bool{false, true} {
+ for i := uint(0); i < totalBits; i++ {
+ x := Int52_12(1 << i)
+ if neg {
+ x = -x
+ } else if i == totalBits-1 {
+ // A signed int64 can't represent 1<<63.
+ continue
+ }
+
+ // want equals x * oneMinusIota, rounded to nearest.
+ want := Int52_12(0)
+ if -1<<fracBits < x && x < 1<<fracBits {
+ // (x * oneMinusIota) isn't exactly representable as an
+ // Int52_12. Calculate the rounded value using float64 math.
+ xF := float64(x) / (1 << fracBits)
+ wantF := xF * oneMinusIotaF * (1 << fracBits)
+ want = Int52_12(math.Floor(wantF + 0.5))
+ } else {
+ // (x * oneMinusIota) is exactly representable.
+ want = oneMinusIota << (i - fracBits)
+ if neg {
+ want = -want
+ }
+ }
+
+ if got := x.Mul(oneMinusIota); got != want {
+ t.Errorf("neg=%t, i=%d, x=%v, Mul: got %v, want %v", neg, i, x, got, want)
+ }
+ }
+ }
+}
+
+func TestInt26_6MulVsMul(t *testing.T) {
+ rng := rand.New(rand.NewSource(1))
+ for i := 0; i < 10000; i++ {
+ u := Int26_6(rng.Uint32())
+ v := Int26_6(rng.Uint32())
+ Mul := u.Mul(v)
+ mul := u.mul(v)
+ if Mul != mul {
+ t.Errorf("u=%#08x, v=%#08x: Mul=%#08x and mul=%#08x differ",
+ uint32(u), uint32(v), uint32(Mul), uint32(mul))
+ }
+ }
+}
+
+func TestMuli32(t *testing.T) {
+ rng := rand.New(rand.NewSource(2))
+ for i := 0; i < 10000; i++ {
+ u := int32(rng.Uint32())
+ v := int32(rng.Uint32())
+ lo, hi := muli32(u, v)
+ got := uint64(lo) | uint64(hi)<<32
+ want := uint64(int64(u) * int64(v))
+ if got != want {
+ t.Errorf("u=%#08x, v=%#08x: got %#016x, want %#016x", uint32(u), uint32(v), got, want)
+ }
+ }
+}
+
+func TestMulu32(t *testing.T) {
+ rng := rand.New(rand.NewSource(3))
+ for i := 0; i < 10000; i++ {
+ u := rng.Uint32()
+ v := rng.Uint32()
+ lo, hi := mulu32(u, v)
+ got := uint64(lo) | uint64(hi)<<32
+ want := uint64(u) * uint64(v)
+ if got != want {
+ t.Errorf("u=%#08x, v=%#08x: got %#016x, want %#016x", u, v, got, want)
+ }
+ }
+}
+
+// mul (with a lower case 'm') is an alternative implementation of Int26_6.Mul
+// (with an upper case 'M'). It has the same structure as the Int52_12.Mul
+// implementation, but Int26_6.mul is easier to test since Go has built-in
+// 64-bit integers.
+func (x Int26_6) mul(y Int26_6) Int26_6 {
+ const M, N = 26, 6
+ lo, hi := muli32(int32(x), int32(y))
+ ret := Int26_6(hi<<M | lo>>N)
+ ret += Int26_6((lo >> (N - 1)) & 1) // Round to nearest, instead of rounding down.
+ return ret
+}
+
+// muli32 multiplies two int32 values, returning the 64-bit signed integer
+// result as two uint32 values.
+//
+// muli32 isn't used directly by this package, but it has the same structure as
+// muli64, and muli32 is easier to test since Go has built-in 64-bit integers.
+func muli32(u, v int32) (lo, hi uint32) {
+ const (
+ s = 16
+ mask = 1<<s - 1
+ )
+
+ u1 := uint32(u >> s)
+ u0 := uint32(u & mask)
+ v1 := uint32(v >> s)
+ v0 := uint32(v & mask)
+
+ w0 := u0 * v0
+ t := u1*v0 + w0>>s
+ w1 := t & mask
+ w2 := uint32(int32(t) >> s)
+ w1 += u0 * v1
+ return uint32(u) * uint32(v), u1*v1 + w2 + uint32(int32(w1)>>s)
+}
+
+// mulu32 is like muli32, except that it multiplies unsigned instead of signed
+// values.
+//
+// This implementation comes from $GOROOT/src/runtime/softfloat64.go's mullu
+// function, which is in turn adapted from Hacker's Delight.
+//
+// mulu32 (and its corresponding test, TestMulu32) isn't used directly by this
+// package. It is provided in this test file as a reference point to compare
+// the muli32 (and TestMuli32) implementations against.
+func mulu32(u, v uint32) (lo, hi uint32) {
+ const (
+ s = 16
+ mask = 1<<s - 1
+ )
+
+ u0 := u & mask
+ u1 := u >> s
+ v0 := v & mask
+ v1 := v >> s
+
+ w0 := u0 * v0
+ t := u1*v0 + w0>>s
+ w1 := t & mask
+ w2 := t >> s
+ w1 += u0 * v1
+ return u * v, u1*v1 + w2 + w1>>s
+}