VirtualBox

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

Last change on this file since 66619 was 65813, checked in by vboxsync, 8 years ago

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