bignum.cpp revision 972c3ecf2c929440ce70e51af38ba021101c8f7b
/* $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 *
*******************************************************************************/
/*#ifdef IN_RING3
# define RTMEM_WRAP_TO_EF_APIS
#endif*/
#include <iprt/asm-math.h>
#include <iprt/memsafer.h>
#if RTBIGNUM_ELEMENT_BITS == 64
#endif
/*******************************************************************************
* Defined Constants And Macros *
*******************************************************************************/
/** Allocation alignment in elements. */
#ifndef RTMEM_WRAP_TO_EF_APIS
# define RTBIGNUM_ALIGNMENT 4U
#else
# define RTBIGNUM_ALIGNMENT 1U
#endif
/** The max size (in bytes) of an elements array. */
#define RTBIGNUM_MAX_SIZE _4M
/** Assert the validity of a big number structure pointer in strict builds. */
#ifdef RT_STRICT
# define RTBIGNUM_ASSERT_VALID(a_pBigNum) \
do { \
} while (0)
#else
# define RTBIGNUM_ASSERT_VALID(a_pBigNum) do {} while (0)
#endif
/** Enable assembly optimizations. */
#if defined(RT_ARCH_AMD64) || defined(RT_ARCH_X86)
# define IPRT_BIGINT_WITH_ASM
#endif
/** @def RTBIGNUM_ZERO_ALIGN
* For calculating the rtBigNumEnsureExtraZeroElements argument from cUsed.
* This has to do with 64-bit assembly instruction operating as RTBIGNUMELEMENT
* was 64-bit on some hosts.
*/
#if defined(IPRT_BIGINT_WITH_ASM) && ARCH_BITS == 64 && RTBIGNUM_ELEMENT_SIZE == 4 && defined(RT_LITTLE_ENDIAN)
#elif defined(IPRT_BIGINT_WITH_ASM)
#else
#endif
#define RTBIGNUMELEMENT_HALF_MASK ( ((RTBIGNUMELEMENT)1 << (RTBIGNUM_ELEMENT_BITS / 2)) - (RTBIGNUMELEMENT)1)
/*******************************************************************************
* Structures and Typedefs *
*******************************************************************************/
/** Type the size of two elements. */
#if RTBIGNUM_ELEMENT_BITS == 64
typedef RTUINT128U RTBIGNUMELEMENT2X;
#else
typedef RTUINT64U RTBIGNUMELEMENT2X;
#endif
/*******************************************************************************
* Internal Functions *
*******************************************************************************/
#ifdef IPRT_BIGINT_WITH_ASM
/* bignum-amd64-x86.asm: */
DECLASM(void) rtBigNumMagnitudeSubAssemblyWorker(RTBIGNUMELEMENT *pauResult, RTBIGNUMELEMENT const *pauMinuend,
DECLASM(void) rtBigNumMagnitudeSubThisAssemblyWorker(RTBIGNUMELEMENT *pauMinuendResult, RTBIGNUMELEMENT const *pauSubtrahend,
DECLASM(RTBIGNUMELEMENT) rtBigNumMagnitudeShiftLeftOneAssemblyWorker(RTBIGNUMELEMENT *pauElements, uint32_t cUsed,
DECLASM(void) rtBigNumElement2xDiv2xBy1x(RTBIGNUMELEMENT2X *puQuotient, RTBIGNUMELEMENT *puRemainder,
#endif
/** @name Functions working on one element.
* @{ */
{
#if RTBIGNUM_ELEMENT_SIZE == 8
if (uElement >> 32)
return ASMBitLastSetU32(uElement);
#else
# error "Bad RTBIGNUM_ELEMENT_SIZE value"
#endif
}
/**
* 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,
{
if (!*pfCarry)
else
{
uRet += 1;
}
return uRet;
}
/**
* 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;
}
/** @} */
/** @name Double element primitives.
* @{ */
{
int rc;
{
if (RT_SUCCESS(rc))
{
}
}
{
if (RT_SUCCESS(rc))
}
else
return rc;
}
{
#if RTBIGNUM_ELEMENT_BITS == 64
#else
#endif
}
#ifndef IPRT_BIGINT_WITH_ASM
{
# if RTBIGNUM_ELEMENT_BITS == 64
uDivisor2x.s.Hi = 0;
/** @todo optimize this. */
# else
# endif
}
#endif
{
#if RTBIGNUM_ELEMENT_BITS == 64
#else
puValue->u -= 1;
#endif
}
{
#if RTBIGNUM_ELEMENT_BITS == 64
#else
#endif
}
/** @} */
/**
* 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.
* @param cMinElements The minimum number of elements.
*/
{
{
void *pvNew;
if (pBigNum->fSensitive)
else
{
return VINF_SUCCESS;
}
return VERR_NO_MEMORY;
}
return VERR_OUT_OF_RANGE;
}
/**
* Changes the cUsed member, growing the pauElements array if necessary.
*
* Any elements added to the array will be initialized to zero.
*
* @returns IPRT status code.
* @param pBigNum The big number.
* @param cNewUsed The new cUsed value.
*/
{
{
#ifdef RT_STRICT
#endif
return VINF_SUCCESS;
}
}
/**
* Extended version of rtBigNumSetUsed that also allow specifying the number of
* zero elements required.
*
* @returns IPRT status code.
* @param pBigNum The big number.
* @param cNewUsed The new cUsed value.
* @param cMinElements The minimum number of elements allocated. The
* difference between @a cNewUsed and @a cMinElements
* is initialized to zero because all free elements are
* zero.
*/
{
{
#ifdef RT_STRICT
#endif
return VINF_SUCCESS;
}
}
/**
* operations.
*
* @returns IPRT status code.
* @param pBigNum The big number.
* @param cElements The number of elements that must be in the elements
* array array, where those after pBigNum->cUsed must
* be zero.
*/
{
{
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.
*/
{
}
/*
* Clear unused elements.
*/
{
{
default: AssertFailed();
case 3: *puUnused++ = 0;
case 2: *puUnused++ = 0;
case 1: *puUnused++ = 0;
}
}
}
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
{
RT_BZERO(&pBigNum->pauElements[pBigNum->cUsed], (pBigNum->cAllocated - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE);
}
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;
}
/**
* 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;
}
/**
* 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;
}
/**
* 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;
}
/**
* 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;
}
/**
* 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);
int rc;
if (pSubtrahend->cUsed)
{
/*
* Resize the result. In the assembly case, ensure that all three arrays
* has the same number of used entries, possibly with an extra zero
* element on 64-bit systems.
*/
#ifdef IPRT_BIGINT_WITH_ASM
if (RT_SUCCESS(rc))
if (RT_SUCCESS(rc))
#endif
if (RT_SUCCESS(rc))
{
#ifdef IPRT_BIGINT_WITH_ASM
/*
* Call assembly to do the work.
*/
# ifdef RT_STRICT
RTBIGNUMELEMENT fBorrow = 0;
{
RTBIGNUMELEMENT uCorrect = rtBigNumElementSubWithBorrow(pMinuend->pauElements[i], rtBigNumGetElement(pSubtrahend, i), &fBorrow);
AssertMsg(pResult->pauElements[i] == uCorrect, ("[%u]=%#x, expected %#x\n", i, pResult->pauElements[i], uCorrect));
}
# endif
#else
/*
* The primitive C way.
*/
RTBIGNUMELEMENT fBorrow = 0;
&fBorrow);
#endif
/*
* Trim the result.
*/
}
}
/*
* Special case: Subtrahend is zero.
*/
else
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.
*
* @returns IPRT status code (memory alloc error).
* @param pMinuendResult What to subtract from and return as result.
* @param pSubtrahend What to subtract.
*/
{
#ifdef IPRT_BIGINT_WITH_ASM
/*
* Use the assembly worker. Requires same sized element arrays, so zero extend them.
*/
int rc = rtBigNumEnsureExtraZeroElements(pMinuendResult, RTBIGNUM_ZERO_ALIGN(pMinuendResult->cUsed));
if (RT_SUCCESS(rc))
rc = rtBigNumEnsureExtraZeroElements((PRTBIGNUM)pSubtrahend, RTBIGNUM_ZERO_ALIGN(pMinuendResult->cUsed));
if (RT_FAILURE(rc))
return rc;
rtBigNumMagnitudeSubThisAssemblyWorker(pMinuendResult->pauElements, pSubtrahend->pauElements, pMinuendResult->cUsed);
#else
/*
* The primitive way, as usual.
*/
RTBIGNUMELEMENT fBorrow = 0;
&fBorrow);
#endif
/*
* Trim the result.
*/
return VINF_SUCCESS;
}
{
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. */
rtBigNumSetUsed(pResult, 0);
}
}
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.
*/
{
rtBigNumSetUsed(pResult, 0);
return VINF_SUCCESS;
}
/*
* Allocate a result array that is the sum of the two factors, initialize
* it to zero.
*/
if (RT_SUCCESS(rc))
{
#ifdef IPRT_BIGINT_WITH_ASM
#else
{
{
#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++;
}
}
}
#endif
/* 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;
}
/**
* 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. */
#ifdef IPRT_BIGINT_WITH_ASM
#else
{
}
#endif
/* If we still carry a bit, we need to increase the size. */
if (uCarry)
{
}
return VINF_SUCCESS;
}
/**
* Shifts the magnitude left by @a cBits.
*
* The variables must be unscrambled.
*
* @returns IPRT status code.
* @param pResult Where to store the result.
* @param pValue The value to shift.
* @param cBits The shift count.
*/
{
int rc;
if (cBits)
{
if (cBitsNew > 0)
{
{
rc = rtBigNumSetUsedEx(pResult, 0, RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS);
if (RT_SUCCESS(rc))
rc = rtBigNumSetUsed(pResult, RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS);
if (RT_SUCCESS(rc))
{
if (cBits)
{
RTBIGNUMELEMENT uPrev = 0;
{
}
if (uPrev)
}
else
}
}
else
}
/* Shifting zero always yields a zero result. */
else
}
else
return rc;
}
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
}
}
return rc;
}
/**
* Shifts the magnitude right by @a cBits.
*
* The variables must be unscrambled.
*
* @returns IPRT status code.
* @param pResult Where to store the result.
* @param pValue The value to shift.
* @param cBits The shift count.
*/
{
int rc;
if (cBits)
{
{
if (RT_SUCCESS(rc))
{
uint32_t i = cElementsNew;
if (cBits)
{
while (i-- > 0)
{
}
}
else
}
}
else
}
else
return rc;
}
{
if (RT_SUCCESS(rc))
{
if (RT_SUCCESS(rc))
{
}
}
return rc;
}
/**
* Implements the D3 test for Qhat decrementation.
*
* @returns True if Qhat should be decremented.
* @param puQhat Pointer to Qhat.
* @param uRhat The remainder.
* @param uDivisorY The penultimate divisor element.
* @param uDividendJMinus2 The j-2 dividend element.
*/
DECLINLINE(bool) rtBigNumKnuthD3_ShouldDecrementQhat(RTBIGNUMELEMENT2X const *puQhat, RTBIGNUMELEMENT uRhat,
{
return true;
#if RTBIGNUM_ELEMENT_BITS == 64
return true;
#else
return true;
#endif
return false;
}
/**
* C implementation of the D3 step of Knuth's division algorithm.
*
* This estimates a value Qhat that will be used as quotient "digit" (element)
* at the current level of the division (j).
*
* @returns The Qhat value we've estimated.
* @param pauDividendJN Pointer to the j+n (normalized) dividend element.
* Will access up to two elements prior to this.
* @param uDivZ The last element in the (normalized) divisor.
* @param uDivY The penultimate element in the (normalized) divisor.
*/
{
if (uDividendJN != uDivZ)
else
{
/*
* This is the case where we end up with an initial Qhat that's all Fs.
*/
/* Calc the remainder for max Qhat value. */
#if RTBIGNUM_ELEMENT_BITS == 64
#else
#endif
/* If we overflowed the remainder, don't bother trying to adjust. */
return RTBIGNUM_ELEMENT_MAX;
}
/*
* Adjust Q to eliminate all cases where it's two to large and most cases
* where it's one too large.
*/
{
break;
}
}
#ifdef IPRT_BIGINT_WITH_ASM
#else
/**
* C implementation of the D4 step of Knuth's division algorithm.
*
* This subtracts Divisor * Qhat from the dividend at the current J index.
*
* @returns true if negative result (unlikely), false if positive.
* @param pauDividendJ Pointer to the j-th (normalized) dividend element.
* Will access up to two elements prior to this.
* @param uDivZ The last element in the (normalized) divisor.
* @param uDivY The penultimate element in the (normalized) divisor.
*/
{
uint32_t i;
bool fBorrow = false;
RTBIGNUMELEMENT uMulCarry = 0;
for (i = 0; i < cDivisor; i++)
{
# if RTBIGNUM_ELEMENT_BITS == 64
# else
# endif
if (!fBorrow)
{
}
else
{
}
pauDividendJ[i] = uDividendI;
}
/* Carry and borrow into the final dividend element. */
if (!fBorrow)
{
}
else
{
}
return fBorrow;
}
#endif /* !IPRT_BIGINT_WITH_ASM */
/**
* C implementation of the D6 step of Knuth's division algorithm.
*
* This adds the divisor to the dividend to undo the negative value step D4
* produced. This is not very frequent occurence.
*
* @param pauDividendJ Pointer to the j-th (normalized) dividend element.
* Will access up to two elements prior to this.
* @param uDivZ The last element in the (normalized) divisor.
* @param uDivY The penultimate element in the (normalized) divisor.
*/
DECLINLINE(void) rtBigNumKnuthD6_AddBack(PRTBIGNUMELEMENT pauDividendJ, PRTBIGNUMELEMENT pauDivisor, uint32_t cDivisor)
{
uint32_t i;
for (i = 0; i < cDivisor; i++)
{
#if RTBIGNUM_ELEMENT_BITS == 64
#else
uTmp.u += pauDivisor[i];
uTmp.u += pauDividendJ[i];
#endif
}
/* The final dividend entry. */
}
/**
* Knuth's division (core).
*
* @returns IPRT status code.
* @param pQuotient Where to return the quotient. Can be NULL.
* @param pRemainder Where to return the remainder.
* @param pDividend What to divide.
* @param pDivisor What to divide by.
*/
static int rtBigNumMagnitudeDivideKnuth(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
{
/*
* Make sure we've got enough space in the quotient, so we can build it
* without any trouble come step D5.
*/
int rc;
if (pQuotient)
{
if (RT_SUCCESS(rc))
if (RT_FAILURE(rc))
return rc;
}
/*
* D1. Normalize. The goal here is to make sure the last element in the
* divisor is greater than RTBIGNUMELEMENTS_MAX/2. We must also make sure
* we can access element pDividend->cUsed of the normalized dividend.
*/
uint32_t cNormShift = (RTBIGNUM_ELEMENT_BITS - rtBigNumMagnitudeBitWidth(pDivisor)) & (RTBIGNUM_ELEMENT_BITS - 1);
if (cNormShift)
{
if (RT_SUCCESS(rc))
}
else
{
}
if (RT_SUCCESS(rc))
{
/*
* D2. Initialize the j index so we can loop thru the elements in the
* dividend that makes it larger than the divisor.
*/
for (;;)
{
/*
* D3. Estimate a Q' by dividing the j and j-1 dividen elements by
* the last divisor element, then adjust against the next elements.
*/
RTBIGNUMELEMENT uQhat = rtBigNumKnuthD3_EstimateQhat(&NormDividend.pauElements[j + cDivisor], DivZ, DivY);
/*
* D4. Multiply and subtract.
*/
bool fNegative = rtBigNumKnuthD4_MulSub(&NormDividend.pauElements[j], pNormDivisor->pauElements, cDivisor, uQhat);
/*
* D5. Test remainder.
* D6. Add back.
*/
if (fNegative)
{
//__debugbreak();
uQhat--;
}
if (pQuotient)
/*
* D7. Loop on j.
*/
if (j == 0)
break;
j--;
}
/*
* D8. Unnormalize the remainder.
*/
if (cNormShift)
else
if (pQuotient)
}
/*
* Delete temporary variables.
*/
if (pDivisor == &NormDivisor)
return rc;
}
static int rtBigNumMagnitudeDivideSlowLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
{
/*
* 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
}
}
/* This shouldn't be necessary. */
return rc;
}
/**
* 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 remainder.
* @param pDividend What to divide.
* @param pDivisor What to divide by.
* @param fForceLong Force long division.
*/
static int rtBigNumMagnitudeDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor,
bool fForceLong)
{
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.
*/
rtBigNumSetUsed(pQuotient, 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;
}
/*
* Sort out special cases before going to the preferred or select algorithm.
*/
int rc;
{
{
/*
* Single element division.
*/
rc = VINF_SUCCESS;
if (uQ)
{
if (RT_SUCCESS(rc))
}
{
if (RT_SUCCESS(rc))
}
}
else
{
/*
* Two elements dividend by a one or two element divisor.
*/
{
pDivisor->pauElements[0]);
}
else
if (RT_SUCCESS(rc))
}
}
/*
* Decide upon which algorithm to use. Knuth requires a divisor that's at
* least 2 elements big.
*/
else
return rc;
}
{
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;
}
RTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
{
}
RTDECL(int) RTBigNumDivideLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
{
}
/**
* 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 remainder.
* @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.
*/
/*
* 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;
/** @todo optimize small numbers. */
int rc = VINF_SUCCESS;
{
/*
* Do very simple long division. This ain't fast, but it does the trick.
*/
while (iBit-- > 0)
{
if (iDiff >= 0)
{
if (iDiff != 0)
{
}
else
}
}
}
else
{
/*
* Join paths with division.
*/
}
/* 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. */
{
rtBigNumSetUsed(pResult, 0);
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;
}