Source file test/divmod.go

     1  // run
     2  
     3  // Copyright 2013 The Go Authors. All rights reserved.
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  // Test division of variables. Generate many test cases,
     8  // compute correct answer using shift and subtract,
     9  // and then compare against results from division and
    10  // modulus operators.
    11  //
    12  // Primarily useful for testing software div/mod.
    13  
    14  package main
    15  
    16  const long = false
    17  
    18  func main() {
    19  	if long {
    20  		// About 3e9 test cases (calls to checkdiv3).
    21  		// Too long for everyday testing.
    22  		gen2(3, 64, 2, 64, checkdiv1)
    23  		println(ntest)
    24  	} else {
    25  		// About 4e6 test cases (calls to checkdiv3).
    26  		// Runs for 8 seconds on ARM chromebook, much faster elsewhere.
    27  		gen2(2, 64, 1, 64, checkdiv1)
    28  	}
    29  }
    30  
    31  // generate all uint64 values x where x has at most n bits set in the low w
    32  // and call f(x) for each.
    33  func gen1(n, w int, f func(uint64)) {
    34  	gen(0, 0, n, w-1, f)
    35  }
    36  
    37  func gen(val uint64, nbits, maxbits, pos int, f func(uint64)) {
    38  	if pos < 0 {
    39  		f(val)
    40  		return
    41  	}
    42  	gen(val, nbits, maxbits, pos-1, f)
    43  	if nbits < maxbits {
    44  		gen(val|1<<uint(pos), nbits+1, maxbits, pos-1, f)
    45  	}
    46  }
    47  
    48  // generate all uint64 values x, y where x has at most n1 bits set in the low w1
    49  // and y has at most n2 bits set in the low w2 and call f(x, y) for each.
    50  func gen2(n1, w1, n2, w2 int, f func(uint64, uint64)) {
    51  	gen1(n1, w1, func(x uint64) {
    52  		gen1(n2, w2, func(y uint64) {
    53  			f(x, y)
    54  		})
    55  	})
    56  }
    57  
    58  // x and y are uint64s with at most 2 bits set.
    59  // Check those values and values above and below,
    60  // along with bitwise inversions of the same (done in checkdiv2).
    61  func checkdiv1(x, y uint64) {
    62  	checkdiv2(x, y)
    63  	// If the low bit is set in x or y, adding or subtracting 1
    64  	// produces a number that checkdiv1 is going to be called
    65  	// with anyway, so don't duplicate effort.
    66  	if x&1 == 0 {
    67  		checkdiv2(x+1, y)
    68  		checkdiv2(x-1, y)
    69  	}
    70  	if y&1 == 0 {
    71  		checkdiv2(x, y-1)
    72  		checkdiv2(x, y+1)
    73  		if x&1 == 0 {
    74  			checkdiv2(x+1, y-1)
    75  			checkdiv2(x-1, y-1)
    76  			checkdiv2(x-1, y+1)
    77  			checkdiv2(x+1, y+1)
    78  		}
    79  	}
    80  }
    81  
    82  func checkdiv2(x, y uint64) {
    83  	checkdiv3(x, y)
    84  	checkdiv3(^x, y)
    85  	checkdiv3(x, ^y)
    86  	checkdiv3(^x, ^y)
    87  }
    88  
    89  var ntest int64 = 0
    90  
    91  func checkdiv3(x, y uint64) {
    92  	ntest++
    93  	if ntest&(ntest-1) == 0 && long {
    94  		println(ntest, "...")
    95  	}
    96  	checkuint64(x, y)
    97  	if (uint64(uint32(x)) == x || uint64(uint32(^x)) == ^x) && (uint64(uint32(y)) == y || uint64(uint32(^y)) == ^y) {
    98  		checkuint32(uint32(x), uint32(y))
    99  	}
   100  	if (uint64(uint16(x)) == x || uint64(uint16(^x)) == ^x) && (uint64(uint16(y)) == y || uint64(uint16(^y)) == ^y) {
   101  		checkuint16(uint16(x), uint16(y))
   102  	}
   103  	if (uint64(uint8(x)) == x || uint64(uint8(^x)) == ^x) && (uint64(uint8(y)) == y || uint64(uint8(^y)) == ^y) {
   104  		checkuint8(uint8(x), uint8(y))
   105  	}
   106  
   107  
   108  	sx := int64(x)
   109  	sy := int64(y)
   110  	checkint64(sx, sy)
   111  	if (int64(int32(sx)) == sx || int64(int32(^sx)) == ^sx) && (int64(int32(sy)) == sy || int64(int32(^sy)) == ^sy) {
   112  		checkint32(int32(sx), int32(sy))
   113  	}
   114  	if (int64(int16(sx)) == sx || int64(int16(^sx)) == ^sx) && (int64(int16(sy)) == sy || int64(int16(^sy)) == ^sy) {
   115  		checkint16(int16(sx), int16(sy))
   116  	}
   117  	if (int64(int8(sx)) == sx || int64(int8(^sx)) == ^sx) && (int64(int8(sy)) == sy || int64(int8(^sy)) == ^sy) {
   118  		checkint8(int8(sx), int8(sy))
   119  	}
   120  }
   121  
   122  // Check result of x/y, x%y for various types.
   123  
   124  func checkuint(x, y uint) {
   125  	if y == 0 {
   126  		divzerouint(x, y)
   127  		modzerouint(x, y)
   128  		return
   129  	}
   130  	q, r := udiv(uint64(x), uint64(y))
   131  	q1 := x/y
   132  	r1 := x%y
   133  	if q1 != uint(q) {
   134  		print("uint(", x, "/", y, ") = ", q1, ", want ", q, "\n")
   135  	}
   136  	if r1 != uint(r) {
   137  		print("uint(", x, "%", y, ") = ", r1, ", want ", r, "\n")
   138  	}
   139  }
   140  
   141  func checkuint64(x, y uint64) {
   142  	if y == 0 {
   143  		divzerouint64(x, y)
   144  		modzerouint64(x, y)
   145  		return
   146  	}
   147  	q, r := udiv(x, y)
   148  	q1 := x/y
   149  	r1 := x%y
   150  	if q1 != q {
   151  		print("uint64(", x, "/", y, ") = ", q1, ", want ", q, "\n")
   152  	}
   153  	if r1 != r {
   154  		print("uint64(", x, "%", y, ") = ", r1, ", want ", r, "\n")
   155  	}
   156  }
   157  
   158  func checkuint32(x, y uint32) {
   159  	if y == 0 {
   160  		divzerouint32(x, y)
   161  		modzerouint32(x, y)
   162  		return
   163  	}
   164  	q, r := udiv(uint64(x), uint64(y))
   165  	q1 := x/y
   166  	r1 := x%y
   167  	if q1 != uint32(q) {
   168  		print("uint32(", x, "/", y, ") = ", q1, ", want ", q, "\n")
   169  	}
   170  	if r1 != uint32(r) {
   171  		print("uint32(", x, "%", y, ") = ", r1, ", want ", r, "\n")
   172  	}
   173  }
   174  
   175  func checkuint16(x, y uint16) {
   176  	if y == 0 {
   177  		divzerouint16(x, y)
   178  		modzerouint16(x, y)
   179  		return
   180  	}
   181  	q, r := udiv(uint64(x), uint64(y))
   182  	q1 := x/y
   183  	r1 := x%y
   184  	if q1 != uint16(q) {
   185  		print("uint16(", x, "/", y, ") = ", q1, ", want ", q, "\n")
   186  	}
   187  	if r1 != uint16(r) {
   188  		print("uint16(", x, "%", y, ") = ", r1, ", want ", r, "\n")
   189  	}
   190  }
   191  
   192  func checkuint8(x, y uint8) {
   193  	if y == 0 {
   194  		divzerouint8(x, y)
   195  		modzerouint8(x, y)
   196  		return
   197  	}
   198  	q, r := udiv(uint64(x), uint64(y))
   199  	q1 := x/y
   200  	r1 := x%y
   201  	if q1 != uint8(q) {
   202  		print("uint8(", x, "/", y, ") = ", q1, ", want ", q, "\n")
   203  	}
   204  	if r1 != uint8(r) {
   205  		print("uint8(", x, "%", y, ") = ", r1, ", want ", r, "\n")
   206  	}
   207  }
   208  
   209  func checkint(x, y int) {
   210  	if y == 0 {
   211  		divzeroint(x, y)
   212  		modzeroint(x, y)
   213  		return
   214  	}
   215  	q, r := idiv(int64(x), int64(y))
   216  	q1 := x/y
   217  	r1 := x%y
   218  	if q1 != int(q) {
   219  		print("int(", x, "/", y, ") = ", q1, ", want ", q, "\n")
   220  	}
   221  	if r1 != int(r) {
   222  		print("int(", x, "%", y, ") = ", r1, ", want ", r, "\n")
   223  	}
   224  }
   225  
   226  func checkint64(x, y int64) {
   227  	if y == 0 {
   228  		divzeroint64(x, y)
   229  		modzeroint64(x, y)
   230  		return
   231  	}
   232  	q, r := idiv(x, y)
   233  	q1 := x/y
   234  	r1 := x%y
   235  	if q1 != q {
   236  		print("int64(", x, "/", y, ") = ", q1, ", want ", q, "\n")
   237  	}
   238  	if r1 != r {
   239  		print("int64(", x, "%", y, ") = ", r1, ", want ", r, "\n")
   240  	}
   241  }
   242  
   243  func checkint32(x, y int32) {
   244  	if y == 0 {
   245  		divzeroint32(x, y)
   246  		modzeroint32(x, y)
   247  		return
   248  	}
   249  	q, r := idiv(int64(x), int64(y))
   250  	q1 := x/y
   251  	r1 := x%y
   252  	if q1 != int32(q) {
   253  		print("int32(", x, "/", y, ") = ", q1, ", want ", q, "\n")
   254  	}
   255  	if r1 != int32(r) {
   256  		print("int32(", x, "%", y, ") = ", r1, ", want ", r, "\n")
   257  	}
   258  }
   259  
   260  func checkint16(x, y int16) {
   261  	if y == 0 {
   262  		divzeroint16(x, y)
   263  		modzeroint16(x, y)
   264  		return
   265  	}
   266  	q, r := idiv(int64(x), int64(y))
   267  	q1 := x/y
   268  	r1 := x%y
   269  	if q1 != int16(q) {
   270  		print("int16(", x, "/", y, ") = ", q1, ", want ", q, "\n")
   271  	}
   272  	if r1 != int16(r) {
   273  		print("int16(", x, "%", y, ") = ", r1, ", want ", r, "\n")
   274  	}
   275  }
   276  
   277  func checkint8(x, y int8) {
   278  	if y == 0 {
   279  		divzeroint8(x, y)
   280  		modzeroint8(x, y)
   281  		return
   282  	}
   283  	q, r := idiv(int64(x), int64(y))
   284  	q1 := x/y
   285  	r1 := x%y
   286  	if q1 != int8(q) {
   287  		print("int8(", x, "/", y, ") = ", q1, ", want ", q, "\n")
   288  	}
   289  	if r1 != int8(r) {
   290  		print("int8(", x, "%", y, ") = ", r1, ", want ", r, "\n")
   291  	}
   292  }
   293  
   294  func divzerouint(x, y uint) uint {
   295  	defer checkudivzero("uint", uint64(x))
   296  	return x / y
   297  }
   298  
   299  func divzerouint64(x, y uint64) uint64 {
   300  	defer checkudivzero("uint64", uint64(x))
   301  	return x / y
   302  }
   303  
   304  func divzerouint32(x, y uint32) uint32 {
   305  	defer checkudivzero("uint32", uint64(x))
   306  	return x / y
   307  }
   308  
   309  func divzerouint16(x, y uint16) uint16 {
   310  	defer checkudivzero("uint16", uint64(x))
   311  	return x / y
   312  }
   313  
   314  func divzerouint8(x, y uint8) uint8 {
   315  	defer checkudivzero("uint8", uint64(x))
   316  	return x / y
   317  }
   318  
   319  func checkudivzero(typ string, x uint64) {
   320  	if recover() == nil {
   321  		print(typ, "(", x, " / 0) did not panic")
   322  	}
   323  }
   324  
   325  func divzeroint(x, y int) int {
   326  	defer checkdivzero("int", int64(x))
   327  	return x / y
   328  }
   329  
   330  func divzeroint64(x, y int64) int64 {
   331  	defer checkdivzero("int64", int64(x))
   332  	return x / y
   333  }
   334  
   335  func divzeroint32(x, y int32) int32 {
   336  	defer checkdivzero("int32", int64(x))
   337  	return x / y
   338  }
   339  
   340  func divzeroint16(x, y int16) int16 {
   341  	defer checkdivzero("int16", int64(x))
   342  	return x / y
   343  }
   344  
   345  func divzeroint8(x, y int8) int8 {
   346  	defer checkdivzero("int8", int64(x))
   347  	return x / y
   348  }
   349  
   350  func checkdivzero(typ string, x int64) {
   351  	if recover() == nil {
   352  		print(typ, "(", x, " / 0) did not panic")
   353  	}
   354  }
   355  
   356  func modzerouint(x, y uint) uint {
   357  	defer checkumodzero("uint", uint64(x))
   358  	return x % y
   359  }
   360  
   361  func modzerouint64(x, y uint64) uint64 {
   362  	defer checkumodzero("uint64", uint64(x))
   363  	return x % y
   364  }
   365  
   366  func modzerouint32(x, y uint32) uint32 {
   367  	defer checkumodzero("uint32", uint64(x))
   368  	return x % y
   369  }
   370  
   371  func modzerouint16(x, y uint16) uint16 {
   372  	defer checkumodzero("uint16", uint64(x))
   373  	return x % y
   374  }
   375  
   376  func modzerouint8(x, y uint8) uint8 {
   377  	defer checkumodzero("uint8", uint64(x))
   378  	return x % y
   379  }
   380  
   381  func checkumodzero(typ string, x uint64) {
   382  	if recover() == nil {
   383  		print(typ, "(", x, " % 0) did not panic")
   384  	}
   385  }
   386  
   387  func modzeroint(x, y int) int {
   388  	defer checkmodzero("int", int64(x))
   389  	return x % y
   390  }
   391  
   392  func modzeroint64(x, y int64) int64 {
   393  	defer checkmodzero("int64", int64(x))
   394  	return x % y
   395  }
   396  
   397  func modzeroint32(x, y int32) int32 {
   398  	defer checkmodzero("int32", int64(x))
   399  	return x % y
   400  }
   401  
   402  func modzeroint16(x, y int16) int16 {
   403  	defer checkmodzero("int16", int64(x))
   404  	return x % y
   405  }
   406  
   407  func modzeroint8(x, y int8) int8 {
   408  	defer checkmodzero("int8", int64(x))
   409  	return x % y
   410  }
   411  
   412  func checkmodzero(typ string, x int64) {
   413  	if recover() == nil {
   414  		print(typ, "(", x, " % 0) did not panic")
   415  	}
   416  }
   417  
   418  // unsigned divide and mod using shift and subtract.
   419  func udiv(x, y uint64) (q, r uint64) {
   420  	sh := 0
   421  	for y+y > y && y+y <= x {
   422  		sh++
   423  		y <<= 1
   424  	}
   425  	for ; sh >= 0; sh-- {
   426  		q <<= 1
   427  		if x >= y {
   428  			x -= y
   429  			q |= 1
   430  		}
   431  		y >>= 1
   432  	}
   433  	return q, x
   434  }
   435  
   436  // signed divide and mod: do unsigned and adjust signs.
   437  func idiv(x, y int64) (q, r int64) {
   438  	// special case for minint / -1 = minint
   439  	if x-1 > x && y == -1 {
   440  		return x, 0
   441  	}
   442  	ux := uint64(x)
   443  	uy := uint64(y)
   444  	if x < 0 {
   445  		ux = -ux
   446  	}
   447  	if y < 0 {
   448  		uy = -uy
   449  	}
   450  	uq, ur := udiv(ux, uy)
   451  	q = int64(uq)
   452  	r = int64(ur)
   453  	if x < 0 {
   454  		r = -r
   455  	}
   456  	if (x < 0) != (y < 0) {
   457  		q = -q
   458  	}
   459  	return q, r
   460  }
   461  

View as plain text