VirtualBox

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

Last change on this file since 58591 was 57944, checked in by vboxsync, 9 years ago

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