// BigNum.cpp: implementation of the CBigNum class.////////////////////////////////////////////////////////////////////////#include <string.h>#include <stdio.h>#include <time.h>#include "bignum.h"const char CBigNum::szBase64[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";//////////////////////////////////////////////////////////////////////// Construction/Destruction//////////////////////////////////////////////////////////////////////CBigNum::CBigNum() : m_arVal(0), m_nSize(0){}CBigNum::CBigNum(unsigned int nValue) : m_arVal(0), m_nSize(0){   if (m_arVal != NULL)      delete[] m_arVal;   m_nSize=2;   m_arVal = new unsigned int[m_nSize];   m_arVal[0] = nValue & 0xFFFF;   m_arVal[1] = nValue >> 16;}CBigNum::~CBigNum(){   if (m_arVal != NULL)   {      delete[] m_arVal;      m_arVal = NULL;      m_nSize = 0;   }}CBigNum::CBigNum(const char *szSourceVal) : m_arVal(0), m_nSize(0){   *this=szSourceVal;}CBigNum & CBigNum::operator=(const char *szSourceVal){   unsigned int nLen = strlen(szSourceVal);   unsigned int nIdx;   const char *pChar;   CBigNum Pow10;   operator=(0U);   if (m_arVal != NULL)   {      Pow10 = 1;      for (pChar = szSourceVal + nLen - 1, nIdx=0; pChar >= szSourceVal; pChar--, nIdx++)      {         operator+=(Pow10 * (unsigned int)(*pChar - '0'));         Pow10*=10;      }   }   return *this;}CBigNum &CBigNum::operator+=(const CBigNum &rhs){   unsigned int nIdx;   if (rhs.m_nSize > m_nSize)      Resize(rhs.m_nSize);   for (nIdx = 0; nIdx < rhs.m_nSize; nIdx++)   {      m_arVal[nIdx] += rhs.m_arVal[nIdx];   }      HandleCarry();   return *this;}CBigNum &CBigNum::operator=(unsigned int intVal){   unsigned int nIdx;   for (nIdx = 0; nIdx < m_nSize; nIdx++)   {      m_arVal[nIdx] = 0;   }   if (m_nSize <= 0)      Resize(1);   m_arVal[0] = intVal;      HandleCarry();   return *this;}void CBigNum::HandleCarry(){   unsigned int nIdx;   for (nIdx=0; nIdx < m_nSize; nIdx++)   {      if ((m_arVal[nIdx] & 0xFFFF0000) != 0)      {         if (nIdx >= m_nSize - 1)         {            Resize(nIdx + 2);         }         m_arVal[nIdx+1] += (m_arVal[nIdx] >> 16);         m_arVal[nIdx] &= 0xFFFF;      }   }}void CBigNum::Resize(unsigned int nNewSize){   unsigned int *pNewVal;   unsigned int nIdx;   if (nNewSize > 0)      pNewVal = new unsigned int[nNewSize];   else      pNewVal = NULL;   if (nNewSize < m_nSize)      m_nSize = nNewSize;   for (nIdx=0; nIdx < m_nSize; nIdx++)   {      pNewVal[nIdx] = m_arVal[nIdx];   }   for (;nIdx<nNewSize; nIdx++)   {      pNewVal[nIdx] = 0;   }   if (m_arVal)      delete[] m_arVal;   m_arVal = pNewVal;   m_nSize = nNewSize;}CBigNum &CBigNum::operator>>=(unsigned int rhs){   unsigned int nIdx;   if (m_nSize)   {      while(rhs>=16)      {         for (nIdx=0; nIdx < m_nSize-1; nIdx++)         {            m_arVal[nIdx] = m_arVal[nIdx+1];         }         rhs-=16;         m_arVal[nIdx] = 0;      }   }   for (nIdx=0; nIdx < m_nSize-1; nIdx++)   {      m_arVal[nIdx] = (m_arVal[nIdx] >> rhs) | ((m_arVal[nIdx+1] << (16 - rhs)) & 0xFFFF);   }      if (nIdx < m_nSize)      m_arVal[nIdx] >>= rhs;   return *this;}CBigNum &CBigNum::operator<<=(unsigned int rhs){   unsigned int nIdx;   if (m_nSize)   {      while(rhs>=16)      {         if (m_arVal[m_nSize-1])            Resize(m_nSize+1);         for (nIdx = m_nSize-1; nIdx > 0; nIdx--)         {            m_arVal[nIdx] = m_arVal[nIdx-1];         }         rhs -=16;         m_arVal[0] = 0;      }      if ((m_arVal[m_nSize - 1] << rhs) & 0xFFFF0000)         Resize(m_nSize + 1);   }   if (m_nSize)   {      for (nIdx = m_nSize-1; nIdx > 0; nIdx--)      {         m_arVal[nIdx] = (m_arVal[nIdx] << rhs) | (m_arVal[nIdx-1] >> (16-rhs));         m_arVal[nIdx] &= 0xFFFF;      }      m_arVal[0] <<= rhs;      m_arVal[0] &= 0xFFFF;   }   return *this;}CBigNum CBigNum::operator<<(unsigned int rhs) const{   CBigNum result(*this);   result <<= rhs;   return result;}CBigNum CBigNum::operator>>(unsigned int rhs) const{   CBigNum result(*this);   result >>= rhs;   return result;}CBigNum::operator bool(void) const{   unsigned int nIdx;   for (nIdx=0; nIdx < m_nSize; nIdx++)      if (m_arVal[nIdx]) return true;      return false;}CBigNum & CBigNum::operator&=(CBigNum rhs){   unsigned int nIdx;   unsigned int nMin;   if (rhs.m_nSize < m_nSize)      nMin = rhs.m_nSize;   for (nIdx=0; nIdx < nMin; nIdx++)      m_arVal[nIdx] &= rhs.m_arVal[nIdx];   for (;nIdx < m_nSize; nIdx++)      m_arVal[nIdx] = 0;      return *this;}unsigned int CBigNum::operator&(unsigned int rhs){   if (m_nSize)      return m_arVal[0] & rhs;   else      return 0;}CBigNum &CBigNum::operator=(CBigNum rhs){   if (rhs.m_arVal != m_arVal)   {      delete m_arVal;      m_arVal = NULL;      m_nSize=0;      unsigned int nIdx;      Resize(rhs.m_nSize);      for (nIdx = 0; nIdx < m_nSize; nIdx++)         m_arVal[nIdx] = rhs.m_arVal[nIdx];   }   return *this;}CBigNum CBigNum::Pow(unsigned int rhs) const{   CBigNum Result(1);   CBigNum CurrentVal = *this;   while (rhs)   {      if (rhs & 1U)         Result *=(CurrentVal);      rhs >>= 1;      CurrentVal *= CurrentVal;   }      return Result;}CBigNum CBigNum::PowMod(CBigNum rhs, const CBigNum &mod, const clock_t ctShowSteps) const{   CBigNum Result(1);   CBigNum CurrentVal = *this;   int nSteps = rhs.log2();   clock_t ctStart, ctCurrent;   ctStart = ctCurrent = clock();   while (rhs > 0U)   {      if (rhs.m_arVal[0] & 1U)      {         Result = (Result * CurrentVal) % mod;         Result.Reduce();      }      rhs>>=1U;      CurrentVal = (CurrentVal * CurrentVal) % mod;      CurrentVal.Reduce();      nSteps--;      if (ctShowSteps)      {         if (clock() > ctCurrent + ctShowSteps)         {                      ctCurrent = clock();         }      }   }      return Result;}bool CBigNum::operator==(unsigned int rhs) const{   if (m_nSize>=2)      return ((m_arVal[0] == (rhs & 0xFFFF)) && ((m_arVal[1]<<16) == (rhs & 0xFFFF0000)));   else if (m_nSize==1)      return (m_arVal[0] == rhs);   else      return (rhs == 0);}bool CBigNum::operator!=(unsigned int rhs) const{   return !(operator==(rhs));}CBigNum CBigNum::operator *(const CBigNum &rhs) const{   CBigNum Result=0U;   unsigned int i, j;   if (Result.m_nSize != rhs.m_nSize + m_nSize)      Result.Resize(rhs.m_nSize + m_nSize);   for (i=0; i < m_nSize; i++)   {      for (j=0; j<rhs.m_nSize; j++)         Result.m_arVal[i+j] += m_arVal[i] * rhs.m_arVal[j];      Result.HandleCarry();   }   return Result;}CBigNum &CBigNum::operator *=(const CBigNum &rhs){   return *this = *this * rhs;}CBigNum CBigNum::operator *(unsigned int rhs) const{   unsigned int nIdx;   CBigNum result(*this);   if (result.m_nSize==0)   {      return result;   }   for (nIdx = 0; nIdx < result.m_nSize; nIdx++)   {      result.m_arVal[nIdx] *= rhs;   }   result.HandleCarry();   return result;}CBigNum::CBigNum(const CBigNum &copy) : m_nSize(0), m_arVal(0){   unsigned int nIdx;   Resize(copy.m_nSize);   for (nIdx = 0; nIdx < m_nSize; nIdx++)      m_arVal[nIdx] = copy.m_arVal[nIdx];}CBigNum &CBigNum::operator*=(unsigned int rhs){   unsigned int nIdx;   if (m_nSize <= 0)   {      operator=(0U);   }   else   {      for (nIdx = 0; nIdx < m_nSize; nIdx++)      {         m_arVal[nIdx] *= rhs;      }      HandleCarry();   }   return *this;}CBigNumString::CBigNumString() : m_szBuffer(NULL), m_nSize(0){}CBigNumString::~CBigNumString(){   if (m_szBuffer)   {      delete[] m_szBuffer;      m_szBuffer = NULL;      m_nSize = 0;   }}void CBigNumString::Realloc(unsigned int nByteCount){   if (m_szBuffer)   {      delete[] m_szBuffer;      m_szBuffer = NULL;   }   m_szBuffer = new char[nByteCount];   memset(m_szBuffer, 0, nByteCount);   m_nSize = nByteCount;}CBigNumString::CBigNumString(const CBigNumString &rhs) : m_szBuffer(NULL), m_nSize(0){   if ((rhs.m_szBuffer) && (rhs.m_nSize > 0))   {      m_szBuffer = new char[rhs.m_nSize];      strcpy(m_szBuffer, rhs.m_szBuffer);      m_nSize = rhs.m_nSize;   }}CBigNumString::operator const char *() const{   return m_szBuffer;}CBigNum CBigNum::FromByteString(const char *szIn, const unsigned int nLength){   CBigNum Result;   unsigned int i, r;   unsigned int nUseLength;   if (!nLength)      nUseLength = strlen(szIn);   else      nUseLength = nLength;   Result.m_nSize = (nUseLength+1) >> 1;   Result.m_arVal = new unsigned int[Result.m_nSize];   for (i=0; i<nUseLength; i+=1)   {      r = nUseLength - 1 - i;      if (i % 2)         Result.m_arVal[i >> 1] |= ((unsigned int)szIn[r]) << 8;      else         Result.m_arVal[i >> 1] = szIn[r];   }   return Result;}CBigNum CBigNum::FromHexString(const char *szIn){   CBigNum Result;   unsigned int i, r;   unsigned int nUseLength;   unsigned int nPlaceVal;   nUseLength = strlen(szIn);      Result.m_nSize = (nUseLength+3) >> 2;   Result.m_arVal = new unsigned int[Result.m_nSize];   for (i=0; i<nUseLength; i+=1)   {      r = nUseLength - 1 - i;      if ((szIn[r] >= '0') && (szIn[r] <= '9'))         nPlaceVal = szIn[r] - '0';      else if ((szIn[r] >= 'A') && (szIn[r] <= 'F'))         nPlaceVal = szIn[r] - 'A' + 10;      else if ((szIn[r] >= 'a') && (szIn[r] <= 'f'))         nPlaceVal = szIn[r] - 'a' + 10;      else         nPlaceVal = 0;      if (!(i % 4))         Result.m_arVal[i >> 2] = nPlaceVal;      else         Result.m_arVal[i >> 2] |= nPlaceVal << ((i % 4) << 2);   }   return Result;}CBigNum CBigNum::FromBase64String(const char *szIn){   CBigNum Result;   int i, r;   const char *pc;   unsigned int nUseLength;   unsigned int nByteCount;   unsigned char szCharMap[255];   unsigned char bin[4], bout;      memset(szCharMap, 255, 255);   for (i=0; i<sizeof(szBase64)-1; i++)   {      szCharMap[szBase64[i]] = i;   }   szCharMap['='] = 0;   nUseLength = strlen(szIn);   nByteCount = (nUseLength / 4) * 3;   Result.Resize((nByteCount+1)/2);   for (pc=szIn+nUseLength-1;((pc > szIn) && (255 == szCharMap[*pc]));pc--)      ;   for (r=0; r<4; r++)   {      bin[r] = *pc;      while ((pc > szIn) && (255 == szCharMap[*(--pc)]))         ;   }   i=0;   if (bin[0] == '=')      i=-1;   if (bin[1] == '=')      i=-2;   while (true)   {      if ((i>=0) && ((unsigned)i>>1 < Result.m_nSize))      {         bout = szCharMap[bin[0]] | ((szCharMap[bin[1]] & 0x03) << 6);         Result.m_arVal[i>>1] |= bout << ((i % 2) << 3);      }         i++;      if ((i>=0) && ((unsigned)i>>1 < Result.m_nSize))      {         bout = ((szCharMap[bin[1]] & 0x3C) >> 2) | ((szCharMap[bin[2]] & 0x0F) << 4);         Result.m_arVal[i>>1] |= bout << ((i % 2) << 3);      }      i++;      if ((unsigned)i>>1 < Result.m_nSize)      {         bout = ((szCharMap[bin[2]] & 0x30) >> 4) | (szCharMap[bin[3]] << 2);         Result.m_arVal[i>>1] |= bout << ((i % 2) << 3);      }      i++;      if (pc <= szIn)         break;      for (r=0; r<4; r++)      {         bin[r] = *pc;         while ((pc > szIn) && (255 == szCharMap[*(--pc)]))            ;      }         }   Result.Reduce();   return Result;}CBigNumString CBigNum::ToByteString(bool bMakePrintable) const{   CBigNumString Result;   unsigned int nOutSize = m_nSize * 2;   unsigned int i, r;   while ((nOutSize > 0) && !(m_arVal[(nOutSize-1) >> 1] & (0xFF << (((nOutSize-1) % 2) << 3))))      nOutSize--;   Result.Realloc(nOutSize+1);   for (i=0; i<nOutSize; i++)   {      r = nOutSize - 1 - i;      if (i % 2)         Result[r] = (m_arVal[i >> 1] >> 8) & 0xFF;      else         Result[r] = m_arVal[i >> 1] & 0xFF;      if (bMakePrintable)      {         switch (Result[r] & 0xE0)         {         case 0:            switch(Result[r])            {            case 10: // lf            case 13: // cr               break;            default:               Result[r] = '.';               break;            }            break;         case 0x80:         case 0xA0:         case 0xC0:         case 0xE0:            Result[r] = '.';            break;         default:            break;         }      }   }   Result[nOutSize] = '\0';   return Result;}CBigNumString CBigNum::ToHexString() const{   CBigNumString Result;   unsigned int nOutSize = m_nSize * 4;   unsigned int i, r;   while ((nOutSize > 0) && !(m_arVal[(nOutSize-1) >> 2] & (0xF << (((nOutSize-1) % 4) << 2))))      nOutSize--;   Result.Realloc(nOutSize+1);   for (i=0; i<nOutSize; i++)   {      r = nOutSize - 1 - i;      switch((m_arVal[i >> 2] >> ((i % 4) << 2)) & 0xF)      {      case 0:         Result[r] = '0';         break;      case 1:         Result[r] = '1';         break;      case 2:         Result[r] = '2';         break;      case 3:         Result[r] = '3';         break;      case 4:         Result[r] = '4';         break;      case 5:         Result[r] = '5';         break;      case 6:         Result[r] = '6';