VirtualBox

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

Last change on this file since 62564 was 62477, checked in by vboxsync, 9 years ago

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