Source file src/golang.org/x/image/math/fixed/fixed_test.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
     6  
     7  import (
     8  	"math"
     9  	"math/rand"
    10  	"testing"
    11  )
    12  
    13  var testCases = []struct {
    14  	x      float64
    15  	s26_6  string
    16  	s52_12 string
    17  	floor  int
    18  	round  int
    19  	ceil   int
    20  }{{
    21  	x:      0,
    22  	s26_6:  "0:00",
    23  	s52_12: "0:0000",
    24  	floor:  0,
    25  	round:  0,
    26  	ceil:   0,
    27  }, {
    28  	x:      1,
    29  	s26_6:  "1:00",
    30  	s52_12: "1:0000",
    31  	floor:  1,
    32  	round:  1,
    33  	ceil:   1,
    34  }, {
    35  	x:      1.25,
    36  	s26_6:  "1:16",
    37  	s52_12: "1:1024",
    38  	floor:  1,
    39  	round:  1,
    40  	ceil:   2,
    41  }, {
    42  	x:      2.5,
    43  	s26_6:  "2:32",
    44  	s52_12: "2:2048",
    45  	floor:  2,
    46  	round:  3,
    47  	ceil:   3,
    48  }, {
    49  	x:      63 / 64.0,
    50  	s26_6:  "0:63",
    51  	s52_12: "0:4032",
    52  	floor:  0,
    53  	round:  1,
    54  	ceil:   1,
    55  }, {
    56  	x:      -0.5,
    57  	s26_6:  "-0:32",
    58  	s52_12: "-0:2048",
    59  	floor:  -1,
    60  	round:  +0,
    61  	ceil:   +0,
    62  }, {
    63  	x:      -4.125,
    64  	s26_6:  "-4:08",
    65  	s52_12: "-4:0512",
    66  	floor:  -5,
    67  	round:  -4,
    68  	ceil:   -4,
    69  }, {
    70  	x:      -7.75,
    71  	s26_6:  "-7:48",
    72  	s52_12: "-7:3072",
    73  	floor:  -8,
    74  	round:  -8,
    75  	ceil:   -7,
    76  }}
    77  
    78  func TestInt26_6(t *testing.T) {
    79  	const one = Int26_6(1 << 6)
    80  	for _, tc := range testCases {
    81  		x := Int26_6(tc.x * (1 << 6))
    82  		if got, want := x.String(), tc.s26_6; got != want {
    83  			t.Errorf("tc.x=%v: String: got %q, want %q", tc.x, got, want)
    84  		}
    85  		if got, want := x.Floor(), tc.floor; got != want {
    86  			t.Errorf("tc.x=%v: Floor: got %v, want %v", tc.x, got, want)
    87  		}
    88  		if got, want := x.Round(), tc.round; got != want {
    89  			t.Errorf("tc.x=%v: Round: got %v, want %v", tc.x, got, want)
    90  		}
    91  		if got, want := x.Ceil(), tc.ceil; got != want {
    92  			t.Errorf("tc.x=%v: Ceil: got %v, want %v", tc.x, got, want)
    93  		}
    94  		if got, want := x.Mul(one), x; got != want {
    95  			t.Errorf("tc.x=%v: Mul by one: got %v, want %v", tc.x, got, want)
    96  		}
    97  		if got, want := x.mul(one), x; got != want {
    98  			t.Errorf("tc.x=%v: mul by one: got %v, want %v", tc.x, got, want)
    99  		}
   100  	}
   101  }
   102  
   103  func TestInt52_12(t *testing.T) {
   104  	const one = Int52_12(1 << 12)
   105  	for _, tc := range testCases {
   106  		x := Int52_12(tc.x * (1 << 12))
   107  		if got, want := x.String(), tc.s52_12; got != want {
   108  			t.Errorf("tc.x=%v: String: got %q, want %q", tc.x, got, want)
   109  		}
   110  		if got, want := x.Floor(), tc.floor; got != want {
   111  			t.Errorf("tc.x=%v: Floor: got %v, want %v", tc.x, got, want)
   112  		}
   113  		if got, want := x.Round(), tc.round; got != want {
   114  			t.Errorf("tc.x=%v: Round: got %v, want %v", tc.x, got, want)
   115  		}
   116  		if got, want := x.Ceil(), tc.ceil; got != want {
   117  			t.Errorf("tc.x=%v: Ceil: got %v, want %v", tc.x, got, want)
   118  		}
   119  		if got, want := x.Mul(one), x; got != want {
   120  			t.Errorf("tc.x=%v: Mul by one: got %v, want %v", tc.x, got, want)
   121  		}
   122  	}
   123  }
   124  
   125  var mulTestCases = []struct {
   126  	x      float64
   127  	y      float64
   128  	z26_6  float64 // Equals truncate26_6(x)*truncate26_6(y).
   129  	z52_12 float64 // Equals truncate52_12(x)*truncate52_12(y).
   130  	s26_6  string
   131  	s52_12 string
   132  }{{
   133  	x:      0,
   134  	y:      1.5,
   135  	z26_6:  0,
   136  	z52_12: 0,
   137  	s26_6:  "0:00",
   138  	s52_12: "0:0000",
   139  }, {
   140  	x:      +1.25,
   141  	y:      +4,
   142  	z26_6:  +5,
   143  	z52_12: +5,
   144  	s26_6:  "5:00",
   145  	s52_12: "5:0000",
   146  }, {
   147  	x:      +1.25,
   148  	y:      -4,
   149  	z26_6:  -5,
   150  	z52_12: -5,
   151  	s26_6:  "-5:00",
   152  	s52_12: "-5:0000",
   153  }, {
   154  	x:      -1.25,
   155  	y:      +4,
   156  	z26_6:  -5,
   157  	z52_12: -5,
   158  	s26_6:  "-5:00",
   159  	s52_12: "-5:0000",
   160  }, {
   161  	x:      -1.25,
   162  	y:      -4,
   163  	z26_6:  +5,
   164  	z52_12: +5,
   165  	s26_6:  "5:00",
   166  	s52_12: "5:0000",
   167  }, {
   168  	x:      1.25,
   169  	y:      1.5,
   170  	z26_6:  1.875,
   171  	z52_12: 1.875,
   172  	s26_6:  "1:56",
   173  	s52_12: "1:3584",
   174  }, {
   175  	x:      1234.5,
   176  	y:      -8888.875,
   177  	z26_6:  -10973316.1875,
   178  	z52_12: -10973316.1875,
   179  	s26_6:  "-10973316:12",
   180  	s52_12: "-10973316:0768",
   181  }, {
   182  	x:      1.515625,      // 1 + 33/64 = 97/64
   183  	y:      1.531250,      // 1 + 34/64 = 98/64
   184  	z26_6:  2.32080078125, // 2 + 1314/4096 = 9506/4096
   185  	z52_12: 2.32080078125, // 2 + 1314/4096 = 9506/4096
   186  	s26_6:  "2:21",        // 2.32812500000, which is closer than 2:20 (in decimal, 2.3125)
   187  	s52_12: "2:1314",      // 2.32080078125
   188  }, {
   189  	x:      0.500244140625,     // 2049/4096, approximately 32/64
   190  	y:      0.500732421875,     // 2051/4096, approximately 32/64
   191  	z26_6:  0.25,               // 4194304/16777216, or 1024/4096
   192  	z52_12: 0.2504884600639343, // 4202499/16777216
   193  	s26_6:  "0:16",             // 0.25000000000
   194  	s52_12: "0:1026",           // 0.25048828125, which is closer than 0:1027 (in decimal, 0.250732421875)
   195  }, {
   196  	x:      0.015625,             // 1/64
   197  	y:      0.000244140625,       // 1/4096, approximately 0/64
   198  	z26_6:  0.0,                  // 0
   199  	z52_12: 0.000003814697265625, // 1/262144
   200  	s26_6:  "0:00",               // 0
   201  	s52_12: "0:0000",             // 0, which is closer than 0:0001 (in decimal, 0.000244140625)
   202  }, {
   203  	// Round the Int52_12 calculation down.
   204  	x:      1.44140625,         // 1 + 1808/4096 = 5904/4096, approximately 92/64
   205  	y:      1.44140625,         // 1 + 1808/4096 = 5904/4096, approximately 92/64
   206  	z26_6:  2.06640625,         // 2 +  272/4096 = 8464/4096
   207  	z52_12: 2.0776519775390625, // 2 +  318/4096 +  256/16777216 = 34857216/16777216
   208  	s26_6:  "2:04",             // 2.06250000000, which is closer than 2:05   (in decimal, 2.078125000000)
   209  	s52_12: "2:0318",           // 2.07763671875, which is closer than 2:0319 (in decimal, 2.077880859375)
   210  }, {
   211  	// Round the Int52_12 calculation up.
   212  	x:      1.44140625,         // 1 + 1808/4096 = 5904/4096, approximately 92/64
   213  	y:      1.441650390625,     // 1 + 1809/4096 = 5905/4096, approximately 92/64
   214  	z26_6:  2.06640625,         // 2 +  272/4096 = 8464/4096
   215  	z52_12: 2.0780038833618164, // 2 +  319/4096 + 2064/16777216 = 34863120/16777216
   216  	s26_6:  "2:04",             // 2.06250000000, which is closer than 2:05   (in decimal, 2.078125000000)
   217  	s52_12: "2:0320",           // 2.07812500000, which is closer than 2:0319 (in decimal, 2.077880859375)
   218  }}
   219  
   220  func TestInt26_6Mul(t *testing.T) {
   221  	for _, tc := range mulTestCases {
   222  		x := Int26_6(tc.x * (1 << 6))
   223  		y := Int26_6(tc.y * (1 << 6))
   224  		if z := float64(x) * float64(y) / (1 << 12); z != tc.z26_6 {
   225  			t.Errorf("tc.x=%v, tc.y=%v: z: got %v, want %v", tc.x, tc.y, z, tc.z26_6)
   226  			continue
   227  		}
   228  		if got, want := x.Mul(y).String(), tc.s26_6; got != want {
   229  			t.Errorf("tc.x=%v: Mul: got %q, want %q", tc.x, got, want)
   230  		}
   231  	}
   232  }
   233  
   234  func TestInt52_12Mul(t *testing.T) {
   235  	for _, tc := range mulTestCases {
   236  		x := Int52_12(tc.x * (1 << 12))
   237  		y := Int52_12(tc.y * (1 << 12))
   238  		if z := float64(x) * float64(y) / (1 << 24); z != tc.z52_12 {
   239  			t.Errorf("tc.x=%v, tc.y=%v: z: got %v, want %v", tc.x, tc.y, z, tc.z52_12)
   240  			continue
   241  		}
   242  		if got, want := x.Mul(y).String(), tc.s52_12; got != want {
   243  			t.Errorf("tc.x=%v: Mul: got %q, want %q", tc.x, got, want)
   244  		}
   245  	}
   246  }
   247  
   248  func TestInt26_6MulByOneMinusIota(t *testing.T) {
   249  	const (
   250  		totalBits = 32
   251  		fracBits  = 6
   252  
   253  		oneMinusIota  = Int26_6(1<<fracBits) - 1
   254  		oneMinusIotaF = float64(oneMinusIota) / (1 << fracBits)
   255  	)
   256  
   257  	for _, neg := range []bool{false, true} {
   258  		for i := uint(0); i < totalBits; i++ {
   259  			x := Int26_6(1 << i)
   260  			if neg {
   261  				x = -x
   262  			} else if i == totalBits-1 {
   263  				// A signed int32 can't represent 1<<31.
   264  				continue
   265  			}
   266  
   267  			// want equals x * oneMinusIota, rounded to nearest.
   268  			want := Int26_6(0)
   269  			if -1<<fracBits < x && x < 1<<fracBits {
   270  				// (x * oneMinusIota) isn't exactly representable as an
   271  				// Int26_6. Calculate the rounded value using float64 math.
   272  				xF := float64(x) / (1 << fracBits)
   273  				wantF := xF * oneMinusIotaF * (1 << fracBits)
   274  				want = Int26_6(math.Floor(wantF + 0.5))
   275  			} else {
   276  				// (x * oneMinusIota) is exactly representable.
   277  				want = oneMinusIota << (i - fracBits)
   278  				if neg {
   279  					want = -want
   280  				}
   281  			}
   282  
   283  			if got := x.Mul(oneMinusIota); got != want {
   284  				t.Errorf("neg=%t, i=%d, x=%v, Mul: got %v, want %v", neg, i, x, got, want)
   285  			}
   286  			if got := x.mul(oneMinusIota); got != want {
   287  				t.Errorf("neg=%t, i=%d, x=%v, mul: got %v, want %v", neg, i, x, got, want)
   288  			}
   289  		}
   290  	}
   291  }
   292  
   293  func TestInt52_12MulByOneMinusIota(t *testing.T) {
   294  	const (
   295  		totalBits = 64
   296  		fracBits  = 12
   297  
   298  		oneMinusIota  = Int52_12(1<<fracBits) - 1
   299  		oneMinusIotaF = float64(oneMinusIota) / (1 << fracBits)
   300  	)
   301  
   302  	for _, neg := range []bool{false, true} {
   303  		for i := uint(0); i < totalBits; i++ {
   304  			x := Int52_12(1 << i)
   305  			if neg {
   306  				x = -x
   307  			} else if i == totalBits-1 {
   308  				// A signed int64 can't represent 1<<63.
   309  				continue
   310  			}
   311  
   312  			// want equals x * oneMinusIota, rounded to nearest.
   313  			want := Int52_12(0)
   314  			if -1<<fracBits < x && x < 1<<fracBits {
   315  				// (x * oneMinusIota) isn't exactly representable as an
   316  				// Int52_12. Calculate the rounded value using float64 math.
   317  				xF := float64(x) / (1 << fracBits)
   318  				wantF := xF * oneMinusIotaF * (1 << fracBits)
   319  				want = Int52_12(math.Floor(wantF + 0.5))
   320  			} else {
   321  				// (x * oneMinusIota) is exactly representable.
   322  				want = oneMinusIota << (i - fracBits)
   323  				if neg {
   324  					want = -want
   325  				}
   326  			}
   327  
   328  			if got := x.Mul(oneMinusIota); got != want {
   329  				t.Errorf("neg=%t, i=%d, x=%v, Mul: got %v, want %v", neg, i, x, got, want)
   330  			}
   331  		}
   332  	}
   333  }
   334  
   335  func TestInt26_6MulVsMul(t *testing.T) {
   336  	rng := rand.New(rand.NewSource(1))
   337  	for i := 0; i < 10000; i++ {
   338  		u := Int26_6(rng.Uint32())
   339  		v := Int26_6(rng.Uint32())
   340  		Mul := u.Mul(v)
   341  		mul := u.mul(v)
   342  		if Mul != mul {
   343  			t.Errorf("u=%#08x, v=%#08x: Mul=%#08x and mul=%#08x differ",
   344  				uint32(u), uint32(v), uint32(Mul), uint32(mul))
   345  		}
   346  	}
   347  }
   348  
   349  func TestMuli32(t *testing.T) {
   350  	rng := rand.New(rand.NewSource(2))
   351  	for i := 0; i < 10000; i++ {
   352  		u := int32(rng.Uint32())
   353  		v := int32(rng.Uint32())
   354  		lo, hi := muli32(u, v)
   355  		got := uint64(lo) | uint64(hi)<<32
   356  		want := uint64(int64(u) * int64(v))
   357  		if got != want {
   358  			t.Errorf("u=%#08x, v=%#08x: got %#016x, want %#016x", uint32(u), uint32(v), got, want)
   359  		}
   360  	}
   361  }
   362  
   363  func TestMulu32(t *testing.T) {
   364  	rng := rand.New(rand.NewSource(3))
   365  	for i := 0; i < 10000; i++ {
   366  		u := rng.Uint32()
   367  		v := rng.Uint32()
   368  		lo, hi := mulu32(u, v)
   369  		got := uint64(lo) | uint64(hi)<<32
   370  		want := uint64(u) * uint64(v)
   371  		if got != want {
   372  			t.Errorf("u=%#08x, v=%#08x: got %#016x, want %#016x", u, v, got, want)
   373  		}
   374  	}
   375  }
   376  
   377  // mul (with a lower case 'm') is an alternative implementation of Int26_6.Mul
   378  // (with an upper case 'M'). It has the same structure as the Int52_12.Mul
   379  // implementation, but Int26_6.mul is easier to test since Go has built-in
   380  // 64-bit integers.
   381  func (x Int26_6) mul(y Int26_6) Int26_6 {
   382  	const M, N = 26, 6
   383  	lo, hi := muli32(int32(x), int32(y))
   384  	ret := Int26_6(hi<<M | lo>>N)
   385  	ret += Int26_6((lo >> (N - 1)) & 1) // Round to nearest, instead of rounding down.
   386  	return ret
   387  }
   388  
   389  // muli32 multiplies two int32 values, returning the 64-bit signed integer
   390  // result as two uint32 values.
   391  //
   392  // muli32 isn't used directly by this package, but it has the same structure as
   393  // muli64, and muli32 is easier to test since Go has built-in 64-bit integers.
   394  func muli32(u, v int32) (lo, hi uint32) {
   395  	const (
   396  		s    = 16
   397  		mask = 1<<s - 1
   398  	)
   399  
   400  	u1 := uint32(u >> s)
   401  	u0 := uint32(u & mask)
   402  	v1 := uint32(v >> s)
   403  	v0 := uint32(v & mask)
   404  
   405  	w0 := u0 * v0
   406  	t := u1*v0 + w0>>s
   407  	w1 := t & mask
   408  	w2 := uint32(int32(t) >> s)
   409  	w1 += u0 * v1
   410  	return uint32(u) * uint32(v), u1*v1 + w2 + uint32(int32(w1)>>s)
   411  }
   412  
   413  // mulu32 is like muli32, except that it multiplies unsigned instead of signed
   414  // values.
   415  //
   416  // This implementation comes from $GOROOT/src/runtime/softfloat64.go's mullu
   417  // function, which is in turn adapted from Hacker's Delight.
   418  //
   419  // mulu32 (and its corresponding test, TestMulu32) isn't used directly by this
   420  // package. It is provided in this test file as a reference point to compare
   421  // the muli32 (and TestMuli32) implementations against.
   422  func mulu32(u, v uint32) (lo, hi uint32) {
   423  	const (
   424  		s    = 16
   425  		mask = 1<<s - 1
   426  	)
   427  
   428  	u0 := u & mask
   429  	u1 := u >> s
   430  	v0 := v & mask
   431  	v1 := v >> s
   432  
   433  	w0 := u0 * v0
   434  	t := u1*v0 + w0>>s
   435  	w1 := t & mask
   436  	w2 := t >> s
   437  	w1 += u0 * v1
   438  	return u * v, u1*v1 + w2 + w1>>s
   439  }
   440  

View as plain text