VirtualBox

source: vbox/trunk/src/VBox/Runtime/common/math/bignum.cpp

Last change on this file was 106061, checked in by vboxsync, 8 weeks ago

Copyright year updates by scm.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 95.0 KB
Line 
1/* $Id: bignum.cpp 106061 2024-09-16 14:03:52Z vboxsync $ */
2/** @file
3 * IPRT - Big Integer Numbers.
4 */
5
6/*
7 * Copyright (C) 2006-2024 Oracle and/or its affiliates.
8 *
9 * This file is part of VirtualBox base platform packages, as
10 * available from https://www.virtualbox.org.
11 *
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation, in version 3 of the
15 * License.
16 *
17 * This program is distributed in the hope that it will be useful, but
18 * WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 * General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License
23 * along with this program; if not, see <https://www.gnu.org/licenses>.
24 *
25 * The contents of this file may alternatively be used under the terms
26 * of the Common Development and Distribution License Version 1.0
27 * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
28 * in the VirtualBox distribution, in which case the provisions of the
29 * CDDL are applicable instead of those of the GPL.
30 *
31 * You may elect to license modified versions of this file under the
32 * terms and conditions of either the GPL or the CDDL or both.
33 *
34 * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
35 */
36
37
38/*********************************************************************************************************************************
39* Header Files *
40*********************************************************************************************************************************/
41/*#ifdef IN_RING3
42# define RTMEM_WRAP_TO_EF_APIS
43#endif*/
44#include "internal/iprt.h"
45#include <iprt/bignum.h>
46
47#include <iprt/asm-mem.h>
48#include <iprt/asm.h>
49#include <iprt/asm-math.h>
50#include <iprt/err.h>
51#include <iprt/mem.h>
52#include <iprt/memsafer.h>
53#include <iprt/string.h>
54#if RTBIGNUM_ELEMENT_BITS == 64
55# include <iprt/uint128.h>
56#endif
57
58
59/*********************************************************************************************************************************
60* Defined Constants And Macros *
61*********************************************************************************************************************************/
62/** Allocation alignment in elements. */
63#ifndef RTMEM_WRAP_TO_EF_APIS
64# define RTBIGNUM_ALIGNMENT 4U
65#else
66# define RTBIGNUM_ALIGNMENT 1U
67#endif
68
69/** The max size (in bytes) of an elements array. */
70#define RTBIGNUM_MAX_SIZE _4M
71
72
73/** Assert the validity of a big number structure pointer in strict builds. */
74#ifdef RT_STRICT
75# define RTBIGNUM_ASSERT_VALID(a_pBigNum) \
76 do { \
77 AssertPtr(a_pBigNum); \
78 Assert(!(a_pBigNum)->fCurScrambled); \
79 Assert( (a_pBigNum)->cUsed == (a_pBigNum)->cAllocated \
80 || ASMMemIsZero(&(a_pBigNum)->pauElements[(a_pBigNum)->cUsed], \
81 ((a_pBigNum)->cAllocated - (a_pBigNum)->cUsed) * RTBIGNUM_ELEMENT_SIZE)); \
82 } while (0)
83#else
84# define RTBIGNUM_ASSERT_VALID(a_pBigNum) do {} while (0)
85#endif
86
87
88/** Enable assembly optimizations. */
89#if defined(RT_ARCH_AMD64) || defined(RT_ARCH_X86)
90# define IPRT_BIGINT_WITH_ASM
91#endif
92
93
94/** @def RTBIGNUM_ZERO_ALIGN
95 * For calculating the rtBigNumEnsureExtraZeroElements argument from cUsed.
96 * This has to do with 64-bit assembly instruction operating as RTBIGNUMELEMENT
97 * was 64-bit on some hosts.
98 */
99#if defined(IPRT_BIGINT_WITH_ASM) && ARCH_BITS == 64 && RTBIGNUM_ELEMENT_SIZE == 4 && defined(RT_LITTLE_ENDIAN)
100# define RTBIGNUM_ZERO_ALIGN(a_cUsed) RT_ALIGN_32(a_cUsed, 2)
101#elif defined(IPRT_BIGINT_WITH_ASM)
102# define RTBIGNUM_ZERO_ALIGN(a_cUsed) (a_cUsed)
103#else
104# define RTBIGNUM_ZERO_ALIGN(a_cUsed) (a_cUsed)
105#endif
106
107#define RTBIGNUMELEMENT_HALF_MASK ( ((RTBIGNUMELEMENT)1 << (RTBIGNUM_ELEMENT_BITS / 2)) - (RTBIGNUMELEMENT)1)
108#define RTBIGNUMELEMENT_LO_HALF(a_uElement) ( (RTBIGNUMELEMENT_HALF_MASK) & (a_uElement) )
109#define RTBIGNUMELEMENT_HI_HALF(a_uElement) ( (a_uElement) >> (RTBIGNUM_ELEMENT_BITS / 2) )
110
111
112/*********************************************************************************************************************************
113* Structures and Typedefs *
114*********************************************************************************************************************************/
115/** Type the size of two elements. */
116#if RTBIGNUM_ELEMENT_BITS == 64
117typedef RTUINT128U RTBIGNUMELEMENT2X;
118#else
119typedef RTUINT64U RTBIGNUMELEMENT2X;
120#endif
121
122
123/*********************************************************************************************************************************
124* Internal Functions *
125*********************************************************************************************************************************/
126DECLINLINE(int) rtBigNumSetUsed(PRTBIGNUM pBigNum, uint32_t cNewUsed);
127
128#ifdef IPRT_BIGINT_WITH_ASM
129/* bignum-amd64-x86.asm: */
130DECLASM(void) rtBigNumMagnitudeSubAssemblyWorker(RTBIGNUMELEMENT *pauResult, RTBIGNUMELEMENT const *pauMinuend,
131 RTBIGNUMELEMENT const *pauSubtrahend, uint32_t cUsed);
132DECLASM(void) rtBigNumMagnitudeSubThisAssemblyWorker(RTBIGNUMELEMENT *pauMinuendResult, RTBIGNUMELEMENT const *pauSubtrahend,
133 uint32_t cUsed);
134DECLASM(RTBIGNUMELEMENT) rtBigNumMagnitudeShiftLeftOneAssemblyWorker(RTBIGNUMELEMENT *pauElements, uint32_t cUsed,
135 RTBIGNUMELEMENT uCarry);
136DECLASM(void) rtBigNumElement2xDiv2xBy1x(RTBIGNUMELEMENT2X *puQuotient, RTBIGNUMELEMENT *puRemainder,
137 RTBIGNUMELEMENT uDividendHi, RTBIGNUMELEMENT uDividendLo, RTBIGNUMELEMENT uDivisor);
138DECLASM(void) rtBigNumMagnitudeMultiplyAssemblyWorker(PRTBIGNUMELEMENT pauResult,
139 PCRTBIGNUMELEMENT pauMultiplier, uint32_t cMultiplier,
140 PCRTBIGNUMELEMENT pauMultiplicand, uint32_t cMultiplicand);
141#endif
142
143
144
145
146
147/** @name Functions working on one element.
148 * @{ */
149
150DECLINLINE(uint32_t) rtBigNumElementBitCount(RTBIGNUMELEMENT uElement)
151{
152#if RTBIGNUM_ELEMENT_SIZE == 8
153 if (uElement >> 32)
154 return ASMBitLastSetU32((uint32_t)(uElement >> 32)) + 32;
155 return ASMBitLastSetU32((uint32_t)uElement);
156#elif RTBIGNUM_ELEMENT_SIZE == 4
157 return ASMBitLastSetU32(uElement);
158#else
159# error "Bad RTBIGNUM_ELEMENT_SIZE value"
160#endif
161}
162
163
164/**
165 * Does addition with carry.
166 *
167 * This is a candidate for inline assembly on some platforms.
168 *
169 * @returns The result (the sum)
170 * @param uAugend What to add to.
171 * @param uAddend What to add to it.
172 * @param pfCarry Where to read the input carry and return the output
173 * carry.
174 */
175DECLINLINE(RTBIGNUMELEMENT) rtBigNumElementAddWithCarry(RTBIGNUMELEMENT uAugend, RTBIGNUMELEMENT uAddend,
176 RTBIGNUMELEMENT *pfCarry)
177{
178 RTBIGNUMELEMENT uRet = uAugend + uAddend;
179 if (!*pfCarry)
180 *pfCarry = uRet < uAugend;
181 else
182 {
183 uRet += 1;
184 *pfCarry = uRet <= uAugend;
185 }
186 return uRet;
187}
188
189
190#if !defined(IPRT_BIGINT_WITH_ASM) || defined(RT_STRICT)
191/**
192 * Does addition with borrow.
193 *
194 * This is a candidate for inline assembly on some platforms.
195 *
196 * @returns The result (the sum)
197 * @param uMinuend What to subtract from.
198 * @param uSubtrahend What to subtract.
199 * @param pfBorrow Where to read the input borrow and return the output
200 * borrow.
201 */
202DECLINLINE(RTBIGNUMELEMENT) rtBigNumElementSubWithBorrow(RTBIGNUMELEMENT uMinuend, RTBIGNUMELEMENT uSubtrahend,
203 RTBIGNUMELEMENT *pfBorrow)
204{
205 RTBIGNUMELEMENT uRet = uMinuend - uSubtrahend - *pfBorrow;
206
207 /* Figure out if we borrowed. */
208 *pfBorrow = !*pfBorrow ? uMinuend < uSubtrahend : uMinuend <= uSubtrahend;
209 return uRet;
210}
211#endif
212
213/** @} */
214
215
216
217
218/** @name Double element primitives.
219 * @{ */
220
221static int rtBigNumElement2xCopyToMagnitude(RTBIGNUMELEMENT2X const *pValue2x, PRTBIGNUM pDst)
222{
223 int rc;
224 if (pValue2x->s.Hi)
225 {
226 rc = rtBigNumSetUsed(pDst, 2);
227 if (RT_SUCCESS(rc))
228 {
229 pDst->pauElements[0] = pValue2x->s.Lo;
230 pDst->pauElements[1] = pValue2x->s.Hi;
231 }
232 }
233 else if (pValue2x->s.Lo)
234 {
235 rc = rtBigNumSetUsed(pDst, 1);
236 if (RT_SUCCESS(rc))
237 pDst->pauElements[0] = pValue2x->s.Lo;
238 }
239 else
240 rc = rtBigNumSetUsed(pDst, 0);
241 return rc;
242}
243
244static void rtBigNumElement2xDiv(RTBIGNUMELEMENT2X *puQuotient, RTBIGNUMELEMENT2X *puRemainder,
245 RTBIGNUMELEMENT uDividendHi, RTBIGNUMELEMENT uDividendLo,
246 RTBIGNUMELEMENT uDivisorHi, RTBIGNUMELEMENT uDivisorLo)
247{
248 RTBIGNUMELEMENT2X uDividend;
249 uDividend.s.Lo = uDividendLo;
250 uDividend.s.Hi = uDividendHi;
251
252 RTBIGNUMELEMENT2X uDivisor;
253 uDivisor.s.Lo = uDivisorLo;
254 uDivisor.s.Hi = uDivisorHi;
255
256#if RTBIGNUM_ELEMENT_BITS == 64
257 RTUInt128DivRem(puQuotient, puRemainder, &uDividend, &uDivisor);
258#else
259 puQuotient->u = uDividend.u / uDivisor.u;
260 puRemainder->u = uDividend.u % uDivisor.u;
261#endif
262}
263
264#ifndef IPRT_BIGINT_WITH_ASM
265static void rtBigNumElement2xDiv2xBy1x(RTBIGNUMELEMENT2X *puQuotient, RTBIGNUMELEMENT *puRemainder,
266 RTBIGNUMELEMENT uDividendHi, RTBIGNUMELEMENT uDividendLo, RTBIGNUMELEMENT uDivisor)
267{
268 RTBIGNUMELEMENT2X uDividend;
269 uDividend.s.Lo = uDividendLo;
270 uDividend.s.Hi = uDividendHi;
271
272# if RTBIGNUM_ELEMENT_BITS == 64
273 RTBIGNUMELEMENT2X uRemainder2x;
274 RTBIGNUMELEMENT2X uDivisor2x;
275 uDivisor2x.s.Hi = 0;
276 uDivisor2x.s.Lo = uDivisor;
277 /** @todo optimize this. */
278 RTUInt128DivRem(puQuotient, &uRemainder2x, &uDividend, &uDivisor2x);
279 *puRemainder = uRemainder2x.s.Lo;
280# else
281 puQuotient->u = uDividend.u / uDivisor;
282 puRemainder->u = uDividend.u % uDivisor;
283# endif
284}
285#endif
286
287DECLINLINE(void) rtBigNumElement2xDec(RTBIGNUMELEMENT2X *puValue)
288{
289#if RTBIGNUM_ELEMENT_BITS == 64
290 if (puValue->s.Lo-- == 0)
291 puValue->s.Hi--;
292#else
293 puValue->u -= 1;
294#endif
295}
296
297#if 0 /* unused */
298DECLINLINE(void) rtBigNumElement2xAdd1x(RTBIGNUMELEMENT2X *puValue, RTBIGNUMELEMENT uAdd)
299{
300#if RTBIGNUM_ELEMENT_BITS == 64
301 RTUInt128AssignAddU64(puValue, uAdd);
302#else
303 puValue->u += uAdd;
304#endif
305}
306#endif /* unused */
307
308/** @} */
309
310
311
312
313
314/**
315 * Scrambles a big number if required.
316 *
317 * @param pBigNum The big number.
318 */
319DECLINLINE(void) rtBigNumScramble(PRTBIGNUM pBigNum)
320{
321 if (pBigNum->fSensitive)
322 {
323 AssertReturnVoid(!pBigNum->fCurScrambled);
324 if (pBigNum->pauElements)
325 {
326 int rc = RTMemSaferScramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
327 pBigNum->fCurScrambled = RT_SUCCESS(rc);
328 }
329 else
330 pBigNum->fCurScrambled = true;
331 }
332}
333
334
335/**
336 * Unscrambles a big number if required.
337 *
338 * @returns IPRT status code.
339 * @param pBigNum The big number.
340 */
341DECLINLINE(int) rtBigNumUnscramble(PRTBIGNUM pBigNum)
342{
343 if (pBigNum->fSensitive)
344 {
345 AssertReturn(pBigNum->fCurScrambled, VERR_INTERNAL_ERROR_2);
346 if (pBigNum->pauElements)
347 {
348 int rc = RTMemSaferUnscramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
349 pBigNum->fCurScrambled = !RT_SUCCESS(rc);
350 return rc;
351 }
352 else
353 pBigNum->fCurScrambled = false;
354 }
355 return VINF_SUCCESS;
356}
357
358
359/**
360 * Getter function for pauElements which extends the array to infinity.
361 *
362 * @returns The element value.
363 * @param pBigNum The big number.
364 * @param iElement The element index.
365 */
366DECLINLINE(RTBIGNUMELEMENT) rtBigNumGetElement(PCRTBIGNUM pBigNum, uint32_t iElement)
367{
368 if (iElement < pBigNum->cUsed)
369 return pBigNum->pauElements[iElement];
370 return 0;
371}
372
373
374/**
375 * Grows the pauElements array so it can fit at least @a cNewUsed entries.
376 *
377 * @returns IPRT status code.
378 * @param pBigNum The big number.
379 * @param cNewUsed The new cUsed value.
380 * @param cMinElements The minimum number of elements.
381 */
382static int rtBigNumGrow(PRTBIGNUM pBigNum, uint32_t cNewUsed, uint32_t cMinElements)
383{
384 Assert(cMinElements >= cNewUsed);
385 uint32_t const cbOld = pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE;
386 uint32_t const cNew = RT_ALIGN_32(cMinElements, RTBIGNUM_ALIGNMENT);
387 uint32_t const cbNew = cNew * RTBIGNUM_ELEMENT_SIZE;
388 Assert(cbNew > cbOld);
389 if (cbNew <= RTBIGNUM_MAX_SIZE && cbNew > cbOld)
390 {
391 void *pvNew;
392 if (pBigNum->fSensitive)
393 pvNew = RTMemSaferReallocZ(cbOld, pBigNum->pauElements, cbNew);
394 else
395 pvNew = RTMemRealloc(pBigNum->pauElements, cbNew);
396 if (RT_LIKELY(pvNew))
397 {
398 if (cbNew > cbOld)
399 RT_BZERO((char *)pvNew + cbOld, cbNew - cbOld);
400 if (pBigNum->cUsed > cNewUsed)
401 RT_BZERO((RTBIGNUMELEMENT *)pvNew + cNewUsed, (pBigNum->cUsed - cNewUsed) * RTBIGNUM_ELEMENT_SIZE);
402
403 pBigNum->pauElements = (RTBIGNUMELEMENT *)pvNew;
404 pBigNum->cUsed = cNewUsed;
405 pBigNum->cAllocated = cNew;
406 return VINF_SUCCESS;
407 }
408 return VERR_NO_MEMORY;
409 }
410 return VERR_OUT_OF_RANGE;
411}
412
413
414/**
415 * Changes the cUsed member, growing the pauElements array if necessary.
416 *
417 * Any elements added to the array will be initialized to zero.
418 *
419 * @returns IPRT status code.
420 * @param pBigNum The big number.
421 * @param cNewUsed The new cUsed value.
422 */
423DECLINLINE(int) rtBigNumSetUsed(PRTBIGNUM pBigNum, uint32_t cNewUsed)
424{
425 if (pBigNum->cAllocated >= cNewUsed)
426 {
427 if (pBigNum->cUsed > cNewUsed)
428 RT_BZERO(&pBigNum->pauElements[cNewUsed], (pBigNum->cUsed - cNewUsed) * RTBIGNUM_ELEMENT_SIZE);
429#ifdef RT_STRICT
430 else if (pBigNum->cUsed != cNewUsed)
431 Assert(ASMMemIsZero(&pBigNum->pauElements[pBigNum->cUsed], (cNewUsed - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE));
432#endif
433 pBigNum->cUsed = cNewUsed;
434 return VINF_SUCCESS;
435 }
436 return rtBigNumGrow(pBigNum, cNewUsed, cNewUsed);
437}
438
439
440/**
441 * Extended version of rtBigNumSetUsed that also allow specifying the number of
442 * zero elements required.
443 *
444 * @returns IPRT status code.
445 * @param pBigNum The big number.
446 * @param cNewUsed The new cUsed value.
447 * @param cMinElements The minimum number of elements allocated. The
448 * difference between @a cNewUsed and @a cMinElements
449 * is initialized to zero because all free elements are
450 * zero.
451 */
452DECLINLINE(int) rtBigNumSetUsedEx(PRTBIGNUM pBigNum, uint32_t cNewUsed, uint32_t cMinElements)
453{
454 if (pBigNum->cAllocated >= cMinElements)
455 {
456 if (pBigNum->cUsed > cNewUsed)
457 RT_BZERO(&pBigNum->pauElements[cNewUsed], (pBigNum->cUsed - cNewUsed) * RTBIGNUM_ELEMENT_SIZE);
458#ifdef RT_STRICT
459 else if (pBigNum->cUsed != cNewUsed)
460 Assert(ASMMemIsZero(&pBigNum->pauElements[pBigNum->cUsed], (cNewUsed - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE));
461#endif
462 pBigNum->cUsed = cNewUsed;
463 return VINF_SUCCESS;
464 }
465 return rtBigNumGrow(pBigNum, cNewUsed, cMinElements);
466}
467
468
469/**
470 * For ensuring zero padding of pauElements for sub/add with carry assembly
471 * operations.
472 *
473 * @returns IPRT status code.
474 * @param pBigNum The big number.
475 * @param cElements The number of elements that must be in the elements
476 * array array, where those after pBigNum->cUsed must
477 * be zero.
478 */
479DECLINLINE(int) rtBigNumEnsureExtraZeroElements(PRTBIGNUM pBigNum, uint32_t cElements)
480{
481 if (pBigNum->cAllocated >= cElements)
482 {
483 Assert( pBigNum->cAllocated == pBigNum->cUsed
484 || ASMMemIsZero(&pBigNum->pauElements[pBigNum->cUsed],
485 (pBigNum->cAllocated - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE));
486 return VINF_SUCCESS;
487 }
488 return rtBigNumGrow(pBigNum, pBigNum->cUsed, cElements);
489}
490
491
492/**
493 * The slow part of rtBigNumEnsureElementPresent where we need to do actual zero
494 * extending.
495 *
496 * @returns IPRT status code.
497 * @param pBigNum The big number.
498 * @param iElement The element we wish to access.
499 */
500static int rtBigNumEnsureElementPresentSlow(PRTBIGNUM pBigNum, uint32_t iElement)
501{
502 uint32_t const cOldUsed = pBigNum->cUsed;
503 int rc = rtBigNumSetUsed(pBigNum, iElement + 1);
504 if (RT_SUCCESS(rc))
505 {
506 RT_BZERO(&pBigNum->pauElements[cOldUsed], (iElement + 1 - cOldUsed) * RTBIGNUM_ELEMENT_SIZE);
507 return VINF_SUCCESS;
508 }
509 return rc;
510}
511
512
513/**
514 * Zero extends the element array to make sure a the specified element index is
515 * accessible.
516 *
517 * This is typically used with bit operations and self modifying methods. Any
518 * new elements added will be initialized to zero. The caller is responsible
519 * for there not being any trailing zero elements.
520 *
521 * The number must be unscrambled.
522 *
523 * @returns IPRT status code.
524 * @param pBigNum The big number.
525 * @param iElement The element we wish to access.
526 */
527DECLINLINE(int) rtBigNumEnsureElementPresent(PRTBIGNUM pBigNum, uint32_t iElement)
528{
529 if (iElement < pBigNum->cUsed)
530 return VINF_SUCCESS;
531 return rtBigNumEnsureElementPresentSlow(pBigNum, iElement);
532}
533
534
535/**
536 * Strips zero elements from the magnitude value.
537 *
538 * @param pBigNum The big number to strip.
539 */
540static void rtBigNumStripTrailingZeros(PRTBIGNUM pBigNum)
541{
542 uint32_t i = pBigNum->cUsed;
543 while (i > 0 && pBigNum->pauElements[i - 1] == 0)
544 i--;
545 pBigNum->cUsed = i;
546}
547
548
549/**
550 * Initialize the big number to zero.
551 *
552 * @returns @a pBigNum
553 * @param pBigNum The big number.
554 * @param fFlags The flags.
555 * @internal
556 */
557DECLINLINE(PRTBIGNUM) rtBigNumInitZeroInternal(PRTBIGNUM pBigNum, uint32_t fFlags)
558{
559 RT_ZERO(*pBigNum);
560 pBigNum->fSensitive = RT_BOOL(fFlags & RTBIGNUMINIT_F_SENSITIVE);
561 return pBigNum;
562}
563
564
565/**
566 * Initialize the big number to zero from a template variable.
567 *
568 * @returns @a pBigNum
569 * @param pBigNum The big number.
570 * @param pTemplate The template big number.
571 * @internal
572 */
573DECLINLINE(PRTBIGNUM) rtBigNumInitZeroTemplate(PRTBIGNUM pBigNum, PCRTBIGNUM pTemplate)
574{
575 RT_ZERO(*pBigNum);
576 pBigNum->fSensitive = pTemplate->fSensitive;
577 return pBigNum;
578}
579
580
581RTDECL(int) RTBigNumInit(PRTBIGNUM pBigNum, uint32_t fFlags, void const *pvRaw, size_t cbRaw)
582{
583 /*
584 * Validate input.
585 */
586 AssertPtrReturn(pBigNum, VERR_INVALID_POINTER);
587 AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_BIG) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE),
588 VERR_INVALID_PARAMETER);
589 AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_UNSIGNED) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_SIGNED), VERR_INVALID_PARAMETER);
590 if (cbRaw)
591 AssertPtrReturn(pvRaw, VERR_INVALID_POINTER);
592
593 /*
594 * Initalize the big number to zero.
595 */
596 rtBigNumInitZeroInternal(pBigNum, fFlags);
597
598 /*
599 * Strip the input and figure the sign flag.
600 */
601 uint8_t const *pb = (uint8_t const *)pvRaw;
602 if (cbRaw)
603 {
604 if (fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE)
605 {
606 if (fFlags & RTBIGNUMINIT_F_UNSIGNED)
607 {
608 while (cbRaw > 0 && pb[cbRaw - 1] == 0)
609 cbRaw--;
610 }
611 else
612 {
613 if (pb[cbRaw - 1] >> 7)
614 {
615 pBigNum->fNegative = 1;
616 while (cbRaw > 1 && pb[cbRaw - 1] == 0xff)
617 cbRaw--;
618 }
619 else
620 while (cbRaw > 0 && pb[cbRaw - 1] == 0)
621 cbRaw--;
622 }
623 }
624 else
625 {
626 if (fFlags & RTBIGNUMINIT_F_UNSIGNED)
627 {
628 while (cbRaw > 0 && *pb == 0)
629 pb++, cbRaw--;
630 }
631 else
632 {
633 if (*pb >> 7)
634 {
635 pBigNum->fNegative = 1;
636 while (cbRaw > 1 && *pb == 0xff)
637 pb++, cbRaw--;
638 }
639 else
640 while (cbRaw > 0 && *pb == 0)
641 pb++, cbRaw--;
642 }
643 }
644 }
645
646 /*
647 * Allocate memory for the elements.
648 */
649 size_t cbAligned = RT_ALIGN_Z(cbRaw, RTBIGNUM_ELEMENT_SIZE);
650 if (RT_UNLIKELY(cbAligned >= RTBIGNUM_MAX_SIZE))
651 return VERR_OUT_OF_RANGE;
652 pBigNum->cUsed = (uint32_t)cbAligned / RTBIGNUM_ELEMENT_SIZE;
653 if (pBigNum->cUsed)
654 {
655 pBigNum->cAllocated = RT_ALIGN_32(pBigNum->cUsed, RTBIGNUM_ALIGNMENT);
656 if (pBigNum->fSensitive)
657 pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemSaferAllocZ(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
658 else
659 pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemAlloc(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
660 if (RT_UNLIKELY(!pBigNum->pauElements))
661 return VERR_NO_MEMORY;
662
663 /*
664 * Initialize the array.
665 */
666 uint32_t i = 0;
667 if (fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE)
668 {
669 while (cbRaw >= RTBIGNUM_ELEMENT_SIZE)
670 {
671#if RTBIGNUM_ELEMENT_SIZE == 8
672 pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[0], pb[1], pb[2], pb[3], pb[4], pb[5], pb[6], pb[7]);
673#elif RTBIGNUM_ELEMENT_SIZE == 4
674 pBigNum->pauElements[i] = RT_MAKE_U32_FROM_U8(pb[0], pb[1], pb[2], pb[3]);
675#else
676# error "Bad RTBIGNUM_ELEMENT_SIZE value"
677#endif
678 i++;
679 pb += RTBIGNUM_ELEMENT_SIZE;
680 cbRaw -= RTBIGNUM_ELEMENT_SIZE;
681 }
682
683 if (cbRaw > 0)
684 {
685 RTBIGNUMELEMENT uLast = pBigNum->fNegative ? ~(RTBIGNUMELEMENT)0 : 0;
686 switch (cbRaw)
687 {
688 default: AssertFailed();
689#if RTBIGNUM_ELEMENT_SIZE == 8
690 RT_FALL_THRU();
691 case 7: uLast = (uLast << 8) | pb[6]; RT_FALL_THRU();
692 case 6: uLast = (uLast << 8) | pb[5]; RT_FALL_THRU();
693 case 5: uLast = (uLast << 8) | pb[4]; RT_FALL_THRU();
694 case 4: uLast = (uLast << 8) | pb[3];
695#endif
696 RT_FALL_THRU();
697 case 3: uLast = (uLast << 8) | pb[2]; RT_FALL_THRU();
698 case 2: uLast = (uLast << 8) | pb[1]; RT_FALL_THRU();
699 case 1: uLast = (uLast << 8) | pb[0];
700 }
701 pBigNum->pauElements[i] = uLast;
702 }
703 }
704 else
705 {
706 pb += cbRaw;
707 while (cbRaw >= RTBIGNUM_ELEMENT_SIZE)
708 {
709 pb -= RTBIGNUM_ELEMENT_SIZE;
710#if RTBIGNUM_ELEMENT_SIZE == 8
711 pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[7], pb[6], pb[5], pb[4], pb[3], pb[2], pb[1], pb[0]);
712#elif RTBIGNUM_ELEMENT_SIZE == 4
713 pBigNum->pauElements[i] = RT_MAKE_U32_FROM_U8(pb[3], pb[2], pb[1], pb[0]);
714#else
715# error "Bad RTBIGNUM_ELEMENT_SIZE value"
716#endif
717 i++;
718 cbRaw -= RTBIGNUM_ELEMENT_SIZE;
719 }
720
721 if (cbRaw > 0)
722 {
723 RTBIGNUMELEMENT uLast = pBigNum->fNegative ? ~(RTBIGNUMELEMENT)0 : 0;
724 pb -= cbRaw;
725 switch (cbRaw)
726 {
727 default: AssertFailed();
728#if RTBIGNUM_ELEMENT_SIZE == 8
729 RT_FALL_THRU();
730 case 7: uLast = (uLast << 8) | *pb++; RT_FALL_THRU();
731 case 6: uLast = (uLast << 8) | *pb++; RT_FALL_THRU();
732 case 5: uLast = (uLast << 8) | *pb++; RT_FALL_THRU();
733 case 4: uLast = (uLast << 8) | *pb++;
734#endif
735 RT_FALL_THRU();
736 case 3: uLast = (uLast << 8) | *pb++; RT_FALL_THRU();
737 case 2: uLast = (uLast << 8) | *pb++; RT_FALL_THRU();
738 case 1: uLast = (uLast << 8) | *pb++;
739 }
740 pBigNum->pauElements[i] = uLast;
741 }
742 }
743
744 /*
745 * If negative, negate it so we get a positive magnitude value in pauElements.
746 */
747 if (pBigNum->fNegative)
748 {
749 pBigNum->pauElements[0] = 0U - pBigNum->pauElements[0];
750 for (i = 1; i < pBigNum->cUsed; i++)
751 pBigNum->pauElements[i] = 0U - pBigNum->pauElements[i] - 1U;
752 }
753
754 /*
755 * Clear unused elements.
756 */
757 if (pBigNum->cUsed != pBigNum->cAllocated)
758 {
759 RTBIGNUMELEMENT *puUnused = &pBigNum->pauElements[pBigNum->cUsed];
760 AssertCompile(RTBIGNUM_ALIGNMENT <= 4);
761 switch (pBigNum->cAllocated - pBigNum->cUsed)
762 {
763 default: AssertFailed(); RT_FALL_THRU();
764 case 3: *puUnused++ = 0; RT_FALL_THRU();
765 case 2: *puUnused++ = 0; RT_FALL_THRU();
766 case 1: *puUnused++ = 0;
767 }
768 }
769 RTBIGNUM_ASSERT_VALID(pBigNum);
770 }
771
772 rtBigNumScramble(pBigNum);
773 return VINF_SUCCESS;
774}
775
776
777RTDECL(int) RTBigNumInitZero(PRTBIGNUM pBigNum, uint32_t fFlags)
778{
779 AssertReturn(!(fFlags & ~RTBIGNUMINIT_F_SENSITIVE), VERR_INVALID_PARAMETER);
780 AssertPtrReturn(pBigNum, VERR_INVALID_POINTER);
781
782 rtBigNumInitZeroInternal(pBigNum, fFlags);
783 rtBigNumScramble(pBigNum);
784 return VINF_SUCCESS;
785}
786
787
788/**
789 * Internal clone function that assumes the caller takes care of scrambling.
790 *
791 * @returns IPRT status code.
792 * @param pBigNum The target number.
793 * @param pSrc The source number.
794 */
795static int rtBigNumCloneInternal(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc)
796{
797 Assert(!pSrc->fCurScrambled);
798 int rc = VINF_SUCCESS;
799
800 /*
801 * Copy over the data.
802 */
803 RT_ZERO(*pBigNum);
804 pBigNum->fNegative = pSrc->fNegative;
805 pBigNum->fSensitive = pSrc->fSensitive;
806 pBigNum->cUsed = pSrc->cUsed;
807 if (pSrc->cUsed)
808 {
809 /* Duplicate the element array. */
810 pBigNum->cAllocated = RT_ALIGN_32(pBigNum->cUsed, RTBIGNUM_ALIGNMENT);
811 if (pBigNum->fSensitive)
812 pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemSaferAllocZ(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
813 else
814 pBigNum->pauElements = (RTBIGNUMELEMENT *)RTMemAlloc(pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
815 if (RT_LIKELY(pBigNum->pauElements))
816 {
817 memcpy(pBigNum->pauElements, pSrc->pauElements, pBigNum->cUsed * RTBIGNUM_ELEMENT_SIZE);
818 if (pBigNum->cUsed != pBigNum->cAllocated)
819 RT_BZERO(&pBigNum->pauElements[pBigNum->cUsed], (pBigNum->cAllocated - pBigNum->cUsed) * RTBIGNUM_ELEMENT_SIZE);
820 }
821 else
822 {
823 RT_ZERO(*pBigNum);
824 rc = VERR_NO_MEMORY;
825 }
826 }
827 return rc;
828}
829
830
831RTDECL(int) RTBigNumClone(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc)
832{
833 int rc = rtBigNumUnscramble((PRTBIGNUM)pSrc);
834 if (RT_SUCCESS(rc))
835 {
836 RTBIGNUM_ASSERT_VALID(pSrc);
837 rc = rtBigNumCloneInternal(pBigNum, pSrc);
838 if (RT_SUCCESS(rc))
839 rtBigNumScramble(pBigNum);
840 rtBigNumScramble((PRTBIGNUM)pSrc);
841 }
842 return rc;
843}
844
845
846RTDECL(int) RTBigNumDestroy(PRTBIGNUM pBigNum)
847{
848 if (pBigNum)
849 {
850 if (pBigNum->pauElements)
851 {
852 Assert(pBigNum->cAllocated > 0);
853 if (!pBigNum->fSensitive)
854 RTMemFree(pBigNum->pauElements);
855 else
856 {
857 RTMemSaferFree(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
858 RT_ZERO(*pBigNum);
859 }
860 pBigNum->pauElements = NULL;
861 }
862 }
863 return VINF_SUCCESS;
864}
865
866
867RTDECL(int) RTBigNumAssign(PRTBIGNUM pDst, PCRTBIGNUM pSrc)
868{
869 AssertReturn(pDst->fSensitive >= pSrc->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
870 int rc = rtBigNumUnscramble(pDst);
871 if (RT_SUCCESS(rc))
872 {
873 RTBIGNUM_ASSERT_VALID(pDst);
874 rc = rtBigNumUnscramble((PRTBIGNUM)pSrc);
875 if (RT_SUCCESS(rc))
876 {
877 RTBIGNUM_ASSERT_VALID(pSrc);
878 if ( pDst->fSensitive == pSrc->fSensitive
879 || pDst->fSensitive)
880 {
881 if (pDst->cAllocated >= pSrc->cUsed)
882 {
883 if (pDst->cUsed > pSrc->cUsed)
884 RT_BZERO(&pDst->pauElements[pSrc->cUsed], (pDst->cUsed - pSrc->cUsed) * RTBIGNUM_ELEMENT_SIZE);
885 pDst->cUsed = pSrc->cUsed;
886 pDst->fNegative = pSrc->fNegative;
887 memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
888 }
889 else
890 {
891 rc = rtBigNumGrow(pDst, pSrc->cUsed, pSrc->cUsed);
892 if (RT_SUCCESS(rc))
893 {
894 pDst->fNegative = pSrc->fNegative;
895 memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
896 }
897 }
898 }
899 else
900 rc = VERR_BIGNUM_SENSITIVE_INPUT;
901 rtBigNumScramble((PRTBIGNUM)pSrc);
902 }
903 rtBigNumScramble(pDst);
904 }
905 return rc;
906}
907
908
909/**
910 * Same as RTBigNumBitWidth, except that it ignore the signed bit.
911 *
912 * The number must be unscrambled.
913 *
914 * @returns The effective width of the magnitude, in bits. Returns 0 if the
915 * value is zero.
916 * @param pBigNum The bit number.
917 */
918static uint32_t rtBigNumMagnitudeBitWidth(PCRTBIGNUM pBigNum)
919{
920 uint32_t idxLast = pBigNum->cUsed;
921 if (idxLast)
922 {
923 idxLast--;
924 RTBIGNUMELEMENT uLast = pBigNum->pauElements[idxLast]; Assert(uLast);
925 return rtBigNumElementBitCount(uLast) + idxLast * RTBIGNUM_ELEMENT_BITS;
926 }
927 return 0;
928}
929
930
931RTDECL(uint32_t) RTBigNumBitWidth(PCRTBIGNUM pBigNum)
932{
933 uint32_t idxLast = pBigNum->cUsed;
934 if (idxLast)
935 {
936 idxLast--;
937 rtBigNumUnscramble((PRTBIGNUM)pBigNum);
938 RTBIGNUMELEMENT uLast = pBigNum->pauElements[idxLast]; Assert(uLast);
939 rtBigNumScramble((PRTBIGNUM)pBigNum);
940 return rtBigNumElementBitCount(uLast) + idxLast * RTBIGNUM_ELEMENT_BITS + pBigNum->fNegative;
941 }
942 return 0;
943}
944
945
946RTDECL(uint32_t) RTBigNumByteWidth(PCRTBIGNUM pBigNum)
947{
948 uint32_t cBits = RTBigNumBitWidth(pBigNum);
949 return (cBits + 7) / 8;
950}
951
952
953RTDECL(int) RTBigNumToBytesBigEndian(PCRTBIGNUM pBigNum, void *pvBuf, size_t cbWanted)
954{
955 AssertPtrReturn(pvBuf, VERR_INVALID_POINTER);
956 AssertReturn(cbWanted > 0, VERR_INVALID_PARAMETER);
957
958 int rc = rtBigNumUnscramble((PRTBIGNUM)pBigNum);
959 if (RT_SUCCESS(rc))
960 {
961 RTBIGNUM_ASSERT_VALID(pBigNum);
962 rc = VINF_SUCCESS;
963 if (pBigNum->cUsed != 0)
964 {
965 uint8_t *pbDst = (uint8_t *)pvBuf;
966 pbDst += cbWanted - 1;
967 for (uint32_t i = 0; i < pBigNum->cUsed; i++)
968 {
969 RTBIGNUMELEMENT uElement = pBigNum->pauElements[i];
970 if (pBigNum->fNegative)
971 uElement = (RTBIGNUMELEMENT)0 - uElement - (i > 0);
972 if (cbWanted >= sizeof(uElement))
973 {
974 *pbDst-- = (uint8_t)uElement;
975 uElement >>= 8;
976 *pbDst-- = (uint8_t)uElement;
977 uElement >>= 8;
978 *pbDst-- = (uint8_t)uElement;
979 uElement >>= 8;
980 *pbDst-- = (uint8_t)uElement;
981#if RTBIGNUM_ELEMENT_SIZE == 8
982 uElement >>= 8;
983 *pbDst-- = (uint8_t)uElement;
984 uElement >>= 8;
985 *pbDst-- = (uint8_t)uElement;
986 uElement >>= 8;
987 *pbDst-- = (uint8_t)uElement;
988 uElement >>= 8;
989 *pbDst-- = (uint8_t)uElement;
990#elif RTBIGNUM_ELEMENT_SIZE != 4
991# error "Bad RTBIGNUM_ELEMENT_SIZE value"
992#endif
993 cbWanted -= sizeof(uElement);
994 }
995 else
996 {
997
998 uint32_t cBitsLeft = RTBIGNUM_ELEMENT_BITS;
999 while (cbWanted > 0)
1000 {
1001 *pbDst-- = (uint8_t)uElement;
1002 uElement >>= 8;
1003 cBitsLeft -= 8;
1004 cbWanted--;
1005 }
1006 Assert(cBitsLeft > 0); Assert(cBitsLeft < RTBIGNUM_ELEMENT_BITS);
1007 if ( i + 1 < pBigNum->cUsed
1008 || ( !pBigNum->fNegative
1009 ? uElement != 0
1010 : uElement != ((RTBIGNUMELEMENT)1 << cBitsLeft) - 1U ) )
1011 rc = VERR_BUFFER_OVERFLOW;
1012 break;
1013 }
1014 }
1015
1016 /* Sign extend the number to the desired output size. */
1017 if (cbWanted > 0)
1018 memset(pbDst - cbWanted, pBigNum->fNegative ? 0 : 0xff, cbWanted);
1019 }
1020 else
1021 RT_BZERO(pvBuf, cbWanted);
1022 rtBigNumScramble((PRTBIGNUM)pBigNum);
1023 }
1024 return rc;
1025}
1026
1027
1028RTDECL(int) RTBigNumCompare(PRTBIGNUM pLeft, PRTBIGNUM pRight)
1029{
1030 int rc = rtBigNumUnscramble(pLeft);
1031 if (RT_SUCCESS(rc))
1032 {
1033 RTBIGNUM_ASSERT_VALID(pLeft);
1034 rc = rtBigNumUnscramble(pRight);
1035 if (RT_SUCCESS(rc))
1036 {
1037 RTBIGNUM_ASSERT_VALID(pRight);
1038 if (pLeft->fNegative == pRight->fNegative)
1039 {
1040 if (pLeft->cUsed == pRight->cUsed)
1041 {
1042 rc = 0;
1043 uint32_t i = pLeft->cUsed;
1044 while (i-- > 0)
1045 if (pLeft->pauElements[i] != pRight->pauElements[i])
1046 {
1047 rc = pLeft->pauElements[i] < pRight->pauElements[i] ? -1 : 1;
1048 break;
1049 }
1050 if (pLeft->fNegative)
1051 rc = -rc;
1052 }
1053 else
1054 rc = !pLeft->fNegative
1055 ? pLeft->cUsed < pRight->cUsed ? -1 : 1
1056 : pLeft->cUsed < pRight->cUsed ? 1 : -1;
1057 }
1058 else
1059 rc = pLeft->fNegative ? -1 : 1;
1060
1061 rtBigNumScramble(pRight);
1062 }
1063 rtBigNumScramble(pLeft);
1064 }
1065 return rc;
1066}
1067
1068
1069RTDECL(int) RTBigNumCompareWithU64(PRTBIGNUM pLeft, uint64_t uRight)
1070{
1071 int rc = rtBigNumUnscramble(pLeft);
1072 if (RT_SUCCESS(rc))
1073 {
1074 RTBIGNUM_ASSERT_VALID(pLeft);
1075 if (!pLeft->fNegative)
1076 {
1077 if (pLeft->cUsed * RTBIGNUM_ELEMENT_SIZE <= sizeof(uRight))
1078 {
1079 if (pLeft->cUsed == 0)
1080 rc = uRight == 0 ? 0 : -1;
1081 else
1082 {
1083#if RTBIGNUM_ELEMENT_SIZE == 8
1084 uint64_t uLeft = rtBigNumGetElement(pLeft, 0);
1085 if (uLeft < uRight)
1086 rc = -1;
1087 else
1088 rc = uLeft == uRight ? 0 : 1;
1089#elif RTBIGNUM_ELEMENT_SIZE == 4
1090 uint32_t uSubLeft = rtBigNumGetElement(pLeft, 1);
1091 uint32_t uSubRight = uRight >> 32;
1092 if (uSubLeft == uSubRight)
1093 {
1094 uSubLeft = rtBigNumGetElement(pLeft, 0);
1095 uSubRight = (uint32_t)uRight;
1096 }
1097 if (uSubLeft < uSubRight)
1098 rc = -1;
1099 else
1100 rc = uSubLeft == uSubRight ? 0 : 1;
1101#else
1102# error "Bad RTBIGNUM_ELEMENT_SIZE value"
1103#endif
1104 }
1105 }
1106 else
1107 rc = 1;
1108 }
1109 else
1110 rc = -1;
1111 rtBigNumScramble(pLeft);
1112 }
1113 return rc;
1114}
1115
1116
1117RTDECL(int) RTBigNumCompareWithS64(PRTBIGNUM pLeft, int64_t iRight)
1118{
1119 int rc = rtBigNumUnscramble(pLeft);
1120 if (RT_SUCCESS(rc))
1121 {
1122 RTBIGNUM_ASSERT_VALID(pLeft);
1123 if (pLeft->fNegative == (unsigned)(iRight < 0)) /* (unsigned cast is for MSC weirdness) */
1124 {
1125 AssertCompile(RTBIGNUM_ELEMENT_SIZE <= sizeof(iRight));
1126 if (pLeft->cUsed * RTBIGNUM_ELEMENT_SIZE <= sizeof(iRight))
1127 {
1128 uint64_t uRightMagn = !pLeft->fNegative ? (uint64_t)iRight : (uint64_t)-iRight;
1129#if RTBIGNUM_ELEMENT_SIZE == 8
1130 uint64_t uLeft = rtBigNumGetElement(pLeft, 0);
1131 if (uLeft < uRightMagn)
1132 rc = -1;
1133 else
1134 rc = uLeft == (uint64_t)uRightMagn ? 0 : 1;
1135#elif RTBIGNUM_ELEMENT_SIZE == 4
1136 uint32_t uSubLeft = rtBigNumGetElement(pLeft, 1);
1137 uint32_t uSubRight = uRightMagn >> 32;
1138 if (uSubLeft == uSubRight)
1139 {
1140 uSubLeft = rtBigNumGetElement(pLeft, 0);
1141 uSubRight = (uint32_t)uRightMagn;
1142 }
1143 if (uSubLeft < uSubRight)
1144 rc = -1;
1145 else
1146 rc = uSubLeft == uSubRight ? 0 : 1;
1147#else
1148# error "Bad RTBIGNUM_ELEMENT_SIZE value"
1149#endif
1150 if (pLeft->fNegative)
1151 rc = -rc;
1152 }
1153 else
1154 rc = pLeft->fNegative ? -1 : 1;
1155 }
1156 else
1157 rc = pLeft->fNegative ? -1 : 1;
1158 rtBigNumScramble(pLeft);
1159 }
1160 return rc;
1161}
1162
1163
1164/**
1165 * Compares the magnitude values of two big numbers.
1166 *
1167 * @retval -1 if pLeft is smaller than pRight.
1168 * @retval 0 if pLeft is equal to pRight.
1169 * @retval 1 if pLeft is larger than pRight.
1170 * @param pLeft The left side number.
1171 * @param pRight The right side number.
1172 */
1173static int rtBigNumMagnitudeCompare(PCRTBIGNUM pLeft, PCRTBIGNUM pRight)
1174{
1175 Assert(!pLeft->fCurScrambled); Assert(!pRight->fCurScrambled);
1176 int rc;
1177 uint32_t i = pLeft->cUsed;
1178 if (i == pRight->cUsed)
1179 {
1180 rc = 0;
1181 while (i-- > 0)
1182 if (pLeft->pauElements[i] != pRight->pauElements[i])
1183 {
1184 rc = pLeft->pauElements[i] < pRight->pauElements[i] ? -1 : 1;
1185 break;
1186 }
1187 }
1188 else
1189 rc = i < pRight->cUsed ? -1 : 1;
1190 return rc;
1191}
1192
1193
1194/**
1195 * Copies the magnitude of on number (@a pSrc) to another (@a pBigNum).
1196 *
1197 * The variables must be unscrambled. The sign flag is not considered nor
1198 * touched.
1199 *
1200 * @returns IPRT status code.
1201 * @param pDst The destination number.
1202 * @param pSrc The source number.
1203 */
1204DECLINLINE(int) rtBigNumMagnitudeCopy(PRTBIGNUM pDst, PCRTBIGNUM pSrc)
1205{
1206 int rc = rtBigNumSetUsed(pDst, pSrc->cUsed);
1207 if (RT_SUCCESS(rc))
1208 memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
1209 return rc;
1210}
1211
1212
1213
1214/**
1215 * Adds two magnitudes and stores them into a third.
1216 *
1217 * All variables must be unscrambled. The sign flag is not considered nor
1218 * touched.
1219 *
1220 * @returns IPRT status code.
1221 * @param pResult The resultant.
1222 * @param pAugend To whom it shall be addede.
1223 * @param pAddend The nombre to addede.
1224 */
1225static int rtBigNumMagnitudeAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend)
1226{
1227 Assert(!pResult->fCurScrambled); Assert(!pAugend->fCurScrambled); Assert(!pAddend->fCurScrambled);
1228 Assert(pResult != pAugend); Assert(pResult != pAddend);
1229
1230 uint32_t cElements = RT_MAX(pAugend->cUsed, pAddend->cUsed);
1231 int rc = rtBigNumSetUsed(pResult, cElements);
1232 if (RT_SUCCESS(rc))
1233 {
1234 /*
1235 * The primitive way, requires at least two additions for each entry
1236 * without machine code help.
1237 */
1238 RTBIGNUMELEMENT fCarry = 0;
1239 for (uint32_t i = 0; i < cElements; i++)
1240 pResult->pauElements[i] = rtBigNumElementAddWithCarry(rtBigNumGetElement(pAugend, i),
1241 rtBigNumGetElement(pAddend, i),
1242 &fCarry);
1243 if (fCarry)
1244 {
1245 rc = rtBigNumSetUsed(pResult, cElements + 1);
1246 if (RT_SUCCESS(rc))
1247 pResult->pauElements[cElements++] = 1;
1248 }
1249 Assert(pResult->cUsed == cElements || RT_FAILURE_NP(rc));
1250 }
1251
1252 return rc;
1253}
1254
1255
1256/**
1257 * Substracts a smaller (or equal) magnitude from another one and stores it into
1258 * a third.
1259 *
1260 * All variables must be unscrambled. The sign flag is not considered nor
1261 * touched. For this reason, the @a pMinuend must be larger or equal to @a
1262 * pSubtrahend.
1263 *
1264 * @returns IPRT status code.
1265 * @param pResult There to store the result.
1266 * @param pMinuend What to subtract from.
1267 * @param pSubtrahend What to subtract.
1268 */
1269static int rtBigNumMagnitudeSub(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend)
1270{
1271 Assert(!pResult->fCurScrambled); Assert(!pMinuend->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
1272 Assert(pResult != pMinuend); Assert(pResult != pSubtrahend);
1273 Assert(pMinuend->cUsed >= pSubtrahend->cUsed);
1274
1275 int rc;
1276 if (pSubtrahend->cUsed)
1277 {
1278 /*
1279 * Resize the result. In the assembly case, ensure that all three arrays
1280 * has the same number of used entries, possibly with an extra zero
1281 * element on 64-bit systems.
1282 */
1283 rc = rtBigNumSetUsedEx(pResult, pMinuend->cUsed, RTBIGNUM_ZERO_ALIGN(pMinuend->cUsed));
1284#ifdef IPRT_BIGINT_WITH_ASM
1285 if (RT_SUCCESS(rc))
1286 rc = rtBigNumEnsureExtraZeroElements((PRTBIGNUM)pMinuend, RTBIGNUM_ZERO_ALIGN(pMinuend->cUsed));
1287 if (RT_SUCCESS(rc))
1288 rc = rtBigNumEnsureExtraZeroElements((PRTBIGNUM)pSubtrahend, RTBIGNUM_ZERO_ALIGN(pMinuend->cUsed));
1289#endif
1290 if (RT_SUCCESS(rc))
1291 {
1292#ifdef IPRT_BIGINT_WITH_ASM
1293 /*
1294 * Call assembly to do the work.
1295 */
1296 rtBigNumMagnitudeSubAssemblyWorker(pResult->pauElements, pMinuend->pauElements,
1297 pSubtrahend->pauElements, pMinuend->cUsed);
1298# ifdef RT_STRICT
1299 RTBIGNUMELEMENT fBorrow = 0;
1300 for (uint32_t i = 0; i < pMinuend->cUsed; i++)
1301 {
1302 RTBIGNUMELEMENT uCorrect = rtBigNumElementSubWithBorrow(pMinuend->pauElements[i], rtBigNumGetElement(pSubtrahend, i), &fBorrow);
1303 AssertMsg(pResult->pauElements[i] == uCorrect, ("[%u]=%#x, expected %#x\n", i, pResult->pauElements[i], uCorrect));
1304 }
1305# endif
1306#else
1307 /*
1308 * The primitive C way.
1309 */
1310 RTBIGNUMELEMENT fBorrow = 0;
1311 for (uint32_t i = 0; i < pMinuend->cUsed; i++)
1312 pResult->pauElements[i] = rtBigNumElementSubWithBorrow(pMinuend->pauElements[i],
1313 rtBigNumGetElement(pSubtrahend, i),
1314 &fBorrow);
1315 Assert(fBorrow == 0);
1316#endif
1317
1318 /*
1319 * Trim the result.
1320 */
1321 rtBigNumStripTrailingZeros(pResult);
1322 }
1323 }
1324 /*
1325 * Special case: Subtrahend is zero.
1326 */
1327 else
1328 rc = rtBigNumMagnitudeCopy(pResult, pMinuend);
1329
1330 return rc;
1331}
1332
1333
1334/**
1335 * Substracts a smaller (or equal) magnitude from another one and stores the
1336 * result into the first.
1337 *
1338 * All variables must be unscrambled. The sign flag is not considered nor
1339 * touched. For this reason, the @a pMinuendResult must be larger or equal to
1340 * @a pSubtrahend.
1341 *
1342 * @returns IPRT status code (memory alloc error).
1343 * @param pMinuendResult What to subtract from and return as result.
1344 * @param pSubtrahend What to subtract.
1345 */
1346static int rtBigNumMagnitudeSubThis(PRTBIGNUM pMinuendResult, PCRTBIGNUM pSubtrahend)
1347{
1348 Assert(!pMinuendResult->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
1349 Assert(pMinuendResult != pSubtrahend);
1350 Assert(pMinuendResult->cUsed >= pSubtrahend->cUsed);
1351
1352#ifdef IPRT_BIGINT_WITH_ASM
1353 /*
1354 * Use the assembly worker. Requires same sized element arrays, so zero extend them.
1355 */
1356 int rc = rtBigNumEnsureExtraZeroElements(pMinuendResult, RTBIGNUM_ZERO_ALIGN(pMinuendResult->cUsed));
1357 if (RT_SUCCESS(rc))
1358 rc = rtBigNumEnsureExtraZeroElements((PRTBIGNUM)pSubtrahend, RTBIGNUM_ZERO_ALIGN(pMinuendResult->cUsed));
1359 if (RT_FAILURE(rc))
1360 return rc;
1361 rtBigNumMagnitudeSubThisAssemblyWorker(pMinuendResult->pauElements, pSubtrahend->pauElements, pMinuendResult->cUsed);
1362#else
1363 /*
1364 * The primitive way, as usual.
1365 */
1366 RTBIGNUMELEMENT fBorrow = 0;
1367 for (uint32_t i = 0; i < pMinuendResult->cUsed; i++)
1368 pMinuendResult->pauElements[i] = rtBigNumElementSubWithBorrow(pMinuendResult->pauElements[i],
1369 rtBigNumGetElement(pSubtrahend, i),
1370 &fBorrow);
1371 Assert(fBorrow == 0);
1372#endif
1373
1374 /*
1375 * Trim the result.
1376 */
1377 rtBigNumStripTrailingZeros(pMinuendResult);
1378
1379 return VINF_SUCCESS;
1380}
1381
1382
1383RTDECL(int) RTBigNumAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend)
1384{
1385 Assert(pResult != pAugend); Assert(pResult != pAddend);
1386 AssertReturn(pResult->fSensitive >= (pAugend->fSensitive | pAddend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1387
1388 int rc = rtBigNumUnscramble(pResult);
1389 if (RT_SUCCESS(rc))
1390 {
1391 RTBIGNUM_ASSERT_VALID(pResult);
1392 rc = rtBigNumUnscramble((PRTBIGNUM)pAugend);
1393 if (RT_SUCCESS(rc))
1394 {
1395 RTBIGNUM_ASSERT_VALID(pAugend);
1396 rc = rtBigNumUnscramble((PRTBIGNUM)pAddend);
1397 if (RT_SUCCESS(rc))
1398 {
1399 RTBIGNUM_ASSERT_VALID(pAddend);
1400
1401 /*
1402 * Same sign: Add magnitude, keep sign.
1403 * 1 + 1 = 2
1404 * (-1) + (-1) = -2
1405 */
1406 if (pAugend->fNegative == pAddend->fNegative)
1407 {
1408 pResult->fNegative = pAugend->fNegative;
1409 rc = rtBigNumMagnitudeAdd(pResult, pAugend, pAddend);
1410 }
1411 /*
1412 * Different sign: Subtract smaller from larger, keep sign of larger.
1413 * (-5) + 3 = -2
1414 * 5 + (-3) = 2
1415 * (-1) + 3 = 2
1416 * 1 + (-3) = -2
1417 */
1418 else if (rtBigNumMagnitudeCompare(pAugend, pAddend) >= 0)
1419 {
1420 pResult->fNegative = pAugend->fNegative;
1421 rc = rtBigNumMagnitudeSub(pResult, pAugend, pAddend);
1422 if (!pResult->cUsed)
1423 pResult->fNegative = 0;
1424 }
1425 else
1426 {
1427 pResult->fNegative = pAddend->fNegative;
1428 rc = rtBigNumMagnitudeSub(pResult, pAddend, pAugend);
1429 }
1430 rtBigNumScramble((PRTBIGNUM)pAddend);
1431 }
1432 rtBigNumScramble((PRTBIGNUM)pAugend);
1433 }
1434 rtBigNumScramble(pResult);
1435 }
1436 return rc;
1437}
1438
1439
1440RTDECL(int) RTBigNumSubtract(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend)
1441{
1442 Assert(pResult != pMinuend); Assert(pResult != pSubtrahend);
1443 AssertReturn(pResult->fSensitive >= (pMinuend->fSensitive | pSubtrahend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1444
1445 int rc = rtBigNumUnscramble(pResult);
1446 if (RT_SUCCESS(rc))
1447 {
1448 RTBIGNUM_ASSERT_VALID(pResult);
1449 if (pMinuend != pSubtrahend)
1450 {
1451 rc = rtBigNumUnscramble((PRTBIGNUM)pMinuend);
1452 if (RT_SUCCESS(rc))
1453 {
1454 RTBIGNUM_ASSERT_VALID(pMinuend);
1455 rc = rtBigNumUnscramble((PRTBIGNUM)pSubtrahend);
1456 if (RT_SUCCESS(rc))
1457 {
1458 RTBIGNUM_ASSERT_VALID(pSubtrahend);
1459
1460 /*
1461 * Different sign: Add magnitude, keep sign of first.
1462 * 1 - (-2) == 3
1463 * -1 - 2 == -3
1464 */
1465 if (pMinuend->fNegative != pSubtrahend->fNegative)
1466 {
1467 pResult->fNegative = pMinuend->fNegative;
1468 rc = rtBigNumMagnitudeAdd(pResult, pMinuend, pSubtrahend);
1469 }
1470 /*
1471 * Same sign, minuend has greater or equal absolute value: Subtract, keep sign of first.
1472 * 10 - 7 = 3
1473 */
1474 else if (rtBigNumMagnitudeCompare(pMinuend, pSubtrahend) >= 0)
1475 {
1476 pResult->fNegative = pMinuend->fNegative;
1477 rc = rtBigNumMagnitudeSub(pResult, pMinuend, pSubtrahend);
1478 }
1479 /*
1480 * Same sign, subtrahend is larger: Reverse and subtract, invert sign of first.
1481 * 7 - 10 = -3
1482 * -1 - (-3) = 2
1483 */
1484 else
1485 {
1486 pResult->fNegative = !pMinuend->fNegative;
1487 rc = rtBigNumMagnitudeSub(pResult, pSubtrahend, pMinuend);
1488 }
1489 rtBigNumScramble((PRTBIGNUM)pSubtrahend);
1490 }
1491 rtBigNumScramble((PRTBIGNUM)pMinuend);
1492 }
1493 }
1494 else
1495 {
1496 /* zero. */
1497 pResult->fNegative = 0;
1498 rtBigNumSetUsed(pResult, 0);
1499 }
1500 rtBigNumScramble(pResult);
1501 }
1502 return rc;
1503}
1504
1505
1506RTDECL(int) RTBigNumNegateThis(PRTBIGNUM pThis)
1507{
1508 pThis->fNegative = !pThis->fNegative;
1509 return VINF_SUCCESS;
1510}
1511
1512
1513RTDECL(int) RTBigNumNegate(PRTBIGNUM pResult, PCRTBIGNUM pBigNum)
1514{
1515 int rc = RTBigNumAssign(pResult, pBigNum);
1516 if (RT_SUCCESS(rc))
1517 rc = RTBigNumNegateThis(pResult);
1518 return rc;
1519}
1520
1521
1522/**
1523 * Multiplies the magnitudes of two values, letting the caller care about the
1524 * sign bit.
1525 *
1526 * @returns IPRT status code.
1527 * @param pResult Where to store the result.
1528 * @param pMultiplicand The first value.
1529 * @param pMultiplier The second value.
1530 */
1531static int rtBigNumMagnitudeMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
1532{
1533 Assert(pResult != pMultiplicand); Assert(pResult != pMultiplier);
1534 Assert(!pResult->fCurScrambled); Assert(!pMultiplicand->fCurScrambled); Assert(!pMultiplier->fCurScrambled);
1535
1536 /*
1537 * Multiplication involving zero is zero.
1538 */
1539 if (!pMultiplicand->cUsed || !pMultiplier->cUsed)
1540 {
1541 pResult->fNegative = 0;
1542 rtBigNumSetUsed(pResult, 0);
1543 return VINF_SUCCESS;
1544 }
1545
1546 /*
1547 * Allocate a result array that is the sum of the two factors, initialize
1548 * it to zero.
1549 */
1550 uint32_t cMax = pMultiplicand->cUsed + pMultiplier->cUsed;
1551 int rc = rtBigNumSetUsed(pResult, cMax);
1552 if (RT_SUCCESS(rc))
1553 {
1554 RT_BZERO(pResult->pauElements, pResult->cUsed * RTBIGNUM_ELEMENT_SIZE);
1555
1556#ifdef IPRT_BIGINT_WITH_ASM
1557 rtBigNumMagnitudeMultiplyAssemblyWorker(pResult->pauElements,
1558 pMultiplier->pauElements, pMultiplier->cUsed,
1559 pMultiplicand->pauElements, pMultiplicand->cUsed);
1560#else
1561 for (uint32_t i = 0; i < pMultiplier->cUsed; i++)
1562 {
1563 RTBIGNUMELEMENT uMultiplier = pMultiplier->pauElements[i];
1564 for (uint32_t j = 0; j < pMultiplicand->cUsed; j++)
1565 {
1566 RTBIGNUMELEMENT uHi;
1567 RTBIGNUMELEMENT uLo;
1568#if RTBIGNUM_ELEMENT_SIZE == 4
1569 uint64_t u64 = ASMMult2xU32RetU64(pMultiplicand->pauElements[j], uMultiplier);
1570 uLo = (uint32_t)u64;
1571 uHi = u64 >> 32;
1572#elif RTBIGNUM_ELEMENT_SIZE == 8
1573 uLo = ASMMult2xU64Ret2xU64(pMultiplicand->pauElements[j], uMultiplier, &uHi);
1574#else
1575# error "Invalid RTBIGNUM_ELEMENT_SIZE value"
1576#endif
1577 RTBIGNUMELEMENT fCarry = 0;
1578 uint64_t k = i + j;
1579 pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], uLo, &fCarry);
1580 k++;
1581 pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], uHi, &fCarry);
1582 while (fCarry)
1583 {
1584 k++;
1585 pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], 0, &fCarry);
1586 }
1587 Assert(k < cMax);
1588 }
1589 }
1590#endif
1591
1592 /* It's possible we overestimated the output size by 1 element. */
1593 rtBigNumStripTrailingZeros(pResult);
1594 }
1595 return rc;
1596}
1597
1598
1599RTDECL(int) RTBigNumMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
1600{
1601 Assert(pResult != pMultiplicand); Assert(pResult != pMultiplier);
1602 AssertReturn(pResult->fSensitive >= (pMultiplicand->fSensitive | pMultiplier->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1603
1604 int rc = rtBigNumUnscramble(pResult);
1605 if (RT_SUCCESS(rc))
1606 {
1607 RTBIGNUM_ASSERT_VALID(pResult);
1608 rc = rtBigNumUnscramble((PRTBIGNUM)pMultiplicand);
1609 if (RT_SUCCESS(rc))
1610 {
1611 RTBIGNUM_ASSERT_VALID(pMultiplicand);
1612 rc = rtBigNumUnscramble((PRTBIGNUM)pMultiplier);
1613 if (RT_SUCCESS(rc))
1614 {
1615 RTBIGNUM_ASSERT_VALID(pMultiplier);
1616
1617 /*
1618 * The sign values follow XOR rules:
1619 * -1 * 1 = -1; 1 ^ 0 = 1
1620 * 1 * -1 = -1; 1 ^ 0 = 1
1621 * -1 * -1 = 1; 1 ^ 1 = 0
1622 * 1 * 1 = 1; 0 ^ 0 = 0
1623 */
1624 pResult->fNegative = pMultiplicand->fNegative ^ pMultiplier->fNegative;
1625 rc = rtBigNumMagnitudeMultiply(pResult, pMultiplicand, pMultiplier);
1626
1627 rtBigNumScramble((PRTBIGNUM)pMultiplier);
1628 }
1629 rtBigNumScramble((PRTBIGNUM)pMultiplicand);
1630 }
1631 rtBigNumScramble(pResult);
1632 }
1633 return rc;
1634}
1635
1636
1637#if 0 /* unused */
1638/**
1639 * Clears a bit in the magnitude of @a pBigNum.
1640 *
1641 * The variables must be unscrambled.
1642 *
1643 * @param pBigNum The big number.
1644 * @param iBit The bit to clear (0-based).
1645 */
1646DECLINLINE(void) rtBigNumMagnitudeClearBit(PRTBIGNUM pBigNum, uint32_t iBit)
1647{
1648 uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1649 if (iElement < pBigNum->cUsed)
1650 {
1651 iBit &= RTBIGNUM_ELEMENT_BITS - 1;
1652 pBigNum->pauElements[iElement] &= ~RTBIGNUM_ELEMENT_BIT(iBit);
1653 if (iElement + 1 == pBigNum->cUsed && !pBigNum->pauElements[iElement])
1654 rtBigNumStripTrailingZeros(pBigNum);
1655 }
1656}
1657#endif /* unused */
1658
1659
1660/**
1661 * Sets a bit in the magnitude of @a pBigNum.
1662 *
1663 * The variables must be unscrambled.
1664 *
1665 * @returns IPRT status code.
1666 * @param pBigNum The big number.
1667 * @param iBit The bit to clear (0-based).
1668 */
1669DECLINLINE(int) rtBigNumMagnitudeSetBit(PRTBIGNUM pBigNum, uint32_t iBit)
1670{
1671 uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1672 int rc = rtBigNumEnsureElementPresent(pBigNum, iElement);
1673 if (RT_SUCCESS(rc))
1674 {
1675 iBit &= RTBIGNUM_ELEMENT_BITS - 1;
1676 pBigNum->pauElements[iElement] |= RTBIGNUM_ELEMENT_BIT(iBit);
1677 return VINF_SUCCESS;
1678 }
1679 return rc;
1680}
1681
1682
1683#if 0 /* unused */
1684/**
1685 * Writes a bit in the magnitude of @a pBigNum.
1686 *
1687 * The variables must be unscrambled.
1688 *
1689 * @returns IPRT status code.
1690 * @param pBigNum The big number.
1691 * @param iBit The bit to write (0-based).
1692 * @param fValue The bit value.
1693 */
1694DECLINLINE(int) rtBigNumMagnitudeWriteBit(PRTBIGNUM pBigNum, uint32_t iBit, bool fValue)
1695{
1696 if (fValue)
1697 return rtBigNumMagnitudeSetBit(pBigNum, iBit);
1698 rtBigNumMagnitudeClearBit(pBigNum, iBit);
1699 return VINF_SUCCESS;
1700}
1701#endif
1702
1703
1704/**
1705 * Returns the given magnitude bit.
1706 *
1707 * The variables must be unscrambled.
1708 *
1709 * @returns The bit value (1 or 0).
1710 * @param pBigNum The big number.
1711 * @param iBit The bit to return (0-based).
1712 */
1713DECLINLINE(RTBIGNUMELEMENT) rtBigNumMagnitudeGetBit(PCRTBIGNUM pBigNum, uint32_t iBit)
1714{
1715 uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1716 if (iElement < pBigNum->cUsed)
1717 {
1718 iBit &= RTBIGNUM_ELEMENT_BITS - 1;
1719 return (pBigNum->pauElements[iElement] >> iBit) & 1;
1720 }
1721 return 0;
1722}
1723
1724
1725/**
1726 * Shifts the magnitude left by one.
1727 *
1728 * The variables must be unscrambled.
1729 *
1730 * @returns IPRT status code.
1731 * @param pBigNum The big number.
1732 * @param uCarry The value to shift in at the bottom.
1733 */
1734DECLINLINE(int) rtBigNumMagnitudeShiftLeftOne(PRTBIGNUM pBigNum, RTBIGNUMELEMENT uCarry)
1735{
1736 Assert(uCarry <= 1);
1737
1738 /* Do the shifting. */
1739 uint32_t cUsed = pBigNum->cUsed;
1740#ifdef IPRT_BIGINT_WITH_ASM
1741 uCarry = rtBigNumMagnitudeShiftLeftOneAssemblyWorker(pBigNum->pauElements, cUsed, uCarry);
1742#else
1743 for (uint32_t i = 0; i < cUsed; i++)
1744 {
1745 RTBIGNUMELEMENT uTmp = pBigNum->pauElements[i];
1746 pBigNum->pauElements[i] = (uTmp << 1) | uCarry;
1747 uCarry = uTmp >> (RTBIGNUM_ELEMENT_BITS - 1);
1748 }
1749#endif
1750
1751 /* If we still carry a bit, we need to increase the size. */
1752 if (uCarry)
1753 {
1754 int rc = rtBigNumSetUsed(pBigNum, cUsed + 1);
1755 AssertRCReturn(rc, rc);
1756 pBigNum->pauElements[cUsed] = uCarry;
1757 }
1758
1759 return VINF_SUCCESS;
1760}
1761
1762
1763/**
1764 * Shifts the magnitude left by @a cBits.
1765 *
1766 * The variables must be unscrambled.
1767 *
1768 * @returns IPRT status code.
1769 * @param pResult Where to store the result.
1770 * @param pValue The value to shift.
1771 * @param cBits The shift count.
1772 */
1773static int rtBigNumMagnitudeShiftLeft(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
1774{
1775 int rc;
1776 if (cBits)
1777 {
1778 uint32_t cBitsNew = rtBigNumMagnitudeBitWidth(pValue);
1779 if (cBitsNew > 0)
1780 {
1781 if (cBitsNew + cBits > cBitsNew)
1782 {
1783 cBitsNew += cBits;
1784 rc = rtBigNumSetUsedEx(pResult, 0, RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS);
1785 if (RT_SUCCESS(rc))
1786 rc = rtBigNumSetUsed(pResult, RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS);
1787 if (RT_SUCCESS(rc))
1788 {
1789 uint32_t const cLeft = pValue->cUsed;
1790 PCRTBIGNUMELEMENT pauSrc = pValue->pauElements;
1791 PRTBIGNUMELEMENT pauDst = pResult->pauElements;
1792
1793 Assert(ASMMemIsZero(pauDst, (cBits / RTBIGNUM_ELEMENT_BITS) * RTBIGNUM_ELEMENT_SIZE));
1794 pauDst += cBits / RTBIGNUM_ELEMENT_BITS;
1795
1796 cBits &= RTBIGNUM_ELEMENT_BITS - 1;
1797 if (cBits)
1798 {
1799 RTBIGNUMELEMENT uPrev = 0;
1800 for (uint32_t i = 0; i < cLeft; i++)
1801 {
1802 RTBIGNUMELEMENT uCur = pauSrc[i];
1803 pauDst[i] = (uCur << cBits) | (uPrev >> (RTBIGNUM_ELEMENT_BITS - cBits));
1804 uPrev = uCur;
1805 }
1806 uPrev >>= RTBIGNUM_ELEMENT_BITS - cBits;
1807 if (uPrev)
1808 pauDst[pValue->cUsed] = uPrev;
1809 }
1810 else
1811 memcpy(pauDst, pauSrc, cLeft * RTBIGNUM_ELEMENT_SIZE);
1812 }
1813 }
1814 else
1815 rc = VERR_OUT_OF_RANGE;
1816 }
1817 /* Shifting zero always yields a zero result. */
1818 else
1819 rc = rtBigNumSetUsed(pResult, 0);
1820 }
1821 else
1822 rc = rtBigNumMagnitudeCopy(pResult, pValue);
1823 return rc;
1824}
1825
1826
1827RTDECL(int) RTBigNumShiftLeft(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
1828{
1829 Assert(pResult != pValue);
1830 AssertReturn(pResult->fSensitive >= pValue->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
1831
1832 int rc = rtBigNumUnscramble(pResult);
1833 if (RT_SUCCESS(rc))
1834 {
1835 RTBIGNUM_ASSERT_VALID(pResult);
1836 rc = rtBigNumUnscramble((PRTBIGNUM)pValue);
1837 if (RT_SUCCESS(rc))
1838 {
1839 RTBIGNUM_ASSERT_VALID(pValue);
1840
1841 pResult->fNegative = pValue->fNegative;
1842 rc = rtBigNumMagnitudeShiftLeft(pResult, pValue, cBits);
1843
1844 rtBigNumScramble((PRTBIGNUM)pValue);
1845 }
1846 rtBigNumScramble(pResult);
1847 }
1848 return rc;
1849}
1850
1851
1852/**
1853 * Shifts the magnitude right by @a cBits.
1854 *
1855 * The variables must be unscrambled.
1856 *
1857 * @returns IPRT status code.
1858 * @param pResult Where to store the result.
1859 * @param pValue The value to shift.
1860 * @param cBits The shift count.
1861 */
1862static int rtBigNumMagnitudeShiftRight(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
1863{
1864 int rc;
1865 if (cBits)
1866 {
1867 uint32_t cBitsNew = rtBigNumMagnitudeBitWidth(pValue);
1868 if (cBitsNew > cBits)
1869 {
1870 cBitsNew -= cBits;
1871 uint32_t cElementsNew = RT_ALIGN_32(cBitsNew, RTBIGNUM_ELEMENT_BITS) / RTBIGNUM_ELEMENT_BITS;
1872 rc = rtBigNumSetUsed(pResult, cElementsNew);
1873 if (RT_SUCCESS(rc))
1874 {
1875 uint32_t i = cElementsNew;
1876 PCRTBIGNUMELEMENT pauSrc = pValue->pauElements;
1877 PRTBIGNUMELEMENT pauDst = pResult->pauElements;
1878
1879 pauSrc += cBits / RTBIGNUM_ELEMENT_BITS;
1880
1881 cBits &= RTBIGNUM_ELEMENT_BITS - 1;
1882 if (cBits)
1883 {
1884 RTBIGNUMELEMENT uPrev = &pauSrc[i] == &pValue->pauElements[pValue->cUsed] ? 0 : pauSrc[i];
1885 while (i-- > 0)
1886 {
1887 RTBIGNUMELEMENT uCur = pauSrc[i];
1888 pauDst[i] = (uCur >> cBits) | (uPrev << (RTBIGNUM_ELEMENT_BITS - cBits));
1889 uPrev = uCur;
1890 }
1891 }
1892 else
1893 memcpy(pauDst, pauSrc, i * RTBIGNUM_ELEMENT_SIZE);
1894 }
1895 }
1896 else
1897 rc = rtBigNumSetUsed(pResult, 0);
1898 }
1899 else
1900 rc = rtBigNumMagnitudeCopy(pResult, pValue);
1901 return rc;
1902}
1903
1904
1905RTDECL(int) RTBigNumShiftRight(PRTBIGNUM pResult, PCRTBIGNUM pValue, uint32_t cBits)
1906{
1907 Assert(pResult != pValue);
1908 AssertReturn(pResult->fSensitive >= pValue->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
1909
1910 int rc = rtBigNumUnscramble(pResult);
1911 if (RT_SUCCESS(rc))
1912 {
1913 RTBIGNUM_ASSERT_VALID(pResult);
1914 rc = rtBigNumUnscramble((PRTBIGNUM)pValue);
1915 if (RT_SUCCESS(rc))
1916 {
1917 RTBIGNUM_ASSERT_VALID(pValue);
1918
1919 pResult->fNegative = pValue->fNegative;
1920 rc = rtBigNumMagnitudeShiftRight(pResult, pValue, cBits);
1921 if (!pResult->cUsed)
1922 pResult->fNegative = 0;
1923
1924 rtBigNumScramble((PRTBIGNUM)pValue);
1925 }
1926 rtBigNumScramble(pResult);
1927 }
1928 return rc;
1929}
1930
1931
1932/**
1933 * Implements the D3 test for Qhat decrementation.
1934 *
1935 * @returns True if Qhat should be decremented.
1936 * @param puQhat Pointer to Qhat.
1937 * @param uRhat The remainder.
1938 * @param uDivisorY The penultimate divisor element.
1939 * @param uDividendJMinus2 The j-2 dividend element.
1940 */
1941DECLINLINE(bool) rtBigNumKnuthD3_ShouldDecrementQhat(RTBIGNUMELEMENT2X const *puQhat, RTBIGNUMELEMENT uRhat,
1942 RTBIGNUMELEMENT uDivisorY, RTBIGNUMELEMENT uDividendJMinus2)
1943{
1944 if (puQhat->s.Lo == RTBIGNUM_ELEMENT_MAX && puQhat->s.Hi == 0)
1945 return true;
1946#if RTBIGNUM_ELEMENT_BITS == 64
1947 RTBIGNUMELEMENT2X TmpLeft;
1948 RTUInt128MulByU64(&TmpLeft, puQhat, uDivisorY);
1949
1950 RTBIGNUMELEMENT2X TmpRight;
1951 TmpRight.s.Lo = 0;
1952 TmpRight.s.Hi = uRhat;
1953 RTUInt128AssignAddU64(&TmpRight, uDividendJMinus2);
1954
1955 if (RTUInt128Compare(&TmpLeft, &TmpRight) > 0)
1956 return true;
1957#else
1958 if (puQhat->u * uDivisorY > ((uint64_t)uRhat << 32) + uDividendJMinus2)
1959 return true;
1960#endif
1961 return false;
1962}
1963
1964
1965/**
1966 * C implementation of the D3 step of Knuth's division algorithm.
1967 *
1968 * This estimates a value Qhat that will be used as quotient "digit" (element)
1969 * at the current level of the division (j).
1970 *
1971 * @returns The Qhat value we've estimated.
1972 * @param pauDividendJN Pointer to the j+n (normalized) dividend element.
1973 * Will access up to two elements prior to this.
1974 * @param uDivZ The last element in the (normalized) divisor.
1975 * @param uDivY The penultimate element in the (normalized) divisor.
1976 */
1977DECLINLINE(RTBIGNUMELEMENT) rtBigNumKnuthD3_EstimateQhat(PCRTBIGNUMELEMENT pauDividendJN,
1978 RTBIGNUMELEMENT uDivZ, RTBIGNUMELEMENT uDivY)
1979{
1980 RTBIGNUMELEMENT2X uQhat;
1981 RTBIGNUMELEMENT uRhat;
1982 RTBIGNUMELEMENT uDividendJN = pauDividendJN[0];
1983 Assert(uDividendJN <= uDivZ);
1984 if (uDividendJN != uDivZ)
1985 rtBigNumElement2xDiv2xBy1x(&uQhat, &uRhat, uDividendJN, pauDividendJN[-1], uDivZ);
1986 else
1987 {
1988 /*
1989 * This is the case where we end up with an initial Qhat that's all Fs.
1990 */
1991 /* Calc the remainder for max Qhat value. */
1992 RTBIGNUMELEMENT2X uTmp1; /* (v[j+n] << bits) + v[J+N-1] */
1993 uTmp1.s.Hi = uDivZ;
1994 uTmp1.s.Lo = pauDividendJN[-1];
1995
1996 RTBIGNUMELEMENT2X uTmp2; /* uQhat * uDividendJN */
1997 uTmp2.s.Hi = uDivZ - 1;
1998 uTmp2.s.Lo = 0 - uDivZ;
1999#if RTBIGNUM_ELEMENT_BITS == 64
2000 RTUInt128AssignSub(&uTmp1, &uTmp2);
2001#else
2002 uTmp1.u -= uTmp2.u;
2003#endif
2004 /* If we overflowed the remainder, don't bother trying to adjust. */
2005 if (uTmp1.s.Hi)
2006 return RTBIGNUM_ELEMENT_MAX;
2007
2008 uRhat = uTmp1.s.Lo;
2009 uQhat.s.Lo = RTBIGNUM_ELEMENT_MAX;
2010 uQhat.s.Hi = 0;
2011 }
2012
2013 /*
2014 * Adjust Q to eliminate all cases where it's two to large and most cases
2015 * where it's one too large.
2016 */
2017 while (rtBigNumKnuthD3_ShouldDecrementQhat(&uQhat, uRhat, uDivY, pauDividendJN[-2]))
2018 {
2019 rtBigNumElement2xDec(&uQhat);
2020 uRhat += uDivZ;
2021 if (uRhat < uDivZ /* overflow */ || uRhat == RTBIGNUM_ELEMENT_MAX)
2022 break;
2023 }
2024
2025 return uQhat.s.Lo;
2026}
2027
2028
2029#ifdef IPRT_BIGINT_WITH_ASM
2030DECLASM(bool) rtBigNumKnuthD4_MulSub(PRTBIGNUMELEMENT pauDividendJ, PRTBIGNUMELEMENT pauDivisor,
2031 uint32_t cDivisor, RTBIGNUMELEMENT uQhat);
2032#else
2033/**
2034 * C implementation of the D4 step of Knuth's division algorithm.
2035 *
2036 * This subtracts Divisor * Qhat from the dividend at the current J index.
2037 *
2038 * @returns true if negative result (unlikely), false if positive.
2039 * @param pauDividendJ Pointer to the j-th (normalized) dividend element.
2040 * Will access up to two elements prior to this.
2041 * @param uDivZ The last element in the (normalized) divisor.
2042 * @param uDivY The penultimate element in the (normalized) divisor.
2043 */
2044DECLINLINE(bool) rtBigNumKnuthD4_MulSub(PRTBIGNUMELEMENT pauDividendJ, PRTBIGNUMELEMENT pauDivisor,
2045 uint32_t cDivisor, RTBIGNUMELEMENT uQhat)
2046{
2047 uint32_t i;
2048 bool fBorrow = false;
2049 RTBIGNUMELEMENT uMulCarry = 0;
2050 for (i = 0; i < cDivisor; i++)
2051 {
2052 RTBIGNUMELEMENT2X uSub;
2053# if RTBIGNUM_ELEMENT_BITS == 64
2054 RTUInt128MulU64ByU64(&uSub, uQhat, pauDivisor[i]);
2055 RTUInt128AssignAddU64(&uSub, uMulCarry);
2056# else
2057 uSub.u = (uint64_t)uQhat * pauDivisor[i] + uMulCarry;
2058# endif
2059 uMulCarry = uSub.s.Hi;
2060
2061 RTBIGNUMELEMENT uDividendI = pauDividendJ[i];
2062 if (!fBorrow)
2063 {
2064 fBorrow = uDividendI < uSub.s.Lo;
2065 uDividendI -= uSub.s.Lo;
2066 }
2067 else
2068 {
2069 fBorrow = uDividendI <= uSub.s.Lo;
2070 uDividendI -= uSub.s.Lo + 1;
2071 }
2072 pauDividendJ[i] = uDividendI;
2073 }
2074
2075 /* Carry and borrow into the final dividend element. */
2076 RTBIGNUMELEMENT uDividendI = pauDividendJ[i];
2077 if (!fBorrow)
2078 {
2079 fBorrow = uDividendI < uMulCarry;
2080 pauDividendJ[i] = uDividendI - uMulCarry;
2081 }
2082 else
2083 {
2084 fBorrow = uDividendI <= uMulCarry;
2085 pauDividendJ[i] = uDividendI - uMulCarry - 1;
2086 }
2087
2088 return fBorrow;
2089}
2090#endif /* !IPRT_BIGINT_WITH_ASM */
2091
2092
2093/**
2094 * C implementation of the D6 step of Knuth's division algorithm.
2095 *
2096 * This adds the divisor to the dividend to undo the negative value step D4
2097 * produced. This is not very frequent occurence.
2098 *
2099 * @param pauDividendJ Pointer to the j-th (normalized) dividend element.
2100 * Will access up to two elements prior to this.
2101 * @param pauDivisor The last element in the (normalized) divisor.
2102 * @param cDivisor The penultimate element in the (normalized) divisor.
2103 */
2104DECLINLINE(void) rtBigNumKnuthD6_AddBack(PRTBIGNUMELEMENT pauDividendJ, PRTBIGNUMELEMENT pauDivisor, uint32_t cDivisor)
2105{
2106 RTBIGNUMELEMENT2X uTmp;
2107 uTmp.s.Lo = 0;
2108
2109 uint32_t i;
2110 for (i = 0; i < cDivisor; i++)
2111 {
2112 uTmp.s.Hi = 0;
2113#if RTBIGNUM_ELEMENT_BITS == 64
2114 RTUInt128AssignAddU64(&uTmp, pauDivisor[i]);
2115 RTUInt128AssignAddU64(&uTmp, pauDividendJ[i]);
2116#else
2117 uTmp.u += pauDivisor[i];
2118 uTmp.u += pauDividendJ[i];
2119#endif
2120 pauDividendJ[i] = uTmp.s.Lo;
2121 uTmp.s.Lo = uTmp.s.Hi;
2122 }
2123
2124 /* The final dividend entry. */
2125 Assert(pauDividendJ[i] + uTmp.s.Lo < uTmp.s.Lo);
2126 pauDividendJ[i] += uTmp.s.Lo;
2127}
2128
2129
2130/**
2131 * Knuth's division (core).
2132 *
2133 * @returns IPRT status code.
2134 * @param pQuotient Where to return the quotient. Can be NULL.
2135 * @param pRemainder Where to return the remainder.
2136 * @param pDividend What to divide.
2137 * @param pDivisor What to divide by.
2138 */
2139static int rtBigNumMagnitudeDivideKnuth(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2140{
2141 Assert(pDivisor->cUsed > 1);
2142 uint32_t const cDivisor = pDivisor->cUsed;
2143 Assert(pDividend->cUsed >= cDivisor);
2144
2145 /*
2146 * Make sure we've got enough space in the quotient, so we can build it
2147 * without any trouble come step D5.
2148 */
2149 int rc;
2150 if (pQuotient)
2151 {
2152 rc = rtBigNumSetUsedEx(pQuotient, 0, pDividend->cUsed - cDivisor + 1);
2153 if (RT_SUCCESS(rc))
2154 rc = rtBigNumSetUsed(pQuotient, pDividend->cUsed - cDivisor + 1);
2155 if (RT_FAILURE(rc))
2156 return rc;
2157 }
2158
2159 /*
2160 * D1. Normalize. The goal here is to make sure the last element in the
2161 * divisor is greater than RTBIGNUMELEMENTS_MAX/2. We must also make sure
2162 * we can access element pDividend->cUsed of the normalized dividend.
2163 */
2164 RTBIGNUM NormDividend;
2165 RTBIGNUM NormDivisor;
2166 PCRTBIGNUM pNormDivisor = &NormDivisor;
2167 rtBigNumInitZeroTemplate(&NormDivisor, pDividend);
2168
2169 uint32_t cNormShift = (RTBIGNUM_ELEMENT_BITS - rtBigNumMagnitudeBitWidth(pDivisor)) & (RTBIGNUM_ELEMENT_BITS - 1);
2170 if (cNormShift)
2171 {
2172 rtBigNumInitZeroTemplate(&NormDividend, pDividend);
2173 rc = rtBigNumMagnitudeShiftLeft(&NormDividend, pDividend, cNormShift);
2174 if (RT_SUCCESS(rc))
2175 rc = rtBigNumMagnitudeShiftLeft(&NormDivisor, pDivisor, cNormShift);
2176 }
2177 else
2178 {
2179 pNormDivisor = pDivisor;
2180 rc = rtBigNumCloneInternal(&NormDividend, pDividend);
2181 }
2182 if (RT_SUCCESS(rc) && pDividend->cUsed == NormDividend.cUsed)
2183 rc = rtBigNumEnsureExtraZeroElements(&NormDividend, NormDividend.cUsed + 1);
2184 if (RT_SUCCESS(rc))
2185 {
2186 /*
2187 * D2. Initialize the j index so we can loop thru the elements in the
2188 * dividend that makes it larger than the divisor.
2189 */
2190 uint32_t j = pDividend->cUsed - cDivisor;
2191
2192 RTBIGNUMELEMENT const DivZ = pNormDivisor->pauElements[cDivisor - 1];
2193 RTBIGNUMELEMENT const DivY = pNormDivisor->pauElements[cDivisor - 2];
2194 for (;;)
2195 {
2196 /*
2197 * D3. Estimate a Q' by dividing the j and j-1 dividen elements by
2198 * the last divisor element, then adjust against the next elements.
2199 */
2200 RTBIGNUMELEMENT uQhat = rtBigNumKnuthD3_EstimateQhat(&NormDividend.pauElements[j + cDivisor], DivZ, DivY);
2201
2202 /*
2203 * D4. Multiply and subtract.
2204 */
2205 bool fNegative = rtBigNumKnuthD4_MulSub(&NormDividend.pauElements[j], pNormDivisor->pauElements, cDivisor, uQhat);
2206
2207 /*
2208 * D5. Test remainder.
2209 * D6. Add back.
2210 */
2211 if (fNegative)
2212 {
2213//__debugbreak();
2214 rtBigNumKnuthD6_AddBack(&NormDividend.pauElements[j], pNormDivisor->pauElements, cDivisor);
2215 uQhat--;
2216 }
2217
2218 if (pQuotient)
2219 pQuotient->pauElements[j] = uQhat;
2220
2221 /*
2222 * D7. Loop on j.
2223 */
2224 if (j == 0)
2225 break;
2226 j--;
2227 }
2228
2229 /*
2230 * D8. Unnormalize the remainder.
2231 */
2232 rtBigNumStripTrailingZeros(&NormDividend);
2233 if (cNormShift)
2234 rc = rtBigNumMagnitudeShiftRight(pRemainder, &NormDividend, cNormShift);
2235 else
2236 rc = rtBigNumMagnitudeCopy(pRemainder, &NormDividend);
2237 if (pQuotient)
2238 rtBigNumStripTrailingZeros(pQuotient);
2239 }
2240
2241 /*
2242 * Delete temporary variables.
2243 */
2244 RTBigNumDestroy(&NormDividend);
2245 if (pNormDivisor == &NormDivisor)
2246 RTBigNumDestroy(&NormDivisor);
2247 return rc;
2248}
2249
2250
2251static int rtBigNumMagnitudeDivideSlowLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2252{
2253 /*
2254 * Do very simple long division. This ain't fast, but it does the trick.
2255 */
2256 int rc = VINF_SUCCESS;
2257 uint32_t iBit = rtBigNumMagnitudeBitWidth(pDividend);
2258 while (iBit-- > 0)
2259 {
2260 rc = rtBigNumMagnitudeShiftLeftOne(pRemainder, rtBigNumMagnitudeGetBit(pDividend, iBit));
2261 AssertRCBreak(rc);
2262 int iDiff = rtBigNumMagnitudeCompare(pRemainder, pDivisor);
2263 if (iDiff >= 0)
2264 {
2265 if (iDiff != 0)
2266 {
2267 rc = rtBigNumMagnitudeSubThis(pRemainder, pDivisor);
2268 AssertRCBreak(rc);
2269 }
2270 else
2271 rtBigNumSetUsed(pRemainder, 0);
2272 rc = rtBigNumMagnitudeSetBit(pQuotient, iBit);
2273 AssertRCBreak(rc);
2274 }
2275 }
2276
2277 /* This shouldn't be necessary. */
2278 rtBigNumStripTrailingZeros(pQuotient);
2279 rtBigNumStripTrailingZeros(pRemainder);
2280
2281 return rc;
2282}
2283
2284
2285/**
2286 * Divides the magnitudes of two values, letting the caller care about the sign
2287 * bit.
2288 *
2289 * All variables must be unscrambled. The sign flag is not considered nor
2290 * touched, this means the caller have to check for zero outputs.
2291 *
2292 * @returns IPRT status code.
2293 * @param pQuotient Where to return the quotient.
2294 * @param pRemainder Where to return the remainder.
2295 * @param pDividend What to divide.
2296 * @param pDivisor What to divide by.
2297 * @param fForceLong Force long division.
2298 */
2299static int rtBigNumMagnitudeDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor,
2300 bool fForceLong)
2301{
2302 Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
2303 Assert(!pQuotient->fCurScrambled); Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
2304
2305 /*
2306 * Just set both output values to zero as that's the return for several
2307 * special case and the initial state of the general case.
2308 */
2309 rtBigNumSetUsed(pQuotient, 0);
2310 rtBigNumSetUsed(pRemainder, 0);
2311
2312 /*
2313 * Dividing something by zero is undefined.
2314 * Diving zero by something is zero, unless the divsor is also zero.
2315 */
2316 if (!pDivisor->cUsed || !pDividend->cUsed)
2317 return pDivisor->cUsed ? VINF_SUCCESS : VERR_BIGNUM_DIV_BY_ZERO;
2318
2319 /*
2320 * Dividing by one? Quotient = dividend, no remainder.
2321 */
2322 if (pDivisor->cUsed == 1 && pDivisor->pauElements[0] == 1)
2323 return rtBigNumMagnitudeCopy(pQuotient, pDividend);
2324
2325 /*
2326 * Dividend smaller than the divisor. Zero quotient, all divisor.
2327 */
2328 int iDiff = rtBigNumMagnitudeCompare(pDividend, pDivisor);
2329 if (iDiff < 0)
2330 return rtBigNumMagnitudeCopy(pRemainder, pDividend);
2331
2332 /*
2333 * Since we already have done the compare, check if the two values are the
2334 * same. The result is 1 and no remainder then.
2335 */
2336 if (iDiff == 0)
2337 {
2338 int rc = rtBigNumSetUsed(pQuotient, 1);
2339 if (RT_SUCCESS(rc))
2340 pQuotient->pauElements[0] = 1;
2341 return rc;
2342 }
2343
2344 /*
2345 * Sort out special cases before going to the preferred or select algorithm.
2346 */
2347 int rc;
2348 if (pDividend->cUsed <= 2 && !fForceLong)
2349 {
2350 if (pDividend->cUsed < 2)
2351 {
2352 /*
2353 * Single element division.
2354 */
2355 RTBIGNUMELEMENT uQ = pDividend->pauElements[0] / pDivisor->pauElements[0];
2356 RTBIGNUMELEMENT uR = pDividend->pauElements[0] % pDivisor->pauElements[0];
2357 rc = VINF_SUCCESS;
2358 if (uQ)
2359 {
2360 rc = rtBigNumSetUsed(pQuotient, 1);
2361 if (RT_SUCCESS(rc))
2362 pQuotient->pauElements[0] = uQ;
2363 }
2364 if (uR && RT_SUCCESS(rc))
2365 {
2366 rc = rtBigNumSetUsed(pRemainder, 1);
2367 if (RT_SUCCESS(rc))
2368 pRemainder->pauElements[0] = uR;
2369 }
2370 }
2371 else
2372 {
2373 /*
2374 * Two elements dividend by a one or two element divisor.
2375 */
2376 RTBIGNUMELEMENT2X uQ, uR;
2377 if (pDivisor->cUsed == 1)
2378 {
2379 rtBigNumElement2xDiv2xBy1x(&uQ, &uR.s.Lo, pDividend->pauElements[1], pDividend->pauElements[0],
2380 pDivisor->pauElements[0]);
2381 uR.s.Hi = 0;
2382 }
2383 else
2384 rtBigNumElement2xDiv(&uQ, &uR, pDividend->pauElements[1], pDividend->pauElements[0],
2385 pDivisor->pauElements[1], pDivisor->pauElements[0]);
2386 rc = rtBigNumElement2xCopyToMagnitude(&uQ, pQuotient);
2387 if (RT_SUCCESS(rc))
2388 rc = rtBigNumElement2xCopyToMagnitude(&uR, pRemainder);
2389 }
2390 }
2391 /*
2392 * Decide upon which algorithm to use. Knuth requires a divisor that's at
2393 * least 2 elements big.
2394 */
2395 else if (pDivisor->cUsed < 2 || fForceLong)
2396 rc = rtBigNumMagnitudeDivideSlowLong(pQuotient, pRemainder, pDividend, pDivisor);
2397 else
2398 rc = rtBigNumMagnitudeDivideKnuth(pQuotient, pRemainder, pDividend, pDivisor);
2399 return rc;
2400}
2401
2402
2403static int rtBigNumDivideCommon(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder,
2404 PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor, bool fForceLong)
2405{
2406 Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
2407 AssertReturn(pQuotient->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
2408 AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
2409
2410 int rc = rtBigNumUnscramble(pQuotient);
2411 if (RT_SUCCESS(rc))
2412 {
2413 RTBIGNUM_ASSERT_VALID(pQuotient);
2414 rc = rtBigNumUnscramble(pRemainder);
2415 if (RT_SUCCESS(rc))
2416 {
2417 RTBIGNUM_ASSERT_VALID(pRemainder);
2418 rc = rtBigNumUnscramble((PRTBIGNUM)pDividend);
2419 if (RT_SUCCESS(rc))
2420 {
2421 RTBIGNUM_ASSERT_VALID(pDividend);
2422 rc = rtBigNumUnscramble((PRTBIGNUM)pDivisor);
2423 if (RT_SUCCESS(rc))
2424 {
2425 RTBIGNUM_ASSERT_VALID(pDivisor);
2426
2427 /*
2428 * The sign value of the remainder is the same as the dividend.
2429 * The sign values of the quotient follow XOR rules, just like multiplication:
2430 * -3 / 2 = -1; r=-1; 1 ^ 0 = 1
2431 * 3 / -2 = -1; r= 1; 1 ^ 0 = 1
2432 * -3 / -2 = 1; r=-1; 1 ^ 1 = 0
2433 * 3 / 2 = 1; r= 1; 0 ^ 0 = 0
2434 */
2435 pQuotient->fNegative = pDividend->fNegative ^ pDivisor->fNegative;
2436 pRemainder->fNegative = pDividend->fNegative;
2437
2438 rc = rtBigNumMagnitudeDivide(pQuotient, pRemainder, pDividend, pDivisor, fForceLong);
2439
2440 if (pQuotient->cUsed == 0)
2441 pQuotient->fNegative = 0;
2442 if (pRemainder->cUsed == 0)
2443 pRemainder->fNegative = 0;
2444
2445 rtBigNumScramble((PRTBIGNUM)pDivisor);
2446 }
2447 rtBigNumScramble((PRTBIGNUM)pDividend);
2448 }
2449 rtBigNumScramble(pRemainder);
2450 }
2451 rtBigNumScramble(pQuotient);
2452 }
2453 return rc;
2454}
2455
2456
2457RTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2458{
2459 return rtBigNumDivideCommon(pQuotient, pRemainder, pDividend, pDivisor, false /*fForceLong*/);
2460}
2461
2462
2463RTDECL(int) RTBigNumDivideLong(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2464{
2465 return rtBigNumDivideCommon(pQuotient, pRemainder, pDividend, pDivisor, true /*fForceLong*/);
2466}
2467
2468
2469/**
2470 * Calculates the modulus of a magnitude value, leaving the sign bit to the
2471 * caller.
2472 *
2473 * All variables must be unscrambled. The sign flag is not considered nor
2474 * touched, this means the caller have to check for zero outputs.
2475 *
2476 * @returns IPRT status code.
2477 * @param pRemainder Where to return the remainder.
2478 * @param pDividend What to divide.
2479 * @param pDivisor What to divide by.
2480 */
2481static int rtBigNumMagnitudeModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2482{
2483 Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor);
2484 Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
2485
2486 /*
2487 * Just set the output value to zero as that's the return for several
2488 * special case and the initial state of the general case.
2489 */
2490 rtBigNumSetUsed(pRemainder, 0);
2491
2492 /*
2493 * Dividing something by zero is undefined.
2494 * Diving zero by something is zero, unless the divsor is also zero.
2495 */
2496 if (!pDivisor->cUsed || !pDividend->cUsed)
2497 return pDivisor->cUsed ? VINF_SUCCESS : VERR_BIGNUM_DIV_BY_ZERO;
2498
2499 /*
2500 * Dividing by one? Quotient = dividend, no remainder.
2501 */
2502 if (pDivisor->cUsed == 1 && pDivisor->pauElements[0] == 1)
2503 return VINF_SUCCESS;
2504
2505 /*
2506 * Dividend smaller than the divisor. Zero quotient, all divisor.
2507 */
2508 int iDiff = rtBigNumMagnitudeCompare(pDividend, pDivisor);
2509 if (iDiff < 0)
2510 return rtBigNumMagnitudeCopy(pRemainder, pDividend);
2511
2512 /*
2513 * Since we already have done the compare, check if the two values are the
2514 * same. The result is 1 and no remainder then.
2515 */
2516 if (iDiff == 0)
2517 return VINF_SUCCESS;
2518
2519 /** @todo optimize small numbers. */
2520 int rc = VINF_SUCCESS;
2521 if (pDivisor->cUsed < 2)
2522 {
2523 /*
2524 * Do very simple long division. This ain't fast, but it does the trick.
2525 */
2526 uint32_t iBit = rtBigNumMagnitudeBitWidth(pDividend);
2527 while (iBit-- > 0)
2528 {
2529 rc = rtBigNumMagnitudeShiftLeftOne(pRemainder, rtBigNumMagnitudeGetBit(pDividend, iBit));
2530 AssertRCBreak(rc);
2531 iDiff = rtBigNumMagnitudeCompare(pRemainder, pDivisor);
2532 if (iDiff >= 0)
2533 {
2534 if (iDiff != 0)
2535 {
2536 rc = rtBigNumMagnitudeSubThis(pRemainder, pDivisor);
2537 AssertRCBreak(rc);
2538 }
2539 else
2540 rtBigNumSetUsed(pRemainder, 0);
2541 }
2542 }
2543 }
2544 else
2545 {
2546 /*
2547 * Join paths with division.
2548 */
2549 rc = rtBigNumMagnitudeDivideKnuth(NULL, pRemainder, pDividend, pDivisor);
2550 }
2551
2552 /* This shouldn't be necessary. */
2553 rtBigNumStripTrailingZeros(pRemainder);
2554 return rc;
2555}
2556
2557
2558RTDECL(int) RTBigNumModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
2559{
2560 Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor);
2561 AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive | pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
2562
2563 int rc = rtBigNumUnscramble(pRemainder);
2564 if (RT_SUCCESS(rc))
2565 {
2566 RTBIGNUM_ASSERT_VALID(pRemainder);
2567 rc = rtBigNumUnscramble((PRTBIGNUM)pDividend);
2568 if (RT_SUCCESS(rc))
2569 {
2570 RTBIGNUM_ASSERT_VALID(pDividend);
2571 rc = rtBigNumUnscramble((PRTBIGNUM)pDivisor);
2572 if (RT_SUCCESS(rc))
2573 {
2574 RTBIGNUM_ASSERT_VALID(pDivisor);
2575
2576 /*
2577 * The sign value of the remainder is the same as the dividend.
2578 */
2579 pRemainder->fNegative = pDividend->fNegative;
2580
2581 rc = rtBigNumMagnitudeModulo(pRemainder, pDividend, pDivisor);
2582
2583 if (pRemainder->cUsed == 0)
2584 pRemainder->fNegative = 0;
2585
2586 rtBigNumScramble((PRTBIGNUM)pDivisor);
2587 }
2588 rtBigNumScramble((PRTBIGNUM)pDividend);
2589 }
2590 rtBigNumScramble(pRemainder);
2591 }
2592 return rc;
2593}
2594
2595
2596
2597/**
2598 * Exponentiate the magnitude.
2599 *
2600 * All variables must be unscrambled. The sign flag is not considered nor
2601 * touched, this means the caller have to reject negative exponents.
2602 *
2603 * @returns IPRT status code.
2604 * @param pResult Where to return power.
2605 * @param pBase The base value.
2606 * @param pExponent The exponent (assumed positive or zero).
2607 */
2608static int rtBigNumMagnitudeExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent)
2609{
2610 Assert(pResult != pBase); Assert(pResult != pExponent);
2611 Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled);
2612
2613 /*
2614 * A couple of special cases.
2615 */
2616 int rc;
2617 /* base ^ 0 => 1. */
2618 if (pExponent->cUsed == 0)
2619 {
2620 rc = rtBigNumSetUsed(pResult, 1);
2621 if (RT_SUCCESS(rc))
2622 pResult->pauElements[0] = 1;
2623 return rc;
2624 }
2625
2626 /* base ^ 1 => base. */
2627 if (pExponent->cUsed == 1 && pExponent->pauElements[0] == 1)
2628 return rtBigNumMagnitudeCopy(pResult, pBase);
2629
2630 /*
2631 * Set up.
2632 */
2633 /* Init temporary power-of-two variable to base. */
2634 RTBIGNUM Pow2;
2635 rc = rtBigNumCloneInternal(&Pow2, pBase);
2636 if (RT_SUCCESS(rc))
2637 {
2638 /* Init result to 1. */
2639 rc = rtBigNumSetUsed(pResult, 1);
2640 if (RT_SUCCESS(rc))
2641 {
2642 pResult->pauElements[0] = 1;
2643
2644 /* Make a temporary variable that we can use for temporary storage of the result. */
2645 RTBIGNUM TmpMultiplicand;
2646 rc = rtBigNumCloneInternal(&TmpMultiplicand, pResult);
2647 if (RT_SUCCESS(rc))
2648 {
2649 /*
2650 * Exponentiation by squaring. Reduces the number of
2651 * multiplications to: NumBitsSet(Exponent) + BitWidth(Exponent).
2652 */
2653 uint32_t const cExpBits = rtBigNumMagnitudeBitWidth(pExponent);
2654 uint32_t iBit = 0;
2655 for (;;)
2656 {
2657 if (rtBigNumMagnitudeGetBit(pExponent, iBit) != 0)
2658 {
2659 rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, pResult);
2660 if (RT_SUCCESS(rc))
2661 rc = rtBigNumMagnitudeMultiply(pResult, &TmpMultiplicand, &Pow2);
2662 if (RT_FAILURE(rc))
2663 break;
2664 }
2665
2666 /* Done? */
2667 iBit++;
2668 if (iBit >= cExpBits)
2669 break;
2670
2671 /* Not done yet, square the base again. */
2672 rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, &Pow2);
2673 if (RT_SUCCESS(rc))
2674 rc = rtBigNumMagnitudeMultiply(&Pow2, &TmpMultiplicand, &TmpMultiplicand);
2675 if (RT_FAILURE(rc))
2676 break;
2677 }
2678
2679 RTBigNumDestroy(&TmpMultiplicand);
2680 }
2681 }
2682 RTBigNumDestroy(&Pow2);
2683 }
2684 return rc;
2685}
2686
2687
2688RTDECL(int) RTBigNumExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent)
2689{
2690 Assert(pResult != pBase); Assert(pResult != pExponent);
2691 AssertReturn(pResult->fSensitive >= (pBase->fSensitive | pExponent->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
2692
2693 int rc = rtBigNumUnscramble(pResult);
2694 if (RT_SUCCESS(rc))
2695 {
2696 RTBIGNUM_ASSERT_VALID(pResult);
2697 rc = rtBigNumUnscramble((PRTBIGNUM)pBase);
2698 if (RT_SUCCESS(rc))
2699 {
2700 RTBIGNUM_ASSERT_VALID(pBase);
2701 rc = rtBigNumUnscramble((PRTBIGNUM)pExponent);
2702 if (RT_SUCCESS(rc))
2703 {
2704 RTBIGNUM_ASSERT_VALID(pExponent);
2705 if (!pExponent->fNegative)
2706 {
2707 pResult->fNegative = pBase->fNegative; /* sign unchanged. */
2708 rc = rtBigNumMagnitudeExponentiate(pResult, pBase, pExponent);
2709 }
2710 else
2711 rc = VERR_BIGNUM_NEGATIVE_EXPONENT;
2712
2713 rtBigNumScramble((PRTBIGNUM)pExponent);
2714 }
2715 rtBigNumScramble((PRTBIGNUM)pBase);
2716 }
2717 rtBigNumScramble(pResult);
2718 }
2719 return rc;
2720}
2721
2722
2723/**
2724 * Modular exponentiation, magnitudes only.
2725 *
2726 * All variables must be unscrambled. The sign flag is not considered nor
2727 * touched, this means the caller have to reject negative exponents and do any
2728 * other necessary sign bit fiddling.
2729 *
2730 * @returns IPRT status code.
2731 * @param pResult Where to return the remainder of the power.
2732 * @param pBase The base value.
2733 * @param pExponent The exponent (assumed positive or zero).
2734 * @param pModulus The modulus value (or divisor if you like).
2735 */
2736static int rtBigNumMagnitudeModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
2737{
2738 Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
2739 Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled); Assert(!pModulus->fCurScrambled);
2740 int rc;
2741
2742 /*
2743 * Check some special cases to get them out of the way.
2744 */
2745 /* Div by 0 => invalid. */
2746 if (pModulus->cUsed == 0)
2747 return VERR_BIGNUM_DIV_BY_ZERO;
2748
2749 /* Div by 1 => no remainder. */
2750 if (pModulus->cUsed == 1 && pModulus->pauElements[0] == 1)
2751 {
2752 rtBigNumSetUsed(pResult, 0);
2753 return VINF_SUCCESS;
2754 }
2755
2756 /* base ^ 0 => 1. */
2757 if (pExponent->cUsed == 0)
2758 {
2759 rc = rtBigNumSetUsed(pResult, 1);
2760 if (RT_SUCCESS(rc))
2761 pResult->pauElements[0] = 1;
2762 return rc;
2763 }
2764
2765 /* base ^ 1 => base. */
2766 if (pExponent->cUsed == 1 && pExponent->pauElements[0] == 1)
2767 return rtBigNumMagnitudeModulo(pResult, pBase, pModulus);
2768
2769 /*
2770 * Set up.
2771 */
2772 /* Result = 1; preallocate space for the result while at it. */
2773 rc = rtBigNumSetUsed(pResult, pModulus->cUsed + 1);
2774 if (RT_SUCCESS(rc))
2775 rc = rtBigNumSetUsed(pResult, 1);
2776 if (RT_SUCCESS(rc))
2777 {
2778 pResult->pauElements[0] = 1;
2779
2780 /* ModBase = pBase or pBase % pModulus depending on the difference in size. */
2781 RTBIGNUM Pow2;
2782 if (pBase->cUsed <= pModulus->cUsed + pModulus->cUsed / 2)
2783 rc = rtBigNumCloneInternal(&Pow2, pBase);
2784 else
2785 rc = rtBigNumMagnitudeModulo(rtBigNumInitZeroTemplate(&Pow2, pBase), pBase, pModulus);
2786
2787 /* Need a couple of temporary variables. */
2788 RTBIGNUM TmpMultiplicand;
2789 rtBigNumInitZeroTemplate(&TmpMultiplicand, pResult);
2790
2791 RTBIGNUM TmpProduct;
2792 rtBigNumInitZeroTemplate(&TmpProduct, pResult);
2793
2794 /*
2795 * We combine the exponentiation by squaring with the fact that:
2796 * (a*b) mod n = ( (a mod n) * (b mod n) ) mod n
2797 *
2798 * Thus, we can reduce the size of intermediate results by mod'ing them
2799 * in each step.
2800 */
2801 uint32_t const cExpBits = rtBigNumMagnitudeBitWidth(pExponent);
2802 uint32_t iBit = 0;
2803 for (;;)
2804 {
2805 if (rtBigNumMagnitudeGetBit(pExponent, iBit) != 0)
2806 {
2807 rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, pResult);
2808 if (RT_SUCCESS(rc))
2809 rc = rtBigNumMagnitudeMultiply(&TmpProduct, &TmpMultiplicand, &Pow2);
2810 if (RT_SUCCESS(rc))
2811 rc = rtBigNumMagnitudeModulo(pResult, &TmpProduct, pModulus);
2812 if (RT_FAILURE(rc))
2813 break;
2814 }
2815
2816 /* Done? */
2817 iBit++;
2818 if (iBit >= cExpBits)
2819 break;
2820
2821 /* Not done yet, square and mod the base again. */
2822 rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, &Pow2);
2823 if (RT_SUCCESS(rc))
2824 rc = rtBigNumMagnitudeMultiply(&TmpProduct, &TmpMultiplicand, &TmpMultiplicand);
2825 if (RT_SUCCESS(rc))
2826 rc = rtBigNumMagnitudeModulo(&Pow2, &TmpProduct, pModulus);
2827 if (RT_FAILURE(rc))
2828 break;
2829 }
2830
2831 RTBigNumDestroy(&TmpMultiplicand);
2832 RTBigNumDestroy(&TmpProduct);
2833 RTBigNumDestroy(&Pow2);
2834 }
2835 return rc;
2836}
2837
2838
2839RTDECL(int) RTBigNumModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
2840{
2841 Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
2842 AssertReturn(pResult->fSensitive >= (pBase->fSensitive | pExponent->fSensitive | pModulus->fSensitive),
2843 VERR_BIGNUM_SENSITIVE_INPUT);
2844
2845 int rc = rtBigNumUnscramble(pResult);
2846 if (RT_SUCCESS(rc))
2847 {
2848 RTBIGNUM_ASSERT_VALID(pResult);
2849 rc = rtBigNumUnscramble((PRTBIGNUM)pBase);
2850 if (RT_SUCCESS(rc))
2851 {
2852 RTBIGNUM_ASSERT_VALID(pBase);
2853 rc = rtBigNumUnscramble((PRTBIGNUM)pExponent);
2854 if (RT_SUCCESS(rc))
2855 {
2856 RTBIGNUM_ASSERT_VALID(pExponent);
2857 rc = rtBigNumUnscramble((PRTBIGNUM)pModulus);
2858 if (RT_SUCCESS(rc))
2859 {
2860 RTBIGNUM_ASSERT_VALID(pModulus);
2861 if (!pExponent->fNegative)
2862 {
2863 pResult->fNegative = pModulus->fNegative; /* pBase ^ pExponent / pModulus; result = remainder. */
2864 rc = rtBigNumMagnitudeModExp(pResult, pBase, pExponent, pModulus);
2865 }
2866 else
2867 rc = VERR_BIGNUM_NEGATIVE_EXPONENT;
2868 rtBigNumScramble((PRTBIGNUM)pModulus);
2869 }
2870 rtBigNumScramble((PRTBIGNUM)pExponent);
2871 }
2872 rtBigNumScramble((PRTBIGNUM)pBase);
2873 }
2874 rtBigNumScramble(pResult);
2875 }
2876 return rc;
2877}
2878
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette