magic_test.go

     1  // Copyright 2017 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 ssa
     6  
     7  import (
     8  	"math/big"
     9  	"testing"
    10  )
    11  
    12  func TestMagicExhaustive8(t *testing.T) {
    13  	testMagicExhaustive(t, 8)
    14  }
    15  func TestMagicExhaustive8U(t *testing.T) {
    16  	testMagicExhaustiveU(t, 8)
    17  }
    18  func TestMagicExhaustive16(t *testing.T) {
    19  	if testing.Short() {
    20  		t.Skip("slow test; skipping")
    21  	}
    22  	testMagicExhaustive(t, 16)
    23  }
    24  func TestMagicExhaustive16U(t *testing.T) {
    25  	if testing.Short() {
    26  		t.Skip("slow test; skipping")
    27  	}
    28  	testMagicExhaustiveU(t, 16)
    29  }
    30  
    31  // exhaustive test of magic for n bits
    32  func testMagicExhaustive(t *testing.T, n uint) {
    33  	min := -int64(1) << (n - 1)
    34  	max := int64(1) << (n - 1)
    35  	for c := int64(1); c < max; c++ {
    36  		if !smagicOK(n, int64(c)) {
    37  			continue
    38  		}
    39  		m := int64(smagic(n, c).m)
    40  		s := smagic(n, c).s
    41  		for i := min; i < max; i++ {
    42  			want := i / c
    43  			got := (i * m) >> (n + uint(s))
    44  			if i < 0 {
    45  				got++
    46  			}
    47  			if want != got {
    48  				t.Errorf("signed magic wrong for %d / %d: got %d, want %d (m=%d,s=%d)\n", i, c, got, want, m, s)
    49  			}
    50  		}
    51  	}
    52  }
    53  func testMagicExhaustiveU(t *testing.T, n uint) {
    54  	max := uint64(1) << n
    55  	for c := uint64(1); c < max; c++ {
    56  		if !umagicOK(n, int64(c)) {
    57  			continue
    58  		}
    59  		m := umagic(n, int64(c)).m
    60  		s := umagic(n, int64(c)).s
    61  		for i := uint64(0); i < max; i++ {
    62  			want := i / c
    63  			got := (i * (max + m)) >> (n + uint(s))
    64  			if want != got {
    65  				t.Errorf("unsigned magic wrong for %d / %d: got %d, want %d (m=%d,s=%d)\n", i, c, got, want, m, s)
    66  			}
    67  		}
    68  	}
    69  }
    70  
    71  func TestMagicUnsigned(t *testing.T) {
    72  	One := new(big.Int).SetUint64(1)
    73  	for _, n := range [...]uint{8, 16, 32, 64} {
    74  		TwoN := new(big.Int).Lsh(One, n)
    75  		Max := new(big.Int).Sub(TwoN, One)
    76  		for _, c := range [...]uint64{
    77  			3,
    78  			5,
    79  			6,
    80  			7,
    81  			9,
    82  			10,
    83  			11,
    84  			12,
    85  			13,
    86  			14,
    87  			15,
    88  			17,
    89  			1<<8 - 1,
    90  			1<<8 + 1,
    91  			1<<16 - 1,
    92  			1<<16 + 1,
    93  			1<<32 - 1,
    94  			1<<32 + 1,
    95  			1<<64 - 1,
    96  		} {
    97  			if c>>n != 0 {
    98  				continue // not appropriate for the given n.
    99  			}
   100  			if !umagicOK(n, int64(c)) {
   101  				t.Errorf("expected n=%d c=%d to pass\n", n, c)
   102  			}
   103  			m := umagic(n, int64(c)).m
   104  			s := umagic(n, int64(c)).s
   105  
   106  			C := new(big.Int).SetUint64(c)
   107  			M := new(big.Int).SetUint64(m)
   108  			M.Add(M, TwoN)
   109  
   110  			// Find largest multiple of c.
   111  			Mul := new(big.Int).Div(Max, C)
   112  			Mul.Mul(Mul, C)
   113  			mul := Mul.Uint64()
   114  
   115  			// Try some input values, mostly around multiples of c.
   116  			for _, x := range [...]uint64{0, 1,
   117  				c - 1, c, c + 1,
   118  				2*c - 1, 2 * c, 2*c + 1,
   119  				mul - 1, mul, mul + 1,
   120  				uint64(1)<<n - 1,
   121  			} {
   122  				X := new(big.Int).SetUint64(x)
   123  				if X.Cmp(Max) > 0 {
   124  					continue
   125  				}
   126  				Want := new(big.Int).Quo(X, C)
   127  				Got := new(big.Int).Mul(X, M)
   128  				Got.Rsh(Got, n+uint(s))
   129  				if Want.Cmp(Got) != 0 {
   130  					t.Errorf("umagic for %d/%d n=%d doesn't work, got=%s, want %s\n", x, c, n, Got, Want)
   131  				}
   132  			}
   133  		}
   134  	}
   135  }
   136  
   137  func TestMagicSigned(t *testing.T) {
   138  	One := new(big.Int).SetInt64(1)
   139  	for _, n := range [...]uint{8, 16, 32, 64} {
   140  		TwoNMinusOne := new(big.Int).Lsh(One, n-1)
   141  		Max := new(big.Int).Sub(TwoNMinusOne, One)
   142  		Min := new(big.Int).Neg(TwoNMinusOne)
   143  		for _, c := range [...]int64{
   144  			3,
   145  			5,
   146  			6,
   147  			7,
   148  			9,
   149  			10,
   150  			11,
   151  			12,
   152  			13,
   153  			14,
   154  			15,
   155  			17,
   156  			1<<7 - 1,
   157  			1<<7 + 1,
   158  			1<<15 - 1,
   159  			1<<15 + 1,
   160  			1<<31 - 1,
   161  			1<<31 + 1,
   162  			1<<63 - 1,
   163  		} {
   164  			if c>>(n-1) != 0 {
   165  				continue // not appropriate for the given n.
   166  			}
   167  			if !smagicOK(n, int64(c)) {
   168  				t.Errorf("expected n=%d c=%d to pass\n", n, c)
   169  			}
   170  			m := smagic(n, int64(c)).m
   171  			s := smagic(n, int64(c)).s
   172  
   173  			C := new(big.Int).SetInt64(c)
   174  			M := new(big.Int).SetUint64(m)
   175  
   176  			// Find largest multiple of c.
   177  			Mul := new(big.Int).Div(Max, C)
   178  			Mul.Mul(Mul, C)
   179  			mul := Mul.Int64()
   180  
   181  			// Try some input values, mostly around multiples of c.
   182  			for _, x := range [...]int64{
   183  				-1, 1,
   184  				-c - 1, -c, -c + 1, c - 1, c, c + 1,
   185  				-2*c - 1, -2 * c, -2*c + 1, 2*c - 1, 2 * c, 2*c + 1,
   186  				-mul - 1, -mul, -mul + 1, mul - 1, mul, mul + 1,
   187  				int64(1)<<(n-1) - 1, -int64(1) << (n - 1),
   188  			} {
   189  				X := new(big.Int).SetInt64(x)
   190  				if X.Cmp(Min) < 0 || X.Cmp(Max) > 0 {
   191  					continue
   192  				}
   193  				Want := new(big.Int).Quo(X, C)
   194  				Got := new(big.Int).Mul(X, M)
   195  				Got.Rsh(Got, n+uint(s))
   196  				if x < 0 {
   197  					Got.Add(Got, One)
   198  				}
   199  				if Want.Cmp(Got) != 0 {
   200  					t.Errorf("smagic for %d/%d n=%d doesn't work, got=%s, want %s\n", x, c, n, Got, Want)
   201  				}
   202  			}
   203  		}
   204  	}
   205  }
   206  
   207  func testDivisibleExhaustiveU(t *testing.T, n uint) {
   208  	maxU := uint64(1) << n
   209  	for c := uint64(1); c < maxU; c++ {
   210  		if !udivisibleOK(n, int64(c)) {
   211  			continue
   212  		}
   213  		k := udivisible(n, int64(c)).k
   214  		m := udivisible(n, int64(c)).m
   215  		max := udivisible(n, int64(c)).max
   216  		mask := ^uint64(0) >> (64 - n)
   217  		for i := uint64(0); i < maxU; i++ {
   218  			want := i%c == 0
   219  			mul := (i * m) & mask
   220  			rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
   221  			got := rot <= max
   222  			if want != got {
   223  				t.Errorf("unsigned divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,max=%d)\n", i, c, got, want, k, m, max)
   224  			}
   225  		}
   226  	}
   227  }
   228  
   229  func TestDivisibleExhaustive8U(t *testing.T) {
   230  	testDivisibleExhaustiveU(t, 8)
   231  }
   232  
   233  func TestDivisibleExhaustive16U(t *testing.T) {
   234  	if testing.Short() {
   235  		t.Skip("slow test; skipping")
   236  	}
   237  	testDivisibleExhaustiveU(t, 16)
   238  }
   239  
   240  func TestDivisibleUnsigned(t *testing.T) {
   241  	One := new(big.Int).SetUint64(1)
   242  	for _, n := range [...]uint{8, 16, 32, 64} {
   243  		TwoN := new(big.Int).Lsh(One, n)
   244  		Max := new(big.Int).Sub(TwoN, One)
   245  		for _, c := range [...]uint64{
   246  			3,
   247  			5,
   248  			6,
   249  			7,
   250  			9,
   251  			10,
   252  			11,
   253  			12,
   254  			13,
   255  			14,
   256  			15,
   257  			17,
   258  			1<<8 - 1,
   259  			1<<8 + 1,
   260  			1<<16 - 1,
   261  			1<<16 + 1,
   262  			1<<32 - 1,
   263  			1<<32 + 1,
   264  			1<<64 - 1,
   265  		} {
   266  			if c>>n != 0 {
   267  				continue // c too large for the given n.
   268  			}
   269  			if !udivisibleOK(n, int64(c)) {
   270  				t.Errorf("expected n=%d c=%d to pass\n", n, c)
   271  			}
   272  			k := udivisible(n, int64(c)).k
   273  			m := udivisible(n, int64(c)).m
   274  			max := udivisible(n, int64(c)).max
   275  			mask := ^uint64(0) >> (64 - n)
   276  
   277  			C := new(big.Int).SetUint64(c)
   278  
   279  			// Find largest multiple of c.
   280  			Mul := new(big.Int).Div(Max, C)
   281  			Mul.Mul(Mul, C)
   282  			mul := Mul.Uint64()
   283  
   284  			// Try some input values, mostly around multiples of c.
   285  			for _, x := range [...]uint64{0, 1,
   286  				c - 1, c, c + 1,
   287  				2*c - 1, 2 * c, 2*c + 1,
   288  				mul - 1, mul, mul + 1,
   289  				uint64(1)<<n - 1,
   290  			} {
   291  				X := new(big.Int).SetUint64(x)
   292  				if X.Cmp(Max) > 0 {
   293  					continue
   294  				}
   295  				want := x%c == 0
   296  				mul := (x * m) & mask
   297  				rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
   298  				got := rot <= max
   299  				if want != got {
   300  					t.Errorf("unsigned divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,max=%d)\n", x, c, got, want, k, m, max)
   301  				}
   302  			}
   303  		}
   304  	}
   305  }
   306  
   307  func testDivisibleExhaustive(t *testing.T, n uint) {
   308  	minI := -int64(1) << (n - 1)
   309  	maxI := int64(1) << (n - 1)
   310  	for c := int64(1); c < maxI; c++ {
   311  		if !sdivisibleOK(n, int64(c)) {
   312  			continue
   313  		}
   314  		k := sdivisible(n, int64(c)).k
   315  		m := sdivisible(n, int64(c)).m
   316  		a := sdivisible(n, int64(c)).a
   317  		max := sdivisible(n, int64(c)).max
   318  		mask := ^uint64(0) >> (64 - n)
   319  		for i := minI; i < maxI; i++ {
   320  			want := i%c == 0
   321  			mul := (uint64(i)*m + a) & mask
   322  			rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
   323  			got := rot <= max
   324  			if want != got {
   325  				t.Errorf("signed divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,a=%d,max=%d)\n", i, c, got, want, k, m, a, max)
   326  			}
   327  		}
   328  	}
   329  }
   330  
   331  func TestDivisibleExhaustive8(t *testing.T) {
   332  	testDivisibleExhaustive(t, 8)
   333  }
   334  
   335  func TestDivisibleExhaustive16(t *testing.T) {
   336  	if testing.Short() {
   337  		t.Skip("slow test; skipping")
   338  	}
   339  	testDivisibleExhaustive(t, 16)
   340  }
   341  
   342  func TestDivisibleSigned(t *testing.T) {
   343  	One := new(big.Int).SetInt64(1)
   344  	for _, n := range [...]uint{8, 16, 32, 64} {
   345  		TwoNMinusOne := new(big.Int).Lsh(One, n-1)
   346  		Max := new(big.Int).Sub(TwoNMinusOne, One)
   347  		Min := new(big.Int).Neg(TwoNMinusOne)
   348  		for _, c := range [...]int64{
   349  			3,
   350  			5,
   351  			6,
   352  			7,
   353  			9,
   354  			10,
   355  			11,
   356  			12,
   357  			13,
   358  			14,
   359  			15,
   360  			17,
   361  			1<<7 - 1,
   362  			1<<7 + 1,
   363  			1<<15 - 1,
   364  			1<<15 + 1,
   365  			1<<31 - 1,
   366  			1<<31 + 1,
   367  			1<<63 - 1,
   368  		} {
   369  			if c>>(n-1) != 0 {
   370  				continue // not appropriate for the given n.
   371  			}
   372  			if !sdivisibleOK(n, int64(c)) {
   373  				t.Errorf("expected n=%d c=%d to pass\n", n, c)
   374  			}
   375  			k := sdivisible(n, int64(c)).k
   376  			m := sdivisible(n, int64(c)).m
   377  			a := sdivisible(n, int64(c)).a
   378  			max := sdivisible(n, int64(c)).max
   379  			mask := ^uint64(0) >> (64 - n)
   380  
   381  			C := new(big.Int).SetInt64(c)
   382  
   383  			// Find largest multiple of c.
   384  			Mul := new(big.Int).Div(Max, C)
   385  			Mul.Mul(Mul, C)
   386  			mul := Mul.Int64()
   387  
   388  			// Try some input values, mostly around multiples of c.
   389  			for _, x := range [...]int64{
   390  				-1, 1,
   391  				-c - 1, -c, -c + 1, c - 1, c, c + 1,
   392  				-2*c - 1, -2 * c, -2*c + 1, 2*c - 1, 2 * c, 2*c + 1,
   393  				-mul - 1, -mul, -mul + 1, mul - 1, mul, mul + 1,
   394  				int64(1)<<(n-1) - 1, -int64(1) << (n - 1),
   395  			} {
   396  				X := new(big.Int).SetInt64(x)
   397  				if X.Cmp(Min) < 0 || X.Cmp(Max) > 0 {
   398  					continue
   399  				}
   400  				want := x%c == 0
   401  				mul := (uint64(x)*m + a) & mask
   402  				rot := (mul>>uint(k) | mul<<(n-uint(k))) & mask
   403  				got := rot <= max
   404  				if want != got {
   405  					t.Errorf("signed divisible wrong for %d %% %d == 0: got %v, want %v (k=%d,m=%d,a=%d,max=%d)\n", x, c, got, want, k, m, a, max)
   406  				}
   407  			}
   408  		}
   409  	}
   410  }
   411
View as plain text