bignum.cpp@ 52050

Last change on this file since 52050 was 52050, checked in by vboxsync, 11 years ago
RTMemSafer: Split generic from ring-3 specific page based implementation. Adjusted the ring-3 implementation to use RTMemPage when SUPR3PageAllocEx isn't available, and to separate the real data from the heap metadata to make finding the data just a little bit more difficult.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 60.6 KB

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

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

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

Download in other formats: