1 /* Copyright (c) MediaArea.net SARL. All Rights Reserved.
2 *
3 * Use of this source code is governed by a zlib-style license that can
4 * be found in the License.txt file in the root of the source tree.
5 */
6
7 //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
8 //
9 // based on http://Tringi.Mx-3.cz
10 // Only adapted for ZenLib:
11 // - uint128.hpp --> int128u.h
12 // - Namespace
13 // - int128u alias
14 //
15 //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
16
17 //---------------------------------------------------------------------------
18 #include "ZenLib/PreComp.h"
19 #ifdef __BORLANDC__
20 #pragma hdrstop
21 #endif
22 //---------------------------------------------------------------------------
23
24 //---------------------------------------------------------------------------
25 #include "ZenLib/Conf_Internal.h"
26 //---------------------------------------------------------------------------
27
28 #include "int128s.h"
29
30 /*
31 Name: int128.cpp
32 Copyright: Copyright (C) 2005, Jan Ringos
33 Author: Jan Ringos, http://Tringi.Mx-3.cz
34
35 Version: 1.1
36 */
37
38 #include <cmath>
39 #if defined (__BORLANDC__) || defined (__SUNPRO_CC)
40 #define fmodf fmod
41 #endif
42 #if defined (__NO_LONG_DOUBLE_MATH) || \
43 defined (__MONTAVISTA__) || defined (__ARMEL__) || \
44 defined (__FreeBSD__) || defined (__OpenBSD__) || \
45 defined (__NetBSD__) || defined (__DragonFly__) || \
46 defined (__sparc__) || defined (__sparc64__) || \
47 defined (__CYGWIN__) || \
48 defined (__SUNPRO_CC)
49 #define fmodl fmod
50 #endif
51 using namespace std;
52
53 namespace ZenLib
54 {
55
56 // IMPLEMENTATION
57
toString(unsigned int radix) const58 const char * int128::toString (unsigned int radix) const throw () {
59 if (!*this) return "0";
60 if (radix < 2 || radix > 37) return "(invalid radix)";
61
62 static char sz [256];
63 memset (sz, 0, 256);
64
65 int128 r;
66 int128 ii = (*this < 0) ? -*this : *this;
67 int i = 255;
68
69 while (!!ii && i) {
70 ii = ii.div (radix, r);
71 sz [--i] = (char) (r.toInt () + ((r.toInt () > 9) ? 'A' - 10 : '0'));
72 };
73
74 if (*this < 0)
75 sz [--i] = '-';
76
77 return &sz [i];
78 }
79
int128(const char * sz)80 int128::int128 (const char * sz) throw ()
81 : lo (0u), hi (0) {
82
83 if (!sz) return;
84 if (!sz [0]) return;
85
86 unsigned int radix = 10;
87 unsigned int i = 0;
88 bool minus = false;
89
90 if (sz [i] == '-') {
91 ++i;
92 minus = true;
93 };
94
95 if (sz [i] == '0') {
96 radix = 8;
97 ++i;
98 if (sz [i] == 'x') {
99 radix = 16;
100 ++i;
101 };
102 };
103 const size_t len = strlen(sz);
104 for (; i < len; ++i) {
105 unsigned int n = 0;
106 if (sz [i] >= '0' && sz [i] <= (('0' + (int) radix) < '9'?('0' + (int) radix):'9')) //if (sz [i] >= '0' && sz [i] <= (('0' + (int) radix) <? '9'))
107 n = sz [i] - '0';
108 else if (sz [i] >= 'a' && sz [i] <= 'a' + (int) radix - 10)
109 n = sz [i] - 'a' + 10;
110 else if (sz [i] >= 'A' && sz [i] <= 'A' + (int) radix - 10)
111 n = sz [i] - 'A' + 10;
112 else
113 break;
114
115 (*this) *= radix;
116 (*this) += n;
117 };
118
119 if (minus)
120 *this = 0 - *this;
121
122 return;
123 }
124
int128(const float a)125 int128::int128 (const float a) throw ()
126 #if defined (__mips__) || defined (__mipsel__)
127 : lo ((int64u) fmodf ((const double)a, 18446744073709551616.0)),
128 #else
129 : lo ((int64u) fmodf (a, 18446744073709551616.0f)),
130 #endif
131 hi ((int64s) (a / 18446744073709551616.0f)) {}
132
int128(const double & a)133 int128::int128 (const double & a) throw ()
134 : lo ((int64u) fmod (a, 18446744073709551616.0)),
135 hi ((int64s) (a / 18446744073709551616.0)) {}
136
int128(const long double & a)137 int128::int128 (const long double & a) throw ()
138 #if defined (__mips__) || defined (__mipsel__)
139 : lo ((int64u) fmod ((const double)a, 18446744073709551616.0)),
140 #else
141 : lo ((int64u) fmodl (a, 18446744073709551616.0l)),
142 #endif
143 hi ((int64s) (a / 18446744073709551616.0l)) {}
144
toFloat() const145 float int128::toFloat () const throw () {
146 return (float) this->hi * 18446744073709551616.0f
147 + (float) this->lo;
148 }
149
toDouble() const150 double int128::toDouble () const throw () {
151 return (double) this->hi * 18446744073709551616.0
152 + (double) this->lo;
153 }
154
toLongDouble() const155 long double int128::toLongDouble () const throw () {
156 return (long double) this->hi * 18446744073709551616.0l
157 + (long double) this->lo;
158 }
159
operator -() const160 int128 int128::operator - () const throw () {
161 if (!this->hi && !this->lo)
162 // number is 0, just return 0
163 return *this;
164 else
165 // non 0 number
166 return int128 (0-this->lo, ~this->hi);
167 }
168
operator ~() const169 int128 int128::operator ~ () const throw () {
170 return int128 (~this->lo, ~this->hi);
171 }
172
operator ++()173 int128 & int128::operator ++ () {
174 ++this->lo;
175 if (!this->lo)
176 ++this->hi;
177
178 return *this;
179 }
180
operator --()181 int128 & int128::operator -- () {
182 if (!this->lo)
183 --this->hi;
184 --this->lo;
185
186 return *this;
187 }
188
operator ++(int)189 int128 int128::operator ++ (int) {
190 int128 b = *this;
191 ++ *this;
192
193 return b;
194 }
195
operator --(int)196 int128 int128::operator -- (int) {
197 int128 b = *this;
198 -- *this;
199
200 return b;
201 }
202
operator +=(const int128 & b)203 int128 & int128::operator += (const int128 & b) throw () {
204 int64u old_lo = this->lo;
205
206 this->lo += b.lo;
207 this->hi += b.hi + (this->lo < old_lo);
208
209 return *this;
210 }
211
operator *=(const int128 & b)212 int128 & int128::operator *= (const int128 & b) throw () {
213 if (!b)
214 return *this = 0u;
215 if (b == 1u)
216 return *this;
217
218 int128 a = *this;
219 int128 t = b;
220
221 this->lo = 0ull;
222 this->hi = 0ll;
223
224 for (unsigned int i = 0; i < 128; ++i) {
225 if (t.lo & 1)
226 *this += a << i;
227
228 t >>= 1;
229 };
230
231 return *this;
232 }
233
234
div(const int128 & divisor,int128 & remainder) const235 int128 int128::div (const int128 & divisor, int128 & remainder) const throw () {
236 if (!divisor)
237 return 1u / (unsigned int) divisor.lo;
238 // or RaiseException (EXCEPTION_INT_DIVIDE_BY_ZERO,
239 // EXCEPTION_NONCONTINUABLE, 0, NULL);
240
241 int128 ds = (divisor < 0) ? -divisor : divisor;
242 int128 dd = (*this < 0) ? -*this : *this;
243
244 // only remainder
245 if (ds > dd) {
246 remainder = *this;
247 return 0ull;
248 };
249
250 int128 r = 0ull;
251 int128 q = 0ull;
252 // while (dd >= ds) { dd -= ds; q += 1; }; // extreme slow version
253
254 unsigned int b = 127;
255 while (r < ds) {
256 r <<= 1;
257 if (dd.bit (b--))
258 r.lo |= 1;
259 };
260 ++b;
261
262 for (;;)
263 if (r < ds) {
264 if (!(b--)) break;
265
266 r <<= 1;
267 if (dd.bit (b))
268 r.lo |= 1;
269
270 } else {
271 r -= ds;
272 q.bit (b, true);
273 };
274
275 // correct
276 if ((divisor < 0) ^ (*this < 0)) q =- q;
277 if (*this < 0) r =- r;
278
279 remainder = r;
280 return q;
281 }
282
bit(unsigned int n) const283 bool int128::bit (unsigned int n) const throw () {
284 n &= 0x7F;
285
286 if (n < 64)
287 return (this->lo & (1ull << n))?true:false;
288 else
289 return (this->hi & (1ull << (n - 64)))?true:false;
290 }
291
bit(unsigned int n,bool val)292 void int128::bit (unsigned int n, bool val) throw () {
293 n &= 0x7F;
294
295 if (val) {
296 if (n < 64) this->lo |= (1ull << n);
297 else this->hi |= (1ull << (n - 64));
298 } else {
299 if (n < 64) this->lo &= ~(1ull << n);
300 else this->hi &= ~(1ull << (n - 64));
301 };
302 }
303
304
operator >>=(unsigned int n)305 int128 & int128::operator >>= (unsigned int n) throw () {
306 n &= 0x7F;
307
308 if (n > 63) {
309 n -= 64;
310 this->lo = this->hi;
311
312 if (this->hi < 0) this->hi = -1ll;
313 else this->hi = 0ll;
314 };
315
316 if (n) {
317 // shift low qword
318 this->lo >>= n;
319
320 // get lower N bits of high qword
321 int64u mask = 0ull;
322 for (unsigned int i = 0; i < n; ++i) mask |= (1ull << i);
323
324 // and add them to low qword
325 this->lo |= (this->hi & mask) << (64 - n);
326
327 // and finally shift also high qword
328 this->hi >>= n;
329 };
330
331 return *this;
332 }
333
operator <<=(unsigned int n)334 int128 & int128::operator <<= (unsigned int n) throw () {
335 n &= 0x7F;
336
337 if (n > 63) {
338 n -= 64;
339 this->hi = this->lo;
340 this->lo = 0ull;
341 };
342
343 if (n) {
344 // shift high qword
345 this->hi <<= n;
346
347 // get higher N bits of low qword
348 int64u mask = 0ull;
349 for (unsigned int i = 0; i < n; ++i) mask |= (1ull << (63 - i));
350
351 // and add them to high qword
352 this->hi |= (this->lo & mask) >> (64 - n);
353
354 // and finally shift also low qword
355 this->lo <<= n;
356 };
357
358 return *this;
359 }
360
operator !() const361 bool int128::operator ! () const throw () {
362 return !(this->hi || this->lo);
363 }
364
operator |=(const int128 & b)365 int128 & int128::operator |= (const int128 & b) throw () {
366 this->hi |= b.hi;
367 this->lo |= b.lo;
368
369 return *this;
370 }
371
operator &=(const int128 & b)372 int128 & int128::operator &= (const int128 & b) throw () {
373 this->hi &= b.hi;
374 this->lo &= b.lo;
375
376 return *this;
377 }
378
operator ^=(const int128 & b)379 int128 & int128::operator ^= (const int128 & b) throw () {
380 this->hi ^= b.hi;
381 this->lo ^= b.lo;
382
383 return *this;
384 }
385
operator <(const int128 & a,const int128 & b)386 bool operator < (const int128 & a, const int128 & b) throw () {
387 if (a.hi == b.hi) {
388 if (a.hi < 0)
389 return (int64s) a.lo < (int64s) b.lo;
390 else
391 return a.lo < b.lo;
392 } else
393 return a.hi < b.hi;
394 }
395
operator ==(const int128 & a,const int128 & b)396 bool operator == (const int128 & a, const int128 & b) throw () {
397 return a.hi == b.hi && a.lo == b.lo;
398 }
operator &&(const int128 & a,const int128 & b)399 bool operator && (const int128 & a, const int128 & b) throw () {
400 return (a.hi || a.lo) && (b.hi || b.lo);
401 }
operator ||(const int128 & a,const int128 & b)402 bool operator || (const int128 & a, const int128 & b) throw () {
403 return (a.hi || a.lo) || (b.hi || b.lo);
404 }
405
406 } //NameSpace
407