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