shithub: mc

ref: 1d6cb9bf584e35be0786467e1786e60ac909ae21
dir: /lib/std/test/bigint.myr/

View raw version
use std
use testr

type cmd = union
	`Add (cmd#, cmd#)
	`Sub (cmd#, cmd#)
	`Mul (cmd#, cmd#)
	`Div (cmd#, cmd#)
	`Mod (cmd#, cmd#)
	`Shl (cmd#, cmd#)
	`Shr (cmd#, cmd#)
	`Modpow (cmd#, cmd#, cmd#)
	`Val byte[:]
;;

const main = {
	testr.run([
		[.name = "smoke-test", .fn = smoketest],
		[.name = "matches-small", .fn = matchsmall],
		[.name = "comparisons", .fn = comparisons],
		[.name = "format-zero", .fn = fmtzero],
		[.name = "division", .fn = smokediv],
		[.name = "modulo", .fn = smokemod],
		[.name = "add-negatives", .fn = addneg],
		[.name = "sub-negatives", .fn = subneg],
		[.name = "bigdivmod", .fn = somebigdivmod],
		[.name = "large-bigmul", .fn = largebigmul],
	][:])
}

const smoketest = {ct
	var a, b, c, d, e, f
	var buf : byte[64], n

	/* a few combined ops */
	a = std.mkbigint(1234)
	b = std.mkbigint(0x7fffffff)
	c = std.mkbigint(7919)
	d = std.mkbigint(113051)
	e = std.mkbigint(11)
	f = std.mkbigint((4294967296 : int64))

	std.bigmul(a, b)
	std.bigmul(a, b)
	std.bigadd(a, c)
	std.bigsub(a, d)
	std.bigdiv(a, e)

	std.bigfree(b)
	std.bigfree(c)
	std.bigfree(d)
	std.bigfree(e)

	n = std.bigbfmt(buf[:], a, 0)
	testr.check(ct, std.eq(buf[:n], "517347321949036993306"), "simple smoke test failed")

	n = std.bigbfmt(buf[:], f, 0)
	testr.check(ct, std.eq(buf[:n], "4294967296"), "smoke test failed for 2^32 case")
}

const matchsmall = {c
	var nums = [ -5, -3, -2, -1, 0, 1, 2, 4, 8, 10 ][:]
	for a : nums
		for b : nums
			var p = std.mkbigint(a)
			var q = std.mkbigint(b)

			var radd = std.mkbigint(a + b)
			var sadd = std.bigdup(p)
			std.bigadd(sadd, q)
			testr.check(c, std.bigeq(radd, sadd), "{} + {} != {} (was {})", a, b, a + b, sadd)

			var rsub = std.mkbigint(a - b)
			var ssub = std.bigdup(p)
			std.bigsub(ssub, q)
			testr.check(c, std.bigeq(rsub, ssub), "{} - {} != {} (was {})", a, b, a - b, ssub)

			var rmul = std.mkbigint(a * b)
			var smul = std.bigdup(p)
			std.bigmul(smul, q)
			testr.check(c, std.bigeq(rmul, smul), "{} * {} != {} (was {})", a, b, a * b, smul)


			if b != 0
				if a > 0 && b > 0
					var rmod = std.mkbigint(a % b)
					var smod = std.bigdup(p)
					std.bigmod(smod, q)
					testr.check(c, std.bigeq(rmod, smod), "{} % {} != {} (was {})", a, b, a % b, smod)
					std.bigfree(rmod)
				;;

				var rdiv = std.mkbigint(a / b)
				var sdiv = std.bigdup(p)
				std.bigdiv(sdiv, q)
				testr.check(c, std.bigeq(rdiv, sdiv), "{} / {} != {} (was {})", a, b, a / b, sdiv)

				std.bigfree(rdiv)
			;;

			std.bigfree(p)
			std.bigfree(q)
			std.bigfree(radd)
			std.bigfree(rsub)
			std.bigfree(rmul)
		;;
	;;
}

const comparisons = {c
	/* some comparison tests */
	var a = try(std.bigparse("1234_5678_1234_6789_6666_7777_8888"))
	var b = try(std.bigparse("2234_5678_1234_6789_6666_7777_8888"))
	testr.check(c, std.bigcmp(a, b) == `std.Before, "{} should be < {}", a, b)
	std.bigfree(a)
	std.bigfree(b)

	a = try(std.bigparse("36028797018963964"))
	b = try(std.bigparse("36028797018963958"))
	testr.check(c, std.bigcmp(a, b) == `std.After, "{} should be > {}", a, b)
	std.bigfree(a)
	std.bigfree(b)
}

const fmtzero = {c
	/* make sure we format '0' correctly */
	run(c, std.mk(`Val "0"), "0")
}

const smokediv = {c
	/* smoke test for division */
	run(c, std.mk(`Div (\
		std.mk(`Val "1234_5678_1234_6789_6666_7777_8888"), \
		std.mk(`Val "1234_5678_1234_6789_6666_7777"))), \
		"10000")
	run(c, std.mk(`Div (\
		std.mk(`Val "0xffff_1234_1234_1234_1234"), \
		std.mk(`Val "0xf010_1234_2314"))), \
		"4580035496")
	run(c, std.mk(`Div (\
		std.mk(`Val "5192296858534810493479828944327220"), \
		std.mk(`Val "75557863709417659441940"))), \
		"68719476751")
	run(c, std.mk(`Div (\
		std.mk(`Val "75557863709417659441940"), \
		std.mk(`Val "5192296858534810493479828944327220"))), \
		"0")
}

const smokemod = {c
	/* smoke test for mod */
	run(c, std.mk(`Mod (\
		std.mk(`Val "5192296858534810493479828944327220"), \
		std.mk(`Val "75557863709417659441940"))),\
		"257025710597479990280")

	run(c, std.mk(`Modpow (\
		std.mk(`Val "1"), \
		std.mk(`Val "3"), \
		std.mk(`Val "2"))), \
		"1")

	run(c, std.mk(`Modpow (\
		std.mk(`Val "5192296858534810493479828944327220"), \
		std.mk(`Val "75557863709417659441940"), \
		std.mk(`Val "755578"))), \
		"49054")
	run(c, std.mk(`Modpow (\
		std.mk(`Val "2393"), \
		std.mk(`Val "2"), \
		std.mk(`Val "6737"))), \
		"6736")
	run(c, std.mk(`Modpow (\
		std.mk(`Val "6193257528475266832463188301662235"), \
		std.mk(`Val "6157075615645799356061575607567581"), \
		std.mk(`Val "12314151231291598712123151215135163"))), \
		"1540381241336817586803754632242117")
	run(c, std.mk(`Modpow (\
		std.mk(`Val "7220"), \
		std.mk(`Val "755578"), \
		std.mk(`Val "75557863709417659441940"))), \
		"27076504425474791131220")
}

const addneg = {c
	run(c, std.mk(`Add (\
		std.mk(`Val "-1"), \
		std.mk(`Val "1"))), \
		"0")

	run(c, std.mk(`Add (\
		std.mk(`Val "4"), \
		std.mk(`Val "-2"))), \
		"2")

	run(c, std.mk(`Add (\
		std.mk(`Val "3"), \
		std.mk(`Val "-6"))), \
		"-3")

	run(c, std.mk(`Add (\
		std.mk(`Val "-4"), \
		std.mk(`Val "8"))), \
		"4")

	run(c, std.mk(`Add (\
		std.mk(`Val "-10"), \
		std.mk(`Val "5"))), \
		"-5")

	run(c, std.mk(`Add (\
		std.mk(`Val "-6"), \
		std.mk(`Val "-12"))), \
		"-18")

	run(c, std.mk(`Add (\
		std.mk(`Val "7"), \
		std.mk(`Val "-7"))), \
		"0")
}

const subneg = {c
	run(c, std.mk(`Sub (\
		std.mk(`Val "-1"), \
		std.mk(`Val "1"))), \
		"-2")

	run(c, std.mk(`Sub (\
		std.mk(`Val "1"), \
		std.mk(`Val "-1"))), \
		"2")

	run(c, std.mk(`Sub (\
		std.mk(`Val "4"), \
		std.mk(`Val "-2"))), \
		"6")

	run(c, std.mk(`Sub (\
		std.mk(`Val "3"), \
		std.mk(`Val "-6"))), \
		"9")

	run(c, std.mk(`Sub (\
		std.mk(`Val "-4"), \
		std.mk(`Val "8"))), \
		"-12")

	run(c, std.mk(`Sub (\
		std.mk(`Val "-10"), \
		std.mk(`Val "5"))), \
		"-15")

	run(c, std.mk(`Sub (\
		std.mk(`Val "-6"), \
		std.mk(`Val "-12"))), \
		"6")

	run(c, std.mk(`Sub (\
		std.mk(`Val "-14"), \
		std.mk(`Val "-7"))), \
		"-7")

	run(c, std.mk(`Sub (\
		std.mk(`Val "-8"), \
		std.mk(`Val "-8"))), \
		"0")
}

const run = {c : testr.ctx#, e : cmd#, res : byte[:]
	var buf : byte[4096]
	var v, n

	v = eval(e)
	n = std.bigbfmt(buf[:], v, 0)
	testr.check(c, std.eq(buf[:n], res), "{} != {}", buf[:n], res)
}

const eval = {e : cmd#
	var buf : byte[2048]
	var a, b, c	/* scratch vars */
	var n		/* buf len */

	match e#
	| `Add (x, y):	-> binop("+", std.bigadd, x, y)
	| `Sub (x, y):	-> binop("-", std.bigsub, x, y)
	| `Mul (x, y):	-> binop("*", std.bigmul, x, y)
	| `Div (x, y):	-> binop("/", std.bigdiv, x, y)
	| `Mod (x, y):	-> binop("%", std.bigmod, x, y)
	| `Shl (x, y):	-> binop("<<", std.bigshl, x, y)
	| `Shr (x, y):	-> binop(">>", std.bigshr, x, y)
	| `Val x:
		a = try(std.bigparse(x))
		n = std.bigbfmt(buf[:], a, 0)
		-> a
	| `Modpow (x, y, z):
		a = eval(x)
		b = eval(y)
		c = eval(z)
		-> std.bigmodpow(a, b, c)
	;;
}

const binop = {name, op, x, y
	var a, b

	a = eval(x)
	b = eval(y)
	op(a, b)
	std.bigfree(b)
	-> a
}

generic try = {x : std.option(@a)
	match x
	| `std.Some v:	-> v
	| `std.None:	std.die("failed to get val")
	;;
}

const somebigdivmod = {c
	var inputs : (byte[:], byte[:], byte[:], byte[:])[:] = [
		/* ( a,  b,  a/b,  a%b),  */
		("6185103187", 	"3519152458", 	"1", 	"2665950729"),
		("6980766832", 	"3087864937", 	"2", 	"805036958"),
		("4991855479", 	"6447381549", 	"0", 	"4991855479"),
		("6119892968", 	"8374603717", 	"0", 	"6119892968"),
		("7442542736", 	"5989044918", 	"1", 	"1453497818"),
		("4580939187", 	"4661174670", 	"0", 	"4580939187"),
		("4935237814", 	"3140079933", 	"1", 	"1795157881"),
		("1010425087", 	"446887574", 	"2", 	"116649939"),
		("1892124804", 	"4011235814", 	"0", 	"1892124804"),
		("2457899196", 	"1885658848", 	"1", 	"572240348"),
		("262030672", 	"1329267171", 	"0", 	"262030672"),
		("8430016289", 	"6215302855", 	"1", 	"2214713434"),
		("3347587073", 	"3855445301", 	"0", 	"3347587073"),
		("8014059310", 	"4622364950", 	"1", 	"3391694360"),
		("2934470708", 	"6439081239", 	"0", 	"2934470708"),
		("420917856", 	"5020252044", 	"0", 	"420917856"),
		("3862040257", 	"4601227994", 	"0", 	"3862040257"),
		("4439858911", 	"4387180962", 	"1", 	"52677949"),
		("165706876", 	"7452574618", 	"0", 	"165706876"),
		("268686047", 	"3047271875", 	"0", 	"268686047"),
		("83484791", 	"4899367309", 	"0", 	"83484791"),
		("1242378916", 	"4909326080", 	"0", 	"1242378916"),
		("980437482", 	"2305509838", 	"0", 	"980437482"),
		("118982655", 	"5051748984", 	"0", 	"118982655"),
		("8521162809", 	"2888108066", 	"2", 	"2744946677"),
		("4600797553", 	"7579789288", 	"0", 	"4600797553"),
		("5533774720", 	"3320264831", 	"1", 	"2213509889"),
	][:]

	for (aS, bS, qS, rS) : inputs
		var a     = try(std.bigparse(aS))
		var b     = try(std.bigparse(bS))
		var q_exp = try(std.bigparse(qS))
		var r_exp = try(std.bigparse(rS))

		var q_act, r_act
		(q_act, r_act) = std.bigdivmod(a, b)
		testr.check(c, std.bigeq(q_exp, q_act), "expected {} / {} to be {}, was {}", a, b, q_exp, q_act)
		testr.check(c, std.bigeq(r_exp, r_act), "expected {} % {} to be {}, was {}", a, b, r_exp, r_act)
	;;
}

/* Tests a and b large enough that we are forced to used kmul, including recursively */
const largebigmul = {c
	var inputs : (byte[:], uint32[:], uint32[:], uint32[:])[:] = [
		( "0", [ 0x1 ][:], [ 0x1 ][:], [ 0x1 ][:] ),
		( "1",
			[0xd438d501, 0x4989bb6c, 0xaa02ccd2, 0x8c02c7fb, 0xd0d39cab, 0x7daee963,
			0x03fa7756, 0x17371fb7, 0x4f2d80c7, 0xbc69e893, 0x02c68eea, 0x0aeec675,
			0x2975319d, 0x4d263e97, 0x6707e6f7, 0x1a4ef735, 0x28c24ac8, 0x1da85267,
			0x5ba370ed, 0x74e5b4c0, 0x45620f6a, 0x670847ec, 0xf285f864, 0xecbac2b5,
			0xc13311b0, 0x15d83f71, 0x38864ab3, 0x338158d0, 0x243593a7, 0x55f00d20,
			0x7bda6d92, 0xa95ce358, 0x80456513, 0x9bdb0419, 0xd0974038, 0xeab6f619,
			0x3c30aeaf, 0x8a4a50a1, 0xa2777800, 0xe1973634, 0xde34e4ad, 0xc85422d0,
			0x536a3638, 0x7bb91969, 0x1b6e1dac, 0x66582385, 0x61aab43a, 0xc0931876,
			0x74d01412, 0x47539d84, 0x2ceb3858, 0xb75a4c69, 0xafee3d68, 0xa8f568f2,
			0x05cd2855, 0x846851fe, 0xc358698e, 0x5ad7e3a2, 0x06c04ec2, 0x49c04dd4,
			0x65af24ee, 0xcaca4901, 0x782682b0, 0x1420ec52, 0xfbd6f634, 0x4e5751b8,
			0xc60275cd, 0x54000917, 0x2543fd5b, 0x6a7e6ee0, 0x84c7cce5, 0x26f9b270,
			0x745c34d8, 0xb461676a, 0x6ca583f0, 0x09ada4f6, 0x17158bf5, 0x312018c3,
			0x2acf878d, 0xa9e0ab50, 0x433370d8, 0x00000005][:],
			[0x5a518f95, 0xef185267, 0x108f864c, 0xec996040, 0x593b2a4b, 0x3c5d1abb,
			0x5c2c7236, 0xfb727af9, 0xccfb6dbf, 0xa8e7df8d, 0x7848bada, 0x879d7999,
			0xfa4c7338, 0x35718a28, 0x0ba6d7c9, 0x18ee1a03, 0xf9730643, 0x114d1a6f,
			0x30fb26f8, 0xa7ce8a60, 0xeb507683, 0xaec6f875, 0xe9ea93d7, 0x5239caec,
			0x1b6e181d, 0x0d05743b, 0xa71a466e, 0x78d271f0, 0x991dc0e6, 0x961ec35c,
			0xe8b25de3, 0x7d8f853a, 0xeed878c0, 0x79a64b5f, 0x33b266f9, 0x737b8b42,
			0xb0018fb3, 0x02fb1917, 0x101803b8, 0x9969897c, 0x8f1e9f84, 0xb8977c7b,
			0x0d94ab3c, 0xba0bdc8c, 0xeb5b271e, 0x71bbc3ac, 0x6b3a99aa, 0xcfca90b2,
			0xc25784a0, 0x4b7b3dab, 0xb4d6301b, 0xe6bf1fb3, 0x4656b287, 0xf71fdd63,
			0x0783c3c5, 0xb399ec3a, 0x7dae1bd3, 0xa6e9cd42, 0x1b215387, 0x2fbfc73d,
			0x5a6684f0, 0x012e8f71, 0x0c059772, 0x00000001][:],
			[0x03608895, 0xcb170728, 0xed235930, 0xa28f5417, 0x5c00f16b, 0x4d742082,
			0x8b0f61ee, 0xfda181e8, 0x2afd0ab2, 0x893be877, 0xc7661174, 0x4b2a1abd,
			0xe873e5fa, 0xeafb1741, 0xc905b9ab, 0x7af419ec, 0x8d7f9ffe, 0x46e45629,
			0x4239bae8, 0x9e50c518, 0x9b38a2c6, 0x4b019ab7, 0x0bf40396, 0xd7dfaa78,
			0x194ea149, 0x72d40c27, 0xc93fb77e, 0xf46a3bae, 0xf205b59a, 0x37d929da,
			0xd88ed984, 0x49a2213e, 0x5ede97a1, 0x3f99adc8, 0x6b4c6f3a, 0xdd193272,
			0x523fc0f7, 0x91f6ac1a, 0x76bcf78d, 0xec30f5e0, 0x71ea7b2b, 0x92fe5381,
			0x01a70007, 0x70ac2e64, 0x46c66e83, 0x2b0a4f4a, 0xde20afb2, 0x637b17d4,
			0x32ebad24, 0x5fbc158c, 0x0839222e, 0xaaa69163, 0x1a41e45d, 0x2596c604,
			0xf241193f, 0x8d7649f6, 0xf14676ab, 0x07e60937, 0x9aa0ec6d, 0xf3f1e581,
			0xaa405903, 0xb7fcc27e, 0xed7a1a3a, 0x09e0393c, 0x417d0d01, 0x3c0b5748,
			0x97b26c8a, 0xb18f2bd4, 0xcce143a0, 0x175aaa0a, 0xb5a199a2, 0xe7419c0e,
			0xad86bb76, 0x21ce336b, 0xdce58113, 0xef9a1639, 0x691857ea, 0x4ea4ce08,
			0xdb78d01e, 0x8a803b54, 0x4e62c40e, 0xede995d5, 0xea466369, 0x4975d5e2,
			0xe16ec2b0, 0x35e9f0f9, 0x734b4486, 0x7fc594c6, 0xf59977b9, 0x6fda8fd9,
			0xc66890ef, 0xa5f6d53f, 0xabc4a213, 0x439e36c9, 0xe1edd657, 0xbef6c23c,
			0xd1b8e53f, 0xef3d7a8e, 0xd5942d9b, 0x3678d074, 0xc7b33a1f, 0xa0da7e2a,
			0x55ff1f4b, 0x17543de3, 0x2f37b8e6, 0xc3c6edf2, 0x8757e107, 0x5a6d6ecc,
			0x05238803, 0xe91265a5, 0x20b6b8d8, 0x49a64334, 0x67d29fd6, 0xf7f64219,
			0xa5316b89, 0xa70e493a, 0x6500a01e, 0x342c92d8, 0x04c47fc5, 0x418fecea,
			0x335c77dd, 0x0075fd81, 0xabe80a7a, 0x1c87978b, 0x040928b4, 0x531c47b5,
			0x5b1abf55, 0x9d62cc66, 0x855394eb, 0xf6045e0b, 0xcd307a1e, 0xab7e9197,
			0x5725390f, 0x64930312, 0xf10b918a, 0x32d52d5e, 0xe4ebf112, 0x2a1174ac,
			0x7681fa2c, 0x554dd47f, 0x26bbf792, 0xd18c803c, 0x50c2caf7, 0x8277471f,
			0x00000005][:] ),
		( "2",
			[0x8fa8c809, 0x543ccfc3, 0x40a67589, 0x13c872a6, 0xca8bd8d8, 0xcaa5195e,
			0x9bfccb1a, 0x5044e5a4, 0x2a1b585a, 0x6e2b558e, 0x02e09bfe, 0xc5773e7b,
			0xaeb80d18, 0xdfcef845, 0x1644673a, 0xc19be15d, 0x8d98234b, 0x424cb607,
			0x08f05d1a, 0xea92e8af, 0xf8d85512, 0xc76f3fb6, 0xaf56b49a, 0x162fb1b3,
			0xc194ef0a, 0x2e48a43b, 0x7952ddba, 0x2605be3e, 0xcd21045e, 0xf3837447,
			0xea4af63e, 0x56c4f0ba, 0xbd345727, 0xdfdac514, 0xb5622e07, 0xea8a3761,
			0x28061058, 0xf89e06a4, 0x635d4ea0, 0x44b0946b, 0x042bd0df, 0x479e38b8,
			0xba572f80, 0x027090ff, 0xafa718bb, 0x5617b2e2, 0x18826318, 0xe7a12367,
			0x59b565df, 0xa0af53db, 0xcf4c9bb9, 0xf0e87494, 0xf205236a, 0x7f9ffdaa,
			0x9a1a6b83, 0xfc817575, 0x787a885e, 0x56980581, 0xdc48c4a2, 0x5dba364d,
			0x3161b177, 0xdffd5d41, 0x8d2e075c, 0xfb7d12c2][:],
			[0xf7ffa08f, 0x6e5c02bd, 0x0cd84a3a, 0x8e28cb47, 0x4cdd6159, 0xe69b9388,
			0xf5366110, 0xa3752c29, 0x4c793e6d, 0x13a9ee28, 0xca1aa614, 0x25fdb9b3,
			0x3fe9c1d2, 0xf9921d1a, 0xe7c9377d, 0x8d79e36f, 0x7a9348de, 0xa110805e,
			0x5df92768, 0xfb1c84da, 0x8d81287c, 0x8eea0ba5, 0x06beecfa, 0x7ec242b7,
			0x0e064d8c, 0x0b292555, 0x382ba0b5, 0x580eb632, 0x2755a606, 0x572f30c6,
			0xf55d2897, 0x2a724e36, 0x657b3ca9, 0x5963dd68, 0x606f5324, 0xf241245d,
			0x055ab33f, 0x3eef5523, 0xda3504d4, 0x61bfc918, 0xdfc30229, 0x695dfd29,
			0xd049f5a2, 0xec3eeabd, 0x54837bf9, 0x5f7a4cb3, 0x24f3a6f7, 0xca49bdf3,
			0x08357231, 0x881af70b, 0x46c7db74, 0x591108dd, 0xc6e63813, 0x7aed2e3b,
			0x5f0161ab, 0x805e6881, 0xe137b4be, 0x85dc2eea, 0x4b16bcdc, 0x97ed5301,
			0x5fd127ab, 0xff570b67, 0xc3995a73, 0x293c53ea][:],
			[0xac445d07, 0xd5a1facb, 0xa0b20e8a, 0x47608bc6, 0xfbfbf40b, 0x1dbfc947,
			0xb2c95000, 0x7e793f5c, 0xad8b43e4, 0xaed1e721, 0xa353d730, 0x43261fd0,
			0x35363d03, 0x84fd0166, 0x89a8b3eb, 0x60657de1, 0x5da0fff8, 0x6886160c,
			0xaba2eb76, 0x56a19809, 0x302b6f1f, 0x3fb5b5c1, 0xb2890ff0, 0x82f8bf60,
			0x8e0d7375, 0xee92358e, 0x7f54bdf5, 0xa7cf09eb, 0x545ea45b, 0xd8417f77,
			0x8cc07ac7, 0x378a2893, 0x7da7f4d9, 0xbc470080, 0xd8bcdf22, 0x1e479f3b,
			0xb6f3f1c4, 0x44f267b2, 0xc3dec7ef, 0x8e63ac6c, 0x1e316ef2, 0x8aa23025,
			0x7e099910, 0x0ca8740b, 0xc85c30d4, 0x017cb92a, 0xbce9d39c, 0xa3480621,
			0xb2fc06af, 0x474e5b39, 0x339a2289, 0x9bc881ca, 0xbce293fd, 0xdbca309d,
			0xbb74a11a, 0xd024441c, 0xf66d6394, 0x3cf320d1, 0x6a1248c3, 0x0b12a871,
			0x0e227c35, 0x629f4969, 0x72cbef9e, 0xae18a37e, 0xfc1be6ff, 0xd95b4131,
			0xaac0a3ac, 0x79629682, 0xb8c6323c, 0x76913f2f, 0x90453e91, 0x78b07c24,
			0xb89ffea0, 0x0cb32917, 0xd75d17e9, 0x52d606c0, 0xc1c33240, 0x0902a819,
			0x75a73f41, 0x5157a6a0, 0x3bcad1ea, 0x50972558, 0xbfcf1c99, 0x7e12a8df,
			0x5659c108, 0x6466a629, 0xaab38244, 0xcff2e6de, 0x43d14392, 0xa56dcc0f,
			0x3ede1c6a, 0xf0ee6c6e, 0xaa1b37b4, 0x9d13b489, 0xa5d5289d, 0xb6b4da73,
			0x8da6fe58, 0xb98e7c64, 0xb12b0842, 0x1291c110, 0x023521c6, 0x3ca866f9,
			0x5e642f8f, 0xc946e820, 0x1f65389d, 0x1615acea, 0x2f2a06d4, 0xc42f7923,
			0x5c4b8d78, 0x9f6bd66b, 0xc16146cd, 0xe18345f3, 0x70e565f9, 0x748bd980,
			0xc2eed91d, 0xc0791edc, 0x52a4b5cc, 0xb6016466, 0x73eee8e4, 0x0400d3de,
			0x249a903f, 0x5a9e5ea2, 0x222e0f92, 0x8a645235, 0x06680935, 0xe6894660,
			0xbbc49b78, 0x28824bc1 ][:] ),
		("3",
			[0x22dfeef3, 0x1295b431, 0xe9529863, 0x348d4b7d, 0x7272b12f, 0x0497c293,
			0xf02f7c25, 0x099e1eb9, 0xda9ba0ea, 0x62a2814d, 0x4fdbe3d7, 0x908a31b8,
			0xe5060b0d, 0x671d15bd, 0x294965ce, 0x232f88f1, 0x4c448988, 0xfc383d3b,
			0x86df2de1, 0x20432646, 0x4c7fbe1f, 0x326f7d3c, 0x38dfbec7, 0xf00f3df9,
			0xce5ea03d, 0x62ab0701, 0x4d23d197, 0x4ef44098, 0x38c375d6, 0xc7d72bc2,
			0x25199975, 0xbe84f268, 0x00d4ad56, 0x50243728, 0x4aea96dc, 0x4740a2e3,
			0x5d07b992, 0x7d0a0770, 0xed6a4976, 0x204cb483, 0xe4d930aa, 0xb5b0f5fc,
			0x3546f99a, 0x42087de5, 0x78cb663c, 0xab2e422d, 0x96214a92, 0x2721b270,
			0xcf272a16, 0xd0da429d, 0xe69f7c29, 0xb1de29e6, 0x9e9f2305, 0x80be09ca,
			0x1f5d8a2f, 0xbe152c9a, 0xc57021ed, 0xb99be11d, 0x6bd527e8, 0xda4ef764,
			0xe1b7d09c, 0xe2693d79, 0x609f8000, 0x69c4d0a3, 0x7f227f5a, 0x9b92e545,
			0x8833cd2c, 0x95a3a9ae, 0xd81e95f4, 0x422321b3, 0xe586291a, 0x8ef5f3a8,
			0x4dc1916b, 0x55136cdf, 0x353c870c, 0x7fb85f91, 0x9407cd80, 0xa18b43fa,
			0xa83d75ec, 0xb72b29e4, 0x99408c66, 0x26080a1e, 0x359f480e, 0xb1344ed4,
			0x8f9d1a7b, 0x3f264a46, 0xfbc27805, 0xd2e4f801, 0xc9f069e8, 0x77eb4d98,
			0x5e4e0744, 0x1a7b6e8a, 0x5033ba97, 0x3c8865ad, 0xf8b6918d, 0xaf58dea5,
			0xa621a059, 0xedd5d287, 0xa7692cf1, 0x08f6da8c, 0xa2f947ff, 0x22a1651b,
			0xba305733, 0x3d77331b, 0xce23609c, 0x7dc2463f, 0xacded3ea, 0x51af503b,
			0x9cbf5ddd, 0xa4f0b163, 0xb5102301, 0xc1f3442a, 0xf2f03659, 0x4a84e291,
			0x719b40f6, 0x1f08c19f, 0x34289a6f, 0xeafbc6da, 0x7e3c1da9, 0xb1736af0,
			0xa278d6fb, 0xf555dcc6, 0xac6db91f, 0x0961cb3e, 0xeb5988ca, 0x3a9d5433,
			0x259e1376, 0x6b6e6503][:],
			[0x6b1ca441, 0x65742248, 0x181e0881, 0xb00f4698, 0x46305741, 0x7b8178e2,
			0x749ceb45, 0xbf901cb4, 0xb7bd02e6, 0x365da057, 0xa1bca303, 0xcde24d9d,
			0x5c389bec, 0xc6a226da, 0xca67fbc5, 0x69c47cae, 0x205abc68, 0x86722c43,
			0x247a94a9, 0x78270cef, 0xedef0dfb, 0x7130c80b, 0xb674b77e, 0xba9534b1,
			0xed537e68, 0x63198332, 0xceff15fa, 0xf68c1dcc, 0x03fe5e89, 0xa11c3e38,
			0x83b79cb9, 0x7cac2f9d, 0x29da9204, 0x4d6e2361, 0x11d237eb, 0xc9ccc25e,
			0x836c1307, 0x54faec3c, 0x42cab0a1, 0xcc53cb2f, 0xca329b79, 0xb1165990,
			0xbc40c6d3, 0x9c18f2d9, 0x54ad9dc1, 0xf32f4d6b, 0x738b9206, 0xf8d89e3b,
			0x9bdae564, 0x0d684ecf, 0x8b3ba78b, 0xc3a026ce, 0x7e57f8e0, 0x75e3af99,
			0xcb0a7aaa, 0x4d7a074c, 0xa7e9f774, 0x10e48e2c, 0x89a10535, 0x267003c0,
			0x74906b9f, 0x4eafe1f6, 0xd99d4ec0, 0x4323b3e1, 0x488d7a83, 0xde62fcc5,
			0x07cae706, 0x74cb362a, 0x6b2f4d61, 0xadf806c3, 0x5bad862c, 0x0c9b2b3a,
			0xf8aa721d, 0xb1b6caa5, 0x04aa9c5b, 0x982bafc9, 0xd1640b6a, 0x45a5c11c,
			0x37ece529, 0x751f30fc, 0xecdb58d9, 0x4de7d68c, 0x57f8e6dc, 0xbd51784c,
			0x5e18ac33, 0xfd96f93f, 0x7b9ae848, 0x4d5c3c7a, 0x01f0ad39, 0x15d79946,
			0x576b4ceb, 0x3fef8d14, 0xe01ff6a5, 0x60717e45, 0x89ec8ffa, 0x11932b09,
			0xcffd0872, 0xedcbb885, 0xff15ecc6, 0x557d81d6, 0x921f3f5f, 0x4d7e153f,
			0xa7103379, 0xa11f6491, 0xa0387abf, 0xc00bdb8b, 0x55f3f081, 0xdbb89eec,
			0x8ab41a4d, 0x59fbc622, 0x11588374, 0x119253b0, 0xf17420d5, 0x964706ec,
			0x81b886e3, 0x2a8052c7, 0x179a777b, 0xc586b2d1, 0x7bf190d0, 0xec24e894,
			0xdc832932, 0xcd755483, 0x7c6425ec, 0x876d7e4c, 0x4a9f72c8, 0xfbc115ad,
			0x25c7d971, 0xedaf521d][:],
			[0x038357b3, 0x90391e87, 0xbb0b1f64, 0x3ddb1c33, 0xe301125b, 0x12aeb1dc,
			0x287ffbb9, 0x9ee982ad, 0x9741ae84, 0x39542c4f, 0x9f61a3e8, 0x09387c33,
			0x70a97e09, 0x1a6c0444, 0x959a837e, 0xa9fa7fbc, 0x93d0cfe3, 0x6983971a,
			0x9b27a516, 0x27fcaf20, 0x548eef04, 0x68133c8a, 0x4a4f180c, 0x588ed2e9,
			0x305789bb, 0x92ff4600, 0x4b9172e6, 0x679ccd52, 0xd6a53f0a, 0xba71774e,
			0x0bdfec3f, 0x0279dd6c, 0x3185adac, 0x8e9aed66, 0xcc7dad42, 0x0879329e,
			0x767a7c62, 0x05357615, 0x50536d95, 0x149f0875, 0x9aa4ead4, 0x934f498b,
			0x7fcbb757, 0x39ddcb63, 0x4b6457f8, 0x485564c0, 0x77fad861, 0xed489f61,
			0x8748a4fc, 0x9c78285c, 0xb8b66eec, 0x5a9a93eb, 0x465223e7, 0x46881a27,
			0x87c2c4a2, 0xac270dbb, 0x44015283, 0xd558c2c8, 0x93447a91, 0xd7133cdf,
			0x5012b012, 0xbe460642, 0x1db983e0, 0xe50ffe77, 0x625183a2, 0x8b5e5ca0,
			0x1163d7b4, 0x0cf9fa2c, 0xad8ab8d8, 0xa0b97c59, 0xa52fefec, 0x58da0bf2,
			0x6f2fd1bf, 0xdc01ce71, 0x1914aa24, 0x82ad1a95, 0xaa53fac0, 0x62d3f9cc,
			0xbaaa8089, 0x2a2d1264, 0xb26ea7ac, 0x04ada4f7, 0xfdbc95f5, 0xf2f50786,
			0x036a237d, 0x64cfacc5, 0x120ef1cc, 0xf3588412, 0x3c7c55ef, 0xb520eb8b,
			0x7a8dd08f, 0x1db1a183, 0x51f7a79f, 0x7f8f307c, 0xc1a97ca7, 0x80671cc7,
			0xf9a328c3, 0x47013e4e, 0x7823b8d1, 0xbbe06af0, 0xe680314e, 0x70a7d72c,
			0x229bf1d7, 0xdf7e1c8f, 0x959b4797, 0xcd2c5562, 0x3a16a7dc, 0xd4ead1f5,
			0x6338caae, 0x41a5b581, 0x3b39fd1b, 0x8a16105a, 0x6f28277c, 0x3136aa67,
			0x5b157dd1, 0x07bc0914, 0x651ab249, 0x85d8916d, 0xeacb3296, 0xa3f334a7,
			0x9a277b25, 0xd22b6466, 0x85e40d95, 0x415f76fa, 0x0e5cf265, 0x0dbfdc80,
			0xe009f0e1, 0x056c74ae, 0x8348b379, 0x6b14d769, 0xfe5068ae, 0x2c7b8ed8,
			0xf146323a, 0x916936ef, 0x5e3a9472, 0x2541af46, 0x68f617d0, 0xc779d3f8,
			0xb78bf034, 0xe4417ac7, 0xf5407b8c, 0x1ea31a97, 0xfd554f03, 0xe7e56918,
			0x525973d4, 0x4c25a06a, 0xf52bfbab, 0x1c8674fe, 0x317d4101, 0xdde64294,
			0xd59cbbdd, 0xe656ea74, 0xc4ff15db, 0xab2d0614, 0x19c67569, 0x3c653357,
			0xf5af550c, 0x26506c80, 0xb279a34d, 0x93cbef6f, 0xd41481f6, 0x76255c7b,
			0xd4f42c8f, 0x3bb49c64, 0xfa96fe56, 0x1e29f491, 0x2a5bede1, 0xf5b005ae,
			0xabfc04bd, 0x95cf0697, 0x4f4b9df6, 0x715de20d, 0x4b98356b, 0xf3d4c333,
			0xad5b4f93, 0x59131b9b, 0x5cd3a556, 0x098bcd23, 0xa06963ba, 0x174395d8,
			0xbb91e26d, 0x9ebc6f33, 0xa807da65, 0xbb4bd098, 0xd2e652a4, 0x3c7d3ee6,
			0x52a91bb1, 0x3f62fb01, 0x41be0494, 0xfab8db16, 0x810447dc, 0xfed91418,
			0x750efd71, 0x3a0ec6bc, 0x2c32e298, 0x151dffff, 0x47f210c1, 0x204e507d,
			0x84cf5792, 0xde782027, 0x9effd3a9, 0xb43ae3d5, 0x16cf97c1, 0x7d95c2df,
			0xf858e612, 0x49859ab9, 0xc16d577d, 0x14dd50d3, 0x2dd08736, 0xe96a7b2e,
			0xeb004b34, 0x9d9bc730, 0x13fe6e1a, 0x7dfd1021, 0x92a3d3d8, 0xf2407043,
			0x4428a7ca, 0x8d1b3922, 0xd33208e8, 0x8e7225d0, 0xc8f4fa13, 0x64272a09,
			0xe2c2038d, 0x830c409f, 0x154393f3, 0xe12f4602, 0x8199707a, 0x792f7290,
			0x64a70bc3, 0xb9bc1551, 0x0db8ffc0, 0x705bcd1b, 0x6471c035, 0x3bf40f65,
			0x6e8afac9, 0x2cd19929, 0x9c16c41c, 0x025648e3, 0xea05f99a, 0xd3fe51b9,
			0x66ce52dd, 0xf880e76e, 0x4aaa8a7b, 0x75142f5f, 0x432bd1dd, 0x1d7ac75e,
			0x5ab946b9, 0xcfdb4114, 0x98a502b7, 0x958470a5, 0xb51024c4, 0x05dd0fd9,
			0x7e46beda, 0x0a1c6800, 0x8eb15526, 0x63bec670 ][:] ),
		("4",
			[0x00000000, 0x00000000, 0x2f80c620, 0xaed77bc2, 0x3e008565, 0xeb544010,
			0x5adb6bbb, 0x6a970524, 0x033da916, 0xe1167ffb, 0xfec62d44, 0x8ead118c,
			0x3fe1b8be, 0xe8d64f72, 0x38a4d68a, 0xc94c5109, 0x0b13ed98, 0x024300e0,
			0x9085d53a, 0xe98641f9, 0x2b8ed0d5, 0xbaf2d8a5, 0x12755828, 0x38ef909e,
			0xa3e8cfa5, 0x35cd9f30, 0xdd0e3b30, 0xca4ebe1d, 0x5b755afb, 0xf397fa0d,
			0x3b5caa19, 0x7b417233, 0x862fa53e, 0x02304de9, 0xf57a2a92, 0x675f10d4,
			0x474e06ca, 0x8ffb7725, 0x6e275c16, 0x6a186d48, 0xc69568eb, 0xf9eda4b9,
			0x5740fd4f, 0x803fd994, 0xfb453312, 0xddb8690a, 0x508e281b, 0x38a5577c,
			0xaab2f536, 0x6ce3b6f4, 0x4dee5d51, 0x60c4bbf2, 0x4c09a599, 0x5eb6c608,
			0xecf2220c, 0xf2588679, 0x44b9c787, 0xa2876cd5, 0x091d3194, 0xd0a82238,
			0xfa427746, 0xc632cfa4, 0x0ddec524, 0x162fe96b, 0xaeb1d611, 0xf178cbcf,
			0x73beb271, 0x28c6479f, 0x6b7f4382, 0x55ba5937, 0x3654d41e, 0xb812a225,
			0x01a7a376, 0x7272f156, 0x3707817c, 0xdf9d61fa, 0x5f6839b3, 0xd111299e,
			0xfe8f6bfd, 0xd8f049a8, 0x6258b970, 0xb0fc8bc1, 0x852852d5, 0x656244ca,
			0x22c6c460, 0x15099b9c, 0x4a1c7a83, 0x81009548, 0xe19c4dee, 0xa3e8eabc,
			0x75dc75bf, 0xe88d7417, 0xd35ea0a1, 0x15120543, 0x4048f128, 0x8b940efe,
			0x37a2e88b, 0x91e0a1be, 0x65315d55, 0xe34ffec8, 0xaed1838a, 0xb9ba4ac8,
			0xf5b565b2, 0xf460ff05, 0xc30257d9, 0x5befcccb, 0x4acecf36, 0x574a5aee,
			0xe30808a3, 0x6da67aa5, 0x7424734e, 0x9a859ca0, 0xb786105a, 0x9b494870,
			0xe45c7b71, 0x3d6bdb2b, 0x19134c3e, 0x92709ac1, 0x5641d664, 0x08a16956,
			0x218f6f73, 0x1e55b83c, 0x949eac19, 0x620564a9, 0xa975f94a, 0xc32bd272,
			0x0d9e7640, 0xcf27d5d6, 0x2b278f0f, 0x2fd0f6fe, 0x13bfef7b, 0xf5d6d904,
			0xb64391bc, 0xfe8a9ca3, 0xa64cab84, 0x653a96cd, 0xb48287fe, 0xdda1eeac,
			0x7b4d0581, 0x4071484b, 0x6c1f6b78, 0x614cb535, 0x56c4c164, 0x2b4a977d,
			0x7f7f640a, 0x871118e6, 0x6a337388, 0xce7b1958, 0x16d35d77, 0x71c0c4be,
			0x58e19d06, 0xc0837407, 0x1cbdd134, 0x22f04921, 0xdd394e98, 0xebefabc2,
			0x2c9b26f9, 0x5afa7c94, 0x04951ae1, 0x62903bfc, 0x194f245f, 0x759490c7,
			0x98680e80, 0x31de9269, 0xcb55b655, 0x3cc4d017, 0xf542431d, 0xbef9a613,
			0x8dad1067, 0xfb8ee54b, 0x80c5808a, 0xd6d5b742, 0x8eacc01e, 0x3d830d99,
			0x13d13a8d, 0x3e807eff, 0x7ed89776, 0x29ca8438, 0x31a6450f, 0xe9d8956b,
			0x2369bad3, 0x85dc23d8, 0xe0b4620a, 0xa1b916e4, 0x62497ae8, 0xdb095b68,
			0x24375842, 0xd34494cf, 0x13ebe06e, 0x95d10197, 0x1fcd4987, 0xa38922d9,
			0x0c7194ae, 0xa1945f61, 0xe8c7c6b6, 0xec4862c6, 0x4eb5323b, 0x3a61c6ed,
			0x0c729cb2, 0xa3540b69, 0xf457f914, 0x23a791d1, 0x7dd319b5, 0xd4099cf5,
			0xd9b4234c, 0xd6d100dd, 0x060e3a18, 0xc74b3904, 0x399d9841, 0x053c2d47,
			0xdf3e5d31, 0x9f9e3b3b, 0x91a0d196, 0x0775ef53, 0xd3f5ca07, 0xed96e3bd,
			0x76902f18, 0xf15245f5, 0x6d8592f7, 0x82da6881, 0x0d42eeca, 0x9d0cff24,
			0x529b91f4, 0x5a6be480, 0xd84fdca3, 0xa3ac3f0b, 0x1e1b173c, 0xc198f3ed,
			0xa4835315, 0x286663ba, 0x6f7f0e02, 0x57117b4c, 0x779342f4, 0xd26b4c19,
			0xf7fe4154, 0x2938c0ea, 0xdfc1e721, 0x8878ddfa, 0x2ca3f2f4, 0x864e6d35,
			0x5183dfcf, 0xba27bf53, 0x6dc12abc, 0xcfec1e5f, 0x1286715f, 0x79a436eb,
			0x3e62c3c1, 0xf586cbf2, 0x03d36e97, 0xc12d9745, 0xb830445c, 0xdeacc59b,
			0xf8f3b30d, 0x383f2dd8, 0x94218a13, 0xcfc2fff1, 0x4d6c9a61, 0x80037097,
			0xbe2a1767, 0xc7de564a, 0x382b15ec, 0x36e06537, 0x0b8e0644][:],
			[0xe5621a7d, 0xb0f6475c, 0x3000e4b0, 0x53b8b119, 0x46c9460a, 0xc2c2f64d,
			0x15eb1ed7, 0xa89990fb, 0x193ed8e9, 0xffb67218, 0x08b28715, 0xca5afee2,
			0xa6d74a73, 0xfa6f1d9e, 0x91df97b8, 0x028125e2, 0xb9e08ff2, 0x31bb04c0,
			0xae8c88b1, 0x563530e8, 0x482163de, 0xab6b78e4, 0xf107ede6, 0xd1d56eb3,
			0xac3c6450, 0xa562b28a, 0x0022c497, 0xc0689e89, 0x59111c1e, 0x81909ce5,
			0x7e3e195d, 0xa93f5404, 0x1f0da612, 0xbab3949d, 0xe524ca5e, 0x4313c3cc,
			0x11be62c7, 0x97ac4245, 0xac8bc99d, 0x3689d84a, 0x7c0b6981, 0x3356bbe0,
			0xa4f96426, 0x85ad3a5e, 0x2945bb74, 0x7c57c074, 0x0e5307fa, 0xae84692f,
			0x1d44c111, 0x2043c096, 0xe6cf2147, 0x305537d8, 0xdf8d0c51, 0xc5c14cfe,
			0x580a9f0a, 0x0d792d22, 0x935e2ef6, 0xa7a51a8e, 0x0eb36a53, 0x7f093172,
			0x3822742b, 0xa5808923, 0xd3fd0a04, 0x8fe43041, 0x2b61a5bf, 0x39c323de,
			0x05d607f2, 0xcc0221d3, 0x9c503cfb, 0xd2cb6150, 0xd8469594, 0xdeeefd8e,
			0x70d9a37d, 0x353bd90d, 0x37cc99e0, 0xc676d61d, 0xa6787990, 0xb29db582,
			0xe1a54d0d, 0xed28287f, 0xf3f1985c, 0xa5cb4625, 0x95c4a133, 0x6427168a,
			0x463e52b8, 0x7185af04, 0x3d1d1d4d, 0x3a90b946, 0xb3dd9ac0, 0x6b9888b6,
			0xe0f14a09, 0xdd2cfe25, 0x22f4527f, 0x4c671823, 0xe155d8f6, 0xaedc37f8,
			0x4eaa2b30, 0x71f0c746, 0xfe2eefae, 0xd0fa4c12, 0xb906f9d4, 0x4d97f1a3,
			0x2d3be158, 0x2f4b0c08, 0x8cb52216, 0xef5e2562, 0x3b9102f4, 0x49b0ca12,
			0x535aa042, 0x5b0d8a57, 0xddcc235f, 0x614d76c5, 0xdfbeecec, 0x5561416d,
			0x57b22ea9, 0x7c6e37a2, 0x50277b6a, 0xfd25c564, 0x5274077a, 0xb147e023,
			0xd839a7a1, 0x1f55ae33, 0x1be20d38, 0x1dfb374e, 0x9c45bc7a, 0x9d41e666,
			0x46e571fc, 0x04fad28c, 0xbc498704, 0xf588c11b, 0xdd64929f, 0xb9646dfc,
			0x59413de3, 0xaf1429b0, 0x7c36290e, 0x8a07aebe, 0xce449549, 0x539518c7,
			0x2b92dd06, 0xd49562de, 0x0dd45c70, 0x317f8db6, 0x3dc9ecef, 0x21e70139,
			0xf4ee8863, 0x143b0fac, 0x65e1a3df, 0xa32aec61, 0x66b8cc77, 0x63ab3183,
			0xd88b7a3f, 0xe0c99eec, 0x0a6aa3dc, 0xaa99a520, 0xfd78cbaf, 0x132201e5,
			0xb74ae9ce, 0x6296ed96, 0x88b3ddf8, 0x82b483b2, 0xff6a80c7, 0xdf0598a3,
			0xf5aa6135, 0x86212925, 0x4f6b11cb, 0x6303a5da, 0xfc5ef8a7, 0x567dea22,
			0x463415fd, 0x2a33b1d0, 0x02230e91, 0x0f753876, 0x23eafb0f, 0xd3b2e9aa,
			0x1f2dcf8c, 0xab90f850, 0xbf072716, 0x46adeeec, 0x6d2edd8d, 0xc8b17c0a,
			0xc5f3d74a, 0xc99ba9e9, 0xc0df38dc, 0xc8422337, 0x03bf7f40, 0x00f14447,
			0x01ac58b0, 0x2c8f2eed, 0x89000dc7, 0x269892bf, 0xdad75fc7, 0xfef8b557,
			0xacffa348, 0xc359bb63, 0xe8674c38, 0x57f772e3, 0xe0bfc767, 0xef93703b,
			0xd497c8b5, 0x3d5219e1, 0x3db17f2b, 0x229c4fb2, 0x94c2e9a3, 0x86486d9f,
			0x69c73a0a, 0x5d4c9350, 0x08f77ae6, 0x682bd8b0, 0x482fcee7, 0x67423b8f,
			0xc1a9bf8c, 0xc373e8fd, 0xe7a19ed0, 0xd0b4c812, 0x89dbbcc9, 0x155a254d,
			0x6d541cad, 0xb4c37fc4, 0x296ea17d, 0x2f66047e, 0x381f9ecd, 0x40f26a79,
			0x9fcffc67, 0x8c098c43, 0xfbb93238, 0xca28fe51, 0x381712f9, 0xd1b97c87,
			0xe7187a4e, 0x94b28566, 0xdf009ad6, 0x4b601b00, 0x03b120de, 0xe3b5c0d3,
			0xf3f196be, 0x6b748491, 0xe7524b75, 0x024e81c3, 0x155ffd4b, 0xfdfd6f95,
			0x488ef2d5, 0x3e7c256b, 0xbb7d8fee, 0xe6aa4e12, 0xa7dc14c4, 0x8e7f07db,
			0x3b7b130d, 0xa2993d38, 0xe1af3de9, 0xa4611524, 0x175426ab, 0x9251aadb,
			0x407a68ad, 0x532e4ab0, 0x2f9ff789, 0x0b3beff1, 0x822b0c6e, 0x94ccd66a,
			0x8529ce24, 0xff0188de, 0xb2dff273, 0x08058dbf, 0x9faafe49, 0xbf9a5387,
			0x00000083][:],
			[0x00000000, 0x00000000, 0xbe3ffda0, 0x82979aaa, 0xb9235f84, 0x04421405,
			0x28ab0324, 0xac4b68da, 0x9a4f0ab4, 0xbd71182a, 0xe412b1e1, 0x55141ce9,
			0x30cb7d22, 0x65a20018, 0x4b824f6f, 0x9e197442, 0x979709db, 0x6690672f,
			0x71ee5909, 0xc684a5d9, 0x3b60be23, 0x2387bcb2, 0xdee08193, 0xf64f208f,
			0x18a662b7, 0x037f0fc5, 0xb0b46377, 0x56bd8be1, 0x1c372107, 0xe3714128,
			0x767d7c37, 0x49214d77, 0x317d3a98, 0x81e6d835, 0x26c9cc7c, 0x127a81a5,
			0xa9ca0b59, 0x0e266bb8, 0xb7ce579f, 0xcae5ce06, 0x2685c5e2, 0x783bfdbc,
			0x090647da, 0x04a97a4c, 0xcb19122b, 0x20118309, 0x33de229b, 0x43d75527,
			0x2e8b1c07, 0x48ba85d7, 0xf54e4335, 0xecdd39e5, 0x64be3504, 0xe75167b3,
			0xcd0dbb77, 0x38090e16, 0xf4686dda, 0x47d6585f, 0xd572d8d1, 0x04dde8b1,
			0x1d93b235, 0xb51aaa24, 0xf66eb3ae, 0xa9f5f5ec, 0x1a0ff5f6, 0xc1bbd14a,
			0x3138fa5f, 0xc908a8d3, 0x6bc03615, 0x1af5e37f, 0x7ca06463, 0xbb0ebb30,
			0x8462f81d, 0x2778d2ce, 0x87205714, 0x4c54da67, 0x8c298b46, 0x6cfa4813,
			0x6571c721, 0x9a796e57, 0xa675b885, 0x1eb64a76, 0xebe54e7b, 0x11f653e5,
			0x4834a66b, 0xf609d1b6, 0xb620e147, 0x2392ca9b, 0xd27ee7ed, 0x7eb5c7c2,
			0xa9069748, 0x6adeeb6b, 0xcc07ab10, 0x0da13808, 0xd78edb23, 0x24ab4bc9,
			0x3404c0a1, 0x56119c6a, 0xf6416665, 0x33f4470c, 0xf2aacf62, 0x83c58c47,
			0xe7d9a5fc, 0x59aead51, 0xf4f7364a, 0xdcd4f5f7, 0x6709a431, 0xd10a6bdd,
			0x9d2eb4c9, 0x99ac2098, 0x7019acae, 0xbec04230, 0x5dc42afa, 0xd7a1bc64,
			0xb617190a, 0xbbb89502, 0x53149b0b, 0xc98de46e, 0xf89cab46, 0x75c9340f,
			0xbe4a25cb, 0xa76d3aec, 0xa0031650, 0x8188d222, 0xcefddfb6, 0xfd51b810,
			0x6eda1784, 0x5b41fd3d, 0x714244dc, 0xbc9d1c24, 0x53171ecc, 0x247c6235,
			0x32432b28, 0x7d0ac109, 0xf911b1c4, 0x5dbe82a4, 0x1b63c5c0, 0x9822ff30,
			0x14e1f7f9, 0x86ab98c0, 0xcd969103, 0xdcffed57, 0x985a484a, 0x00754e46,
			0xffa3b7a1, 0x31f1e4ef, 0xe8188d71, 0x565b93ce, 0x072240c4, 0x73a1c849,
			0xe05f999d, 0xd2103ce1, 0x0778a8e2, 0x96168f1a, 0x5c30942a, 0x420d4166,
			0x7d3157da, 0xbb9a4931, 0x012bd8f2, 0x66771ec3, 0x224bd3bb, 0x7fafa887,
			0xe82d297a, 0x1a7a8962, 0x67ee9a9d, 0x57193c34, 0xf22879fb, 0x518eae1d,
			0xf5844664, 0x79052b91, 0x265574d3, 0xe41ddcd5, 0xb0934575, 0xd71a14c1,
			0xb8b39ddd, 0xa11113d6, 0x6ef91c08, 0x290304a0, 0x56603b25, 0xcfc73457,
			0xa52cf8d9, 0xc9497ffc, 0xb05843a2, 0xd5dfa56e, 0x24e7f1ce, 0x283cbfe5,
			0x1f3519dd, 0x3fe86a1b, 0xb29bee1d, 0x7d454b14, 0x57fbaa22, 0xbc3a58b6,
			0x9931bb0a, 0x8240b67c, 0xbec15ccf, 0x9677fdbf, 0xde453b6f, 0x93917fa8,
			0x3653b793, 0x06a2e9f4, 0x677a3a31, 0xa68e508a, 0xc9392611, 0x6315adec,
			0xc0e895e2, 0x37c9a043, 0x7cb07fd7, 0x450417a9, 0x54b9acb4, 0x76414b62,
			0xdc6128e5, 0xc75a67e7, 0x4533f93f, 0xda0e6a3c, 0xfc7461ef, 0xc53a5440,
			0xe8aede4f, 0x655e62dc, 0x33bcec2b, 0xe0e6497f, 0xcb40f223, 0xa425fbd2,
			0x5c14cfc3, 0x5c0c8a72, 0x1ef898ac, 0x95a3edbb, 0xb520a67f, 0xc6410c1f,
			0x23cd82c3, 0xf26d59ea, 0x578f1a28, 0x4870b3c4, 0x91e0ab6b, 0x2f146b6c,
			0x52012d4f, 0x61a38d2a, 0x9f61eeb9, 0xa4b093eb, 0x6e90b268, 0x1e87f1a9,
			0xe9923052, 0x09e43b35, 0xe5852a70, 0xacd454e2, 0xb1a5a567, 0x09439ed5,
			0x79aab59c, 0xc456aaaa, 0x783983f1, 0xf8963bcf, 0xe063f94c, 0xbe5ec39b,
			0x237798db, 0x572ee3e1, 0xf656f0b6, 0x409ca341, 0x9405fc6c, 0x459f1382,
			0x145b0b46, 0x054d0d28, 0xc0502da9, 0x23d7965d, 0xc04e09b9, 0xcc82c64e,
			0x2da02d3a, 0x3d578803, 0xa0373dc5, 0x10f715cc, 0x38badb6f, 0x7e1ebd29,
			0xd80beefe, 0x2a01de6f, 0x47cfaf0a, 0x961e2329, 0x681767c6, 0xe1f26e44,
			0x73e32959, 0x3d5516ba, 0x33150281, 0xf0e32acb, 0x2ff58942, 0x3a81d0f8,
			0x0537dcd9, 0x66bf7242, 0xd239462c, 0x67815ee0, 0xf3602fc8, 0x63379c53,
			0x6038fb63, 0x16fe7fd4, 0xdf2a7271, 0xe388af54, 0x837a99ed, 0x23dfbfc6,
			0x9f5a7bf7, 0xe2903d2d, 0xca0298a5, 0xd19ba36e, 0xa936e528, 0x32ba65b1,
			0x65943496, 0x62a80493, 0x0ab3057a, 0xf7f18bc1, 0x995188be, 0x1dfcf7c8,
			0xa161ccfd, 0xa303757d, 0x3a8aa296, 0x551b6caf, 0xe977eef2, 0x0bd85cf8,
			0xc2af8f39, 0x5bf8952a, 0x7acef741, 0x0ab1771a, 0x0156008c, 0xfa3facea,
			0x1d25085f, 0x6a9e94ea, 0x7c2f77cd, 0x2ec7c794, 0xdde58996, 0x57a55297,
			0x9398de73, 0xe773282e, 0xc5ce08db, 0x83009b93, 0x530dbb2d, 0x97fd15c3,
			0xa6ce14cb, 0x576506a0, 0x26c0d23f, 0xb224fbe2, 0x08bdfeb4, 0xa0829671,
			0xd713b291, 0x50f47f73, 0x04f4dac5, 0x14c05208, 0x8444aa80, 0x1c4493d9,
			0xc6129bbb, 0x8e287680, 0xd348d4b1, 0x6710a259, 0xa31505ce, 0xb03f4c69,
			0xc5d524a6, 0x093332b8, 0x1c443255, 0xe0a67d66, 0xe4c0a9fc, 0xc39980f9,
			0xc3016d16, 0x6dbc33aa, 0xaaaf7f7a, 0x49e7e357, 0x8b7c1cc2, 0xbf9b3ccf,
			0x6710a38a, 0x23bc2ee9, 0x3ac655d1, 0x54909b56, 0x69e72155, 0xbd60706e,
			0x4c3cde2c, 0x1e79c4cb, 0x9c6199cb, 0x622363a2, 0x56e86c30, 0xf1110343,
			0x390ecc6d, 0x0cebbb28, 0xe430de2c, 0x2da244ee, 0xffee679b, 0xd74aaa35,
			0x341080b9, 0x841d42cb, 0xea44a03a, 0x68690521, 0xc2c02368, 0x519e0a3e,
			0xfc5316d3, 0xfa07bffa, 0x5b7ff4de, 0x3f284fc0, 0xd5298b15, 0xa34df1ad,
			0x3310e56f, 0xa6a7b5d9, 0x5311d3f0, 0xaa20df2a, 0x62f3940e, 0xbf9e92ea,
			0x884085dc, 0xe7f5d811, 0x4929e44e, 0xddd835cd, 0x5165edf4, 0x59e39525,
			0xae54cfaf, 0x887cdaea, 0xf4aaa590, 0xa6f4996b, 0x448d0000, 0xfb087d2f,
			0x161986ba, 0xb8074968, 0x15a4b409, 0x452286b0, 0xd7678ec8, 0xe08ee9ab,
			0xb84a452e, 0x8be3020b, 0x9861f3b9, 0x7e9a0e5a, 0xfd36a044, 0x3a7bc5f6,
			0xda5049c3, 0xc7a81a96, 0xa2dc3955, 0xab6bc016, 0x9383ec7c, 0x807aa367,
			0x2940d087, 0x137142ec, 0x378b956a, 0x35974daa, 0xdde753c7, 0x50bbb74f,
			0xa783762c, 0x853112e9, 0x5827ab32, 0x5b1ca0cd, 0x3b19be68, 0xd018137a,
			0x641a8394, 0x55d94c04, 0xb90f0637, 0xe335c233, 0xf63c2d18, 0x488ad935,
			0xc91097f0, 0xb3125f28, 0x40281ae9, 0x118e5b7b, 0x6730822f, 0xafd46678,
			0x2f349032, 0x3d23f660, 0xe9c8c940, 0xbe013000, 0xe831b243, 0x83b6be88,
			0x09f664ef, 0xf5e28265, 0x242107c2, 0x08d8c500, 0xf237e14f, 0x7081d19f,
			0x8ac71ab5, 0xd163e11d, 0xd425148a, 0x0f94724c, 0x381c0ef4, 0xb3196dad,
			0x62f53c77, 0xd8661911, 0x7b55387a, 0x05a155a6, 0x393f1c55, 0xb934a609,
			0xb18e5d81, 0x007224ad, 0x2bb4508f, 0xc9c87369, 0xb84821ce, 0x9070c6b3,
			0xfd371781, 0xd927036a, 0x032d173c, 0xc598df4a, 0xf3bc6d10, 0xf3ba63b1,
			0x6858c1b7, 0xd0ebf6e0, 0xde64f41f, 0x8e217531, 0x36403e12, 0x7c7aad22,
			0xe76fd6cf, 0xfbc5602b, 0xdfdd0451, 0x57859ce7, 0xb96c78e4, 0xf87ccd9d,
			0x6554c42e, 0xa4e4132d, 0xa6e1ab00, 0x933b6684, 0xfb6234c7, 0x75adffb8,
			0x55d835f1, 0xb91aeca8, 0xb58f54d9, 0x7c0a51d3, 0x48f1c33d, 0x2fcd22e9,
			0x67d2854d, 0xa8a0ec60, 0xa426d787, 0x89100511, 0xa5dc1a28, 0x030deedb,
			0x5594c424, 0x58d45125, 0x5116afb8, 0x665e5006, 0x8bf53db8, 0x533d88d5,
			0x7ad58de2, 0xa5aa816e, 0x42c866ea, 0xe9f09335, 0xf25322c9, 0x00000005
			][:]),
	][:]

	for (id, a_dig, b_dig, exp_dig) : inputs
		var a = [ .sign = 1, .dig = a_dig ]
		var b = [ .sign = 1, .dig = b_dig ]
		var exp_base = [ .sign = 1, .dig = exp_dig ]
		var exp = &exp_base
		var act = std.bigdup(&a)
		std.bigmul(act, &b)
		testr.check(c, std.bigeq(exp, act), "input #{}: a0 = 0x{x,w=8,p=0}, b0 = 0x{x,w=8,p=0}, exp0 = 0x{x,w=8,p=0}, act0=0x{x,w=8,p=0}", id, a.dig[0], b.dig[0], exp.dig[0], act.dig[0])
	;;
}