bignum.cpp revision 13493ab7596e827b8d0caab2c89e635dd65f78f9
/* $Id$ */
/** @file
* IPRT - Big Integer Numbers.
*/
/*
* Copyright (C) 2006-2014 Oracle Corporation
*
* This file is part of VirtualBox Open Source Edition (OSE), as
* available from http://www.virtualbox.org. This file is free software;
* General Public License (GPL) as published by the Free Software
* Foundation, in version 2 as it comes in the "COPYING" file of the
* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
*
* The contents of this file may alternatively be used under the terms
* of the Common Development and Distribution License Version 1.0
* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
* VirtualBox OSE distribution, in which case the provisions of the
* CDDL are applicable instead of those of the GPL.
*
* You may elect to license modified versions of this file under the
* terms and conditions of either the GPL or the CDDL or both.
*/
/*******************************************************************************
* Header Files *
*******************************************************************************/
#if defined(DEBUG_bird) && !defined(IN_SUP_HARDENED_R3)
# define RTMEM_WRAP_TO_EF_APIS
#endif
#include <iprt/asm-math.h>
#include <iprt/memsafer.h>
/** The max size (in bytes) of an elements array. */
#define RTBIGNUM_MAX_SIZE _4M
/**
* Scrambles a big number if required.
*
* @param pBigNum The big number.
*/
{
if (pBigNum->fSensitive)
{
if (pBigNum->pauElements)
{
int rc = RTMemSaferScramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
}
else
pBigNum->fCurScrambled = true;
}
}
/**
* Unscrambles a big number if required.
*
* @returns IPRT status code.
* @param pBigNum The big number.
*/
{
if (pBigNum->fSensitive)
{
if (pBigNum->pauElements)
{
int rc = RTMemSaferUnscramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
return rc;
}
else
pBigNum->fCurScrambled = false;
}
return VINF_SUCCESS;
}
/**
* Getter function for pauElements which extends the array to infinity.
*
* @returns The element value.
* @param pBigNum The big number.
* @param iElement The element index.
*/
{
return 0;
}
/**
* Grows the pauElements array so it can fit at least @a cNewUsed entries.
*
* @returns IPRT status code.
* @param pBigNum The big number.
* @param cNewUsed The new cUsed value.
*/
{
void *pvNew;
if (pBigNum->fSensitive)
else
{
return VINF_SUCCESS;
}
return VERR_NO_MEMORY;
}
/**
* Changes the cUsed member, growing the pauElements array if necessary.
*
* No assumptions about the value of any added elements should be made. This
* method is mainly for resizing result values where the caller will repopulate
* the element values short after this call.
*
* @returns IPRT status code.
* @param pBigNum The big number.
* @param cNewUsed The new cUsed value.
*/
{
{
return VINF_SUCCESS;
}
}
/**
* The slow part of rtBigNumEnsureElementPresent where we need to do actual zero
* extending.
*
* @returns IPRT status code.
* @param pBigNum The big number.
* @param iElement The element we wish to access.
*/
{
if (RT_SUCCESS(rc))
{
return VINF_SUCCESS;
}
return rc;
}
/**
* Zero extends the element array to make sure a the specified element index is
* accessible.
*
* This is typically used with bit operations and self modifying methods. Any
* new elements added will be initialized to zero. The caller is responsible
* for there not being any trailing zero elements.
*
* The number must be unscrambled.
*
* @returns IPRT status code.
* @param pBigNum The big number.
* @param iElement The element we wish to access.
*/
{
return VINF_SUCCESS;
}
/**
* Strips zero elements from the magnitude value.
*
* @param pBigNum The big number to strip.
*/
{
i--;
}
/**
* Initialize the big number to zero.
*
* @returns @a pBigNum
* @param pBigNum The big number.
* @param fFlags The flags.
* @internal
*/
{
return pBigNum;
}
/**
* Initialize the big number to zero from a template variable.
*
* @returns @a pBigNum
* @param pBigNum The big number.
* @param pTemplate The template big number.
* @internal
*/
{
return pBigNum;
}
{
/*
* Validate input.
*/
AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_BIG) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE),
AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_UNSIGNED) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_SIGNED), VERR_INVALID_PARAMETER);
if (cbRaw)
/*
* Initalize the big number to zero.
*/
/*
* Strip the input and figure the sign flag.
*/
if (cbRaw)
{
{
if (fFlags & RTBIGNUMINIT_F_UNSIGNED)
{
cbRaw--;
}
else
{
{
cbRaw--;
}
else
cbRaw--;
}
}
else
{
if (fFlags & RTBIGNUMINIT_F_UNSIGNED)
{
}
else
{
if (*pb >> 7)
{
}
else
}
}
}
/*
* Allocate memory for the elements.
*/
return VERR_OUT_OF_RANGE;
{
if (pBigNum->fSensitive)
pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemSaferAllocZ(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
else
return VERR_NO_MEMORY;
/*
* Initialize the array.
*/
uint32_t i = 0;
{
while (cbRaw >= RTBIGNUM_ELEMENT_SIZE)
{
#if RTBIGNUM_ELEMENT_SIZE == 8
pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[0], pb[1], pb[2], pb[3], pb[4], pb[5], pb[6], pb[7]);
#else
# error "Bad RTBIGNUM_ELEMENT_SIZE value"
#endif
i++;
}
if (cbRaw > 0)
{
switch (cbRaw)
{
default: AssertFailed();
#if RTBIGNUM_ELEMENT_SIZE == 8
#endif
}
}
}
else
{
while (cbRaw >= RTBIGNUM_ELEMENT_SIZE)
{
#if RTBIGNUM_ELEMENT_SIZE == 8
pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[7], pb[6], pb[5], pb[4], pb[3], pb[2], pb[1], pb[0]);
#else
# error "Bad RTBIGNUM_ELEMENT_SIZE value"
#endif
i++;
}
if (cbRaw > 0)
{
switch (cbRaw)
{
default: AssertFailed();
#if RTBIGNUM_ELEMENT_SIZE == 8
#endif
}
}
}
/*
* If negative, negate it so we get a positive magnitude value in pauElements.
*/
{
}
}
return VINF_SUCCESS;
}
{
return VINF_SUCCESS;
}
/**
* Internal clone function that assumes the caller takes care of scrambling.
*
* @returns IPRT status code.
* @param pBigNum The target number.
* @param pSrc The source number.
*/
{
int rc = VINF_SUCCESS;
/*
* Copy over the data.
*/
{
/* Duplicate the element array. */
if (pBigNum->fSensitive)
pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemSaferAllocZ(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
else
else
{
rc = VERR_NO_MEMORY;
}
}
return rc;
}
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
}
return rc;
}
{
if (pBigNum)
{
if (pBigNum->pauElements)
{
if (pBigNum->fSensitive)
{
}
}
}
return VINF_SUCCESS;
}
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
|| pDst->fSensitive)
{
{
}
else
{
if (RT_SUCCESS(rc))
{
}
}
}
else
}
}
return rc;
}
{
#if RTBIGNUM_ELEMENT_SIZE == 8
if (uElement >> 32)
return ASMBitLastSetU32(uElement);
#else
# error "Bad RTBIGNUM_ELEMENT_SIZE value"
#endif
}
/**
* Same as RTBigNumBitWidth, except that it ignore the signed bit.
*
* The number must be unscrambled.
*
* @returns The effective width of the magnitude, in bits. Returns 0 if the
* value is zero.
* @param pBigNum The bit number.
*/
{
if (idxLast)
{
idxLast--;
}
return 0;
}
{
if (idxLast)
{
idxLast--;
}
return 0;
}
{
}
{
if (RT_SUCCESS(rc))
{
rc = VINF_SUCCESS;
{
{
{
uElement >>= 8;
uElement >>= 8;
uElement >>= 8;
#if RTBIGNUM_ELEMENT_SIZE == 8
uElement >>= 8;
uElement >>= 8;
uElement >>= 8;
uElement >>= 8;
# error "Bad RTBIGNUM_ELEMENT_SIZE value"
#endif
}
else
{
while (cbWanted > 0)
{
uElement >>= 8;
cBitsLeft -= 8;
cbWanted--;
}
? uElement != 0
break;
}
}
/* Sign extend the number to the desired output size. */
if (cbWanted > 0)
}
else
}
return rc;
}
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
{
{
rc = 0;
while (i-- > 0)
{
break;
}
}
else
}
else
}
}
return rc;
}
{
if (RT_SUCCESS(rc))
{
{
{
else
{
#if RTBIGNUM_ELEMENT_SIZE == 8
rc = -1;
else
{
}
rc = -1;
else
#else
# error "Bad RTBIGNUM_ELEMENT_SIZE value"
#endif
}
}
else
rc = 1;
}
else
rc = -1;
}
return rc;
}
{
if (RT_SUCCESS(rc))
{
{
{
#if RTBIGNUM_ELEMENT_SIZE == 8
if (uLeft < uRightMagn)
rc = -1;
else
{
}
rc = -1;
else
#else
# error "Bad RTBIGNUM_ELEMENT_SIZE value"
#endif
}
else
}
else
}
return rc;
}
#define RTBIGNUMELEMENT_HALF_MASK ( ((RTBIGNUMELEMENT)1 << (RTBIGNUM_ELEMENT_BITS / 2)) - (RTBIGNUMELEMENT)1)
/**
* Compares the magnitude values of two big numbers.
*
* @retval -1 if pLeft is smaller than pRight.
* @retval 0 if pLeft is equal to pRight.
* @retval 1 if pLeft is larger than pRight.
* @param pLeft The left side number.
* @param pRight The right side number.
*/
{
int rc;
{
rc = 0;
while (i-- > 0)
{
break;
}
}
else
return rc;
}
/**
* Does addition with carry.
*
* This is a candidate for inline assembly on some platforms.
*
* @returns The result (the sum)
* @param uAugend What to add to.
* @param uAddend What to add to it.
* @param pfCarry Where to read the input carry and return the output
* carry.
*/
DECLINLINE(RTBIGNUMELEMENT) rtBigNumElementAddWithCarry(RTBIGNUMELEMENT uAugend, RTBIGNUMELEMENT uAddend,
{
/* Determin carry the expensive way. */
if (uTmp < RTBIGNUMELEMENT_HALF_MASK)
*pfCarry = 0;
else
return uRet;
}
/**
* Adds two magnitudes and stores them into a third.
*
* All variables must be unscrambled. The sign flag is not considered nor
* touched.
*
* @returns IPRT status code.
* @param pResult The resultant.
* @param pAugend To whom it shall be addede.
* @param pAddend The nombre to addede.
*/
{
if (RT_SUCCESS(rc))
{
/*
* The primitive way, requires at least two additions for each entry
* without machine code help.
*/
RTBIGNUMELEMENT fCarry = 0;
&fCarry);
if (fCarry)
{
if (RT_SUCCESS(rc))
}
}
return rc;
}
/**
* Does addition with borrow.
*
* This is a candidate for inline assembly on some platforms.
*
* @returns The result (the sum)
* @param uMinuend What to subtract from.
* @param uSubtrahend What to subtract.
* @param pfBorrow Where to read the input borrow and return the output
* borrow.
*/
DECLINLINE(RTBIGNUMELEMENT) rtBigNumElementSubWithBorrow(RTBIGNUMELEMENT uMinuend, RTBIGNUMELEMENT uSubtrahend,
{
/* Figure out if we borrowed. */
return uRet;
}
/**
* Substracts a smaller (or equal) magnitude from another one and stores it into
* a third.
*
* All variables must be unscrambled. The sign flag is not considered nor
* touched. For this reason, the @a pMinuend must be larger or equal to @a
* pSubtrahend.
*
* @returns IPRT status code.
* @param pResult There to store the result.
* @param pMinuend What to subtract from.
* @param pSubtrahend What to subtract.
*/
{
Assert(!pResult->fCurScrambled); Assert(!pMinuend->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
if (RT_SUCCESS(rc))
{
/*
* The primitive way, as usual.
*/
RTBIGNUMELEMENT fBorrow = 0;
&fBorrow);
/*
* Trim the result.
*/
}
return rc;
}
/**
* Substracts a smaller (or equal) magnitude from another one and stores the
* result into the first.
*
* All variables must be unscrambled. The sign flag is not considered nor
* touched. For this reason, the @a pMinuendResult must be larger or equal to
* @a pSubtrahend.
*
* @param pMinuendResult What to subtract from and return as result.
* @param pSubtrahend What to subtract.
*/
{
/*
* The primitive way, as usual.
*/
RTBIGNUMELEMENT fBorrow = 0;
&fBorrow);
/*
* Trim the result.
*/
}
{
AssertReturn(pResult->fSensitive >= (pAugend->fSensitive | pAddend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
/*
* Same sign: Add magnitude, keep sign.
* 1 + 1 = 2
* (-1) + (-1) = -2
*/
{
}
/*
* Different sign: Subtract smaller from larger, keep sign of larger.
* (-5) + 3 = -2
* 5 + (-3) = 2
* (-1) + 3 = 2
* 1 + (-3) = -2
*/
{
}
else
{
}
}
}
}
return rc;
}
{
AssertReturn(pResult->fSensitive >= (pMinuend->fSensitive | pSubtrahend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
if (RT_SUCCESS(rc))
{
if (pMinuend != pSubtrahend)
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
/*
* Different sign: Add magnitude, keep sign of first.
* 1 - (-2) == 3
* -1 - 2 == -3
*/
{
}
/*
* Same sign, minuend has greater or equal absolute value: Subtract, keep sign of first.
* 10 - 7 = 3
*/
{
}
/*
* Same sign, subtrahend is larger: Reverse and subtract, invert sign of first.
* 7 - 10 = -3
* -1 - (-3) = 2
*/
else
{
}
}
}
}
else
{
/* zero. */
}
}
return rc;
}
{
return VINF_SUCCESS;
}
{
if (RT_SUCCESS(rc))
return rc;
}
/**
* Multiplies the magnitudes of two values, letting the caller care about the
* sign bit.
*
* @returns IPRT status code.
* @param pResult Where to store the result.
* @param pMultiplicand The first value.
* @param pMultiplier The second value.
*/
static int rtBigNumMagnitudeMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
{
Assert(!pResult->fCurScrambled); Assert(!pMultiplicand->fCurScrambled); Assert(!pMultiplier->fCurScrambled);
/*
* Multiplication involving zero is zero.
*/
{
return VINF_SUCCESS;
}
/*
* Allocate a result array that is the sum of the two factors, initialize
* it to zero.
*/
if (RT_SUCCESS(rc))
{
{
{
#if RTBIGNUM_ELEMENT_SIZE == 4
#else
# error "Invalid RTBIGNUM_ELEMENT_SIZE value"
#endif
RTBIGNUMELEMENT fCarry = 0;
uint64_t k = i + j;
k++;
while (fCarry)
{
k++;
}
}
}
/* It's possible we overestimated the output size by 1 element. */
}
return rc;
}
{
AssertReturn(pResult->fSensitive >= (pMultiplicand->fSensitive | pMultiplier->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
/*
* The sign values follow XOR rules:
* -1 * 1 = -1; 1 ^ 0 = 1
* 1 * -1 = -1; 1 ^ 0 = 1
* -1 * -1 = 1; 1 ^ 1 = 0
* 1 * 1 = 1; 0 ^ 0 = 0
*/
}
}
}
return rc;
}
/**
* Copies the magnitude of on number (@a pSrc) to another (@a pBigNum).
*
* The variables must be unscrambled. The sign flag is not considered nor
* touched.
*
* @returns IPRT status code.
* @param pDst The destination number.
* @param pSrc The source number.
*/
{
if (RT_SUCCESS(rc))
return rc;
}
/**
* Clears a bit in the magnitude of @a pBigNum.
*
* The variables must be unscrambled.
*
* @param pBigNum The big number.
* @param iBit The bit to clear (0-based).
*/
{
{
}
}
/**
* Sets a bit in the magnitude of @a pBigNum.
*
* The variables must be unscrambled.
*
* @returns IPRT status code.
* @param pBigNum The big number.
* @param iBit The bit to clear (0-based).
*/
{
if (RT_SUCCESS(rc))
{
return VINF_SUCCESS;
}
return rc;
}
/**
* Writes a bit in the magnitude of @a pBigNum.
*
* The variables must be unscrambled.
*
* @returns IPRT status code.
* @param pBigNum The big number.
* @param iBit The bit to write (0-based).
* @param fValue The bit value.
*/
{
if (fValue)
return VINF_SUCCESS;
}
/**
* Returns the given magnitude bit.
*
* The variables must be unscrambled.
*
* @returns The bit value (1 or 0).
* @param pBigNum The big number.
* @param iBit The bit to return (0-based).
*/
{
return 0;
}
/**
* Shifts the magnitude left by one.
*
* The variables must be unscrambled.
*
* @returns IPRT status code.
* @param pBigNum The big number.
* @param uCarry The value to shift in at the bottom.
*/
{
/* Do the shifting. */
{
}
/* If we still carry a bit, we need to increase the size. */
if (uCarry)
{
}
return VINF_SUCCESS;
}
/**
* Divides the magnitudes of two values, letting the caller care about the sign
* bit.
*
* All variables must be unscrambled. The sign flag is not considered nor
* touched, this means the caller have to check for zero outputs.
*
* @returns IPRT status code.
* @param pQuotient Where to return the quotient.
* @param pRemainder Where to return the reminder.
* @param pDividend What to divide.
* @param pDivisor What to divide by.
*/
static int rtBigNumMagnitudeDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
{
Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
Assert(!pQuotient->fCurScrambled); Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
/*
* Just set both output values to zero as that's the return for several
* special case and the initial state of the general case.
*/
pRemainder->cUsed = 0;
/*
* Dividing something by zero is undefined.
* Diving zero by something is zero, unless the divsor is also zero.
*/
/*
* Dividing by one? Quotient = dividend, no remainder.
*/
/*
* Dividend smaller than the divisor. Zero quotient, all divisor.
*/
if (iDiff < 0)
/*
* Since we already have done the compare, check if the two values are the
* same. The result is 1 and no remainder then.
*/
if (iDiff == 0)
{
if (RT_SUCCESS(rc))
return rc;
}
/*
* Do very simple long division. This ain't fast, but it does the trick.
*/
int rc = VINF_SUCCESS;
while (iBit-- > 0)
{
if (iDiff >= 0)
{
if (iDiff != 0)
else
pRemainder->cUsed = 0;
}
}
/* This shouldn't be necessary. */
return rc;
}
RTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
{
Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
AssertReturn(pQuotient->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
/*
* The sign value of the remainder is the same as the dividend.
* The sign values of the quotient follow XOR rules, just like multiplication:
* -3 / 2 = -1; r=-1; 1 ^ 0 = 1
* 3 / -2 = -1; r= 1; 1 ^ 0 = 1
* -3 / -2 = 1; r=-1; 1 ^ 1 = 0
* 3 / 2 = 1; r= 1; 0 ^ 0 = 0
*/
if (pRemainder->cUsed == 0)
pRemainder->fNegative = 0;
}
}
}
}
return rc;
}
/**
* Calculates the modulus of a magnitude value, leaving the sign bit to the
* caller.
*
* All variables must be unscrambled. The sign flag is not considered nor
* touched, this means the caller have to check for zero outputs.
*
* @returns IPRT status code.
* @param pRemainder Where to return the reminder.
* @param pDividend What to divide.
* @param pDivisor What to divide by.
*/
{
Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
/*
* Just set the output value to zero as that's the return for several
* special case and the initial state of the general case.
*/
pRemainder->cUsed = 0;
/*
* Dividing something by zero is undefined.
* Diving zero by something is zero, unless the divsor is also zero.
*/
/*
* Dividing by one? Quotient = dividend, no remainder.
*/
return VINF_SUCCESS;
/*
* Dividend smaller than the divisor. Zero quotient, all divisor.
*/
if (iDiff < 0)
/*
* Since we already have done the compare, check if the two values are the
* same. The result is 1 and no remainder then.
*/
if (iDiff == 0)
return VINF_SUCCESS;
/*
* Do very simple long division. This ain't fast, but it does the trick.
*/
int rc = VINF_SUCCESS;
while (iBit-- > 0)
{
if (iDiff >= 0)
{
if (iDiff != 0)
else
pRemainder->cUsed = 0;
}
}
/* This shouldn't be necessary. */
return rc;
}
{
AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
/*
* The sign value of the remainder is the same as the dividend.
*/
if (pRemainder->cUsed == 0)
pRemainder->fNegative = 0;
}
}
}
return rc;
}
/**
* Exponentiate the magnitude.
*
* All variables must be unscrambled. The sign flag is not considered nor
* touched, this means the caller have to reject negative exponents.
*
* @returns IPRT status code.
* @param pResult Where to return power.
* @param pBase The base value.
* @param pExponent The exponent (assumed positive or zero).
*/
{
/*
* A couple of special cases.
*/
int rc;
/* base ^ 0 => 1. */
{
if (RT_SUCCESS(rc))
return rc;
}
/* base ^ 1 => base. */
/*
* Set up.
*/
/* Init temporary power-of-two variable to base. */
if (RT_SUCCESS(rc))
{
/* Init result to 1. */
if (RT_SUCCESS(rc))
{
/* Make a temporary variable that we can use for temporary storage of the result. */
if (RT_SUCCESS(rc))
{
/*
* Exponentiation by squaring. Reduces the number of
* multiplications to: NumBitsSet(Exponent) + BitWidth(Exponent).
*/
for (;;)
{
{
if (RT_SUCCESS(rc))
if (RT_FAILURE(rc))
break;
}
/* Done? */
iBit++;
break;
/* Not done yet, square the base again. */
if (RT_SUCCESS(rc))
if (RT_FAILURE(rc))
break;
}
}
}
}
return rc;
}
{
AssertReturn(pResult->fSensitive >= (pBase->fSensitive | pExponent->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
{
}
else
}
}
}
return rc;
}
/**
* Modular exponentiation, magnitudes only.
*
* All variables must be unscrambled. The sign flag is not considered nor
* touched, this means the caller have to reject negative exponents and do any
* other necessary sign bit fiddling.
*
* @returns IPRT status code.
* @param pResult Where to return the remainder of the power.
* @param pBase The base value.
* @param pExponent The exponent (assumed positive or zero).
* @param pModulus The modulus value (or divisor if you like).
*/
static int rtBigNumMagnitudeModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
{
Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled); Assert(!pModulus->fCurScrambled);
int rc;
/*
* Check some special cases to get them out of the way.
*/
/* Div by 0 => invalid. */
return VERR_BIGNUM_DIV_BY_ZERO;
/* Div by 1 => no remainder. */
{
return VINF_SUCCESS;
}
/* base ^ 0 => 1. */
{
if (RT_SUCCESS(rc))
return rc;
}
/* base ^ 1 => base. */
/*
* Set up.
*/
/* Result = 1; preallocate space for the result while at it. */
if (RT_SUCCESS(rc))
if (RT_SUCCESS(rc))
{
/* ModBase = pBase or pBase % pModulus depending on the difference in size. */
else
/* Need a couple of temporary variables. */
/*
* We combine the exponentiation by squaring with the fact that:
* (a*b) mod n = ( (a mod n) * (b mod n) ) mod n
*
* Thus, we can reduce the size of intermediate results by mod'ing them
* in each step.
*/
for (;;)
{
{
if (RT_SUCCESS(rc))
if (RT_SUCCESS(rc))
if (RT_FAILURE(rc))
break;
}
/* Done? */
iBit++;
break;
/* Not done yet, square and mod the base again. */
if (RT_SUCCESS(rc))
if (RT_SUCCESS(rc))
if (RT_FAILURE(rc))
break;
}
}
return rc;
}
RTDECL(int) RTBigNumModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
{
Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
AssertReturn(pResult->fSensitive >= (pBase->fSensitive | pExponent->fSensitive | pModulus->fSensitive),
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
{
}
else
}
}
}
}
return rc;
}