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 divison and
10// modulus operators.
11//
12// Primarily useful for testing software div/mod.
13
14package main
15
16const long = false
17
18func 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.
33func gen1(n, w int, f func(uint64)) {
34	gen(0, 0, n, w-1, f)
35}
36
37func 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.
50func 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).
61func 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
82func checkdiv2(x, y uint64) {
83	checkdiv3(x, y)
84	checkdiv3(^x, y)
85	checkdiv3(x, ^y)
86	checkdiv3(^x, ^y)
87}
88
89var ntest int64 = 0
90
91func 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
124func 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
141func 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
158func 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
175func 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
192func 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
209func 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
226func 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
243func 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
260func 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
277func 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
294func divzerouint(x, y uint) uint {
295	defer checkudivzero("uint", uint64(x))
296	return x / y
297}
298
299func divzerouint64(x, y uint64) uint64 {
300	defer checkudivzero("uint64", uint64(x))
301	return x / y
302}
303
304func divzerouint32(x, y uint32) uint32 {
305	defer checkudivzero("uint32", uint64(x))
306	return x / y
307}
308
309func divzerouint16(x, y uint16) uint16 {
310	defer checkudivzero("uint16", uint64(x))
311	return x / y
312}
313
314func divzerouint8(x, y uint8) uint8 {
315	defer checkudivzero("uint8", uint64(x))
316	return x / y
317}
318
319func checkudivzero(typ string, x uint64) {
320	if recover() == nil {
321		print(typ, "(", x, " / 0) did not panic")
322	}
323}
324
325func divzeroint(x, y int) int {
326	defer checkdivzero("int", int64(x))
327	return x / y
328}
329
330func divzeroint64(x, y int64) int64 {
331	defer checkdivzero("int64", int64(x))
332	return x / y
333}
334
335func divzeroint32(x, y int32) int32 {
336	defer checkdivzero("int32", int64(x))
337	return x / y
338}
339
340func divzeroint16(x, y int16) int16 {
341	defer checkdivzero("int16", int64(x))
342	return x / y
343}
344
345func divzeroint8(x, y int8) int8 {
346	defer checkdivzero("int8", int64(x))
347	return x / y
348}
349
350func checkdivzero(typ string, x int64) {
351	if recover() == nil {
352		print(typ, "(", x, " / 0) did not panic")
353	}
354}
355
356func modzerouint(x, y uint) uint {
357	defer checkumodzero("uint", uint64(x))
358	return x % y
359}
360
361func modzerouint64(x, y uint64) uint64 {
362	defer checkumodzero("uint64", uint64(x))
363	return x % y
364}
365
366func modzerouint32(x, y uint32) uint32 {
367	defer checkumodzero("uint32", uint64(x))
368	return x % y
369}
370
371func modzerouint16(x, y uint16) uint16 {
372	defer checkumodzero("uint16", uint64(x))
373	return x % y
374}
375
376func modzerouint8(x, y uint8) uint8 {
377	defer checkumodzero("uint8", uint64(x))
378	return x % y
379}
380
381func checkumodzero(typ string, x uint64) {
382	if recover() == nil {
383		print(typ, "(", x, " % 0) did not panic")
384	}
385}
386
387func modzeroint(x, y int) int {
388	defer checkmodzero("int", int64(x))
389	return x % y
390}
391
392func modzeroint64(x, y int64) int64 {
393	defer checkmodzero("int64", int64(x))
394	return x % y
395}
396
397func modzeroint32(x, y int32) int32 {
398	defer checkmodzero("int32", int64(x))
399	return x % y
400}
401
402func modzeroint16(x, y int16) int16 {
403	defer checkmodzero("int16", int64(x))
404	return x % y
405}
406
407func modzeroint8(x, y int8) int8 {
408	defer checkmodzero("int8", int64(x))
409	return x % y
410}
411
412func 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.
419func 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.
437func 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