diff options
Diffstat (limited to '')
| -rw-r--r-- | include/iprt/bignum.h | 187 |
1 files changed, 187 insertions, 0 deletions
diff --git a/include/iprt/bignum.h b/include/iprt/bignum.h new file mode 100644 index 00000000..d2849bc5 --- /dev/null +++ b/include/iprt/bignum.h @@ -0,0 +1,187 @@ +/** @file + * IPRT - Big Integer Numbers. + */ + +/* + * Copyright (C) 2006-2019 Oracle Corporation + * + * This file is part of VirtualBox Open Source Edition (OSE), as + * available from http://www.virtualbox.org. This file is free software; + * you can redistribute it and/or modify it under the terms of the GNU + * 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. + */ + +#ifndef IPRT_INCLUDED_bignum_h +#define IPRT_INCLUDED_bignum_h +#ifndef RT_WITHOUT_PRAGMA_ONCE +# pragma once +#endif + +#include <iprt/types.h> + +RT_C_DECLS_BEGIN + +/** @defgroup grp_rtbignum RTBigNum - Big Integer Numbers + * @ingroup grp_rt + * @{ + */ + +/** The big integer number element type. */ +#if ARCH_BITS == 64 +typedef uint64_t RTBIGNUMELEMENT; +#else +typedef uint32_t RTBIGNUMELEMENT; +#endif +/** Pointer to a big integer number element. */ +typedef RTBIGNUMELEMENT *PRTBIGNUMELEMENT; +/** Pointer to a const big integer number element. */ +typedef RTBIGNUMELEMENT const *PCRTBIGNUMELEMENT; + +/** The size (in bytes) of one array element. */ +#if ARCH_BITS == 64 +# define RTBIGNUM_ELEMENT_SIZE 8 +#else +# define RTBIGNUM_ELEMENT_SIZE 4 +#endif +/** The number of bits in one array element. */ +#define RTBIGNUM_ELEMENT_BITS (RTBIGNUM_ELEMENT_SIZE * 8) +/** Returns the bitmask corrsponding to given bit number. */ +#if ARCH_BITS == 64 +# define RTBIGNUM_ELEMENT_BIT(iBit) RT_BIT_64(iBit) +#else +# define RTBIGNUM_ELEMENT_BIT(iBit) RT_BIT_32(iBit) +#endif +/** The maximum value one element can hold. */ +#if ARCH_BITS == 64 +# define RTBIGNUM_ELEMENT_MAX UINT64_MAX +#else +# define RTBIGNUM_ELEMENT_MAX UINT32_MAX +#endif +/** Mask including all the element bits set to 1. */ +#define RTBIGNUM_ELEMENT_MASK RTBIGNUM_ELEMENT_MAX + + +/** + * IPRT big integer number. + */ +typedef struct RTBIGNUM +{ + /** Elements array where the magnitue of the value is stored. */ + RTBIGNUMELEMENT *pauElements; + /** The current number of elements we're using in the pauElements array. */ + uint32_t cUsed; + /** The current allocation size of pauElements. */ + uint32_t cAllocated; + /** Reserved for future use. */ + uint32_t uReserved; + + /** Set if it's a negative number, clear if positive or zero. */ + uint32_t fNegative : 1; + + /** Whether to use a the data is sensitive (RTBIGNUMINIT_F_SENSITIVE). */ + uint32_t fSensitive : 1; + /** The number is currently scrambled */ + uint32_t fCurScrambled : 1; + + /** Bits reserved for future use. */ + uint32_t fReserved : 30; +} RTBIGNUM; + + +RTDECL(int) RTBigNumInit(PRTBIGNUM pBigNum, uint32_t fFlags, void const *pvRaw, size_t cbRaw); +RTDECL(int) RTBigNumInitZero(PRTBIGNUM pBigNum, uint32_t fFlags); + +/** @name RTBIGNUMINIT_F_XXX - RTBigNumInit flags. + * @{ */ +/** The number is sensitive so use a safer allocator, scramble it when not + * in use, and apply RTMemWipeThoroughly before freeing. The RTMemSafer API + * takes care of these things. + * @note When using this flag, concurrent access is not possible! */ +#define RTBIGNUMINIT_F_SENSITIVE RT_BIT(0) +/** Big endian number. */ +#define RTBIGNUMINIT_F_ENDIAN_BIG RT_BIT(1) +/** Little endian number. */ +#define RTBIGNUMINIT_F_ENDIAN_LITTLE RT_BIT(2) +/** The raw number is unsigned. */ +#define RTBIGNUMINIT_F_UNSIGNED RT_BIT(3) +/** The raw number is signed. */ +#define RTBIGNUMINIT_F_SIGNED RT_BIT(4) +/** @} */ + +RTDECL(int) RTBigNumClone(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc); + +RTDECL(int) RTBigNumDestroy(PRTBIGNUM pBigNum); + + +/** + * The minimum number of bits require store the two's complement representation + * of the number. + * + * @returns Width in number of bits. + * @param pBigNum The big number. + */ +RTDECL(uint32_t) RTBigNumBitWidth(PCRTBIGNUM pBigNum); +RTDECL(uint32_t) RTBigNumByteWidth(PCRTBIGNUM pBigNum); + + +/** + * Converts the big number to a sign-extended big endian byte sequence. + * + * @returns IPRT status code + * @retval VERR_BUFFER_OVERFLOW if the specified buffer is too small. + * @param pBigNum The big number. + * @param pvBuf The output buffer (size is at least cbWanted). + * @param cbWanted The number of bytes wanted. + */ +RTDECL(int) RTBigNumToBytesBigEndian(PCRTBIGNUM pBigNum, void *pvBuf, size_t cbWanted); + +/** + * Compares two numbers. + * + * @retval -1 if pLeft < pRight. + * @retval 0 if pLeft == pRight. + * @retval 1 if pLeft > pRight. + * + * @param pLeft The left side number. + * @param pRight The right side number. + */ +RTDECL(int) RTBigNumCompare(PRTBIGNUM pLeft, PRTBIGNUM pRight); +RTDECL(int) RTBigNumCompareWithU64(PRTBIGNUM pLeft, uint64_t uRight); +RTDECL(int) RTBigNumCompareWithS64(PRTBIGNUM pLeft, int64_t iRight); + +RTDECL(int) RTBigNumAssign(PRTBIGNUM pDst, PCRTBIGNUM pSrc); +RTDECL(int) RTBigNumNegate(PRTBIGNUM pResult, PCRTBIGNUM pBigNum); +RTDECL(int) RTBigNumNegateThis(PRTBIGNUM pThis); + +RTDECL(int) RTBigNumAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend); +RTDECL(int) RTBigNumSubtract(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend); +RTDECL(int) RTBigNumMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier); +RTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor); +RTDECL(int) RTBigNumDivideKnuth(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor); +RTDECL(int) RTBigNumDivideLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor); +RTDECL(int) RTBigNumModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor); +RTDECL(int) RTBigNumExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent); +RTDECL(int) RTBigNumShiftLeft(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits); +RTDECL(int) RTBigNumShiftRight(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits); + +RTDECL(int) RTBigNumModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus); + + +/** @} */ + +RT_C_DECLS_END + +#endif /* !IPRT_INCLUDED_bignum_h */ + |