| blob | a252cd75ff586710667b1a67d7a3a830406032c7 |
1 ;;;; This file contains DERIVE-TYPE methods for LOGAND, LOGIOR, and
2 ;;;; friends.
4 ;;;; This software is part of the SBCL system. See the README file for
5 ;;;; more information.
6 ;;;;
7 ;;;; This software is derived from the CMU CL system, which was
8 ;;;; written at Carnegie Mellon University and released into the
9 ;;;; public domain. The software is in the public domain and is
10 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
11 ;;;; files for more information.
15 ;;; Return the maximum number of bits an integer of the supplied type
16 ;;; can take up, or NIL if it is unbounded. The second (third) value
17 ;;; is T if the integer can be positive (negative) and NIL if not.
18 ;;; Zero counts as positive.
28 ;;;; Generators for simple bit masks
30 ;;; Return an integer consisting of zeroes in its N least significant
31 ;;; bit positions and ones in all others. If N is negative, return -1.
36 ;;; Return an integer consisting of ones in its N least significant
37 ;;; bit positions and zeroes in all others. If N is negative, return 0.
42 ;;; The functions LOG{AND,IOR,XOR}-DERIVE-UNSIGNED-BOUNDS below use
43 ;;; algorithms derived from those in the chapter "Propagating Bounds
44 ;;; through Logical Operations" from _Hacker's Delight_, Henry S.
45 ;;; Warren, Jr., 2nd ed., pp 87-90.
46 ;;;
47 ;;; We used to implement the algorithms from that source (then its first
48 ;;; edition) very faithfully here which exposed a weakness of theirs,
49 ;;; namely worst case quadratical runtime in the number of bits of the
50 ;;; input values, potentially leading to excessive compilation times for
51 ;;; expressions involving bignums. To avoid that, I have devised and
52 ;;; implemented variations of these algorithms that achieve linear
53 ;;; runtime in all cases.
54 ;;;
55 ;;; Like Warren, let's start with the high bound on LOGIOR to explain
56 ;;; how this is done. To follow, please read Warren's explanations on
57 ;;; his "maxOR" function and compare this with how the second return
58 ;;; value of LOGIOR-DERIVE-UNSIGNED-BOUNDS below is calculated.
59 ;;;
60 ;;; "maxOR" loops starting from the left until it finds a position where
61 ;;; both B and D are 1 and where it is possible to decrease one of these
62 ;;; bounds by setting this bit in it to 0 and all following ones to 1
63 ;;; without the resulting value getting below the corresponding lower
64 ;;; bound (A or C). This is done by calculating the modified values
65 ;;; during each iteration where both B and D are 1 and comparing them
66 ;;; against the lower bounds.
67 ;;; The trick to avoid the loop is to exchange the order of the steps:
68 ;;; First determine from which position rightwards it would be allowed
69 ;;; to change B or D in this way and have the result be larger or equal
70 ;;; than A or C respectively and then find the leftmost position equal
71 ;;; to this or to the right of it where both B and D are 1.
72 ;;; It is quite simple to find from where rightwards B could be modified
73 ;;; this way: This is the leftmost position where B has a 1 and A a 0,
74 ;;; or, cheaper to calculate, the leftmost position where A and B
75 ;;; differ. Thus (INTEGER-LENGTH (LOGXOR A B)) gives us this position
76 ;;; where a result of 1 corresponds to the rightmost bit position. As we
77 ;;; don't care which of B or D we modify we can take the maximum of this
78 ;;; value and of (INTEGER-LENGTH (LOGXOR C D)).
79 ;;; The rest is equally simple: Build a mask of 1 bits from the thusly
80 ;;; found position rightwards, LOGAND it with B and D and feed that into
81 ;;; INTEGER-LENGTH. From this build another mask and LOGIOR it with B
82 ;;; and D to set the desired bits.
83 ;;; The special cases where A equals B and/or C equals D are covered by
84 ;;; the same code provided the mask generator treats an argument of -1
85 ;;; the same as 0, which both ZEROES and ONES do.
86 ;;;
87 ;;; To calculate the low bound on LOGIOR we need to treat X and Y
88 ;;; independently for longer but the basic idea stays the same.
89 ;;;
90 ;;; LOGAND-DERIVE-UNSIGNED-BOUNDS can be derived by sufficiently many
91 ;;; applications of DeMorgan's law from LOGIOR-DERIVE-UNSIGNED-BOUNDS.
92 ;;; The implementation additionally avoids work (that is, calculations
93 ;;; of one's complements) by using the identity (INTEGER-LENGTH X) =
94 ;;; (INTEGER-LENGTH (LOGNOT X)) and observing that ZEROES is cheaper
95 ;;; than ONES.
96 ;;;
97 ;;; For the low bound on LOGXOR we use Warren's formula
98 ;;; minXOR(a, b, c, d) = minAND(a, b, !d, !c) | minAND(!b, !a, c, d)
99 ;;; where "!" is bitwise negation and "|" is bitwise or. Both minANDs
100 ;;; are implemented as in LOGAND-DERIVE-UNSIGNED-BOUNDS (the part for
101 ;;; the first result), sharing the first LOGXOR and INTEGER-LENGTH
102 ;;; calculations as (LOGXOR A B) = (LOGXOR (LOGNOT B) (LOGNOT A)).
103 ;;;
104 ;;; For the high bound on LOGXOR Warren's formula seems unnecessarily
105 ;;; complex. Instead, with (LOGNOT (LOGXOR X Y)) = (LOGXOR X (LOGNOT Y))
106 ;;; we have
107 ;;; maxXOR(a, b, c, d) = !minXOR(a, b, !d, !c)
108 ;;; and rewriting minXOR as above yields
109 ;;; maxXOR(a, b, c, d) = !(minAND(a, b, c, d) | minAND(!b, !a, !d, !c))
110 ;;; This again shares the first LOGXOR and INTEGER-LENGTH calculations
111 ;;; between both minANDs and with the ones for the low bound.
112 ;;;
113 ;;; LEU, 2013-04-29.
131 ;; Both indexes are 0 here.
146 ;; X must be positive.
148 ;; They must both be positive.
159 ;; X is positive, but Y might be negative.
164 ;; X might be negative.
166 ;; Y must be positive.
170 ;; Either might be negative.
172 ;; The result is bounded.
174 ;; We can't tell squat about the result.
190 ;; Both indexes are 0 here.
207 ;; Both are positive.
214 ;; X must be negative.
216 ;; Both are negative. The result is going to be negative
217 ;; and be the same length or shorter than the smaller.
219 ;; It's bounded.
221 ;; It's unbounded.
223 ;; X is negative, but we don't know about Y. The result
224 ;; will be negative, but no more negative than X.
229 ;; X might be either positive or negative.
231 ;; But Y is negative. The result will be negative.
235 ;; We don't know squat about either. It won't get any bigger.
237 ;; Bounded.
239 ;; Unbounded.
269 ;; Both are positive
276 ;; Both are negative. The result will be positive, and as long
277 ;; as the longer.
280 '*))))
283 ;; Either X is negative and Y is positive or vice-versa. The
284 ;; result will be negative.
287 '*)
289 ;; We can't tell what the sign of the result is going to be.
290 ;; All we know is that we don't create new bits.