bignum.cpp@ 51770

Last change on this file since 51770 was 51770, checked in by vboxsync, 11 years ago
Merged in iprt++ dev branch.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 60.7 KB

Line
1	/* $Id: bignum.cpp 51770 2014-07-01 18:14:02Z vboxsync $ */
2	/** @file
3	* IPRT - Big Integer Numbers.
4	*/
5
6	/*
7	* Copyright (C) 2006-2014 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	#if defined(DEBUG_bird) && !defined(IN_SUP_HARDENED_R3)
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
44
45	/** The max size (in bytes) of an elements array. */
46	#define RTBIGNUM_MAX_SIZE _4M
47
48
49	/**
50	* Scrambles a big number if required.
51	*
52	* @param pBigNum The big number.
53	*/
54	DECLINLINE(void) rtBigNumScramble(PRTBIGNUM pBigNum)
55	{
56	if (pBigNum->fSensitive)
57	{
58	AssertReturnVoid(!pBigNum->fCurScrambled);
59	if (pBigNum->pauElements)
60	{
61	int rc = RTMemSaferScramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
62	pBigNum->fCurScrambled = RT_SUCCESS(rc);
63	}
64	else
65	pBigNum->fCurScrambled = true;
66	}
67	}
68
69
70	/**
71	* Unscrambles a big number if required.
72	*
73	* @returns IPRT status code.
74	* @param pBigNum The big number.
75	*/
76	DECLINLINE(int) rtBigNumUnscramble(PRTBIGNUM pBigNum)
77	{
78	if (pBigNum->fSensitive)
79	{
80	AssertReturn(pBigNum->fCurScrambled, VERR_INTERNAL_ERROR_2);
81	if (pBigNum->pauElements)
82	{
83	int rc = RTMemSaferUnscramble(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE); AssertRC(rc);
84	pBigNum->fCurScrambled = !RT_SUCCESS(rc);
85	return rc;
86	}
87	else
88	pBigNum->fCurScrambled = false;
89	}
90	return VINF_SUCCESS;
91	}
92
93
94	/**
95	* Getter function for pauElements which extends the array to infinity.
96	*
97	* @returns The element value.
98	* @param pBigNum The big number.
99	* @param iElement The element index.
100	*/
101	DECLINLINE(RTBIGNUMELEMENT) rtBigNumGetElement(PCRTBIGNUM pBigNum, uint32_t iElement)
102	{
103	if (iElement < pBigNum->cUsed)
104	return pBigNum->pauElements[iElement];
105	return 0;
106	}
107
108
109	/**
110	* Grows the pauElements array so it can fit at least @a cNewUsed entries.
111	*
112	* @returns IPRT status code.
113	* @param pBigNum The big number.
114	* @param cNewUsed The new cUsed value.
115	*/
116	static int rtBigNumGrow(PRTBIGNUM pBigNum, uint32_t cNewUsed)
117	{
118	uint32_t const cbOld = pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE;
119	uint32_t const cNew = RT_ALIGN_32(cNewUsed, 4);
120	uint32_t const cbNew = cNew * RTBIGNUM_ELEMENT_SIZE;
121	Assert(cbNew > cbOld);
122
123	void *pvNew;
124	if (pBigNum->fSensitive)
125	pvNew = RTMemSaferReallocZ(cbOld, pBigNum->pauElements, cbNew);
126	else
127	pvNew = RTMemRealloc(pBigNum->pauElements, cbNew);
128	if (RT_LIKELY(pvNew))
129	{
130	if (cbNew > cbOld)
131	RT_BZERO((char *)pvNew + cbOld, cbNew - cbOld);
132
133	pBigNum->pauElements = (RTBIGNUMELEMENT *)pvNew;
134	pBigNum->cUsed = cNewUsed;
135	pBigNum->cAllocated = cNew;
136	return VINF_SUCCESS;
137	}
138	return VERR_NO_MEMORY;
139	}
140
141
142	/**
143	* Changes the cUsed member, growing the pauElements array if necessary.
144	*
145	* No assumptions about the value of any added elements should be made. This
146	* method is mainly for resizing result values where the caller will repopulate
147	* the element values short after this call.
148	*
149	* @returns IPRT status code.
150	* @param pBigNum The big number.
151	* @param cNewUsed The new cUsed value.
152	*/
153	DECLINLINE(int) rtBigNumSetUsed(PRTBIGNUM pBigNum, uint32_t cNewUsed)
154	{
155	if (pBigNum->cAllocated >= cNewUsed)
156	{
157	pBigNum->cUsed = cNewUsed;
158	return VINF_SUCCESS;
159	}
160	return rtBigNumGrow(pBigNum, cNewUsed);
161	}
162
163	/**
164	* The slow part of rtBigNumEnsureElementPresent where we need to do actual zero
165	* extending.
166	*
167	* @returns IPRT status code.
168	* @param pBigNum The big number.
169	* @param iElement The element we wish to access.
170	*/
171	static int rtBigNumEnsureElementPresentSlow(PRTBIGNUM pBigNum, uint32_t iElement)
172	{
173	uint32_t const cOldUsed = pBigNum->cUsed;
174	int rc = rtBigNumSetUsed(pBigNum, iElement + 1);
175	if (RT_SUCCESS(rc))
176	{
177	RT_BZERO(&pBigNum->pauElements[cOldUsed], (iElement + 1 - cOldUsed) * RTBIGNUM_ELEMENT_SIZE);
178	return VINF_SUCCESS;
179	}
180	return rc;
181	}
182
183
184	/**
185	* Zero extends the element array to make sure a the specified element index is
186	* accessible.
187	*
188	* This is typically used with bit operations and self modifying methods. Any
189	* new elements added will be initialized to zero. The caller is responsible
190	* for there not being any trailing zero elements.
191	*
192	* The number must be unscrambled.
193	*
194	* @returns IPRT status code.
195	* @param pBigNum The big number.
196	* @param iElement The element we wish to access.
197	*/
198	DECLINLINE(int) rtBigNumEnsureElementPresent(PRTBIGNUM pBigNum, uint32_t iElement)
199	{
200	if (iElement < pBigNum->cUsed)
201	return VINF_SUCCESS;
202	return rtBigNumEnsureElementPresentSlow(pBigNum, iElement);
203	}
204
205
206	/**
207	* Strips zero elements from the magnitude value.
208	*
209	* @param pBigNum The big number to strip.
210	*/
211	static void rtBigNumStripTrailingZeros(PRTBIGNUM pBigNum)
212	{
213	uint32_t i = pBigNum->cUsed;
214	while (i > 0 && pBigNum->pauElements[i - 1] == 0)
215	i--;
216	pBigNum->cUsed = i;
217	}
218
219
220	/**
221	* Initialize the big number to zero.
222	*
223	* @returns @a pBigNum
224	* @param pBigNum The big number.
225	* @param fFlags The flags.
226	* @internal
227	*/
228	DECLINLINE(PRTBIGNUM) rtBigNumInitZeroInternal(PRTBIGNUM pBigNum, uint32_t fFlags)
229	{
230	RT_ZERO(*pBigNum);
231	pBigNum->fSensitive = RT_BOOL(fFlags & RTBIGNUMINIT_F_SENSITIVE);
232	return pBigNum;
233	}
234
235
236	/**
237	* Initialize the big number to zero from a template variable.
238	*
239	* @returns @a pBigNum
240	* @param pBigNum The big number.
241	* @param pTemplate The template big number.
242	* @internal
243	*/
244	DECLINLINE(PRTBIGNUM) rtBigNumInitZeroTemplate(PRTBIGNUM pBigNum, PCRTBIGNUM pTemplate)
245	{
246	RT_ZERO(*pBigNum);
247	pBigNum->fSensitive = pTemplate->fSensitive;
248	return pBigNum;
249	}
250
251
252	RTDECL(int) RTBigNumInit(PRTBIGNUM pBigNum, uint32_t fFlags, void const *pvRaw, size_t cbRaw)
253	{
254	/*
255	* Validate input.
256	*/
257	AssertPtrReturn(pBigNum, VERR_INVALID_POINTER);
258	AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_BIG) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE),
259	VERR_INVALID_PARAMETER);
260	AssertReturn(RT_BOOL(fFlags & RTBIGNUMINIT_F_UNSIGNED) ^ RT_BOOL(fFlags & RTBIGNUMINIT_F_SIGNED), VERR_INVALID_PARAMETER);
261	if (cbRaw)
262	AssertPtrReturn(pvRaw, VERR_INVALID_POINTER);
263
264	/*
265	* Initalize the big number to zero.
266	*/
267	rtBigNumInitZeroInternal(pBigNum, fFlags);
268
269	/*
270	* Strip the input and figure the sign flag.
271	*/
272	uint8_t const pb = (uint8_t const )pvRaw;
273	if (cbRaw)
274	{
275	if (fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE)
276	{
277	if (fFlags & RTBIGNUMINIT_F_UNSIGNED)
278	{
279	while (cbRaw > 0 && pb[cbRaw - 1] == 0)
280	cbRaw--;
281	}
282	else
283	{
284	if (pb[cbRaw - 1] >> 7)
285	{
286	pBigNum->fNegative = 1;
287	while (cbRaw > 1 && pb[cbRaw - 1] == 0xff)
288	cbRaw--;
289	}
290	else
291	while (cbRaw > 0 && pb[cbRaw - 1] == 0)
292	cbRaw--;
293	}
294	}
295	else
296	{
297	if (fFlags & RTBIGNUMINIT_F_UNSIGNED)
298	{
299	while (cbRaw > 0 && *pb == 0)
300	pb++, cbRaw--;
301	}
302	else
303	{
304	if (*pb >> 7)
305	{
306	pBigNum->fNegative = 1;
307	while (cbRaw > 1 && *pb == 0xff)
308	pb++, cbRaw--;
309	}
310	else
311	while (cbRaw > 0 && *pb == 0)
312	pb++, cbRaw--;
313	}
314	}
315	}
316
317	/*
318	* Allocate memory for the elements.
319	*/
320	size_t cbAligned = RT_ALIGN_Z(cbRaw, RTBIGNUM_ELEMENT_SIZE);
321	if (RT_UNLIKELY(cbAligned >= RTBIGNUM_MAX_SIZE))
322	return VERR_OUT_OF_RANGE;
323	pBigNum->cUsed = (uint32_t)cbAligned / RTBIGNUM_ELEMENT_SIZE;
324	if (pBigNum->cUsed)
325	{
326	pBigNum->cAllocated = RT_ALIGN_32(pBigNum->cUsed, 4);
327	if (pBigNum->fSensitive)
328	pBigNum->pauElements = (RTBIGNUMELEMENT )RTMemSaferAllocZ(pBigNum->cAllocated RTBIGNUM_ELEMENT_SIZE);
329	else
330	pBigNum->pauElements = (RTBIGNUMELEMENT )RTMemAlloc(pBigNum->cAllocated RTBIGNUM_ELEMENT_SIZE);
331	if (RT_UNLIKELY(!pBigNum->pauElements))
332	return VERR_NO_MEMORY;
333
334	/*
335	* Initialize the array.
336	*/
337	uint32_t i = 0;
338	if (fFlags & RTBIGNUMINIT_F_ENDIAN_LITTLE)
339	{
340	while (cbRaw >= RTBIGNUM_ELEMENT_SIZE)
341	{
342	#if RTBIGNUM_ELEMENT_SIZE == 8
343	pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[0], pb[1], pb[2], pb[3], pb[4], pb[5], pb[6], pb[7]);
344	#elif RTBIGNUM_ELEMENT_SIZE == 4
345	pBigNum->pauElements[i] = RT_MAKE_U32_FROM_U8(pb[0], pb[1], pb[2], pb[3]);
346	#else
347	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
348	#endif
349	i++;
350	pb += RTBIGNUM_ELEMENT_SIZE;
351	cbRaw -= RTBIGNUM_ELEMENT_SIZE;
352	}
353
354	if (cbRaw > 0)
355	{
356	RTBIGNUMELEMENT uLast = pBigNum->fNegative ? ~(RTBIGNUMELEMENT)0 : 0;
357	switch (cbRaw)
358	{
359	default: AssertFailed();
360	#if RTBIGNUM_ELEMENT_SIZE == 8
361	case 7: uLast = (uLast << 8) \| pb[6];
362	case 6: uLast = (uLast << 8) \| pb[5];
363	case 5: uLast = (uLast << 8) \| pb[4];
364	case 4: uLast = (uLast << 8) \| pb[3];
365	#endif
366	case 3: uLast = (uLast << 8) \| pb[2];
367	case 2: uLast = (uLast << 8) \| pb[1];
368	case 1: uLast = (uLast << 8) \| pb[0];
369	}
370	pBigNum->pauElements[i] = uLast;
371	}
372	}
373	else
374	{
375	pb += cbRaw;
376	while (cbRaw >= RTBIGNUM_ELEMENT_SIZE)
377	{
378	pb -= RTBIGNUM_ELEMENT_SIZE;
379	#if RTBIGNUM_ELEMENT_SIZE == 8
380	pBigNum->pauElements[i] = RT_MAKE_U64_FROM_U8(pb[7], pb[6], pb[5], pb[4], pb[3], pb[2], pb[1], pb[0]);
381	#elif RTBIGNUM_ELEMENT_SIZE == 4
382	pBigNum->pauElements[i] = RT_MAKE_U32_FROM_U8(pb[3], pb[2], pb[1], pb[0]);
383	#else
384	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
385	#endif
386	i++;
387	cbRaw -= RTBIGNUM_ELEMENT_SIZE;
388	}
389
390	if (cbRaw > 0)
391	{
392	RTBIGNUMELEMENT uLast = pBigNum->fNegative ? ~(RTBIGNUMELEMENT)0 : 0;
393	pb -= cbRaw;
394	switch (cbRaw)
395	{
396	default: AssertFailed();
397	#if RTBIGNUM_ELEMENT_SIZE == 8
398	case 7: uLast = (uLast << 8) \| *pb++;
399	case 6: uLast = (uLast << 8) \| *pb++;
400	case 5: uLast = (uLast << 8) \| *pb++;
401	case 4: uLast = (uLast << 8) \| *pb++;
402	#endif
403	case 3: uLast = (uLast << 8) \| *pb++;
404	case 2: uLast = (uLast << 8) \| *pb++;
405	case 1: uLast = (uLast << 8) \| *pb++;
406	}
407	pBigNum->pauElements[i] = uLast;
408	}
409	}
410
411	/*
412	* If negative, negate it so we get a positive magnitude value in pauElements.
413	*/
414	if (pBigNum->fNegative)
415	{
416	pBigNum->pauElements[0] = 0U - pBigNum->pauElements[0];
417	for (i = 1; i < pBigNum->cUsed; i++)
418	pBigNum->pauElements[i] = 0U - pBigNum->pauElements[i] - 1U;
419	}
420	}
421
422	rtBigNumScramble(pBigNum);
423	return VINF_SUCCESS;
424	}
425
426
427	RTDECL(int) RTBigNumInitZero(PRTBIGNUM pBigNum, uint32_t fFlags)
428	{
429	AssertReturn(!(fFlags & ~RTBIGNUMINIT_F_SENSITIVE), VERR_INVALID_PARAMETER);
430	AssertPtrReturn(pBigNum, VERR_INVALID_POINTER);
431
432	rtBigNumInitZeroInternal(pBigNum, fFlags);
433	rtBigNumScramble(pBigNum);
434	return VINF_SUCCESS;
435	}
436
437
438	/**
439	* Internal clone function that assumes the caller takes care of scrambling.
440	*
441	* @returns IPRT status code.
442	* @param pBigNum The target number.
443	* @param pSrc The source number.
444	*/
445	static int rtBigNumCloneInternal(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc)
446	{
447	Assert(!pSrc->fCurScrambled);
448	int rc = VINF_SUCCESS;
449
450	/*
451	* Copy over the data.
452	*/
453	RT_ZERO(*pBigNum);
454	pBigNum->fNegative = pSrc->fNegative;
455	pBigNum->fSensitive = pSrc->fSensitive;
456	pBigNum->cUsed = pSrc->cUsed;
457	if (pSrc->cUsed)
458	{
459	/* Duplicate the element array. */
460	pBigNum->cAllocated = RT_ALIGN_32(pBigNum->cUsed, 4);
461	if (pBigNum->fSensitive)
462	pBigNum->pauElements = (RTBIGNUMELEMENT )RTMemSaferAllocZ(pBigNum->cAllocated RTBIGNUM_ELEMENT_SIZE);
463	else
464	pBigNum->pauElements = (RTBIGNUMELEMENT )RTMemAlloc(pBigNum->cAllocated RTBIGNUM_ELEMENT_SIZE);
465	if (RT_LIKELY(pBigNum->pauElements))
466	memcpy(pBigNum->pauElements, pSrc->pauElements, pBigNum->cUsed * RTBIGNUM_ELEMENT_SIZE);
467	else
468	{
469	RT_ZERO(*pBigNum);
470	rc = VERR_NO_MEMORY;
471	}
472	}
473	return rc;
474	}
475
476
477	RTDECL(int) RTBigNumClone(PRTBIGNUM pBigNum, PCRTBIGNUM pSrc)
478	{
479	int rc = rtBigNumUnscramble((PRTBIGNUM)pSrc);
480	if (RT_SUCCESS(rc))
481	{
482	rc = rtBigNumCloneInternal(pBigNum, pSrc);
483	if (RT_SUCCESS(rc))
484	rtBigNumScramble(pBigNum);
485	rtBigNumScramble((PRTBIGNUM)pSrc);
486	}
487	return rc;
488	}
489
490
491	RTDECL(int) RTBigNumDestroy(PRTBIGNUM pBigNum)
492	{
493	if (pBigNum)
494	{
495	if (pBigNum->pauElements)
496	{
497	Assert(pBigNum->cAllocated > 0);
498	if (pBigNum->fSensitive)
499	{
500	RTMemSaferFree(pBigNum->pauElements, pBigNum->cAllocated * RTBIGNUM_ELEMENT_SIZE);
501	RT_ZERO(*pBigNum);
502	}
503	RTMemFree(pBigNum->pauElements);
504	pBigNum->pauElements = NULL;
505	}
506	}
507	return VINF_SUCCESS;
508	}
509
510
511	RTDECL(int) RTBigNumAssign(PRTBIGNUM pDst, PCRTBIGNUM pSrc)
512	{
513	AssertReturn(pDst->fSensitive >= pSrc->fSensitive, VERR_BIGNUM_SENSITIVE_INPUT);
514	int rc = rtBigNumUnscramble(pDst);
515	if (RT_SUCCESS(rc))
516	{
517	rc = rtBigNumUnscramble((PRTBIGNUM)pSrc);
518	if (RT_SUCCESS(rc))
519	{
520	if ( pDst->fSensitive == pSrc->fSensitive
521	\|\| pDst->fSensitive)
522	{
523	if (pDst->cAllocated >= pSrc->cUsed)
524	{
525	pDst->cUsed = pSrc->cUsed;
526	pDst->fNegative = pSrc->fNegative;
527	memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
528	}
529	else
530	{
531	rc = rtBigNumGrow(pDst, pSrc->cUsed);
532	if (RT_SUCCESS(rc))
533	{
534	pDst->fNegative = pSrc->fNegative;
535	memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
536	}
537	}
538	}
539	else
540	rc = VERR_BIGNUM_SENSITIVE_INPUT;
541	rtBigNumScramble((PRTBIGNUM)pSrc);
542	}
543	rtBigNumScramble(pDst);
544	}
545	return rc;
546	}
547
548
549	static uint32_t rtBigNumElementBitCount(RTBIGNUMELEMENT uElement)
550	{
551	#if RTBIGNUM_ELEMENT_SIZE == 8
552	if (uElement >> 32)
553	return ASMBitLastSetU32((uint32_t)(uElement >> 32)) + 32;
554	return ASMBitLastSetU32((uint32_t)uElement);
555	#elif RTBIGNUM_ELEMENT_SIZE == 4
556	return ASMBitLastSetU32(uElement);
557	#else
558	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
559	#endif
560	}
561
562
563	/**
564	* Same as RTBigNumBitWidth, except that it ignore the signed bit.
565	*
566	* The number must be unscrambled.
567	*
568	* @returns The effective width of the magnitude, in bits. Returns 0 if the
569	* value is zero.
570	* @param pBigNum The bit number.
571	*/
572	static uint32_t rtBigNumMagnitudeBitWidth(PCRTBIGNUM pBigNum)
573	{
574	uint32_t idxLast = pBigNum->cUsed;
575	if (idxLast)
576	{
577	idxLast--;
578	RTBIGNUMELEMENT uLast = pBigNum->pauElements[idxLast]; Assert(uLast);
579	return rtBigNumElementBitCount(uLast) + idxLast * RTBIGNUM_ELEMENT_BITS;
580	}
581	return 0;
582	}
583
584
585	RTDECL(uint32_t) RTBigNumBitWidth(PCRTBIGNUM pBigNum)
586	{
587	uint32_t idxLast = pBigNum->cUsed;
588	if (idxLast)
589	{
590	idxLast--;
591	rtBigNumUnscramble((PRTBIGNUM)pBigNum);
592	RTBIGNUMELEMENT uLast = pBigNum->pauElements[idxLast]; Assert(uLast);
593	rtBigNumScramble((PRTBIGNUM)pBigNum);
594	return rtBigNumElementBitCount(uLast) + idxLast * RTBIGNUM_ELEMENT_BITS + pBigNum->fNegative;
595	}
596	return 0;
597	}
598
599
600	RTDECL(uint32_t) RTBigNumByteWidth(PCRTBIGNUM pBigNum)
601	{
602	uint32_t cBits = RTBigNumBitWidth(pBigNum);
603	return (cBits + 7) / 8;
604	}
605
606
607	RTDECL(int) RTBigNumToBytesBigEndian(PCRTBIGNUM pBigNum, void *pvBuf, size_t cbWanted)
608	{
609	AssertPtrReturn(pvBuf, VERR_INVALID_POINTER);
610	AssertReturn(cbWanted > 0, VERR_INVALID_PARAMETER);
611
612	int rc = rtBigNumUnscramble((PRTBIGNUM)pBigNum);
613	if (RT_SUCCESS(rc))
614	{
615	rc = VINF_SUCCESS;
616	if (pBigNum->cUsed != 0)
617	{
618	uint8_t pbDst = (uint8_t )pvBuf;
619	pbDst += cbWanted - 1;
620	for (uint32_t i = 0; i < pBigNum->cUsed; i++)
621	{
622	RTBIGNUMELEMENT uElement = pBigNum->pauElements[i];
623	if (pBigNum->fNegative)
624	uElement = (RTBIGNUMELEMENT)0 - uElement - (i > 0);
625	if (cbWanted >= sizeof(uElement))
626	{
627	*pbDst-- = (uint8_t)uElement;
628	uElement >>= 8;
629	*pbDst-- = (uint8_t)uElement;
630	uElement >>= 8;
631	*pbDst-- = (uint8_t)uElement;
632	uElement >>= 8;
633	*pbDst-- = (uint8_t)uElement;
634	#if RTBIGNUM_ELEMENT_SIZE == 8
635	uElement >>= 8;
636	*pbDst-- = (uint8_t)uElement;
637	uElement >>= 8;
638	*pbDst-- = (uint8_t)uElement;
639	uElement >>= 8;
640	*pbDst-- = (uint8_t)uElement;
641	uElement >>= 8;
642	*pbDst-- = (uint8_t)uElement;
643	#elif RTBIGNUM_ELEMENT_SIZE != 4
644	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
645	#endif
646	cbWanted -= sizeof(uElement);
647	}
648	else
649	{
650
651	uint32_t cBitsLeft = RTBIGNUM_ELEMENT_BITS;
652	while (cbWanted > 0)
653	{
654	*pbDst-- = (uint8_t)uElement;
655	uElement >>= 8;
656	cBitsLeft -= 8;
657	cbWanted--;
658	}
659	Assert(cBitsLeft > 0); Assert(cBitsLeft < RTBIGNUM_ELEMENT_BITS);
660	if ( i + 1 < pBigNum->cUsed
661	\|\| ( !pBigNum->fNegative
662	? uElement != 0
663	: uElement != ((RTBIGNUMELEMENT)1 << cBitsLeft) - 1U ) )
664	rc = VERR_BUFFER_OVERFLOW;
665	break;
666	}
667	}
668
669	/* Sign extend the number to the desired output size. */
670	if (cbWanted > 0)
671	memset(pbDst - cbWanted, pBigNum->fNegative ? 0 : 0xff, cbWanted);
672	}
673	else
674	RT_BZERO(pvBuf, cbWanted);
675	rtBigNumScramble((PRTBIGNUM)pBigNum);
676	}
677	return rc;
678	}
679
680
681	RTDECL(int) RTBigNumCompare(PRTBIGNUM pLeft, PRTBIGNUM pRight)
682	{
683	int rc = rtBigNumUnscramble(pLeft);
684	if (RT_SUCCESS(rc))
685	{
686	rc = rtBigNumUnscramble(pRight);
687	if (RT_SUCCESS(rc))
688	{
689	if (pLeft->fNegative == pRight->fNegative)
690	{
691	if (pLeft->cUsed == pRight->cUsed)
692	{
693	rc = 0;
694	uint32_t i = pLeft->cUsed;
695	while (i-- > 0)
696	if (pLeft->pauElements[i] != pRight->pauElements[i])
697	{
698	rc = pLeft->pauElements[i] < pRight->pauElements[i] ? -1 : 1;
699	break;
700	}
701	if (pLeft->fNegative)
702	rc = -rc;
703	}
704	else
705	rc = !pLeft->fNegative
706	? pLeft->cUsed < pRight->cUsed ? -1 : 1
707	: pLeft->cUsed < pRight->cUsed ? 1 : -1;
708	}
709	else
710	rc = pLeft->fNegative ? -1 : 1;
711
712	rtBigNumScramble(pRight);
713	}
714	rtBigNumScramble(pLeft);
715	}
716	return rc;
717	}
718
719
720	RTDECL(int) RTBigNumCompareWithU64(PRTBIGNUM pLeft, uint64_t uRight)
721	{
722	int rc = rtBigNumUnscramble(pLeft);
723	if (RT_SUCCESS(rc))
724	{
725	if (!pLeft->fNegative)
726	{
727	if (pLeft->cUsed * RTBIGNUM_ELEMENT_SIZE <= sizeof(uRight))
728	{
729	if (pLeft->cUsed == 0)
730	rc = uRight == 0 ? 0 : -1;
731	else
732	{
733	#if RTBIGNUM_ELEMENT_SIZE == 8
734	uint64_t uLeft = rtBigNumGetElement(pLeft, 0);
735	if (uLeft < uRight)
736	rc = -1;
737	else
738	rc = uLeft == uRight ? 0 : 1;
739	#elif RTBIGNUM_ELEMENT_SIZE == 4
740	uint32_t uSubLeft = rtBigNumGetElement(pLeft, 1);
741	uint32_t uSubRight = uRight >> 32;
742	if (uSubLeft == uSubRight)
743	{
744	uSubLeft = rtBigNumGetElement(pLeft, 0);
745	uSubRight = (uint32_t)uRight;
746	}
747	if (uSubLeft < uSubRight)
748	rc = -1;
749	else
750	rc = uSubLeft == uSubRight ? 0 : 1;
751	#else
752	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
753	#endif
754	}
755	}
756	else
757	rc = 1;
758	}
759	else
760	rc = -1;
761	rtBigNumScramble(pLeft);
762	}
763	return rc;
764	}
765
766
767	RTDECL(int) RTBigNumCompareWithS64(PRTBIGNUM pLeft, int64_t iRight)
768	{
769	int rc = rtBigNumUnscramble(pLeft);
770	if (RT_SUCCESS(rc))
771	{
772	if (pLeft->fNegative == (iRight < 0))
773	{
774	if (pLeft->cUsed * RTBIGNUM_ELEMENT_SIZE <= sizeof(iRight))
775	{
776	uint64_t uRightMagn = !pLeft->fNegative ? (uint64_t)iRight : (uint64_t)-iRight;
777	#if RTBIGNUM_ELEMENT_SIZE == 8
778	uint64_t uLeft = rtBigNumGetElement(pLeft, 0);
779	if (uLeft < uRightMagn)
780	rc = -1;
781	else
782	rc = uLeft == (uint64_t)uRightMagn ? 0 : 1;
783	#elif RTBIGNUM_ELEMENT_SIZE == 4
784	uint32_t uSubLeft = rtBigNumGetElement(pLeft, 1);
785	uint32_t uSubRight = uRightMagn >> 32;
786	if (uSubLeft == uSubRight)
787	{
788	uSubLeft = rtBigNumGetElement(pLeft, 0);
789	uSubRight = (uint32_t)uRightMagn;
790	}
791	if (uSubLeft < uSubRight)
792	rc = -1;
793	else
794	rc = uSubLeft == uSubRight ? 0 : 1;
795	#else
796	# error "Bad RTBIGNUM_ELEMENT_SIZE value"
797	#endif
798	if (pLeft->fNegative)
799	rc = -rc;
800	}
801	else
802	rc = pLeft->fNegative ? -1 : 1;
803	}
804	else
805	rc = pLeft->fNegative ? -1 : 1;
806	rtBigNumScramble(pLeft);
807	}
808	return rc;
809	}
810
811
812	#define RTBIGNUMELEMENT_HALF_MASK ( ((RTBIGNUMELEMENT)1 << (RTBIGNUM_ELEMENT_BITS / 2)) - (RTBIGNUMELEMENT)1)
813	#define RTBIGNUMELEMENT_LO_HALF(a_uElement) ( (RTBIGNUMELEMENT_HALF_MASK) & (a_uElement) )
814	#define RTBIGNUMELEMENT_HI_HALF(a_uElement) ( (a_uElement) >> (RTBIGNUM_ELEMENT_BITS / 2) )
815
816
817	/**
818	* Compares the magnitude values of two big numbers.
819	*
820	* @retval -1 if pLeft is smaller than pRight.
821	* @retval 0 if pLeft is equal to pRight.
822	* @retval 1 if pLeft is larger than pRight.
823	* @param pLeft The left side number.
824	* @param pRight The right side number.
825	*/
826	static int rtBigNumMagnitudeCompare(PCRTBIGNUM pLeft, PCRTBIGNUM pRight)
827	{
828	Assert(!pLeft->fCurScrambled); Assert(!pRight->fCurScrambled);
829	int rc;
830	uint32_t i = pLeft->cUsed;
831	if (i == pRight->cUsed)
832	{
833	rc = 0;
834	while (i-- > 0)
835	if (pLeft->pauElements[i] != pRight->pauElements[i])
836	{
837	rc = pLeft->pauElements[i] < pRight->pauElements[i] ? -1 : 1;
838	break;
839	}
840	}
841	else
842	rc = i < pRight->cUsed ? -1 : 1;
843	return rc;
844	}
845
846
847	/**
848	* Does addition with carry.
849	*
850	* This is a candidate for inline assembly on some platforms.
851	*
852	* @returns The result (the sum)
853	* @param uAugend What to add to.
854	* @param uAddend What to add to it.
855	* @param pfCarry Where to read the input carry and return the output
856	* carry.
857	*/
858	DECLINLINE(RTBIGNUMELEMENT) rtBigNumElementAddWithCarry(RTBIGNUMELEMENT uAugend, RTBIGNUMELEMENT uAddend,
859	RTBIGNUMELEMENT *pfCarry)
860	{
861	RTBIGNUMELEMENT uRet = uAugend + uAddend + *pfCarry;
862
863	/* Determin carry the expensive way. */
864	RTBIGNUMELEMENT uTmp = RTBIGNUMELEMENT_HI_HALF(uAugend) + RTBIGNUMELEMENT_HI_HALF(uAddend);
865	if (uTmp < RTBIGNUMELEMENT_HALF_MASK)
866	*pfCarry = 0;
867	else
868	*pfCarry = uTmp > RTBIGNUMELEMENT_HALF_MASK
869	\|\| RTBIGNUMELEMENT_LO_HALF(uAugend) + RTBIGNUMELEMENT_LO_HALF(uAddend) + *pfCarry
870	> RTBIGNUMELEMENT_HALF_MASK;
871	return uRet;
872	}
873
874
875	/**
876	* Adds two magnitudes and stores them into a third.
877	*
878	* All variables must be unscrambled. The sign flag is not considered nor
879	* touched.
880	*
881	* @returns IPRT status code.
882	* @param pResult The resultant.
883	* @param pAugend To whom it shall be addede.
884	* @param pAddend The nombre to addede.
885	*/
886	static int rtBigNumMagnitudeAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend)
887	{
888	Assert(!pResult->fCurScrambled); Assert(!pAugend->fCurScrambled); Assert(!pAddend->fCurScrambled);
889	Assert(pResult != pAugend); Assert(pResult != pAddend);
890
891	uint32_t cElements = RT_MAX(pAugend->cUsed, pAddend->cUsed);
892	int rc = rtBigNumSetUsed(pResult, cElements);
893	if (RT_SUCCESS(rc))
894	{
895	/*
896	* The primitive way, requires at least two additions for each entry
897	* without machine code help.
898	*/
899	RTBIGNUMELEMENT fCarry = 0;
900	for (uint32_t i = 0; i < cElements; i++)
901	pResult->pauElements[i] = rtBigNumElementAddWithCarry(rtBigNumGetElement(pAugend, i),
902	rtBigNumGetElement(pAddend, i),
903	&fCarry);
904	if (fCarry)
905	{
906	rc = rtBigNumSetUsed(pResult, cElements + 1);
907	if (RT_SUCCESS(rc))
908	pResult->pauElements[cElements++] = 1;
909	}
910	Assert(pResult->cUsed == cElements \|\| RT_FAILURE_NP(rc));
911	}
912
913	return rc;
914	}
915
916
917	/**
918	* Does addition with borrow.
919	*
920	* This is a candidate for inline assembly on some platforms.
921	*
922	* @returns The result (the sum)
923	* @param uMinuend What to subtract from.
924	* @param uSubtrahend What to subtract.
925	* @param pfBorrow Where to read the input borrow and return the output
926	* borrow.
927	*/
928	DECLINLINE(RTBIGNUMELEMENT) rtBigNumElementSubWithBorrow(RTBIGNUMELEMENT uMinuend, RTBIGNUMELEMENT uSubtrahend,
929	RTBIGNUMELEMENT *pfBorrow)
930	{
931	RTBIGNUMELEMENT uRet = uMinuend - uSubtrahend - *pfBorrow;
932
933	/* Figure out if we borrowed. */
934	pfBorrow = !pfBorrow ? uMinuend < uSubtrahend : uMinuend <= uSubtrahend;
935	return uRet;
936	}
937
938
939	/**
940	* Substracts a smaller (or equal) magnitude from another one and stores it into
941	* a third.
942	*
943	* All variables must be unscrambled. The sign flag is not considered nor
944	* touched. For this reason, the @a pMinuend must be larger or equal to @a
945	* pSubtrahend.
946	*
947	* @returns IPRT status code.
948	* @param pResult There to store the result.
949	* @param pMinuend What to subtract from.
950	* @param pSubtrahend What to subtract.
951	*/
952	static int rtBigNumMagnitudeSub(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend)
953	{
954	Assert(!pResult->fCurScrambled); Assert(!pMinuend->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
955	Assert(pResult != pMinuend); Assert(pResult != pSubtrahend);
956	Assert(pMinuend->cUsed >= pSubtrahend->cUsed);
957
958	int rc = rtBigNumSetUsed(pResult, pMinuend->cUsed);
959	if (RT_SUCCESS(rc))
960	{
961	/*
962	* The primitive way, as usual.
963	*/
964	RTBIGNUMELEMENT fBorrow = 0;
965	for (uint32_t i = 0; i < pMinuend->cUsed; i++)
966	pResult->pauElements[i] = rtBigNumElementSubWithBorrow(pMinuend->pauElements[i],
967	rtBigNumGetElement(pSubtrahend, i),
968	&fBorrow);
969	Assert(fBorrow == 0);
970
971	/*
972	* Trim the result.
973	*/
974	rtBigNumStripTrailingZeros(pResult);
975	}
976
977	return rc;
978	}
979
980
981	/**
982	* Substracts a smaller (or equal) magnitude from another one and stores the
983	* result into the first.
984	*
985	* All variables must be unscrambled. The sign flag is not considered nor
986	* touched. For this reason, the @a pMinuendResult must be larger or equal to
987	* @a pSubtrahend.
988	*
989	* @param pMinuendResult What to subtract from and return as result.
990	* @param pSubtrahend What to subtract.
991	*/
992	static void rtBigNumMagnitudeSubThis(PRTBIGNUM pMinuendResult, PCRTBIGNUM pSubtrahend)
993	{
994	Assert(!pMinuendResult->fCurScrambled); Assert(!pSubtrahend->fCurScrambled);
995	Assert(pMinuendResult != pSubtrahend);
996	Assert(pMinuendResult->cUsed >= pSubtrahend->cUsed);
997
998	/*
999	* The primitive way, as usual.
1000	*/
1001	RTBIGNUMELEMENT fBorrow = 0;
1002	for (uint32_t i = 0; i < pMinuendResult->cUsed; i++)
1003	pMinuendResult->pauElements[i] = rtBigNumElementSubWithBorrow(pMinuendResult->pauElements[i],
1004	rtBigNumGetElement(pSubtrahend, i),
1005	&fBorrow);
1006	Assert(fBorrow == 0);
1007
1008	/*
1009	* Trim the result.
1010	*/
1011	rtBigNumStripTrailingZeros(pMinuendResult);
1012	}
1013
1014
1015	RTDECL(int) RTBigNumAdd(PRTBIGNUM pResult, PCRTBIGNUM pAugend, PCRTBIGNUM pAddend)
1016	{
1017	Assert(pResult != pAugend); Assert(pResult != pAddend);
1018	AssertReturn(pResult->fSensitive >= (pAugend->fSensitive \| pAddend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1019
1020	int rc = rtBigNumUnscramble(pResult);
1021	if (RT_SUCCESS(rc))
1022	{
1023	rc = rtBigNumUnscramble((PRTBIGNUM)pAugend);
1024	if (RT_SUCCESS(rc))
1025	{
1026	rc = rtBigNumUnscramble((PRTBIGNUM)pAddend);
1027	if (RT_SUCCESS(rc))
1028	{
1029	/*
1030	* Same sign: Add magnitude, keep sign.
1031	* 1 + 1 = 2
1032	* (-1) + (-1) = -2
1033	*/
1034	if (pAugend->fNegative == pAddend->fNegative)
1035	{
1036	pResult->fNegative = pAugend->fNegative;
1037	rc = rtBigNumMagnitudeAdd(pResult, pAugend, pAddend);
1038	}
1039	/*
1040	* Different sign: Subtract smaller from larger, keep sign of larger.
1041	* (-5) + 3 = -2
1042	* 5 + (-3) = 2
1043	* (-1) + 3 = 2
1044	* 1 + (-3) = -2
1045	*/
1046	else if (rtBigNumMagnitudeCompare(pAugend, pAddend) >= 0)
1047	{
1048	pResult->fNegative = pAugend->fNegative;
1049	rc = rtBigNumMagnitudeSub(pResult, pAugend, pAddend);
1050	if (!pResult->cUsed)
1051	pResult->fNegative = 0;
1052	}
1053	else
1054	{
1055	pResult->fNegative = pAddend->fNegative;
1056	rc = rtBigNumMagnitudeSub(pResult, pAddend, pAugend);
1057	}
1058	rtBigNumScramble((PRTBIGNUM)pAddend);
1059	}
1060	rtBigNumScramble((PRTBIGNUM)pAugend);
1061	}
1062	rtBigNumScramble(pResult);
1063	}
1064	return rc;
1065	}
1066
1067
1068	RTDECL(int) RTBigNumSubtract(PRTBIGNUM pResult, PCRTBIGNUM pMinuend, PCRTBIGNUM pSubtrahend)
1069	{
1070	Assert(pResult != pMinuend); Assert(pResult != pSubtrahend);
1071	AssertReturn(pResult->fSensitive >= (pMinuend->fSensitive \| pSubtrahend->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1072
1073	int rc = rtBigNumUnscramble(pResult);
1074	if (RT_SUCCESS(rc))
1075	{
1076	if (pMinuend != pSubtrahend)
1077	{
1078	rc = rtBigNumUnscramble((PRTBIGNUM)pMinuend);
1079	if (RT_SUCCESS(rc))
1080	{
1081	rc = rtBigNumUnscramble((PRTBIGNUM)pSubtrahend);
1082	if (RT_SUCCESS(rc))
1083	{
1084	/*
1085	* Different sign: Add magnitude, keep sign of first.
1086	* 1 - (-2) == 3
1087	* -1 - 2 == -3
1088	*/
1089	if (pMinuend->fNegative != pSubtrahend->fNegative)
1090	{
1091	pResult->fNegative = pMinuend->fNegative;
1092	rc = rtBigNumMagnitudeAdd(pResult, pMinuend, pSubtrahend);
1093	}
1094	/*
1095	* Same sign, minuend has greater or equal absolute value: Subtract, keep sign of first.
1096	* 10 - 7 = 3
1097	*/
1098	else if (rtBigNumMagnitudeCompare(pMinuend, pSubtrahend) >= 0)
1099	{
1100	pResult->fNegative = pMinuend->fNegative;
1101	rc = rtBigNumMagnitudeSub(pResult, pMinuend, pSubtrahend);
1102	}
1103	/*
1104	* Same sign, subtrahend is larger: Reverse and subtract, invert sign of first.
1105	* 7 - 10 = -3
1106	* -1 - (-3) = 2
1107	*/
1108	else
1109	{
1110	pResult->fNegative = !pMinuend->fNegative;
1111	rc = rtBigNumMagnitudeSub(pResult, pSubtrahend, pMinuend);
1112	}
1113	rtBigNumScramble((PRTBIGNUM)pSubtrahend);
1114	}
1115	rtBigNumScramble((PRTBIGNUM)pMinuend);
1116	}
1117	}
1118	else
1119	{
1120	/* zero. */
1121	pResult->fNegative = 0;
1122	pResult->cUsed = 0;
1123	}
1124	rtBigNumScramble(pResult);
1125	}
1126	return rc;
1127	}
1128
1129
1130	RTDECL(int) RTBigNumNegateThis(PRTBIGNUM pThis)
1131	{
1132	pThis->fNegative = !pThis->fNegative;
1133	return VINF_SUCCESS;
1134	}
1135
1136
1137	RTDECL(int) RTBigNumNegate(PRTBIGNUM pResult, PCRTBIGNUM pBigNum)
1138	{
1139	int rc = RTBigNumAssign(pResult, pBigNum);
1140	if (RT_SUCCESS(rc))
1141	rc = RTBigNumNegateThis(pResult);
1142	return rc;
1143	}
1144
1145
1146	/**
1147	* Multiplies the magnitudes of two values, letting the caller care about the
1148	* sign bit.
1149	*
1150	* @returns IPRT status code.
1151	* @param pResult Where to store the result.
1152	* @param pMultiplicand The first value.
1153	* @param pMultiplier The second value.
1154	*/
1155	static int rtBigNumMagnitudeMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
1156	{
1157	Assert(pResult != pMultiplicand); Assert(pResult != pMultiplier);
1158	Assert(!pResult->fCurScrambled); Assert(!pMultiplicand->fCurScrambled); Assert(!pMultiplier->fCurScrambled);
1159
1160	/*
1161	* Multiplication involving zero is zero.
1162	*/
1163	if (!pMultiplicand->cUsed \|\| !pMultiplier->cUsed)
1164	{
1165	pResult->fNegative = 0;
1166	pResult->cUsed = 0;
1167	return VINF_SUCCESS;
1168	}
1169
1170	/*
1171	* Allocate a result array that is the sum of the two factors, initialize
1172	* it to zero.
1173	*/
1174	uint32_t cMax = pMultiplicand->cUsed + pMultiplier->cUsed;
1175	int rc = rtBigNumSetUsed(pResult, cMax);
1176	if (RT_SUCCESS(rc))
1177	{
1178	RT_BZERO(pResult->pauElements, pResult->cUsed * RTBIGNUM_ELEMENT_SIZE);
1179
1180	for (uint32_t i = 0; i < pMultiplier->cUsed; i++)
1181	{
1182	RTBIGNUMELEMENT uMultiplier = pMultiplier->pauElements[i];
1183	for (uint32_t j = 0; j < pMultiplicand->cUsed; j++)
1184	{
1185	RTBIGNUMELEMENT uHi;
1186	RTBIGNUMELEMENT uLo;
1187	#if RTBIGNUM_ELEMENT_SIZE == 4
1188	uint64_t u64 = ASMMult2xU32RetU64(pMultiplicand->pauElements[j], uMultiplier);
1189	uLo = (uint32_t)u64;
1190	uHi = u64 >> 32;
1191	#elif RTBIGNUM_ELEMENT_SIZE == 8
1192	uLo = ASMMult2xU64Ret2xU64(pMultiplicand->pauElements[j], uMultiplier, &uHi);
1193	#else
1194	# error "Invalid RTBIGNUM_ELEMENT_SIZE value"
1195	#endif
1196	RTBIGNUMELEMENT fCarry = 0;
1197	uint64_t k = i + j;
1198	pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], uLo, &fCarry);
1199	k++;
1200	pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], uHi, &fCarry);
1201	while (fCarry)
1202	{
1203	k++;
1204	pResult->pauElements[k] = rtBigNumElementAddWithCarry(pResult->pauElements[k], 0, &fCarry);
1205	}
1206	Assert(k < cMax);
1207	}
1208	}
1209
1210	/* It's possible we overestimated the output size by 1 element. */
1211	rtBigNumStripTrailingZeros(pResult);
1212	}
1213	return rc;
1214	}
1215
1216
1217	RTDECL(int) RTBigNumMultiply(PRTBIGNUM pResult, PCRTBIGNUM pMultiplicand, PCRTBIGNUM pMultiplier)
1218	{
1219	Assert(pResult != pMultiplicand); Assert(pResult != pMultiplier);
1220	AssertReturn(pResult->fSensitive >= (pMultiplicand->fSensitive \| pMultiplier->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1221
1222	int rc = rtBigNumUnscramble(pResult);
1223	if (RT_SUCCESS(rc))
1224	{
1225	rc = rtBigNumUnscramble((PRTBIGNUM)pMultiplicand);
1226	if (RT_SUCCESS(rc))
1227	{
1228	rc = rtBigNumUnscramble((PRTBIGNUM)pMultiplier);
1229	if (RT_SUCCESS(rc))
1230	{
1231	/*
1232	* The sign values follow XOR rules:
1233	* -1 * 1 = -1; 1 ^ 0 = 1
1234	* 1 * -1 = -1; 1 ^ 0 = 1
1235	* -1 * -1 = 1; 1 ^ 1 = 0
1236	* 1 * 1 = 1; 0 ^ 0 = 0
1237	*/
1238	pResult->fNegative = pMultiplicand->fNegative ^ pMultiplier->fNegative;
1239	rc = rtBigNumMagnitudeMultiply(pResult, pMultiplicand, pMultiplier);
1240
1241	rtBigNumScramble((PRTBIGNUM)pMultiplier);
1242	}
1243	rtBigNumScramble((PRTBIGNUM)pMultiplicand);
1244	}
1245	rtBigNumScramble(pResult);
1246	}
1247	return rc;
1248	}
1249
1250
1251	/**
1252	* Copies the magnitude of on number (@a pSrc) to another (@a pBigNum).
1253	*
1254	* The variables must be unscrambled. The sign flag is not considered nor
1255	* touched.
1256	*
1257	* @returns IPRT status code.
1258	* @param pDst The destination number.
1259	* @param pSrc The source number.
1260	*/
1261	DECLINLINE(int) rtBigNumMagnitudeCopy(PRTBIGNUM pDst, PCRTBIGNUM pSrc)
1262	{
1263	int rc = rtBigNumSetUsed(pDst, pSrc->cUsed);
1264	if (RT_SUCCESS(rc))
1265	memcpy(pDst->pauElements, pSrc->pauElements, pSrc->cUsed * RTBIGNUM_ELEMENT_SIZE);
1266	return rc;
1267	}
1268
1269
1270	/**
1271	* Clears a bit in the magnitude of @a pBigNum.
1272	*
1273	* The variables must be unscrambled.
1274	*
1275	* @param pBigNum The big number.
1276	* @param iBit The bit to clear (0-based).
1277	*/
1278	DECLINLINE(void) rtBigNumMagnitudeClearBit(PRTBIGNUM pBigNum, uint32_t iBit)
1279	{
1280	uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1281	if (iElement < pBigNum->cUsed)
1282	{
1283	pBigNum->pauElements[iElement] &= ~RTBIGNUM_ELEMENT_BIT(iBit);
1284	if (iElement + 1 == pBigNum->cUsed && !pBigNum->pauElements[iElement])
1285	rtBigNumStripTrailingZeros(pBigNum);
1286	}
1287	}
1288
1289
1290	/**
1291	* Sets a bit in the magnitude of @a pBigNum.
1292	*
1293	* The variables must be unscrambled.
1294	*
1295	* @returns IPRT status code.
1296	* @param pBigNum The big number.
1297	* @param iBit The bit to clear (0-based).
1298	*/
1299	DECLINLINE(int) rtBigNumMagnitudeSetBit(PRTBIGNUM pBigNum, uint32_t iBit)
1300	{
1301	uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1302	int rc = rtBigNumEnsureElementPresent(pBigNum, iElement);
1303	if (RT_SUCCESS(rc))
1304	{
1305	pBigNum->pauElements[iElement] \|= RTBIGNUM_ELEMENT_BIT(iBit);
1306	return VINF_SUCCESS;
1307	}
1308	return rc;
1309	}
1310
1311
1312	/**
1313	* Writes a bit in the magnitude of @a pBigNum.
1314	*
1315	* The variables must be unscrambled.
1316	*
1317	* @returns IPRT status code.
1318	* @param pBigNum The big number.
1319	* @param iBit The bit to write (0-based).
1320	* @param fValue The bit value.
1321	*/
1322	DECLINLINE(int) rtBigNumMagnitudeWriteBit(PRTBIGNUM pBigNum, uint32_t iBit, bool fValue)
1323	{
1324	if (fValue)
1325	return rtBigNumMagnitudeSetBit(pBigNum, iBit);
1326	rtBigNumMagnitudeClearBit(pBigNum, iBit);
1327	return VINF_SUCCESS;
1328	}
1329
1330
1331	/**
1332	* Returns the given magnitude bit.
1333	*
1334	* The variables must be unscrambled.
1335	*
1336	* @returns The bit value (1 or 0).
1337	* @param pBigNum The big number.
1338	* @param iBit The bit to return (0-based).
1339	*/
1340	DECLINLINE(RTBIGNUMELEMENT) rtBigNumMagnitudeGetBit(PCRTBIGNUM pBigNum, uint32_t iBit)
1341	{
1342	uint32_t iElement = iBit / RTBIGNUM_ELEMENT_BITS;
1343	if (iElement < pBigNum->cUsed)
1344	return (pBigNum->pauElements[iElement] >> iBit) & 1;
1345	return 0;
1346	}
1347
1348
1349	/**
1350	* Shifts the magnitude left by one.
1351	*
1352	* The variables must be unscrambled.
1353	*
1354	* @returns IPRT status code.
1355	* @param pBigNum The big number.
1356	* @param uCarry The value to shift in at the bottom.
1357	*/
1358	DECLINLINE(int) rtBigNumMagnitudeShiftLeftOne(PRTBIGNUM pBigNum, RTBIGNUMELEMENT uCarry)
1359	{
1360	Assert(uCarry <= 1);
1361
1362	/* Do the shifting. */
1363	uint32_t cUsed = pBigNum->cUsed;
1364	for (uint32_t i = 0; i < cUsed; i++)
1365	{
1366	RTBIGNUMELEMENT uTmp = pBigNum->pauElements[i];
1367	pBigNum->pauElements[i] = (uTmp << 1) \| uCarry;
1368	uCarry = uTmp >> (RTBIGNUM_ELEMENT_BITS - 1);
1369	}
1370
1371	/* If we still carry a bit, we need to increase the size. */
1372	if (uCarry)
1373	{
1374	int rc = rtBigNumSetUsed(pBigNum, cUsed + 1);
1375	pBigNum->pauElements[cUsed] = uCarry;
1376	}
1377
1378	return VINF_SUCCESS;
1379	}
1380
1381
1382	/**
1383	* Divides the magnitudes of two values, letting the caller care about the sign
1384	* bit.
1385	*
1386	* All variables must be unscrambled. The sign flag is not considered nor
1387	* touched, this means the caller have to check for zero outputs.
1388	*
1389	* @returns IPRT status code.
1390	* @param pQuotient Where to return the quotient.
1391	* @param pRemainder Where to return the reminder.
1392	* @param pDividend What to divide.
1393	* @param pDivisor What to divide by.
1394	*/
1395	static int rtBigNumMagnitudeDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
1396	{
1397	Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
1398	Assert(!pQuotient->fCurScrambled); Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
1399
1400	/*
1401	* Just set both output values to zero as that's the return for several
1402	* special case and the initial state of the general case.
1403	*/
1404	pQuotient->cUsed = 0;
1405	pRemainder->cUsed = 0;
1406
1407	/*
1408	* Dividing something by zero is undefined.
1409	* Diving zero by something is zero, unless the divsor is also zero.
1410	*/
1411	if (!pDivisor->cUsed \|\| !pDividend->cUsed)
1412	return pDivisor->cUsed ? VINF_SUCCESS : VERR_BIGNUM_DIV_BY_ZERO;
1413
1414	/*
1415	* Dividing by one? Quotient = dividend, no remainder.
1416	*/
1417	if (pDivisor->cUsed == 1 && pDivisor->pauElements[0] == 1)
1418	return rtBigNumMagnitudeCopy(pQuotient, pDividend);
1419
1420	/*
1421	* Dividend smaller than the divisor. Zero quotient, all divisor.
1422	*/
1423	int iDiff = rtBigNumMagnitudeCompare(pDividend, pDivisor);
1424	if (iDiff < 0)
1425	return rtBigNumMagnitudeCopy(pRemainder, pDividend);
1426
1427	/*
1428	* Since we already have done the compare, check if the two values are the
1429	* same. The result is 1 and no remainder then.
1430	*/
1431	if (iDiff == 0)
1432	{
1433	int rc = rtBigNumSetUsed(pQuotient, 1);
1434	if (RT_SUCCESS(rc))
1435	pQuotient->pauElements[0] = 1;
1436	return rc;
1437	}
1438
1439	/*
1440	* Do very simple long division. This ain't fast, but it does the trick.
1441	*/
1442	int rc = VINF_SUCCESS;
1443	uint32_t iBit = rtBigNumMagnitudeBitWidth(pDividend);
1444	while (iBit-- > 0)
1445	{
1446	rc = rtBigNumMagnitudeShiftLeftOne(pRemainder, rtBigNumMagnitudeGetBit(pDividend, iBit));
1447	AssertRCBreak(rc);
1448	iDiff = rtBigNumMagnitudeCompare(pRemainder, pDivisor);
1449	if (iDiff >= 0)
1450	{
1451	if (iDiff != 0)
1452	rtBigNumMagnitudeSubThis(pRemainder, pDivisor);
1453	else
1454	pRemainder->cUsed = 0;
1455	rc = rtBigNumMagnitudeSetBit(pQuotient, iBit);
1456	AssertRCBreak(rc);
1457	}
1458	}
1459
1460	/* This shouldn't be necessary. */
1461	rtBigNumStripTrailingZeros(pQuotient);
1462	rtBigNumStripTrailingZeros(pRemainder);
1463	return rc;
1464	}
1465
1466
1467	RTDECL(int) RTBigNumDivide(PRTBIGNUM pQuotient, PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
1468	{
1469	Assert(pQuotient != pDividend); Assert(pQuotient != pDivisor); Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor); Assert(pRemainder != pQuotient);
1470	AssertReturn(pQuotient->fSensitive >= (pDividend->fSensitive \| pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1471	AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive \| pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1472
1473	int rc = rtBigNumUnscramble(pQuotient);
1474	if (RT_SUCCESS(rc))
1475	{
1476	rc = rtBigNumUnscramble(pRemainder);
1477	if (RT_SUCCESS(rc))
1478	{
1479	rc = rtBigNumUnscramble((PRTBIGNUM)pDividend);
1480	if (RT_SUCCESS(rc))
1481	{
1482	rc = rtBigNumUnscramble((PRTBIGNUM)pDivisor);
1483	if (RT_SUCCESS(rc))
1484	{
1485	/*
1486	* The sign value of the remainder is the same as the dividend.
1487	* The sign values of the quotient follow XOR rules, just like multiplication:
1488	* -3 / 2 = -1; r=-1; 1 ^ 0 = 1
1489	* 3 / -2 = -1; r= 1; 1 ^ 0 = 1
1490	* -3 / -2 = 1; r=-1; 1 ^ 1 = 0
1491	* 3 / 2 = 1; r= 1; 0 ^ 0 = 0
1492	*/
1493	pQuotient->fNegative = pDividend->fNegative ^ pDivisor->fNegative;
1494	pRemainder->fNegative = pDividend->fNegative;
1495
1496	rc = rtBigNumMagnitudeDivide(pQuotient, pRemainder, pDividend, pDivisor);
1497
1498	if (pQuotient->cUsed == 0)
1499	pQuotient->fNegative = 0;
1500	if (pRemainder->cUsed == 0)
1501	pRemainder->fNegative = 0;
1502
1503	rtBigNumScramble((PRTBIGNUM)pDivisor);
1504	}
1505	rtBigNumScramble((PRTBIGNUM)pDividend);
1506	}
1507	rtBigNumScramble(pRemainder);
1508	}
1509	rtBigNumScramble(pQuotient);
1510	}
1511	return rc;
1512	}
1513
1514
1515	/**
1516	* Calculates the modulus of a magnitude value, leaving the sign bit to the
1517	* caller.
1518	*
1519	* All variables must be unscrambled. The sign flag is not considered nor
1520	* touched, this means the caller have to check for zero outputs.
1521	*
1522	* @returns IPRT status code.
1523	* @param pRemainder Where to return the reminder.
1524	* @param pDividend What to divide.
1525	* @param pDivisor What to divide by.
1526	*/
1527	static int rtBigNumMagnitudeModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
1528	{
1529	Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor);
1530	Assert(!pRemainder->fCurScrambled); Assert(!pDividend->fCurScrambled); Assert(!pDivisor->fCurScrambled);
1531
1532	/*
1533	* Just set the output value to zero as that's the return for several
1534	* special case and the initial state of the general case.
1535	*/
1536	pRemainder->cUsed = 0;
1537
1538	/*
1539	* Dividing something by zero is undefined.
1540	* Diving zero by something is zero, unless the divsor is also zero.
1541	*/
1542	if (!pDivisor->cUsed \|\| !pDividend->cUsed)
1543	return pDivisor->cUsed ? VINF_SUCCESS : VERR_BIGNUM_DIV_BY_ZERO;
1544
1545	/*
1546	* Dividing by one? Quotient = dividend, no remainder.
1547	*/
1548	if (pDivisor->cUsed == 1 && pDivisor->pauElements[0] == 1)
1549	return VINF_SUCCESS;
1550
1551	/*
1552	* Dividend smaller than the divisor. Zero quotient, all divisor.
1553	*/
1554	int iDiff = rtBigNumMagnitudeCompare(pDividend, pDivisor);
1555	if (iDiff < 0)
1556	return rtBigNumMagnitudeCopy(pRemainder, pDividend);
1557
1558	/*
1559	* Since we already have done the compare, check if the two values are the
1560	* same. The result is 1 and no remainder then.
1561	*/
1562	if (iDiff == 0)
1563	return VINF_SUCCESS;
1564
1565	/*
1566	* Do very simple long division. This ain't fast, but it does the trick.
1567	*/
1568	int rc = VINF_SUCCESS;
1569	uint32_t iBit = rtBigNumMagnitudeBitWidth(pDividend);
1570	while (iBit-- > 0)
1571	{
1572	rc = rtBigNumMagnitudeShiftLeftOne(pRemainder, rtBigNumMagnitudeGetBit(pDividend, iBit));
1573	AssertRCBreak(rc);
1574	iDiff = rtBigNumMagnitudeCompare(pRemainder, pDivisor);
1575	if (iDiff >= 0)
1576	{
1577	if (iDiff != 0)
1578	rtBigNumMagnitudeSubThis(pRemainder, pDivisor);
1579	else
1580	pRemainder->cUsed = 0;
1581	AssertRCBreak(rc);
1582	}
1583	}
1584
1585	/* This shouldn't be necessary. */
1586	rtBigNumStripTrailingZeros(pRemainder);
1587	return rc;
1588	}
1589
1590
1591	RTDECL(int) RTBigNumModulo(PRTBIGNUM pRemainder, PCRTBIGNUM pDividend, PCRTBIGNUM pDivisor)
1592	{
1593	Assert(pRemainder != pDividend); Assert(pRemainder != pDivisor);
1594	AssertReturn(pRemainder->fSensitive >= (pDividend->fSensitive \| pDivisor->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1595
1596	int rc = rtBigNumUnscramble(pRemainder);
1597	if (RT_SUCCESS(rc))
1598	{
1599	rc = rtBigNumUnscramble((PRTBIGNUM)pDividend);
1600	if (RT_SUCCESS(rc))
1601	{
1602	rc = rtBigNumUnscramble((PRTBIGNUM)pDivisor);
1603	if (RT_SUCCESS(rc))
1604	{
1605	/*
1606	* The sign value of the remainder is the same as the dividend.
1607	*/
1608	pRemainder->fNegative = pDividend->fNegative;
1609
1610	rc = rtBigNumMagnitudeModulo(pRemainder, pDividend, pDivisor);
1611
1612	if (pRemainder->cUsed == 0)
1613	pRemainder->fNegative = 0;
1614
1615	rtBigNumScramble((PRTBIGNUM)pDivisor);
1616	}
1617	rtBigNumScramble((PRTBIGNUM)pDividend);
1618	}
1619	rtBigNumScramble(pRemainder);
1620	}
1621	return rc;
1622	}
1623
1624
1625
1626	/**
1627	* Exponentiate the magnitude.
1628	*
1629	* All variables must be unscrambled. The sign flag is not considered nor
1630	* touched, this means the caller have to reject negative exponents.
1631	*
1632	* @returns IPRT status code.
1633	* @param pResult Where to return power.
1634	* @param pBase The base value.
1635	* @param pExponent The exponent (assumed positive or zero).
1636	*/
1637	static int rtBigNumMagnitudeExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent)
1638	{
1639	Assert(pResult != pBase); Assert(pResult != pExponent);
1640	Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled);
1641
1642	/*
1643	* A couple of special cases.
1644	*/
1645	int rc;
1646	/* base ^ 0 => 1. */
1647	if (pExponent->cUsed == 0)
1648	{
1649	rc = rtBigNumSetUsed(pResult, 1);
1650	if (RT_SUCCESS(rc))
1651	pResult->pauElements[0] = 1;
1652	return rc;
1653	}
1654
1655	/* base ^ 1 => base. */
1656	if (pExponent->cUsed == 1 && pExponent->pauElements[0] == 1)
1657	return rtBigNumMagnitudeCopy(pResult, pBase);
1658
1659	/*
1660	* Set up.
1661	*/
1662	/* Init temporary power-of-two variable to base. */
1663	RTBIGNUM Pow2;
1664	rc = rtBigNumCloneInternal(&Pow2, pBase);
1665	if (RT_SUCCESS(rc))
1666	{
1667	/* Init result to 1. */
1668	rc = rtBigNumSetUsed(pResult, 1);
1669	if (RT_SUCCESS(rc))
1670	{
1671	pResult->pauElements[0] = 1;
1672
1673	/* Make a temporary variable that we can use for temporary storage of the result. */
1674	RTBIGNUM TmpMultiplicand;
1675	rc = rtBigNumCloneInternal(&TmpMultiplicand, pResult);
1676	if (RT_SUCCESS(rc))
1677	{
1678	/*
1679	* Exponentiation by squaring. Reduces the number of
1680	* multiplications to: NumBitsSet(Exponent) + BitWidth(Exponent).
1681	*/
1682	uint32_t const cExpBits = rtBigNumMagnitudeBitWidth(pExponent);
1683	uint32_t iBit = 0;
1684	for (;;)
1685	{
1686	if (rtBigNumMagnitudeGetBit(pExponent, iBit) != 0)
1687	{
1688	rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, pResult);
1689	if (RT_SUCCESS(rc))
1690	rc = rtBigNumMagnitudeMultiply(pResult, &TmpMultiplicand, &Pow2);
1691	if (RT_FAILURE(rc))
1692	break;
1693	}
1694
1695	/* Done? */
1696	iBit++;
1697	if (iBit >= cExpBits)
1698	break;
1699
1700	/* Not done yet, square the base again. */
1701	rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, &Pow2);
1702	if (RT_SUCCESS(rc))
1703	rc = rtBigNumMagnitudeMultiply(&Pow2, &TmpMultiplicand, &TmpMultiplicand);
1704	if (RT_FAILURE(rc))
1705	break;
1706	}
1707	}
1708	}
1709	RTBigNumDestroy(&Pow2);
1710	}
1711	return rc;
1712	}
1713
1714
1715	RTDECL(int) RTBigNumExponentiate(PRTBIGNUM pResult, PCRTBIGNUM pBase, PCRTBIGNUM pExponent)
1716	{
1717	Assert(pResult != pBase); Assert(pResult != pExponent);
1718	AssertReturn(pResult->fSensitive >= (pBase->fSensitive \| pExponent->fSensitive), VERR_BIGNUM_SENSITIVE_INPUT);
1719
1720	int rc = rtBigNumUnscramble(pResult);
1721	if (RT_SUCCESS(rc))
1722	{
1723	rc = rtBigNumUnscramble((PRTBIGNUM)pBase);
1724	if (RT_SUCCESS(rc))
1725	{
1726	rc = rtBigNumUnscramble((PRTBIGNUM)pExponent);
1727	if (RT_SUCCESS(rc))
1728	{
1729	if (!pExponent->fNegative)
1730	{
1731	pResult->fNegative = pBase->fNegative; /* sign unchanged. */
1732	rc = rtBigNumMagnitudeExponentiate(pResult, pBase, pExponent);
1733	}
1734	else
1735	rc = VERR_BIGNUM_NEGATIVE_EXPONENT;
1736
1737	rtBigNumScramble((PRTBIGNUM)pExponent);
1738	}
1739	rtBigNumScramble((PRTBIGNUM)pBase);
1740	}
1741	rtBigNumScramble(pResult);
1742	}
1743	return rc;
1744	}
1745
1746
1747	/**
1748	* Modular exponentiation, magnitudes only.
1749	*
1750	* All variables must be unscrambled. The sign flag is not considered nor
1751	* touched, this means the caller have to reject negative exponents and do any
1752	* other necessary sign bit fiddling.
1753	*
1754	* @returns IPRT status code.
1755	* @param pResult Where to return the remainder of the power.
1756	* @param pBase The base value.
1757	* @param pExponent The exponent (assumed positive or zero).
1758	* @param pModulus The modulus value (or divisor if you like).
1759	*/
1760	static int rtBigNumMagnitudeModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
1761	{
1762	Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
1763	Assert(!pResult->fCurScrambled); Assert(!pBase->fCurScrambled); Assert(!pExponent->fCurScrambled); Assert(!pModulus->fCurScrambled);
1764	int rc;
1765
1766	/*
1767	* Check some special cases to get them out of the way.
1768	*/
1769	/* Div by 0 => invalid. */
1770	if (pModulus->cUsed == 0)
1771	return VERR_BIGNUM_DIV_BY_ZERO;
1772
1773	/* Div by 1 => no remainder. */
1774	if (pModulus->cUsed == 1 && pModulus->pauElements[0] == 1)
1775	{
1776	pResult->cUsed = 0;
1777	return VINF_SUCCESS;
1778	}
1779
1780	/* base ^ 0 => 1. */
1781	if (pExponent->cUsed == 0)
1782	{
1783	rc = rtBigNumSetUsed(pResult, 1);
1784	if (RT_SUCCESS(rc))
1785	pResult->pauElements[0] = 1;
1786	return rc;
1787	}
1788
1789	/* base ^ 1 => base. */
1790	if (pExponent->cUsed == 1 && pExponent->pauElements[0] == 1)
1791	return rtBigNumMagnitudeModulo(pResult, pBase, pModulus);
1792
1793	/*
1794	* Set up.
1795	*/
1796	/* Result = 1; preallocate space for the result while at it. */
1797	rc = rtBigNumSetUsed(pResult, pModulus->cUsed + 1);
1798	if (RT_SUCCESS(rc))
1799	rc = rtBigNumSetUsed(pResult, 1);
1800	if (RT_SUCCESS(rc))
1801	{
1802	pResult->pauElements[0] = 1;
1803
1804	/* ModBase = pBase or pBase % pModulus depending on the difference in size. */
1805	RTBIGNUM Pow2;
1806	if (pBase->cUsed <= pModulus->cUsed + pModulus->cUsed / 2)
1807	rc = rtBigNumCloneInternal(&Pow2, pBase);
1808	else
1809	rc = rtBigNumMagnitudeModulo(rtBigNumInitZeroTemplate(&Pow2, pBase), pBase, pModulus);
1810
1811	/* Need a couple of temporary variables. */
1812	RTBIGNUM TmpMultiplicand;
1813	rtBigNumInitZeroTemplate(&TmpMultiplicand, pResult);
1814
1815	RTBIGNUM TmpProduct;
1816	rtBigNumInitZeroTemplate(&TmpProduct, pResult);
1817
1818	/*
1819	* We combine the exponentiation by squaring with the fact that:
1820	* (ab) mod n = ( (a mod n) (b mod n) ) mod n
1821	*
1822	* Thus, we can reduce the size of intermediate results by mod'ing them
1823	* in each step.
1824	*/
1825	uint32_t const cExpBits = rtBigNumMagnitudeBitWidth(pExponent);
1826	uint32_t iBit = 0;
1827	for (;;)
1828	{
1829	if (rtBigNumMagnitudeGetBit(pExponent, iBit) != 0)
1830	{
1831	rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, pResult);
1832	if (RT_SUCCESS(rc))
1833	rc = rtBigNumMagnitudeMultiply(&TmpProduct, &TmpMultiplicand, &Pow2);
1834	if (RT_SUCCESS(rc))
1835	rc = rtBigNumMagnitudeModulo(pResult, &TmpProduct, pModulus);
1836	if (RT_FAILURE(rc))
1837	break;
1838	}
1839
1840	/* Done? */
1841	iBit++;
1842	if (iBit >= cExpBits)
1843	break;
1844
1845	/* Not done yet, square and mod the base again. */
1846	rc = rtBigNumMagnitudeCopy(&TmpMultiplicand, &Pow2);
1847	if (RT_SUCCESS(rc))
1848	rc = rtBigNumMagnitudeMultiply(&TmpProduct, &TmpMultiplicand, &TmpMultiplicand);
1849	if (RT_SUCCESS(rc))
1850	rc = rtBigNumMagnitudeModulo(&Pow2, &TmpProduct, pModulus);
1851	if (RT_FAILURE(rc))
1852	break;
1853	}
1854
1855	RTBigNumDestroy(&TmpMultiplicand);
1856	RTBigNumDestroy(&TmpProduct);
1857	RTBigNumDestroy(&Pow2);
1858	}
1859	return rc;
1860	}
1861
1862
1863	RTDECL(int) RTBigNumModExp(PRTBIGNUM pResult, PRTBIGNUM pBase, PRTBIGNUM pExponent, PRTBIGNUM pModulus)
1864	{
1865	Assert(pResult != pBase); Assert(pResult != pBase); Assert(pResult != pExponent); Assert(pResult != pModulus);
1866	AssertReturn(pResult->fSensitive >= (pBase->fSensitive \| pExponent->fSensitive \| pModulus->fSensitive),
1867	VERR_BIGNUM_SENSITIVE_INPUT);
1868
1869	int rc = rtBigNumUnscramble(pResult);
1870	if (RT_SUCCESS(rc))
1871	{
1872	rc = rtBigNumUnscramble((PRTBIGNUM)pBase);
1873	if (RT_SUCCESS(rc))
1874	{
1875	rc = rtBigNumUnscramble((PRTBIGNUM)pExponent);
1876	if (RT_SUCCESS(rc))
1877	{
1878	rc = rtBigNumUnscramble((PRTBIGNUM)pModulus);
1879	if (RT_SUCCESS(rc))
1880	{
1881	if (!pExponent->fNegative)
1882	{
1883	pResult->fNegative = pModulus->fNegative; /* pBase ^ pExponent / pModulus; result = remainder. */
1884	rc = rtBigNumMagnitudeModExp(pResult, pBase, pExponent, pModulus);
1885	}
1886	else
1887	rc = VERR_BIGNUM_NEGATIVE_EXPONENT;
1888	rtBigNumScramble((PRTBIGNUM)pModulus);
1889	}
1890	rtBigNumScramble((PRTBIGNUM)pExponent);
1891	}
1892	rtBigNumScramble((PRTBIGNUM)pBase);
1893	}
1894	rtBigNumScramble(pResult);
1895	}
1896	return rc;
1897	}
1898

Note: See TracBrowser for help on using the repository browser.

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

Download in other formats: