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