fixed.go

Documentation: golang.org/x/image/math/fixed

     1  // Copyright 2015 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package fixed implements fixed-point integer types.
     6  package fixed // import "golang.org/x/image/math/fixed"
     7  
     8  import (
     9  	"fmt"
    10  )
    11  
    12  // TODO: implement fmt.Formatter for %f and %g.
    13  
    14  // I returns the integer value i as an Int26_6.
    15  //
    16  // For example, passing the integer value 2 yields Int26_6(128).
    17  func I(i int) Int26_6 {
    18  	return Int26_6(i << 6)
    19  }
    20  
    21  // Int26_6 is a signed 26.6 fixed-point number.
    22  //
    23  // The integer part ranges from -33554432 to 33554431, inclusive. The
    24  // fractional part has 6 bits of precision.
    25  //
    26  // For example, the number one-and-a-quarter is Int26_6(1<<6 + 1<<4).
    27  type Int26_6 int32
    28  
    29  // String returns a human-readable representation of a 26.6 fixed-point number.
    30  //
    31  // For example, the number one-and-a-quarter becomes "1:16".
    32  func (x Int26_6) String() string {
    33  	const shift, mask = 6, 1<<6 - 1
    34  	if x >= 0 {
    35  		return fmt.Sprintf("%d:%02d", int32(x>>shift), int32(x&mask))
    36  	}
    37  	x = -x
    38  	if x >= 0 {
    39  		return fmt.Sprintf("-%d:%02d", int32(x>>shift), int32(x&mask))
    40  	}
    41  	return "-33554432:00" // The minimum value is -(1<<25).
    42  }
    43  
    44  // Floor returns the greatest integer value less than or equal to x.
    45  //
    46  // Its return type is int, not Int26_6.
    47  func (x Int26_6) Floor() int { return int((x + 0x00) >> 6) }
    48  
    49  // Round returns the nearest integer value to x. Ties are rounded up.
    50  //
    51  // Its return type is int, not Int26_6.
    52  func (x Int26_6) Round() int { return int((x + 0x20) >> 6) }
    53  
    54  // Ceil returns the least integer value greater than or equal to x.
    55  //
    56  // Its return type is int, not Int26_6.
    57  func (x Int26_6) Ceil() int { return int((x + 0x3f) >> 6) }
    58  
    59  // Mul returns x*y in 26.6 fixed-point arithmetic.
    60  func (x Int26_6) Mul(y Int26_6) Int26_6 {
    61  	return Int26_6((int64(x)*int64(y) + 1<<5) >> 6)
    62  }
    63  
    64  // Int52_12 is a signed 52.12 fixed-point number.
    65  //
    66  // The integer part ranges from -2251799813685248 to 2251799813685247,
    67  // inclusive. The fractional part has 12 bits of precision.
    68  //
    69  // For example, the number one-and-a-quarter is Int52_12(1<<12 + 1<<10).
    70  type Int52_12 int64
    71  
    72  // String returns a human-readable representation of a 52.12 fixed-point
    73  // number.
    74  //
    75  // For example, the number one-and-a-quarter becomes "1:1024".
    76  func (x Int52_12) String() string {
    77  	const shift, mask = 12, 1<<12 - 1
    78  	if x >= 0 {
    79  		return fmt.Sprintf("%d:%04d", int64(x>>shift), int64(x&mask))
    80  	}
    81  	x = -x
    82  	if x >= 0 {
    83  		return fmt.Sprintf("-%d:%04d", int64(x>>shift), int64(x&mask))
    84  	}
    85  	return "-2251799813685248:0000" // The minimum value is -(1<<51).
    86  }
    87  
    88  // Floor returns the greatest integer value less than or equal to x.
    89  //
    90  // Its return type is int, not Int52_12.
    91  func (x Int52_12) Floor() int { return int((x + 0x000) >> 12) }
    92  
    93  // Round returns the nearest integer value to x. Ties are rounded up.
    94  //
    95  // Its return type is int, not Int52_12.
    96  func (x Int52_12) Round() int { return int((x + 0x800) >> 12) }
    97  
    98  // Ceil returns the least integer value greater than or equal to x.
    99  //
   100  // Its return type is int, not Int52_12.
   101  func (x Int52_12) Ceil() int { return int((x + 0xfff) >> 12) }
   102  
   103  // Mul returns x*y in 52.12 fixed-point arithmetic.
   104  func (x Int52_12) Mul(y Int52_12) Int52_12 {
   105  	const M, N = 52, 12
   106  	lo, hi := muli64(int64(x), int64(y))
   107  	ret := Int52_12(hi<<M | lo>>N)
   108  	ret += Int52_12((lo >> (N - 1)) & 1) // Round to nearest, instead of rounding down.
   109  	return ret
   110  }
   111  
   112  // muli64 multiplies two int64 values, returning the 128-bit signed integer
   113  // result as two uint64 values.
   114  //
   115  // This implementation is similar to $GOROOT/src/runtime/softfloat64.go's mullu
   116  // function, which is in turn adapted from Hacker's Delight.
   117  func muli64(u, v int64) (lo, hi uint64) {
   118  	const (
   119  		s    = 32
   120  		mask = 1<<s - 1
   121  	)
   122  
   123  	u1 := uint64(u >> s)
   124  	u0 := uint64(u & mask)
   125  	v1 := uint64(v >> s)
   126  	v0 := uint64(v & mask)
   127  
   128  	w0 := u0 * v0
   129  	t := u1*v0 + w0>>s
   130  	w1 := t & mask
   131  	w2 := uint64(int64(t) >> s)
   132  	w1 += u0 * v1
   133  	return uint64(u) * uint64(v), u1*v1 + w2 + uint64(int64(w1)>>s)
   134  }
   135  
   136  // P returns the integer values x and y as a Point26_6.
   137  //
   138  // For example, passing the integer values (2, -3) yields Point26_6{128, -192}.
   139  func P(x, y int) Point26_6 {
   140  	return Point26_6{Int26_6(x << 6), Int26_6(y << 6)}
   141  }
   142  
   143  // Point26_6 is a 26.6 fixed-point coordinate pair.
   144  //
   145  // It is analogous to the image.Point type in the standard library.
   146  type Point26_6 struct {
   147  	X, Y Int26_6
   148  }
   149  
   150  // Add returns the vector p+q.
   151  func (p Point26_6) Add(q Point26_6) Point26_6 {
   152  	return Point26_6{p.X + q.X, p.Y + q.Y}
   153  }
   154  
   155  // Sub returns the vector p-q.
   156  func (p Point26_6) Sub(q Point26_6) Point26_6 {
   157  	return Point26_6{p.X - q.X, p.Y - q.Y}
   158  }
   159  
   160  // Mul returns the vector p*k.
   161  func (p Point26_6) Mul(k Int26_6) Point26_6 {
   162  	return Point26_6{p.X * k / 64, p.Y * k / 64}
   163  }
   164  
   165  // Div returns the vector p/k.
   166  func (p Point26_6) Div(k Int26_6) Point26_6 {
   167  	return Point26_6{p.X * 64 / k, p.Y * 64 / k}
   168  }
   169  
   170  // In returns whether p is in r.
   171  func (p Point26_6) In(r Rectangle26_6) bool {
   172  	return r.Min.X <= p.X && p.X < r.Max.X && r.Min.Y <= p.Y && p.Y < r.Max.Y
   173  }
   174  
   175  // Point52_12 is a 52.12 fixed-point coordinate pair.
   176  //
   177  // It is analogous to the image.Point type in the standard library.
   178  type Point52_12 struct {
   179  	X, Y Int52_12
   180  }
   181  
   182  // Add returns the vector p+q.
   183  func (p Point52_12) Add(q Point52_12) Point52_12 {
   184  	return Point52_12{p.X + q.X, p.Y + q.Y}
   185  }
   186  
   187  // Sub returns the vector p-q.
   188  func (p Point52_12) Sub(q Point52_12) Point52_12 {
   189  	return Point52_12{p.X - q.X, p.Y - q.Y}
   190  }
   191  
   192  // Mul returns the vector p*k.
   193  func (p Point52_12) Mul(k Int52_12) Point52_12 {
   194  	return Point52_12{p.X * k / 4096, p.Y * k / 4096}
   195  }
   196  
   197  // Div returns the vector p/k.
   198  func (p Point52_12) Div(k Int52_12) Point52_12 {
   199  	return Point52_12{p.X * 4096 / k, p.Y * 4096 / k}
   200  }
   201  
   202  // In returns whether p is in r.
   203  func (p Point52_12) In(r Rectangle52_12) bool {
   204  	return r.Min.X <= p.X && p.X < r.Max.X && r.Min.Y <= p.Y && p.Y < r.Max.Y
   205  }
   206  
   207  // R returns the integer values minX, minY, maxX, maxY as a Rectangle26_6.
   208  //
   209  // For example, passing the integer values (0, 1, 2, 3) yields
   210  // Rectangle26_6{Point26_6{0, 64}, Point26_6{128, 192}}.
   211  //
   212  // Like the image.Rect function in the standard library, the returned rectangle
   213  // has minimum and maximum coordinates swapped if necessary so that it is
   214  // well-formed.
   215  func R(minX, minY, maxX, maxY int) Rectangle26_6 {
   216  	if minX > maxX {
   217  		minX, maxX = maxX, minX
   218  	}
   219  	if minY > maxY {
   220  		minY, maxY = maxY, minY
   221  	}
   222  	return Rectangle26_6{
   223  		Point26_6{
   224  			Int26_6(minX << 6),
   225  			Int26_6(minY << 6),
   226  		},
   227  		Point26_6{
   228  			Int26_6(maxX << 6),
   229  			Int26_6(maxY << 6),
   230  		},
   231  	}
   232  }
   233  
   234  // Rectangle26_6 is a 26.6 fixed-point coordinate rectangle. The Min bound is
   235  // inclusive and the Max bound is exclusive. It is well-formed if Min.X <=
   236  // Max.X and likewise for Y.
   237  //
   238  // It is analogous to the image.Rectangle type in the standard library.
   239  type Rectangle26_6 struct {
   240  	Min, Max Point26_6
   241  }
   242  
   243  // Add returns the rectangle r translated by p.
   244  func (r Rectangle26_6) Add(p Point26_6) Rectangle26_6 {
   245  	return Rectangle26_6{
   246  		Point26_6{r.Min.X + p.X, r.Min.Y + p.Y},
   247  		Point26_6{r.Max.X + p.X, r.Max.Y + p.Y},
   248  	}
   249  }
   250  
   251  // Sub returns the rectangle r translated by -p.
   252  func (r Rectangle26_6) Sub(p Point26_6) Rectangle26_6 {
   253  	return Rectangle26_6{
   254  		Point26_6{r.Min.X - p.X, r.Min.Y - p.Y},
   255  		Point26_6{r.Max.X - p.X, r.Max.Y - p.Y},
   256  	}
   257  }
   258  
   259  // Intersect returns the largest rectangle contained by both r and s. If the
   260  // two rectangles do not overlap then the zero rectangle will be returned.
   261  func (r Rectangle26_6) Intersect(s Rectangle26_6) Rectangle26_6 {
   262  	if r.Min.X < s.Min.X {
   263  		r.Min.X = s.Min.X
   264  	}
   265  	if r.Min.Y < s.Min.Y {
   266  		r.Min.Y = s.Min.Y
   267  	}
   268  	if r.Max.X > s.Max.X {
   269  		r.Max.X = s.Max.X
   270  	}
   271  	if r.Max.Y > s.Max.Y {
   272  		r.Max.Y = s.Max.Y
   273  	}
   274  	// Letting r0 and s0 be the values of r and s at the time that the method
   275  	// is called, this next line is equivalent to:
   276  	//
   277  	// if max(r0.Min.X, s0.Min.X) >= min(r0.Max.X, s0.Max.X) || likewiseForY { etc }
   278  	if r.Empty() {
   279  		return Rectangle26_6{}
   280  	}
   281  	return r
   282  }
   283  
   284  // Union returns the smallest rectangle that contains both r and s.
   285  func (r Rectangle26_6) Union(s Rectangle26_6) Rectangle26_6 {
   286  	if r.Empty() {
   287  		return s
   288  	}
   289  	if s.Empty() {
   290  		return r
   291  	}
   292  	if r.Min.X > s.Min.X {
   293  		r.Min.X = s.Min.X
   294  	}
   295  	if r.Min.Y > s.Min.Y {
   296  		r.Min.Y = s.Min.Y
   297  	}
   298  	if r.Max.X < s.Max.X {
   299  		r.Max.X = s.Max.X
   300  	}
   301  	if r.Max.Y < s.Max.Y {
   302  		r.Max.Y = s.Max.Y
   303  	}
   304  	return r
   305  }
   306  
   307  // Empty returns whether the rectangle contains no points.
   308  func (r Rectangle26_6) Empty() bool {
   309  	return r.Min.X >= r.Max.X || r.Min.Y >= r.Max.Y
   310  }
   311  
   312  // In returns whether every point in r is in s.
   313  func (r Rectangle26_6) In(s Rectangle26_6) bool {
   314  	if r.Empty() {
   315  		return true
   316  	}
   317  	// Note that r.Max is an exclusive bound for r, so that r.In(s)
   318  	// does not require that r.Max.In(s).
   319  	return s.Min.X <= r.Min.X && r.Max.X <= s.Max.X &&
   320  		s.Min.Y <= r.Min.Y && r.Max.Y <= s.Max.Y
   321  }
   322  
   323  // Rectangle52_12 is a 52.12 fixed-point coordinate rectangle. The Min bound is
   324  // inclusive and the Max bound is exclusive. It is well-formed if Min.X <=
   325  // Max.X and likewise for Y.
   326  //
   327  // It is analogous to the image.Rectangle type in the standard library.
   328  type Rectangle52_12 struct {
   329  	Min, Max Point52_12
   330  }
   331  
   332  // Add returns the rectangle r translated by p.
   333  func (r Rectangle52_12) Add(p Point52_12) Rectangle52_12 {
   334  	return Rectangle52_12{
   335  		Point52_12{r.Min.X + p.X, r.Min.Y + p.Y},
   336  		Point52_12{r.Max.X + p.X, r.Max.Y + p.Y},
   337  	}
   338  }
   339  
   340  // Sub returns the rectangle r translated by -p.
   341  func (r Rectangle52_12) Sub(p Point52_12) Rectangle52_12 {
   342  	return Rectangle52_12{
   343  		Point52_12{r.Min.X - p.X, r.Min.Y - p.Y},
   344  		Point52_12{r.Max.X - p.X, r.Max.Y - p.Y},
   345  	}
   346  }
   347  
   348  // Intersect returns the largest rectangle contained by both r and s. If the
   349  // two rectangles do not overlap then the zero rectangle will be returned.
   350  func (r Rectangle52_12) Intersect(s Rectangle52_12) Rectangle52_12 {
   351  	if r.Min.X < s.Min.X {
   352  		r.Min.X = s.Min.X
   353  	}
   354  	if r.Min.Y < s.Min.Y {
   355  		r.Min.Y = s.Min.Y
   356  	}
   357  	if r.Max.X > s.Max.X {
   358  		r.Max.X = s.Max.X
   359  	}
   360  	if r.Max.Y > s.Max.Y {
   361  		r.Max.Y = s.Max.Y
   362  	}
   363  	// Letting r0 and s0 be the values of r and s at the time that the method
   364  	// is called, this next line is equivalent to:
   365  	//
   366  	// if max(r0.Min.X, s0.Min.X) >= min(r0.Max.X, s0.Max.X) || likewiseForY { etc }
   367  	if r.Empty() {
   368  		return Rectangle52_12{}
   369  	}
   370  	return r
   371  }
   372  
   373  // Union returns the smallest rectangle that contains both r and s.
   374  func (r Rectangle52_12) Union(s Rectangle52_12) Rectangle52_12 {
   375  	if r.Empty() {
   376  		return s
   377  	}
   378  	if s.Empty() {
   379  		return r
   380  	}
   381  	if r.Min.X > s.Min.X {
   382  		r.Min.X = s.Min.X
   383  	}
   384  	if r.Min.Y > s.Min.Y {
   385  		r.Min.Y = s.Min.Y
   386  	}
   387  	if r.Max.X < s.Max.X {
   388  		r.Max.X = s.Max.X
   389  	}
   390  	if r.Max.Y < s.Max.Y {
   391  		r.Max.Y = s.Max.Y
   392  	}
   393  	return r
   394  }
   395  
   396  // Empty returns whether the rectangle contains no points.
   397  func (r Rectangle52_12) Empty() bool {
   398  	return r.Min.X >= r.Max.X || r.Min.Y >= r.Max.Y
   399  }
   400  
   401  // In returns whether every point in r is in s.
   402  func (r Rectangle52_12) In(s Rectangle52_12) bool {
   403  	if r.Empty() {
   404  		return true
   405  	}
   406  	// Note that r.Max is an exclusive bound for r, so that r.In(s)
   407  	// does not require that r.Max.In(s).
   408  	return s.Min.X <= r.Min.X && r.Max.X <= s.Max.X &&
   409  		s.Min.Y <= r.Min.Y && r.Max.Y <= s.Max.Y
   410  }
   411
View as plain text