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 }