src/common/longlong.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        wx/longlong.cpp
   3 // Purpose:     implementation of wxLongLongNative
   4 // Author:      Jeffrey C. Ollie <jeff@ollie.clive.ia.us>, Vadim Zeitlin
   5 // Remarks:     this class is not public in wxWindows 2.0! It is intentionally
   6 //              not documented and is for private use only.
   7 // Modified by:
   8 // Created:     10.02.99
   9 // RCS-ID:      $Id$
  10 // Copyright:   (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
  11 // Licence:     wxWindows license
  12 /////////////////////////////////////////////////////////////////////////////
  13
  14 // ============================================================================
  15 // headers
  16 // ============================================================================
  17
  18 #ifdef __GNUG__
  19     #pragma implementation "longlong.h"
  20 #endif
  21
  22 #include "wx/wxprec.h"
  23
  24 #ifdef __BORLANDC__
  25     #pragma hdrstop
  26 #endif
  27
  28 #if wxUSE_LONGLONG
  29
  30 #include "wx/longlong.h"
  31
  32 #include <memory.h>     // for memset()
  33 #include <math.h>       // for fabs()
  34
  35 // ============================================================================
  36 // implementation
  37 // ============================================================================
  38
  39 #if wxUSE_LONGLONG_NATIVE
  40
  41 // ----------------------------------------------------------------------------
  42 // misc
  43 // ----------------------------------------------------------------------------
  44
  45 void *wxLongLongNative::asArray(void) const
  46 {
  47     static unsigned char temp[8];
  48
  49     temp[0] = (m_ll >> 56) & 0xFF;
  50     temp[1] = (m_ll >> 48) & 0xFF;
  51     temp[2] = (m_ll >> 40) & 0xFF;
  52     temp[3] = (m_ll >> 32) & 0xFF;
  53     temp[4] = (m_ll >> 24) & 0xFF;
  54     temp[5] = (m_ll >> 16) & 0xFF;
  55     temp[6] = (m_ll >> 8)  & 0xFF;
  56     temp[7] = (m_ll >> 0)  & 0xFF;
  57
  58     return temp;
  59 }
  60
  61 #if wxUSE_STD_IOSTREAM
  62
  63 // input/output
  64 ostream& operator<< (ostream& o, const wxLongLongNative& ll)
  65 {
  66     char result[65];
  67
  68     memset(result, 'A', 64);
  69
  70     result[64] = '\0';
  71
  72     for (int i = 0; i < 64; i++)
  73     {
  74         result[63 - i] = '0' + (char) ((ll.m_ll >> i) & 1);
  75     }
  76
  77     return o << result;
  78 }
  79
  80 #endif // wxUSE_STD_IOSTREAM
  81
  82 #endif // wxUSE_LONGLONG_NATIVE
  83
  84 // ============================================================================
  85 // wxLongLongWx: emulation of 'long long' using 2 longs
  86 // ============================================================================
  87
  88 #if wxUSE_LONGLONG_WX
  89
  90 // assignment
  91 wxLongLongWx& wxLongLongWx::Assign(double d)
  92 {
  93     if ( fabs(d) <= LONG_MAX )
  94     {
  95         m_hi = d < 0 ? 1 << (8*sizeof(long) - 1) : 0l;
  96         m_lo = (long)d;
  97     }
  98     else
  99     {
 100         wxFAIL_MSG(_T("TODO"));
 101     }
 102
 103     return *this;
 104 }
 105
 106 wxLongLongWx wxLongLongWx::operator<<(int shift) const
 107 {
 108     if (shift == 0)
 109         return *this;
 110
 111     if (shift < 32)
 112         return wxLongLongWx((m_hi << shift) | (m_lo >> (32 - shift)),
 113                              m_lo << shift);
 114     else
 115         return wxLongLongWx(m_lo << (shift - 32),
 116                             0);
 117 }
 118
 119 wxLongLongWx& wxLongLongWx::operator<<=(int shift)
 120 {
 121     if (shift == 0)
 122         return *this;
 123
 124     if (shift < 32)
 125     {
 126         m_hi <<= shift;
 127         m_hi |= m_lo >> (32 - shift);
 128         m_lo <<= shift;
 129     }
 130     else
 131     {
 132         m_hi = m_lo << (shift - 32);
 133         m_lo = 0;
 134     }
 135
 136     return *this;
 137 }
 138
 139 wxLongLongWx wxLongLongWx::operator>>(int shift) const
 140 {
 141     if (shift == 0)
 142         return *this;
 143
 144     if (shift < 32)
 145         return wxLongLongWx(m_hi >> shift,
 146                           (m_lo >> shift) | (m_hi << (32 - shift)));
 147     else
 148         return wxLongLongWx((m_hi < 0 ? -1l : 0),
 149                           m_hi >> (shift - 32));
 150 }
 151
 152 wxLongLongWx& wxLongLongWx::operator>>=(int shift)
 153 {
 154     if (shift == 0)
 155         return *this;
 156
 157     if (shift < 32)
 158     {
 159         m_lo >>= shift;
 160         m_lo |= m_hi << (32 - shift);
 161         m_hi >>= shift;
 162     }
 163     else
 164     {
 165         m_lo = m_hi >> (shift - 32);
 166         m_hi = (m_hi < 0 ? -1L : 0);
 167     }
 168
 169     return *this;
 170 }
 171
 172 wxLongLongWx wxLongLongWx::operator+(const wxLongLongWx& ll) const
 173 {
 174     wxLongLongWx temp;
 175
 176     temp.m_lo = m_lo + ll.m_lo;
 177     temp.m_hi = m_hi + ll.m_hi;
 178     if ((temp.m_lo < m_lo) || (temp.m_lo < ll.m_lo))
 179         temp.m_hi++;
 180
 181     return temp;
 182 }
 183
 184 wxLongLongWx wxLongLongWx::operator+(long l) const
 185 {
 186     wxLongLongWx temp;
 187
 188     temp.m_lo = m_lo + l;
 189
 190     if (l < 0)
 191         temp.m_hi += -1l;
 192
 193     if ((temp.m_lo < m_lo) || (temp.m_lo < (unsigned long)l))
 194         temp.m_hi++;
 195
 196     return temp;
 197 }
 198
 199 wxLongLongWx& wxLongLongWx::operator+=(const wxLongLongWx& ll)
 200 {
 201     unsigned long previous = m_lo;
 202
 203     m_lo += ll.m_lo;
 204     m_hi += ll.m_hi;
 205
 206     if ((m_lo < previous) || (m_lo < ll.m_lo))
 207         m_hi++;
 208
 209     return *this;
 210 }
 211
 212 wxLongLongWx& wxLongLongWx::operator+=(long l)
 213 {
 214     unsigned long previous = m_lo;
 215
 216     m_lo += l;
 217     if (l < 0)
 218         m_hi += -1l;
 219
 220     if ((m_lo < previous) || (m_lo < (unsigned long)l))
 221         m_hi++;
 222
 223     return *this;
 224 }
 225
 226 // pre increment
 227 wxLongLongWx& wxLongLongWx::operator++()
 228 {
 229     m_lo++;
 230     if (m_lo == 0)
 231         m_hi++;
 232
 233     return *this;
 234 }
 235
 236 // post increment
 237 wxLongLongWx& wxLongLongWx::operator++(int)
 238 {
 239     m_lo++;
 240     if (m_lo == 0)
 241         m_hi++;
 242
 243     return *this;
 244 }
 245
 246 // negation
 247 wxLongLongWx wxLongLongWx::operator-() const
 248 {
 249     wxLongLongWx temp(~m_hi, ~m_lo);
 250
 251     temp.m_lo++;
 252     if (temp.m_lo == 0)
 253         temp.m_hi++;
 254
 255     return temp;
 256 }
 257
 258 // subtraction
 259
 260 wxLongLongWx wxLongLongWx::operator-(const wxLongLongWx& ll) const
 261 {
 262     wxLongLongWx temp;
 263
 264     temp.m_lo = m_lo - ll.m_lo;
 265     temp.m_hi = m_hi - ll.m_hi;
 266
 267     if (m_lo < ll.m_lo)
 268         temp.m_hi--;
 269
 270     return temp;
 271 }
 272
 273 wxLongLongWx& wxLongLongWx::operator-=(const wxLongLongWx& ll)
 274 {
 275     unsigned long previous = m_lo;
 276
 277     m_lo -= ll.m_lo;
 278     m_hi -= ll.m_hi;
 279
 280     if (previous < ll.m_lo)
 281         m_hi--;
 282
 283     return *this;;
 284 }
 285
 286 // pre decrement
 287 wxLongLongWx& wxLongLongWx::operator--()
 288 {
 289     m_lo--;
 290     if (m_lo == 0xFFFFFFFF)
 291         m_hi--;
 292
 293     return *this;
 294 }
 295
 296 // post decrement
 297 wxLongLongWx& wxLongLongWx::operator--(int)
 298 {
 299     m_lo--;
 300     if (m_lo == 0xFFFFFFFF)
 301         m_hi--;
 302
 303     return *this;
 304 }
 305
 306 // comparison operators
 307
 308 bool wxLongLongWx::operator<(const wxLongLongWx& ll) const
 309 {
 310     if ( m_hi < ll.m_hi )
 311         return TRUE;
 312     else if ( m_hi == ll.m_hi )
 313         return m_lo < ll.m_lo;
 314     else
 315         return FALSE;
 316 }
 317
 318 bool wxLongLongWx::operator>(const wxLongLongWx& ll) const
 319 {
 320     if ( m_hi > ll.m_hi )
 321         return TRUE;
 322     else if ( m_hi == ll.m_hi )
 323         return m_lo > ll.m_lo;
 324     else
 325         return FALSE;
 326 }
 327
 328 // bitwise operators
 329
 330 wxLongLongWx wxLongLongWx::operator&(const wxLongLongWx& ll) const
 331 {
 332     return wxLongLongWx(m_hi & ll.m_hi, m_lo & ll.m_lo);
 333 }
 334
 335 wxLongLongWx wxLongLongWx::operator|(const wxLongLongWx& ll) const
 336 {
 337     return wxLongLongWx(m_hi | ll.m_hi, m_lo | ll.m_lo);
 338 }
 339
 340 wxLongLongWx wxLongLongWx::operator^(const wxLongLongWx& ll) const
 341 {
 342     return wxLongLongWx(m_hi ^ ll.m_hi, m_lo ^ ll.m_lo);
 343 }
 344
 345 wxLongLongWx& wxLongLongWx::operator&=(const wxLongLongWx& ll)
 346 {
 347     m_lo &= ll.m_lo;
 348     m_hi &= ll.m_hi;
 349
 350     return *this;
 351 }
 352
 353 wxLongLongWx& wxLongLongWx::operator|=(const wxLongLongWx& ll)
 354 {
 355     m_lo |= ll.m_lo;
 356     m_hi |= ll.m_hi;
 357
 358     return *this;
 359 }
 360
 361 wxLongLongWx& wxLongLongWx::operator^=(const wxLongLongWx& ll)
 362 {
 363     m_lo ^= ll.m_lo;
 364     m_hi ^= ll.m_hi;
 365
 366     return *this;
 367 }
 368
 369 wxLongLongWx wxLongLongWx::operator~() const
 370 {
 371     return wxLongLongWx(~m_hi, ~m_lo);
 372 }
 373
 374 // multiplication
 375
 376 wxLongLongWx wxLongLongWx::operator*(const wxLongLongWx& ll) const
 377 {
 378     wxLongLongWx t(m_hi, m_lo);
 379     wxLongLongWx q(ll.m_hi, ll.m_lo);
 380     wxLongLongWx p;
 381     int counter = 0;
 382
 383     do
 384     {
 385         if ((q.m_lo & 1) != 0)
 386               p += t;
 387         q >>= 1;
 388         t <<= 1;
 389         counter++;
 390       }
 391       while ((counter < 64) && ((q.m_hi != 0) || (q.m_lo != 0)));
 392     return p;
 393 }
 394
 395 wxLongLongWx& wxLongLongWx::operator*=(const wxLongLongWx& ll)
 396 {
 397     wxLongLongWx t(m_hi, m_lo);
 398     wxLongLongWx q(ll.m_hi, ll.m_lo);
 399     int counter = 0;
 400
 401     do
 402     {
 403         if ((q.m_lo & 1) != 0)
 404               *this += t;
 405         q >>= 1;
 406         t <<= 1;
 407         counter++;
 408       }
 409       while ((counter < 64) && ((q.m_hi != 0) || (q.m_lo != 0)));
 410     return *this;
 411 }
 412
 413 // division
 414
 415 void wxLongLongWx::Divide(const wxLongLongWx& divisorIn,
 416                           wxLongLongWx& quotient,
 417                           wxLongLongWx& remainder) const
 418 {
 419     if ((divisorIn.m_lo == 0) && (divisorIn.m_hi == 0))
 420     {
 421         // provoke division by zero error and silence the compilers warnings
 422         // about an expression without effect and unused variable
 423         long dummy = divisorIn.m_lo/divisorIn.m_hi;
 424         dummy += 0;
 425     }
 426
 427     // VZ: I'm writing this in a hurry and it's surely not the fastest way to
 428     //     do this - any improvements are more than welcome
 429     //
 430     //     code inspired by the snippet at
 431     //          http://www.bearcave.com/software/divide.htm
 432     //
 433     //     Copyright notice:
 434     //
 435     //     Use of this program, for any purpose, is granted the author, Ian
 436     //     Kaplan, as long as this copyright notice is included in the source
 437     //     code or any source code derived from this program. The user assumes
 438     //     all responsibility for using this code.
 439
 440     // init everything
 441     wxLongLongWx dividend = *this,
 442                  divisor = divisorIn;
 443
 444     quotient = 0l;
 445     remainder = 0l;
 446
 447     // check for some particular cases
 448     if ( divisor > dividend )
 449     {
 450         remainder = dividend;
 451
 452         return;
 453     }
 454
 455     if ( divisor == dividend )
 456     {
 457         quotient = 1l;
 458
 459         return;
 460     }
 461
 462     // always do unsigned division and adjust the signs later: in C integer
 463     // division, the sign of the remainder is the same as the sign of the
 464     // dividend, while the sign of the quotient is the product of the signs of
 465     // the dividend and divisor. Of course, we also always have
 466     //
 467     //      dividend = quotient*divisor + remainder
 468     //
 469     // with 0 <= abs(remainder) < abs(divisor)
 470     bool negRemainder = dividend.m_hi < 0;
 471     bool negQuotient = FALSE;   // assume positive
 472     if ( dividend.m_hi < 0 )
 473     {
 474         negQuotient = !negQuotient;
 475         dividend = -dividend;
 476     }
 477     if ( divisor.m_hi < 0 )
 478     {
 479         negQuotient = !negQuotient;
 480         divisor = -divisor;
 481     }
 482
 483     // here: dividend > divisor and both are positibe: do unsigned division
 484     size_t nBits = 64u;
 485     wxLongLongWx d;
 486
 487     #define IS_MSB_SET(ll)  ((ll.m_hi) & (1 << (8*sizeof(long) - 1)))
 488
 489     while ( remainder < divisor )
 490     {
 491         remainder <<= 1;
 492         if ( IS_MSB_SET(dividend) )
 493         {
 494             remainder |= 1;
 495         }
 496
 497         d = dividend;
 498         dividend <<= 1;
 499
 500         nBits--;
 501     }
 502
 503     // undo the last loop iteration
 504     dividend = d;
 505     remainder >>= 1;
 506     nBits++;
 507
 508     for ( size_t i = 0; i < nBits; i++ )
 509     {
 510         remainder <<= 1;
 511         if ( IS_MSB_SET(dividend) )
 512         {
 513             remainder |= 1;
 514         }
 515
 516         wxLongLongWx t = remainder - divisor;
 517         dividend <<= 1;
 518         quotient <<= 1;
 519         if ( !IS_MSB_SET(t) )
 520         {
 521             quotient |= 1;
 522
 523             remainder = t;
 524         }
 525     }
 526
 527     // adjust signs
 528     if ( negRemainder )
 529     {
 530         remainder = -remainder;
 531     }
 532
 533     if ( negQuotient )
 534     {
 535         quotient = -quotient;
 536     }
 537 }
 538
 539 wxLongLongWx wxLongLongWx::operator/(const wxLongLongWx& ll) const
 540 {
 541     wxLongLongWx quotient, remainder;
 542
 543     Divide(ll, quotient, remainder);
 544
 545     return quotient;
 546 }
 547
 548 wxLongLongWx& wxLongLongWx::operator/=(const wxLongLongWx& ll)
 549 {
 550     wxLongLongWx quotient, remainder;
 551
 552     Divide(ll, quotient, remainder);
 553
 554     return *this = quotient;
 555 }
 556
 557 wxLongLongWx wxLongLongWx::operator%(const wxLongLongWx& ll) const
 558 {
 559     wxLongLongWx quotient, remainder;
 560
 561     Divide(ll, quotient, remainder);
 562
 563     return remainder;
 564 }
 565
 566 // ----------------------------------------------------------------------------
 567 // misc
 568 // ----------------------------------------------------------------------------
 569
 570 // temporary - just for testing
 571 void *wxLongLongWx::asArray(void) const
 572 {
 573     static unsigned char temp[8];
 574
 575     temp[0] = (m_hi >> 24) & 0xFF;
 576     temp[1] = (m_hi >> 16) & 0xFF;
 577     temp[2] = (m_hi >> 8)  & 0xFF;
 578     temp[3] = (m_hi >> 0)  & 0xFF;
 579     temp[4] = (m_lo >> 24) & 0xFF;
 580     temp[5] = (m_lo >> 16) & 0xFF;
 581     temp[6] = (m_lo >> 8)  & 0xFF;
 582     temp[7] = (m_lo >> 0)  & 0xFF;
 583
 584     return temp;
 585 }
 586
 587 #if wxUSE_STD_IOSTREAM
 588
 589 // input/output
 590 ostream& operator<< (ostream& o, const wxLongLongWx& ll)
 591 {
 592     char result[65];
 593
 594     memset(result, 'A', 64);
 595
 596     result[64] = '\0';
 597
 598     for (int i = 0; i < 32; i++)
 599     {
 600         result[31 - i] = (char) ('0' + (int) ((ll.m_hi >> i) & 1));
 601         result[63 - i] = (char) ('0' + (int) ((ll.m_lo >> i) & 1));
 602     }
 603
 604     return o << result;
 605 }
 606 #endif // wxUSE_STD_IOSTREAM
 607
 608 #endif // wxUSE_LONGLONG_NATIVE
 609
 610 #endif // wxUSE_LONGLONG