1// Copyright 2018 The Wuffs Authors. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// https://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package interval 16 17// This file provides "radial numbers", which partition the infinite set 18// ℤ∪{NaN} into a finite number of boxes. The source set ℤ∪{NaN} is the set of 19// integers, ℤ, augmented with a "Not a Number" element to represent the result 20// of computations such as a division by zero or a shift by a negative integer. 21// NaN-ness is viral: if x or y is NaN then (x op y) is also NaN, for any 22// binary operator op. 23// 24// Specifically, there are (2*R + 4) boxes, for some non-negative integer 25// radius R, and all but two of them contain exactly one element. There are 26// (2*R + 1) single-element boxes for "small" integers: those whose absolute 27// values are less than or equal to R. There is another single-element box for 28// NaN. The two remaining boxes hold "large" integers: those that are less than 29// -R and those that are greater than +R. 30// 31// A rough analogy for a radial number is a primitive counting system: one, 32// two, three, many. 33// 34// This file defines two concrete "radial number" types: 35// - radialInput has a radius R of 15. 36// - radialOutput has a radius R of 16 << 16 (which equals 1048576). 37// 38// If x and y are "small" radialInput values or one of the two "smallest large" 39// radialInput values, i.e. x and y are in the range [-16 ..= +16], then (x op 40// y) will always be a "small" radialOutput value, for the common binary 41// operators: add, subtract, multiply, divide, left-shift, right-shift, and, 42// or. 43// 44// Both of these radialInput and radialOutput types are encoded as an int32: 45// - math.MinInt32 (which equals -1 << 31) encodes a NaN. 46// - "small" numbers (within the interval [-R ..= +R]) encode themselves. 47// - any other negative int32 encodes "less than -R". 48// - any other positive int32 encodes "greater than +R". 49// 50// For example, radialInput(20) and radialInput(30) represent the same box: 51// integers greater than +15. 52// 53// Binary operators take two radialInput values and produce a pair of 54// radialOutput values: either a [min ..= max] interval, or [NaN ..= NaN]. For 55// example, adding the "-3" box to the "greater than +15" box would produce the 56// radialOutPair ["13" ..= "greater than +16 << 16"], or in more conventional 57// notation, the half-open interval [13 ..= +∞]. 58// 59// These radial number types are not exported by package interval, as the 60// radius values (15 and 16 << 16) are somewhat arbitrary and not so generally 61// useful. They are only used for brute force testing in interval_test.go. When 62// tests in that other file use radial numbers (via calling the bruteForce 63// function), the test cases are constructed so that every non-nil member of an 64// interval.IntRange maps to a "small" radialInput, and asSmallRadialInput will 65// panic if that doesn't hold. 66// 67// These types exist in order to simplify calculations. The general problem of 68// calculating bounds for (x * y), given intervals for x and y, becomes 69// complicated if e.g. x's possible values include both positive and negative 70// numbers. In comparison, a radial number's box is either a single value, or 71// if multiple values, those values all have the same sign. Computation on 72// "small" radial numbers can use Go's built-in operators (+, -, etc) instead 73// of the clumsier *big.Int API. 74// 75// The radial number methods like Add and Mul also have a simpler API than the 76// corresponding *big.Int methods, since the radial number methods don't 77// allocate memory or therefore need a destination argument. 78 79import ( 80 "math/big" 81) 82 83const ( 84 radialNaN = -1 << 31 85 86 // Note that radialInput.And and radialInput.Or require that (riRadius + 1) 87 // is a power of 2. 88 riRadius = 15 89 roRadius = 16 << 16 90 91 roLargeNeg = -(16<<16 + 1) 92 roLargePos = +(16<<16 + 1) 93) 94 95type ( 96 radialInput int32 97 radialOutput int32 98 radialOutPair [2]radialOutput 99) 100 101func (x radialInput) canonicalize() radialOutput { 102 o := radialOutput(x) 103 if o != radialNaN { 104 // No-op. 105 } else if o < -riRadius { 106 return -riRadius - 1 107 } else if o > +riRadius { 108 return +riRadius + 1 109 } 110 return o 111} 112 113func (x radialOutput) bigInt() *big.Int { 114 if x < -roRadius || +roRadius < x { 115 return nil 116 } 117 return big.NewInt(int64(x)) 118} 119 120func asSmallRadialInput(x *big.Int, defaultIfXIsNil radialInput) radialInput { 121 if x == nil { 122 return defaultIfXIsNil 123 } 124 if !x.IsInt64() { 125 panic("asSmallRadialInput passed too large a value") 126 } 127 i := x.Int64() 128 if i < -riRadius || +riRadius < i { 129 panic("asSmallRadialInput passed too large a value") 130 } 131 return radialInput(i) 132} 133 134func enumerate(x IntRange) (min radialInput, max radialInput) { 135 if x.Empty() { 136 return +1, -1 137 } 138 return asSmallRadialInput(x[0], -riRadius-1), asSmallRadialInput(x[1], +riRadius+1) 139} 140 141func (x radialInput) Add(y radialInput) radialOutPair { 142 if x == radialNaN || y == radialNaN { 143 return radialOutPair{radialNaN, radialNaN} 144 } 145 ox := x.canonicalize() 146 oy := y.canonicalize() 147 148 switch { 149 case ox < -riRadius: 150 if oy > +riRadius { 151 return radialOutPair{roLargeNeg, roLargePos} 152 } 153 return radialOutPair{roLargeNeg, ox + oy} 154 case ox > +riRadius: 155 if oy < -riRadius { 156 return radialOutPair{roLargeNeg, roLargePos} 157 } 158 return radialOutPair{ox + oy, roLargePos} 159 default: 160 switch { 161 case oy < -riRadius: 162 return radialOutPair{roLargeNeg, ox + oy} 163 case oy > +riRadius: 164 return radialOutPair{ox + oy, roLargePos} 165 default: 166 return radialOutPair{ox + oy, ox + oy} 167 } 168 } 169} 170 171func (x radialInput) Sub(y radialInput) radialOutPair { 172 if x == radialNaN || y == radialNaN { 173 return radialOutPair{radialNaN, radialNaN} 174 } 175 ox := x.canonicalize() 176 oy := y.canonicalize() 177 178 switch { 179 case ox < -riRadius: 180 switch { 181 case oy < -riRadius, oy > +riRadius: 182 return radialOutPair{roLargeNeg, roLargePos} 183 default: 184 return radialOutPair{roLargeNeg, ox - oy} 185 } 186 case ox > +riRadius: 187 switch { 188 case oy < -riRadius, oy > +riRadius: 189 return radialOutPair{roLargeNeg, roLargePos} 190 default: 191 return radialOutPair{ox - oy, roLargePos} 192 } 193 default: 194 switch { 195 case oy < -riRadius: 196 return radialOutPair{ox - oy, roLargePos} 197 case oy > +riRadius: 198 return radialOutPair{roLargeNeg, ox - oy} 199 default: 200 return radialOutPair{ox - oy, ox - oy} 201 } 202 } 203} 204 205func (x radialInput) Mul(y radialInput) radialOutPair { 206 if x == radialNaN || y == radialNaN { 207 return radialOutPair{radialNaN, radialNaN} 208 } 209 ox := x.canonicalize() 210 oy := y.canonicalize() 211 212 switch { 213 case ox < -riRadius: 214 if oy < 0 { 215 return radialOutPair{ox * oy, roLargePos} 216 } else if oy > 0 { 217 return radialOutPair{roLargeNeg, ox * oy} 218 } 219 return radialOutPair{0, 0} 220 case ox > +riRadius: 221 if oy < 0 { 222 return radialOutPair{roLargeNeg, ox * oy} 223 } else if oy > 0 { 224 return radialOutPair{ox * oy, roLargePos} 225 } 226 return radialOutPair{0, 0} 227 default: 228 switch { 229 case oy < -riRadius: 230 if ox < 0 { 231 return radialOutPair{ox * oy, roLargePos} 232 } else if ox > 0 { 233 return radialOutPair{roLargeNeg, ox * oy} 234 } 235 return radialOutPair{0, 0} 236 case oy > +riRadius: 237 if ox < 0 { 238 return radialOutPair{roLargeNeg, ox * oy} 239 } else if ox > 0 { 240 return radialOutPair{ox * oy, roLargePos} 241 } 242 return radialOutPair{0, 0} 243 default: 244 return radialOutPair{ox * oy, ox * oy} 245 } 246 } 247} 248 249func (x radialInput) Lsh(y radialInput) radialOutPair { 250 if x == radialNaN || y == radialNaN || y < 0 { 251 return radialOutPair{radialNaN, radialNaN} 252 } 253 ox := x.canonicalize() 254 oy := uint32(y.canonicalize()) 255 256 switch { 257 case ox < -riRadius: 258 return radialOutPair{roLargeNeg, ox << oy} 259 case ox > +riRadius: 260 return radialOutPair{ox << oy, roLargePos} 261 default: 262 if oy <= +riRadius { 263 return radialOutPair{ox << oy, ox << oy} 264 } else if ox < 0 { 265 return radialOutPair{roLargeNeg, ox << oy} 266 } else if ox > 0 { 267 return radialOutPair{ox << oy, roLargePos} 268 } 269 return radialOutPair{0, 0} 270 } 271} 272 273func (x radialInput) Quo(y radialInput) radialOutPair { 274 if x == radialNaN || y == radialNaN || y == 0 { 275 return radialOutPair{radialNaN, radialNaN} 276 } 277 ox := x.canonicalize() 278 oy := y.canonicalize() 279 280 switch { 281 case ox < -riRadius: 282 switch { 283 case oy < -riRadius: 284 return radialOutPair{0, roLargePos} 285 case oy > +riRadius: 286 return radialOutPair{roLargeNeg, 0} 287 default: 288 if oy < 0 { 289 return radialOutPair{ox / oy, roLargePos} 290 } 291 return radialOutPair{roLargeNeg, ox / oy} 292 } 293 case ox > +riRadius: 294 switch { 295 case oy < -riRadius: 296 return radialOutPair{roLargeNeg, 0} 297 case oy > +riRadius: 298 return radialOutPair{0, roLargePos} 299 default: 300 if oy < 0 { 301 return radialOutPair{roLargeNeg, ox / oy} 302 } 303 return radialOutPair{ox / oy, roLargePos} 304 } 305 default: 306 switch { 307 case oy < -riRadius, oy > +riRadius: 308 return radialOutPair{0, 0} 309 default: 310 return radialOutPair{ox / oy, ox / oy} 311 } 312 } 313} 314 315func (x radialInput) Rsh(y radialInput) radialOutPair { 316 if x == radialNaN || y == radialNaN || y < 0 { 317 return radialOutPair{radialNaN, radialNaN} 318 } 319 ox := x.canonicalize() 320 oy := uint32(y.canonicalize()) 321 322 switch { 323 case ox < -riRadius: 324 if oy > +riRadius { 325 return radialOutPair{roLargeNeg, -1} 326 } 327 return radialOutPair{roLargeNeg, ox >> oy} 328 case ox > +riRadius: 329 if oy > +riRadius { 330 return radialOutPair{0, roLargePos} 331 } 332 return radialOutPair{ox >> oy, roLargePos} 333 default: 334 if oy <= +riRadius { 335 return radialOutPair{ox >> oy, ox >> oy} 336 } else if ox < 0 { 337 return radialOutPair{-1, -1} 338 } 339 return radialOutPair{0, 0} 340 } 341} 342 343func (x radialInput) And(y radialInput) radialOutPair { 344 if x == radialNaN || y == radialNaN { 345 return radialOutPair{radialNaN, radialNaN} 346 } 347 ox := x.canonicalize() 348 oy := y.canonicalize() 349 350 // r is a power of 2, so that its binary representation contains one "1" 351 // digit, and that digit is not shared with any "small" value <= riRadius. 352 const r = riRadius + 1 353 354 if ox < -riRadius { 355 if oy < -riRadius { 356 return radialOutPair{roLargeNeg, -r} 357 } else if oy > +riRadius { 358 return radialOutPair{0, roLargePos} 359 } else if oy < 0 { 360 return radialOutPair{roLargeNeg, -r} 361 } else { 362 return radialOutPair{0, oy} 363 } 364 } else if ox > +riRadius { 365 if oy < -riRadius { 366 return radialOutPair{0, roLargePos} 367 } else if oy > +riRadius { 368 return radialOutPair{0, roLargePos} 369 } else if oy < 0 { 370 return radialOutPair{+r, roLargePos} 371 } else { 372 return radialOutPair{0, oy} 373 } 374 } 375 376 if oy < -riRadius { 377 if ox < 0 { 378 return radialOutPair{roLargeNeg, -r} 379 } else { 380 return radialOutPair{0, ox} 381 } 382 } else if oy > +riRadius { 383 if ox < 0 { 384 return radialOutPair{+r, roLargePos} 385 } else { 386 return radialOutPair{0, ox} 387 } 388 } 389 390 return radialOutPair{ox & oy, ox & oy} 391} 392 393func (x radialInput) Or(y radialInput) radialOutPair { 394 if x == radialNaN || y == radialNaN { 395 return radialOutPair{radialNaN, radialNaN} 396 } 397 ox := x.canonicalize() 398 oy := y.canonicalize() 399 400 // r is a power of 2, so that its binary representation contains one "1" 401 // digit, and that digit is not shared with any "small" value <= riRadius. 402 const r = riRadius + 1 403 404 if ox < -riRadius { 405 if oy < -riRadius { 406 return radialOutPair{roLargeNeg, -1} 407 } else if oy > +riRadius { 408 return radialOutPair{roLargeNeg, -1} 409 } else if oy < 0 { 410 return radialOutPair{oy, -1} 411 } else { 412 return radialOutPair{roLargeNeg, oy | -r} 413 } 414 } else if ox > +riRadius { 415 if oy < -riRadius { 416 return radialOutPair{roLargeNeg, -1} 417 } else if oy > +riRadius { 418 return radialOutPair{+r, roLargePos} 419 } else if oy < 0 { 420 return radialOutPair{oy, -1} 421 } else { 422 return radialOutPair{oy | +r, roLargePos} 423 } 424 } 425 426 if oy < -riRadius { 427 if ox < 0 { 428 return radialOutPair{ox, -1} 429 } else { 430 return radialOutPair{roLargeNeg, ox | -r} 431 } 432 } else if oy > +riRadius { 433 if ox < 0 { 434 return radialOutPair{ox, -1} 435 } else { 436 return radialOutPair{ox | +r, roLargePos} 437 } 438 } 439 440 return radialOutPair{ox | oy, ox | oy} 441} 442 443var riOperators = map[rune]func(radialInput, radialInput) radialOutPair{ 444 '+': radialInput.Add, 445 '-': radialInput.Sub, 446 '*': radialInput.Mul, 447 '/': radialInput.Quo, 448 '«': radialInput.Lsh, 449 '»': radialInput.Rsh, 450 '&': radialInput.And, 451 '|': radialInput.Or, 452} 453 454func bruteForce(x IntRange, y IntRange, opKey rune) (z IntRange, ok bool) { 455 op := riOperators[opKey] 456 iMin, iMax := enumerate(x) 457 jMin, jMax := enumerate(y) 458 result := radialOutPair{} 459 first := true 460 merge := func(k radialOutPair) { 461 if first { 462 result = k 463 first = false 464 return 465 } 466 if result[0] > k[0] { 467 result[0] = k[0] 468 } 469 if result[1] < k[1] { 470 result[1] = k[1] 471 } 472 } 473 474 switch opKey { 475 case '∪': 476 if iMinC, iMaxC := iMin.canonicalize(), iMax.canonicalize(); iMinC <= iMaxC { 477 merge(radialOutPair{iMinC, iMaxC}) 478 } 479 if jMinC, jMaxC := jMin.canonicalize(), jMax.canonicalize(); jMinC <= jMaxC { 480 merge(radialOutPair{jMinC, jMaxC}) 481 } 482 if result[0] < -riRadius { 483 result[0] = -roRadius - 1 484 } 485 if result[1] > +riRadius { 486 result[1] = +roRadius + 1 487 } 488 489 case '∩': 490 iMinC, iMaxC := iMin.canonicalize(), iMax.canonicalize() 491 for j := jMin; j <= jMax; j++ { 492 jC := j.canonicalize() 493 if (iMinC <= jC) && (jC <= iMaxC) { 494 merge(radialOutPair{jC, jC}) 495 } 496 } 497 if result[0] < -riRadius { 498 result[0] = -roRadius - 1 499 } 500 if result[1] > +riRadius { 501 result[1] = +roRadius + 1 502 } 503 504 default: 505 for i := iMin; i <= iMax; i++ { 506 for j := jMin; j <= jMax; j++ { 507 k := op(i, j) 508 if k[0] == radialNaN || k[1] == radialNaN { 509 return IntRange{}, false 510 } 511 merge(k) 512 } 513 } 514 } 515 516 if first { 517 return makeEmptyRange(), true 518 } 519 return IntRange{result[0].bigInt(), result[1].bigInt()}, true 520} 521