13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * IPRT - Big Integer Numbers.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Copyright (C) 2006-2014 Oracle Corporation
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * available from http://www.virtualbox.org. This file is free software;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * you can redistribute it and/or modify it under the terms of the GNU
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * General Public License (GPL) as published by the Free Software
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The contents of this file may alternatively be used under the terms
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * of the Common Development and Distribution License Version 1.0
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * VirtualBox OSE distribution, in which case the provisions of the
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * CDDL are applicable instead of those of the GPL.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * You may elect to license modified versions of this file under the
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * terms and conditions of either the GPL or the CDDL or both.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync/*******************************************************************************
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync* Header Files *
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync*******************************************************************************/
400422edee24dcbb377417b13ed03412cc3a226bvboxsync/*#ifdef IN_RING3
400422edee24dcbb377417b13ed03412cc3a226bvboxsync# define RTMEM_WRAP_TO_EF_APIS
400422edee24dcbb377417b13ed03412cc3a226bvboxsync/*******************************************************************************
400422edee24dcbb377417b13ed03412cc3a226bvboxsync* Defined Constants And Macros *
400422edee24dcbb377417b13ed03412cc3a226bvboxsync*******************************************************************************/
400422edee24dcbb377417b13ed03412cc3a226bvboxsync/** Allocation alignment in elements. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync/** The max size (in bytes) of an elements array. */
400422edee24dcbb377417b13ed03412cc3a226bvboxsync/** Assert the validity of a big number structure pointer in strict builds. */
400422edee24dcbb377417b13ed03412cc3a226bvboxsync Assert( (a_pBigNum)->cUsed == (a_pBigNum)->cAllocated \
400422edee24dcbb377417b13ed03412cc3a226bvboxsync || ASMMemIsAllU32(&(a_pBigNum)->pauElements[(a_pBigNum)->cUsed], \
400422edee24dcbb377417b13ed03412cc3a226bvboxsync ((a_pBigNum)->cAllocated - (a_pBigNum)->cUsed) * RTBIGNUM_ELEMENT_SIZE, 0) == NULL); \
400422edee24dcbb377417b13ed03412cc3a226bvboxsync } while (0)
400422edee24dcbb377417b13ed03412cc3a226bvboxsync# define RTBIGNUM_ASSERT_VALID(a_pBigNum) do {} while (0)
400422edee24dcbb377417b13ed03412cc3a226bvboxsync/** Enable assembly optimizations. */
400422edee24dcbb377417b13ed03412cc3a226bvboxsync/** @def RTBIGNUM_ZERO_ALIGN
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * For calculating the rtBigNumEnsureExtraZeroElements argument from cUsed.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * This has to do with 64-bit assembly instruction operating as RTBIGNUMELEMENT
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * was 64-bit on some hosts.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync#if defined(IPRT_BIGINT_WITH_ASM) && ARCH_BITS == 64 && RTBIGNUM_ELEMENT_SIZE == 4 && defined(RT_LITTLE_ENDIAN)
400422edee24dcbb377417b13ed03412cc3a226bvboxsync# define RTBIGNUM_ZERO_ALIGN(a_cUsed) RT_ALIGN_32(a_cUsed, 2)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync#define RTBIGNUMELEMENT_HALF_MASK ( ((RTBIGNUMELEMENT)1 << (RTBIGNUM_ELEMENT_BITS / 2)) - (RTBIGNUMELEMENT)1)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync#define RTBIGNUMELEMENT_LO_HALF(a_uElement) ( (RTBIGNUMELEMENT_HALF_MASK) & (a_uElement) )
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync#define RTBIGNUMELEMENT_HI_HALF(a_uElement) ( (a_uElement) >> (RTBIGNUM_ELEMENT_BITS / 2) )
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync/*******************************************************************************
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync* Structures and Typedefs *
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync*******************************************************************************/
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync/** Type the size of two elements. */
400422edee24dcbb377417b13ed03412cc3a226bvboxsync/*******************************************************************************
400422edee24dcbb377417b13ed03412cc3a226bvboxsync* Internal Functions *
400422edee24dcbb377417b13ed03412cc3a226bvboxsync*******************************************************************************/
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLINLINE(int) rtBigNumSetUsed(PRTBIGNUM pBigNum, uint32_t cNewUsed);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync/* bignum-amd64-x86.asm: */
400422edee24dcbb377417b13ed03412cc3a226bvboxsyncDECLASM(void) rtBigNumMagnitudeSubAssemblyWorker(RTBIGNUMELEMENT *pauResult, RTBIGNUMELEMENT const *pauMinuend,
400422edee24dcbb377417b13ed03412cc3a226bvboxsync RTBIGNUMELEMENT const *pauSubtrahend, uint32_t cUsed);
400422edee24dcbb377417b13ed03412cc3a226bvboxsyncDECLASM(void) rtBigNumMagnitudeSubThisAssemblyWorker(RTBIGNUMELEMENT *pauMinuendResult, RTBIGNUMELEMENT const *pauSubtrahend,
400422edee24dcbb377417b13ed03412cc3a226bvboxsyncDECLASM(RTBIGNUMELEMENT) rtBigNumMagnitudeShiftLeftOneAssemblyWorker(RTBIGNUMELEMENT *pauElements, uint32_t cUsed,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLASM(void) rtBigNumElement2xDiv2xBy1x(RTBIGNUMELEMENT2X *puQuotient, RTBIGNUMELEMENT *puRemainder,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT uDividendHi, RTBIGNUMELEMENT uDividendLo, RTBIGNUMELEMENT uDivisor);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLASM(void) rtBigNumMagnitudeMultiplyAssemblyWorker(PRTBIGNUMELEMENT pauResult,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync PCRTBIGNUMELEMENT pauMultiplier, uint32_t cMultiplier,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync PCRTBIGNUMELEMENT pauMultiplicand, uint32_t cMultiplicand);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync/** @name Functions working on one element.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLINLINE(uint32_t) rtBigNumElementBitCount(RTBIGNUMELEMENT uElement)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync return ASMBitLastSetU32((uint32_t)(uElement >> 32)) + 32;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Does addition with carry.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * This is a candidate for inline assembly on some platforms.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @returns The result (the sum)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uAugend What to add to.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uAddend What to add to it.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pfCarry Where to read the input carry and return the output
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLINLINE(RTBIGNUMELEMENT) rtBigNumElementAddWithCarry(RTBIGNUMELEMENT uAugend, RTBIGNUMELEMENT uAddend,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Does addition with borrow.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * This is a candidate for inline assembly on some platforms.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @returns The result (the sum)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uMinuend What to subtract from.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uSubtrahend What to subtract.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pfBorrow Where to read the input borrow and return the output
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLINLINE(RTBIGNUMELEMENT) rtBigNumElementSubWithBorrow(RTBIGNUMELEMENT uMinuend, RTBIGNUMELEMENT uSubtrahend,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT uRet = uMinuend - uSubtrahend - *pfBorrow;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync /* Figure out if we borrowed. */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync *pfBorrow = !*pfBorrow ? uMinuend < uSubtrahend : uMinuend <= uSubtrahend;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync/** @name Double element primitives.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncstatic int rtBigNumElement2xCopyToMagnitude(RTBIGNUMELEMENT2X const *pValue2x, PRTBIGNUM pDst)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncstatic void rtBigNumElement2xDiv(RTBIGNUMELEMENT2X *puQuotient, RTBIGNUMELEMENT2X *puRemainder,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT uDividendHi, RTBIGNUMELEMENT uDividendLo,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT uDivisorHi, RTBIGNUMELEMENT uDivisorLo)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTUInt128DivRem(puQuotient, puRemainder, &uDividend, &uDivisor);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncstatic void rtBigNumElement2xDiv2xBy1x(RTBIGNUMELEMENT2X *puQuotient, RTBIGNUMELEMENT *puRemainder,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT uDividendHi, RTBIGNUMELEMENT uDividendLo, RTBIGNUMELEMENT uDivisor)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync /** @todo optimize this. */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTUInt128DivRem(puQuotient, &uRemainder2x, &uDividend, &uDivisor2x);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLINLINE(void) rtBigNumElement2xDec(RTBIGNUMELEMENT2X *puValue)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLINLINE(void) rtBigNumElement2xAdd1x(RTBIGNUMELEMENT2X *puValue, RTBIGNUMELEMENT uAdd)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Scrambles a big number if required.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(void) rtBigNumScramble(PRTBIGNUM pBigNum)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync int rc = RTMemSaferScramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Unscrambles a big number if required.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(int) rtBigNumUnscramble(PRTBIGNUM pBigNum)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(pBigNum->fCurScrambled, VERR_INTERNAL_ERROR_2);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync int rc = RTMemSaferUnscramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Getter function for pauElements which extends the array to infinity.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns The element value.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param iElement The element index.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(RTBIGNUMELEMENT) rtBigNumGetElement(PCRTBIGNUM pBigNum, uint32_t iElement)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Grows the pauElements array so it can fit at least @a cNewUsed entries.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param cNewUsed The new cUsed value.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @param cMinElements The minimum number of elements.
400422edee24dcbb377417b13ed03412cc3a226bvboxsyncstatic int rtBigNumGrow(PRTBIGNUM pBigNum, uint32_t cNewUsed, uint32_t cMinElements)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uint32_t const cbOld = pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE;
400422edee24dcbb377417b13ed03412cc3a226bvboxsync uint32_t const cNew = RT_ALIGN_32(cMinElements, RTBIGNUM_ALIGNMENT);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uint32_t const cbNew = cNew * RTBIGNUM_ELEMENT_SIZE;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync pvNew = RTMemSaferReallocZ(cbOld, pBigNum->pauElements, cbNew);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RT_BZERO((RTBIGNUMELEMENT *)pvNew + cNewUsed, (pBigNum->cUsed - cNewUsed) * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Changes the cUsed member, growing the pauElements array if necessary.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * Any elements added to the array will be initialized to zero.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param cNewUsed The new cUsed value.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(int) rtBigNumSetUsed(PRTBIGNUM pBigNum, uint32_t cNewUsed)
400422edee24dcbb377417b13ed03412cc3a226bvboxsync RT_BZERO(&pBigNum->pauElements[cNewUsed], (pBigNum->cUsed - cNewUsed) * RTBIGNUM_ELEMENT_SIZE);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync Assert(ASMMemIsAllU32(&pBigNum->pauElements[pBigNum->cUsed],
400422edee24dcbb377417b13ed03412cc3a226bvboxsync (cNewUsed - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE, 0) == NULL);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * Extended version of rtBigNumSetUsed that also allow specifying the number of
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * zero elements required.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @returns IPRT status code.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @param pBigNum The big number.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @param cNewUsed The new cUsed value.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @param cMinElements The minimum number of elements allocated. The
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * difference between @a cNewUsed and @a cMinElements
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * is initialized to zero because all free elements are
400422edee24dcbb377417b13ed03412cc3a226bvboxsyncDECLINLINE(int) rtBigNumSetUsedEx(PRTBIGNUM pBigNum, uint32_t cNewUsed, uint32_t cMinElements)
400422edee24dcbb377417b13ed03412cc3a226bvboxsync RT_BZERO(&pBigNum->pauElements[cNewUsed], (pBigNum->cUsed - cNewUsed) * RTBIGNUM_ELEMENT_SIZE);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync Assert(ASMMemIsAllU32(&pBigNum->pauElements[pBigNum->cUsed],
400422edee24dcbb377417b13ed03412cc3a226bvboxsync (cNewUsed - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE, 0) == NULL);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync return rtBigNumGrow(pBigNum, cNewUsed, cMinElements);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * For ensuring zero padding of pauElements for sub/add with carry assembly
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * operations.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @returns IPRT status code.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @param pBigNum The big number.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @param cElements The number of elements that must be in the elements
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * array array, where those after pBigNum->cUsed must
400422edee24dcbb377417b13ed03412cc3a226bvboxsyncDECLINLINE(int) rtBigNumEnsureExtraZeroElements(PRTBIGNUM pBigNum, uint32_t cElements)
400422edee24dcbb377417b13ed03412cc3a226bvboxsync || ASMMemIsAllU32(&pBigNum->pauElements[pBigNum->cUsed],
400422edee24dcbb377417b13ed03412cc3a226bvboxsync (pBigNum->cAllocated - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE, 0) == NULL);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync return rtBigNumGrow(pBigNum, pBigNum->cUsed, cElements);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The slow part of rtBigNumEnsureElementPresent where we need to do actual zero
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * extending.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param iElement The element we wish to access.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic int rtBigNumEnsureElementPresentSlow(PRTBIGNUM pBigNum, uint32_t iElement)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync RT_BZERO(&pBigNum->pauElements[cOldUsed], (iElement + 1 - cOldUsed) * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Zero extends the element array to make sure a the specified element index is
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * accessible.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * This is typically used with bit operations and self modifying methods. Any
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * new elements added will be initialized to zero. The caller is responsible
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * for there not being any trailing zero elements.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The number must be unscrambled.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param iElement The element we wish to access.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(int) rtBigNumEnsureElementPresent(PRTBIGNUM pBigNum, uint32_t iElement)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync return rtBigNumEnsureElementPresentSlow(pBigNum, iElement);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Strips zero elements from the magnitude value.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number to strip.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic void rtBigNumStripTrailingZeros(PRTBIGNUM pBigNum)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Initialize the big number to zero.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns @a pBigNum
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param fFlags The flags.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @internal
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(PRTBIGNUM) rtBigNumInitZeroInternal(PRTBIGNUM pBigNum, uint32_t fFlags)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->fSensitive = RT_BOOL(fFlags & RTBIGNUMINIT_F_SENSITIVE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Initialize the big number to zero from a template variable.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns @a pBigNum
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pTemplate The template big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @internal
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(PRTBIGNUM) rtBigNumInitZeroTemplate(PRTBIGNUM pBigNum, PCRTBIGNUM pTemplate)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumInit(PRTBIGNUM pBigNum, uint32_t fFlags, void const *pvRaw, size_t cbRaw)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Validate input.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_BIG) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE),
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_UNSIGNED) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_SIGNED), VERR_INVALID_PARAMETER);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Initalize the big number to zero.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Strip the input and figure the sign flag.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Allocate memory for the elements.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync size_t cbAligned = RT_ALIGN_Z(cbRaw, RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->cUsed = (uint32_t)cbAligned / RTBIGNUM_ELEMENT_SIZE;
400422edee24dcbb377417b13ed03412cc3a226bvboxsync pBigNum->cAllocated = RT_ALIGN_32(pBigNum->cUsed, RTBIGNUM_ALIGNMENT);
bcb3083f42e955d186649946e002930e75134f8dvboxsync pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemSaferAllocZ(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemAlloc(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Initialize the array.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[0], pb[1], pb[2], pb[3], pb[4], pb[5], pb[6], pb[7]);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->pauElements[i] = RT_MAKE_U32_FROM_U8(pb[0], pb[1], pb[2], pb[3]);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync RTBIGNUMELEMENT uLast = pBigNum->fNegative ? ~(RTBIGNUMELEMENT)0 : 0;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[7], pb[6], pb[5], pb[4], pb[3], pb[2], pb[1], pb[0]);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->pauElements[i] = RT_MAKE_U32_FROM_U8(pb[3], pb[2], pb[1], pb[0]);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync RTBIGNUMELEMENT uLast = pBigNum->fNegative ? ~(RTBIGNUMELEMENT)0 : 0;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * If negative, negate it so we get a positive magnitude value in pauElements.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->pauElements[0] = 0U - pBigNum->pauElements[0];
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->pauElements[i] = 0U - pBigNum->pauElements[i] - 1U;
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * Clear unused elements.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync RTBIGNUMELEMENT *puUnused = &pBigNum->pauElements[pBigNum->cUsed];
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumInitZero(PRTBIGNUM pBigNum, uint32_t fFlags)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(!(fFlags & ~RTBIGNUMINIT_F_SENSITIVE), VERR_INVALID_PARAMETER);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Internal clone function that assumes the caller takes care of scrambling.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The target number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pSrc The source number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic int rtBigNumCloneInternal(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Copy over the data.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Duplicate the element array. */
400422edee24dcbb377417b13ed03412cc3a226bvboxsync pBigNum->cAllocated = RT_ALIGN_32(pBigNum->cUsed, RTBIGNUM_ALIGNMENT);
bcb3083f42e955d186649946e002930e75134f8dvboxsync pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemSaferAllocZ(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemAlloc(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync memcpy(pBigNum->pauElements, pSrc->pauElements, pBigNum->cUsed * RTBIGNUM_ELEMENT_SIZE);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync RT_BZERO(&pBigNum->pauElements[pBigNum->cUsed], (pBigNum->cAllocated - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumClone(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync RTMemSaferFree(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumAssign(PRTBIGNUM pDst, PCRTBIGNUM pSrc)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(pDst->fSensitive >= pSrc->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync RT_BZERO(&pDst->pauElements[pSrc->cUsed], (pDst->cUsed - pSrc->cUsed) * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Same as RTBigNumBitWidth, except that it ignore the signed bit.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The number must be unscrambled.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns The effective width of the magnitude, in bits. Returns 0 if the
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * value is zero.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The bit number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic uint32_t rtBigNumMagnitudeBitWidth(PCRTBIGNUM pBigNum)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync RTBIGNUMELEMENT uLast = pBigNum->pauElements[idxLast]; Assert(uLast);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync return rtBigNumElementBitCount(uLast) + idxLast * RTBIGNUM_ELEMENT_BITS;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(uint32_t) RTBigNumBitWidth(PCRTBIGNUM pBigNum)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync RTBIGNUMELEMENT uLast = pBigNum->pauElements[idxLast]; Assert(uLast);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync return rtBigNumElementBitCount(uLast) + idxLast * RTBIGNUM_ELEMENT_BITS + pBigNum->fNegative;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(uint32_t) RTBigNumByteWidth(PCRTBIGNUM pBigNum)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumToBytesBigEndian(PCRTBIGNUM pBigNum, void *pvBuf, size_t cbWanted)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(cbWanted > 0, VERR_INVALID_PARAMETER);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync RTBIGNUMELEMENT uElement = pBigNum->pauElements[i];
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uElement = (RTBIGNUMELEMENT)0 - uElement - (i > 0);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(cBitsLeft > 0); Assert(cBitsLeft < RTBIGNUM_ELEMENT_BITS);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync : uElement != ((RTBIGNUMELEMENT)1 << cBitsLeft) - 1U ) )
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Sign extend the number to the desired output size. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync memset(pbDst - cbWanted, pBigNum->fNegative ? 0 : 0xff, cbWanted);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumCompare(PRTBIGNUM pLeft, PRTBIGNUM pRight)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync while (i-- > 0)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync if (pLeft->pauElements[i] != pRight->pauElements[i])
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = pLeft->pauElements[i] < pRight->pauElements[i] ? -1 : 1;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumCompareWithU64(PRTBIGNUM pLeft, uint64_t uRight)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync if (pLeft->cUsed * RTBIGNUM_ELEMENT_SIZE <= sizeof(uRight))
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumCompareWithS64(PRTBIGNUM pLeft, int64_t iRight)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync AssertCompile(RTBIGNUM_ELEMENT_SIZE <= sizeof(iRight));
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync if (pLeft->cUsed * RTBIGNUM_ELEMENT_SIZE <= sizeof(iRight))
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uint64_t uRightMagn = !pLeft->fNegative ? (uint64_t)iRight : (uint64_t)-iRight;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Compares the magnitude values of two big numbers.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @retval -1 if pLeft is smaller than pRight.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @retval 0 if pLeft is equal to pRight.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @retval 1 if pLeft is larger than pRight.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pLeft The left side number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pRight The right side number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic int rtBigNumMagnitudeCompare(PCRTBIGNUM pLeft, PCRTBIGNUM pRight)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(!pLeft->fCurScrambled); Assert(!pRight->fCurScrambled);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync while (i-- > 0)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync if (pLeft->pauElements[i] != pRight->pauElements[i])
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = pLeft->pauElements[i] < pRight->pauElements[i] ? -1 : 1;
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * Copies the magnitude of on number (@a pSrc) to another (@a pBigNum).
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * The variables must be unscrambled. The sign flag is not considered nor
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @returns IPRT status code.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @param pDst The destination number.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @param pSrc The source number.
400422edee24dcbb377417b13ed03412cc3a226bvboxsyncDECLINLINE(int) rtBigNumMagnitudeCopy(PRTBIGNUM pDst, PCRTBIGNUM pSrc)
400422edee24dcbb377417b13ed03412cc3a226bvboxsync memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Adds two magnitudes and stores them into a third.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * All variables must be unscrambled. The sign flag is not considered nor
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pResult The resultant.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pAugend To whom it shall be addede.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pAddend The nombre to addede.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic int rtBigNumMagnitudeAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(!pResult->fCurScrambled); Assert(!pAugend->fCurScrambled); Assert(!pAddend->fCurScrambled);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult != pAugend); Assert(pResult != pAddend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uint32_t cElements = RT_MAX(pAugend->cUsed, pAddend->cUsed);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The primitive way, requires at least two additions for each entry
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * without machine code help.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pResult->pauElements[i] = rtBigNumElementAddWithCarry(rtBigNumGetElement(pAugend, i),
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult->cUsed == cElements || RT_FAILURE_NP(rc));
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Substracts a smaller (or equal) magnitude from another one and stores it into
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * All variables must be unscrambled. The sign flag is not considered nor
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * touched. For this reason, the @a pMinuend must be larger or equal to @a
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * pSubtrahend.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pResult There to store the result.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pMinuend What to subtract from.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pSubtrahend What to subtract.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic int rtBigNumMagnitudeSub(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(!pResult->fCurScrambled); Assert(!pMinuend->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult != pMinuend); Assert(pResult != pSubtrahend);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * Resize the result. In the assembly case, ensure that all three arrays
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * has the same number of used entries, possibly with an extra zero
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * element on 64-bit systems.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync rc = rtBigNumSetUsedEx(pResult, pMinuend->cUsed, RTBIGNUM_ZERO_ALIGN(pMinuend->cUsed));
400422edee24dcbb377417b13ed03412cc3a226bvboxsync rc = rtBigNumEnsureExtraZeroElements((PRTBIGNUM)pMinuend, RTBIGNUM_ZERO_ALIGN(pMinuend->cUsed));
400422edee24dcbb377417b13ed03412cc3a226bvboxsync rc = rtBigNumEnsureExtraZeroElements((PRTBIGNUM)pSubtrahend, RTBIGNUM_ZERO_ALIGN(pMinuend->cUsed));
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * Call assembly to do the work.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync rtBigNumMagnitudeSubAssemblyWorker(pResult->pauElements, pMinuend->pauElements,
400422edee24dcbb377417b13ed03412cc3a226bvboxsync RTBIGNUMELEMENT uCorrect = rtBigNumElementSubWithBorrow(pMinuend->pauElements[i], rtBigNumGetElement(pSubtrahend, i), &fBorrow);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync AssertMsg(pResult->pauElements[i] == uCorrect, ("[%u]=%#x, expected %#x\n", i, pResult->pauElements[i], uCorrect));
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * The primitive C way.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync pResult->pauElements[i] = rtBigNumElementSubWithBorrow(pMinuend->pauElements[i],
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * Trim the result.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * Special case: Subtrahend is zero.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Substracts a smaller (or equal) magnitude from another one and stores the
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * result into the first.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * All variables must be unscrambled. The sign flag is not considered nor
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * touched. For this reason, the @a pMinuendResult must be larger or equal to
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @a pSubtrahend.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * @returns IPRT status code (memory alloc error).
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pMinuendResult What to subtract from and return as result.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pSubtrahend What to subtract.
400422edee24dcbb377417b13ed03412cc3a226bvboxsyncstatic int rtBigNumMagnitudeSubThis(PRTBIGNUM pMinuendResult, PCRTBIGNUM pSubtrahend)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(!pMinuendResult->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pMinuendResult->cUsed >= pSubtrahend->cUsed);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync * Use the assembly worker. Requires same sized element arrays, so zero extend them.
400422edee24dcbb377417b13ed03412cc3a226bvboxsync int rc = rtBigNumEnsureExtraZeroElements(pMinuendResult, RTBIGNUM_ZERO_ALIGN(pMinuendResult->cUsed));
400422edee24dcbb377417b13ed03412cc3a226bvboxsync rc = rtBigNumEnsureExtraZeroElements((PRTBIGNUM)pSubtrahend, RTBIGNUM_ZERO_ALIGN(pMinuendResult->cUsed));
400422edee24dcbb377417b13ed03412cc3a226bvboxsync rtBigNumMagnitudeSubThisAssemblyWorker(pMinuendResult->pauElements, pSubtrahend->pauElements, pMinuendResult->cUsed);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The primitive way, as usual.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync for (uint32_t i = 0; i < pMinuendResult->cUsed; i++)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pMinuendResult->pauElements[i] = rtBigNumElementSubWithBorrow(pMinuendResult->pauElements[i],
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Trim the result.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult != pAugend); Assert(pResult != pAddend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(pResult->fSensitive >= (pAugend->fSensitive | pAddend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Same sign: Add magnitude, keep sign.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * 1 + 1 = 2
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * (-1) + (-1) = -2
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeAdd(pResult, pAugend, pAddend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Different sign: Subtract smaller from larger, keep sign of larger.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * (-5) + 3 = -2
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * 5 + (-3) = 2
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * (-1) + 3 = 2
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * 1 + (-3) = -2
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync else if (rtBigNumMagnitudeCompare(pAugend, pAddend) >= 0)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeSub(pResult, pAugend, pAddend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeSub(pResult, pAddend, pAugend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumSubtract(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult != pMinuend); Assert(pResult != pSubtrahend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(pResult->fSensitive >= (pMinuend->fSensitive | pSubtrahend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Different sign: Add magnitude, keep sign of first.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * 1 - (-2) == 3
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * -1 - 2 == -3
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeAdd(pResult, pMinuend, pSubtrahend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Same sign, minuend has greater or equal absolute value: Subtract, keep sign of first.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * 10 - 7 = 3
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync else if (rtBigNumMagnitudeCompare(pMinuend, pSubtrahend) >= 0)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeSub(pResult, pMinuend, pSubtrahend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Same sign, subtrahend is larger: Reverse and subtract, invert sign of first.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * 7 - 10 = -3
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * -1 - (-3) = 2
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeSub(pResult, pSubtrahend, pMinuend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* zero. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumNegate(PRTBIGNUM pResult, PCRTBIGNUM pBigNum)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Multiplies the magnitudes of two values, letting the caller care about the
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * sign bit.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pResult Where to store the result.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pMultiplicand The first value.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pMultiplier The second value.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic int rtBigNumMagnitudeMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult != pMultiplicand); Assert(pResult != pMultiplier);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(!pResult->fCurScrambled); Assert(!pMultiplicand->fCurScrambled); Assert(!pMultiplier->fCurScrambled);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Multiplication involving zero is zero.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Allocate a result array that is the sum of the two factors, initialize
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * it to zero.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uint32_t cMax = pMultiplicand->cUsed + pMultiplier->cUsed;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync RT_BZERO(pResult->pauElements, pResult->cUsed * RTBIGNUM_ELEMENT_SIZE);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rtBigNumMagnitudeMultiplyAssemblyWorker(pResult->pauElements,
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync RTBIGNUMELEMENT uMultiplier = pMultiplier->pauElements[i];
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync for (uint32_t j = 0; j < pMultiplicand->cUsed; j++)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uint64_t u64 = ASMMult2xU32RetU64(pMultiplicand->pauElements[j], uMultiplier);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uLo = ASMMult2xU64Ret2xU64(pMultiplicand->pauElements[j], uMultiplier, &uHi);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], uLo, &fCarry);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], uHi, &fCarry);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], 0, &fCarry);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* It's possible we overestimated the output size by 1 element. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult != pMultiplicand); Assert(pResult != pMultiplier);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(pResult->fSensitive >= (pMultiplicand->fSensitive | pMultiplier->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The sign values follow XOR rules:
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * -1 * 1 = -1; 1 ^ 0 = 1
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * 1 * -1 = -1; 1 ^ 0 = 1
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * -1 * -1 = 1; 1 ^ 1 = 0
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * 1 * 1 = 1; 0 ^ 0 = 0
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pResult->fNegative = pMultiplicand->fNegative ^ pMultiplier->fNegative;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeMultiply(pResult, pMultiplicand, pMultiplier);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Clears a bit in the magnitude of @a pBigNum.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The variables must be unscrambled.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param iBit The bit to clear (0-based).
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(void) rtBigNumMagnitudeClearBit(PRTBIGNUM pBigNum, uint32_t iBit)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->pauElements[iElement] &= ~RTBIGNUM_ELEMENT_BIT(iBit);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync if (iElement + 1 == pBigNum->cUsed && !pBigNum->pauElements[iElement])
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Sets a bit in the magnitude of @a pBigNum.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The variables must be unscrambled.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param iBit The bit to clear (0-based).
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(int) rtBigNumMagnitudeSetBit(PRTBIGNUM pBigNum, uint32_t iBit)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync int rc = rtBigNumEnsureElementPresent(pBigNum, iElement);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pBigNum->pauElements[iElement] |= RTBIGNUM_ELEMENT_BIT(iBit);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Writes a bit in the magnitude of @a pBigNum.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The variables must be unscrambled.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param iBit The bit to write (0-based).
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param fValue The bit value.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(int) rtBigNumMagnitudeWriteBit(PRTBIGNUM pBigNum, uint32_t iBit, bool fValue)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Returns the given magnitude bit.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The variables must be unscrambled.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns The bit value (1 or 0).
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param iBit The bit to return (0-based).
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(RTBIGNUMELEMENT) rtBigNumMagnitudeGetBit(PCRTBIGNUM pBigNum, uint32_t iBit)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync return (pBigNum->pauElements[iElement] >> iBit) & 1;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Shifts the magnitude left by one.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The variables must be unscrambled.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBigNum The big number.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param uCarry The value to shift in at the bottom.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncDECLINLINE(int) rtBigNumMagnitudeShiftLeftOne(PRTBIGNUM pBigNum, RTBIGNUMELEMENT uCarry)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Do the shifting. */
400422edee24dcbb377417b13ed03412cc3a226bvboxsync uCarry = rtBigNumMagnitudeShiftLeftOneAssemblyWorker(pBigNum->pauElements, cUsed, uCarry);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* If we still carry a bit, we need to increase the size. */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Shifts the magnitude left by @a cBits.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * The variables must be unscrambled.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pResult Where to store the result.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pValue The value to shift.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param cBits The shift count.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncstatic int rtBigNumMagnitudeShiftLeft(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync uint32_t cBitsNew = rtBigNumMagnitudeBitWidth(pValue);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumSetUsedEx(pResult, 0, RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumSetUsed(pResult, RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync Assert(ASMMemIsAllU32(pauDst, (cBits / RTBIGNUM_ELEMENT_BITS) * RTBIGNUM_ELEMENT_SIZE, 0) == NULL);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync pauDst[i] = (uCur << cBits) | (uPrev >> (RTBIGNUM_ELEMENT_BITS - cBits));
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync memcpy(pauDst, pauSrc, cLeft * RTBIGNUM_ELEMENT_SIZE);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync /* Shifting zero always yields a zero result. */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncRTDECL(int) RTBigNumShiftLeft(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync AssertReturn(pResult->fSensitive >= pValue->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeShiftLeft(pResult, pValue, cBits);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Shifts the magnitude right by @a cBits.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * The variables must be unscrambled.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @returns IPRT status code.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pResult Where to store the result.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pValue The value to shift.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param cBits The shift count.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncstatic int rtBigNumMagnitudeShiftRight(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync uint32_t cBitsNew = rtBigNumMagnitudeBitWidth(pValue);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync uint32_t cElementsNew = RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT uPrev = &pauSrc[i] == &pValue->pauElements[pValue->cUsed] ? 0 : pauSrc[i];
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync while (i-- > 0)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync pauDst[i] = (uCur >> cBits) | (uPrev << (RTBIGNUM_ELEMENT_BITS - cBits));
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncRTDECL(int) RTBigNumShiftRight(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync AssertReturn(pResult->fSensitive >= pValue->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeShiftRight(pResult, pValue, cBits);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Implements the D3 test for Qhat decrementation.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @returns True if Qhat should be decremented.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param puQhat Pointer to Qhat.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uRhat The remainder.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uDivisorY The penultimate divisor element.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uDividendJMinus2 The j-2 dividend element.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLINLINE(bool) rtBigNumKnuthD3_ShouldDecrementQhat(RTBIGNUMELEMENT2X const *puQhat, RTBIGNUMELEMENT uRhat,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT uDivisorY, RTBIGNUMELEMENT uDividendJMinus2)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync if (puQhat->s.Lo == RTBIGNUM_ELEMENT_MAX && puQhat->s.Hi == 0)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync return true;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTUInt128AssignAddU64(&TmpRight, uDividendJMinus2);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync return true;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync if (puQhat->u * uDivisorY > ((uint64_t)uRhat << 32) + uDividendJMinus2)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync return true;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync return false;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * C implementation of the D3 step of Knuth's division algorithm.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * This estimates a value Qhat that will be used as quotient "digit" (element)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * at the current level of the division (j).
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @returns The Qhat value we've estimated.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pauDividendJN Pointer to the j+n (normalized) dividend element.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Will access up to two elements prior to this.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uDivZ The last element in the (normalized) divisor.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uDivY The penultimate element in the (normalized) divisor.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLINLINE(RTBIGNUMELEMENT) rtBigNumKnuthD3_EstimateQhat(PCRTBIGNUMELEMENT pauDividendJN,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rtBigNumElement2xDiv2xBy1x(&uQhat, &uRhat, uDividendJN, pauDividendJN[-1], uDivZ);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * This is the case where we end up with an initial Qhat that's all Fs.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync /* Calc the remainder for max Qhat value. */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT2X uTmp1; /* (v[j+n] << bits) + v[J+N-1] */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync /* If we overflowed the remainder, don't bother trying to adjust. */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Adjust Q to eliminate all cases where it's two to large and most cases
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * where it's one too large.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync while (rtBigNumKnuthD3_ShouldDecrementQhat(&uQhat, uRhat, uDivY, pauDividendJN[-2]))
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync if (uRhat < uDivZ /* overflow */ || uRhat == RTBIGNUM_ELEMENT_MAX)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLASM(bool) rtBigNumKnuthD4_MulSub(PRTBIGNUMELEMENT pauDividendJ, PRTBIGNUMELEMENT pauDivisor,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * C implementation of the D4 step of Knuth's division algorithm.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * This subtracts Divisor * Qhat from the dividend at the current J index.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @returns true if negative result (unlikely), false if positive.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pauDividendJ Pointer to the j-th (normalized) dividend element.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Will access up to two elements prior to this.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uDivZ The last element in the (normalized) divisor.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uDivY The penultimate element in the (normalized) divisor.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLINLINE(bool) rtBigNumKnuthD4_MulSub(PRTBIGNUMELEMENT pauDividendJ, PRTBIGNUMELEMENT pauDivisor,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync bool fBorrow = false;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync for (i = 0; i < cDivisor; i++)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync uSub.u = (uint64_t)uQhat * pauDivisor[i] + uMulCarry;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync /* Carry and borrow into the final dividend element. */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync#endif /* !IPRT_BIGINT_WITH_ASM */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * C implementation of the D6 step of Knuth's division algorithm.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * This adds the divisor to the dividend to undo the negative value step D4
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * produced. This is not very frequent occurence.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pauDividendJ Pointer to the j-th (normalized) dividend element.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Will access up to two elements prior to this.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uDivZ The last element in the (normalized) divisor.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param uDivY The penultimate element in the (normalized) divisor.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncDECLINLINE(void) rtBigNumKnuthD6_AddBack(PRTBIGNUMELEMENT pauDividendJ, PRTBIGNUMELEMENT pauDivisor, uint32_t cDivisor)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync for (i = 0; i < cDivisor; i++)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync /* The final dividend entry. */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Knuth's division (core).
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @returns IPRT status code.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pQuotient Where to return the quotient. Can be NULL.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pRemainder Where to return the remainder.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pDividend What to divide.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pDivisor What to divide by.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncstatic int rtBigNumMagnitudeDivideKnuth(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Make sure we've got enough space in the quotient, so we can build it
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * without any trouble come step D5.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumSetUsedEx(pQuotient, 0, pDividend->cUsed - cDivisor + 1);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumSetUsed(pQuotient, pDividend->cUsed - cDivisor + 1);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * D1. Normalize. The goal here is to make sure the last element in the
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * divisor is greater than RTBIGNUMELEMENTS_MAX/2. We must also make sure
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * we can access element pDividend->cUsed of the normalized dividend.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync uint32_t cNormShift = (RTBIGNUM_ELEMENT_BITS - rtBigNumMagnitudeBitWidth(pDivisor)) & (RTBIGNUM_ELEMENT_BITS - 1);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rtBigNumInitZeroTemplate(&NormDividend, pDividend);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeShiftLeft(&NormDividend, pDividend, cNormShift);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeShiftLeft(&NormDivisor, pDivisor, cNormShift);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumCloneInternal(&NormDividend, pDividend);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync if (RT_SUCCESS(rc) && pDividend->cUsed == NormDividend.cUsed)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumEnsureExtraZeroElements(&NormDividend, NormDividend.cUsed + 1);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * D2. Initialize the j index so we can loop thru the elements in the
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * dividend that makes it larger than the divisor.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT const DivZ = pNormDivisor->pauElements[cDivisor - 1];
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT const DivY = pNormDivisor->pauElements[cDivisor - 2];
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * D3. Estimate a Q' by dividing the j and j-1 dividen elements by
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * the last divisor element, then adjust against the next elements.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT uQhat = rtBigNumKnuthD3_EstimateQhat(&NormDividend.pauElements[j + cDivisor], DivZ, DivY);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * D4. Multiply and subtract.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync bool fNegative = rtBigNumKnuthD4_MulSub(&NormDividend.pauElements[j], pNormDivisor->pauElements, cDivisor, uQhat);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * D5. Test remainder.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * D6. Add back.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync//__debugbreak();
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rtBigNumKnuthD6_AddBack(&NormDividend.pauElements[j], pNormDivisor->pauElements, cDivisor);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * D7. Loop on j.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync if (j == 0)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * D8. Unnormalize the remainder.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeShiftRight(pRemainder, &NormDividend, cNormShift);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeCopy(pRemainder, &NormDividend);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Delete temporary variables.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncstatic int rtBigNumMagnitudeDivideSlowLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Do very simple long division. This ain't fast, but it does the trick.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uint32_t iBit = rtBigNumMagnitudeBitWidth(pDividend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync while (iBit-- > 0)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeShiftLeftOne(pRemainder, rtBigNumMagnitudeGetBit(pDividend, iBit));
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync int iDiff = rtBigNumMagnitudeCompare(pRemainder, pDivisor);
400422edee24dcbb377417b13ed03412cc3a226bvboxsync rc = rtBigNumMagnitudeSubThis(pRemainder, pDivisor);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* This shouldn't be necessary. */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Divides the magnitudes of two values, letting the caller care about the sign
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * All variables must be unscrambled. The sign flag is not considered nor
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * touched, this means the caller have to check for zero outputs.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @returns IPRT status code.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pQuotient Where to return the quotient.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pRemainder Where to return the remainder.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pDividend What to divide.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pDivisor What to divide by.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param fForceLong Force long division.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncstatic int rtBigNumMagnitudeDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync Assert(!pQuotient->fCurScrambled); Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Just set both output values to zero as that's the return for several
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * special case and the initial state of the general case.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Dividing something by zero is undefined.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Diving zero by something is zero, unless the divsor is also zero.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync return pDivisor->cUsed ? VINF_SUCCESS : VERR_BIGNUM_DIV_BY_ZERO;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Dividing by one? Quotient = dividend, no remainder.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync if (pDivisor->cUsed == 1 && pDivisor->pauElements[0] == 1)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync return rtBigNumMagnitudeCopy(pQuotient, pDividend);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Dividend smaller than the divisor. Zero quotient, all divisor.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync int iDiff = rtBigNumMagnitudeCompare(pDividend, pDivisor);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync return rtBigNumMagnitudeCopy(pRemainder, pDividend);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Since we already have done the compare, check if the two values are the
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * same. The result is 1 and no remainder then.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Sort out special cases before going to the preferred or select algorithm.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Single element division.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT uQ = pDividend->pauElements[0] / pDivisor->pauElements[0];
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync RTBIGNUMELEMENT uR = pDividend->pauElements[0] % pDivisor->pauElements[0];
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Two elements dividend by a one or two element divisor.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rtBigNumElement2xDiv2xBy1x(&uQ, &uR.s.Lo, pDividend->pauElements[1], pDividend->pauElements[0],
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rtBigNumElement2xDiv(&uQ, &uR, pDividend->pauElements[1], pDividend->pauElements[0],
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync pDivisor->pauElements[1], pDivisor->pauElements[0]);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumElement2xCopyToMagnitude(&uQ, pQuotient);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumElement2xCopyToMagnitude(&uR, pRemainder);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Decide upon which algorithm to use. Knuth requires a divisor that's at
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * least 2 elements big.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeDivideSlowLong(pQuotient, pRemainder, pDividend, pDivisor);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeDivideKnuth(pQuotient, pRemainder, pDividend, pDivisor);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncstatic int rtBigNumDivideCommon(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder,
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor, bool fForceLong)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(pQuotient->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The sign value of the remainder is the same as the dividend.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The sign values of the quotient follow XOR rules, just like multiplication:
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * -3 / 2 = -1; r=-1; 1 ^ 0 = 1
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * 3 / -2 = -1; r= 1; 1 ^ 0 = 1
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * -3 / -2 = 1; r=-1; 1 ^ 1 = 0
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * 3 / 2 = 1; r= 1; 0 ^ 0 = 0
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pQuotient->fNegative = pDividend->fNegative ^ pDivisor->fNegative;
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeDivide(pQuotient, pRemainder, pDividend, pDivisor, fForceLong);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncRTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync return rtBigNumDivideCommon(pQuotient, pRemainder, pDividend, pDivisor, false /*fForceLong*/);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsyncRTDECL(int) RTBigNumDivideLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync return rtBigNumDivideCommon(pQuotient, pRemainder, pDividend, pDivisor, true /*fForceLong*/);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Calculates the modulus of a magnitude value, leaving the sign bit to the
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * All variables must be unscrambled. The sign flag is not considered nor
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * touched, this means the caller have to check for zero outputs.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * @param pRemainder Where to return the remainder.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pDividend What to divide.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pDivisor What to divide by.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic int rtBigNumMagnitudeModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Just set the output value to zero as that's the return for several
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * special case and the initial state of the general case.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Dividing something by zero is undefined.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Diving zero by something is zero, unless the divsor is also zero.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync return pDivisor->cUsed ? VINF_SUCCESS : VERR_BIGNUM_DIV_BY_ZERO;
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Dividing by one? Quotient = dividend, no remainder.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync if (pDivisor->cUsed == 1 && pDivisor->pauElements[0] == 1)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Dividend smaller than the divisor. Zero quotient, all divisor.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync int iDiff = rtBigNumMagnitudeCompare(pDividend, pDivisor);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync return rtBigNumMagnitudeCopy(pRemainder, pDividend);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Since we already have done the compare, check if the two values are the
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * same. The result is 1 and no remainder then.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync /** @todo optimize small numbers. */
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Do very simple long division. This ain't fast, but it does the trick.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync uint32_t iBit = rtBigNumMagnitudeBitWidth(pDividend);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync while (iBit-- > 0)
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeShiftLeftOne(pRemainder, rtBigNumMagnitudeGetBit(pDividend, iBit));
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync iDiff = rtBigNumMagnitudeCompare(pRemainder, pDivisor);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeSubThis(pRemainder, pDivisor);
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync * Join paths with division.
972c3ecf2c929440ce70e51af38ba021101c8f7bvboxsync rc = rtBigNumMagnitudeDivideKnuth(NULL, pRemainder, pDividend, pDivisor);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* This shouldn't be necessary. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
400422edee24dcbb377417b13ed03412cc3a226bvboxsync Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * The sign value of the remainder is the same as the dividend.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeModulo(pRemainder, pDividend, pDivisor);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Exponentiate the magnitude.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * All variables must be unscrambled. The sign flag is not considered nor
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * touched, this means the caller have to reject negative exponents.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pResult Where to return power.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBase The base value.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pExponent The exponent (assumed positive or zero).
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic int rtBigNumMagnitudeExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult != pBase); Assert(pResult != pExponent);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * A couple of special cases.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* base ^ 0 => 1. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* base ^ 1 => base. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync if (pExponent->cUsed == 1 && pExponent->pauElements[0] == 1)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Init temporary power-of-two variable to base. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Init result to 1. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Make a temporary variable that we can use for temporary storage of the result. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumCloneInternal(&TmpMultiplicand, pResult);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Exponentiation by squaring. Reduces the number of
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * multiplications to: NumBitsSet(Exponent) + BitWidth(Exponent).
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uint32_t const cExpBits = rtBigNumMagnitudeBitWidth(pExponent);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, pResult);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeMultiply(pResult, &TmpMultiplicand, &Pow2);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Done? */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Not done yet, square the base again. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, &Pow2);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeMultiply(&Pow2, &TmpMultiplicand, &TmpMultiplicand);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult != pBase); Assert(pResult != pExponent);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(pResult->fSensitive >= (pBase->fSensitive | pExponent->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pResult->fNegative = pBase->fNegative; /* sign unchanged. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeExponentiate(pResult, pBase, pExponent);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Modular exponentiation, magnitudes only.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * All variables must be unscrambled. The sign flag is not considered nor
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * touched, this means the caller have to reject negative exponents and do any
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * other necessary sign bit fiddling.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @returns IPRT status code.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pResult Where to return the remainder of the power.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pBase The base value.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pExponent The exponent (assumed positive or zero).
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * @param pModulus The modulus value (or divisor if you like).
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncstatic int rtBigNumMagnitudeModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled); Assert(!pModulus->fCurScrambled);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Check some special cases to get them out of the way.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Div by 0 => invalid. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Div by 1 => no remainder. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync if (pModulus->cUsed == 1 && pModulus->pauElements[0] == 1)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* base ^ 0 => 1. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* base ^ 1 => base. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync if (pExponent->cUsed == 1 && pExponent->pauElements[0] == 1)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync return rtBigNumMagnitudeModulo(pResult, pBase, pModulus);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Result = 1; preallocate space for the result while at it. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumSetUsed(pResult, pModulus->cUsed + 1);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* ModBase = pBase or pBase % pModulus depending on the difference in size. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync if (pBase->cUsed <= pModulus->cUsed + pModulus->cUsed / 2)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeModulo(rtBigNumInitZeroTemplate(&Pow2, pBase), pBase, pModulus);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Need a couple of temporary variables. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rtBigNumInitZeroTemplate(&TmpMultiplicand, pResult);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * We combine the exponentiation by squaring with the fact that:
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * (a*b) mod n = ( (a mod n) * (b mod n) ) mod n
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * Thus, we can reduce the size of intermediate results by mod'ing them
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync * in each step.
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync uint32_t const cExpBits = rtBigNumMagnitudeBitWidth(pExponent);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, pResult);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeMultiply(&TmpProduct, &TmpMultiplicand, &Pow2);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeModulo(pResult, &TmpProduct, pModulus);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Done? */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync /* Not done yet, square and mod the base again. */
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, &Pow2);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeMultiply(&TmpProduct, &TmpMultiplicand, &TmpMultiplicand);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync rc = rtBigNumMagnitudeModulo(&Pow2, &TmpProduct, pModulus);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsyncRTDECL(int) RTBigNumModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync AssertReturn(pResult->fSensitive >= (pBase->fSensitive | pExponent->fSensitive | pModulus->fSensitive),
13493ab7596e827b8d0caab2c89e635dd65f78f9vboxsync pResult->fNegative = pModulus->fNegative; /* pBase ^ pExponent / pModulus; result = remainder. */