gbignumber.cpp

一个非常有用的开源代码

/*
	Copyright (C) 2006, Mike Gashler

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	see http://www.gnu.org/copyleft/lesser.html
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "GBigNumber.h"
#include "GMacros.h"
#include "GKeyPair.h"
#include "GRand.h"
#ifndef WIN32
#include <sys/types.h>
typedef int64_t __int64;
#endif // not WIN32

GBigNumber::GBigNumber()
{
	m_pBits = NULL;
	m_nUInts = 0;
	m_bSign = true;
}

GBigNumber::~GBigNumber()
{
	delete [] m_pBits;
}

unsigned int GBigNumber::GetBitCount()
{
	if(m_nUInts < 1)
		return 0;
	unsigned int nEnd = m_nUInts - 1;
	unsigned int nBitCount = m_nUInts * BITS_PER_INT;
	while(m_pBits[nEnd] == 0)
	{
		nBitCount -= BITS_PER_INT;
		if(nEnd == 0)
			return 0;
		nEnd--;
	}
	unsigned int nVal = m_pBits[nEnd];
	unsigned int nMask = 1 << (BITS_PER_INT - 1);
	while((nVal & nMask) == 0)
	{
		nBitCount--;
		nMask >>= 1;
	}
	return nBitCount;
}

void GBigNumber::Resize(unsigned int nBits)
{
	if(nBits < 1)
	{
		delete [] m_pBits;
		m_pBits = NULL;
		m_nUInts = 0;
		return;
	}
	unsigned int nNewUInts = ((nBits - 1) / BITS_PER_INT) + 1;
	if(nNewUInts <= m_nUInts && nNewUInts + 2 > m_nUInts / 2) // magic heuristic
	{
		unsigned int i;
		for(i = nNewUInts; i < m_nUInts; i++)
			m_pBits[i] = 0;
		return;
	}
	unsigned int* pNewBits = new unsigned int[nNewUInts];
	unsigned int nTop = m_nUInts;
	if(nNewUInts < nTop)
		nTop = nNewUInts;
	unsigned int n;
	for(n = 0; n < nTop; n++)
		pNewBits[n] = m_pBits[n];
	for( ; n < nNewUInts; n++)
		pNewBits[n] = 0;
	delete [] m_pBits;
	m_pBits = pNewBits;
	m_nUInts = nNewUInts;
}

void GBigNumber::SetBit(unsigned int nPos, bool bVal)
{
	if(nPos >= m_nUInts * BITS_PER_INT)
		Resize(nPos + 1);
	if(bVal)
		m_pBits[nPos / BITS_PER_INT] |= (1 << (nPos % BITS_PER_INT));
	else
		m_pBits[nPos / BITS_PER_INT] &= ~(1 << (nPos % BITS_PER_INT));
}

void GBigNumber::SetUInt(unsigned int nPos, unsigned int nVal)
{
	if(nPos >= m_nUInts)
		Resize((nPos + 1) * BITS_PER_INT);
	m_pBits[nPos] = nVal;
}

void GBigNumber::Copy(GBigNumber* pBigNumber)
{
	if(m_nUInts < pBigNumber->m_nUInts)
		Resize(pBigNumber->m_nUInts * BITS_PER_INT);
	if(m_nUInts < 1)
		return;
	unsigned int n;
	for(n = 0; n < pBigNumber->m_nUInts; n++)
		m_pBits[n] = pBigNumber->m_pBits[n];
	for(;n < m_nUInts; n++)
		m_pBits[n] = 0;
	m_bSign = pBigNumber->m_bSign;
}

void GBigNumber::SetToZero()
{
	memset(m_pBits, '\0', m_nUInts * sizeof(unsigned int));
	m_bSign = true;
}

bool GBigNumber::IsZero()
{
	if(m_nUInts < 1)
		return true;
	unsigned int n;
	for(n = 0; n < m_nUInts; n++)
	{
		if(m_pBits[n] != 0)
			return false;
	}
	return true;
}

unsigned int* GBigNumber::ToBufferGiveOwnership()
{
	unsigned int* pBuffer = m_pBits;
	m_bSign = true;
	m_nUInts = 0;
	m_pBits = NULL;
	return pBuffer;
}

bool GBigNumber::ToBuffer(unsigned int* pBuffer, int nBufferSize)
{
	int nSize = GetUIntCount();
	if(nBufferSize < nSize)
		return false;
	int n;
	for(n = nSize - 1; n >= 0; n--)
		pBuffer[n] = m_pBits[n];
	return true;
}

void GBigNumber::FromBuffer(const unsigned int* pBuffer, int nBufferSize)
{
	SetToZero();
	int n;
	for(n = nBufferSize - 1; n >= 0; n--)
		SetUInt(n, pBuffer[n]);
}

void GBigNumber::FromByteBuffer(const unsigned char* pBuffer, int nBufferChars)
{
	// Make sure input is alligned to sizeof(unsigned int)
	int nTempBufSize = nBufferChars + sizeof(unsigned int) - 1;
	GTEMPBUF(unsigned char, pBuf, nTempBufSize);
	if((nBufferChars % sizeof(unsigned int)) != 0)
	{
		memset(pBuf, '\0', nBufferChars + sizeof(unsigned int) - 1);
		memcpy(pBuf, pBuffer, nBufferChars);
		pBuffer = pBuf;
		nBufferChars += sizeof(unsigned int) - 1;
	}
	nBufferChars /= sizeof(unsigned int);
	FromBuffer((unsigned int*)pBuffer, nBufferChars);
}

bool GBigNumber::ToHex(char* szBuff, int nBufferSize)
{
	bool bStarted = false;
	int nUInts = GetUIntCount();
	int n, i;
	unsigned char byte;
	char c;
	int nPos = 0;
	for(n = nUInts - 1; n >= 0; n--)
	{
		for(i = sizeof(int) * 2 - 1; i >= 0; i--)
		{
			byte = (m_pBits[n] >> (4 * i)) & 15;
			if(byte == 0 && !bStarted)
				continue;
			bStarted = true;
			c = byte < 10 ? '0' + byte : 'a' - 10 + byte;
			szBuff[nPos] = c;
			nPos++;
			if(nPos >= nBufferSize)
				return false;
		}
	}
	szBuff[nPos] = '\0';
	return true;
}

bool GBigNumber::FromHex(const char* szHexValue)
{
	unsigned int nLength = strlen(szHexValue);
	Resize(nLength * 4);
	SetToZero();
	unsigned int nUIntPos = 0;
	unsigned int nHexCount = 0;
	unsigned int n;
	for(n = 0; n < nLength; n++)
	{
		unsigned int nTmp;
		char cTmp = szHexValue[nLength - n - 1];
		if(cTmp >= '0' && cTmp <= '9')
			nTmp = cTmp - '0';
		else if(cTmp >= 'A' && cTmp <= 'F')
			nTmp = cTmp - 'A' + 10;
		else if(cTmp >= 'a' && cTmp <= 'f')
			nTmp = cTmp - 'a' + 10;
		else
			return false;
		m_pBits[nUIntPos] |= (nTmp << (4 * nHexCount));
		nHexCount++;
		if(nHexCount >= sizeof(unsigned int) * 2)
		{
			nHexCount = 0;
			nUIntPos++;
		}
	}
	return true;
}

void GBigNumber::Invert()
{
	m_bSign = !m_bSign;
}

int GBigNumber::CompareTo(GBigNumber* pOperand)
{
	if(m_bSign != pOperand->m_bSign)
	{
		if(IsZero() && pOperand->IsZero())
			return 0;
		return m_bSign ? 1 : -1;
	}
	int nCmp = 0;
	unsigned int nA;
	unsigned int nB;
	unsigned int n = m_nUInts;
	if(pOperand->m_nUInts > n)
		n = pOperand->m_nUInts;
	n--;
	while(true)
	{
		nA = GetUInt(n);
		nB = pOperand->GetUInt(n);
		if(nA != nB)
		{
			nCmp = nA > nB ? 1 : -1;
			break;
		}
		if(n == 0)
			break;
		n--;
	}
	return m_bSign ? nCmp : -nCmp;
}

void GBigNumber::Increment()
{
	if(!m_bSign)
	{
		Invert();
		Decrement();
		Invert();
		return;
	}
	unsigned int n;
	for(n = 0; true; n++)
	{
		if(n == m_nUInts)
			Resize(m_nUInts * BITS_PER_INT + 1);
		m_pBits[n]++;
		if(m_pBits[n] != 0)
			return;
	}
}

void GBigNumber::Decrement()
{
	if(!m_bSign)
	{
		Invert();
		Increment();
		Invert();
		return;
	}
	if(IsZero())
	{
		Increment();
		Invert();
		return;
	}
	unsigned int n;
	for(n = 0; true; n++)
	{
		if(m_pBits[n] == 0)
			m_pBits[n]--;
		else
		{
			m_pBits[n]--;
			return;
		}
	}
}

void GBigNumber::Add(GBigNumber* pBigNumber)
{
	// Check signs
	if(!m_bSign)
	{
		Invert();
		Subtract(pBigNumber);
		Invert();
		return;
	}
	if(!pBigNumber->m_bSign)
	{
		pBigNumber->Invert();
		Subtract(pBigNumber);
		pBigNumber->Invert();
		return;
	}

	// See if we need a bigger buffer
	unsigned int nBits = GetBitCount();
	unsigned int nTmp = pBigNumber->GetBitCount();
	if(nTmp > nBits)
		nBits = nTmp;
	nBits++;
	if(nBits > m_nUInts * BITS_PER_INT)
		Resize(nBits);

	// Add it up
	unsigned int nSum;
	unsigned int n;
	unsigned int nOperand;
	bool bNextCarry;
	bool bCarry = false;
	for(n = 0; n < m_nUInts; n++)
	{
		nOperand = pBigNumber->GetUInt(n);
		nSum = m_pBits[n] + nOperand;
		if(nSum < m_pBits[n] && nSum < nOperand)
			bNextCarry = true;
		else
			bNextCarry = false;
		if(bCarry)
		{
			if(++nSum == 0)
				bNextCarry = true;
		}
		bCarry = bNextCarry;
		m_pBits[n] = nSum;
	}
}

void GBigNumber::Subtract(GBigNumber* pBigNumber)
{
	// Check signs
	if(!m_bSign)
	{
		Invert();
		Add(pBigNumber);
		Invert();
		return;
	}
	if(!pBigNumber->m_bSign)
	{
		pBigNumber->Invert();
		Add(pBigNumber);
		pBigNumber->Invert();
		return;
	}

	// Check sizes
	GBigNumber tmp;
	GBigNumber* pA = this;
	GBigNumber* pB = pBigNumber;
	int nCmp = CompareTo(pBigNumber);
	if(nCmp < 0)
	{
		tmp.Copy(pBigNumber);
		pA = &tmp;
		pB = this;
	}

	// Subtract
	unsigned int n;
	unsigned int nA;
	unsigned int nB;
	bool bNextBorrow;
	bool bBorrow = false;
	for(n = 0; n < pA->m_nUInts; n++)
	{
		nA = pA->m_pBits[n];
		nB = pB->GetUInt(n);
		bNextBorrow = false;
		if(bBorrow)
		{
			if(nA == 0)
				bNextBorrow = true;
			nA--;
		}
		if(nB > nA)
			bNextBorrow = true;
		pA->m_pBits[n] = nA - nB;
		bBorrow = bNextBorrow;
	}

	// Invert again if we swapped A and B
	if(nCmp < 0)
	{
		tmp.Invert();
		Copy(&tmp);
	}
}

void GBigNumber::ShiftLeft(unsigned int nBits)
{
	ShiftLeftBits(nBits % BITS_PER_INT);
	ShiftLeftUInts(nBits / BITS_PER_INT);
}

void GBigNumber::ShiftLeftBits(unsigned int nBits)
{
	if(m_nUInts == 0)
		return;
	if(nBits == 0)
		return;
	if(m_pBits[m_nUInts - 1] != 0)
		Resize(GetBitCount() + nBits);
	unsigned int n;
	unsigned int nCarry = 0;
	unsigned int nNextCarry;
	for(n = 0; n < m_nUInts; n++)
	{
		nNextCarry = m_pBits[n] >> (BITS_PER_INT - nBits);