1  /** @file


2  * IPRT  Big Integer Numbers.


3  */


4 


5  /*


6  * Copyright (C) 20062023 Oracle and/or its affiliates.


7  *


8  * This file is part of VirtualBox base platform packages, as


9  * available from https://www.virtualbox.org.


10  *


11  * This program is free software; you can redistribute it and/or


12  * modify it under the terms of the GNU General Public License


13  * as published by the Free Software Foundation, in version 3 of the


14  * License.


15  *


16  * This program is distributed in the hope that it will be useful, but


17  * WITHOUT ANY WARRANTY; without even the implied warranty of


18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU


19  * General Public License for more details.


20  *


21  * You should have received a copy of the GNU General Public License


22  * along with this program; if not, see <https://www.gnu.org/licenses>.


23  *


24  * The contents of this file may alternatively be used under the terms


25  * of the Common Development and Distribution License Version 1.0


26  * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included


27  * in the VirtualBox distribution, in which case the provisions of the


28  * CDDL are applicable instead of those of the GPL.


29  *


30  * You may elect to license modified versions of this file under the


31  * terms and conditions of either the GPL or the CDDL or both.


32  *


33  * SPDXLicenseIdentifier: GPL3.0only OR CDDL1.0


34  */


35 


36  #ifndef IPRT_INCLUDED_bignum_h


37  #define IPRT_INCLUDED_bignum_h


38  #ifndef RT_WITHOUT_PRAGMA_ONCE


39  # pragma once


40  #endif


41 


42  #include <iprt/types.h>


43 


44  RT_C_DECLS_BEGIN


45 


46  /** @defgroup grp_rtbignum RTBigNum  Big Integer Numbers


47  * @ingroup grp_rt


48  * @{


49  */


50 


51  /** The big integer number element type. */


52  #if ARCH_BITS == 64


53  typedef uint64_t RTBIGNUMELEMENT;


54  #else


55  typedef uint32_t RTBIGNUMELEMENT;


56  #endif


57  /** Pointer to a big integer number element. */


58  typedef RTBIGNUMELEMENT *PRTBIGNUMELEMENT;


59  /** Pointer to a const big integer number element. */


60  typedef RTBIGNUMELEMENT const *PCRTBIGNUMELEMENT;


61 


62  /** The size (in bytes) of one array element. */


63  #if ARCH_BITS == 64


64  # define RTBIGNUM_ELEMENT_SIZE 8


65  #else


66  # define RTBIGNUM_ELEMENT_SIZE 4


67  #endif


68  /** The number of bits in one array element. */


69  #define RTBIGNUM_ELEMENT_BITS (RTBIGNUM_ELEMENT_SIZE * 8)


70  /** Returns the bitmask corrsponding to given bit number. */


71  #if ARCH_BITS == 64


72  # define RTBIGNUM_ELEMENT_BIT(iBit) RT_BIT_64(iBit)


73  #else


74  # define RTBIGNUM_ELEMENT_BIT(iBit) RT_BIT_32(iBit)


75  #endif


76  /** The maximum value one element can hold. */


77  #if ARCH_BITS == 64


78  # define RTBIGNUM_ELEMENT_MAX UINT64_MAX


79  #else


80  # define RTBIGNUM_ELEMENT_MAX UINT32_MAX


81  #endif


82  /** Mask including all the element bits set to 1. */


83  #define RTBIGNUM_ELEMENT_MASK RTBIGNUM_ELEMENT_MAX


84 


85 


86  /**


87  * IPRT big integer number.


88  */


89  typedef struct RTBIGNUM


90  {


91  /** Elements array where the magnitue of the value is stored. */


92  RTBIGNUMELEMENT *pauElements;


93  /** The current number of elements we're using in the pauElements array. */


94  uint32_t cUsed;


95  /** The current allocation size of pauElements. */


96  uint32_t cAllocated;


97  /** Reserved for future use. */


98  uint32_t uReserved;


99 


100  /** Set if it's a negative number, clear if positive or zero. */


101  uint32_t fNegative : 1;


102 


103  /** Whether to use a the data is sensitive (RTBIGNUMINIT_F_SENSITIVE). */


104  uint32_t fSensitive : 1;


105  /** The number is currently scrambled */


106  uint32_t fCurScrambled : 1;


107 


108  /** Bits reserved for future use. */


109  uint32_t fReserved : 30;


110  } RTBIGNUM;


111 


112 


113  RTDECL(int) RTBigNumInit(PRTBIGNUM pBigNum, uint32_t fFlags, void const *pvRaw, size_t cbRaw);


114  RTDECL(int) RTBigNumInitZero(PRTBIGNUM pBigNum, uint32_t fFlags);


115 


116  /** @name RTBIGNUMINIT_F_XXX  RTBigNumInit flags.


117  * @{ */


118  /** The number is sensitive so use a safer allocator, scramble it when not


119  * in use, and apply RTMemWipeThoroughly before freeing. The RTMemSafer API


120  * takes care of these things.


121  * @note When using this flag, concurrent access is not possible! */


122  #define RTBIGNUMINIT_F_SENSITIVE RT_BIT(0)


123  /** Big endian number. */


124  #define RTBIGNUMINIT_F_ENDIAN_BIG RT_BIT(1)


125  /** Little endian number. */


126  #define RTBIGNUMINIT_F_ENDIAN_LITTLE RT_BIT(2)


127  /** The raw number is unsigned. */


128  #define RTBIGNUMINIT_F_UNSIGNED RT_BIT(3)


129  /** The raw number is signed. */


130  #define RTBIGNUMINIT_F_SIGNED RT_BIT(4)


131  /** @} */


132 


133  RTDECL(int) RTBigNumClone(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc);


134 


135  RTDECL(int) RTBigNumDestroy(PRTBIGNUM pBigNum);


136 


137 


138  /**


139  * The minimum number of bits require store the two's complement representation


140  * of the number.


141  *


142  * @returns Width in number of bits.


143  * @param pBigNum The big number.


144  */


145  RTDECL(uint32_t) RTBigNumBitWidth(PCRTBIGNUM pBigNum);


146  RTDECL(uint32_t) RTBigNumByteWidth(PCRTBIGNUM pBigNum);


147 


148 


149  /**


150  * Converts the big number to a signextended big endian byte sequence.


151  *


152  * @returns IPRT status code


153  * @retval VERR_BUFFER_OVERFLOW if the specified buffer is too small.


154  * @param pBigNum The big number.


155  * @param pvBuf The output buffer (size is at least cbWanted).


156  * @param cbWanted The number of bytes wanted.


157  */


158  RTDECL(int) RTBigNumToBytesBigEndian(PCRTBIGNUM pBigNum, void *pvBuf, size_t cbWanted);


159 


160  /**


161  * Compares two numbers.


162  *


163  * @retval 1 if pLeft < pRight.


164  * @retval 0 if pLeft == pRight.


165  * @retval 1 if pLeft > pRight.


166  *


167  * @param pLeft The left side number.


168  * @param pRight The right side number.


169  */


170  RTDECL(int) RTBigNumCompare(PRTBIGNUM pLeft, PRTBIGNUM pRight);


171  RTDECL(int) RTBigNumCompareWithU64(PRTBIGNUM pLeft, uint64_t uRight);


172  RTDECL(int) RTBigNumCompareWithS64(PRTBIGNUM pLeft, int64_t iRight);


173 


174  RTDECL(int) RTBigNumAssign(PRTBIGNUM pDst, PCRTBIGNUM pSrc);


175  RTDECL(int) RTBigNumNegate(PRTBIGNUM pResult, PCRTBIGNUM pBigNum);


176  RTDECL(int) RTBigNumNegateThis(PRTBIGNUM pThis);


177 


178  RTDECL(int) RTBigNumAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend);


179  RTDECL(int) RTBigNumSubtract(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend);


180  RTDECL(int) RTBigNumMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier);


181  RTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);


182  RTDECL(int) RTBigNumDivideKnuth(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);


183  RTDECL(int) RTBigNumDivideLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);


184  RTDECL(int) RTBigNumModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);


185  RTDECL(int) RTBigNumExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent);


186  RTDECL(int) RTBigNumShiftLeft(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits);


187  RTDECL(int) RTBigNumShiftRight(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits);


188 


189  RTDECL(int) RTBigNumModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus);


190 


191 


192  /** @} */


193 


194  RT_C_DECLS_END


195 


196  #endif /* !IPRT_INCLUDED_bignum_h */


197 

