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