go divmod 源码

golang divmod 代码

文件路径：/test/divmod.go

// run

// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Test division of variables. Generate many test cases,
// compute correct answer using shift and subtract,
// and then compare against results from division and
// modulus operators.
//
// Primarily useful for testing software div/mod.

package main

const long = false

func main() {
	if long {
		// About 3e9 test cases (calls to checkdiv3).
		// Too long for everyday testing.
		gen2(3, 64, 2, 64, checkdiv1)
		println(ntest)
	} else {
		// About 4e6 test cases (calls to checkdiv3).
		// Runs for 8 seconds on ARM chromebook, much faster elsewhere.
		gen2(2, 64, 1, 64, checkdiv1)
	}
}

// generate all uint64 values x where x has at most n bits set in the low w
// and call f(x) for each.
func gen1(n, w int, f func(uint64)) {
	gen(0, 0, n, w-1, f)
}

func gen(val uint64, nbits, maxbits, pos int, f func(uint64)) {
	if pos < 0 {
		f(val)
		return
	}
	gen(val, nbits, maxbits, pos-1, f)
	if nbits < maxbits {
		gen(val|1<<uint(pos), nbits+1, maxbits, pos-1, f)
	}
}

// generate all uint64 values x, y where x has at most n1 bits set in the low w1
// and y has at most n2 bits set in the low w2 and call f(x, y) for each.
func gen2(n1, w1, n2, w2 int, f func(uint64, uint64)) {
	gen1(n1, w1, func(x uint64) {
		gen1(n2, w2, func(y uint64) {
			f(x, y)
		})
	})
}

// x and y are uint64s with at most 2 bits set.
// Check those values and values above and below,
// along with bitwise inversions of the same (done in checkdiv2).
func checkdiv1(x, y uint64) {
	checkdiv2(x, y)
	// If the low bit is set in x or y, adding or subtracting 1
	// produces a number that checkdiv1 is going to be called
	// with anyway, so don't duplicate effort.
	if x&1 == 0 {
		checkdiv2(x+1, y)
		checkdiv2(x-1, y)
	}
	if y&1 == 0 {
		checkdiv2(x, y-1)
		checkdiv2(x, y+1)
		if x&1 == 0 {
			checkdiv2(x+1, y-1)
			checkdiv2(x-1, y-1)
			checkdiv2(x-1, y+1)
			checkdiv2(x+1, y+1)
		}
	}
}

func checkdiv2(x, y uint64) {
	checkdiv3(x, y)
	checkdiv3(^x, y)
	checkdiv3(x, ^y)
	checkdiv3(^x, ^y)
}

var ntest int64 = 0

func checkdiv3(x, y uint64) {
	ntest++
	if ntest&(ntest-1) == 0 && long {
		println(ntest, "...")
	}
	checkuint64(x, y)
	if (uint64(uint32(x)) == x || uint64(uint32(^x)) == ^x) && (uint64(uint32(y)) == y || uint64(uint32(^y)) == ^y) {
		checkuint32(uint32(x), uint32(y))
	}
	if (uint64(uint16(x)) == x || uint64(uint16(^x)) == ^x) && (uint64(uint16(y)) == y || uint64(uint16(^y)) == ^y) {
		checkuint16(uint16(x), uint16(y))
	}
	if (uint64(uint8(x)) == x || uint64(uint8(^x)) == ^x) && (uint64(uint8(y)) == y || uint64(uint8(^y)) == ^y) {
		checkuint8(uint8(x), uint8(y))
	}
	
	
	sx := int64(x)
	sy := int64(y)
	checkint64(sx, sy)
	if (int64(int32(sx)) == sx || int64(int32(^sx)) == ^sx) && (int64(int32(sy)) == sy || int64(int32(^sy)) == ^sy) {
		checkint32(int32(sx), int32(sy))
	}
	if (int64(int16(sx)) == sx || int64(int16(^sx)) == ^sx) && (int64(int16(sy)) == sy || int64(int16(^sy)) == ^sy) {
		checkint16(int16(sx), int16(sy))
	}
	if (int64(int8(sx)) == sx || int64(int8(^sx)) == ^sx) && (int64(int8(sy)) == sy || int64(int8(^sy)) == ^sy) {
		checkint8(int8(sx), int8(sy))
	}
}

// Check result of x/y, x%y for various types.

func checkuint(x, y uint) {
	if y == 0 {
		divzerouint(x, y)
		modzerouint(x, y)
		return
	}
	q, r := udiv(uint64(x), uint64(y))
	q1 := x/y
	r1 := x%y
	if q1 != uint(q) {
		print("uint(", x, "/", y, ") = ", q1, ", want ", q, "\n")
	}
	if r1 != uint(r) {
		print("uint(", x, "%", y, ") = ", r1, ", want ", r, "\n")
	}
}

func checkuint64(x, y uint64) {
	if y == 0 {
		divzerouint64(x, y)
		modzerouint64(x, y)
		return
	}
	q, r := udiv(x, y)
	q1 := x/y
	r1 := x%y
	if q1 != q {
		print("uint64(", x, "/", y, ") = ", q1, ", want ", q, "\n")
	}
	if r1 != r {
		print("uint64(", x, "%", y, ") = ", r1, ", want ", r, "\n")
	}
}

func checkuint32(x, y uint32) {
	if y == 0 {
		divzerouint32(x, y)
		modzerouint32(x, y)
		return
	}
	q, r := udiv(uint64(x), uint64(y))
	q1 := x/y
	r1 := x%y
	if q1 != uint32(q) {
		print("uint32(", x, "/", y, ") = ", q1, ", want ", q, "\n")
	}
	if r1 != uint32(r) {
		print("uint32(", x, "%", y, ") = ", r1, ", want ", r, "\n")
	}
}

func checkuint16(x, y uint16) {
	if y == 0 {
		divzerouint16(x, y)
		modzerouint16(x, y)
		return
	}
	q, r := udiv(uint64(x), uint64(y))
	q1 := x/y
	r1 := x%y
	if q1 != uint16(q) {
		print("uint16(", x, "/", y, ") = ", q1, ", want ", q, "\n")
	}
	if r1 != uint16(r) {
		print("uint16(", x, "%", y, ") = ", r1, ", want ", r, "\n")
	}
}

func checkuint8(x, y uint8) {
	if y == 0 {
		divzerouint8(x, y)
		modzerouint8(x, y)
		return
	}
	q, r := udiv(uint64(x), uint64(y))
	q1 := x/y
	r1 := x%y
	if q1 != uint8(q) {
		print("uint8(", x, "/", y, ") = ", q1, ", want ", q, "\n")
	}
	if r1 != uint8(r) {
		print("uint8(", x, "%", y, ") = ", r1, ", want ", r, "\n")
	}
}

func checkint(x, y int) {
	if y == 0 {
		divzeroint(x, y)
		modzeroint(x, y)
		return
	}
	q, r := idiv(int64(x), int64(y))
	q1 := x/y
	r1 := x%y
	if q1 != int(q) {
		print("int(", x, "/", y, ") = ", q1, ", want ", q, "\n")
	}
	if r1 != int(r) {
		print("int(", x, "%", y, ") = ", r1, ", want ", r, "\n")
	}
}

func checkint64(x, y int64) {
	if y == 0 {
		divzeroint64(x, y)
		modzeroint64(x, y)
		return
	}
	q, r := idiv(x, y)
	q1 := x/y
	r1 := x%y
	if q1 != q {
		print("int64(", x, "/", y, ") = ", q1, ", want ", q, "\n")
	}
	if r1 != r {
		print("int64(", x, "%", y, ") = ", r1, ", want ", r, "\n")
	}
}

func checkint32(x, y int32) {
	if y == 0 {
		divzeroint32(x, y)
		modzeroint32(x, y)
		return
	}
	q, r := idiv(int64(x), int64(y))
	q1 := x/y
	r1 := x%y
	if q1 != int32(q) {
		print("int32(", x, "/", y, ") = ", q1, ", want ", q, "\n")
	}
	if r1 != int32(r) {
		print("int32(", x, "%", y, ") = ", r1, ", want ", r, "\n")
	}
}

func checkint16(x, y int16) {
	if y == 0 {
		divzeroint16(x, y)
		modzeroint16(x, y)
		return
	}
	q, r := idiv(int64(x), int64(y))
	q1 := x/y
	r1 := x%y
	if q1 != int16(q) {
		print("int16(", x, "/", y, ") = ", q1, ", want ", q, "\n")
	}
	if r1 != int16(r) {
		print("int16(", x, "%", y, ") = ", r1, ", want ", r, "\n")
	}
}

func checkint8(x, y int8) {
	if y == 0 {
		divzeroint8(x, y)
		modzeroint8(x, y)
		return
	}
	q, r := idiv(int64(x), int64(y))
	q1 := x/y
	r1 := x%y
	if q1 != int8(q) {
		print("int8(", x, "/", y, ") = ", q1, ", want ", q, "\n")
	}
	if r1 != int8(r) {
		print("int8(", x, "%", y, ") = ", r1, ", want ", r, "\n")
	}
}

func divzerouint(x, y uint) uint {
	defer checkudivzero("uint", uint64(x))
	return x / y
}

func divzerouint64(x, y uint64) uint64 {
	defer checkudivzero("uint64", uint64(x))
	return x / y
}

func divzerouint32(x, y uint32) uint32 {
	defer checkudivzero("uint32", uint64(x))
	return x / y
}

func divzerouint16(x, y uint16) uint16 {
	defer checkudivzero("uint16", uint64(x))
	return x / y
}

func divzerouint8(x, y uint8) uint8 {
	defer checkudivzero("uint8", uint64(x))
	return x / y
}

func checkudivzero(typ string, x uint64) {
	if recover() == nil {
		print(typ, "(", x, " / 0) did not panic")
	}
}

func divzeroint(x, y int) int {
	defer checkdivzero("int", int64(x))
	return x / y
}

func divzeroint64(x, y int64) int64 {
	defer checkdivzero("int64", int64(x))
	return x / y
}

func divzeroint32(x, y int32) int32 {
	defer checkdivzero("int32", int64(x))
	return x / y
}

func divzeroint16(x, y int16) int16 {
	defer checkdivzero("int16", int64(x))
	return x / y
}

func divzeroint8(x, y int8) int8 {
	defer checkdivzero("int8", int64(x))
	return x / y
}

func checkdivzero(typ string, x int64) {
	if recover() == nil {
		print(typ, "(", x, " / 0) did not panic")
	}
}

func modzerouint(x, y uint) uint {
	defer checkumodzero("uint", uint64(x))
	return x % y
}

func modzerouint64(x, y uint64) uint64 {
	defer checkumodzero("uint64", uint64(x))
	return x % y
}

func modzerouint32(x, y uint32) uint32 {
	defer checkumodzero("uint32", uint64(x))
	return x % y
}

func modzerouint16(x, y uint16) uint16 {
	defer checkumodzero("uint16", uint64(x))
	return x % y
}

func modzerouint8(x, y uint8) uint8 {
	defer checkumodzero("uint8", uint64(x))
	return x % y
}

func checkumodzero(typ string, x uint64) {
	if recover() == nil {
		print(typ, "(", x, " % 0) did not panic")
	}
}

func modzeroint(x, y int) int {
	defer checkmodzero("int", int64(x))
	return x % y
}

func modzeroint64(x, y int64) int64 {
	defer checkmodzero("int64", int64(x))
	return x % y
}

func modzeroint32(x, y int32) int32 {
	defer checkmodzero("int32", int64(x))
	return x % y
}

func modzeroint16(x, y int16) int16 {
	defer checkmodzero("int16", int64(x))
	return x % y
}

func modzeroint8(x, y int8) int8 {
	defer checkmodzero("int8", int64(x))
	return x % y
}

func checkmodzero(typ string, x int64) {
	if recover() == nil {
		print(typ, "(", x, " % 0) did not panic")
	}
}

// unsigned divide and mod using shift and subtract.
func udiv(x, y uint64) (q, r uint64) {
	sh := 0
	for y+y > y && y+y <= x {
		sh++
		y <<= 1
	}
	for ; sh >= 0; sh-- {
		q <<= 1
		if x >= y {
			x -= y
			q |= 1
		}
		y >>= 1
	}
	return q, x	
}

// signed divide and mod: do unsigned and adjust signs.
func idiv(x, y int64) (q, r int64) {
	// special case for minint / -1 = minint
	if x-1 > x && y == -1 {
		return x, 0
	}
	ux := uint64(x)
	uy := uint64(y)
	if x < 0 {
		ux = -ux
	}
	if y < 0 {
		uy = -uy
	}
	uq, ur := udiv(ux, uy)
	q = int64(uq)
	r = int64(ur)
	if x < 0 {
		r = -r
	}
	if (x < 0) != (y < 0) {
		q = -q
	}
	return q, r
}

相关信息

go 源码目录

相关文章

go 235 源码

go 64bit 源码

go alg 源码

go alias 源码

go alias1 源码

go alias2 源码

go alias3 源码

go align 源码

go append 源码

go append1 源码