00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include "compiler.hh"
00024 #include "globals.types.hh"
00025 #include <cassert>
00026
00027 namespace Parma_Polyhedra_Library {
00028
00029 namespace Checked {
00030
00031 template <typename Policy, typename Type>
00032 struct FUNCTION_CLASS(construct)<Policy, Type, Type> {
00033 static inline Result function(Type& to, const Type& from, Rounding_Dir) {
00034 new (&to) Type(from);
00035 return V_EQ;
00036 }
00037 };
00038
00039 template <typename Policy, typename To, typename From>
00040 struct FUNCTION_CLASS(construct) {
00041 static inline Result function(To& to, const From& from, Rounding_Dir dir) {
00042 new (&to) To();
00043 return assign<Policy>(to, from, dir);
00044 }
00045 };
00046
00047 template <typename Policy, typename Type>
00048 struct FUNCTION_CLASS(assign)<Policy, Type, Type> {
00049 static inline Result function(Type& to, const Type& from, Rounding_Dir) {
00050 to = from;
00051 return V_EQ;
00052 }
00053 };
00054
00055 template <typename Policy, typename Type>
00056 inline void
00057 copy_generic(Type& to, const Type& from) {
00058 to = from;
00059 }
00060
00061 template <typename Policy, typename To, typename From>
00062 inline Result
00063 abs_generic(To& to, const From& from, Rounding_Dir dir) {
00064 if (from < 0)
00065 return neg<Policy>(to, from, dir);
00066 to = from;
00067 return V_EQ;
00068 }
00069
00070 inline Result
00071 neg(Result r) {
00072 assert(!is_special(r));
00073 Result ret = static_cast<Result>(r & V_EQ);
00074 if (r & V_LT)
00075 ret = static_cast<Result>(ret | V_GT);
00076 if (r & V_GT)
00077 ret = static_cast<Result>(ret | V_LT);
00078 return ret;
00079 }
00080
00081 inline Result
00082 add(Result r1, Result r2) {
00083 assert(!is_special(r1));
00084 assert(!is_special(r2));
00085 if (r1 == V_EQ)
00086 return r2;
00087 if (r2 == V_EQ)
00088 return r1;
00089 if (((r1 & V_LT) && (r2 & V_GT))
00090 || ((r1 & V_GT) && (r2 & V_LT)))
00091 return V_LGE;
00092 return static_cast<Result>((((r1 & r2) & V_EQ) ? V_EQ : 0) |
00093 (r1 & (V_LT | V_GT)));
00094 }
00095
00096 inline Result
00097 sub(Result r1, Result r2) {
00098 return add(r1, neg(r2));
00099 }
00100
00101 template <typename Policy, typename To, typename From>
00102 inline void
00103 gcd_exact_noabs(To& to, const From& x, const From& y) {
00104 To nx = x;
00105 To ny = y;
00106 To rm;
00107 while (ny != 0) {
00108
00109
00110
00111 rem<Policy>(rm, nx, ny, ROUND_NOT_NEEDED);
00112 nx = ny;
00113 ny = rm;
00114 }
00115 to = nx;
00116 }
00117
00118 template <typename Policy, typename To, typename From1, typename From2>
00119 inline Result
00120 gcd_exact(To& to, const From1& x, const From2& y, Rounding_Dir dir) {
00121 gcd_exact_noabs<Policy>(to, x, y);
00122 return abs<Policy>(to, to, dir);
00123 }
00124
00125 template <typename Policy, typename To1,
00126 typename From1, typename From2, typename To2, typename To3>
00127 inline Result
00128 gcdext_exact(To1& to, const From1& x, const From2& y, To2& s, To3& t,
00129 Rounding_Dir dir) {
00130 if (y == 0) {
00131 if (x == 0) {
00132 s = 0;
00133 t = 1;
00134 return V_EQ;
00135 }
00136 else {
00137 if (x < 0)
00138 s = -1;
00139 else
00140 s = 1;
00141 t = 0;
00142 return abs<Policy>(to, x, dir);
00143 }
00144 }
00145
00146 s = 1;
00147 t = 0;
00148 bool negative_x = x < 0;
00149 bool negative_y = y < 0;
00150
00151 Result r;
00152 r = abs<Policy>(to, x, dir);
00153 if (r != V_EQ)
00154 return r;
00155
00156 From2 ay;
00157 r = abs<Policy>(ay, y, dir);
00158 if (r != V_EQ)
00159 return r;
00160
00161
00162
00163
00164
00165 #define COPY_GMP
00166 #ifdef COPY_GMP
00167 if (to == ay)
00168 goto sign_check;
00169 #endif
00170
00171 {
00172 To2 v1 = 0;
00173 To3 v2 = 1;
00174 To1 v3 = static_cast<To1>(ay);
00175 while (true) {
00176 To1 q = to / v3;
00177
00178 To1 t3 = to - q*v3;
00179 To2 t1 = s - static_cast<To2>(q)*v1;
00180 To3 t2 = t - static_cast<To3>(q)*v2;
00181 s = v1;
00182 t = v2;
00183 to = v3;
00184 if (t3 == 0)
00185 break;
00186 v1 = t1;
00187 v2 = t2;
00188 v3 = t3;
00189 }
00190 }
00191
00192 #ifdef COPY_GMP
00193 sign_check:
00194 #endif
00195 if (negative_x) {
00196 r = neg<Policy>(s, s, dir);
00197 if (r != V_EQ)
00198 return r;
00199 }
00200 if (negative_y)
00201 return neg<Policy>(t, t, dir);
00202 return V_EQ;
00203 }
00204
00205 template <typename Policy, typename To, typename From1, typename From2>
00206 inline Result
00207 lcm_gcd_exact(To& to, const From1& x, const From2& y, Rounding_Dir dir) {
00208 if (x == 0 || y == 0) {
00209 to = 0;
00210 return V_EQ;
00211 }
00212 To nx, ny;
00213 Result r;
00214 r = abs<Policy>(nx, x, dir);
00215 if (r != V_EQ)
00216 return r;
00217 r = abs<Policy>(ny, y, dir);
00218 if (r != V_EQ)
00219 return r;
00220 To gcd;
00221 gcd_exact_noabs<Policy>(gcd, nx, ny);
00222
00223
00224
00225 div<Policy>(to, nx, gcd, ROUND_NOT_NEEDED);
00226 return mul<Policy>(to, to, ny, dir);
00227 }
00228
00229 template <typename Policy, typename Type>
00230 inline Result
00231 sgn_generic(const Type& x) {
00232 if (x > 0)
00233 return V_GT;
00234 if (x == 0)
00235 return V_EQ;
00236 return V_LT;
00237 }
00238
00239 template <typename Policy, typename Type>
00240 inline Result
00241 cmp_generic(const Type& x, const Type& y) {
00242 if (x > y)
00243 return V_GT;
00244 if (x < y)
00245 return V_LT;
00246 return V_EQ;
00247 }
00248
00249 template <typename Policy, typename Type>
00250 inline Result
00251 input_generic(Type& to, std::istream& is, Rounding_Dir dir) {
00252 mpq_class q;
00253 Result r = input_mpq(q, is);
00254 if (r == VC_MINUS_INFINITY)
00255 return assign<Policy>(to, MINUS_INFINITY, dir);
00256 if (r == VC_PLUS_INFINITY)
00257 return assign<Policy>(to, PLUS_INFINITY, dir);
00258 if (r == V_EQ)
00259 return assign<Policy>(to, q, dir);
00260 return set_special<Policy>(to, r);
00261 }
00262
00263 template <typename T>
00264 inline memory_size_type
00265 external_memory_in_bytes(T) {
00266 return 0;
00267 }
00268
00269 template <typename T>
00270 inline memory_size_type
00271 total_memory_in_bytes(T& x) {
00272 return sizeof(x) + external_memory_in_bytes(x);
00273 }
00274
00275 }
00276
00277 }