bignum.cpp@ 52291

Last change on this file since 52291 was 52290, checked in by vboxsync, 11 years ago
RTBigNum: Two assembly optimizations related to RTBigNumModExp. Use 64-bit element type on 64-bit hosts (instead of 32-bit everywhere). Fixed some bugs in the bit operations, which apparently didn't affect x86 or AMD64.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 70.5 KB

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

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

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

Download in other formats: