Update copyright to LGPL on all files
[dyninst.git] / common / src / fraction.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #include "common/h/fraction.h"
33 #include "common/h/int64iostream.h"
34
35 fraction::ostream_fmt fraction::curFmt = sparse;
36
37 /*
38 const fraction operator*(const fraction &a, const fraction &b) {
39   if(b.getNumer() < a.getMultOverflowPt()) {
40     return fraction(a.getNumer() * b.getNumer(), a.getDenom() * b.getDenom());
41   } else {
42     fraction c = a * b.getNumer();
43     c.setDenom(c.getDenom()*b.getDenom());
44     return c;
45   }
46 };
47 */
48
49 int64_t lcd(int64_t a, int64_t b) {
50   int64_t _gcd = gcd(a,b);
51   if(a > b) { a = a / _gcd; }
52   else      { b = b / _gcd; }
53   int64_t overflowPt = I64_MAX / b;
54   if(a > overflowPt) {  cerr << "lcd: overflow\n";  return -1; }
55   return a * b;
56 }
57
58 int64_t gcd(int64_t a, int64_t b) {
59   if (b == 0) return a;
60   return gcd(b, a % b);
61 }
62
63 // fraction + fraction
64 /*const fraction operator+(const fraction &a, const fraction &b) {
65   if(a.getDenom() == b.getDenom()) {
66     return fraction(a.getNumer() + b.getNumer(), a.getDenom());
67   } else {
68     int64_t ilcd = lcd(a.getDenom(), b.getDenom());
69     return fraction(a.getNumer()*ilcd + b.getNumer()*ilcd, a.getDenom()*ilcd);
70   }
71 }
72
73 // fraction - fraction
74 const fraction operator-(const fraction &a, const fraction &b) {
75   if(a.getDenom() == b.getDenom()) {
76     return fraction(a.getNumer() - b.getNumer(), a.getDenom());
77   } else {
78     int64_t ilcd = lcd(a.getDenom(), b.getDenom());
79     return fraction(a.getNumer()*ilcd - b.getNumer()*ilcd, a.getDenom()*ilcd);
80   }
81 }
82 */
83
84 const fraction operator*(const fraction &a, int64_t b) {
85   if(b < a.getInterimMultOverflowPt()) {
86     //   b < interimMultOverflowPt
87     return fraction(b * a.getNumer(), a.getDenom());
88   } else if(b <= a.getFinalMultOverflowPt()) {
89     //   interimMultOverflowPt <= b <= finalMultInterimPt
90     cerr << "fraction::operator*- an interim overflow has occurred\n";
91     return fraction(I64_MAX);
92   } else {  //  finalMultInterimPt < b
93     cerr << "fraction::operator*- a final overflow has occurred\n";
94     return fraction(I64_MAX);
95   }
96 }
97
98 int64_t fraction::multReturnInt64(int64_t b) const {
99   int64_t ret = 0;
100   if(b < getInterimMultOverflowPt()) {
101     //   b < interimMultOverflowPt
102     fraction fres(b * getNumer(), getDenom());
103     ret = fres.getI();
104   } else if(b <= getFinalMultOverflowPt()) {
105     //   interimMultOverflowPt <= b <= finalMultInterimPt
106     ret = multNoInterimOverflow(b);
107   } else {  //  finalMultInterimPt < b
108     cerr << "fraction::multReturnInt64- a final overflow has occurred\n";    
109     return I64_MAX;
110   }
111   return ret;
112 }
113
114 void fraction::calcOverflowPts() const {
115   if(getNumer() == 0) 
116     interimMultOverflowPt = I64_MAX;
117   else 
118     interimMultOverflowPt = I64_MAX / getNumer();
119   fraction recip;
120   recip.setRaw(getDenom(), getNumer());
121   if(recip.getDenom()==0 || recip.getD() > 1.0) 
122     finalMultOverflowPt = I64_MAX;
123   else
124     finalMultOverflowPt = recip.multNoInterimOverflow(I64_MAX);
125 }
126
127 // getFrSpec is a helper routine for the gt, lt operators
128 // n : numerator,   d: denominator
129 // ra: returns the numerator high 32 bits / denom (always positive)
130 // rb: returns the numerator low  32 bits / denom (always positive)
131 // rsign: -1 for negative, 1 for positive result
132 void getFrSpec(int64_t n, int64_t d, double *ra, double *rb, int *rsign) {
133   int sign = 1;
134   if(n < 0) { n = -n;  sign = -sign; }
135   if(d < 0) { d = -d;  sign = -sign; }
136   *rsign = sign;
137   int64_t upperI = n & I64_C(0xFFFFFFFF00000000);
138   *ra = static_cast<double>(upperI) / static_cast<double>(d);
139   int64_t lowerI = n & 0xFFFFFFFF;
140   *rb = static_cast<double>(lowerI) / static_cast<double>(d);
141 }
142
143 // the gcd of the denominators could easily grow beyond the int64 max
144 // so implement using doubles
145 bool operator>(const fraction &a, const fraction &b) {
146   double ax, ay;
147   int as;
148   getFrSpec(a.getNumer(), a.getDenom(), &ax, &ay, &as);
149   if(as == -1) { ax =- ax; ay =-ay; }
150
151   double bx, by;
152   int bs;
153   getFrSpec(b.getNumer(), b.getDenom(), &bx, &by, &bs);
154   if(bs == -1) { bx =- bx; by =-by; }
155   return (ax > bx || (ax == bx && ay > by));
156 }
157
158 bool operator<(const fraction &a, const fraction &b) {
159   double ax, ay;
160   int as;
161   getFrSpec(a.getNumer(), a.getDenom(), &ax, &ay, &as);
162   if(as == -1) { ax =- ax; ay =-ay; }
163
164   double bx, by;
165   int bs;
166   getFrSpec(b.getNumer(), b.getDenom(), &bx, &by, &bs);
167   if(bs == -1) { bx =- bx; by =-by; }
168   return (ax < bx || (ax == bx && ay < by));
169 }
170
171 bool operator>=(const fraction &a, const fraction &b) {
172   return ((a > b) || (a == b));
173 }
174
175 bool operator<=(const fraction &a, const fraction &b) {
176   return ((a < b) || (a == b));
177 }
178
179 ostream& operator<<(ostream&s, const fraction::ostream_fmt u) {
180   fraction::curFmt = u;
181   return s;
182 }
183
184 ostream& operator<<(ostream&s, const fraction &z) {
185   if(fraction::curFmt == fraction::sparse) {
186     s << "(" << z.getNumer() << "/" << z.getDenom() << ")";
187   } else { // fraction::verbose
188     s << "(" << z.getNumer() << "/" << z.getDenom() << " - interimOvflw:";
189     s << z.getInterimMultOverflowPt() << ", finalOvflw: " 
190       << z.getFinalMultOverflowPt();
191   }
192   return s;
193 }
194
195