[51770] | 1 | /** @file
|
---|
| 2 | * IPRT - Big Integer Numbers.
|
---|
| 3 | */
|
---|
| 4 |
|
---|
| 5 | /*
|
---|
[76553] | 6 | * Copyright (C) 2006-2019 Oracle Corporation
|
---|
[51770] | 7 | *
|
---|
| 8 | * This file is part of VirtualBox Open Source Edition (OSE), as
|
---|
| 9 | * available from http://www.virtualbox.org. This file is free software;
|
---|
| 10 | * you can redistribute it and/or modify it under the terms of the GNU
|
---|
| 11 | * General Public License (GPL) as published by the Free Software
|
---|
| 12 | * Foundation, in version 2 as it comes in the "COPYING" file of the
|
---|
| 13 | * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
|
---|
| 14 | * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
|
---|
| 15 | *
|
---|
| 16 | * The contents of this file may alternatively be used under the terms
|
---|
| 17 | * of the Common Development and Distribution License Version 1.0
|
---|
| 18 | * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
|
---|
| 19 | * VirtualBox OSE distribution, in which case the provisions of the
|
---|
| 20 | * CDDL are applicable instead of those of the GPL.
|
---|
| 21 | *
|
---|
| 22 | * You may elect to license modified versions of this file under the
|
---|
| 23 | * terms and conditions of either the GPL or the CDDL or both.
|
---|
| 24 | */
|
---|
| 25 |
|
---|
[76557] | 26 | #ifndef IPRT_INCLUDED_bignum_h
|
---|
| 27 | #define IPRT_INCLUDED_bignum_h
|
---|
[76507] | 28 | #ifndef RT_WITHOUT_PRAGMA_ONCE
|
---|
| 29 | # pragma once
|
---|
| 30 | #endif
|
---|
[51770] | 31 |
|
---|
| 32 | #include <iprt/types.h>
|
---|
| 33 |
|
---|
| 34 | RT_C_DECLS_BEGIN
|
---|
| 35 |
|
---|
| 36 | /** @defgroup grp_rtbignum RTBigNum - Big Integer Numbers
|
---|
| 37 | * @ingroup grp_rt
|
---|
| 38 | * @{
|
---|
| 39 | */
|
---|
| 40 |
|
---|
| 41 | /** The big integer number element type. */
|
---|
[52290] | 42 | #if ARCH_BITS == 64
|
---|
| 43 | typedef uint64_t RTBIGNUMELEMENT;
|
---|
| 44 | #else
|
---|
[51770] | 45 | typedef uint32_t RTBIGNUMELEMENT;
|
---|
[52290] | 46 | #endif
|
---|
[52335] | 47 | /** Pointer to a big integer number element. */
|
---|
| 48 | typedef RTBIGNUMELEMENT *PRTBIGNUMELEMENT;
|
---|
| 49 | /** Pointer to a const big integer number element. */
|
---|
| 50 | typedef RTBIGNUMELEMENT const *PCRTBIGNUMELEMENT;
|
---|
| 51 |
|
---|
[51770] | 52 | /** The size (in bytes) of one array element. */
|
---|
[52290] | 53 | #if ARCH_BITS == 64
|
---|
| 54 | # define RTBIGNUM_ELEMENT_SIZE 8
|
---|
| 55 | #else
|
---|
| 56 | # define RTBIGNUM_ELEMENT_SIZE 4
|
---|
| 57 | #endif
|
---|
[51770] | 58 | /** The number of bits in one array element. */
|
---|
| 59 | #define RTBIGNUM_ELEMENT_BITS (RTBIGNUM_ELEMENT_SIZE * 8)
|
---|
| 60 | /** Returns the bitmask corrsponding to given bit number. */
|
---|
[52290] | 61 | #if ARCH_BITS == 64
|
---|
| 62 | # define RTBIGNUM_ELEMENT_BIT(iBit) RT_BIT_64(iBit)
|
---|
| 63 | #else
|
---|
| 64 | # define RTBIGNUM_ELEMENT_BIT(iBit) RT_BIT_32(iBit)
|
---|
| 65 | #endif
|
---|
[52335] | 66 | /** The maximum value one element can hold. */
|
---|
| 67 | #if ARCH_BITS == 64
|
---|
| 68 | # define RTBIGNUM_ELEMENT_MAX UINT64_MAX
|
---|
| 69 | #else
|
---|
| 70 | # define RTBIGNUM_ELEMENT_MAX UINT32_MAX
|
---|
| 71 | #endif
|
---|
| 72 | /** Mask including all the element bits set to 1. */
|
---|
| 73 | #define RTBIGNUM_ELEMENT_MASK RTBIGNUM_ELEMENT_MAX
|
---|
[51770] | 74 |
|
---|
[52335] | 75 |
|
---|
[51770] | 76 | /**
|
---|
| 77 | * IPRT big integer number.
|
---|
| 78 | */
|
---|
| 79 | typedef struct RTBIGNUM
|
---|
| 80 | {
|
---|
| 81 | /** Elements array where the magnitue of the value is stored. */
|
---|
| 82 | RTBIGNUMELEMENT *pauElements;
|
---|
| 83 | /** The current number of elements we're using in the pauElements array. */
|
---|
| 84 | uint32_t cUsed;
|
---|
| 85 | /** The current allocation size of pauElements. */
|
---|
| 86 | uint32_t cAllocated;
|
---|
| 87 | /** Reserved for future use. */
|
---|
| 88 | uint32_t uReserved;
|
---|
| 89 |
|
---|
| 90 | /** Set if it's a negative number, clear if positive or zero. */
|
---|
| 91 | uint32_t fNegative : 1;
|
---|
| 92 |
|
---|
| 93 | /** Whether to use a the data is sensitive (RTBIGNUMINIT_F_SENSITIVE). */
|
---|
| 94 | uint32_t fSensitive : 1;
|
---|
| 95 | /** The number is currently scrambled */
|
---|
| 96 | uint32_t fCurScrambled : 1;
|
---|
| 97 |
|
---|
| 98 | /** Bits reserved for future use. */
|
---|
| 99 | uint32_t fReserved : 30;
|
---|
| 100 | } RTBIGNUM;
|
---|
| 101 |
|
---|
| 102 |
|
---|
| 103 | RTDECL(int) RTBigNumInit(PRTBIGNUM pBigNum, uint32_t fFlags, void const *pvRaw, size_t cbRaw);
|
---|
| 104 | RTDECL(int) RTBigNumInitZero(PRTBIGNUM pBigNum, uint32_t fFlags);
|
---|
| 105 |
|
---|
| 106 | /** @name RTBIGNUMINIT_F_XXX - RTBigNumInit flags.
|
---|
| 107 | * @{ */
|
---|
| 108 | /** The number is sensitive so use a safer allocator, scramble it when not
|
---|
| 109 | * in use, and apply RTMemWipeThoroughly before freeing. The RTMemSafer API
|
---|
| 110 | * takes care of these things.
|
---|
| 111 | * @note When using this flag, concurrent access is not possible! */
|
---|
| 112 | #define RTBIGNUMINIT_F_SENSITIVE RT_BIT(0)
|
---|
| 113 | /** Big endian number. */
|
---|
| 114 | #define RTBIGNUMINIT_F_ENDIAN_BIG RT_BIT(1)
|
---|
| 115 | /** Little endian number. */
|
---|
| 116 | #define RTBIGNUMINIT_F_ENDIAN_LITTLE RT_BIT(2)
|
---|
| 117 | /** The raw number is unsigned. */
|
---|
| 118 | #define RTBIGNUMINIT_F_UNSIGNED RT_BIT(3)
|
---|
| 119 | /** The raw number is signed. */
|
---|
| 120 | #define RTBIGNUMINIT_F_SIGNED RT_BIT(4)
|
---|
| 121 | /** @} */
|
---|
| 122 |
|
---|
| 123 | RTDECL(int) RTBigNumClone(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc);
|
---|
| 124 |
|
---|
| 125 | RTDECL(int) RTBigNumDestroy(PRTBIGNUM pBigNum);
|
---|
| 126 |
|
---|
| 127 |
|
---|
| 128 | /**
|
---|
| 129 | * The minimum number of bits require store the two's complement representation
|
---|
| 130 | * of the number.
|
---|
| 131 | *
|
---|
| 132 | * @returns Width in number of bits.
|
---|
| 133 | * @param pBigNum The big number.
|
---|
| 134 | */
|
---|
| 135 | RTDECL(uint32_t) RTBigNumBitWidth(PCRTBIGNUM pBigNum);
|
---|
| 136 | RTDECL(uint32_t) RTBigNumByteWidth(PCRTBIGNUM pBigNum);
|
---|
| 137 |
|
---|
| 138 |
|
---|
| 139 | /**
|
---|
| 140 | * Converts the big number to a sign-extended big endian byte sequence.
|
---|
| 141 | *
|
---|
| 142 | * @returns IPRT status code
|
---|
| 143 | * @retval VERR_BUFFER_OVERFLOW if the specified buffer is too small.
|
---|
| 144 | * @param pBigNum The big number.
|
---|
| 145 | * @param pvBuf The output buffer (size is at least cbWanted).
|
---|
| 146 | * @param cbWanted The number of bytes wanted.
|
---|
| 147 | */
|
---|
| 148 | RTDECL(int) RTBigNumToBytesBigEndian(PCRTBIGNUM pBigNum, void *pvBuf, size_t cbWanted);
|
---|
| 149 |
|
---|
| 150 | /**
|
---|
| 151 | * Compares two numbers.
|
---|
| 152 | *
|
---|
| 153 | * @retval -1 if pLeft < pRight.
|
---|
| 154 | * @retval 0 if pLeft == pRight.
|
---|
| 155 | * @retval 1 if pLeft > pRight.
|
---|
| 156 | *
|
---|
| 157 | * @param pLeft The left side number.
|
---|
| 158 | * @param pRight The right side number.
|
---|
| 159 | */
|
---|
| 160 | RTDECL(int) RTBigNumCompare(PRTBIGNUM pLeft, PRTBIGNUM pRight);
|
---|
| 161 | RTDECL(int) RTBigNumCompareWithU64(PRTBIGNUM pLeft, uint64_t uRight);
|
---|
| 162 | RTDECL(int) RTBigNumCompareWithS64(PRTBIGNUM pLeft, int64_t iRight);
|
---|
| 163 |
|
---|
| 164 | RTDECL(int) RTBigNumAssign(PRTBIGNUM pDst, PCRTBIGNUM pSrc);
|
---|
| 165 | RTDECL(int) RTBigNumNegate(PRTBIGNUM pResult, PCRTBIGNUM pBigNum);
|
---|
| 166 | RTDECL(int) RTBigNumNegateThis(PRTBIGNUM pThis);
|
---|
| 167 |
|
---|
| 168 | RTDECL(int) RTBigNumAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend);
|
---|
| 169 | RTDECL(int) RTBigNumSubtract(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend);
|
---|
| 170 | RTDECL(int) RTBigNumMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier);
|
---|
| 171 | RTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);
|
---|
[52335] | 172 | RTDECL(int) RTBigNumDivideKnuth(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);
|
---|
| 173 | RTDECL(int) RTBigNumDivideLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);
|
---|
[51770] | 174 | RTDECL(int) RTBigNumModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor);
|
---|
| 175 | RTDECL(int) RTBigNumExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent);
|
---|
[52335] | 176 | RTDECL(int) RTBigNumShiftLeft(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits);
|
---|
| 177 | RTDECL(int) RTBigNumShiftRight(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits);
|
---|
[51770] | 178 |
|
---|
| 179 | RTDECL(int) RTBigNumModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus);
|
---|
| 180 |
|
---|
| 181 |
|
---|
| 182 | /** @} */
|
---|
| 183 |
|
---|
| 184 | RT_C_DECLS_END
|
---|
| 185 |
|
---|
[76585] | 186 | #endif /* !IPRT_INCLUDED_bignum_h */
|
---|
[51770] | 187 |
|
---|