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.
6package fixed // import "golang.org/x/image/math/fixed"
7
8import (
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).
17func 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).
27type 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".
32func (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.
47func (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.
52func (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.
57func (x Int26_6) Ceil() int { return int((x + 0x3f) >> 6) }
58
59// Mul returns x*y in 26.6 fixed-point arithmetic.
60func (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).
70type 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".
76func (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.
91func (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.
96func (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.
101func (x Int52_12) Ceil() int { return int((x + 0xfff) >> 12) }
102
103// Mul returns x*y in 52.12 fixed-point arithmetic.
104func (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.
117func 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}.
139func 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.
146type Point26_6 struct {
147 X, Y Int26_6
148}
149
150// Add returns the vector p+q.
151func (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.
156func (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.
161func (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.
166func (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.
171func (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.
178type Point52_12 struct {
179 X, Y Int52_12
180}
181
182// Add returns the vector p+q.
183func (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.
188func (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.
193func (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.
198func (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.
203func (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.
215func 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.
239type Rectangle26_6 struct {
240 Min, Max Point26_6
241}
242
243// Add returns the rectangle r translated by p.
244func (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.
252func (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.
261func (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.
285func (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.
308func (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.
313func (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.
328type Rectangle52_12 struct {
329 Min, Max Point52_12
330}
331
332// Add returns the rectangle r translated by p.
333func (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.
341func (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.
350func (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.
374func (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.
397func (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.
402func (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}